7.Арифметичні предикати, мн-ни та функції. Арифметичність чрф та рпм. Теорема Тарського.

Предикат Р : N^k→{T, F} арифметичний, якщо iснує арифметична формула (x₁, .., x_k) з вільними іменами x₁, .., x_k така, що Р(п₁, .., п_k) = Т  N [,...,]. Така формула  виражає предикат Р.

Множина LN^k арифметична, якщо iснує арифметична формула (x₁, .., x_k) з вільними іменами x₁, .., x_k така, що (,...,)L  N [,...,]. Така формула  виражає множину L.

Отже, множина LN^k арифметична  L є областю iстинностi деякого арифметичного предикату.

Функцiя f : N^k→N арифметична, якщо її графiк _f є арифметичною множиною.

Арифметична формула  виражає функцiю f, якщо формула  виражає _f.

Тeорeма Клас арифметичних множин замкнений вiдносно операцiй ,  та доповнення.

Тeорeма Кожна ЧРФ арифметична.

Тeорeма Кожна РПМ арифметична.

Наслідок. Для класiв РПМ i АМ має мiсце строге включення РПМАМ.

Множину номерiв всiх ІАФ (індексна арифметична функція) позначимо T.

Тeорeма (Тарський). Множина T неарифметична.

8.Теорія 1-го порядку, числення предикатів 1-го порядку. Моделі теорій 1-го порядку. Теорема дедукції. Поняття несупреречливості, повноти.

Теорією 1-го порядку (численням 1-го порядку) назвемо формальну систему T=(L, A, P), де L мова 1-го порядку, A  множина аксіом, яка розбита на множину логiчних аксіом та множину власних аксiом, P множина правил виведення. Логiчнi аксiоми присутнi у всiх теоріях 1-го порядку, власнi аксiоми визначають специфiку тієї чи iншої теорії.

Множина логiчних аксiом задається такими схемами аксiом:

Ах1)   пропозицiйнi аксiоми;

Ах2) x=x  аксiоми тотожностi;

Ах3) _x[t]x  аксiоми пiдстановки;

Ах4) x₁=y₁...x_n=y_n fx₁...x_n = fy₁...y_n та x₁=y₁...x_n = y_n px₁...x_nрy₁...y_n  аксiоми рiвностi.

Теорія 1-го порядку, яка не мiстить власних аксiом, називається численням предикатiв 1-го порядку (скорочено ЧП-1).

Множина P складається з наступних правил виведення:

П1) |  правило розширення. 

П2) |  правило скорочення.

П3) () |()  правило асоціативності.

П4) , |  правило перетину.

П5)  x, якщо x не вiльна в ,  правило -введення.

Теоремою теорії 1-го порядку T називають формулу, яка виводиться iз логiчних та власних аксiом за допомогою скiнченної кiлькостi застосувань правил виведення П1 - П5.

Моделлю теорії 1-го порядку T називається iнтерпретацiя мови теорії, на якiй iстиннi всi власнi аксiоми теорії.

Моделлю елементарної теорiї груп Gr є кожна група.

Моделлю елементарної теорiї полiв Fl є кожне поле.

Моделлю формальної арифметики Ar є N  стандартна iнтерпретацiя L_ar.

Нехай T  довiльна теорія 1-го порядку, Ax  множина її власних аксiом,   деяка множина формул. Розширення теорії T з множиною власних аксiом Ax позначають T []. Зокрема, теорію, отриману iз T додаванням A як нової аксiоми, позначимо T [A]. Вживатимемо також зрозумiлi позначення T [A₁, ..., A_n] та T [A₁, ..., A_n , ...].

Тeорeма дeдукції Нехай A  замкнена формула. Тодi для довiльної формули B маємо: T AB  T [A] B.

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

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

Тeорeма Теорія 1-го порядку T супeрeчлива  T S для кожної формули S мови теорії T.

Тeорeма Числeння прeдикатiв 1-го порядку нeповнe.