Аксиоматические теории

Автор Administrator

12/07/2008 г.

§ 7. Аксиоматические теории.

В этом параграфе предполагается, что сигнатура s не более чем счетна. Исчислением предикатов сигнатуры s с равенством (ИПР) называется исчисление, аксиомами которого являются:

аксиомы ИП сигнатуры s
аксиомы равенства:

Е1. " х (х=х),

Е2. " х " y " z ((x = y & y = z ) É x = z ),

E3. " x " y ( x = y É y = x);

Формулы вида

Ep ." x1…" xn " y1…" yn (( x1=y1 &…& xn= yn) É

É (P ( x1,…,xn)º P(y1,…,yn)));

Ef . " x1…" xn " y1…" yn((x1 =y1 &…& xn = yn) É

É (f(x1, …, xn )= f(y1,…,yn)))

для любого предикатного п-местного символа Р из s и любого функционального п-местного символа f из s . Правилами вывода этого исчисления являются правила вывода ИП. Выводимость, а также другие понятия определяются аналогично соответствующим понятиям для ИП.

Используем следующее сокрашение:

$ ! x Â (x) = $ x ( Â (x) & " y (Â (y) É x = y )),

где Â (x) – произвольная формула. Квантор $ !x читается как”существует единственное х такое, что…”.

Элементарной теорией сигнатуры s называется множество Т предложений сигнатуры s È { = }, содержащее все предложения, выводимые из Т в ИПР. Теоремами Т называются все формулы сигнатуры s È { = }, выводимые из Т. Системой аксиом для теории Т называется любое множество формул А Í Т, из которого выводимы в ИПР все предложения в Т. Элементарная теория Т называется непротиворечивой (противоречивой, полной, неполной), если множество предложений Т непротиворечиво (противоречиво, полно, неполно). Система предложений называется независимой, если ни одно из них не может быть выведено в ИПР из остальных.

Моделью теории Т называется всякая нормальная алгебраическая система, в которой истинны все формулы из Т.

Алгебраические системы Â 1 = á М1 ; s ñ и Â 2 = á М2 ; s ñ называются изоморфными, если существует взаимно однозначное соответствие j между М1 и М2 такое, что для любых m1,…,mn Î M1 и Pn, fn, ak Î s

Â 1 ╞ P (m1 ,…, mn) Û Â 2 ╞ P ( j (m1) ,…, j (mn)),

j ( f (m1,…,mn)) = f( j (m1) ,…, j (mn) ),

j (ak) = ak.

Если Â изоморфна некоторой подсистеме системы Â 1, то Â называется изоморфно вложимой в Â 1.

Теорией равенства Е называется множество предложений сигнатуры á = ñ , выводимых в ИПР.

Пусть s а=á s, +, × , 0ñ , где s – символ 1-местной, а + и × – символы 2-местных функций, 0 – предметная константа.

Через Q будем обозначать теорию, аксиомами которой являются:

Q1. " x " y(s(x) = s(y) É x = y ),

Q2. " x ù s(x) = 0,

Q3. " x ( ù x =0 É $ y (x = s(y))),

Q4. " x ( x + 0 = x),

Q5. " x " y( x+ s(y) = s(x+y)),

Q6. " x ( x* 0 = 0),

Q7. " x" y (x * s(y) = x * y +x).

Через x £ y обозначаем формулу $ z (z + x = y), а через x < y – формулу (x £ y & ù x = y).

Через Р будем обозначать теорию сигнатуры s а, аксиомами которой являются Q1—Q7 и бесконечное множество формул вида

РÁ * " y (( Á (0) & " x (Á (x) É Á ( s( x )))) É Á (y)),

Где Á (х) – любая формула сигнатуры s а со свободной переменной х . Формула РÁ называется аксиомой индукции для Á .

Введем следующие обозначения:

Δ0 = 0, Δ1= s(0), …, Δn+1 = s(Δn),…

Через R будем обозначать теорию сигнатуры s а со следующим бесконечным множеством аксиом:

R1(np). Δn+ Δp = Δn+p (для любых n, p Î N ),

R2(np). Δn * Δp = Δn*p (для любых n, p Î N ),

R3(np). Δn ¹ Δp (для любых n, p Î N, n ¹ p),

R4(np). " x ( x £ Δn É (x= Δ0 È … È x = Δn )) (для каждого nÎ N ),

R5(np). " x ( x £ Δn È Δn £ х) (для каждого nÎ N ).

Множество натуральных чисел N , с s(x) = x + 1, обычными сложением и умножением и константой 0, называется стандартной моделью арифметики и обозначается через À = á N ; s, +, × , 0 ñ .

Пусть ZF – теория сигнатуры á Î ñ , где Î бинарный предикат, со следующими аксиомами:

ZF1 . Аксиома объёмности:

" x " y (" z (z Î x º z Î y) º x = y).

ZF2 . Аксиома пары:

" x " y $ z " v (v Î z º (v = x È v = y)).

ZF3 . Аксиома выделения:

" x $ y " z ( z Î y º (zÎ x & Á )),

где Á - формула, не содержащая x, y.

ZF4 . Аксиома множества подмножеств:

" x $ y " z ( z Î y º " u ( uÎ z É u Î x)).

ZF5. Аксиома множества суммы:

" x $ y " z( z Î y º $ v (z Î v & v Î x)).