Трансфинитная индукция

[bubu gaga]

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

2. В википедии написано, "Трансфинитная индукция — метод доказательства, обобщающий математическую индукцию на случай несчетного числа значений параметра". Означает ли это, что с помощью трансфинитных чисел можно "конструировать" множества равномощные континууму?

Спасибо.

[Someone]

bubu gaga в сообщении #139174 писал(а):

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

Вопрос неправильно сформулирован. Обычная математическая индукция (по натуральным числам) может не то, чтобы не работать, а просто быть недостаточной.

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

bubu gaga в сообщении #139174 писал(а):

2. В википедии написано, "Трансфинитная индукция — метод доказательства, обобщающий математическую индукцию на случай несчетного числа значений параметра".

Не обязательно несчётного. Может быть, значения параметра пробегают счётный ординал, больший первого бесконечного $\omega_0$, который отождествляется с натуральным рядом.

bubu gaga в сообщении #139174 писал(а):

Означает ли это, что с помощью трансфинитных чисел можно "конструировать" множества равномощные континууму?

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

[zoo]

bubu gaga писал(а):

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

см. например доказательство теоремы Хана-Банаха в линейном пространстве в котором нет счетного базиса

[AD]

А ещё первые интегралы Данжуа работали на трансфинитной индукции

[Виктор Викторов]

Трансфинитная индукция используется не только для доказательств, но и для задания (построения) функций на вполне упорядоченных множествах. Френкель (тот самый который вторая буква в ZFC) доказывает специальную теорему о единственности и существовании такой функции, если дано рекурсивное правило, которое каждому элементу вполне упорядоченного множества придает некоторое вполне определённое значение определяемое этим правилом с помощью значений для всех элементов этого множества предшествующих данному элементу. Френкель пишет, что Кантор пользовался трансфинитной индукций для построения функций, считая этот метод очевидным, но фон Нёйман обнаружил некую дыру. Теперь эта дыра оформлена специальной легко доказываемой теоремой. Но я так и не смог понять в чём дыра?

[Профессор Снэйп]

bubu gaga в сообщении #139174 писал(а):

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

Существует такое множество точек плоскости, что любая прямая проходит ровно через две точки этого множества. Попробуйте докажите сей факт без трансфинитной индукции

[AGu]

Виктор Викторов в сообщении #259891 писал(а):

Френкель пишет, что Кантор пользовался трансфинитной индукций для построения функций, считая этот метод очевидным, но фон Нёйман обнаружил некую дыру. Теперь эта дыра оформлена специальной легко доказываемой теоремой. Но я так и не смог понять в чём дыра?

Чтобы получить возможность увидеть дыру в рассуждении было бы неплохо для начала увидеть само рассуждение. Френкель ничего более конкретного по этому поводу не говорит? (Кстати, где именно? В какой книге/статье, в каком разделе?)

[Виктор Викторов]

Речь идёт о книге: Abraham A. Fraenkel «Abstract Set Theory». Цитирую по первому изданию 1953 года cтр. 250: «Everyone had shared the conviction that theorem 6 was sufficient not only to prove but also to define (construct) with the aid of transfinite induction, and even the strictest and most profound of the contemporary textbooks and handbooks of the theory treat the subject in the light of this attitude. Only in the twenties did J. von Neumann discover that a gap had been left at this juncture of the theory of well-ordered sets and ordinal numbers. The nature of this gap will be easily understood from the following theorem and its proof.»
Дальше идёт теорема о существовании и единственности функции, заданной рекурсивным правилом с помощью трансфинитной индукции. Доказательство единственности проводится традиционным для трансфинитной индукции способом: рассматриваются две такие функции, а так как область определения вполне упорядоченное множество, то у подмножества элементов на которых значения этих функций различаются имеется первый элемент. И, следовательно, учитывая, что функции совпадают на всех предшествующих элементах, по рекурсивному правилу они должны совпасть и на этом первом элементе. Противоречие. А вот дальше доказывается существование такой функции. Доказательство прозрачно и просто. Так как вполне упорядоченное множество (область определения) не является отрезком никакого из своих элементов, то доказывается лемма, что функция определена на каждом начале (initial) этого множества. Почему не проходит стандартное рассуждение используемое при доказательстве единственности? Из-за того, что само множество не является своим отрезком? Но для каждого элемента значение функции определено рекурсивным правилом с помощью всех элементов предшествующих этому элементу.

