Схема аксиомы замены

В теории множеств схема аксиом замены — это схема аксиом образ в теории множеств Цермело-Френкеля (ZF), которая утверждает, что любого множества при любом определимом отображении также является множеством. Это необходимо для построения некоторых бесконечных множеств в ZF.

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

Заявление

Схема аксиомы замены: изображение $F[A]$ из набора доменов $A$ под определяемой функцией класса $F$ сам по себе является набором, $B$.

Предполагать $P$ — определимое бинарное отношение (которое может быть собственным классом ), такое, что для каждого набора $x$ есть уникальный набор $y$ такой, что $P(x,y)$ держит. Существует соответствующая определимая функция $F_{P}$, где $F_{P}(x)=y$ тогда и только тогда, когда $P(x,y)$. Рассмотрим (возможно, собственный) класс $B$ определено так, что для любого множества $y$, $y\in B$ тогда и только тогда, когда существует $x\in A$ с $F_{P}(x)=y$. $B$ называется изображением $A$ под $F_{P}$и обозначили $F_{P}[A]$ или (используя обозначение set-builder ) $\{F_{P}(x):x\in A\}$.

Схема аксиом замены гласит, что если $F$ является определяемой функцией класса, как указано выше, и $A$ любое множество, то изображение $F[A]$ это тоже набор. Это можно рассматривать как принцип малости: аксиома гласит, что если $A$ достаточно мал, чтобы быть множеством, тогда $F[A]$ также достаточно мал, чтобы представлять собой набор. Это подразумевается более сильной аксиомой ограничения размера .

Поскольку невозможно дать количественную оценку определяемым функциям в логике первого порядка, для каждой формулы включается один экземпляр схемы. $\phi$ на языке теории множеств со свободными переменными среди $w_{1},\dotsc ,w_{n},A,x,y$; но $B$ не является бесплатным в $\phi$. На формальном языке теории множеств схема аксиом выглядит следующим образом:

${\begin{aligned}\forall w_{1},\ldots ,w_{n}\,\forall A\,([\forall x\in A&\,\exists !y\,\phi (x,y,w_{1},\ldots ,w_{n},A)]\ \Longrightarrow \ \exists B\,\forall y\,[y\in B\Leftrightarrow \exists x\in A\,\phi (x,y,w_{1},\ldots ,w_{n},A)])\end{aligned}}$

По смыслу $\exists !$, см. количественную оценку уникальности .

Для ясности, в случае отсутствия переменных $w_{i}$, это упрощается до:

${\begin{aligned}\forall A\,([\forall x\in A&\,\exists !y\,\phi (x,y,A)]\ \Longrightarrow \ \exists B\,\forall y\,[y\in B\Leftrightarrow \exists x\in A\,\phi (x,y,A)])\end{aligned}}$

Поэтому всякий раз, когда $\phi$ указывает уникальный $x$-к- $y$ соответствие, похожее на функцию $F$ на $A$, тогда все $y$ Достигнутые таким образом, можно собрать в набор $B$, сродни $F[A]$.

Приложения

Схема аксиом замены не требуется для доказательства большинства теорем обычной математики. Действительно, теория множеств Цермело (Z) уже может интерпретировать арифметику второго порядка и большую часть теории типов в конечных типах, что, в свою очередь, достаточно для формализации основной части математики. Хотя схема аксиом замены сегодня является стандартной аксиомой в теории множеств, ее часто исключают из систем теории типов и базовых систем теории топоса .

В любом случае, схема аксиом резко увеличивает силу ZF как с точки зрения теорем, которые она может доказать (например, множеств, существование которых показано), так и с точки зрения ее теоретической непротиворечивости по сравнению с Z. Некоторые важные примеры следуют:

