обобщённая аксиома подстановки/выбора

[маткиб]

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

Доказать, что для любой теоретико-множественной формулы $\Phi(x,y)$ следующее утверждение является теоремой ZFC:

Если для любого $x\in A$ существует такой $y$, что $\Phi(x,y)$, то существует такая функция $f$ с областью определения $A$, что $\Phi(x,f(x))$ при любом $x\in A$.

[AGu]

Тут может помочь принцип отражения, а точнее, лемма к нему
(см. Т.Йех, Теория множеств и метод форсинга, $\S$10, лемма 30),
согласно которой
$(\forall\,A)(\exists\,B\supset A)(\forall\,x\in B)\bigl(\,(\exists y)\,\Phi(x,y)\Leftrightarrow(\exists y\in B)\,\Phi(x,y)\,\bigr)$.

P.S. Если что, могу набросать идею доказательства
(хотя, откровенно говоря, лень ).

[маткиб]

Было бы интересно увидеть доказательство, придуманное человеком, не читавшим Йеха, Коэна или подобных книжек (чтобы это было маленьким открытием ).

[AGu]

маткиб писал(а):

Было бы интересно увидеть доказательство, придуманное человеком, не читавшим Йеха, Коэна или подобных книжек (чтобы это было маленьким открытием ).

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

[ddn]

маткиб писал(а):

Доказать, что для любой теоретико-множественной формулы $\Phi(x,y)$ следующее утверждение является теоремой ZFC:
Если для любого $x\in A$ существует такой $y$, что $\Phi(x,y)$, то существует такая функция $f$ с областью определения $A$, что $\Phi(x,f(x))$ при любом $x\in A$.

AGu писал(а):

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

Ну что Вы! Никаких ординалов и иерархий не нужно!

Используйте просто схему-аксиому подстановки:
$\forall\phi(\cdot,\cdot,\cdot|_{i=1}^n)\{\forall z_i\}_{i=1}^n$...$\forall A$
$(\forall x\exists C\forall y(y\in C\Leftrightarrow\phi(x,y,z))\Leftrightarrow\exists B\forall C(C\in B\Leftrightarrow\exists x\forall y(y\in C\Leftrightarrow\phi(x,y,z))))$
где, очевидно единственное, $B$ представляет собой множество $\{\{y|\phi(x,y,z)\}|x\in A\}$, а условием его существования является существование множеств $C(x)=\{y|\phi(x,y,z)\}$ для любого $x\in A$;
здесь взята последовательность переменных $z=z_i|_{i=1}^n=z_1,...,z_n$ (где $n\in\mathbb{N}_0$);

и аксиому выбора:
$\forall A(\{\}\not\in A\Rightarrow\exists B\forall x\in A\exists! y\in x((x,y)\in B))$
Здесь, упорядоченная пара определена как $(x,y)=\{\{x\},\{x,y\}\}$; а $\exists!$ означает существует и единственно.
Если воспользоваться аксиомой выделения, то можно получить множество, очищенное от посторонних элементов: $B_0=\{w|w\in B\wedge\exists x\in A\exists y\in x(w=(x,y))\}$


Если для каждого $x\in A$ существует непустое множество $C(x)=\{y|\Phi(x,y)\}$, то по аксиоме подстановки для формулы $\Phi(x,y)$ устанавливаем существование множества $D=\{\{y|\Phi(x,y)\}|x\in A\}$ без пустых элементов: $\{\}\not\in D$.

Учитывая, что множество $D$ существует, то существует и множества
$E=\{y|x\in A\wedge\Phi(x,y)\}=\bigcup D$ - по аксиоме объединения,
и $F=\{(x,y)|x\in A\wedge\Phi(x,y)\}=$
$=\{w|w\in\mathcal{P}(\mathcal{P}(A\cup E))\wedge\exists x\in A\exists y\in E(w=(x,y)\wedge\Phi(x,y))\}$ - по аксиоме степени и выделения.
Факт существования объединения двух множеств $A\cup E$ следует из применения аксиомы подстановки к формуле $\Upsilon(x,y)=(x=\{\}\Rightarrow y\in A)\wedge(x=\{\{\}\}\Rightarrow y\in E)$ над двухэлементным множеством $\{\{\},\{\{\}\}\}$. Это двухэлементное множество существует как двойная степень пустого множества $\{\{\},\{\{\}\}\}=\mathcal{P}(\mathcal{P}(\{\}))$, существование же пустого множества постулируется аксиоматически или выводится с помощью аксиомы выделения из аксиомы существования некоторого множества $\exists X$, например бесконечного (аксиома бесконечности): $\{\}=\{x|x\in X\wedge\neg(x=x)\}$.

