10: Теорема про повноту
- Page ID
- 52739
\( \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}}\)
- 10.1: Вступ
- Теорема про повноту є одним з найбільш фундаментальних результатів про логіку.
- 10.2: Контур доказу
- Доказ теореми про повноту трохи складний, і при першому її прочитанні легко загубитися. Отже, виділимо доказ.
- 10.3: Повні послідовні набори речень
- Повні комплекти пропозицій не залишають жодних питань без відповіді. Для будь-якого речення\(\Gamma\) «говорить»\(A\), якщо\(A\) є істинним чи хибним.
- 10.4: Розширення Хенкіна
- Частина завдання в доведенні теореми про повноту полягає в тому, що модель, яку ми будуємо з повного узгодженого набору,\(\Gamma\) повинна зробити всі кількісні формули\(\Gamma\) істинними. Для того, щоб гарантувати це, ми використовуємо трюк завдяки Леону Хенкіну.
- 10.5: Лемма Лінденбаума
- Зараз ми доведемо лему, яка показує, що будь-який послідовний набір речень міститься в деякому наборі речень, який є не просто послідовним, але й повним.
- 10.6: Побудова моделі
- Зараз нас це не турбує\(=\), тобто ми хочемо лише показати, що послідовний набір\(\Gamma\) пропозицій, які не містять,\(=\) є задовільним. Спочатку ми\(\Gamma\) поширюємося на послідовний, повний і насичений набір\(\Gamma^*\). В даному випадку визначення моделі\(M(\Gamma^*)\) нескладне.
- 10.7: Ідентичність
- Побудова термінової моделі, наведеної в попередньому розділі, достатньо для встановлення повноти логіки першого порядку для множин\(\Gamma\), які не містять\(=\). Він не працює, однак, якщо він\(=\) присутній. Ми можемо виправити це за допомогою конструкції, відомої як «факторинг».
- 10.8: Теорема про повноту
- Давайте об'єднаємо наші результати: дійдемо до теореми повноти. \(\Gamma\)Дозволяти бути сукупністю речень. Якщо\(\Gamma\) послідовний, він задовольняється.
- 10.9: Теорема компактності
- Одним з важливих наслідків теореми повноти є теорема компактності. Теорема компактності стверджує, що якщо кожна скінченна підмножина множини речень задовольняється, вся множина є задовільною, навіть якщо сама множина нескінченна.
- 10.10: Пряме доказ теореми компактності
- Теорему компактності можна довести безпосередньо, не звертаючись до теореми повноти, використовуючи ті ж ідеї, що і в доведенні теореми повноти.
- 10.11: Теорема Левенгейма-Сколема
- Теорема Левенгейма-Сколема говорить, що якщо теорія має нескінченну модель, то вона також має модель, яка не більше ніж незліченно нескінченна.