Аксиоматическая схема замены

Понятие в теории множеств

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

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

Заявление

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

Предположим, что есть определяемое бинарное отношение (которое может быть собственным классом ), такое, что для каждого наборасуществует уникальный набор,такой чтовыполняется. Существует соответствующая определяемая функция, где тогда и только тогда, когда . Рассмотрим (возможно собственный) класс, определенный таким образом, что для каждого набора,тогда и только тогда, когда существуетс.называется образомподи обозначаетсяили (используя нотацию конструктора наборов ). ${\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}}}$

Таким образом, всякий раз, когда указывается уникальное соответствие -to- , подобное функции на , то все, что достигнуто таким образом, может быть собрано в набор , подобное . ${\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)}$
• В свете вышесказанного существование назначения ординала каждому вполне упорядоченному множеству также требует замены. Аналогично кардинальное назначение фон Неймана , которое назначает кардинальное число каждому множеству, требует замены, а также аксиомы выбора .
• Для наборов кортежей, рекурсивно определенных как и для больших , набор имеет слишком высокий ранг, чтобы его существование можно было доказать с помощью теории множеств только с помощью аксиомы мощности множества, выбора и без замены. ${\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 }}$

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

Упрощения

Некоторые упрощения могут быть сделаны в схеме аксиом замены для получения различных эквивалентных версий. Азриэль Леви показал, что версия замены с удаленными параметрами, т.е. следующая схема, эквивалентна исходной форме. В частности, эквивалентность сохраняется при наличии аксиом экстенсиональности, спаривания, объединения и powerset. ^[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}$

Доказательство выглядит следующим образом: либо содержит некоторый элемент , проверяющий , либо нет. В последнем случае взятие пустого множества для соответствует соответствующему экземпляру схемы аксиом разделения, и одно выполнено. В противном случае выберите такой фиксированный в , который проверяет . Теперь определим для использования с заменой. Используя функциональную нотацию для этого предиката , он действует как тождество везде, где истинно, и как постоянная функция везде, где ложно. По анализу случая возможные значения уникальны для любого , то есть действительно составляют функцию класса. В свою очередь, изображение под , то есть класс , предоставляется как множество аксиомой замены. Это точно подтверждает аксиому разделения. ${\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 })}$

История

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

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

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

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

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

Торальф Скулем обнародовал свое открытие пробела в системе Цермело (того самого пробела, который обнаружил Френкель) в докладе, который он сделал 6 июля 1922 года на 5-м Конгрессе скандинавских математиков, который состоялся в Хельсинки ; труды этого конгресса были опубликованы в 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. Maddy, Penelope (1988), «Вера в аксиомы. I», Journal of Symbolic Logic , 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.