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

[EminentVictorians]

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

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

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

Ну и банально. Кто-нибудь (допустим Коэн) доказал, что утверждение $A$ (допустим континуум гипотеза) не зависит от аксиом некоторой формальной теории первого порядка (например, ZFC). Для меня в этом результате нету глубокого смысла, т.к. я просто подумаю, что "Это же логика первого порядка; она просто слишком бедная и не допускает формализацию каких-то нормальных, логичных рассуждений. Была бы логика получше, не было бы никакой независимости, а был бы просто ответ "да"/"нет" и все." Да, в логике второго порядка такое тоже может быть. Но я хочу верить, что в ней это гораздо более редкое явление. (А в идеале, чтобы была какая-нибудь теорема, типа что любое такое утверждение будет, например, слишком длинным. А значит "человеко-ориентированным" теоремам ничто не угрожает. )

[Mikhail_K]

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

При "обычных" (т.е. на естественном языке) доказательствах я на всю катушку использую кванторы второго порядка.

А приведите пример, где Вы их используете. Вот Вы писали как-то:

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

Да элементарно кванторы по множествам (по всяким функциям, операторам, подмножествам и т.д.). А это логика второго порядка

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

[zykov]

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

При "обычных" (т.е. на естественном языке) доказательствах я на всю катушку использую кванторы второго порядка.

Сильно сомневаюсь.
Как раз логика первого порядка соответсвует "бытовой" логике. Поэтому почти везед и используется.

[EminentVictorians]

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

А приведите пример, где Вы их используете.

Ну вот в топологии, например, иногда приходится говорить: "для любой окрестности $U$ точки $x$...". Или в алгебре: "для любой подгруппы $S$ группы $G$...". Это же квантификация по подмножествам. Я понимаю, что конкретно эти выражения можно переформулировать в ZFC. Но хочется смотреть на них как на готовые низкоуровневые высказывания в духе $\forall U (x \in U \to ...)$. Я не вижу причин считать, что такие высказывания нуждаются в еще какой-то более низкоуровневой формализации.

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

-- 13.05.2023, 23:47 --

А, кстати помню что-то такое. Но не про ZFC, а про PA. Где-то видел какое-то банальнейшее утверждение про натуральные числа, которое при формализации завязывались на какую-то супер нетривиальную теорему (вроде бы теорему Лагранжа о четырех квадратах). Ну т.е. чтобы сформулировать в PA какое-то обычное свойство (типа положительности или что-то такое же банальное), приходилось использовать разложение в сумму четырех квадратов. Извините, что сумбурно. Я совсем плохо помню эту историю (но вроде бы я ее как раз здесь, на форуме, и увидел; если найду - напишу ссылку). Вот я боюсь, что в ZFC может быть так же.

-- 13.05.2023, 23:51 --

Ой, стоп. Плохой пример с окрестностью. Лучше так: $\forall U (U \subset V \to ...)$.

[Mikhail_K]

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

Это же квантификация по подмножествам.

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

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

А, кстати помню что-то такое. Но не про ZFC, а про PA. Где-то видел какое-то банальнейшее утверждение про натуральные числа, которое при формализации завязывались на какую-то супер нетривиальную теорему (вроде бы теорему Лагранжа о четырех квадратах). Ну т.е. чтобы сформулировать в PA какое-то обычное свойство (типа положительности или что-то такое же банальное), приходилось использовать разложение в сумму четырех квадратов.

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

[EminentVictorians]

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

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

Не понимаю. Вот рассматриваем мы, например, какое-нибудь нигде не плотное множество $M$ в топологическом пространстве $X$. Вот я начинаю рассуждать: "Берем произвольное подмножество $P \subset M$ такое что $P \in \Omega$. Тогда $P = \varnothing$." Разве это не квантификация по предикату? Я хочу написать $\forall P (P \subset M \wedge P \in \Omega \to P = \varnothing)$ (ну разве что раскрывая $\subset$ и $\varnothing$). Но в ZFC же так прямолинейно не напишешь. По-моему, именно из-за квантификации по предикату. (Конкретно это я могу перевести в ZFC, но речь то о положении в целом)

[zykov]

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

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

Я тоже особо не знаю примеров.
Математики работющие в области логики исследуют логики высших порядков.
В других разделах математики оно как-то не нужно.

Единственный пример - схема индукции в Пеано. Либо логика второго порядка, либо это схема.

[mihaild]

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

При "обычных" (т.е. на естественном языке) доказательствах я на всю катушку использую кванторы второго порядка

Те части логики второго порядка, которые Вы используете, формализуются и в логике первого порядка. Собственно рассуждения в логике второго порядка ничем принципиально не отличаются. Отличаются модели - мы объявляем, что у нас есть некоторая магическая стандартная семантика, которая произвольным образом запрещает часть моделей, чтобы получить категоричность.

[Doctor Boom]

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

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

А как тогда эти теории отличить, кто из них кто?
И наверное ни одна теория не будет полностью верно описывать натуральные числа из-за теоремы Геделя?

[mathematician123]

(Оффтоп)

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

