Недоказуемое

[Padawan]

И как это число кодирует доказательство противоречивости? Можно ли по это кодировке восстановить доказательство противоречивости?

[EminentVictorians]

Padawan в сообщении #1567395 писал(а):

Насчёт аксиом Пеано - они категоричны, если аксиому индукции сформулировать в логике второго порядка: для любого множества $A\subset \mathbb N$ из того, что $1\in A$ и $\forall n\in A\Rightarrow n+1\in A$ следует $A=\mathbb N$.

Да мне вообще кажется, что логика второго порядка ближе к тому, как мы мыслим, чем логика первого порядка. Ну хуже у нее теоретико-модельные свойства, и что теперь. По мне так это не должно быть проблемой. К сожалению, я с ней совсем мало знаком, чтобы сказать что-то внятное.

-- 23.10.2022, 11:53 --

Кстати теоремы Геделя останутся справедливыми если взять логику второго порядка?

[Anton_Peplov]

EminentVictorians в сообщении #1567403 писал(а):

Кстати теоремы Геделя останутся справедливыми если взять логику второго порядка?

Anton_Peplov в сообщении #1297668 писал(а):

В максимальной (видимо) общности теорема Гёделя о неполноте сформулирована Клини в 1943 г.

Если на языке формальной системы для любого натурального числа $n$ можно выразить утверждение "универсальный алгоритм остановится, получив на вход число $n$", то такая система либо противоречива, либо неполна. Поскольку, будь она полна, алгоритм, для каждого $n$ перебирающий все доказательства подряд, пока одно из них не окажется доказательством утверждения "универсальный алгоритм остановится, получив на вход число $n$" или его отрицания, всегда останавливался бы, и тем самым, если система непротиворечива, решал проблему останова. Но известно, что проблема останова алгоритмически неразрешима.

[mihaild]

Padawan в сообщении #1567399 писал(а):

И как это число кодирует доказательство противоречивости?

Как-то. Могу наврать, но кажется если мы разрешим схему вывода $A \vdash A$, то например "последовательность" $\top, \top, \ldots, \ldots, \bot, \bot$ (бесконечно вправо $\top$, потом бесконечно слева $\bot$) вполне является нестандартным доказательством противоречия.
Но в любом случае, такое число точно есть. Добавьте к PA аксиому "PA противоречива" - получится непротиворечивая теория, значит у неё есть модель.

[warlock66613]

EminentVictorians в сообщении #1567403 писал(а):

Кстати теоремы Геделя останутся справедливыми если взять логику второго порядка?

Там всё сложнее, чем в первом порядке. Есть стандартная семантика — в ней арифметика категорична, нет нестандартных моделей. Но при этом не существует дедуктивной системы, для которой логика второго порядка со стандартной семантикой полна. Есть семантика Хенкина — для логики с ней доказан аналог теоремы о полноте, но одновременно на неё переносятся и все проблемы и особенности логики первого порядка, вплоть до того, что логика второго порядка с семантикой Хенкина оказывается не более выразительна чем логика первого порядка.

[Skipper]

Доказательства утверждений - типа "рациональных чисел не больше чем натуральных", или "вещественных чисел явно больше чем рациональных", используют такой подход, как переходы к бесконечностям.

Но с таким подходом, можно доказать разные кажущиеся нелепостью, утверждения.

Вот я например, сейчас докажу следующее -
Теорема. Существует чётное число, которое больше чем все простые числа.

Доказательство. Пусть $M$ - множество всех простых чисел. И нам неважно, бесконечное оно или конечное, пусть мы этого не знаем и вообще живём раньше Евклида.
Перемножим все числа этого множества между собой, и прибавим $2$, назовём его $B$ . Получившееся число явно чётное - так как оба слагаемых делятся на $2$, прибавленная двойка , произведение всех простых, так как там есть множитель двойка.
Также, это число явно больше чем все числа из множества $M$ - всех простых чисел, потому что при перемножении положительных чисел, их произведение может быть только больше или равно, а при суммировании то же самое.
Вывод - мы получили чётное число $B$, которое больше чем все простые числа.
Теорема доказана.

Не кажется ли эта теорема бредом?
Но вот аналогичные суждения используются и в утверждениях выше, что например рациональных чисел не больше чем натуральных (а я считаю что больше явно, и вообще это как аксиому принять хочу), (или что вещественных больше чем рациональных),