• Используя современное определение фон Неймана , доказательство существования любого предельного ординала, большего, чем ω, требует аксиомы замены. Порядковый номер ω·2 = ω + ω является первым таким порядковым числом. Аксиома бесконечности утверждает существование бесконечного множества ω = {0, 1, 2, ...}. Можно надеяться определить ω·2 как объединение последовательности {ω, ω + 1, ω + 2,...}. Однако произвольные такие классы ординалов не обязательно должны быть множествами - например, класс всех ординалов не является множеством. Замена теперь позволяет заменить каждое конечное число n в ω соответствующим ω + n и, таким образом, гарантирует, что этот класс является множеством. В качестве пояснения отметим, что можно легко построить хорошо упорядоченное множество , изоморфное ω · 2, не прибегая к замене – просто возьмите непересекающееся объединение двух копий ω, причем вторая копия больше первой – но это не является порядковым, поскольку не полностью упорядочен по включению.
• Большие порядковые номера меньше зависят от замены. Например, ω1 _, первый несчетный ординал , можно построить следующим образом – множество счетных порядков ям существует как подмножество $P({\mathbb {N} }\times {\mathbb {N} })$ разделением является и набором степеней ( отношение на A подмножеством $A\times A$, и поэтому элемент набора степеней $P(A\times A)$. Таким образом, совокупность отношений является подмножеством $P(A\times A)$)). Замените каждое упорядоченное множество его порядковым номером. Это набор счетных ординалов ω ₁ , который сам по себе несчетен. В конструкции дважды используется замена; один раз, чтобы обеспечить присвоение порядкового номера для каждого хорошо упорядоченного набора, и еще раз, чтобы заменить хорошо упорядоченные наборы их порядковыми номерами. Это частный случай результата числа Хартогса , а общий случай доказывается аналогично.
• В свете вышесказанного существование присвоения порядкового номера каждому упорядоченному множеству также требует замены. Точно так же кардинальное присвоение фон Неймана , которое присваивает кардинальное число каждому множеству, требует замены, а также аксиомы выбора .
• Для наборов кортежей, рекурсивно определяемых как $A^{n}=A^{n-1}\times A$ и для больших $A$, набор $\{A^{n}\mid n\in {\mathbb {N} }\}$ имеет слишком высокий ранг, чтобы его существование можно было доказать с помощью теории множеств, используя только аксиому степенного множества, выбора и без замены.
• Точно так же Харви Фридман показал, что замена необходима, чтобы показать, что Бореля детерминированы игры . Доказанным результатом является Дональда А. Мартина теорема Бореля об детерминированности .
• ZF с заменой доказывает непротиворечивость Z, поскольку множество V _ω·2 является моделью Z, существование которой можно доказать в ZF. Кардинальное число $\aleph _{\omega }$ является первой, существование которой можно показать в ZF, но не в Z. Для пояснения отметим, что вторая теорема Гёделя о неполноте показывает, что каждая из этих теорий содержит предложение, «выражающее» собственную непротиворечивость теории, что недоказуемо в этой теории. , если эта теория непротиворечива - этот результат часто грубо выражается как утверждение, что ни одна из этих теорий не может доказать свою непротиворечивость, если она непротиворечива.

Связь с другими схемами аксиом

Упрощения

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

$\forall A\,([\forall x\,\exists !y\,\phi (x,y,A)]\ \Longrightarrow \ \exists B\,\forall y\,[y\in B\Leftrightarrow \exists x\in A\,\phi (x,y,A)])$

Коллекция

Схема аксиомы коллекции: изображение $f[A]$ из набора доменов $A$ под определяемой функцией класса $f$ попадает в набор $B$.

Схема аксиом сбора тесно связана со схемой аксиом замены и ее часто путают. В остальных аксиомах ZF она эквивалентна схеме аксиом замены. Аксиома сбора сильнее замены в отсутствие аксиомы набора мощности. или его конструктивный аналог ZF , но более слабый в рамках IZF, в котором отсутствует закон исключенного третьего .

В то время как замена может означать, что образ функции является набором, коллекция говорит об образах отношений, а затем просто говорит, что некоторый суперкласс изображения отношения является набором. Другими словами, полученный набор $B$ не имеет требования минимальности, т.е. в этом варианте также отсутствует требование уникальности $\phi$. То есть отношение, определяемое $\phi$ не обязательно должна быть функцией — некоторые $x\in A$ может соответствовать многим $y$в $B$. В этом случае набор изображений $B$ существование которого утверждается, должно содержать хотя бы один такой $y$ для каждого $x$ в исходном наборе, без гарантии, что он будет содержать только один.

Предположим, что свободные переменные $\phi$ входят в число $w_{1},\dotsc ,w_{n},x,y$; но ни $A$ ни $B$ бесплатно в $\phi$. Тогда схема аксиом такова:

