Определение натурального числа

[arseniiv]

Можно предложить Sicker установить их эквивалентность. Тогда уж точно мимо понимания трудно пролететь.

А мне нравится определение $\mathrm{Nat} = \mu N.1+N$ (частично шутка).

[epros]

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

Предикат $\mathbb{N}(x)$, читаемый как "x является натуральным числом", определяется формулой:
$\forall X~((X(1) \wedge \forall x~X(x) \to X(x+1)) \to (\forall x~\mathbb{N}(x) \to X(x)))$

Однако, если прочитать эту формулу, интерпретируя предикатные символы как "множества", то она прозвучит именно так, что $\mathbb{N}$ - минимальное индуктивное множество.

[Sicker]

iifat в сообщении #1298578 писал(а):

Ну и где вдруг отрицательные-то пойдут?

Можно не называть их отрицательными, а каким-то другим термом обозначить

iifat в сообщении #1298578 писал(а):

К какому положительному числу надо прибавить единицу, чтоб отрицательное появилось?

А как это требование следует из определения? Мы в принципе можем никак специально не выделять эти множества.

DeBill в сообщении #1298661 писал(а):

Вы упорно игнорируете уже неоднократно упоминавшееся (и пропущенное в Вашем "определении") требование "наименьшести".

А как вы доказываете наименьшесть?

-- 22.03.2018, 03:01 --

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

Предикат $\mathbb{N}(x)$, читаемый как "x является натуральным числом", определяется формулой:
$\forall X~((X(1) \wedge \forall x~X(x) \to X(x+1)) \to (\forall x~\mathbb{N}(x) \to X(x)))$

А что такое $X$?

[iifat]

Sicker в сообщении #1298947 писал(а):

А как это требование следует из определения?

Напрямую — наверное, никак. А вот последняя аксиома Пеано, касательно индукции, как по мне, выполняться не будет.
Опять же, что, собственно, с того? Множество целых чисел равномощно натуральному ряду. Если брать их во всей полноте, то уж точно аксиома индуктивности выполняться не будет. Если не брать — ну, скажем, возьмём последовательность 0, 1, -1, 2, -2... — те же натуральные числа, только переобозначенные.
Кстати говоря, ваше множество пятой аксиоме не удовлетворяет в любом случае.
Теорема: запись любого натурального числа начинается с цифры.
База индукции: для нуля — очевидно.
Шаг индукции: если $n$ начинается с цифры, то и $n+1$ начинается с цифры — очевидно.
Заключение: запись любого натурального числа начинается с цифры.
Контрпример: -1.

[Sicker]

iifat в сообщении #1298949 писал(а):

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

А как доказать, что аксиома индуктивности выполняться не будет?

-- 22.03.2018, 04:10 --

iifat в сообщении #1298949 писал(а):

Теорема: запись любого натурального числа начинается с цифры.

А причем тут форма записи термов Я вообще могу хоть инопланетными иероглифами писать

[iifat]

Sicker в сообщении #1298954 писал(а):

причем тут форма записи термов

При том, что не выполняется аксиома индукции. Разумеется, вы, подобно Иисусу, можете вообще возить пальцем по грязи — но тогда она не выполнится где-нить в другом месте, только и всего.

[Sicker]

iifat в сообщении #1298956 писал(а):

При том, что не выполняется аксиома индукции.

А как доказать, что она не выполнится?

-- 22.03.2018, 07:11 --

Пусть я хочу это проверить. Гипотеза-пусть она выполняется для наших положительных и условных отрицательных чисел.Проверяем определение, для любого $n$ из того, что оно истинно, следует, что истинно $n+1$. Да, для любого.И никого противоречия. Где ошибка?

-- 22.03.2018, 07:12 --

Я знаю, что есть трансфинитная индукция, но как доказать эта не работает?

-- 22.03.2018, 07:16 --

Тут фишка в том, что мое множество не вполне упорядочено

[eugensk]

Sicker в сообщении #1298964 писал(а):

А как доказать, что она не выполнится?