Где-то видел какое-то банальнейшее утверждение про натуральные числа, которое при формализации завязывались на какую-то супер нетривиальную теорему (вроде бы теорему Лагранжа о четырех квадратах).

Скорее всего не то, но как раз про теорему Лагранжа. Есть такая задача: доказать, что проблема разрешимости диофантового уравнения в целых числах эквивалентна проблеме разрешимости диофантового уравнения в натуральных числах. В одну сторону легко доказывается. Уравнение $f(x_1, x_2, \ldots, x_n) = 0$ разрешимо в целых числах тогда и только тогда, когда уравнение $f(y_1 - y_2, y_3 - y_4, \ldots, y_{2n-1} - y_{2n}) = 0$ разрешимо в натуральных числах. А для доказательства в обратную сторону обычно используют теорему Лагранжа. Уравнение $f(x_1, x_2, \ldots, x_n) = 0$ разрешимо в натуральных числах, тогда и только тогда, когда уравнение $f(y_1^2 + y_2^2 + y_3^2 + y_4^2, \ldots, y_{4n-3}^2 + y_{4n-2}^2 + y_{4n-1}^2 + y_{4n}^2) = 0$ разрешимо в целых числах.

[mihaild]

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

И наверное ни одна теория не будет полностью верно описывать натуральные числа из-за теоремы Геделя?

Элементарная теория натуральных чисел будет:) Правда её аксиомы выписать не получится.

[epros]

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

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

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

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

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

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

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

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

[EminentVictorians]

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

Собственно рассуждения в логике второго порядка ничем принципиально не отличаются.

Я все равно не понимаю. Как не отличаются, если я привел конкретный пример, который "непосредственно" в логике первого порядка не записывается? Да хотя бы та же аксиома индукции в PA второго порядка. Это же именно рассуждение, которое "непосредственно" в первопорядковой логике тоже не формализуется.

[epros]

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

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

Собственно рассуждения в логике второго порядка ничем принципиально не отличаются.

Я все равно не понимаю. Как не отличаются, если я привел конкретный пример, который "непосредственно" в логике первого порядка не записывается? Да хотя бы та же аксиома индукции в PA второго порядка. Это же именно рассуждение, которое "непосредственно" в первопорядковой логике тоже не формализуется.

Я бы сказал, что рассуждения кое-в чём всё же отличаются. А конкретно - в том, что логика второго порядка разрешает квантификацию предикатов, невыразимых в языке. Казалось бы, что это может дать, раз мы всё равно не можем указать такой предикат в формуле, ибо не имеем возможности его записать? А вот и нет. Например, представьте, что у нас есть последовательность формул $\varphi_i$, где $i$ - не переменная, а просто числовой индекс формулы. Для наглядности можно даже вообразить, что с увеличением $i$ неограниченно возрастает длина формулы (количество знаков). При этом каждую следующую формулу можно в каком-то смысле трактовать как "уточнение" предыдущих, так что "в пределе" мы надеемся получить "точную формулу" (вот только ограничения языка теории таковы, что эта "предельная формула" никак не может получиться конечной). Так вот, логика второго порядка позволяет свободно оперировать такими "не формулами". Например, если мы знаем, что у всех формул последовательности есть свободная переменная $x$, то мы можем применить индукцию по $x$ не только к каждой формуле последовательности, но и к тому "предельному случаю", который, как мы знаем, формулой языка невыразим. Просто обозначим его как-то (типа $\varphi_{\infty}$), и все дела.

-- Вс май 14, 2023 17:11:41 --

Кстати, EminentVictorians, вот в этой теме Вы излагаете довольно интересную философию. Интересную тем, в том числе, что она практически диаметрально противоположна моей.

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

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

[EminentVictorians]

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

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

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

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

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

С множествами могу согласиться. Но как можно иметь 2 разных представления о натуральных числах - не понимаю. Ну точнее может быть как в примере с теоремой Гудстейна. Один верит в законность трансфинитной индукции, другой не верит. Для одного доказательство есть, для другого нету. Но иметь 2 аксиоматики, обе из которых основаны на самоочевидных вещах, но не тождественны (в точности то, о чем сказал Mikhail_K выше) - не представляю.

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

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

Так они появляются только в теориях первого порядка. Я то считаю, что это аргумент в пользу слабости $PA$ первого порядка или даже слабости всей логики первого порядка. Для меня тут нету мистики: взяли какой-то кастрированный набор средств и сказали "барахтайся как хочешь". Ну и что удивительного, что этим набором средств не получается дотянуться до некоторых концепций (в частности он не улавливает категоричность натуральных чисел). Но имхо это проблема набора средств, а не натуральных чисел. Собственно, если взять набор средств побогаче (логику второго порядка), то категоричность появляется.

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

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

Да, я как-то так и думаю. По крайней мере про несовершенство логики первого порядка точно согласен.

С логикой второго порядка я пока мало знаком, но навскидку для меня она выглядит более приятной. Мне нравится, что в ней чувствуется какая-то индоктринация теорией множеств. Ощущается так, будто какие-то базовые теоретико-множественные концепции уже "вшиты" в логику второго порядка. И мне это очень нравится. Так что на нее у меня пока есть надежды.