$\forall w_{1},\ldots ,w_{n}\,[(\forall x\,\exists \,y\phi (x,y,w_{1},\ldots ,w_{n}))\Rightarrow \forall A\,\exists B\,\forall x\in A\,\exists y\in B\,\phi (x,y,w_{1},\ldots ,w_{n})]$

Схема аксиом иногда формулируется без предварительных ограничений (кроме $B$ не происходит бесплатно в $\phi$) по предикату, $\phi$:

$\forall w_{1},\ldots ,w_{n}\,\forall A\,\exists B\,\forall x\in A\,[\exists y\phi (x,y,w_{1},\ldots ,w_{n})\Rightarrow \exists y\in B\,\phi (x,y,w_{1},\ldots ,w_{n})]$

В этом случае могут присутствовать элементы $x$ в $A$ которые не связаны ни с какими другими множествами посредством $\phi$. Однако указанная схема аксиом требует, чтобы, если элемент $x$ из $A$ связан хотя бы с одним набором $y$, то набор изображений $B$ будет содержать хотя бы один такой $y$. Полученную схему аксиом также называют схемой аксиом ограниченности .

Разделение

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

$\forall A\,\exists B\,\forall C\,(C\in B\Leftrightarrow [C\in A\land \theta (C)])$

для каждой формулы $\theta$ на языке теории множеств, в которой $B$ не является бесплатным, т.е. $\theta$ это не упоминает $B$.

Доказательство следующее: либо $A$ содержит некоторый элемент $a$ проверка $\theta (a)$, или это не так. В последнем случае, взяв за $B$ выполняет соответствующий экземпляр схемы аксиом разделения, и все готово. В противном случае выберите такой фиксированный $a$ в $A$ что подтверждает $\theta (a)$. Теперь определите $\phi (x,y):=(\theta (x)\land y=x)\lor (\neg \theta (x)\land y=a)$ для использования с заменой. Использование обозначения функции для этого предиката $\phi$, он действует как тождество $F_{a}(x)=x$ где угодно $\theta (x)$ верно и как постоянная функция $F_{a}(x)=a$ где угодно $\theta (x)$ является ложным. Путем анализа случая возможные значения $y$ уникальны для любого $x$, значение $F_{a}$ действительно представляет собой функцию класса. В свою очередь, образ $B:=\{F_{a}(x):x\in A\}$ из $A$ под $F_{a}$, то есть класс $A\cap \{x:\theta (x)\}$, по аксиоме замены считается множеством. Этот $B$ точно подтверждает аксиому разделения.

Этот результат показывает, что возможно аксиоматизировать ZFC с помощью одной бесконечной схемы аксиом. Поскольку требуется по крайней мере одна такая бесконечная схема (ZFC не является конечно аксиоматизируемой), это показывает, что схема аксиом замены при желании может выступать в качестве единственной бесконечной схемы аксиом в ZFC. Поскольку схема аксиом разделения не является независимой, ее иногда исключают из современных формулировок аксиом Цермело-Френкеля.

Однако разделение по-прежнему важно для использования во фрагментах ZFC из-за исторических соображений и для сравнения с альтернативными аксиоматизациями теории множеств. Формулировка теории множеств, которая не включает аксиому замены, вероятно, будет включать в себя некоторую форму аксиомы разделения, чтобы гарантировать, что ее модели содержат достаточно богатую коллекцию множеств. При изучении моделей теории множеств иногда полезно рассматривать модели ZFC без замены, например модели $V_{\delta }$ в иерархии фон Неймана.

Доказательство, приведенное выше, предполагает закон исключенного третьего для предложения о том, что $A$ населён проверяющим множеством, $\theta$, и для любого $\theta (x)$ когда устанавливается, что отношение $\phi$ является функциональным. Аксиома разделения явно включена в конструктивную теорию множеств или ее ограниченный вариант .

Отражение

Основная статья: Принцип отражения

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

Для любого $x_{1},\ldots ,x_{n}$ и любая формула первого порядка $\phi (x_{1},\ldots ,x_{n})$, существует $\alpha$ такой, что $\phi (x_{1},\ldots ,x_{n})\iff \phi ^{V_{\alpha }}(x_{1},\ldots ,x_{n})$.

