10: Теорема про повноту

Last updated

Oct 27, 2022
Save as PDF
- 9.14: Резюме
- 10.1: Вступ

$\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: Теорема Левенгейма-Сколема
Теорема Левенгейма-Сколема говорить, що якщо теорія має нескінченну модель, то вона також має модель, яка не більше ніж незліченно нескінченна.
10.12: Резюме