Проверка аксиом Пеано по фон Нейману

[ipinyagin]

Здравствуйте!

Читаю "Математический анализ" Зорича, а именно раздел про аксиоматическую теорию множеств. Аксиоматика у Зорича содержит аксиомы: объемности, выделения, объединения, пары, множества подмножеств, бесконечности, подстановки, выбора. Далее определяется, по фон Нейману, модель натуральных чисел $\mathbb{N}_0$.

После этого предлагается при помощи этих аксиом доказать ряд утверждений, которые очень похожи на аксиомы Пеано ( $x^+$ обозначает последователь элемента $x$ ):

1. $x = y \Rightarrow x^+ = y^+$
2. $(\forall x \in \mathbb{N}_0) (x^+ \ne \varnothing)$
3. $x^+ = y^+ \Rightarrow x = y$
4. $(\forall x \in \mathbb{N}_0) (x \ne \varnothing \Rightarrow (\exists y \in \mathbb{N}_0) (x = y^+))$

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

Будем доказывать от противного. Предположим, что $\exists x \in \mathbb{N}_0 (x^+ = \varnothing)$. Тогда:
$x^+ = x \cup \left\lbrace x \right\rbrace = \varnothing$ $\Leftrightarrow$ $(x = \varnothing) \wedge (\left\lbrace x \right\rbrace = \varnothing)$
Очевидно, что $\left\lbrace x \right\rbrace \ne \varnothing$, значит, и $x^+ \ne \varnothing$. Полученное противоречие доказывает исходное утверждение.

В пп.3,4 же я не совсем понимаю, какие рассуждения требуется провести. Например, п.4 выглядит просто самоочевидно в силу того, как устроено $\mathbb{N}_0$ (пустое множество и цепочка последователей, построенная от него). В принципе, можно его и подоказывать совсем уж строго, но я вижу здесь доказательство только при помощи мат. индукции. И в этом еще одна загвоздка: а правомерно ли использовать здесь метод мат. индукции? Я не силен в основаниях математики, но предполагаю, что, как и с любым другим математическим утверждением, принцип мат. индукции либо должен постулироваться (а в приведенной Зоричем аксиоматике я не вижу ничего похожего на это), либо доказываться (тогда возникает вопрос даже не как его доказать, а как его хотя бы сформулировать в терминах нашей модели натуральных чисел, ведь других-то натуральных чисел нам пока еще "не завезли"; и дополнительный вопрос: насколько это вообще методически корректно - давать такого рода задачи в качестве упражнения).

Буду благодарен, если кто-нибудь поможет мне разобраться в этих моментах. Большое спасибо!

[dgwuqtj]

ipinyagin в сообщении #1625230 писал(а):

Например, п.4 выглядит просто самоочевидно в силу того, как устроено $\mathbb{N}_0$

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

[schmetterling]

ipinyagin в сообщении #1625230 писал(а):

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

Правильно — нужно пользоваться аксиоматикой. Отвлекитесь от $\in$ как от чего-то, что значит "принадлежит множеству", и думайте о нём как о значке, про который известно то-то, то-то и то-то.

Утверждение из пункта 1 можно доказать так:
Пусть $x = y$. Благодаря аксиоме объёмности достаточно для всякого $a$ доказать, что $a \in x^{+} \Leftrightarrow a \in y^{+}$.

По определению $\cup$ выполняется $a \in x^{+} \Leftrightarrow a \in x \text{ или } a \in \{x\}$. По определению $\{ \cdot \}$ выполняется $a \in \{x\} \Leftrightarrow a = x$. По свойству равенства $a = x \Leftrightarrow a = y$. По аксиоме объёмности $a \in x \Leftrightarrow a \in y$. Таким образом,
\begin{multline*}a \in x^{+} \Leftrightarrow a \in x \text{ или } a \in \{x\} \Leftrightarrow a \in x \text{ или } a = x \Leftrightarrow \\ \Leftrightarrow a \in y \text{ или } a = y \Leftrightarrow a \in y \text{ или } a \in \{y\} \Leftrightarrow a \in y^{+}\end{multline*}
ч.т.д.

ipinyagin в сообщении #1625230 писал(а):

Будем доказывать от противного. Предположим, что $\exists x \in \mathbb{N}_0 (x^+ = \varnothing)$. Тогда:
$x^+ = x \cup \left\lbrace x \right\rbrace = \varnothing$ $\Leftrightarrow$ $(x = \varnothing) \wedge (\left\lbrace x \right\rbrace = \varnothing)$
Очевидно, что $\left\lbrace x \right\rbrace \ne \varnothing$, значит, и $x^+ \ne \varnothing$. Полученное противоречие доказывает исходное утверждение.