[Профессор Снэйп]

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

[Виктор Викторов]

Нет. Мы не определяем функцию на «немножестве» всех ординалов. Просто на некотором вполне упорядоченном множестве. Тут скорее, что-то связанное с тем фактом, что каждое вполне упорядоченное множество не является своим отрезком. Кстати, первое издание Abraham A. Fraenkel «Abstract Set Theory» есть в http://lib.homelinux.org/.

[AGu]

Виктор Викторов в сообщении #260527 писал(а):

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

Какая такая «функция»? Ее ведь еще нет. Мы ведь только доказываем ее существование. На самом деле доказывается, что существует множество $F$ функций $f_I$, определенных на начальных фрагментах $I\subseteq S$ и удовлетворяющих нашему рекурсивному правилу. (Существование такого $F$ можно доказать с помощью аксиомы подстановки.) А итоговая функция $f$ потом строится по $F$. (В качестве $f$ можно взять объединение $F$ или, что в данном случае то же самое, наибольший по включению элемент $f_S$ множества $F$.)

Виктор Викторов в сообщении #260527 писал(а):

Почему не проходит стандартное рассуждение используемое при доказательстве единственности?

Вот потому и не проходит. Функции еще нет, а мы уже хотим про «нее» что-то доказать — что, мол, «она» определена на всем множестве $S$.

[Виктор Викторов]

AGu в сообщении #260804 писал(а):

Какая такая «функция»? Ее ведь еще нет. Мы ведь только доказываем ее существование. На самом деле доказывается, что существует множество $F$ функций $f_I$, определенных на начальных фрагментах $I\subseteq S$ и удовлетворяющих нашему рекурсивному правилу. (Существование такого $F$ можно доказать с помощью аксиомы подстановки.) А итоговая функция $f$ потом строится по $F$. (В качестве $f$ можно взять объединение $F$ или, что в данном случае то же самое, наибольший по включению элемент $f_S$ множества $F$.)

Итак, функции еще нет. И мы доказываем что существует множество $F$ функций $f_I$, определенных на каждом из начальных фрагментов $I\subseteq S$ и удовлетворяющих нашему рекурсивному правилу. Все эти функций на каждом элементе, на котором они определены, совпадают. И, именно, поэтому итоговая функция $f$ определена и на единственном начальном фрагменте, который не является отрезком – всём множестве. Здесь всё ясно.

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

Уважаемый AGu!

Буду Вам благодарен, если Вы покажете, как используется аксиома подстановки для доказательства существования множества $F$ функций $f_I$. Также я впечатлён Вашим переводом в данном контексте слова «initial», как «начальный фрагмент». Сами придумали или нашли в литературе?

[AGu]

Виктор Викторов в сообщении #261107 писал(а):

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

Хмм... Область определения чего?

Виктор Викторов в сообщении #261107 писал(а):

Получается, что наша функция [...]

Какая функция?

Виктор Викторов в сообщении #261107 писал(а):

Но тут возникает ещё один вопрос. Почему нельзя считать, что раз функция [...]

Какая функция?

Виктор Викторов в сообщении #261107 писал(а):

Уважаемый AGu!

Буду Вам благодарен, если Вы покажете, как используется аксиома подстановки для доказательства существования множества $F$ функций $f_I$.

Пусть $\varphi(I,f)$ — формальная запись утверждения о том, что $I$ является начальным фрагментом, а $f$ — функция, определенная на $I$ и удовлетворяющая нашему рекурсивному правилу. С помощью трансфинитной индукции легко показать, что для каждого $I$ существует не более одного $f$ такого, что $\varphi(I,f)$. Применяя аксиому подстановки с формулой $\varphi$ к множеству начальных фрагментов, получаем искомое $F$.

Виктор Викторов в сообщении #261107 писал(а):

«начальный фрагмент». Сами придумали или нашли в литературе?

Трудно сказать. Само всплыло. Наверняка где-то видел. Еще всплывает «начальный сегмент». Возможно, это более традиционный термин.

[Виктор Викторов]

Уважаемый AGu!

В трёх комментариях Вы говорите, что функции ещё нет. Поэтому я возвращаюсь к Вашему предыдущему комментарию, где Вы пишете об этом подробно:

AGu в сообщении #260804 писал(а):