[Gagarin1968]

Skipper в сообщении #1567513 писал(а):

Теорема. Существует чётное число, которое больше чем все простые числа

А на самом деле Вы доказали теорему: какое бы простое число мы ни взяли, всегда найдётся превосходящее его чётное число.

Skipper в сообщении #1567513 писал(а):

нам неважно, бесконечное оно или конечное, пусть мы этого не знаем и вообще живём раньше Евклида

Очень важно. Евклид (как и греки до него) не оперировал понятием бесконечности.

[Skipper]

Gagarin1968 в сообщении #1567514 писал(а):

А на самом деле Вы доказали теорему: какое бы простое число мы ни взяли, всегда найдётся превосходящее его чётное число.

Если "какое бы простое число мы ни взяли, всегда найдётся превосходящее его чётное число" - верно, то это может означать, и то что больше этого чётного числа также есть другие простые.

А моё утверждение более сильное - моё чётное число $B$, больше чем все простые числа, потому что по определению, мы взяли в начале доказательства, "$A$ - множество всех простых чисел ".
А значит, нету больших простых чисел чем наше полученное в моей теореме чётное число $B$,

[Gagarin1968]

Skipper в сообщении #1567519 писал(а):

моё чётное число $B$, больше чем все простые числа

Skipper
А можно Вас попросить записать это высказывание формально. Я хочу взглянуть, как число может быть больше множества!

[EminentVictorians]

Skipper в сообщении #1567513 писал(а):

Перемножим все числа этого множества между собой

Операция умножения определена для двух аргументов. Если операция ассоциативна, то можно перемножать произвольное конечное число аргументов, не заботясь о расстановке скобок (но заботясь о порядке их следования). Вы пытаетесь перемножить бесконечное число слагаемых. Такая операция просто напросто не определена. Можно вместо "перемножить" взять другое действие: рассмотреть бесконечное произведение (разница такая же как между суммой и рядом). Ряд, в отличие от суммы, может быть расходящимся. Поэтому, когда Вы говорите о "перемножении" бесконечного числа слагаемых, Вы на самом деле рассматриваете бесконечное произведение. Ну а если Вы рассматриваете бесконечное произведение, Вы должны сразу указывать множество конечных подмножеств (это те, для которых определено произведение) и фильтр на этом множестве (чтобы понимать, в каком смысле сходимость). Ни то, ни другое Вы не предоставили. Если взять самое очевидное, просто "последовательное перемножение", то такое произведение, очевидно, расходится. У него нет конечного результата, поэтому прибавить к нему двойку Вы не можете. Отличие от доказательства Евклида о бесконечности простых в том, что Евклид перемножает только конечное множество чисел, так что у него все корректно.

[Mikhail_K]

Skipper в сообщении #1567513 писал(а):

Доказательства утверждений - типа "рациональных чисел не больше чем натуральных", или "вещественных чисел явно больше чем рациональных", используют такой подход, как переходы к бесконечностям.

Во всяком случае, в этих доказательствах не используется такое понятие, как произведение бесконечного количества чисел:

Skipper в сообщении #1567513 писал(а):

Пусть $M$ - множество всех простых чисел. И нам неважно, бесконечное оно или конечное, пусть мы этого не знаем и вообще живём раньше Евклида. Перемножим все числа этого множества между собой

Перед тем как что-то перемножать, надо убедиться, что произведение вообще определено. Произведение двух чисел - определено. На основе этого можно определить произведение любого конечного количества чисел. Можно определить и бесконечное произведение, но оно не всегда будет существовать. Поэтому, если мы не знаем, сколько чисел в множестве, мы не можем просто так взять и перемножить их все - такая операция, вообще говоря, не определена.

В доказательствах же теорем о сравнении мощностей различных множеств ($\mathbb{N}$, $\mathbb{Q}$, $\mathbb{R}$ и др.) бесконечные множества, конечно, присутствуют, но не используются никакие операции, которые не были ранее определены или аксиоматически описаны.

[Skipper]

Gagarin1968 в сообщении #1567520 писал(а):

Skipper в сообщении #1567519 писал(а):

моё чётное число $B$, больше чем все простые числа

Skipper
А можно Вас попросить записать это высказывание формально. Я хочу взглянуть, как число может быть больше множества!

