Природа натуральных чисел

[mathematician123]

mathematician123 в сообщении #1593287 писал(а):

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

Кстати, вот что подумал. А существуют ли утверждения о натуральных числах, независящие от аксиом ZFC? Я таких не встречал.

https://en.m.wikipedia.org/wiki/Diophantine_set
Раздел "Further applications".

Цитата:

Corresponding to any given consistent axiomatization of number theory,[4] one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.

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

[mihaild]

Doctor Boom в сообщении #1593577 писал(а):

Я просто другой тип утверждений имел ввиду

А как вы "типизируете" утверждения? Если показать Вам запись формулы $\Box_{PA} \ulcorner\bot\urcorner$, то Вам понадобится много времени, чтобы понять, что она что-то там говорит про арифметику и доказуемость:)

mathematician123 в сообщении #1593588 писал(а):

Правда непонятно, откуда тогда известно, что это диофантово уравнение не имеет решений

Есть разные подходы. Например можно по МТ составить уравнение, которое разрешимо тогда и только тогда, когда эта МТ останавливается. Ну а сделать МТ, вопрос остановки которой не зависит от ZFC, несложно.

[Doctor Boom]

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

А как вы "типизируете" утверждения? Если показать Вам запись формулы $\Box_{PA} \ulcorner\bot\urcorner$, то Вам понадобится много времени, чтобы понять, что она что-то там говорит про арифметику и доказуемость:)

Ну например, пусть существуют некие свойства $P$ и $Q$, на которые мы можем проверить нат числа. Тогда например утверждение "если нат.число удовлетворяет свойству $P$, то оно удовлетворяет свойству и $Q$" не зависит ни от каких аксиом, и имеет объективную истинность. В противном случае, если из какой-то системы аксиом следует, что это не так, то из этого следует существование контрпримера, который внезапно может найтись, тем самым доказав ошибочность системы аксиом и "независимость" от нашего мышления реальности натуральных чисел, существующей в платоновском мире идей
И еще вопрос, что вы думаете об аксиоматике, в которой можно доказать, что нечетные числа делятся на два? Она будет ложной, или такое нельзя сказать про систему аксиом?

[mihaild]

Doctor Boom в сообщении #1593679 писал(а):

Тогда например утверждение "если нат.число удовлетворяет свойству $P$, то оно удовлетворяет свойству и $Q$" не зависит ни от каких аксиом, и имеет объективную истинность.

Ну например утверждение "если число кодирует противоречивость арифметики, то оно равно нулю".

Doctor Boom в сообщении #1593679 писал(а):

В противном случае, если из какой-то системы аксиом следует, что это не так, то из этого следует существование контрпримера

Это называется $\omega$-непротиворечивостью: не бывает такого, что теория доказывает $P(0)$, $P(1)$ и т.д., но доказывает $\exists x: \neg P(x)$.

Doctor Boom в сообщении #1593679 писал(а):

И еще вопрос, что вы думаете об аксиоматике, в которой можно доказать, что нечетные числа делятся на два?

Ну, если она содержит хотя бы арифметику Пресбургера (а иначе вообще непонятно, почему мы какие-то её термы сопоставляем нечетным числам и делимости на два), то она будет противоречивой. "Ложными" аксиоматики не бывают.

[Doctor Boom]

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

Ну например утверждение "если число кодирует противоречивость арифметики, то оно равно нулю".

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

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

Ну, если она содержит хотя бы арифметику Пресбургера

А может не содержать?

-- 13.05.2023, 03:54 --

mihaild
Вы согласны с тем, что не существуют две непротиворечивые аксиоматики, которые дают противоположные ответы на вопрос бесконечности простых пар близнецов?

[mihaild]

Doctor Boom в сообщении #1593714 писал(а):

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

Я Вам советую прочитать где-нибудь доказательство теоремы Гёделя. Увидите, что формула "число кодирует протокол МТ" ничем принципиально от каких-то более понятных арифметических формул не отличается.
Ну ладно, не хотите так - утверждение "число является корнем вот такого диофантова уравнения" Вас устраивает?

Doctor Boom в сообщении #1593714 писал(а):

А может не содержать?

Может, конечно. Мы можем взять значки $+$ и $1$ (вроде бы минимальные, необходимые для выражения понятий "нечетное число" и "делится на $2$"), и придать им вообще произвольный смысл.

