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

[mihaild]

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

Как не отличаются, если я привел конкретный пример, который "непосредственно" в логике первого порядка не записывается?

В теории множеств записываются. Я утверждаю, что все Ваши рассуждения в логике второго порядка формализуются в рамках ZF. А те, которые не формализуются, я объявлю необоснованными:)

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

[EminentVictorians]

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

В теории множеств записываются.

Так я ж не спорю. Я же не просто так написал слово "непосредственно. Вот же:

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

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

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

Я утверждаю, что все Ваши рассуждения в логике второго порядка формализуются в рамках ZF.

Я подумаю над примером, но это, очевидно, непростая задача.

[epros]

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

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

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

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

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

Собственно, если взять набор средств побогаче (логику второго порядка), то категоричность появляется.

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

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

С логикой второго порядка я пока мало знаком, но навскидку для меня она выглядит более приятной.

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

[zykov]

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

С логикой второго порядка я пока мало знаком, но навскидку для меня она выглядит более приятной.

Логика первого порядка обладает доказанными полезными свойствами:

Цитата:

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

1) полнота (это означает, что для любой замкнутой формулы выводима либо она сама, либо её отрицание);
2) непротиворечивость (ни одна формула не может быть выведена одновременно со своим отрицанием).

При этом если непротиворечивость более или менее очевидна, то полнота — нетривиальный результат, полученный Гёделем в 1930 году (теорема Гёделя о полноте). По сути теорема Гёделя устанавливает фундаментальную эквивалентность понятий доказуемости и общезначимости.

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

Согласно теореме Лёвенгейма — Скулема если множество формул имеет модель, то оно также имеет модель не более чем счётной мощности. С этой теоремой связан парадокс Скулема, который, однако, является лишь мнимым парадоксом.

Для логик второго и выше порядков таких свойств нет.
И не то чтобы не пытались.

[Mikhail_K]

mihaild
А какую литературу Вы бы посоветовали о логике второго порядка, стандартной семантике и семантике Хенкина?

[mihaild]

А не знаю литературы, я про них знаю только из когда-то прослушанного курса (где про них были полторы лекции). Есть 10 страниц в "Logic and structure" Далена (там он называет стандартную семантику principal models, а Хенкина all models).
Возможно как раз из-за отсутствия хороших дедуктивных систем про логики второго порядка вообще мало что можно сказать - показываем, что выводимость для второго порядка сводится к выводимости для первого, после чего становится не очень понятно, что нам собственно второй порядок дает.

[epros]

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

А какую литературу Вы бы посоветовали о логике второго порядка, стандартной семантике и семантике Хенкина?

Попробуйте Stewart Shapiro, Foundations without Foundationalism. A Case for Second-order Logic.

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

[Doctor Boom]

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

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

А что это за теория?

[mihaild]

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

А что это за теория?

Теория, аксиомами которой являются все истинные в натуральных числах утверждения.

[Geen]

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

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

А что это за теория?

Теория, аксиомами которой являются все истинные в натуральных числах утверждения.

А эта теория будет непротиворечивой?

[Padawan]

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

все истинные в натуральных числах утверждения.

А что это значит "истинные в натуральных числах"?

[mihaild]

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

А что это значит "истинные в натуральных числах"?

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

Geen в сообщении #1594140 писал(а):

А эта теория будет непротиворечивой?

При условии что натуральные числа существуют - будет:)

[Padawan]

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

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

Ничего не понял. Натуральное число (определяемое в ZF как элемент некоторого множества $N$) кодирует формулу (в какой сигнатуре?) выполненную в $N$? Что значит кодирует?

[zykov]

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

Что значит кодирует?

Видимо это про Set-theoretic definition of natural numbers.

[mihaild]

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

в какой сигнатуре?

В арифметической, конечно.

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

Что значит кодирует?

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

zykov в сообщении #1594148 писал(а):

Видимо это про Set-theoretic definition of natural numbers

Это скорее про https://en.wikipedia.org/wiki/G%C3%B6del_numbering (или что-то подобное - после Гёделя придумали более технически простые способы делать то же самое).