14. Доопределение теорий. Теория множеств Цермело-Френкеля - сигнатура, аксиомы, вопрос непротиворечивости (Лекции)

Математическая логикаЛектор:Подымов Владислав Васильевичe-mail:valdus@yandex.ru2017, весенний семестрЛекция 14Доопределение теорийТеория множеств Цермело-Френкеля:сигнатура, аксиомы,вопрос непротиворечивостиВступление: итоги лекции 13Наивная теория множеств допускаетIнеправдоподобные умозаключения о бесконечныхмножествах, основанные на понятиях и способахрассуждений, “рациональных” для конечных множествIIэто “хорошие” парадоксы: если описать подходящийнабор понятий и способов рассуждения о множествах, тоони исчезнут сами собойбезусловные логические противоречияIэто “плохие” парадоксы: они не исчезают даже приналичии строгого базового аппарата работы с множествамиВступление: итоги лекции 13Чтобы уметь работать с множествами, не имея ни хороших, ниплохих парадоксов, достаточно предложить адекватнуюаксиоматическую теорию множествЕсли это получится, то можно будет попробовать1 дать такоеопределение множества:Множество — этопредмет любой модели аксиоматической теории множеств1Это слово здесь важно, но об этом разговор будет потомВступление: итоги лекции 13Какие возможности должна предоставлять теория множеств?Например, неплохо было бы уметьI проверять принадлежность элемента множеству:x ∈SI задавать множество перечислением его элементов:{x1 , .

. . , xk }I задавать множество свойством его элементов:{x | ϕ(x)}I применять теоретико-множественные операции:SX , X ∪ Y , X ∩ Y , X \ Y , 2X , . . .I сравнивать множества:X = Y, X ⊆ Y, X ⊂ YI сравнивать мощности множеств:|X | = |Y |, |X | < |Y |Сигнатура теории множествБудем пытаться описать теорию множествс как можно меньшей сигнатуройНачнём с включения символов ∈ и = в сигнатуруНа основе этих символов можно явно определить многиебазовые множества, отношения и операции:IIIIII∀x ∀y (x 6= y ↔ ¬x = y)∀x ∀y (x ∈/ y ↔ ¬x ∈ y)∀x ∀y (x ⊆ y ↔ ∀z (z ∈ x → z ∈ y))∀x ∀y (x ⊂ y ↔ (x ⊆ y & x 6= y))∀u (u ∈/ ∅)схема определений:∀exn ∀u (u ∈ {x1 , .

. . , xk } ↔ (u = x1 ∨ · · · ∨ u = xk ))Сигнатура теории множествБудем пытаться описать теорию множествс как можно меньшей сигнатуройНачнём с включения символов ∈ и = в сигнатуруНа основе этих символов можно явно определить многиебазовые множества, отношения и операции:IIIIIIсхема определений:∀exn ∀u (u ∈ {z | ϕ(z, exn )} ↔ ϕ {z/u})∀x ∀y (x ∪ y = {z | z ∈ x ∨ z ∈ y})∀x ∀y (x ∩ y = {z | z ∈ x & z ∈ y})∀x ∀y (x \ y = {z | z ∈ x & z ∈/ y})S∀x ( x = {z | ∃y (y ∈ x & z ∈ y)})∀x (2x = {z | z ⊆ x})Сигнатура теории множествА можно ли теперь сказать “добавим в теориювсе определённые символы и все определяющие аксиомы,исследуем непротиворечивость и полноту полученной теориии скажем, что результаты переносятся и на исходную теорию”?(Контр)пример: арифметика Пресбургера Tpaнепротиворечива и полна, и при этомI теория Tpa ∪ {∀x (Even(x) ↔ ∃y (x = y + y))} сигнатурыσpa+Even непротиворечива и полнаI теория Tpa ∪ {C = 0 & ¬C = 0} сигнатуры σpa+CпротиворечиваI теория Tpa ∪ {∃x (C = x + x)} сигнатуры σpa+C неполнаСигнатура теории множеств∃!x ϕ — это сокращение для формулы∃x ϕ & ∀x ∀x0 (ϕ & ϕ {x/x0 } → x = x0 )Теорема о непротиворечивости и полноте доопределения теорииПустьT — теория с равенством сигнатуры σA — аксиома, определяющая символ s в сигнатуре σ согласноопределению ϕI T 0 = T ∪ {A} — теория с равенством сигнатуры σ+sI верно одно из трёх:I s — предикатный символI s = c — константа, и |=T ∃!xc ϕI s = f (n) — функциональный символ, и |=xn ∃!xf ϕT ∀eIIТогда1.