Doctor Boom в сообщении #1593714 писал(а):

Вы согласны с тем, что не существуют две непротиворечивые аксиоматики, которые дают противоположные ответы на вопрос бесконечности простых пар близнецов?

Так, давайте всё же построже. Чтобы вообще было осмысленно говорить о том, что теория что-то утверждает про близнецы, нужны некоторые условия на неё. Например можно потребовать, чтобы в ней интерпретировалась арифметика Робинсона. Ну и я совершенно не уверен, что арифметика Робинсона (или даже Пеано) отвечает на вопрос о бесконечности близнецов.

[mihaild]

Doctor Boom в сообщении #1593714 писал(а):

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

Я Вам советую прочитать где-нибудь доказательство теоремы Гёделя. Увидите, что формула "число кодирует протокол МТ" ничем принципиально от каких-то более понятных арифметических формул не отличается.
Ну ладно, не хотите так - утверждение "число является корнем вот такого диофантова уравнения" Вас устраивает?

Doctor Boom в сообщении #1593714 писал(а):

А может не содержать?

Может, конечно. Мы можем взять значки $+$ и $1$ (вроде бы минимальные, необходимые для выражения понятий "нечетное число" и "делится на $2$"), и придать им вообще произвольный смысл.

Doctor Boom в сообщении #1593714 писал(а):

Вы согласны с тем, что не существуют две непротиворечивые аксиоматики, которые дают противоположные ответы на вопрос бесконечности простых пар близнецов?

Так, давайте всё же построже. Чтобы вообще было осмысленно говорить о том, что теория что-то утверждает про близнецы, нужны некоторые условия на неё. Например можно потребовать, чтобы в ней интерпретировалась арифметика Робинсона. Ну и я совершенно не уверен, что арифметика Робинсона (или даже Пеано) отвечает на вопрос о бесконечности близнецов.

[EminentVictorians]

mihaild, а не знаете, вот этот результат про диофантово уравнение - он относится только к теориями первого порядка или порядок логики здесь ни при чем? (Просто насколько я понял, достаточно, чтобы теория содержала арифметику Робинсона; но "теория" тут обязательно первого порядка или вообще любая - я не понял)

[Doctor Boom]

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

Ну ладно, не хотите так - утверждение "число является корнем вот такого диофантова уравнения" Вас устраивает?

Да

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

Может, конечно. Мы можем взять значки $+$ и $1$ (вроде бы минимальные, необходимые для выражения понятий "нечетное число" и "делится на $2$"), и придать им вообще произвольный смысл.

Короче, осмысленная не может

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

Например можно потребовать, чтобы в ней интерпретировалась арифметика Робинсона. Ну и я совершенно не уверен, что арифметика Робинсона (или даже Пеано) отвечает на вопрос о бесконечности близнецов.

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

[mihaild]

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

а не знаете, вот этот результат про диофантово уравнение - он относится только к теориями первого порядка или порядок логики здесь ни при чем?

Тут вопрос в том, как именно формулировать этот результат - его можно понимать двумя способами, которые для первого порядка эквивалентны, а для второго нет.
Явно выпишу термины (пригодится в любом случае в этой теме).
Пусть у нас есть исчисление (правила записи формул), дедуктивная система (правила, по которым из одних формул выводятся другие) и класс моделей. Мы говорим, что дедуктивная система корректна относительно класса моделей, если для любой модели из этого класса из истинных в этой модели формул дедуктивная система выводит только истинные в этой модели формулы. Мы говорим, что дедуктивная система полна относительно класса моделей, если для любого набора утверждений $X$ любая формула, следующая из него синтаксически (т.е. истинная во всех моделях, в которых выполнены все формулы из $X$), выводится в этой дедуктивной системе.
Для классического исчисления предикатов есть классическая же семантика (класс моделей - интерпретируем предикатные символы, дальше рекурсивно), и классические правила вывода, и эти правила вывода корректны и полны. Т.е. если у нас какое-то утверждение не зависит от теории, то у этой теории есть как модели, в которых утверждение выполнено, так и в которых не выполнено.
С логикой второго порядка со стандартной семантикой есть проблема, из-за которой лично мне вся эта история про большую выразительность кажется жульничеством (хотя, конечно, математические результаты в этой области вполне нормальные и строгие, мне именно околофилософская обвязка вокруг не нравится) - для неё не существует полной корректной эффективной (т.е. в которой доказательства можно проверять алгоритмически) дедуктивной системы.

