10.11: Теорема Левенгейма-Сколема

Last updated

Oct 27, 2022
Save as PDF
- 10.10: Пряме доказ теореми компактності
- 10.12: Резюме

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

Template:MathJaxZach

Теорема Левенгейма-Сколема говорить, що якщо теорія має нескінченну модель, то вона також має модель, яка не більше ніж незліченно нескінченна. Безпосереднім наслідком цього факту є те, що логіка першого порядку не може висловити, що розмір структури є незліченним: будь-яке речення або набір речень, задоволених у всіх незліченних структурах, також задовольняється деякою підрахунковою структурою.

Теорема $\PageIndex{1}$

Якщо $\Gamma$ послідовний, то він має підрахункову модель, тобто вона задовольняється в структурі, область якої або скінченна, або незліченно нескінченна.

Доказ. Якщо $\Gamma$ послідовна, структура, $\Struct M$ поставлена доказом теореми повноти, має область $\Domain{M}$ , яка не перевищує сукупність термінів мови $\Lang L$ . Так $\Struct M$ і в більшості незліченно нескінченно. ◻

Теорема $\PageIndex{2}$

Якщо $\Gamma$ послідовний набір пропозицій мовою логіки першого порядку без ідентичності, то він має незліченно нескінченну модель, тобто вона задовольняється в структурі, область якої нескінченна і піддається зліченню.

Доказ. Якщо $\Gamma$ послідовний і не містить речень, в яких фігурує ідентичність, то структура, $\Struct M$ поставлена доказом теореми повноти, має область, $\Domain{M}$ ідентичну набору термінів мови $\Lang L'$ . Так $\Struct{M}$ зліченно нескінченно, так як $\Trm[L']$ є. ◻

Приклад $\PageIndex{1}$ : Skolem’s Paradox

Теорія множин Цермело-Френкеля $\Log{ZFC}$ - це дуже потужна основа, в якій можуть бути виражені практично всі математичні твердження, включаючи факти про розміри множин. Так, наприклад, $\Log{ZFC}$ може довести, що безліч $\Real$ дійсних чисел є незліченним, це може довести Теорему Кантора, що потужність набору будь-якої множини більше, ніж сама множина, і т.д., Якщо $\Log{ZFC}$ послідовний, його моделі всі нескінченні, і, крім того, всі вони містять елементи, про які теорія говорить, що вони незліченні, такі як елемент, який робить істинною теорему про $\Log{ZFC}$ те, що існує набір степенів натуральних чисел. За теоремою Левенгейма-Сколема $\Log{ZFC}$ також має підрахункові моделі - моделі, які містять «незліченні» множини, але які самі по собі підраховуються.