Другими словами, моё четное число больше любого простого числа из множества всех простых чисел,

-- Пн окт 24, 2022 20:28:31 --

EminentVictorians в сообщении #1567521 писал(а):

просто "последовательное перемножение", то такое произведение, очевидно, расходится. У него нет конечного результата,

Это вы принимаете, как аксиому, т.е. само собой разумеющееся. "Нет конечного результата" . Но аналогично и при сравнении множеств натуральных и рациональных чисел, я могу утверждать, что "нет конечного результата". В моём случае при перемножении - потому что мы не дождёмся этого перемножения, что вы и указали,
т.к. бесконечно долго надо ждать, а при сравнении , т.е. составлении в соответствие всех натуральных чисел и всех рациональных чисел, множества $N$ и $Q$, аналогично, дождаться пока они все пройдут соответствие невозможно, надо бесконечно долго ждать.

Поэтому кажущееся интуитивным представление - если множество $N$ является подмножеством $Q$, а там остаются и другие числа, уже ненатуральные, можно принять как аксиому, что рациональных чисел больше чем натуральных,

-- Пн окт 24, 2022 20:32:53 --

Mikhail_K в сообщении #1567559 писал(а):

Во всяком случае, в этих доказательствах не используется такое понятие, как произведение бесконечного количества чисел

Но можно аксиоматизировать, что оно существует. Ведь аксиоматизируют же "существование" разных бесконечных множеств, и даже бОльших по мощности чем мощность континуума, так почему тогда я не могу принять как аксиому существование некоего реального числа, которое содержит в качестве делителя все простые из множества всех простых. А потом к нему и двойку добавить,

[Mikhail_K]

Skipper в сообщении #1567586 писал(а):

Но можно аксиоматизировать, что оно существует. Ведь аксиоматизируют же "существование" разных бесконечных множеств, и даже бОльших по мощности чем мощность континуума

Нет, аксиоматизировать стараются только самый необходимый минимум для математических рассуждений. Аксиома бесконечности, фактически, утверждает существование множества натуральных чисел. Ещё для каждого множества утверждается существование множества его подмножеств. И ещё несколько таких же естественных вещей, без которых сложно было бы и обычный математический анализ построить. А тогда множества высоких мощностей, типа гиперконтинуума, получаются сами собой, их аксиоматизировать уже не нужно.

Другое дело, что можно рассмотреть и менее очевидные аксиомы, например утверждающую существование недостижимых кардиналов. Но это своего рода игра, интересно посмотреть, какие выводы получатся из такой аксиомы, но никто не считает такую аксиому сколько-нибудь самоочевидной.

Skipper в сообщении #1567586 писал(а):

так почему тогда я не могу принять как аксиому существование некоего реального числа, которое содержит в качестве делителя все простые из множества всех простых.

Если Вы примете за аксиому существование такого натурального числа, то получите противоречие. Потому что это число плюс один, с одной стороны, будет простым, а с другой стороны, будет больше всех простых. Очевидно противоречивые системы аксиом в математике мало кого интересуют.

Если же Вы постулируете существование такого объекта, не относя его к натуральным числам - то как хотите, только пользы от него никакой не видно. Кстати, тогда Вы должны будете пояснить, что вообще такое "делитель" этого числа, и можно ли к такому числу что-нибудь прибавлять, и какими свойствами будет обладать такая операция сложения. Для натуральных чисел это ясно, а для Вашего постулированного числа - надо будет постулировать. Причём так, чтобы противоречие не получить.

[mihaild]

Skipper в сообщении #1567513 писал(а):

используют такой подход, как переходы к бесконечностям

Что это такое?
Доказательство утверждения "множество рациональных чисел равномощно множеству натуральных" использует определения и аксиомы (точнее только аксиомы, определения используются для его формулировки).

Mikhail_K в сообщении #1567592 писал(а):

Потому что это число плюс один, с одной стороны, будет простым, а с другой стороны, будет больше всех простых

Нет же. Оно будет всего лишь иметь простой множитель, не принадлежащий множеству всех простых чисел.

[Mikhail_K]

mihaild в сообщении #1567620 писал(а):

Оно будет всего лишь иметь простой множитель, не принадлежащий множеству всех простых чисел.

Нет ли в этом предложении противоречия?