§ 9. Аксиоматизируемые классы.

Обозначим через К класс всех алгебраических систем сигнатуры Класс К алгебраических систем сигнатуры назовем аксиоматизируемым, если существует элементарная теория Т (К) сигнатуры есть семейство всех моделей теории Т(К). Система аксиом для теории Т(К) называетсясистемой аксиом для К. Класс К называется конечно аксиоматизируемым, если существует конечная система аксиом для К. Класс К называется универсально аксиоматизируемым, если существует система аксиом для К, состоящая из " -формул. Алгебраические системы из класса К будем называть К-системами. К-подсистемой (К-расширением) данной системы Â будем называть систему из класса К , являющуюся подсистемой (расширением) Â . Класс К назовем абстрактным, если вместе с каждой алгебраической системой К содержит ей изоморфные алгебраические системы. Системы Â = <М;s > и Â 1= <М1;s > назовем элементарно эквивалентными, если для любого предложения Á сигнатуры s такая, что

 ╞ Á Û Â 1 ╞ Á 1.

Отображение j : М® М1 назовем элементарным, если для любой формулы Á (х1,…,хп) и любых m1,…,mn Î M

 ╞ Á (m1,…,mn) Þ Â 1( j (m1),…, j (mn)).

Система Â называется элементарно вложимой в Â 1, если существует элементарное отображение Â в Â 1.

§ 8. Фильтрованные произведения.

Фильтром над множеством I называется произвольный фильтр на булевой алгебре R (I ) , т.е. непустое множество D множества P(I), удовлетворяющее условиям:

(а) если X, Y Î D, то (X Ç Y) Î D;

(б) если X Î D, X Í Y Í I, то Y Î D;

(в) Æ Î D.

Фильтр D, удовлетворяющий условию

(г) для всех X Í I X Í D или ( I \ X )Î D,

называется ультрафильтром над I. Фильтр D называется главным, если он содержит наименьший элемент. Фильтр D называется счетно полным, если для любой счетной системы элементов D её пересечение принадлежит D.

Пусть I = m ³ N 0 . Фильтром Фреше над I называется любой фильтр над I, содержащий Ф={X | X Í I и I \ X < m}.

Пусть Â 1= á М1 ; s ñ и Â 2= á М2 ; s ñ ¾ алгебраические системы. Отображение j : M 1® M 2 называется гомоморфизмом из Â 1 в Â 2, если для любых b1 ,… , bn Î M1:

(а) Â 1¦ Pn (b1 ,… , bn ) Þ Â 2¦ Pn ( j (b1),…, j (bn)) для любого предикатного символа Pn Î s ;

(б) j ( Fn (b1 ,… , bn)) = Fn ( j (b1), …, j (bn) ) для любого функционального символа FnÎ s ;

(в) j (а)=а для любой предметной константы а Î s 

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

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

1. аксиомы ИП сигнатуры s
È { = };
2. аксиомы равенства:

Е1. " х (х=х),

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

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

3. Формулы вида

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

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

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

§6. Исчисления предикатов.

Рассмотрим алфавит V = V 1È V 2 È V 3 È V 4 È V 5 È V 6, где V 1 -- V 6 взяты из §4. Понятия и обозначения сигнатуры, терма, формулы, подформулы, свободной и связанной переменной, предложения определяются, как в §4.

В этом параграфе предполагается, что сигнатура s конечна или счетна.

Определим исчисление ИПС. Алфавит исчисления ИПС есть V È á ├ ñ . Понятия секвенции, правила вывода и т.п. определяются аналогично соответствующим понятиям для ИС (см. §3).

Исчисление ИПС определяется следующими схемой аксиом и правилами вывода ( Á , B , Ã -- произвольные формулы, Г, Г1, Г2 , Г3 – конечные последовательности формул, возможно пустые, t – терм, свободный для х в Á (х); Á (t) получается из Á (х) заменой всех свободных вхождений x на t; Г4 – конечная последовательность формул, не содержащих х свободно; D – формула, не содержащая х свободно).

Схема аксиом Á + Á .

§5. Выполнимость формул логики предикатов.

Формулу Á сигнатуры s назовем выполнимой, если существует такая алгебраическая система Â = á M ; s ñ, что Á истинна в Â при некоторых значениях свободных переменных. Формулу Á сигнатуры s назовем тождественно истинной ( или тавтологией) , если Á истинна в любой алгебраической системе сигнатуры sÁ семантически следует из множества формул Г ( символически Г ╞ Á ), если для любой алгебраической системы Â из истинности в ÂÁ в Â при тех же значениях переменных. Если Á ╞ В и В¦ Á , то пишем Á ~ В . при любых значениях свободных переменных. Будем говорить, что формула всех формул из Г при некоторых значениях переменных следует истинность

Формулы вида Q1 x1…QnxnÁ , где Á -- бескванторная формула, Qi есть " или $ , называется предваренной (или пренексной) нормальной формой. Если все Qi равны " , то эта форма называется "-формулой (универсальной формулой), если все Qi равны $ , то эта форма называется $ -формулой. Если существует i (0 £ i £ n) такое, что Q1 ,… ,Qi суть $ , а Qi+1 ,… ,Qn суть " , то эта форма называется скулемовской нормальной формой ( $ " -формулой ).

§4. Язык логики предикатов.

Пусть I, J, K – произвольные множества.

Рассмотрим алфавит V = V 1 È V 2 È V 3 È V 4 È V 5 È V 6, где

V 1 = {v0,v1,v2,…} - предметные переменные,

V 2 ={Pini}i Î I (ni Î N) - предикатные символы,

V 3 = {fjnj} j Î J (nj Î N) - функциональные символы,

V 4= {ak}kÎ K - предметные константы,

V 5 = {&, Ú , É , ù , " , $ } - логические символы,

V 6 = {,, (, )} - вспомогательные символы.

Pini – называется ni-местным предикатным символом, fjnj -- называется nj-местным функциональным символом, символ " называется квантором общности, а символ $ -- квантором существования. Названия остальных символов и сокращенные обозначения формул приведены в §1.

s = V 2 È V 3 È V 4 назовем сигнатурой. На дальнейшем зафиксируем некоторую сигнатуру s . Дадим определение терма сигнатуры s :

1. предметные переменные и предметные константы являются термами;
2. если
fn—п-местный функциональный символ из s и t1, …, tn—термы, то fn(t1, …, tn )-- терм;
3. никаких термов, кроме построенных по пп. 1), 2), нет.

§3. Исчисления высказываний.

Определим исчисление высказываний ИС. Рассмотрим алфавит V = V 1È V 2 È V 3 È V 4, где V 1= {A0,A1,…}, V 2 = { ┐, &,Ú , É }, V 3 = {(, ), ,}, V 4 = { ├ }. Понятие формулы определяется, как в §1. Секвенциями называют выражения вида ( где Á 1,…,Á п, В – любые формулы)

Á 1,…,Á п + В, где п > 0 ( из Á 1,…,Á п следует В)

+ В (В доказуема)

Á 1,…,Á п ├, где п > 0 ( система Á 1,…,Á п противоречива).

Правилом вывода называется выражение вида , где S 1,… , S к, S -- произвольные секвенции. S называется непосредственным следствием S 1,… , S к по данному правилу вывода.

Исчисление ИС определяется следующими схемой аксиом и правилами вывода (где Á , B , Ã -- произвольные формулы, Г, Г1, Г2 , Г3 – конечные последовательности формул, возможно пустые).

Схема аксиом Á + Á .