Возвращаясь к диофантовым уравнениям, результат Матиясевича, благодаря совпадению в логике первого порядка выводимости и общезначимости, можно сформулировать двумя способами:
1) для любой (перечислимой) теории, содержащий арифметику, существует диофантово уравнение, такое что ни наличие ни отсутствие корней у этого уравнения в этой теории не доказуемо
2) для любой (перечислимой) теории, содержащий арифметику, существует диофантово уравнение, такое что ни наличие ни отсутствие корней у этого уравнения в моделях этой теории не общезначимо

В теориях второго порядка со стандартной семантикой вторая формулировка просто неверна: арифметика Пеано второго порядка категорична в стандартной семантике (т.е. все её модели изоморфны), и, соответственно, любое уравнение либо разрешимо во всех моделях, либо не разрешимо ни в одной.
С первой же формулировкой в теориях второго порядка проблема, потому что непонятно, какую дедуктивную систему брать (для первого порядка есть хорошие выделенные системы, для второго нет). Если взять любую вычислимую корректную - то результат будет верен.

Doctor Boom в сообщении #1593764 писал(а):

Но даже если и не отвечает, то какие-нибудь отвечают? И вот могут они отвечать противоположно?

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

[Mikhail_K]

Doctor Boom в сообщении #1593764 писал(а):

какие-нибудь отвечают? И вот могут они отвечать противоположно? И что из этого следует

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

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

Мне со стороны кажется, что собеседники в этой теме говорят о разных вещах.

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

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

[Doctor Boom]

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

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

Да ладно, значит одна из них истинна, а другая ложна. Я даже знаю какая, потому что Беклемишев доказал, что бессмертного червя не существует

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

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

Как это не противоречит? Если натуральные числа объективны, то и истинность утверждений на них объективна, и пусть она положительна. Тогда если аксиомой добавить ее отрицание, то эта аксиома будет ложной, или давать противоречия? Но аксиомы ложными не бывают

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

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

А как определить интуитивность и верность аксиом? Ведь mihaild отрицает применимость верности к аксиомам

[EminentVictorians]

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

Мы говорим, что дедуктивная система полна относительно класса моделей, если для любого набора утверждений $X$ любая формула, следующая из него синтаксически (т.е. истинная во всех моделях, в которых выполнены все формулы из $X$), выводится в этой дедуктивной системе.

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

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

для неё не существует полной корректной эффективной (т.е. в которой доказательства можно проверять алгоритмически) дедуктивной системы.

Ну я не вижу, чем здесь можно пожертвовать, кроме как полнотой. Но вообще, я не знаю, как к этому относиться. Выглядит очень грустно. Хотя с другой стороны... Я постоянно чувствую подставу в таких "общих" теоретических результатах. Ну будут истинные утверждения, верные во всех моделях, которые мы не сможем вывести. А так ли это плохо? Найдутся ли среди этих утверждений те, которые нам будут интересны? Просто мне кажется, что это еще не конец. И про такие утверждения должны быть какие-то результаты. Если Вам вдруг встречались такие - буду благодарен, если поделитесь.

[Mikhail_K]

Doctor Boom в сообщении #1593797 писал(а):

Как это не противоречит? Если натуральные числа объективны, то и истинность утверждений на них объективна, и пусть она положительна. Тогда если аксиомой добавить ее отрицание, то эта аксиома будет ложной, или давать противоречия? Но аксиомы ложными не бывают

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

[mihaild]

Doctor Boom в сообщении #1593797 писал(а):

Да ладно, значит одна из них истинна, а другая ложна.

Ага, а еще либо элементарная теория $\mathbb Z_2$, либо элементарная теория $\matrhbb Z_3$, либо обе сразу ложны.

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

Только наверное "следующая из него семантически".

Да, опечатка.

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

Ну я не вижу, чем здесь можно пожертвовать, кроме как полнотой

Еще можно отказаться от стандартной семантики. Относительно семантики Хенкина полные дедуктивные системы есть (в ней больше моделей, значит меньше общезначимых формул).

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

Ну будут истинные утверждения, верные во всех моделях, которые мы не сможем вывести. А так ли это плохо? Найдутся ли среди этих утверждений те, которые нам будут интересны?

А чем Вас тогда не устраивает логика первого порядка?