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

Концепция теории множеств

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

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

Заявление

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

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

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

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

${\displaystyle {\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}}}$

Значение см. в разделе « Количественная оценка уникальности» . ${\displaystyle \exists !}$

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

${\displaystyle {\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}}}$

Таким образом, всякий раз, когда указывается уникальное соответствие , подобное функции на , тогда все достигнутое таким образом может быть собрано в набор , аналогичный . ${\displaystyle \phi }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle F}$ ${\displaystyle A}$ ${\displaystyle y}$ ${\displaystyle B}$ ${\displaystyle F[A]}$

Приложения

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

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

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

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

Упрощения

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

${\displaystyle \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)])}$

Коллекция

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

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

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

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

${\displaystyle \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})]}$

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

${\displaystyle \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})]}$

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

Разделение

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

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

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

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

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

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

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

Отражение

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

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

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

История

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

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

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

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

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

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

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

Рекомендации

• Эббингауз, Хайнц-Дитер (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.

Цитаты

1. А. Канамори, «Похвала замене», стр. 74–75. Бюллетень символической логики, том. 18, нет. 1 (2012). По состоянию на 22 августа 2023 г.
2. Гитман, Виктория; Джоэл Дэвид Хэмкинс; Джонстон, Томас А. (2011). «Что такое теория ZFC без силового набора?». arXiv : 1110.2430 [math.LO].
3. А. Канамори, «Похвала замене», стр.73. Бюллетень символической логики, том. 18, нет. 1 (2012). По состоянию на 22 августа 2023 г.
4. Мэдди, Пенелопа (1988), «Веря в аксиомы. I», Журнал символической логики , 53 (2): 481–511, doi : 10.2307/2274520, JSTOR  2274520, MR  0947855, Ранние намеки на аксиому замены могут можно найти в письме Кантора к Дедекинду [1899 г.] и у Мириманова [1917 г.].. Мэдди цитирует две статьи Мириманова: «Антиномии Рассела и Бурали-Форти и фундаментальная проблема теории ансамблей» и «Примечания к теории ансамблей и антиномии Канториенны», обе в L'Enseignement Mathématique (1917). .
5. Эббингауз, с. 92.
6. Эббингауз, стр. 135-138.
7. Эббингауз, с. 189.
8. Эббингауз, с. 184.