Рекурсивная функция

[mihaild]

QuantumCoder в сообщении #1638379 писал(а):

Согласно доказанной выше лемме мы можем сопоставить для каждого $n$ уникальную функцию $a_n$

Что в точности это значит, с кванторами?
Мы доказали $\forall n \exists c: \{0, \ldots, n\} \to \mathbb N$ (с нужными свойствами). Что дальше?

QuantumCoder в сообщении #1638379 писал(а):

Мне показалось, что я пока не могу использовать минимальный элемент

Это рассуждение автоматически раскрывается в индукцию: в нуле совпадают, и если совпадают в $m$, то совпадают в $m++$.

[QuantumCoder]

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

Мы доказали $\forall n \exists c: \{0, \ldots, n\} \to \mathbb N$ (с нужными свойствами). Что дальше?

Не очень понимаю вопрос. Пусть для произвольного $n$ такая функция обозначается, как $a_n$. Дальше я просто строю $a$, как $a(n) = a_n(n)$, где $a_n$ - это уникальная функция с заданными свойствами, существование и единственность которой мы доказали.

-- 07.05.2024, 22:15 --

Тогда $a(0) = a_0(0) = c$. А $a(n++) = a_{n++}(n++) = f(n, a_{n++}(n)) = f(n, a_n(n)) = f(n, a(n))$. То есть это функция с нужными свойствами.

[mihaild]

QuantumCoder в сообщении #1638430 писал(а):

Пусть для произвольного $n$ такая функция обозначается, как $a_n$. Дальше я просто строю $a$, как $a(n) = a_n(n)$, где $a_n$ - это уникальная функция с заданными свойствами, существование и единственность которой мы доказали

И какая же теорема позволяет такое построение?
Понятно как если есть функция $b$ такая что $b(n) = a_n$: можно взять $a(n) = b(n)(n)$. Но как из $\forall n \exists! a_n: P(n, a_n)$ получить $\exists b \forall n: P(n, b(n))$ (или что-то аналогичное)?
(у Вас достаточно сведений чтобы это доказать, но это нужно сделать)

[QuantumCoder]

Я что-то никак не могу понять, к чему Вы ведете. Давайте пойдем по определению. Согласно книге задать функцию - это задать $X$ (domain), $Y$ (range) и $P(x, y)$ (такое property, что для любого $x \in X$ существует один единственный $y \in Y$ такой, что $P(x, y)$ верно).
$X$ - это $\mathbb N$
$Y$ - это $\bigcup_{N \in \mathbb N} \mathbb N ^ {\{n \in \mathbb N : n \leq N\} }$
Остается задать property $P(x, y)$ такое, что для любого $x \in X$ существует один единственный $y \in Y$, такой, что $P(x, y)$ - верно.
Определим $P(x, y)$ - как "$y$ это функция $a: \{n \in \mathbb N : n \leq x\} \to \mathbb N $ такая, что выполняются определенные условия описанные в лемме".
Согласно лемме для любого натурального числа такая функция существует и единственна, это значит, что для любого $x \in X$ найдется один единственный $y \in Y$ такой, что $P(x, y)$ - верно. Все, функция построена.

[mihaild]

QuantumCoder в сообщении #1638444 писал(а):

Остается задать property $P(x, y)$

Посмотрел повнимательнее книгу - я не очень понимаю, какой уровень строгости тут предполагает Тао.
По-хорошему, $P$ должно быть не каким-то "property", а просто множеством (подмножеством $X \times Y$). И его существование надо доказывать, исходя из аксиом теории множеств.
Возможно считается, что это анализ, так что рукомахательного "ну понятно же что описали свойство" достаточно, тогда у Вас всё хорошо. Но тогда непонятно, зачем доказывать аксиому выбора для конечных семейств, на этом уровне она очевидна.

По сути я говорил о том, что аксиома выбора для случая когда все множества одноэлементны выполнены - если все $X_i$ одноэлементны, то $\prod X_i$ непусто, и это и позволяет построить $P$ как множество (если бы они были более чем одноэлементны, то $P$ без аксиомы выбора уже не построишь). Но поскольку от $P$ требуется быть property, а не множеством, то я не знаю, нужно ли это.

[QuantumCoder]

А что вас смущает в данном случае? Все согласно вот этому:






Из примеров видно, что предполагается, что мы можем просто задать свойство. Главное, чтобы оно было "функциональным". Вот я и задал свойство. И убедился, что оно функционально. Что касается существования множеств $X$ и $Y$, то $X$ - это натуральные числа, а Y - это объединение семейства множеств, что по аксиоме:

само является множеством.

[mihaild]

