Схема аксиомы замены - Axiom schema of replacement

В теория множеств, то схема аксиомы замены это схема из аксиомы в Теория множеств Цермело – Френкеля (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}}}$

Так что всякий раз, когда ${\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, ...}. Однако произвольные такие классы порядковых номеров не обязательно быть наборами - например, класс всех порядковых номеров не является набором. Замена теперь позволяет заменять каждое конечное число п в ω с соответствующим ω + п, и тем самым гарантирует, что этот класс является набором. В качестве пояснения отметим, что можно легко построить упорядоченный набор который изоморфен ω · 2, не прибегая к замене - просто возьмем несвязный союз двух копий ω, причем вторая копия больше первой, но это не порядковый номер, поскольку он не полностью упорядочен включением.
• Более крупные ординалы менее напрямую зависят от замены. Например, ω₁, то первый несчетный порядковый номер, можно построить следующим образом - множество счетных порядков скважин существует как подмножество ${\displaystyle P({\mathbb {N} }\times {\mathbb {N} })}$ от разделение и powerset (а связь на А это подмножество ${\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. В количественное числительное ${\displaystyle \aleph _{\omega }}$ является первым, которое, как можно показать, существует в ZF, но не в Z. Для пояснения обратите внимание, что Вторая теорема Гёделя о неполноте показывает, что каждая из этих теорий содержит предложение, «выражающее» собственную непротиворечивость теории, которая недоказуема в этой теории, если эта теория непротиворечива - этот результат часто свободно выражается как утверждение, что ни одна из этих теорий не может доказать свою собственную непротиворечивость , если он согласован.

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

Коллекция

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

В схема аксиомы коллекции тесно связана со схемой аксиомы замены и часто ее путают. По остальным аксиомам ZF это эквивалентно схеме аксиом замены. Аксиома сбора сильнее замены при отсутствии аксиома набора мощности или его конструктивный аналог 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 (C)}$ это не упоминает ${\displaystyle B}$, и набор ${\displaystyle A}$. Если нет элемента ${\displaystyle E}$ из ${\displaystyle A}$ удовлетворяет ${\displaystyle \theta (E)}$ тогда набор ${\displaystyle B}$ желательным для соответствующего примера схемы аксиомы разделения является пустое множество. В противном случае выберите фиксированный ${\displaystyle E}$ в ${\displaystyle A}$ такой, что ${\displaystyle \theta (E)}$ держит. Определите функцию класса ${\displaystyle F}$ так что для любого элемента ${\displaystyle D}$, ${\displaystyle F(D)=D}$ если ${\displaystyle \theta (D)}$ держит и ${\displaystyle F(D)=E}$ если ${\displaystyle \theta (D)}$ ложно. Тогда образ ${\displaystyle A}$ под ${\displaystyle F}$, т.е. множество ${\displaystyle B=F''A:=\{F(x):x\in A\}=A\cap \{x:\theta (x)\}}$, существует (по аксиоме замены) и является в точности множеством ${\displaystyle B}$ требуется для аксиомы разделения.

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

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

В приведенном выше доказательстве используется закон исключенного среднего в предположении, что если ${\displaystyle A}$ непусто, то оно должно содержать элемент (в интуиционистской логике набор является «пустым», если он не содержит элемента, а «непустой» - это формальное отрицание этого, которое слабее, чем «действительно содержит элемент»). Аксиома разделения включена в интуиционистская теория множеств.

История

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

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

Торльф Сколем, 1930-е гг.

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

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

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

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

использованная литература

1. Мэдди, Пенелопа (1988), «Вера в аксиомы. Я», Журнал символической логики, 53 (2): 481–511, Дои:10.2307/2274520, JSTOR  2274520, Г-Н  0947855, Ранние намеки на Аксиому Замещения можно найти в письме Кантора Дедекинду [1899] и у Мириманова [1917]. Мэдди цитирует две статьи Мириманофф: «Антиномии Рассела и Бурали-Форти и фундаментальные проблемы теории ансамблей» и «Ремарки по теории ансамблей и канторианских антиномий», обе в L'Enseignement Mathématique (1917).
2. Эббингаус, стр. 92.
3. Эббингауз, стр. 135-138.
4. Эббингаус, стр. 189.
5. Эббингаус, стр. 184.

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