все модели T могут быть получены из моделей T 0удалением оценки s, и2. теория T полна ⇔ теория T 0 полнаДоказательство. Попробуйте сами адаптировать доказательствотеоремы о разрешимости доопределения теорииСигнатура теории множествИтог: можно рассуждать о непротиворечивости и полнотетеории множеств, доопределяя еёI любыми предикатными символамиIIIв частности, можно использовать символы 6=, ∈,/ ⊆, ⊂любыми константами c, определяя их формулами ϕc ,такими что предложения ∃!xc ϕc — теоремы теориимножествлюбыми функциональными символами f (n) , определяя ихформулами ϕf , такими что предложения ∀exn ∃!xf ϕf —теоремы теории множествВ рассуждениях о теории множеств, в том числе при описанииаксиом, будут использоваться такие символыЧтобы получить “настоящие” аксиомы исходной сигнатуры,достаточно применить преобразования формулы, описанные вдоказательстве теоремы о разрешимости доопределения теорииСигнатура теории множествМожно начать определение теории множеств несколькимиспособами:1.

это теория с равенством сигнатуры ∅, ∅, ∈(2) h. . .i2. это теория сигнатуры ∅, ∅, ∈(2) , =(2) , содержащаяаксиомы равенства и h. . .i3. это теория сигнатуры ∅, ∅, ∈(2) , в которой предикатныйсимвол =(2) используется как сокращение формулы∀u (u ∈ x1 ↔ u ∈ x2 ) & ∀u (x1 ∈ u ↔ x2 ∈ u) h. . .i4+. .

. .Остановимся на первом способе: определим теорию множествкак теорию с равенством сигнатуры ∅, ∅, ∈(2)Аксиома объёмностиПрежде всего разберёмся с равенством множествЕстественное определение равенства множеств:множества равны ⇔ они состоят из одних и тех же элементовЕсли мы хотим придать символу =значение равенства множеств, то предложение∀x ∀y (x = y ↔ ∀u (u ∈ x ↔ u ∈ y))должно быть теоремой теории множествОчевидно, чтоI |= ∀x ∀y (x = y → ∀u (u ∈ x ↔ u ∈ y))I 6|= ∀x ∀y (∀u (u ∈ x ↔ u ∈ y) → x = y)Аксиома объёмности A= :∀x ∀y (∀u (u ∈ x ↔ u ∈ y) → x = y)Аксиомой объёмности гарантируется единственностьмножества, содержащего заданную совокупность элементовАксиома пустого множестваКонструктивный способ задания любого множестваобязательно начинается с ∅∅ — это предмет, удовлетворяющий отношению Empty(1) :∀x (Empty(x) ↔ ∀u ¬(u ∈ x))Но такой предмет не обязан существовать:A= 6|= ∃x Empty(x)Аксиома пустого множества A∅ :∃x Empty(x)Очевидно, чтоA= , A∅ |= ∃!x Empty(x)Итог: теперь можно доопределить теорию символом ∅ (так, какэто делалось в начале лекции)Аксиома парыИз аксиом A= и A∅ не следует существование/единственностькаких бы то ни было множеств, кроме ∅Добавим в теорию аксиомы, позволяющие доказыватьсуществование (и единственность) хоть каких-нибудь множеств,получаемых в результате применения теоретико-множественныхопераций к существующим множествамОпределим новый предикатный символ:∀x ∀y ∀z (Pair(x, y, z) ↔ ∀u (u ∈ z ↔ u = x ∨ u = y))Аксиома пары A2 :∀x ∀y ∃z Pair(x, y, z)И что это означает?Какие бы существующие множества x, y мы ни взяли,всегда существует множество z = {x, y}Аксиома парыТеперь можно доказать, что:I для любого множества x существует единственноемножество y = {x}:A= , A2 |= ∀y ∃!x ∀u (u ∈ x ↔ u = y)I для любых множеств x, y существует единственноемножество z = {x, y}:A= , A2 |= ∀x ∀y ∃!z ∀u (u ∈ z ↔ (u = x ∨ u = y))Итог: можно доопределить теорию символами операцийx → {x} и x, y → {x, y}Все множества, получаемые из ∅, {·} и {·, ·}, имеютмощность 0, 1 или 2А как показать существование более мощных множеств —например, мощностей 3, 4, .