Тогда, применим аксиому подстановки для формулы $\Psi(x,w)=\exists y(w=(x,y)\wedge\Phi(x,y))$, так как при $x\in A$ множества $C(x)=\{(x,y)|\Phi(x,y)\}=\{w|\Psi(x,w)\}\subseteq F$ существуют как подмножества $F$, и докажем, тем самым, существование множества $B=\{\{w|\Psi(x,w)\}|x\in A\}=\{\{(x,y)|\Phi(x,y)\}|x\in A\}$.
Применяя к нему аксиому выбора, то есть отбирая из каждого непустого множества $C(x)=\{(x,y)|\Phi(x,y)\}\in B$ по одному элементу $(x,y_x)$, устанавливаем существование такого множества-функции $f=\{(x,y_x)|x\in A\}$, что $\Phi(x,f(x))$ для любого $x\in A$.

[маткиб]

ddn писал(а):

Используйте просто схему-аксиому подстановки:
$\forall\phi(\cdot,\cdot,\cdot|_{i=1}^n)\{\forall z_i\}_{i=1}^n$...$\forall A$
$(\forall x\exists C\forall y(y\in C\Leftrightarrow\phi(x,y,z))\Leftrightarrow\exists B\forall C(C\in B\Leftrightarrow\exists x\forall y(y\in C\Leftrightarrow\phi(x,y,z))))$

Что-то какая-то странная у Вас аксиома подстановки, которая, к тому же, неверна. Например, можно взять
$\phi(x,y,z)\equiv(y\in x)$.
Тогда левая часть $\forall x\exists C\forall y(y\in C\Leftrightarrow\phi(x,y,z))$ будет верна, а правая $\exists B\forall C(C\in B\Leftrightarrow\exists x\forall y(y\in C\Leftrightarrow\phi(x,y,z)))$ - неверна (она будет выражать существование множества всех множеств).
Дальше не читал.

Добавлено спустя 8 минут 25 секунд:

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

Добавлено спустя 11 минут 32 секунды:

А вот и ошибка:

ddn писал(а):

Если для каждого $x\in A$ существует непустое множество $C(x)=\{y|\Phi(x,y)\}$, ...

и далее по тексту предложенного решения рассуждения проводятся в предположении этого существования.

В задаче ничего не сказано про существование такого множества $C(x)$ для любого $x\in A$, а оно может и не существовать, например, если $\Phi(x,y)$ - тождественная истина. Соль задачи как раз в том, чтобы обойти это несуществование!

[ddn]

маткиб писал(а):

А вот и ошибка:

ddn писал(а):

Если для каждого $x\in A$ существует непустое множество $C(x)=\{y|\Phi(x,y)\}$, ...

и далее по тексту предложенного решения рассуждения проводятся в предположении этого существования.

В задаче ничего не сказано про существование такого множества $C(x)$ для любого $x\in A$, а оно может и не существовать, например, если $\Phi(x,y)$ - тождественная истина. Соль задачи как раз в том, чтобы обойти это несуществование!

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

Есть четырехтомник "Справочник по мат. логике" - это первая книжка, где я познакомился (том III) с аксиоматическим изложением теории множеств и индуктивным, то есть пошаговым, построением множеств - хорошая книжка, ясное изложение. Там аналогично решается вопрос об категоричном выборе множества - представителя множеств данной мощности, когда аксиома выбора отсутствует (кардиналы здесь уже не выполняют своих функций):
отбираются множества данной мощности, принадлежащие минимальной иерархии, содержащей такие множества - а эта подсовокупность множеств сама является множеством по включению в иерархию.

В нашей "задаче" также отыскивается минимальная иерархия-множество $\mathcal{P}_{\alpha}$ (с минимальным ординальным уровнем $\alpha$), в которой присутствуют множества $y$ из совокупности (класса) множеств, удовлетворяющих свойству $\Phi(x,y)$. Хоть одна такая иерархия найдется (значит найдется и минимальная), ибо объединение всех иерархий - класс $\mathcal{P}_{On}=\bigcup\limits_{\alpha\in On}\mathcal{P}_{\alpha}$ совпадает с классом всех множеств $V$, а совокупность $\Phi(x,y)$ по условию непуста. Некоторое непустое подмножество $C(x)\cap\mathcal{P}_{\alpha}$ вообще говоря класса $C(x)=\{y|\Phi(x,y)\}$ всегда найдется, и для его получения через аксиому подстановки можно сконструировать соответствующую формулу - так что нет нужны изменять этот пункт в доказательстве.
Все эти рассуждения можно сформулировать и без использования классов - применяя трансфинитую индукцию.

