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

2) для кожної (-позитивної формули ( сигнатури ( з множиною вільних імен Х для довільних d(AХ маємо: якщо (А (d)=Т, то (В(((d))=Т.

Теорема 5.2 Нехай сюр’єктивне відображення ( : А\x2192В є гомо-морфізмом АС A=(A, () в АС B=(B, (). Тоді виконується твердження 1) теореми 4.5.1 та

2) для кожної позитивної формули ( сигнатури ( з множиною вільних імен Х для довільних d(AХ маємо: якщо (А (d)=Т, то (В (((d))=Т.

Наслідок. Нехай ( \xF02D сюр’єктивний гомоморфізм АС A=(A, () в АС B=(B, (). Тоді для кожної позитивної формули ( сигнатури ( якщо A \xF07C((, то B \xF07C((.

Теорема 5.3. Нехай ( : А\x2192В \xF02D сильний гомоморфізм АС A=(A, () в АС B=(B, (). Тоді виконується твердження 1) теореми 4.5.1 та

2) для кожної формули ( сигнатури ( з множиною вільних імен Х для довільних d(AХ маємо (А (d)=(В(((d)).

Наслідок 1 (теорема про ізоморфізм). Нехай ( : А\x2192В \xF02D ізоморфізм АС A=(A, () в АС B=(B, (). Тоді виконуються твердження 1) теореми 4.5.1 та твердження 2) теореми 4.5.3.

Наслідок 2. Нехай ( \xF02D сильний гомоморфізм АС A=(A, () в АС B=(B, (). Тоді для кожної формули ( сигнатури ( A \xF07C(( ( B \xF07C((.

={[0], [1]} є сюр’єктивним гомоморфізмом АС N в АС Nmod2 . Розглянемо формулу ((1+1)=0, яку позначимо (. Тоді маємо N \xF07C((, але N mod2 \xF07C((, адже +([1], [1])=[0].

6. ІЗОМОРФІЗМ ТА ЕЛЕМЕНТАРНА ЕКВІВАЛЕНТНІСТЬ АГЕБРАЇЧНИХ СИСТЕМ. МЕТОД АВТОМОРФІЗМІВ

АС A=(A, () та B=(B, () назвемо елементарно еквівалентними, якщо для кожної формули ( сигнатури ( A \xF07C(( ( B \xF07C((.

B.

Елементарна еквівалентність алгебраїчних систем означає, що вони мають однакові властивості на рівні логіки 1-го порядку, тобто їх ніяк не можна відрізнити, використовуючи мову 1-го порядку.

(Q; {(, =}). Справді, нехай ( \xF02D формула (x(y(x=y(y(y). Тоді (R; {(, =}) \xF07C(( та (Q; {(, =}) \xF07C((.

(Q; {+, =}). Справді, нехай ( \xF02D формула (x(y(x=y+y). Тоді (Q; {+, =}) \xF07C(( та (Z; {+, =}) \xF07C((.

(Z, {(, =}). Справді, нехай ( \xF02D формула (m(x(m(x). Тоді (N, {<, =}) \xF07C(( та (Z, {<, =}) \xF07C((.

Із теореми про ізоморфізм (наслідок 1 теореми 4.5.3) випливає:

Твердження 1. Нехай ( \xF02D ізоморфізм АС A=(A, () в АС B=(B, (). Тоді для кожної формули ( сигнатури ( A \xF07C(( ( B \xF07C((.

Твердження 2. Нехай ( \xF02D автоморфізм АС A=(A, (). Тоді для кожної формули ( сигнатури ( з множиною вільних імен Х для довільних d(AХ маємо (А (d)=(А(((d)).

(R, {<, =}), але ці АС неізоморфні, бо множина Q зліченна, а множина R має потужність континууму.

B.

Для доведення виразимості предикату P в АС A достатньо вказати таку формулу (, що P \xF02D суть (A . В той же час для дове-дення невиразимості предикатів в АС доводиться використовувати потужніші засоби. Розглянемо метод доведення невиразимості предикатів в АС за допомогою автоморфізмів.

Теорема 6.1. Нехай ( \xF02D автоморфізм АС A=(A, (). Якщо преди-кат P :AX\x2192{T, F} виразимий в A, то P(d)=P(((d)) для всіх d(AХ.

Нехай P виразимий в A деякою формулою ( сигнатури (, тобто P \xF02D суть (A . Використовуючи твердження 2, маємо P(d)=(А(d)=(А(((d))=Р(((d)) для довільних d(AХ.

Отже, для доведення невиразимості P в A досить знайти авто-морфізм ( системи A такий, що порушується умова P(d)=P(((d)).

Приклад 4. Предикат “z=x+y” не виразимий в АС Z<=(Z, {<, =}).

Відображення ((х)=х+1 є автоморфізмом Z< , бо бієктивне і зберігає значення предикатів < та = . Але ((0)=1, тому вірно 0=0+0 та невірно ((0)=((0)+((0).

Приклад 6. Предикат “x
Приклад 7. Предикат “y=x+1” не виразимий в АС (N, {y=x+2, =}).

є автоморфізмом такої АС, бо бієктивне і зберігає значення базових предикатів. Предикат "y=x+1" позначимо Р(х, у). Тоді маємо Р(1, 0)=T та Р(((0), ((1))=Р(0, 1)=F.