Построение множества натуральных чисел

[arseniiv]

Sdy в сообщении #1394086 писал(а):

Правильно ли я понимаю, что я просто отягощаю высказывание, причём этим отягощением еще и не пользуюсь?

Как-то так, да.

[Sdy]

mihaild, спасибо за ответ.
Честно сказать, я не понимаю, о чём Вы говорите, и где моя индукция ломается. Я вроде как пользуюсь имеющейся аксиомой индукции, быть может я ее понимаю неверно.
Вот как она формулируется у Тао :
Axiom 2.5 (Principle of mathematical induction). Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n)$ is true for every natural number $n$.

Мой перевод
Аксиома 2.5 (Принцип математической индукции).Пусть $P(n)$ - любое свойство натурального числа $n$.
Предположим, что $P(0)$ верно, тогда, положим, что когда бы ни было верно $P(n)$, $P(n++)$ также верно. Тогда $P(n)$ верно для любого натурального числа $n$.

Далее идёт
Proposition 2.1.11. A certain property $P(n)$ is true for every natural number $n$.
Мой перевод.
Утверждение 2.1.11. Свойство, верное для для некоторого натурального числа, остается верным для любого натурального
числа.
Доказывается это по индукции.
Что именно я понимаю не так?

-- 20.05.2019, 04:49 --

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

Как-то так, да.

Понял, спасибо.

[arseniiv]

(mihaild)

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

Тут проблема в том, что принцип индукции зачем-то сформулирован для натуральных чисел как подмножества вещественных

Насколько я сейчас почитал, Тао не выделяет $\mathbb N$ в $\mathbb R$. Это ничего особо не меняет, но. (Возможно, это из-за того листка про вещественные числа, который как-то обсуждали на форуме? Там-то точно действительно было такое выделение, это я помню!)

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

Почему бы не брать честно натуральные числа в качестве модели, и вместо "что-то там - натуральное число" говорить "что-то там существует"?..

Возможно чтобы не запутать потом читателя совмещением этой теории со всем остальным. Тут или многосортный язык делать, или иным способом потом во все старые утверждения добавлять вот эти все «… — натуральное число», и, видимо, если предположить, что уже известно что-то о множествах, то проще всё погрузить в наивную теорию множеств и аксиомы, типа $n\in\mathbb N\Rightarrow n+\!+\in\mathbb N$ добавлять к ней.

-- Пн май 20, 2019 02:02:28 --

Sdy в сообщении #1394094 писал(а):

Мой перевод.
Утверждение 2.1.11. Свойство, верное для для некоторого натурального числа, остается верным для любого натурального
числа.

Ненене, тут certain относится к property, «некоторое свойство $P(n)$ верно для любого натурального $n$».

[mihaild]

Тао писал(а):

Let P(n) be any property pertaining to a natural number n. Suppose that P(0) is true, and suppose that whenever P(n) is true, P(n++) is also true

Вот тут на самом деле не совсем понятно, о чем речь. Понятие "свойства" к тому моменту не введено, что такое "свойство натурального числа" - тем более. Можно ли во второе предложение подставлять не натуральные $n$?.. Моя трактовка - да, можно, и это сильно осложняет жизнь.

[arseniiv]

Sdy
Мгм, я там выше не очень хорошее доказательство предлагал, думая, что положительное натуральное определяется как чей-то инкремент. Нет, оно определяется (2.2.7) как не равное нулю натуральное. Тогда всё немного сложнее, конечно. Придётся в индукционном переходе всё-таки использовать гипотезу $P(n)$, чтобы иметь $n\in\mathbb N$, нужное в заключении.

mihaild
Да, точно, как выше. Не уверен, что сильно, но осложняет.

-- Пн май 20, 2019 02:41:28 --

А вот с другой стороны то самое Proposition 2.1.11 относится к предлагаемому шаблону доказательства по индукции, который имеет такой текст:

Цитата:

