Аксиома замены в теории множеств

Введение

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

В теории множеств схема аксиом замены – это схема аксиом в теории множеств Цермело — Френкеля (ZF), утверждающая, что образ любого множества при любом определяемом отображении также является множеством. Она необходима для построения определенных бесконечных множеств в ZF. Схема аксиом обосновывается идеей о том, что принадлежность класса к множествам зависит только от мощности класса, а не от ранга его элементов. Таким образом, если один класс "достаточно мал", чтобы быть множеством, и существует сюръекция из этого класса на другой класс, то аксиома утверждает, что второй класс также является множеством. Однако, поскольку ZFC оперирует только множествами, а не собственными классами, схема формулируется только для определяемых сюръекций, которые отождествляются с определяющими их формулами.

Приложения

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

Используя современное определение, предложенное фон Нейманом, для доказательства существования любого предельного ординала, большего, чем ω, требуется аксиома замещения. Ординальное число ω·2 = ω + ω является первым таким ординалом. Аксиома бесконечности утверждает существование бесконечного множества ω = {0, 1, 2, ...}. Можно попытаться определить ω·2 как объединение последовательности {ω, ω + 1, ω + 2, ...}. Однако произвольные классы ординалов не обязаны быть множествами – например, класс всех ординалов не является множеством. Аксиома замещения позволяет заменить каждое конечное число n в ω на соответствующее ω + n, тем самым гарантируя, что этот класс является множеством. Для уточнения отметим, что можно легко построить хорошо упорядоченное множество, изоморфное ω·2, без использования аксиомы замещения – достаточно взять непересекающееся объединение двух копий ω, где вторая копия больше первой, – но это не будет ординалом, поскольку оно не полностью упорядочено по включению. Более крупные ординалы зависят от аксиомы замещения менее прямо. Например, ω1, первый несчётный ординал, можно построить следующим образом: множество счётных хорошо упорядоченных множеств существует как подмножество посредством аксиомы выделения и аксиомы степени (отношение на A является подмножеством , и, следовательно, является элементом множества степеней A; множество отношений, таким образом, является подмножеством ). Замените каждое хорошо упорядоченное множество на его ординальное число. Это множество счётных ординалов ω1, которое само по себе может быть показано несчётным. В этой конструкции аксиома замещения используется дважды: один раз для обеспечения ординального соответствия каждому хорошо упорядоченному множеству и второй раз для замены хорошо упорядоченных множеств их ординальными числами. Это частный случай результата Хартогса о числе, и общий случай может быть доказан аналогичным образом. В свете вышесказанного, существование соответствия между каждым хорошо упорядоченным множеством и его ординальным числом также требует аксиомы замещения. Аналогично, кардинальное соответствие фон Неймана, которое присваивает кардинальное число каждому множеству, требует аксиомы замещения, а также аксиомы выбора. Для множеств кортежей, рекурсивно определенных как и для больших , множество имеет слишком высокий ранг, чтобы его существование можно было доказать из теории множеств, используя только аксиому степени, аксиому выбора и без аксиомы замещения. Кроме того, Харви Фридман показал, что аксиома замещения необходима для доказательства детерминированности игр Бореля. Доказанным результатом является теорема о детерминированности Бореля Дональда А. Мартина. ZF с аксиомой замещения доказывает непротиворечивость Z, поскольку множество Vω·2 является моделью Z, существование которой можно доказать в ZF. Кардинальное число является первым, существование которого можно доказать в ZF, но не в Z. Для уточнения отметим, что вторая теорема о неполноте Гёделя показывает, что каждая из этих теорий содержит предложение, "выражающее" собственную непротиворечивость, которое недоказуемо в этой теории, если эта теория непротиворечива; этот результат часто неточно формулируется как утверждение о том, что ни одна из этих теорий не может доказать свою собственную непротиворечивость, если она непротиворечива.

