Используем следующее сокрашение:
$ ! x  (x) = $ x (  (x) & " y ( (y) É x = y )),
Используем следующее сокрашение:
$ ! 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)).
ZF6. Аксиома выбора:
" x( " y " z((y Î x & zÎ x) É ($ v (v Î y) &
&( $ u ( u Î z & u Î y) É z = y))) É
É $ u " t (t Î x É $ v " w (v = w º (w Î u & w Î t)))).
ZF7. Аксиома бесконечности:
$ x (" y (ù $ z (z Î y) É yÎ x) & " w (w Î x) É
É " u (" v (v Î u º (v = w È v Î w)) É u Î x))).
ZF8 . Аксиома регулярности:
" x ( $ y (y Î x) É $ y ( y Î x & " z (z Î x É ù z Î y))).
ZF9. Аксиома замены:
" x (" y" z " w (( y Î x & Á ( y , z) & Á (y, w)) É z = w) É
É $ r " s (s Î r º $ t ( t Î x & Á (t, s)))),
где Á (t, s)—формула ZF.
ZF