Справка:
Иерархии для определяются по индукции $\mathcal{P}_{\alpha}=\bigcup\limits_{\beta\in\alpha}\mathcal{P}(\mathcal{P}_{\beta})$ для всех ординалов $\alpha\in On$.
Очевидно $\mathcal{P}_{0}=\{\}$ и $\mathcal{P}_{\beta}\subset\mathcal{P}_{\alpha}$ при $\beta<\alpha$ (эквивалентно: при $\beta\in\alpha$, при $\beta\subset\alpha$).
Каждая иерархия $\mathcal{P}_{\alpha}$ - множество.

Как видите, здесь представлена только общая схема доказательства, ибо строгий формальный вывод его непосредственно из аксиом слишком длинный: транзитивные множества$\to$ординалы$\to$иерархии.
Ваше утверждение гарантировано доказуемо лишь когда класс всех множеств совпадает с классом $\mathcal{P}_{On}$ всех множеств, индуктивно построенных из пустого - что справедливо лишь при выполнении аксиомы фундирования. Ведь может оказаться, что все множества $y$, удовлетворяющие свойству $\Phi(x,y)$, неидуктивны (найдется бесконечная цепочка $y\ni y_1\ni...\ni y_i\ni...$) и категорично выделить (т.е. выделить формулой) из них непустое подмножество будет невозможно. Без этого пункта доказательство не сделать!
Нужно использовать аксиому фундирования, а значит иерархии (здесь AGu прав), а там где иерархии - там громоздкие формальные доказательства.

В общем, я хочу сказать, что это не олимпиадная задачка - слишком громоздкий формализм. Это вообще не задача. Задачи касаются частных примеров, а ваш вопрос относится к фундаментальным вещам.
Ваше утверждение относится к классу так называемых элементарных следствий аксиоматической теории, раскрывающей суть теории и назначение ее аксиом. Не секрет, что аксиомы стараются изложить наиболее сжато, в наиболее ослабленной формулировке и чтобы наглядно продемонстрировать их основное содержание, приходиться делать ряд простых следствий: например, в теории групп приходится доказывать единственность нейтрального и обратного элемента, в теории векторных пространств - доказывать коммутативность сложения векторов и т.д. Но не называть же это задачами?

[маткиб]

ddn, идея доказательства верна.

ddn в сообщении #167600 писал(а):

В общем, я хочу сказать, что это не олимпиадная задачка - слишком громоздкий формализм

С этим я не согласен. Тут не нужен формализм, всё можно объяснить на идейном уровне. Например,

Идея 1. Для любого кардинала существует множество всех множеств, мощность транзитивного замыкания которых не превосходит этого кардинала (транзитивное замыкание $\mathrm{TrClos}(x)$ - это минимальное по включению множество, включающее $x$ и содержащее все элементы своих элементов). Это легко понять, если представлять множества в виде корневых деревьев (листья - пустые множества), при таком представлении мощность транзитивного замыкания - это количество вершин дерева.

Идея 2. Рассмотрим формулу $\Psi(x,y)$, гласящую, что $y$ есть минимальный кардинал, для которого существует такой $z$, что $\Phi(x,z)$ и $|\mathrm{TrClos}(z)|\leq y$. Применим аксиому подстановки и получим множество всех таких кардиналов для всех $x\in A$. Затем применим аксиому объединения и получим кардинал $c$, который их всех не меньше. Теперь рассматриваем только элементы $y$, для которых $|\mathrm{TrClos}(y)|\leq c$ (множество всех таких элементов существует), далее всё очевидно.

Идея 3. Проблема в том, что кардинал, вообще говоря, не является множеством. Но, к счастью, можно использовать такое определение (см. книгу Йеха): кардинал - это ординал, не равномощный никакому меньшему ординалу, ординал - это транзитивно замкнутое множество, все элементы которого транзитивно замкнуты (для ординалов $x<y$ означает $x\in y$).

ddn в сообщении #167600 писал(а):

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

Аксиома фундирования в ZFC входит. Надо заметить, что нефундированные множества - это "вещи в себе", их рассматривать - это большое извращение. Поэтому аксиома фундирования - вполне естественное требование к множествам, а не просто формально выписанная аксиома.