Иерархия Леви - Lévy hierarchy

В теория множеств и математическая логика, то Иерархия Леви, представлен Азриэль Леви в 1965 г. представляет собой иерархию формул в формальный язык из Теория множеств Цермело – Френкеля, который обычно называют просто языком теории множеств. Это аналогично арифметическая иерархия который обеспечивает классификации, но для предложений языка арифметики.

Определения

На языке теории множеств атомарные формулы имеют вид x = y или x ∈ y, что означает равенство и соответственно установить членство предикаты.

Первый уровень иерархии Леви определяется как содержащий только формулы без неограниченных кванторов и обозначается ${\displaystyle \Delta _{0}=\Sigma _{0}=\Pi _{0}}$.^[1] Следующие уровни задаются путем нахождения эквивалентной формулы в Prenex нормальная форма, и подсчитывая количество изменений кванторы:

В теории ZFC формула ${\displaystyle A}$ называется:^[1]

${\displaystyle \Sigma _{i+1}}$ если ${\displaystyle A}$ эквивалентно ${\displaystyle \exists x_{1}...\exists x_{n}B}$ в ZFC, где ${\displaystyle B}$ является ${\displaystyle \Pi _{i}}$

${\displaystyle \Pi _{i+1}}$ если ${\displaystyle A}$ эквивалентно ${\displaystyle \forall x_{1}...\forall x_{n}B}$ в ZFC, где ${\displaystyle B}$ является ${\displaystyle \Sigma _{i}}$

Если формула совпадает с ${\displaystyle \Sigma _{i}}$ и ${\displaystyle \Pi _{i}}$, это называется ${\displaystyle \Delta _{i}}$. Поскольку формула может иметь несколько разных эквивалентных формул в нормальной форме Prenex, она может принадлежать к нескольким различным уровням иерархии. В этом случае самый низкий возможный уровень - это уровень формулы.

Иерархия Леви иногда определяется для других теорий. S. В этом случае ${\displaystyle \Sigma _{i}}$ и ${\displaystyle \Pi _{i}}$ сами по себе относятся только к формулам, которые начинаются с последовательности кванторов с не более чем я−1 чередование и ${\displaystyle \Sigma _{i}^{S}}$ и ${\displaystyle \Pi _{i}^{S}}$ относятся к формулам, эквивалентным ${\displaystyle \Sigma _{i}}$ и ${\displaystyle \Pi _{i}}$ формулы в теории S. Строго говоря, уровни ${\displaystyle \Sigma _{i}}$ и ${\displaystyle \Pi _{i}}$ иерархии Леви для ZFC, определенной выше, следует обозначать ${\displaystyle \Sigma _{i}^{ZFC}}$ и ${\displaystyle \Pi _{i}^{ZFC}}$.

Примеры

Σ₀= Π₀= Δ₀ формулы и концепции

• х = {у, z}
• х ⊆ у
• Икс это переходный набор
• Икс является порядковый, Икс предельный порядковый номер, Икс порядковый номер преемника
• Икс конечный ординал
• Первый счетный ординал ω.
• ж это функция. Диапазон и домен функции. Значение функции в наборе.
• Изделие из двух наборов.
• Объединение набора.

Δ₁-формулы и концепции

• Икс это обоснованные отношения на у
• Икс конечно
• Порядковое сложение, умножение и возведение в степень
• Ранг набора
• Транзитивное замыкание множества

Σ₁-формулы и концепции

• Икс является счетный
• |Икс|≤|Y|, |Икс|=|Y|
• Икс конструктивно

Π₁-формулы и концепции

• Икс это кардинал
• Икс это обычный кардинал
• Икс это предельный кардинал
• Икс является недоступный кардинал.
• Икс это powerset из у

Δ₂-формулы и концепции

• κ является γ-сверхкомпактным

Σ₂-формулы и концепции

• то Гипотеза континуума
• существует недоступный кардинал
• существует измеримый кардинал
• κ - это п-огромный кардинал

Π₂-формулы и концепции

• В аксиома конструктивности: V = L

Δ₃-формулы и концепции

Σ₃-формулы и концепции

• Существует сверхкомпактный кардинал

Π₃-формулы и концепции

• κ - это расширяемый кардинал

Σ₄-формулы и концепции

• Существует расширяемый кардинал

Характеристики

Jech p. 184Девлин с. 29

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

• арифметическая иерархия
• Абсолютность

Рекомендации

1. Валицки, Михал (2012). Математическая логика, п. 225. World Scientific Publishing Co. Pte. ООО ISBN  9789814343862

• Девлин, Кейт Дж. (1984). Конструктивность. Перспективы математической логики. Берлин: Springer-Verlag. стр.27 –30. Zbl  0542.03029.
• Jech, Thomas (2003). Теория множеств. Монографии Спрингера по математике (изд. Третьего тысячелетия). Берлин, Нью-Йорк: Springer-Verlag. п. 183. ISBN  978-3-540-44085-7. Zbl  1007.03002.
• Канамори, Акихиро (2006). «Леви и теория множеств» (PDF). Анналы чистой и прикладной логики. 140: 233–252. Дои:10.1016 / j.apal.2005.09.009. Zbl  1089.03004. Архивировано из оригинал (PDF) на 2016-10-20. Получено 2014-08-16.
• Леви, Азриэль (1965). Иерархия формул в теории множеств. Mem. Являюсь. Математика. Soc. 57. Zbl  0202.30502.