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

[Sdy]

Читаю книгу Terence Tao, Analysis 1. Прямая ссылка на скачивание - http://booksdl.org/get.php?md5=850af3cc ... e82691a69b
Хотелось бы проверить доказательства упражнений из первой главы этой книги.
Упражнение 2.2.2)Докажите, что для любого положительного числа $a$ $\exists!$ натуральное число $b$, такое что $b++=a$.
Доказательство.
Доказательство существования проведем по индукции.
$b = 0$ является предшествующим для положительного числа $1$.
Предположим, что число $b$ является предшествующим для некоторого положительного числа $a$. Тогда необходимо доказать, что следующее за cледующим после $b$ число также является положительным. Но мы знаем, что за $b$ следует положительное число, то есть натуральное число, неравное $0$. А у нас есть аксиома, утверждающая, что за любым натуральным числом следует число натуральное. Значит и за $b++$ следует число натуральное и при этом положительное, так как число $b++$ - число неравное $0$, а у нас есть аксиома, утверждающая, что у $0$ нет предшествующего элемента и поэтому нулем число, следующее за $b++$ , быть не может.
Таким образом, за любым натуральным числом следует число положительное, что и означает, что у любого положительного числа есть число предшествующее.
Докажем единственность.
Предположим противное - пусть $\exists$ два различных натуральных числа $b,c$, такие, что для некоторого положительного $a$ верно $b++=a \wedge c++=a$. Но число $a$ - число натуральное (неравное $0$), а у нас есть аксиома, которая утверждает, что $ n = m \Rightarrow n++ = m++$ или что тоже самое - $n \ne m \Rightarrow n++ \ne m++$. Получили противоречие. $\triangle$

Проблема тут в том что можно пользоваться лишь материалом, определенным в этом пункте, если понадобится, я могу привести все доказанные доселе в тексте утверждения и пункты аксиоматики. И решений к упражнениям у него, к сожалению нет.
Соотвественно вопрос - верно ли доказательство и не вышел ли я в нем за рамки дозволенного?

[Connector]

Поясните, зачем Вы доказываете, что за каждым натуральным числом следует число положительное?
Я бы провёл шаг индукции немного иначе: если утверждение теоремы верно для $b$, то оно справедливо и для $b++$ (которое, как Вы доказали, положительно), поскольку $b$ и есть натуральное число, существование которого утверждает теорема.
UPD Сложилось впечатление, что Вы проводите доказательство существования индукцией по $b$; по-моему, следует проводить индукцией по $a$.

[mihaild]

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

Тогда необходимо доказать, что следующее за cледующим после $b$ число также является положительным.

Нет, не это нужно доказать. Мы доказываем $P(a)$: $a = 0$ или существует $b$ такое что $b++ = a$. Нам нужно доказать, что $P(0)$ истинно, и $P(n) \rightarrow P(n++)$.

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

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

Совершенно не значит. Например, квадрат любого натурального числа есть число положительное, но не любое положительное число есть квадрат натурального.

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

$ n = m \Rightarrow n++ = m++$ или что тоже самое - $n \ne m \Rightarrow n++ \ne m++$.

При навешивании отрциания импликация переворачивается: $n = m \Rightarrow n++ = m++$ эквивалетно $n ++ \neq m++ \Rightarrow n = m$.
Но аксиома 2.4 формулируется именно как $n++ = m++ \Rightarrow n = m$ (и её и нужно использовать).
(а то, что вы сформулировали - следствие аксиомы подстановки)

[Padawan]

(Оффтоп)

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

$b++$

Ужасное обозначение!

[Someone]

(Оффтоп)

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

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

$b++$

Ужасное обозначение!

Да, выглядит кошмарно. Обычно используют что-нибудь вроде $b'$, $b\vert$ или $S(b)$. А это Теренс Тао явно позаимствовал из языков программирования.

[Sdy]

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

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

Совершенно не значит. Например, квадрат любого натурального числа есть число положительное, но не любое положительное число есть квадрат натурального.

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

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

Нет, не это нужно доказать. Мы доказываем $P(a)$: $a = 0$ или существует $b$ такое что $b++ = a$. Нам нужно доказать, что $P(0)$ истинно, и $P(n) \rightarrow P(n++)$

Я изначально хотел строить индукцию по $a$, но в книге аксиома индукции формулируется вот так -
Пусть $P(n)$ - свойство некоторого натурального числа $n$. Предположим, что $P(0)$ верно и всегда, когда верно $P(n)$ верно и $P(n++)$. Тогда $P(n)$ верно для всех натуральных чисел.
Но $a$ не может быть равно нулю. По определению натуральное число $a$ называется положительным тогда и только тогда, когда оно не равно нулю. И тогда я не могу доказать базис индукции. Ведь я формулирую $P(a)$ таким образом - любому положительному числу предшествует число натуральное. Но нуль вообще не является положительным числом и тогда мой базис ломается. (А также нулю ничего не предшествует по одной из аксиом.) Из-за этого я и начал думать,как её строить по $b$.

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