. . ?Аксиома объединенияСамый простой способ получения более мощных множеств изменее мощных — это использование операции объединениямножеств, например:{0, 1} ∪ {2} = {∅, {∅}} ∪ {{∅, {∅}}} = {∅, {∅} , {∅, {∅}}} = 33 ∪ {3} = 4...Каждую пару множеств x, y можно объединить в множество{x, y}, а значит, операция объединенияпары множеств x ∪ y —Sчастное проявление операции SX:x ∪ y = {x, y}Введём такое отношение:∀x ∀y (BigUnion(x, y) ↔ ∀u (u ∈ x ↔ ∃v (v ∈ y & u ∈ v)))Аксиома объединения AS :∀y ∃x BigUnion(x, y)Аксиома объединенияТеперь можно доказать, что:I для любого множества x существует единственноеSобъединение y = x:A= , AS |= ∀x ∃!y ∀u (u ∈ y ↔ ∃v (v ∈ x & u ∈ v))I для любых множеств x, y существует единственноеобъединение z = x ∪ y:A= , A2 , AS |= ∀x ∀y ∃!z ∀u (u ∈ z ↔ (u ∈ x ∨ u ∈ y))I существует и единственно любое множество, состоящее иззаданного конечного числа существующихмножеств:S{x1 , .

. . , xn−1 , xn } = {{x1 , . . . , xn−1 } , {xn }}Итог:Sтеперь можно доопределить теорию символами операцийx → x, x, y → x ∪ y и exn → {exn }А откуда взять бесконечные множества?Аксиома бесконечностиСамое известное бесконечное множество — это множествонатуральных чисел (с нолём):N0 = {0, 1, 2, 3, . . .} = {∅, {∅} , {∅, {∅}} , {∅, {∅} , {∅, {∅}}} , . . .}Индуктивный способ задания множества N0 выглядит так:1. ∅ ∈ N02. если u ∈ N0 , то u ∪ {u} ∈ N0Введём отношение, основанное на этом способе задания:∀x (BigSet(x) ↔ (∅ ∈ x & ∀u (u ∈ x → u ∪ {u} ∈ x)))Аксиома бесконечности A∞ :∃x BigSet(x)Теперь в модели обязано существовать некоторое множество S,такое что N0 ⊆ SА как выделить подмножество N0 из множества S?Схема выделенияz — натуральное число в том и только в том случае, если:I если z 6= ∅, то z представимо в виде u ∪ {u}I если v ∈ z и v 6= ∅, то v представим в виде v = w ∪ {w}, гдеw∈zВведём отношение,описывающее натуральность z:(z = ∅ ∨ ∃u (z = u ∪ {u})) &∀z (N(z) ↔)∀v (v ∈ z → v = ∅ ∨ ∃w (w ∈ z & v = w ∪ {w}))Адекватно ли определено отношение N?Если в нашем распоряжении имеются только аксиомы A= , A∅ ,A2 , AS , то этим отношением допускается такое наивно заданноерекурсивное натуральное число:n∞ = n∞ ∪ {n∞ }Схема выделенияДалее будет описана аксиома A↓ , исключающая существованиетакого числа n∞Сейчас будем полагать, что при наличии этой аксиомы N —адекватное определение натуральности числаТогда множество натуральных чисел можно задать так:N0 = {z | z ∈ S & N(z)}Введём схему отношений, позволяющих выделять подмножествазаданного множества:∀exn ∀x ∀y (Subsetϕ(exn ,u,y) (exn , x, y) ↔ ∀u (u ∈ S ↔ (u ∈ y & ϕ)))Схема выделения A⊆ (ϕ(exn , u, y)):n∀ex ∀y ∃x Subsetϕ (exn , x, y)Схема выделенияТеперь можно доказать, что:I существует единственное множество натуральных чисел:A= , A∅ , A2 , AS , A∞ , A⊆ (N), A↓ |= ∃!x ∀z (z ∈ x ↔ N(z))I для любого множества y существует единственноеподмножество x всех его элементов u, удовлетворяющихсвойству ϕ(u, y):A= , A⊂ (ϕ) |= ∀y ∃!x ∀u (u ∈ x ↔ (u ∈ y & ϕ))Схема выделенияТеперь можно доказать, что:I для любых множеств x, y существует единственноепересечение z = x ∩ y:(ϕ∩ (x1 , u): u ∈ x1 )A= , A⊂ (ϕ∩ ) |= ∀x ∀y ∃!z ∀u (u ∈ z ↔ (u ∈ x & u ∈ y))I для любых множеств x, y существует единственнаяразность z = x \ y:(ϕ\ (x1 , u): u ∈/ x1 )A= , A⊂ (ϕ\ ) |= ∀x ∀y ∃!z ∀u (u ∈ z ↔ (u ∈ x & u ∈/ y))Итог: теперь можно доопределить теориюI множеством натуральных чисел N0I операцией x → {z | z ∈ x & ϕ}I операциями пересечения x, y → x ∪ y и разностиx, y → x \ y множествАксиома степениА существуют ли множества более чем счётной мощности?SОперация x позволяет увеличивать мощность, только еслиперед этим получено множество элементов, имеющихдостаточно большую мощностьSПока множество таких элементов не получено, операция xбеполезна для увеличения мощности“Естественный” способ получения таких элементов —применение операции степениВведём новое отношение, определяющее степень множества:∀x ∀y (Power(x, y) ↔ ∀u (u ∈ x ↔ u ⊆ y))Аксиома степени Ap :∀y ∃x Power(x, y)Очевидно, что A= , Ap |= ∀y ∃!x ∀u (u ∈ x ↔ u ⊆ y)Итог: теперь можно доопределить теорию операцией x → 2xСхема преобразованияА как доказать существование и единственность множестваS = {{0} , {0, 1} , {0, 2} , .