28. Поняття несуперечливості та максимальності (повноти) теорії 1-го порядку. Теорема Лінденбаума.

Теорія 1-го порядку T називається несуперечливою, якщо не існує формули F такої, що T |F та T | F.

Несуперечлива теорія 1-го порядку T називається повною, якщо для кожної замкненої формули F маємо T |F або T | F.

Теорему Лінденбаума: кожне несуперечлива теорія 1-го порядку має несуперечливе просте повне розширення.

28. Поняття пересічності та розв’язності теорії 1-го порядку. Теорема про розв’язність.

Теорія T перелічна, якщо множина k(Th(T)) рекурсивно перелічна.

Теорія T розв’язна, або рекурсивна, якщо множина k(Th(T)) номерів теорем теорії T рекурсивна.

Теорема 6.3.1 (про розв’язність). Нехай T  повна теорія 1-го порядку із алгоритмічно перелічною множиною аксіом. Тоді T розв’язна.

Наслідок. Кожна повна перелічна теорія 1--го порядку розв’язна.

28. Теорема Гьоделя про повноту. Теорема компактності.

Теорема 6.3.3 (теорема Гьоделя про повноту, 1-е формулювання). Нехай T  теорія 1-го порядку. Тоді формула F істинна в T  T F.

Теорема 6.3.4 (теорема Гьоделя про повноту, 2-е формулювання). Теорія 1-го порядку T несуперечлива  T має модель.

Приклад 6.3.4 (теорема компактності, 1-е формулювaння). Формула F істинна в T  F істинна в деякій САЧ КÍT.

Нехай F істинна в T. За теоремою 6.3.3 TF. Таке виведення використовує тільки скінченну кількість аксіом, тому може бути проведене в рамках деякої САЧ КÍT. Отже, КF, звідки F істинна в К.

Кожна модель теорії T є моделлю кожного її звуження, тому якщо F істинна в деякій САЧ КÍT, то F істинна в T.

28. Теорема Льовенгейма-Сколема. Парадокси Сколема. Нестандартні моделі Ar.

Теорема 6.3.5 (теорема Льовенгейма-Сколема про підйом) Нехай теорія 1-го порядку T потужності a має нескінченну модель. Тоді T має модель довільної потужності b³a.

Приклад 6.3.5. Теорія 1-го порядку T, сигнатура якої не має нелогічних символів, а множина власних аксіом складається з формул вигляду х=у, категорична. Справді, всі моделі теорії T 1-елементні. Такі моделі ізоморфні, бо сигнатура мови має тільки логічний символ =.

Якщо теорія 1-го порядку T має нескінченні моделі, вона не може бути категоричною, бо в силу теореми 6.3.5 T має моделі різних нескінченних потужностей, а такі моделі неізоморфні.

Неповнота Ar має принциповий характер [6, 12, 23], її не можна усунути послідовними розширеннями Ar шляхом поступового приєднання до системи нових аксіом.

28. Теорема Гьоделя про неповноту, їх значення.

Тeорeма 7.1.4 (перша тeорeма Гьодeля про нeповноту). Якщо формальна арифмeтика Ar нeсупeрeчлива, то Ar нeповна.

Доведення 1-ї теореми Гьоделя можна провести для кожної формальної системи, в якій моделюється Ar. Таким чином, кожна достатньо багата несуперечлива аксіоматична система необхідно неповна, причому така неповнота має принциповий характер

Тeорeма 7.1.6 (друга тeорeма Гьодeля про нeповноту). Якщо Ar нeсупeрeчлива, то Сon не є теоремою Ar.

Друга теорема Гьоделя про неповноту справджується для кожної формальної системи, в якій моделюється Ar. Тому для кожної достатньо багатої системи доведення її несуперечливості з необхідністю вимагає засобів, які лежать за межами самої системи.