Using the modern definition due to von Neumann, proving the existence of any limit ordinal greater than ω requires the replacement axiom. The ordinal number ω·2 = ω + ω is the first such ordinal. The axiom of infinity asserts the existence of an infinite set ω = {0, 1, 2, }. One may hope to define ω·2 as the union of the sequence {ω, ω + 1, ω + 2, }. However, arbitrary such classes of ordinals need not be sets for example, the class of all ordinals is not a set. Replacement now allows one to replace each finite number n in ω with the corresponding ω + n, and thus guarantees that this class is a set. As a clarification, note that one can easily construct a well ordered set that is isomorphic to ω·2 without resorting to replacement – simply take the disjoint union of two copies of ω, with the second copy greater than the first – but that this is not an ordinal since it is not totally ordered by inclusion. Larger ordinals rely on replacement less directly. For example, ω1, the first uncountable ordinal, can be constructed as follows – the set of countable well orders exists as a subset of by separation and powerset (a relation on A is a subset of , and so an element of the power set A set of relations is thus a subset of )). Replace each well ordered set with its ordinal. This is the set of countable ordinals ω1, which can itself be shown to be uncountable. The construction uses replacement twice; once to ensure an ordinal assignment for each well ordered set and again to replace well ordered sets by their ordinals. This is a special case of the result of Hartogs number, and the general case can be proved similarly. In light of the above, the existence of an assignment of an ordinal to every well ordered set requires replacement as well. Similarly the von Neumann cardinal assignment which assigns a cardinal number to each set requires replacement, as well as axiom of choice. For sets of tuples recursively defined as and for large , the set has too high of a rank for its existence to be provable from set theory with just the axiom of power set, choice and without replacement. Similarly, Harvey Friedman showed that replacement is required to show that Borel games are determined. The proven result is Donald A. Martin's Borel determinacy theorem. ZF with replacement proves the consistency of Z, as the set Vω·2 is a model of Z whose existence can be proved in ZF. The cardinal number is the first one which can be shown to exist in ZF but not in Z. For clarification, note that Gödel's second incompleteness theorem shows that each of these theories contains a sentence, "expressing" the theory's own consistency, that is unprovable in that theory, if that theory is consistent this result is often loosely expressed as the claim that neither of these theories can prove its own consistency, if it is consistent.

Упрощения

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

Разделение

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

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

Доказательство следующее: либо содержит некоторый элемент, удовлетворяющий , либо не содержит. В последнем случае, принятие пустого множества за удовлетворяет соответствующему экземпляру аксиомы схемы разделения, и задача решена. В противном случае, выберем такое фиксированное в , которое удовлетворяет . Теперь определим для использования с заменой. Используя функциональную нотацию для этого предиката, он действует как тождественное отображение везде, где истинно, и как постоянная функция везде, где ложно. В силу анализа случаев, возможные значения уникальны для любого , что означает, что действительно является классовой функцией. В свою очередь, образ при отображении , то есть класс , считается множеством по аксиоме замены. Это точно подтверждает аксиому разделения. Этот результат показывает, что можно аксиоматизировать ZFC с помощью единственной бесконечной аксиоматической схемы. Поскольку требуется по крайней мере одна такая бесконечная схема (ZFC не является конечно аксиоматизируемой), это показывает, что аксиоматическая схема замены может служить единственной бесконечной аксиоматической схемой в ZFC, если это необходимо. Поскольку аксиома схемы разделения не является независимой, она иногда опускается в современных формулировках аксиом Цермело — Френкеля. Однако разделение по-прежнему важно для использования во фрагментах ZFC, в силу исторических соображений и для сравнения с альтернативными аксиоматизациями теории множеств. Формулировка теории множеств, которая не включает аксиому замены, вероятно, будет включать в себя некоторую форму аксиомы разделения, чтобы гарантировать, что ее модели содержат достаточно богатую коллекцию множеств. При изучении моделей теории множеств иногда полезно рассматривать модели ZFC без замены, такие как модели в иерархии фон Неймана. Приведенное выше доказательство предполагает закон исключённого третьего для утверждения о том, что содержит множество, удовлетворяющее , и для любого при условии, что отношение является функциональным. Аксиома разделения явно включена в конструктивную теорию множеств или ее ограниченный вариант.

Отражение

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

Для любого множества и любой формулы первого порядка существует множество такое, что
Это схема, состоящая из счетного числа утверждений, по одному для каждой формулы . Здесь означает с ограничением всех кванторов областью , то есть , но с каждой вхождением и замененной на и соответственно.

История

Схема аксиом замещения не входила в аксиоматизацию теории множеств, предложенную Эрнстом Зермело в 1908 году (Z). Некоторые неформальные приближения к ней встречаются в неопубликованных работах Кантора и вновь появляются в работах Мириманова (1917). Публикация Авраамом Френкелем в 1922 году положила начало современной теории множеств, известной как теория множеств Цермело — Френкеля (ZFC). Аксиома была независимо открыта и объявлена Торальфом Сколемом позднее в том же году (и опубликована в 1923 году). Сам Зермело включил аксиому Френкеля в пересмотренную систему, опубликованную им в 1930 году, которая также содержала новую аксиому фон Неймана о фундаменте. Хотя сегодня мы используем версию аксиоматического списка Сколема в форме первого порядка,

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