аксиоматика множеств Цермело - Френкеля

в аксиоматике множеств ZF всего один тип объектов - множества, всего одно отношение - ∈, всего одна константа - ∅. в нее входит девять естественных (и удивительно простых) аксиом. ее выразительная мощь чудовищно велика

аксиомы ZF

ZF1 (аксиома экстенсиональности)

два множества равны, если они содержат одни и те же элементы, т.е. для равных множеств x и y выполняется z ∈ x ⇐⇒ z ∈ y

ZF2 (аксиома существования)

уяснение разницы между вещью x и множеством {x}, единственным элементом которого является эта вещь, представляет серьезные психологические трудности для детей, народных масс и философов

существует пустое множество ∅. заметим, что согласно аксиоме ZF1 существует ровно одно пустое множество

по определению утверждение x ∈ ∅ ложно для любого x. поэтому утверждение x ∈ ∅ ⇒ P (x) или, что то же самое, ∀ x ∈ ∅, P (x) истинно для любого свойства P. таким образом, элемент пустого множества обладает любым свойством (а также - отрицанием этого свойства)

о том, что понятие пустого множества совершенно не очевидно, говорит хотя бы тот факт, что оно было введено лишь в конце XVII века Лейбницем под именем ‘non Ens’ (‘небытие’, ‘не сущее’). вся традиционная логика, следуя Аристотелю, признавала правило конверсии: “если всякое A есть B, то некоторое A есть B”, явным образом подразумевающее, что A непусто. на нашем языке это означает, что из A ⊆ B делается вывод, что A ∩ B ≠ ∅. например, из посылки “все кентавры лысы” Аристотель делает вывод “существует лысый кентавр”. может быть лысый кентавр действительно существует (это не противоречит известным физическим законам), но это никак не следует из посылки

именно на игре с этим правилом построено большинство так называемых ‘логических парадоксов’ (парадокс Рассела и его родственники). берется произвольный элемент пустого множества и выводится, что он обладает как свойством P, так и свойством ¬P, после чего все долго в недоумении смотрят на получившееся противоречие. однако в действительности противоречие получается только при дополнительном (абсурдном) предположении, что в пустом множестве есть хотя бы один элемент

"доказать, что все поезда RER на планете Марс - красно-синего цвета"

вот образец решения:

обозначим через X_n(Y) множество всех поездов системы Y на планете номер n (считая от Солнца)
согласно таблице, опубликованной CNRS там-то и тогда-то, планета Марс имеет в Солнечной системе номер 4
множество X₄(RER) пусто. согласно теореме 999-в из курса анализа все элементы пустого множества обладают всеми наперед заданными свойствами
следовательно, все поезда RER на планете Марс - красно-синего цвета. QED

В.Арнольд

пусть n - такое целое число, которое одновременно больше и меньше нуля. тогда n в том и только том случае является положительным, когда оно является отрицательным

но ведь такого числа не существует! вот именно. все “логические парадоксы” построены по следующей схеме:

предположим, что существует некоторый обьект X
тогда этот обьект X одновременно обладает и не обладает некоторым свойством

но это в точности и значит, что требуемого обьекта X не существует - именно так устроены доказательства от противного!

ZF3 (аксиома неупорядоченных пар)

для любых двух обьектов x и y существует множество {x,y}, единственными элементами которого являются x и y

в случае, когда x ≠ y множество {x,y}, существование которого утверждается в этой аксиоме, называется неупорядоченной парой с элементами x и y или просто парой. такая пара называется неупорядоченной, потому что, согласно аксиоме ZF1 пара {y,x} равна паре {x,y}

в случае же, когда x = y, в силу той же аксиомы {x,x} = {x}, так что из ZF3 вытекает, что для любого объекта x существует одноэлементное множество {x}, называемое "синглетоном"

заметим, что ни для одного обьекта x одноэлементное множество {x} не может совпадать с x

ZF4 (аксиома объединения)

для любого множества множеств x существует их объединение ∪

просто потому, что из аксиом ZF3 и ZF4 вытекает, что любая конечная совокупность обьектов образует множество

ZF5 (аксиома бесконечности)

существует такое множество ω, что: ∅ ∈ ω, ∀ x ∈ ω ∃ {x,{x}} ∈ ω

эта аксиома - существование актуально бесконечных множеств - есть ‘альфа’ (но еще не ‘омега’, вопреки обозначению) канторовской теории множеств

в окружающей нас действительности нет, повидимому, ничего бесконечного: концепция актуальной бесконечности представляет собой творение человеческого разума - причем совершенно не очевидное. вот что пишет по этому поводу известный критик канторовской математики Петр Вопенка:

в настоящее время существование актуально бесконечных множеств превратилось в догму, в которую верит большинство математиков; более того, математики пытаются внушить веру в эту догму и другим людям. в то же время мы не можем указать какое-либо актуально бесконечное множество в реальном мире - здесь мы имеем дело с конструкцией, расширяющей реальный мир и качественно превосходящей пределы наших наблюдений

видимо, большинство профессиональных математиков согласится с фактической стороной этого замечания, но они видят в этом силу математики, которая как раз и заключается в том, что она использует придуманные ей конструкции, использующие бесконечность, чтобы с их помощью решать вопросы, по самой своей сути относящиеся к конечному

ZF6 (аксиома подстановки)

допустим, что ∀ x ∃! y : y = F(x). тогда для любого множества z существует единственное множество u, состоящее из всех y таких, что x ∈ z , y = F(x)

эта аксиома была введена Абрахамом Френкелем. с содержательной точки зрения ее смысл состоит в том, что образ функции на множестве является множеством

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

ZF7 (аксиома степени)

для любого множества x существует множество z такое, что y ∈ z в том и только том случае, когда y ⊆ x

множество z существование которого утверждается этой аксиомой, обычно обозначается 2^x и называется "булеаном x". по определению, y ∈ 2^x ⇐⇒ y ⊆ x

ZF8 (аксиома выбора)

пусть f : X → Y - сюръективное отображение. тогда существует отображение g : Y → X такое, что для любого y ∈ Y имеет место равенство y = f(g(y))

Coq listing

(* Coq.Init.Specif *)

bool_choice : forall (S : Set) (R1 R2 : S → Prop),
  (forall x : S, {R1 x} + {R2 x}) ->
  {f : S → bool | forall x : S, f x = true /\ R1 x \/ f x = false /\ R2 x}


dependent_choice : forall (X : Set) (R : X → X → Prop),
  (forall x : X, {y : X | R x y}) ->
  forall x0 : X, {f : nat → X | f 0 = x0 /\ (forall n : nat, R (f n) (f (S n)))}

end of listing

ZF9 (аксиома регулярности)

пусть y ≠ ∅. тогда существует такой элемент x ∈ y, что для любого элемента z ∈ y выполняется z ∉ x

аксиома регулярности запрещает существование множеств x таких, что x ∈ x. в самом деле, эта аксиома явным образом запрещает принадлежность x ∈ x, так как иначе в множестве {x} не было бы элемента, который не содержит ни одного элемента этого множества

кроме того, ZF9 запрещает одновременное выполнение включений x ∈ y ∈ x

точно так же, не существует трех обьектов x, y и z, для которых x ∈ y ∈ z ∈ x и т.д