эквивалетно $n ++ \neq m++ \Rightarrow n = m$.

Тут же знак равенства? $n ++ = m++ \Rightarrow n = m$?

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

Connector в сообщении #1393022 писал(а):

по-моему, следует проводить индукцией по $a$.

Свои затруднения по этому поводу описал выше.

Попробую пока доказать единственность.
Имеется аксиома $2.4$, она утверждает -
Если $n$ - натуральное число и $m$ - натуральное число, и они при этом различны, то
и последующие для них числа различны.
(Просто у меня как-то закрепилось, что высказывания $n \neq m \rightarrow n++ \neq m++$ и $n = m \rightarrow n++ = m++$ полностью эквиваленты, хотя в сноске к этой аксиоме Тао пишет то на что и вы мне указали - что это лишь следствие из аксиомы подстановки, до которой я еще не дошел)
Тогда предположим, что существуют натуральные $b,c : b \neq c \wedge b++ = a \wedge c++=a$. Но $b$ и $c$ не равны, значит и последующие для них числа не равны по аксиоме 2.4. Следовательно, пришли к противоречию.

С существованием для меня пока существуют описанные выше проблемы.

[mihaild]

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

Ведь я формулирую $P(a)$ таким образом - любому положительному числу предшествует число натуральное.

Давайте сначала по индукции докажем, что либо $a$ не положительно, либо ему предшествует натуральное. А из этого уже выведем что любому положительному числу предшествует натуральное.
Собственно "любому положительному предшествует натуральное" означает "для любого числа: из того, что оно положительное, следует, что оно натуральное". А дальше свойства импликации.

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

Тут же знак равенства? $n ++ = m++ \Rightarrow n = m$?

Нет, тут знак неравенства справа: $n++ \neq m++ \Rightarrow n\neq m$.

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

высказывания $n \neq m \rightarrow n++ \neq m++$ и $n = m \rightarrow n++ = m++$ полностью эквиваленты

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

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

Следовательно, пришли к противоречию

Так можно, но можно и напрямик: $b++ = a \wedge c++ = a \Rightarrow b++ = c++ \Rightarrow b = c$. Первый переход - следствие транзитивности (и симметричности) равенства, второй - аксиома 2.4.

[Sdy]

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

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

по индукции докажем, что либо $a$ не положительно, либо ему предшествует натуральное

Базис индукции - $a = 0 \rightarrow a$ неположительно, то есть выполняется первая часть утверждения.
Предположение индукции - пусть для некоторого $a$ (как я понимаю, я могу сказать, что для некоторого $a$,не равного нулю, ведь случай с ним мы проверили) существует натуральное $b$, такое, что $b++ = a$. Докажем, что тогда и для $a++$ существует предшествующее натуральное число.
Но предшествующим для $a++$ является $a$ (по определению), но для $a$ в свою очередь есть предшествующее натуральное $b$, значит по аксиоме 2.2 $a$ является натуральным числом, но тогда и $a++$ является натуральным числом, причём не равным нулю, так как у него есть предшествующее.
Значит мы доказали, что для любого натурального $a$ - либо оно равно нулю, либо оно (по определению) положительно и ему предшествует натуральное число.
Значит любому положительному числу (оно ведь не равно нулю) предшествует натуральное число.
Корректное ли рассуждение?

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

Так можно, но можно и напрямик:

Да, понял.

[mihaild]

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

как я понимаю, я могу сказать, что для некоторого $a$,не равного нулю, ведь случай с ним мы проверили

Нет, так нельзя. Мы должны доказать два утверждения: $P(0)$ (доказали) и что для любого $n$ выполнено $P(n) \rightarrow P(n++)$.
Тут надо рассмотреть два случая:
1) $n$ - не натуральное. Тогда $P(n)$ не выполнено (не натуральное число не может быть нулем, и не может следовать за натуральным) и импликация выполнена.
2) $n$ - натуральное. Тогда $P(n++)$ выполнено, т.к. $n++$ предшествует натуральное $n$.

(Оффтоп)

Вообще мне очень не нравятся разговоры об арифметике с рассмотрением натуральных чисел как части чего-то большего. В частности приводит к странным утверждениям типа "Let $a$ be a positive number. Then there exists ... natural number $b$ such that $b++ = a$" (жирный шрифт мой - mihaild). Явно нужно добавить, что число не просто положительное, а натуральное положительное. При этом просто положительные числа к этому моменту вообще не определены.
Почему бы не брать честно натуральные числа в качестве модели, и вместо "что-то там - натуральное число" говорить "что-то там существует"?..

