Достаточные свойства для понятия "натуральное число"

[epros]

AGu в сообщении #1005890 писал(а):

«Аксиома индукции в аксиомах Пеано фактически требует использования логики второго порядка» — неправда, потому что это не аксиома, а схема аксиом, и не второго порядка, а первого (и Вы наверняка это знаете).

Вообще-то в логике второго порядка индукция действительно определяется одной аксиомой. В логике первого порядка её одной аксиомой сформулировать невозможно, поэтому приходится определять схему.

Вопрос действительно сформулирован не очень понятно. Могу предположить такой перевод: "Является ли определение натурального числа в логике первого порядка однозначным?" И ответ на этот вопрос: "Нет". Потому что арифметика Пеано первого порядка имеет множество неизоморфных моделей, в некоторых из которых существуют т.н. "нестандартные" натуральные числа (это такие числа, которые больше любого стандартного). Раз мы не можем однозначно из аксиоматики определить, являются ли такие нестандартные числа натуральными, значит аксиоматика определяет натуральные числа неоднозначно.

Арифметика Пеано второго порядка имеет единственную модель (в полной семантике). Но с ней проблемы похуже...

[kp9r4d]

epros в сообщении #1005986 писал(а):

Арифметика Пеано второго порядка имеет единственную модель (в полной семантике). Но с ней проблемы похуже...

Какие?

[epros]

kp9r4d в сообщении #1005989 писал(а):

epros в сообщении #1005986 писал(а):

Арифметика Пеано второго порядка имеет единственную модель (в полной семантике). Но с ней проблемы похуже...

Какие?

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

[Brukvalub]

Наверное, подразумеваются трудности типа теоремы Гудстейна или чего-то похожего.

[epros]

Теорема Гудстейна, кстати, в арифметике второго порядка доказуема.

[kp9r4d]

То есть, по сути, утверждение об однозначности арифметики второго порядка истинно, но не доказуемо?

[epros]

kp9r4d в сообщении #1005996 писал(а):

То есть, по сути, утверждение об однозначности арифметики второго порядка истинно, но не доказуемо?

Хм. Я понимаю, что практически это и сказал, но всё-таки это не совсем то, что я хотел сказать. Вся тонкость в том, что считать легитимным доказательством. С формальной точки зрения, если принять за аксиому, что "драконы существуют", то это сразу станет "доказуемым фактом". Однако ж такое доказательство не очень убедительно...

С арифметикой второго порядка ситуация примерно такая: То, что у неё единственная модель, следует практически из её же собственной аксиоматики (аксиома индукции примерно это и утверждает). В этом смысле однозначность определения натуральных чисел конечно доказана. Вот только это доказательство (как и доказательство существования драконов) не является конструктивным. Т.е. вполне может оказаться так, что для некоторого конкретного объекта невозможно будет ни доказать, ни опровергнуть, что он является натуральным числом.

[arseniiv]

epros в сообщении #1006069 писал(а):

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

А как выразить «$a$ является/не является натуральным числом» в арифметике второго порядка? В арифметике первого вот это никак не написать дословно, разве что $a=a,a\ne a$. Если всё правильно понимаю, арифметика второго порядка с этой стороны ничем не лучше.

-- Пн апр 20, 2015 23:49:03 --

(Тогда, какой бы мы терм ни взяли, для него всегда будет доказуемо $t=t$ и никогда, если арифметика не противоречива, $t\ne t$, и вопроса как бы и нет. Так что я точно что-то не так понимаю.)

[kp9r4d]

epros
Спасибо, примерно понятно.

[epros]

arseniiv в сообщении #1006079 писал(а):

А как выразить «$a$ является/не является натуральным числом» в арифметике второго порядка?

Зачем в арифметике? В языке логики второго порядка. Куайн даже называл логику второго порядка "теорией множеств в овечьей шкуре", поскольку в ней можно выразить всё, выразимое на языке множеств. И предикат "является натуральным числом" выразим одной формулой -- именно потому, что арифметика второго порядка конечно аксиоматизируема (в отличие от арифметики первого пррядка).

[arseniiv]

А какой формулой-то?

[AGu]

epros в сообщении #1006150 писал(а):

предикат "является натуральным числом" выразим одной формулой -- именно потому, что арифметика второго порядка конечно аксиоматизируема (в отличие от арифметики первого пррядка).

Я тоже слегка заинтригован. Подозреваю, что epros, произнося известные нам слова, вкладывает в них неизвестный нам смысл. Вероятно, речь идет, как и раньше, всего лишь о категоричности арифметики второго порядка в рамках теории множеств. (И тогда она была выражена очень странными словами.)

[epros]

arseniiv в сообщении #1006151 писал(а):

А какой формулой-то?

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

[Anton_Peplov]

epros
А теперь, пожалуйста, книгу, в которой обо всем этом можно прочитать.
Дико заинтриговали.

[AGu]

epros в сообщении #1006325 писал(а):

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

При чем тут второй порядок??? Это же классическое определение множества натуральных чисел в самой обычной теории множеств первого порядка.