Это рассуждение это почти то, что нужно. Но вы используете утверждения $x \cup \left\lbrace x \right\rbrace = \varnothing$ $\Leftrightarrow$ $(x = \varnothing) \wedge (\left\lbrace x \right\rbrace = \varnothing)$ и $\left\lbrace x \right\rbrace \ne \varnothing$, которые вы перед этим не вывели из аксиом. Возможно, они очевидно следуют из аксиом, но задача в том, чтобы это расписать.

[ipinyagin]

dgwuqtj в сообщении #1625234 писал(а):

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

Хорошо. То есть вы хотите сказать, что в рамках ZFC вывести, что таким наименьшим индуктивным множеством является именно построенное через цепочку последователей пустого множества множество $\mathbb{N}_0$, нельзя? Или можно, но это требует просто дополнительных рассуждений, которые Зорич не приводит (с этим соглашусь)?

dgwuqtj в сообщении #1625234 писал(а):

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

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

[schmetterling]

ipinyagin в сообщении #1625230 писал(а):

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

Варианта два.

1) пусть $\varphi(x)$ — произвольное утверждение о множестве $x$. Тогда

$$\left(\varphi(\varnothing) \land (\forall x \in \mathbb{N}_0\; \varphi(x) \Rightarrow \varphi(x^{+}))\right) \Rightarrow \forall x \in \mathbb{N}_0\; \varphi(x)$$

2) интуитивно, мы в (1) качестве утверждения $\varphi$ берём $x \in m$ и добавляем квантор по $m$. Это частный случай того, что в (1), но он настолько сильный, что его можно использовать всегда, когда нужно провести рассуждения по индукции. Он лучше того, что в (1), тем, что отсутствует мутное "произвольное утверждение о множестве $x$", да и доказывается легче.

$$\forall m \left(\left(\varnothing \in m \land (\forall x \in \mathbb{N}_0\; x \in m \Rightarrow x^{+} \in m)\right) \Rightarrow \forall x \in \mathbb{N}_0\; x \in m\right)$$

[ipinyagin]

schmetterling в сообщении #1625235 писал(а):

Правильно — нужно пользоваться аксиоматикой. Отвлекитесь от $\in$ как от чего-то, что значит "принадлежит множеству", и думайте о нём как о значке, про который известно то-то, то-то и то-то.

...

Это рассуждение это почти то, что нужно. Но вы используете утверждения $x \cup \left\lbrace x \right\rbrace = \varnothing$ $\Leftrightarrow$ $(x = \varnothing) \wedge (\left\lbrace x \right\rbrace = \varnothing)$ и $\left\lbrace x \right\rbrace \ne \varnothing$, которые вы перед этим не вывели из аксиом. Возможно, они очевидно следуют из аксиом, но задача в том, чтобы это расписать.

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

Цитата:

Варианта два.

Ага, хорошо. Но правильно ли я понял, что утверждение 4) в самом деле без мат. индукции не доказать? Если так, то Зорич как-то не очень красиво, на мой взгляд, поступил, предложив такое утверждение в качестве упражнения.

И тогда еще по утверждению 3). Приведу опять свои попытки рассуждения:

$x^+ = y^+ \Leftrightarrow x \cup \left\lbrace x \right\rbrace = y \cup \left\lbrace y \right\rbrace$
Докажем, что $x \subset y$. Пусть $z \in x$ - произвольный элемент; хочу показать, что $z \in y$.
$z \in x$ $\Rightarrow$ $z \in x \cup \left\lbrace x \right\rbrace$ $\Rightarrow$ $z \in y \cup \left\lbrace y \right\rbrace$ $\Rightarrow$ $(z \in y) \vee (z \in \left\lbrace y \right\rbrace)$ $\Rightarrow$ $(z \in y) \vee (z = y)$
Но если $z = y$, то, т.к. $z \in x$, получается что $y \in x$.
После чего я пустился в очень туманные рассуждения с неясным исходом. Полностью строго убедить себя в том, что случай $y \in x$ несовместим с условием $x^+ = y^+$, мне не удалось.

[EminentVictorians]