[Sdy]

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

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

Let $a$ be a positive number.

Скажите, пожалуйста, не может ли здесь подразумеваться под positive number именно positive natural number? Просто на данный момент было введено только понятие натурального положительного числа, и я думал, что именно это здесь и подразумевается. Тогда в качестве $n$ можно предполагать лишь натуральные числа.
И тогда такое доказательство будет корректно?

Докажем по индукции, что либо число $a$ равно нулю, либо оно положительно (по определению) и тогда существует натуральное число $b : b++=a$.
$\triangle$
Базис индукции - $a = 0$, предположение индукции выполнено.
Возьмём произвольное натуральное число $a$. По предположению индукции оно или равно нулю или существует $b : b++=a$.
Проведем переход индукции. Возьмём $a++$ - в обоих случаях это число положительно, так как оно не равно нулю. В обоих случаях ему предшествует натуральное число - в первом случае нуль, во втором - положительное число, которое натуральное по определению. Тогда переход индукции произведен корректно, а значит любое натуральное число или равно нулю или оно положительно и перед ним идёт число натуральное.
$\triangle$

[arseniiv]

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

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

Ну правильно, ничего другого желать не остаётся. Если понимать иначе, получится ерунда с утверждениями.

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

Докажем по индукции, что либо число $a$ равно нулю, либо оно положительно (по определению) и тогда существует натуральное число $b : b++=a$.

Плохая формулировка. Можно так:
1. Или натуральное число равно нулю, или существует …
2. Если натуральное число положительно, тогда существует …

Дальше какая-то слишком ветвистая индукция идёт. Если $a$ — это то, про которое мы доказываем, не нужно рассматривать $a++$. Если же под ним имелось в виду как раз то $b$, то собственно и всё.

[Sdy]

arseniiv, спасибо за ответ.
А чем плоха моя формулировка? Ведь либо натуральное $a=0$, либо нет. И если не равно - тогда оно положительное по определению. И тогда существует $b : b++ = a$.

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

Если $a$ — это то, про которое мы доказываем, не нужно рассматривать $a++$

Я вроде как таким образом делаю переход индукции, то есть доказываю, что $P(a) \to P(a++)$. Иначе какая здесь индукция.

[arseniiv]

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

А чем плоха моя формулировка? Ведь либо натуральное $a=0$, либо нет. И если не равно - тогда оно положительное по определению. И тогда существует $b : b++ = a$.

Вы смешиваете вместе высказывание и вывод, и получается что-то странное. Например можно попытаться распарсить это как «либо $a = 0$, либо ($a$ положительно и (если $a$ положительно, то существует $b$ такое, что $b++ = a$))», и тогда это хоть и истинно, но не совсем то.

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

Я вроде как таким образом делаю переход индукции, то есть доказываю, что $P(a) \to P(a++)$. Иначе какая здесь индукция.

Ну, в данном случае можно доказать сразу $P(a++)$, не используя $P(a)$.

[Sdy]

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

Тогда имеем
Утверждение. Натуральное число $a$ либо равно нулю, либо $ \exists$ натуральное $b : b++ = a$.
Доказательство.
$\triangle$
Проведём индукцию по $a$.
1.Базис индукции - $a = 0$ - тогда наше утверждение верно.
2.Предположение индукции. Пусть для произвольного натурального числа $a$ выполнено наше утверждение.
Произведем индуктивный переход, то есть докажем, что из верности утверждения для $a$ следует истинность утверждения для $a++$.
Рассмотрим $a++$. Ему предшествует $a$, для которого выполнено утверждение индукции. Но тогда по аксиоме $a++$ - натуральное число, так как ему предшествует натуральное число. При этом $a++$ не может быть равно нулю, так как у нас есть аксиома, утверждающая, что ни за каким натуральным числом нуль не следует. Значит для него выполнено утверждение индукции, тогда наше утверждение доказано.
$\triangle$
Теперь докажем первоначальное утверждение.
$\triangle$
$a$ - положительное натуральное число, тогда это натуральное число, которое не равно нулю. Но как мы доказали, либо натуральное число равно нулю, либо для него существует предыдущее. Утверждение доказано.
$\triangle$
Это верный вариант?

[mihaild]

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

2.Предположение индукции. Пусть для произвольного натурального числа $a$ выполнено наше утверждение.

Тут проблема в том, что принцип индукции зачем-то сформулирован для натуральных чисел как подмножества вещественных, и он требует доказывать переход $P(n) \to P(n++)$ вообще для всех $n$ - не только для натуральных.
(ИМХО тут стоит аккуратно сформулировать более четкую формулировку, в которой будет неважно, как ведет себя $P$ на не натуральных числах)