QuantumCoder в сообщении #1638642 писал(а):

Из примеров видно, что предполагается, что мы можем просто задать свойство

Вот именно это меня и смущает - непонятно, что значит "задать".
В строгом изложении вместо непонятных "свойств" у нас просто подмножества множества $X \times Y$ (такие подмножества называются бинарными отношениями), ну и дальше понятно, что значит "бинарное отношение функционально". И соответственно нужно из аксиом теории множеств доказывать, что желаемое бинарное отношение существует.
Т.е. "формальное" определение функции у Тао ИМХО не особо формально, потому что ссылается на неформальное "property" (по крайней мере я не нашел, где он бы его определял). И соответственно непонятно, что предлагается честно выводить из аксиом, а где просто помахать руками.

[QuantumCoder]

mihaild
У меня тут возник вопрос по второму доказательству. Хотим доказать, что для любого $N$ существует уникальная пара множеств $A_N, B_N$, которая удовлетворяет перечисленным свойствам $a-f$. Естественно будем использовать индукцию.

Для $N = 0$ построим $A_0$ и $B_0$, как $\{0\}$ и $\mathbb N \backslash A_N $.
Пункты $a$, $b$, $c$, $d$ напрямую следуют из построения. $e$ следует из одной из акисиом Пеано, о том, что ни один successor не равен $0$, $f$ - тривиально верно. Теперь нужно показать уникальность. Пусть существуют $A_0'$ и $B_0'$, такие, что $A_0' \neq A_0$ и удовлетворяют перечисленным свойствам $a-f$. Это значит в нем есть какой-то элемент $n$, который не равен $0$. Из свойства $d$ следует, что $1$ принадлежит $B_0'$. $n$ - это икремент от $0$ повторенный $n$ раз, то есть $(((0++)++)..)++$, так как $0++ = 1$ принадлежит $B_0'$, то по свойству $d$ число $1++$ тоже принадлежит $B_0'$. Применяя конечное количество раз $d$ получим, что $n$ тоже принадлежит $B_0'$. Но тогда получается, что $n$ входит в оба множества, что противоречит свойству $a$.

Это корректные рассуждения? Меня смущает момент с применением $d$ какое-то количество раз. Просто в одной из моих предыдущих тем мне дали по рукам, когда я применял аксиому бесконечное количество раз. Теперь вот лишний раз хочу убедиться

[mihaild]

Правильно смущает. Тут нужна еще одна индукция, по $n$.
К этому моменту уже есть порядок на натуральных числах? Если да, то выведите из (e), что если $n \in B, m > n$, то $m \in B$.

[QuantumCoder]

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

[mihaild]

Тогда надо как-то явно использовать индукцию, и не опираться на то, что можно провести рассуждение длины, равной числу шагов. В конце концов, существуют и модели аксиом Пеано, в которых так нельзя.
Просто индукцией по $n$ докажите $\forall n: n = 0 \wedge n \in B_0$.

[QuantumCoder]

mihaild
Решил все-таки доделать эту задачу Предложенное Вами утверждение легко доказывается по индукции, да. И из него слеудует, что пара $A_0$, $B_0$ существует и уникальна. Допустим для $N = k$ существует уникальная пара $A_k$, $B_k$, которая удовлетворяет свойствам $a-f$. Докажем для $N = k++$. Пусть $A_{k++} = A_k \cup \{k++\}$, $B_{k++} = B_k \backslash \{k++\}$. Свойства $a-c$ напрямую следуют из построения. Свойство $d$ легко доказывается:
$k++ \in B_k \implies (k++)++ \in B_k \implies (k++)++ \in B_{k++}$

А вот со свойством $e$ какой-то затык. Нам нужно доказать, что $n \in B_{k++} \implies n++ \in B_{k++}$
$n \in B_{k++} \implies n \in B_k \backslash \{k++\} \implies n++ \in B_k \implies n++ \notin A_k$
Теперь пойдем от противного, пусть $n++ \in A_{k++}$, но тогда из $n++ \notin A_k$ следует, что $n++ = k++$, то есть $n = k$. Теперь хочется доказать, что $k \in A_k$, тогда получили бы противоречие. Но как-то не получается этот шаг. Тут тоже нужна хитрая мат индукция? Или я вообще не тем путем пошел и можно проще? Напомню, что по условию задачи я могу пользоваться только аксиомами Пеано напрямую.

[mihaild]

QuantumCoder в сообщении #1644530 писал(а):

Теперь хочется доказать, что $k \in A_k$,

А Вы доказывайте индукцией сразу более сильное утверждение: что существует уникальная пара $A_k, B_k$ такая что выполнены нужные свойства и $k \in A_k$.