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

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

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

Заявление

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

Предположим , существует определимое бинарное отношение (которое может быть собственным классом ) такое, что для каждого набора существует уникальный набор , который выполняется. Имеется соответствующая определимая функция , где тогда и только тогда, когда . Рассмотрим (возможно, правильный) класс, определенный таким образом, что для каждого набора , если и только если существует with . называется изображением под и обозначается или (с использованием нотации конструктора множеств ) . ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ Displaystyle Р (х, у)}$${\ displaystyle F_ {P}}$${\ Displaystyle F_ {P} (х) = у}$ ${\ Displaystyle Р (х, у)}$${\ displaystyle B}$${\ displaystyle y}$${\ displaystyle y \ in B}$${\ displaystyle x \ in A}$${\ Displaystyle F_ {P} (х) = у}$${\ 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 {align} \ 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 {выровнено}}}$

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

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

${\ Displaystyle {\ begin {align} \ forall A \, ([\ forall x \ in A & \, \ exists! y \, \ phi (x, y, A)] \ \ Longrightarrow \ \ exists B \, \ forall y \, [y \ in B \ Leftrightarrow \ существует x \ in A \, \ phi (x, y, A)]) \ end {выравнивается}}}$

Таким образом , всякий раз , когда задает уникальный -До- корреспонденция, сродни функции на , то все достигается таким образом , может быть собрана в набор , сродни . ${\ 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 А \ раз А}$ ${\ Displaystyle Р (А \ раз А)}$${\ Displaystyle Р (А \ раз А)}$
• В свете вышесказанного, наличие присвоения порядкового номера каждому хорошо упорядоченному набору также требует замены. Точно так же кардинальное присвоение фон Неймана, которое присваивает количественное число каждому набору, требует замены, а также аксиомы выбора .
• Для наборов кортежей, рекурсивно определенных как и для больших , набор имеет слишком высокий ранг, чтобы его существование можно было доказать с помощью теории множеств с помощью только аксиомы набора мощности, выбора и без замены.${\ Displaystyle А ^ {п} = А ^ {п-1} \ раз А}$${\ displaystyle A}$${\ displaystyle \ {A ^ {n} \ mid n \ in {\ mathbb {N}} \}}$
• Точно так же, Харви Фридман показал , что замена требуется , чтобы показать , что борелевские будут определены . Проверенный результат Donald A. Martin «s Борель детерминированность теорема .
• ZF с заменой доказывает непротиворечивость Z, так как множество V _{ω · 2} является моделью Z, существование которой можно доказать в ZF. Кардинальное число является первым из которых может быть доказано существование в ZF , но не в Z. Для разъяснения, отметим , что вторая теорема Гёделя о неполноте показывает , что каждая из этих теорий содержит предложение « выражающее» собственную непротиворечивость теории, то есть недоказуемо в этой теории, если эта теория непротиворечива - этот результат часто свободно выражается как утверждение, что ни одна из этих теорий не может доказать свою непротиворечивость, если она непротиворечива.${\ displaystyle \ aleph _ {\ omega}}$

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

Коллекция

Схема аксиомы коллекции: изображение области, установленной под определяемой функцией класса, попадает внутрь набора .${\ 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 \ существует 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 \, \ существует B \, \ forall C \, (C \ in B \ Leftrightarrow [C \ in A \ land \ theta (C)])}$

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

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

История

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

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

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

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

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

Торльф Сколем обнародовал свое открытие пробела в системе Цермело (тот же пробел, который обнаружил Френкель) в своем выступлении 6 июля 1922 года на 5-м Конгрессе скандинавских математиков , который проходил в Хельсинки ; протоколы этого конгресса были опубликованы в 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.
• Jech, Томас (2003), Теория множеств: издание третьего тысячелетия, пересмотренное и расширенное , Springer, ISBN 3-540-44085-2.
• Кунен, Кеннет (1980), Теория множеств: Введение в доказательства независимости , Elsevier, ISBN 0-444-86839-9.