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

на множині АС одної сигнатури є відношенням еквівалентності.

Ізоморфізм ( АС A в АС A назвемо автоморфізмом алгебраїчної системи A.

є бієкцією B\x2192А, причому для + та = викону-ються умови (HF) та (EР). Отже, ( є ізоморфізмом A в B.

є бієкцією А\x2192В, причому для + та = виконуються умови (HF) та (EР). Отже, ( є ізоморфізмом B в A.

. Тоді ( є гомоморфізмом АС (N, {+, =}) в АС ({0, 1}, {+, =}), бо для + та = виконуються умови (HF) та (НР). Умова (EР) не виконується, бо 0(2, але ((0)=((1). Отже, такий гомоморфізм не є повним.

Приклад 3. Нехай A =(Z, {+, =}). Тоді ((x) = -х є бієкцією Z\x2192Z, причому для + та = виконуються умови (HF) та (EР). Отже, ( є автоморфізмом АС A =(Z, {+, =}).

Відношення еквівалентності ( на множині А називають відношенням конгруентності на АС A=(A, (), якщо ( стабільне відносно базових функцій АС A . Це означає: для кожного f(Fs арності п якщо a1 (b1 , ..., an (bn , то fA (a1 , ..., an) ( fA (b1 , ..., bn).

Нехай A=(A, (), ( \xF02D відношення конгруентності на A . Фактор система B=(B, () системи A по відгошенню ( задається так.

.

Для кожного f(Fs арності п задамо fB ([a1],..., [an])=[fA (a1 ,..., an)].

Для кожного p(Ps арності п покладемо

знайдуться c1([a1], ..., cn([an] такі, що pA (c1 , ..., cn)=T.

Конгруентність відношення ( гарантує коректність такого визна-чення функцій fB . Спрaвді, для довільних c1 , ..., cn таких, що [a1]=[c1], ..., [an]=[cn], маємо a1 ( c1 , ..., an ( cn , звідки за конгруентні-стю ( fA (a1 , ..., an) ( fA (с1 , ..., сn), тому [fA (a1 , ..., an)]=.[fA (c1 , ..., cn)].

наступним чином:

для кожного a(A покладемо ((а)=[a].

є гомоморфізмом АС A=(A, () в АС B=(B, (). Такий гомоморфізм називається канонічним.

{[0], [1]}. Тут [0] та [1] є відповідно множиною парних та непарних натуральних чисел.

, (ar) наступним чином :

+([0], [0])=[0]; (([0], [0])=[0];

+([0], [1])=[1]; (([0], [1])=[0];

+([1], [0])=[1]; (([1], [0])=[0];

+([1], [1])=[0]; (([1], [1])=[1].

Константні символи 0 та 1 інтерпретуються як [0] та [1].

.

В подальших визначеннях імена & та (x похідних логічних операції & та (x трактуємо як символи розширеного алфавіту. Визначення формули мови розширеного алфавіту цілком зрозуміле.

Формулу, утворену з атомарних формул за допомогою символів логічних операцій (, & та (x, назвемо (-позитивною формулою.

Формулу, утворену з атомарних формул за допомогою допомогою символів логічних операцій (, &, (x та (x, назвемо позитивною формулою.

Кожне відображення ( : А\x2192В можна розширити до відображення ( : АХ \x2192ВХ таким чином: (([xi (ai] i(() = [xi (((ai)] i((). Зокрема, (((a1 , ..., an)) = (((a1) , ..., ((an)).

Теорема 5.1. Нехай ( : А\x2192В \xF02D гомоморфізм АС A=(A, () в АС B=(B, (). Тоді :

1) для кожного терма t сигнатури ( з множиною предметних імен Х для довільних d(AХ маємо ((tA(d)) = tB(((d)) ;