Лекция №18

Тема: ТЕОРИИ ПЕРВОГО ПОРЯДКА С РАВЕНСТВОМ.

КАТЕГОРИЧНЫЕ ТЕОРИИ

Основные вопросы, рассматриваемые на лекции:

1. Аксиомы для равенства

2. Теоремы симметричности и транзитивности равенства

3. Изоморфизм интерпретаций

4. Категоричные в мощности теории

Краткое содержание лекционного материала

Теории первого порядка чаще рассматриваются как теории с равенством, в которых предполагается дополнительный логический символ – бинарный предикатный символ = и в которых принимаются следующие дополнительные логические аксиомы:

(A ₅) x = x;

(A ₆) x ₁= y ₁Þ x ₂= y ₂Þ…Þ x_n = y_n Þ fx ₁ x ₂… x_n = fy ₁ x ₂… x_n;

(A ₇) x ₁= y ₁Þ x ₂= y ₂Þ…Þ x_n = y_n Þ Px ₁ x ₂… x_n = Py ₁ x ₂… x_n.

В формулах (A ₅) - (A ₇): символы x, x ₁, y ₁, x ₂, y ₂, …, x_n, y_n – переменные, f – n -арный функциональный символ, P – n -арный предикатный символ.

В аксиомах (A ₅) - (A ₇) отражены простейшие, но основные, свойства равенства: (A ₅) – свойство симметричности, (A ₆) – свойство подстановки для функции, (A ₆) – свойство подстановки для отношения. Еще два основных свойства равенства приведем в виде теорем:

(T ₃) |¾ x = y Þ x = y; (симметричность)

(T ₄) |¾ x = y Þ y = z Þ x = z. (транзитивность)

Вывод теоремы (T ₃):

1. x = y Þ x = x Þ y = x (A ₇), P есть само равенство

2. x = x (A ₅)

3. x = y Þ y = x тавтологическое следствие

Вывод теоремы (T ₄):

1. x = z Þ y = x Þ y = z (A ₇), P есть само равенство

2. y = x Þ x = y Þ y = z тавтологическое следствие

3. x = y Þ x = y (T ₃)

4. x = y Þ y = z Þ x = z тавтологическое следствие, 2, 3

Пусть I, J – две интерпретации языка L. Отображение H:I ® J изоморфизмом интерпретаций, если H – биекция и H сохраняет константы, функции, отношения интерпретации I в J:

H(e_I) = e_J для каждой константы e из L;

H(f_I(x₁,…,x_n)) = f_J(H(x₁),…,H(x_n) для каждого n- арного функционального символа f из L;

p_I(x₁,…,x_n) Û p_J(H(x₁),…,H(x_n) для каждого n- арного предикатного символа p из L.

Отношение изоморфизма между интерпретациями является отношением эквивалентности.

Теория T называется категоричной в мощности m, если теория T имеет хотя бы одну модель мощности m и все модели мощности m теории T попарно изоморфны.

Теория T с нелогической аксиомой x = y категорична в мощности 1.

Элементарная теория групп не категорична ни в одной бесконечной мощности m.