Можно вообще сформулировать аксиомы $\mathbb R$ (как полного упорядоченного поля), построить модель, а потом по определению положить
$2:=1 + 1$
$3:=(1+1) + 1$
$4:=((1+1) + 1) + 1$
и т.д.

И потом пользоваться всеми аксиомами $\mathbb R$ при доказательстве свойств натуральных чисел. Но я Вас пойму, если Вам не понравится такой подход.

Вообще, на момент изучения матанализа лучше считать, что все вплоть до $\mathbb Q$ построено и изучено. И сразу начинать строить $\mathbb R$. А честное построение тех же натуральных чисел наверное лучше изучать по книжкам о теории множеств.

[ipinyagin]

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

Можно вообще сформулировать аксиомы $\mathbb R$ (как полного упорядоченного поля), построить модель, а потом по определению положить
$2:=1 + 1$
$3:=(1+1) + 1$
$4:=((1+1) + 1) + 1$
и т.д.

И потом пользоваться всеми аксиомами $\mathbb R$ при доказательстве свойств натуральных чисел. Но я Вас пойму, если Вам не понравится такой подход.

Вообще, на момент изучения матанализа лучше считать, что все вплоть до $\mathbb Q$ построено и изучено. И сразу начинать строить $\mathbb R$. А честное построение тех же натуральных чисел наверное лучше изучать по книжкам о теории множеств.

В старом добром Фихтенгольце как раз рациональные числа (и до кучи еще много чего) считаются уже известными, после чего идет построение вещественных чисел. Но Фихтенгольц - это все-таки не совсем то, чего нужно. Хочется именно честно пройти, в методическом порядке, современный "полноценный" курс для математиков, не перепрыгивая через разделы по причине того, что что-то непонятно. Одно дело, если бы Зорич, к примеру, пользовался какими-то вещами из линейной алгебры или других дисциплин, которые, как подразумевается, студент-математик изучает параллельно с матаном, тогда можно было бы честно сослаться на междисциплинарные связи и отправить интересующегося читателя (то есть себя самого ) к учебнику алгебры. Но здесь выглядит так, будто учебник не подразумевает для того, чтобы разобраться в данном вопросе, параллельного изучения каких-то дополнительных дисциплин, т.е. выглядит так, будто весь необходимый "теорминимум" уже дан.

[KhAl]

ipinyagin в сообщении #1625242 писал(а):

Полностью строго убедить себя в том, что случай $y \in x$ несовместим с условием $x^+ = y^+$, мне не удалось.

Это хорошо. Из указанных Зоричем аксиом не следует (вроде), например, что не существует двух множеств $x \neq y$ таких, что $x = \{y\}$ и $y = \{x\}$. Для такой пары множеств было бы $x^{+} = y^{+} = \{x, y\}$, но $x \neq y$. Чтобы сделать то, что вы хотите, дополнительно к аксиомам из Зорича нужна аксиома регулярности.

В аксиомах Зорича существенно то, что $x, y \in \mathbb{N}_0$, и нужно применять индукцию.

ipinyagin в сообщении #1625242 писал(а):

Ага, хорошо. Но правильно ли я понял, что утверждение 4) в самом деле без мат. индукции не доказать? Если так, то Зорич как-то не очень красиво, на мой взгляд, поступил, предложив такое утверждение в качестве упражнения.

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

[EminentVictorians]

ipinyagin в сообщении #1625245 писал(а):

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

По-моему, нет. Зорич не строит модель аксиом действительных чисел (т.е. не доказывает ее непротиворечивость), и так же не доказывает категоричность (в том смысле, что все модели $\mathbb R$ изоморфны между собой). Да и натуральные числа, если мне не изменяет память, он вводит не как в ZFC. По-моему, он рассматривает не индуктивные множества вообще, а только индуктивные (относительно прибавления вещественной единицы) подмножества множества действительных чисел (которое само не построено).

Я пишу по памяти, за точность не ручаюсь, но надеюсь информация лишней не будет.

[dgwuqtj]

ipinyagin в сообщении #1625245 писал(а):

Хочется именно честно пройти, в методическом порядке, современный "полноценный" курс для математиков, не перепрыгивая через разделы по причине того, что что-то непонятно.

Вот я учился на математика, в мат. анализе вещественные числа определялись аксиоматически. Курс мат. логики и теории множеств (где давалась ZFC в каком-то виде) был только во втором семестре, а построение вещественных чисел через пополнение $\mathbb Q$ было в качестве доп. материала уже на втором или третьем курсе, в рамках функционального анализа. Нельзя изучать математику совсем "по порядку", хотя бы потому что строгое изложение основ уже требует мат. логики (для теорий первого порядка) и теории множеств (для моделей). А мат. логика требует знания арифметики, разумеется, там вовсю индукция по формулам используется.

