Теория множеств Крипке – Платека - Kripke–Platek set theory

Теория множеств Крипке-Платек ( КП ), выраженный / к R ɪ р к я р л ɑː т ɛ к / , является аксиомой теории множеств , разработанная Сол Крипке и Ричард Платек.

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

Аксиомы КП

• Аксиома протяженности : два набора одинаковы тогда и только тогда, когда они имеют одинаковые элементы.
• Аксиома индукции : φ ( a ) является формулой , если для всех множеств x предположение, что φ ( y ) выполняется для всех элементов y из x, влечет выполнение φ ( x ), то φ ( x ) выполняется для всех множеств x .
• Аксиома пустого множества : существует множество без членов, называемое пустым множеством и обозначаемое {}. (Примечание: существование члена во вселенной дискурса, то есть ∃x (x = x), подразумевается в некоторых формулировках логики первого порядка , и в этом случае аксиома пустого множества следует из аксиомы Σ ₀ -разделение и, следовательно, является избыточным.)
• Аксиома спаривания : если x , y являются наборами, то также и { x , y }, набор, содержащий x и y как свои единственные элементы.
• Аксиома объединения : для любого множества x существует такое множество y , что элементы y являются в точности элементами элементов x .
• Аксиома Σ ₀ -разделения : Для любого множества и любой Σ ₀ -формулы φ ( x ) существует подмножество исходного набора, содержащее в точности те элементы x, для которых выполняется φ ( x ). (Это схема аксиомы .)
• Аксиома Σ ₀ -коллекции : для любой Σ ₀ -формулы φ ( x , y ), если для каждого множества x существует единственное множество y такое, что φ ( x , y ) выполняется, то для всех множеств u существует множество v такое, что для каждого x в u существует y в v , для которого выполняется φ ( x , y ).

Здесь Σ ₀ , или Π ₀ , или Δ ₀ формула - это формула, все кванторы которой ограничены . Это означает, что любое количественное определение - это форма или (В более общем плане мы бы сказали, что формула - это Σ _{n +1,} когда она получена путем добавления кванторов существования перед формулой Π _n , и что она равна _{n +1,} когда это полученный путем добавления универсальных кванторов перед формулой Σ _n : это связано с арифметической иерархией, но в контексте теории множеств.) ${\ displaystyle \ forall u \ in v}$${\ Displaystyle \ существует и \ в v.}$

• Некоторые, но не все авторы включают аксиому бесконечности (в этом случае аксиома пустого множества не нужна, поскольку ее существование можно доказать с помощью разделения).

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

Аксиома индукции в контексте КП сильнее обычной аксиомы регулярности , которая сводится к применению индукции к дополнению набора (классу всех множеств не в данном наборе). Не принимая Регулярность или Аксиому выбора , КП можно изучать как конструктивную теорию множеств , отбросив закон исключенного середины без изменения каких-либо аксиом.

Доказательство существования декартовых произведений

Теорема:

Если и B являются множествами, то существует множество × B , который состоит из всех упорядоченных пар ( , б ) элементов через из A и B из B .

Доказательство:

Набор { a } (который по аксиоме экстенсиональности совпадает с { a , a }) и набор { a , b } существуют по аксиоме спаривания. Таким образом

${\ Displaystyle (а, Ь): = \ {\ {а \}, \ {а, Ь \} \}}$

существует и по аксиоме спаривания.

Возможная Δ ₀ формула, выражающая то, что p означает ( a , b ), такова:

${\ Displaystyle \ существует р \ в п \, (а \ в г \, \ земля \, \ для всех х \ в г \, (х = а)) \, \ земля \, \ существует s \ в р \, (a \ in s \, \ land \, b \ in s \, \ land \, \ forall x \ in s \, (x = a \, \ lor \, x = b)) \, \ land \, }$

${\ displaystyle \ forall t \ in p \, ((a \ in t \, \ land \, \ forall x \ in t \, (x = a)) \, \ lor \, (a \ in t \ land b \ in t \ land \ forall x \ in t \, (x = a \, \ lor \, x = b))).}$

Таким образом, надмножество A × { b } = {( a , b ) | a в A } существует по аксиоме коллекции.

Обозначим формулу для p выше . Тогда следующая формула также Δ ₀${\ displaystyle \ psi (a, b, p)}$

${\ Displaystyle \ существует a \ в A \, \ psi (a, b, p) \ ,.}$

Таким образом, само A × { b } существует по аксиоме отделимости.

Если v означает A × { b }, тогда формула Δ _0, выражающая это:

${\ Displaystyle \ forall a \ in A \, \ существует p \ in v \, \ psi (a, b, p) \, \ land \, \ forall p \ in v \, \ существует a \ in A \, \ psi (a, b, p) \ ,.}$

Таким образом, надмножество { A × { b } | b в B } существует по аксиоме набора.

Подставляя перед последней формулой, мы получаем из аксиомы разделения, что множество { A × { b } | b в B } существует сам по себе. ${\ displaystyle \ существует b \ in B}$

Наконец, A × B = { A × { b } | b в B } существует по аксиоме объединения. ${\ Displaystyle \ чашка}$

QED

Допустимые множества

Множество называется допустимым, если оно транзитивно и является моделью теории множеств Крипке – Платека. ${\ Displaystyle А \,}$${\ displaystyle \ langle A, \ in \ rangle}$

Порядковое число α называется допустимым порядковый номер, если L _α является допустимым множеством.

Ординал α является допустимым ординалом тогда и только тогда, когда α является предельным ординалом и не существует γ  <  α, для которого существует Σ ₁ (L _α ) отображение из γ на α . Если M - стандартная модель КП, то множество ординалов в M - допустимый ординал.

Если L _α - стандартная модель теории множеств КП без аксиомы Σ ₀ -коллекции, то она называется « аменабельным множеством ».

Смотрите также

• Конструируемая вселенная
• Допустимый порядковый номер
• Теория множеств Крипке – Платека с элементарными элементами.

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

Библиография

• Девлин, Кейт Дж. (1984). Конструктивность . Берлин: Springer-Verlag . ISBN 0-387-13258-9.
• Гостанян, Ричард (1980). «Конструируемые модели подсистем ZF». Журнал символической логики . Ассоциация символической логики . 45 (2): 237. DOI : 10,2307 / 2273185 . JSTOR  2273185 .
• Крипка, S. (1964), "Трансфинитные рекурсии на допустимом порядковом", журнал символической логики , 29 : 161-162, DOI : 10,2307 / 2271646 , JSTOR  2271646
• Платек, Ричард Алан (1966), Основы теории рекурсии , Диссертация (докторская) - Стэнфордский университет , MR  2615453