Логіки першого порядку, Детальна інформація

Приклад 9. Aрифметичними є предикати: “x є парним числом” та “x ділиться на у”. Ці предикати виражаються арифметичними формулами \xF024y(x=y+y) та \xF024z(x=y(z).

Приклад 10. Предикат “x є простим числом” арифметичний. Він ви-ражається арифметичною формулою \xF024y\xF024z(x=y(z( y=1( z=1)&(x=1.

Приклад 11. Предикати "x(y" та "x
Використовуючи приклад 11, в записах арифметичних формул надалi вживатимемо скорочення вигляду x(y та x
Приклад 12. Предикат "х(у" в АС N=(N, \xF073ar), R=(R, \xF073ar), Z=(Z, \xF073ar) виражається рiзними арифметичними формулами. Наприклад, для N маємо \xF024z(x+z=y); для R маємо \xF024z(x+z(z=y), для Z маємо маємо \xF024z\xF024u\xF024v\xF024w(x+z(z+u(u+v(v+w(w=y).

Приклад 13. Арифметичними є наступні функцiї:

1) Функцiя x+y виражається арифметичною формулою z=x+y.

2) Функцiя x(y виражається арифметичною формулою z=x(y.

3) Функцiя x-y виражається арифметичною формулою y+z=x.

4) Функцiя [x/y] виражається арифметичною формулою

z(y (x & x<(z+1)(y.

5) Функцiя mod(х, у) виражається арифметичною формулою

\xF024u(x=z+u(y & z
] виражається арифметичною формулою

z(z (x & z<(z+1)((z+1).

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

виража-ються вiдповiдно арифметичними формулами (\xF0DA(, (&( та \xF0D8( .

5. ГОМОМОРФІЗМИ АЛГЕБРАЇЧНИХ СИСТЕМ

Для алгебраїчних систем однієї сигнатури введемо поняття гомоморфізму. Нехай A=(A, I, () та B=(B, I, ().

Гомоморфізмом АС A в АС B будемо називати відображення ( : А\x2192В таке, що:

\xF02D для кожного f(Fs арності п для всіх a1 , ..., an (A маємо

((fA (a1 , ..., an))=fВ (((a1) , ..., ((an)) (HF)

\xF02D для кожного р(Рs арності п для всіх a1 , ..., an (A маємо

якщо рA (a1 , ..., an))=Т, то рВ(((a1) , ..., ((an))=Т (HР)

Гомоморфізм ( АС A в АС B назвемо повним гомоморфізмом, якщо умова (HP) замінюється сильнішою умовою:

\xF02D для кожного р(Рs арності п для всіх a1 , ..., an (A маємо

рA (a1 , ..., an)) = рВ(((a1) , ..., ((an))=Т (ЕР)

Повний гомоморфізм ( назвемо сильним гомоморфізмом, якщо відображення ( сюр’єктивне.

Повний гомоморфізм ( назвемо ізоморфізмом, якщо відобра-ження ( бієктивне.

B, якщо існує ізоморфізм ( АС A в АС B.