Skip to main content
LibreTexts - Ukrayinska

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

  1. Last updated
  2. Save as PDF
  • Page ID
    52759

    • \( \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}\) також має підрахункові моделі - моделі, які містять «незліченні» множини, але які самі по собі підраховуються.