ipinyagin в сообщении #1625236 писал(а):

То есть вы хотите сказать, что в рамках ZFC вывести, что таким наименьшим индуктивным множеством является именно построенное через цепочку последователей пустого множества множество $\mathbb{N}_0$, нельзя?

Если бы у Зорича были аксиомы ZFC первого порядка, как их обычно излагают в книгах по аксиоматической теории множеств, то было бы нельзя. Но у него аксиомы второго порядка, в аксиоме выделения $P$ - это "любое свойство" (что бы это ни значило). Всегда можно взять произвольное индуктивное множество $X$ и свойство $P$, утверждающее, что его аргумент - это стандартное натуральное число (тогда $\{x \in X \mid P(x)\}$ тоже будет индуктивным и, как легко проверить, наименьшим индуктивным).

Что касается математической индукции, то её можно либо доказать (с помощью аксиомы выделения), либо вообще вместо неё использовать минимальность $\mathbb N_0$ как индуктивного множества.

-- 08.01.2024, 17:19 --

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

Я пишу по памяти, за точность не ручаюсь, но надеюсь информация лишней не будет.

Вот я открыл книгу, там в 1 главе натуральные числа вводятся как множество конечных ординалов, а в 2 главе - как подмножество $\mathbb R$ (само $\mathbb R$ определяется аксиоматически).

[ipinyagin]

KhAl в сообщении #1625246 писал(а):

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

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

Цитата:

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

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

Цитата:

Что касается математической индукции, то её можно либо доказать (с помощью аксиомы выделения), либо вообще вместо неё использовать минимальность $\mathbb N_0$ как индуктивного множества.

Если не трудно, можете немного более подробно рассказать, каким образом можно использовать минимальность $\mathbb{N}_0$ взамен мат. индукции?

[EminentVictorians]

dgwuqtj в сообщении #1625251 писал(а):

Вот я открыл книгу, там в 1 главе натуральные числа вводятся как множество конечных ординалов, а в 2 главе - как подмножество $\mathbb R$ (само $\mathbb R$ определяется аксиоматически).

А я и забыл совсем, что он в первой главе о них говорит. Да, сейчас вижу. Но вообще это, конечно, мельком упомянул, не больше. Я изучал полное построение $\mathbb N$ по фон Нейману, у меня на это, кажется, неделя целая ушла. Там не так уж и мало теорем, как может показаться: у $\mathbb N$ много свойств.

В общем, честно все это строить - это отдельная деятельность под названием "Числовые системы" или как-то в таком духе. Мне тоже это все было интересно. Один раз сделал, успокоился, в целом считаю не лишним. Но на момент начала матанализа, имхо, разумнее всего считать $\mathbb Q$ известным и строить уже $\mathbb R$.

[dgwuqtj]

ipinyagin в сообщении #1625252 писал(а):

Если не трудно, можете немного более подробно рассказать, каким образом можно использовать минимальность $\mathbb{N}_0$ взамен мат. индукции?

Давайте пункт 4 разберём. Рассмотрим множество $\{x \in \mathbb N_0 \mid x = \varnothing \text{ или } \exists y \in \mathbb N_0 \enskip y^{+} = x\}$, это действительно множество по аксиоме выделения. Оно содержится в $\mathbb N_0$ и если окажется, что оно индуктивное, то оно будет совпадать с $\mathbb N_0$ в силу минимальности. А индуктивность вроде очевидна (если нет, оставлю вам в качестве упражнения).

[ipinyagin]

dgwuqtj в сообщении #1625256 писал(а):

Давайте пункт 4 разберём. Рассмотрим множество $\{x \in \mathbb N_0 \mid x = \varnothing \text{ или } \exists y \in \mathbb N_0 \enskip y^{+} = x\}$, это действительно множество по аксиоме выделения. Оно содержится в $\mathbb N_0$ и если окажется, что оно индуктивное, то оно будет совпадать с $\mathbb N_0$ в силу минимальности. А индуктивность вроде очевидна (если нет, оставлю вам в качестве упражнения).

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

А по поводу п.3 не дадите каких-то соображений? Может, все-таки можно там обойтись без регулярности.