Иерархия Леви

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

Определения

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

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

Формула $A$ называется:

• $\Sigma _{i+1}$ если $A$ эквивалентно $\exists x_{1}...\exists x_{n}B$ в ZFC, где $B$ является $\Pi _{i}$
• $\Pi _{i+1}$ если $A$ эквивалентно $\forall x_{1}...\forall x_{n}B$ в ZFC, где $B$ является $\Sigma _{i}$
• Если в формуле есть оба $\Sigma _{i}$ форма и $\Pi _{i}$ форму, это называется $\Delta _{i}$.

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

Первоначальное обозначение Леви было $\Sigma _{i}^{\mathsf {ZFC}}$ (соответственно $\Pi _{i}^{\mathsf {ZFC}}$) в силу доказуемой логической эквивалентности, Строго говоря, указанные выше уровни следует называть $\Sigma _{i}^{\mathsf {ZFC}}$ (соответственно $\Pi _{i}^{\mathsf {ZFC}}$) для указания теории, в которой осуществляется эквивалентность, однако это обычно ясно из контекста. ^{стр. 441–442.} Полерс определил $\Delta _{1}$ в частности семантически, в котором формула " $\Delta _{1}$ в структуре $M$".

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

Примеры

Σ ₀ =Π ₀ =Δ ₀ формулы и понятия

• х = {у, z} ^{п. 14}
• х ⊆ у
• x — транзитивное множество
• x — порядковый номер , x — предельный порядковый номер , x — порядковый номер-преемник
• x — конечный ординал
• Первый счетный ординал ω
• x — упорядоченная пара. Первая запись упорядоченной пары x — это . Вторая запись упорядоченной пары x — b. ^{п. 14}
• f — функция. x — область определения/диапазон функции f . y — значение f по x ^{п. 14}
• Декартово произведение двух множеств.
• x - это объединение y
• x является членом α- го уровня гёделевской L
• R — это отношение с доменом/диапазоном/полем a ^{п. 14}

Δ ₁ -формулы и понятия

• x — обоснованное отношение к y
• х конечен ^стр.15
• Порядковое сложение , умножение и возведение в степень
• Ранг (относительно конструктивной вселенной Гёделя ) множества ^{п. 61}
• Транзитивное замыкание множества.

Σ ₁ -формулы и понятия

• х счетен ​ .
• | Икс |≤| И |, | Х |=| И |.
• x конструктивен.
• g — ограничение функции f на a ^{п. 23}
• g образ f на — ^{п. 23}
• b является порядковым номером преемника a ^{п. 23}
• ранг( х ) ^{п. 29}
• Крах Мостовского ​ $(x,\in )$ ^{п. 29}

Π ₁ -формулы и понятия

• х — кардинал
• x — правильный кардинал
• x — предельный кардинал
• x — недоступный кардинал .
• x - это мощности набор y

Δ ₂ -формулы и понятия

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

Σ ₂ -формулы и понятия

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

Π ₂ -формулы и понятия

• Аксиома выбора
• Обобщенная гипотеза континуума
• Аксиома конструктивности : V = L

Σ ₃ -формулы и понятия

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

Π ₃ -формулы и понятия

• κ — расширяемый кардинал

Σ ₄ -формулы и понятия

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

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

Позволять $n\geq 1$. Иерархия Леви обладает следующими свойствами: ^{п. 184}

• Если $\phi$ является $\Sigma _{n}$, затем $\lnot \phi$ является $\Pi _{n}$.
• Если $\phi$ является $\Pi _{n}$, затем $\lnot \phi$ является $\Sigma _{n}$.
• Если $\phi$ и $\psi$ являются $\Sigma _{n}$, затем $\exists x\phi$, $\phi \land \psi$, $\phi \lor \psi$, $\exists (x\in z)\phi$, и $\forall (x\in z)\phi$ все $\Sigma _{n}$.
• Если $\phi$ и $\psi$ являются $\Pi _{n}$, затем $\forall x\phi$, $\phi \land \psi$, $\phi \lor \psi$, $\exists (x\in z)\phi$, и $\forall (x\in z)\phi$ все $\Pi _{n}$.
• Если $\phi$ является $\Sigma _{n}$ и $\psi$ является $\Pi _{n}$, затем $\phi \implies \psi$ является $\Pi _{n}$.
• Если $\phi$ является $\Pi _{n}$ и $\psi$ является $\Sigma _{n}$, затем $\phi \implies \psi$ является $\Sigma _{n}$.

Девлин п. 29

См. также

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

Ссылки

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