Proof. We use induction. We first verify the base case $n = 0$, i.e., we prove $P(0)$. (Insert proof of $P(0)$ here). Now suppose inductively that $n$ is a natural number [выделение моё], and $P(n)$ has already been proven. We now prove $P(n+\!+)$. (Insert proof of $P(n+\!+)$, assuming that $P(n)$ is true, here). This closes the induction, and thus $P(n)$ is true for all numbers n. $\square$

Выделенное снимает ту трудность, которую я увидел: теперь нам не нужно вытаскивать натуральность $n$ из $P(n)$.

-- Пн май 20, 2019 02:43:43 --

То есть мы всё же сможем иметь $P(n)$ уже не обязательно вида $n\in\mathbb N\to\ldots$ и не думать о том, что там с истинностью на ненатуральных аргументах.

[Sdy]

mihaild,
arseniiv, спасибо за ответ.
Я подумаю и напишу, так как ничего не пишу в силу того что не понимаю.
Ведь $0$ - натуральное по определению, $n$ - натуральное по условию, $n++$ натуральное по имеющейся аксиоме. Значит никаких ненатуральных $n$ в имеющихся конструкциях для построения индукции быть не может.
Единственное, что мне действительно не очень понравилось, так это то что и правда, ни что такое свойство, ни даже что такое функция (это использовалось при доказательстве корректности построения рекурсии) Тао не говорит, и мне неясно, почему, ведь эти понятия можно объяснить не привлекая натуральные числа, которые мы строим.

[arseniiv]

Возможно, он не хочет ударяться в аксиоматическую теорию множеств, книга-то об анализе. В учебниках, где предлагают какой-то величины знание о $\mathbb N, \mathbb Z, \mathbb Q$ и не строят их, тоже ведь обычно остерегаются определять свойства.

(О свойствах)

Почему с определением свойства могут быть проблемы, если мы даже ограничимся построениями в наивной теории множеств. Кажется, в качестве конкретной реализации свойства сгодится множество такое, что в него входят ровно те элементы, для которых свойство выполняется. Но возьмём например свойство «быть множеством и иметь три элемента» (не совсем уж бесполезное): если мы потом начнём копаться в нашей теории множеств и возьмём в её качестве ZFC или некоторые другие, окажется, что множества всех множеств, имеющих три элемента, не существует. Мы можем обойти это, но тогда не сможем говорить что-то обо всех свойствах сразу. К счастью, при обсуждении индукции на $\mathbb N$ используются только свойства элементов $\mathbb N$, а представляющее такое свойство множество всегда будет существовать (в ZFC).

Но предыдущий абзац уведёт вас в сторону. Постарался его сократить, но и то он вышел слишком длинным.

[Sdy]

arseniiv, спасибо за ответ.
Я видел этот пример у Зорича (чуть иначе сформулированный), он назывался "Парадокс Рассела", поэтому об этом я знал. Но вот про то что он может возникнуть в контексте определения что такое "свойство" не подумал.
Если же считать, что мы оперируем лишь на $\mathbb{N}$ , мое доказательство считается верным?

И хотелось бы понять, mihaild говорил мне о том же? Ну, что раз неясно как определять свойство, то там могут быть и другие объекты, для которых необходимо также рассматривать индуктивный переход.

[Someone]

Sdy
В формальной теории первого порядка свойство — это высказывательная функция, то есть, формула с одной свободной переменой.

[arseniiv]

Sdy
Ну как-то длинно выходит. Я бы написал так (с учётом милосердного выделенного куска в цитате Тао, как и у вас):

Докажем по индукции, что если натуральное число $n$ положительное (не является нулём), то существует натуральное $m$ такое, что $m+\!+ = n$.
База. 0 является собой, так что утверждение автоматически выполняется.
Переход. Пусть $n$ натуральное число. [И для него выполняется утверждение. Но это нам здесь не потребуется.] Тогда $n+\!+$ тоже натуральное число. Оно не равно нулю и существует $m = n$, такое, что $m+\!+ = n$, утверждение доказано.

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

[Sdy]