Мы можем отличать конечные множества от бесконечных: бесконечные равномощны собственному подмножеству, верно?
В множестве натуральных чисел множество чисел, меньших произвольно выбранного - конечно (докажете по индукции сами?), а у вас нет.
Всё потому, что множество натуральных чисел - наименьшее индуктивное, а ваше нет.

[iifat]

Sicker в сообщении #1298964 писал(а):

А как доказать, что она не выполнится?

Да мало ли. Вот я, например, привёл контрпример. Можно не приводить, достаточно доказать, что он имеется.

Sicker в сообщении #1298964 писал(а):

Где ошибка?

Ошибка, во-первых, в том, что определения стоит читать полностью, а не случайно выбранную половину.

Sicker в сообщении #1298964 писал(а):

Я знаю, что есть трансфинитная индукция, но как доказать эта не работает?

Sicker в сообщении #1298964 писал(а):

мое множество не вполне упорядочено

Слова, конечно, умные, вот только какое они имеют отношение к делу? Контрпример я вам привёл. Больше не надо ничего.

eugensk в сообщении #1298982 писал(а):

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

И даже это уже лишнее. Аксиомы Пеано не содержат отношений больше/меньше.

-- 22.03.2018, 16:26 --

Sicker в сообщении #1298567 писал(а):

пусть у нас такое упорядочивание на множестве целых чисел, сначала идут натуральные, а потом, после них, отрицательные в сторону уменьшения модуля, т.е. до -1

Кстати говоря, а что идёт за -1? У каждого наттурального есть последователь!

[epros]

Sicker в сообщении #1298947 писал(а):

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

Предикат $\mathbb{N}(x)$, читаемый как "x является натуральным числом", определяется формулой:
$\forall X~((X(1) \wedge \forall x~X(x) \to X(x+1)) \to (\forall x~\mathbb{N}(x) \to X(x)))$

А что такое $X$?

Любой предикат. Что, собственно, видно из первого квантора. Можете вместо "предиката" сказать "множество". Тогда формула прочитается как: "Для любого множества, если оно индуктивно, множество $\mathbb{N}$ является его подмножеством".

[arseniiv]

Sicker в сообщении #1298947 писал(а):

А как вы доказываете наименьшесть?

Берём пересечение всех индуктивных множеств. Оно единственное включается в каждое индуктивное множество, так что остаётся только сравнить, оно это или не оно нам попалось.

[mihaild]

Sicker в сообщении #1298964 писал(а):

А как доказать, что она не выполнится?

Для начала - полностью сформулировать.
В арифметики аксиома индукции выдает аксиому для формул в арифметическом языке. Вы какую сигнатуру рассматриваете? И какую модель?
Пока что я понял что вы вроде бы хотите посмотреть на $\omega + \omega^*$. Это множество не является индуктивным, т.к. содержит $0^*$, но не $0^* + 1$.
Если вы хотите попытаться рассмотреть это множество как носитель модели для аксиом арифметики - то вам нужно указать, как интерпретировать символы из сигнатуры в этой модели.

(заметим, что существуют нестандартные модели арифметики - например, упорядоченные как $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$, но сложение и умножение на таких моделях вычислимо задать уже не получится)

[Someone]

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

существуют нестандартные модели арифметики - например, упорядоченные как $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$

Уточню, что произведение $\mathbb Z\times\mathbb Q$ предполагается упорядоченным антилексикографически, то есть, $(m,p)<(n,q)\Leftrightarrow(p<q\vee(p=q\wedge m<n))$. И такое упорядочение имеют все счётные нестандартные модели.

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

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

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

[mihaild]

Someone в сообщении #1299091 писал(а):

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

Сложение точно нельзя.

Richard Kaye в Tennenbaum’s Theorem for Models of Arithmetic писал(а):

Theorem 2.7. Let $M$ be a nonstandard model of Peano arithmetic. Then $SSy (M)$ contains a nonrecursive set.
Theorem 2.8. Let $M$ be a model of Peano arithmetic for which $SSy (M)$ contains a nonrecursive set. Then $(M, +)$ is not recursive.

Слышал (и на stackexchange скажем пишут), что и умножение нельзя, но источников не нашел.

[Someone]

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