Это схема, состоящая из счетного числа утверждений, по одному на каждую формулу. $\phi$. Здесь, $\phi ^{M}$ означает $\phi$ со всеми кванторами, ограниченными $M$, то есть $\phi$ но с каждым экземпляром $\exists x$ и $\forall x$ заменен на $\exists (x\in V_{\alpha })$ и $\forall (x\in V_{\alpha })$ соответственно.

История

Схема аксиом замены не была частью аксиоматизации теории множеств Эрнста Цермело 1908 года ( Z ). Некоторое неформальное приближение к нему существовало в Мириманова неопубликованных работах Кантора, и неформально оно снова появилось у ( 1917).

Авраам Френкель, между 1939 и 1949 годами.

Торальф Скулем, 1930-е годы.

Ее публикация Абрахамом Френкелем в 1922 году стала основой современной теории множеств — теории множеств Цермело- Френкеля ( ZFC ). Аксиома была независимо открыта и объявлена ​​Торальфом Скулемом позже в том же году (и опубликована в 1923 году). Сам Цермело включил аксиому Френкеля в свою пересмотренную систему, которую он опубликовал в 1930 году, которая также включала в качестве новой аксиомы аксиому основания фон Неймана . Хотя сегодня мы используем первую версию списка аксиом Скулема, он обычно не получает должного признания, поскольку каждая отдельная аксиома была ранее разработана либо Цермело, либо Френкелем. Фраза «теория множеств Цермело-Френкеля» впервые была использована в печати фон Нейманом в 1928 году.

Цермело и Френкель активно переписывались в 1921 году; аксиома замены была основной темой этого разговора. Френкель начал переписку с Цермело где-то в марте 1921 года. Однако его письма до письма от 6 мая 1921 года утеряны. Цермело впервые признал пробел в своей системе в ответе Френкелю от 9 мая 1921 года. 10 июля 1921 года Френкель завершил и представил для публикации статью (опубликованную в 1922 году), в которой его аксиома описывалась как допускающая произвольные замены: « M Если множество и каждый элемент М заменяется [набором или ур-элементом], тогда М снова превращается в множество» (завершение в скобках и перевод Эббингауза). Публикация Френкеля 1922 года поблагодарила Цермело за полезные аргументы. Перед этой публикацией Френкель публично объявил о своей новой аксиоме на собрании Немецкого математического общества, состоявшемся в Йене 22 сентября 1921 года. Цермело присутствовал на этом собрании; в дискуссии после выступления Френкеля он принял аксиому замены в общих чертах, но высказал оговорки относительно ее масштабов.

Торальф Скулем обнародовал свое открытие пробела в системе Цермело (того самого пробела, который нашел Френкель) в докладе, который он произнес 6 июля 1922 года на V Конгрессе скандинавских математиков , проходившем в Хельсинки ; материалы этого конгресса были опубликованы в 1923 году. Скулем представил резолюцию в терминах определяемых замен первого порядка: «Пусть U — определенное предложение, справедливое для определенных пар ( a , b ) в области B ; предположим далее, что для для каждого a существует не более одного b такого, что U истинно. Тогда, поскольку a пробегает все элементы множества M _a , b пробегает все элементы множества M _b ». В том же году Френкель написал рецензию на статью Скулема, в которой Френкель просто заявил, что соображения Скулема соответствуют его собственным.

Сам Цермело никогда не принимал формулировку Скулема схемы аксиом замещения. В какой-то момент он назвал подход Скулема «теорией множеств бедных». Цермело предвидел систему, которая позволила бы иметь крупных кардиналов . Он также решительно возражал против философских последствий счетных моделей теории множеств , которые следовали из аксиоматизации Скулема первого порядка. Согласно биографии Цермело, написанной Хайнцем-Дитером Эббингаузом , неодобрение Цермело подхода Скулема ознаменовало конец влияния Цермело на развитие теории множеств и логики.

Ссылки

• Эббингауз, Хайнц-Дитер (2007), Эрнст Цермело: подход к его жизни и работе , Springer Science & Business Media, ISBN  978-3-540-49553-6 .
• Халмош, Пол Р. (1974) [1960], Наивная теория множеств , Springer-Verlag, ISBN  0-387-90092-6 .
• Джех, Томас (2003), Теория множеств: издание третьего тысячелетия, исправленное и расширенное , Springer, ISBN  3-540-44085-2 .
• Кунен, Кеннет (1980), Теория множеств: введение в доказательства независимости , Elsevier, ISBN  0-444-86839-9 .