Разобравшись с тем, как применяется аксиома подстановки и что такое "закон контрапозиции" хотел было вернуться к анализу и построению множества натуральных чисел, но замялся на моменте, который казалось бы, был уже понятен.
В дополнении Terence Tao также пишет и об отношении равенства, говоря, что это некоторое отношение, которое симметрично, рефлексивно, транзитивно и которому применима аксиома подстановки. Но перед его применением в утверждениях для выяснения их истинности нужно определить множество $T$, на котором оно определяется и некоторые правила, которые будут согласовываться с вышеописанными свойствами.

Соответственно, мы определяем множество натуральных чисел таким образом :
1)$0$ - натуральное число.
2)Если $n$ - натуральное, то и $n++$ - натуральное.
3)$0$ не является последующим ни для какого натурального числа.
4)Если $m,n$ - натуральные числа, то $n \ne m \Rightarrow n++ \ne m++$.
Далее говорится , что в силу закона контрапозиции
$n++ = m++ \Rightarrow n = m$.
Далее, в силу аксиомы подстановки:
$n = m \Rightarrow n++ = m++$.
Мы воспользовались равенством и аксиомой подстановки, но никак не определили само равенство. После этого в книге идёт утверждение "$6 \ne 2$" , которое доказывается с помощью аксиомы 4. Но разве сама аксиома была уже сформирована?
Как вообще понимается равенство натуральных чисел и почему его можно не определяя использовать в аксиоматике Пеано?
Странно как-то получается, что определяя множество $T$ на котором будет работать равенство мы используем ещё не определённое равенство.

Я понимаю, что вопрос прямо-таки глупый.

[arseniiv]

Нет, оно определяется. Вот теми аксиомами (рефлексивность, симметричность, транзитивность, подстановка), общими для всех теорий (иногда все или некоторые из них выводимы, но пусть будет полный набор всё равно — так и проще), плюс всеми аксиомами конкретной теории, которые включают это самое равенство в себя (здесь это 3, 4 и не упомянутая индукция). Эта вся пачка аксиом, строго говоря, понимается не как вводимая последовательно, а вся целиком, а делим мы их на части просто для удобства укладывания в голове. (Ну и в принципе можно формализовать такое последовательное добавление аксиом, но никаких откровений оно не даст, а даст только кучу промежуточных теорий, которые надо будет после этого забыть; Оккам будет недоволен.)

Вообще равенство немного выделяется по сравнению с остальными отношениями, так что нередко его рассматривают как часть логики, а не предметной теории. И можно считать, что предметные аксиомы никаких новых свойств равенству не приписывают, а касаются ровно только внелогической части языка (здесь $0, {+\!+}$, вводимые когда-нибудь потом ${+}, {\cdot}, {<}$ и т. д.)

-- Сб сен 07, 2019 21:56:40 --

(Особенное равенство именно из-за отношений с подстановками, конечно.)

[epros]

Sdy в сообщении #1414060 писал(а):

Как вообще понимается равенство натуральных чисел и почему его можно не определяя использовать в аксиоматике Пеано?
Странно как-то получается, что определяя множество $T$ на котором будет работать равенство мы используем ещё не определённое равенство.

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

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

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

Например, $x++$ и $x+1$ - неразличимы в рамках арифметики, хотя мы явно видим, что буковки-то - разные.

P.S. Вопросы совсем не глупые.

[Sdy]

arseniiv, спасибо за ответ.

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

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

То есть формально говоря, я ввожу $\forall n, m \in \mathbb{N}$ отношение $R(n,m)$, которое определяется обычными свойствами равенства и при этом удовлетворяет аксиомам Пеано?
epros, спасибо за ответ.

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

Т.е. мы должны для начала определить язык (например, язык арифметики), а потом определить схему аксиом неразличимости:

Вот это вот не понял. Может есть пример конкретного построения в какой-нибудь литературе?

[epros]

Sdy в сообщении #1415252 писал(а):

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

Т.е. мы должны для начала определить язык (например, язык арифметики), а потом определить схему аксиом неразличимости:

Вот это вот не понял. Может есть пример конкретного построения в какой-нибудь литературе?

Хм, что тут непонятно? Это по-сути про ту же подстановку, только с некоторой предысторией о том, откуда это взялось: Про закон неразличимости равных говорил ещё Лейбниц.