Какая такая «функция»? Ее ведь еще нет. Мы ведь только доказываем ее существование. На самом деле доказывается, что существует множество $F$ функций $f_I$, определенных на начальных фрагментах $I\subseteq S$ и удовлетворяющих нашему рекурсивному правилу. (Существование такого $F$ можно доказать с помощью аксиомы подстановки.) А итоговая функция $f$ потом строится по $F$. (В качестве $f$ можно взять объединение $F$ или, что в данном случае то же самое, наибольший по включению элемент $f_S$ множества $F$.)

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

AGu в сообщении #264115 писал(а):

Пусть $\varphi(I,f)$ — формальная запись утверждения о том, что $I$ является начальным фрагментом, а $f$ — функция, определенная на $I$ и удовлетворяющая нашему рекурсивному правилу. С помощью трансфинитной индукции легко показать, что для каждого $I$ существует не более одного $f$ такого, что $\varphi(I,f)$. Применяя аксиому подстановки с формулой $\varphi$ к множеству начальных фрагментов, получаем искомое $F$.

Правильно ли я Вас понял, что функции $f$ существуют до применения аксиомы подстановки, а вот множество $F$ появляется только в результате аксиомы подстановки? Т. е. в данном случае совокупность уже существующих объектов является множеством только на основании аксиомы подстановки?

AGu в сообщении #264115 писал(а):

Виктор Викторов в сообщении #261107 писал(а):

«начальный фрагмент». Сами придумали или нашли в литературе?

Трудно сказать. Само всплыло. Наверняка где-то видел. Еще всплывает «начальный сегмент». Возможно, это более традиционный термин.

Мне кажется, что «начальный сегмент» менее удачный термин. Сегмент ассоциируется с интервалом имеющим концы.

[AGu]

Виктор Викторов в сообщении #264279 писал(а):

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

Фраза «если уже заданы значения для всех элементов предшествующих данному элементу» означает, что значение $f(x)$ искомой функции $f$ на данном элементе $x\in S$ определяется некоторой конструкцией $v$ по сужению $f|_{S_x}$ функции $f$ на $S_x:=\{y\in S:y<x\}$. Стало быть, все, что у нас пока есть, — это условие на искомую функцию $f$, имеющее вид $(\forall\,x\in S)\ f(x)=v(f|_{S_x})$. Проблема в том, что в равенстве $f(x)=v(f|_{S_x})$ в правой части участвует символ $f$. Если бы его там не было, т.е. если бы было выражение вида $f(x)=v(S_x)$, то действительно каждому элементу $x\in S$ было бы сопоставлено «конкретное» множество $v(S_x)$. Но при участии в правой части символа $f$ это не «конкретное» множество, а множество, определяемое самой функцией $f$, существование которой нам еще предстоит доказать.

Поэтому изначально у нас нет конкретного «задания функции», у нас есть лишь условие на функцию. Рекурсивное. Не было бы рекурсии — было бы «задание» $f(x):=v(S_x)$. И тогда искомая функция возникла бы гораздо проще — сразу из аксиомы подстановки — как множество $\bigl\{\bigl(x,v(S_x)\bigr):x\in S\bigr\}$.

Виктор Викторов в сообщении #264279 писал(а):

Правильно ли я Вас понял, что функции $f$ существуют до применения аксиомы подстановки, а вот множество $F$ появляется только в результате аксиомы подстановки? Т. е. в данном случае совокупность уже существующих объектов является множеством только на основании аксиомы подстановки?

В общих чертах — да. Я не вчитывался в доказательство Френкеля, но думаю, идея там примерно такая. Сначала (трансфинитной индукцией) мы показываем, что для каждого $x\in S$ существует единственная определенная на $S_x$ функция $f_x$ такая, что $(\forall\,y\in S_x)\ f_x(y)=v(f_x|_{S_y})$. По аксиоме подстановки существует множество $F:=\{f_x:x\in S\}$. Наконец, применяя аксиому объединения, получаем искомую функцию $f:=\cup F=\bigcup_{x\in S}f_x$. Кстати, эта идея повторяет себя на предельном индукционном шаге: доказательство существования $f_x$ для предельного $x$ проводится по той же схеме. Т.е. доказательство получается как бы фрактальным. (И кажется, Френкель, что-то там оптимизировал, чтобы не повторяться.)