Математическая логика - Кожухов И.Б., Романов А.В. [2008]

новых констант.

Ω* = Ωn . Тогда

Доказательство. Положим Ω0 = Ω и Ωn+1 = Ωn

{cϕ,x | x VarS ,ϕ FormΩn } n,

n : N

Th*

=Theory(Th { x :S ϕ(x) → ϕ(cϕ,x ) | x VarS ,ϕ FormΩ }).

*

Как следствие, Th*

будет полной теорией Хенкина в сигнатуре Ω , расширяющей Th.

*

*

Лемма 3. Если теория Th непротиворечива, то у неё есть модель.

Доказательство. Мы построим модель E для Th*. Носителем каждого сорта S будет множество всех

*

термов

сорта

S.

Для

каждого терма

t

полагаем

tE = t. Для

атомарных

формул

PE(t ,…,t ) = 1 Th*

P(t ,…,t ). Индукцией по построению замкнутой формулы ϕ легко показать, что

1

n

*

1

n

E

ϕ Th*

ϕ.

*

В логике с равенством нужно сделать ещё один шаг, поскольку в полученной модели не обязательно

выполняется пункт 5 –

конструкция

гарантирует

только, что

(t1 ) =

(t2 )

(t1

= t2 ) = 1

для

любой

π

π

π

оценки

π. Назовём два терма

t и s

одного сорта Th* -эквивалентными, если Th*

t = s.

В качестве

*

*

носителя S следует взять множество классов Th* -эквивалентности термов сорта S.

*

Следствие. Если Γ

ND ϕ,

то Γ

ϕ.

Доказательство. По лемме 1.6.4

Γ, ¬ϕ непротиворечиво. По лемме 3 существует модель для Γ, ¬ϕ.

Это будет модель для Γ и контрмодель для ϕ.

Теорема 4 (о полноте ИП). Γ ND ϕ тогда и только тогда, когда Γ ϕ

Для всякой формулы ϕ в сигнатуре ;i′/1; 0 со свободными переменными n,m ,…,m

,

1

k

51

(П1)

Γ t′ = s′

(П2)

Γ

¬t′

=

0

Γ

t = s

ϕ(n′)

Γ

ϕ(0)

Γ

,n Nat,ϕ(n)

1

2

(П3)

Γ1 Γ2 n ϕ(n)

Теорема 1.

У

каждого

числа,

кроме 0, есть предшествующее ему.

Формально:

n (¬n = 0 → m m′ = n).

Доказательство: Положим ϕ(n) = (¬n = 0 → m :Nat m′ = n). Имеем

(ИВ)

(I =)

ϕ → (¬ϕ → ψ)

(0 = 0 → (¬0 = 0 → m m′ = 0))

0 = 0

E →

¬0 = 0 → m m′ = 0

ϕ(0)

и

n Nat

n′ = n′

n Nat

m m′ = n′

n Nat, ¬0 = n′

m m′ = n′

n Nat

¬0 = n′ → m m′ = n′

n Nat

ϕ(n′)

n Nat,ϕ(n) ϕ(n′)

Применение П3 даёт искомое.

Определим операцию сложения двух

натуральных чисел. Пусть n :Nat. Положим

n + 0 = n и

Докажем закон коммутативности сложения натуральных чисел, т.е. n,m n +m = m +n. Для этого

нам понадобятся три леммы.

Лемма 1. n 0 +n = n.

Доказательство проведём индукцией по предикату

0 +n = n.

При n = 0 утверждение очевидно.

Пусть 0 +n = n; тогда 0 +n′ = (0 +n)′ = n′.

Лемма 2. n n + 0 = 0 +n.

Доказательство. n + 0 = n = 0 +n.

′

′

Лемма 3. n,m n

+m = n +m .

Доказательство.

Индукция по

предикату n n′ +m = n +m′.

При

m = 0 :

n

′

+ 0 = n

′

= n +1 = n

+ 0

′

.

Пусть

теперь

известно

′

+m

′

Тогда

n n

= n +m .

a <b a ≤b ¬a = b, операцию умножения: a 1 = a,

a x ′ = a x +a,

и так далее. С помощью аксиом

Пеано можно доказать законы ассоциативности

(a b) c = a (b c) и

коммутативности a b = b a

умножения,

а также закон дистрибутивности (a +b) c = a c +b c.

Доказываются также свойства

неравенств:

a <b b <c a <c, a <b a +c <b +c

и многие другие. Тем самым аксиомы Пеано

позволяют построить строгую и стройную теорию натуральных чисел.

Теорема 2. Любые два модели N1 и N2, удовлетворяющие аксиомам PA2, изоморфны друг другу.

Доказательство. Определим отображение f

следующим образом:

положим f (0N1 ) = 0N2 ,

и если

f (a) = b, то положим f (a′N1 ) = b′N2 . В силу аксиомы (П2)

f – вложение. Определим предикат ϕ на N

1

и

1

предикат ϕ2

на N2 следующим образом:

ϕ1(x) y :N2

f (x) = y и ϕ2 (y) x :N1 f (x) = y. По аксиоме

(П3') верно x :N1

ϕ1(x) и y :N2 ϕ2 (y).

То есть f

определено на всём N1 и область значений f

– N2 .

Следовательно, f

– взаимно однозначное отображение из N1 в N2 . Из определения f немедленно видно,

что f (x ′) = f (x)′. Таким образом, f – изоморфизм.

Теорема 3. Если стандартный ряд натуральных чисел N– модель теории первого порядка T,

то у T

есть также модель, неизоморфная N.

= (ax +a) +(bx +b) = ax ′ +bx ′.

3. Используя аксиомы действительных чисел, доказать,

что

0 a = 0 для любого действительного

числа a.

Доказательство. По аксиоме (9) ba = (b + 0)a =ba + 0a.

Пусть x

– число, противоположное к ba

(оно существует по аксиоме (3)). Тогда

x +ba = x +(ba + 0a).

По

аксиомам (4)

и (1) получаем:

0 = (x +ba) + 0a, т.е. 0a = 0.

4. Используя аксиомы действительных чисел, доказать, что 1 > 0.

Доказательство. Предположим, что соотношение 1 > 0

неверно.

По аксиоме (6)

1 ≠ 0. Значит, по

аксиоме (13) 1 < 0. Пусть a = −1 (т.е. a

– элемент, противоположный элементу 1 и существующий по

то (a +1)a = 0,

т.е. a2 +a = 0.

Прибавим 1: (a2 +a) +1 = 1.

Воспользуемся

аксиомой (1):

a2 +(a +1) = 1; a2 + 0 = 1; a2 = 1.

Ранее было

доказано, что

a2 > 0. Следовательно, 1 > 0.

Мы получили

противоречие с

3.

Пользуясь

аксиомами

действительных

чисел,

докажите

их

плотность:

a,b a <b → ( c a <b a <c).

4.

Докажите,

что для любого действительного числа

ε > 0 существует натуральное число n

такое,

что

1

< ε.

Можно ли использовать заменить аксиому Архимеда на эту теорему?

n

3.6. Выразимость предикатов

Пусть

M – структура с сигнатурой Ω,

P(x1,…,xn )

– предикат типа (S1M,…,SnM ) → B. Мы будем

говорить, что формула ϕ(x

,…,x

n

) выражает P,

если a

1

:S M,…,a

n

:S M

P(x

,…,x

n

) M

ϕ(x

,…,x

n

),

1

1

n

1

1

и что предикат P выразим в модели M,

если существует формула, выражающая P.

Рассмотрим в

качестве примера

модель

;=;S; ,

где

– множество натуральных чисел, =

понимается

как

совпадение

элементов,

а

S(x) = x +1.

Как выразить в этой модели

предикаты

"y = x +2 ", " x = 0 "

(мы используем здесь кавычки, чтобы было ясно, что это не формулы

что всех формул сигнатуры =;S счётное число, а множество всех предикатов на множестве

имеет

мощность континуум.

Простым примером невыразимого предиката служит предикат " x = 0 " в модели

;=;; .

Действительно, интуитивно ясно, что если в сигнатуре

нет арифметических операций, то все элементы

множества

равноправны и отличить число 0 от

других чисел невозможно. Приведём строгое

доказательство

этого факта. Докажем индукцией по длине формулы сигнатуры =;; , что значение

что то же будет верно для формул

¬ϕ, (ϕ ψ),

(ϕ ψ) и (ϕ → ψ).

Если

формула ϕ

имеет

вид

ϕ(x1,…,xn ) = y ψ(y,x1,…,xn ) и она

истинна на

наборе (a1,…,an ), то

для

любого a

формула

ψ(a,a1,…,an )

истинна. По предположению

индукции ψ(a +1, a1 +1,…, an +1) истинна.

Так как

a

произвольно,

то ϕ(a1 +1,…,an +1) истинна.

Аналогично рассматривается

случай, когда ϕ

имеет

вид

этой модели формула ϕ′,

не содержащая кванторов (то есть M

x

,…, x

n

ϕ′ ↔ ϕ, где x

,…,x

n

– все

1

1

свободные переменные ϕ′

и ϕ). В этом случае мы будем говорить,

что

M допускает элиминацию

кванторов.

Используем

следующее

сокращение:

для

всякого

терма t

и

натурального

числа

n

Sn (t) = S(…(S(t))…),

где

S

повторяется

n раз. Мы будем

пользоваться тем, что в

,=,S, 0

t = s ≡ S(t) = S(s).

Индукция по количеству кванторов в формуле. От квантора

в любой формуле можно избавиться,

заменив формулу x τ

на эквивалентную ей формулу ¬ x ¬τ.

Бескванторную формулу всегда можно

привести к ДНФ. Наконец, формула x τ1 … τl

эквивалентна ( x τ1 ) … ( x τl ). Таким образом, нам

достаточно доказать, что существует эквивалентная бескванторная формула для формулы ϕ(x1,…,xk )

вида

x σ(x,x1,…,xk ), где σ = σ1 … σl

– элементарная конъюнкция атомарных формул и их отрицаний.

Атомарные формулы, содержащие переменную x, имеют один из двух видов:

Sn (x) = Sm (x),

или

Sn (x) = Sm (v), где v = x

j

или v = 0.

Всякая формула первого вида либо тождественно истинна (если n = m),

либо тождественно ложна,

поэтому её можно заменить на эквивалентную формулу, не содержащую x :

0 = 0 или . Таким образом,

можно считать, что все σi

– формулы второго вида или их отрицания.

Если все σi

– отрицания, то x σ тождественно истинна и эквивалентна 0 = 0. Последний случай для

простоты понимания разберём на примере

x S 5 (x) = S 3 (x

2

) ¬x = x

5

S 3 (x) = S2 (x

) ¬S1(x) = S

3 (x

3

) ≡

1

x S2 (x) = x

2

S(x) = x

1

¬S(x) = S

3 (x

3

) ¬S(x)

= S(x

5

) ≡

x S(x)

= x

1

S

2 (x) = x

2

¬S(x) = S

3 (x

3

) ¬S(x)

= S(x

5

) ≡

x S(x)

= x

1

S

(x

) = x

2

¬x

1

= S 3 (x

3

) ¬x

1

= S(x

5

) ≡

1

понимаются

в

обычном смысле. Выразить в модели

;=;+,

следующие предикаты:

" x ≤ y ",

"y = x +1",

" x

делится на y ", “остаток от деления x на y

равен z ",

" x – степень числа 2”.

Решение. Понятно, что x ≤ y

в том и только в том случае, если y представимо в виде y = x +z при

некотором

z

.

Следовательно,

" x ≤ y " z y = x +z. Предикат

"y = x +1" можно

записать

многими способами, например: z y = x +z ( u u = zu). Далее, x

делится на y, если и только если x

представим в виде yz, т.е. x y z x = yz. Предпоследний предикат (обозначим его P(x,y,z))

говорит о

том, что x = yt +z

при некотором t, причём 0 ≤ z < x.

В свою очередь,

z < x означает, что z ≠ x и

x = z +u при некотором u. Таким образом,

P(x,y,z) ( t x = yt +z) ¬z = x ( u x = z +u).

Наконец, степень двойки характеризуется тем, что все её делители, кроме 1, – целые числа. Значит,

" x – степень 2" y z x = yz → y = 1 ( u y = u +u).

5. Доказать, что в модели

, =, < предикат " x = 1"

невыразим.

Доказательство. Рассмотрим

автоморфизм ϕ(x) = 2x

данной

модели. Так как предикаты = и <

инвариантны относительно этого автоморфизма, а предикат

" x = 1"

не инвариантен (он превращается в

ситуация

"y = x +1" неотличима от ситуации "y = x +2 ", так как

в обеих ситуациях значения

истинности атомарных формул одни и те же. Значит,

y = x +1 в том

и только в том случае, когда

y = x +2,

но это неверно. Значит, предикат "y = x +1"

невыразим с помощью бескванторной формулы, и

xy =

(x +y)2 −(x −y)2

, то

4

xy = z (x +y)2 −(x −y)2 = 4z

u v p q (u = x +y x = y +v P(u, p) P(v,q)

p = q +z +z +z +z).

5. Указать автоморфизм модели ,=,<, 0,1 , доказывающий невыразимость предиката “ x =

1

”.

2

Ответ: P(x1,…,xn

) ≡ xi = xj

… xi

= xj ( l :1…k il , jl

1…n).

1

1

k

k

3.8. Ультрапроизведение моделей. Теорема Лося

3.8.1. Ультрафильтры

Напомним, что P(X)

– множество всех подмножеств множества X.

Фильтром на множестве X называется любое F P(X),

обладающее свойствами:

(1)

F; (2) A: F B : P(X) A B B F;

(3)

A,B : F A ∩B F.

Примеры фильтров:

Тогда

–

фильтр. Он называется

фильтром,

1.

Пусть A X,A ≠ .

F(A) = {B : P(X) | A B}

порождённым множеством A.

главным

2.

Пусть a X.

Тогда

F(a) = F({a}) = {B : P(X) | a B}

–

фильтр.

Он

называется

фильтром, порождённым элементом a.

3.

Пусть |X | ≥ 0 . Тогда F = {A: P(X) ||X \ A| < 0 } – фильтр.

S P(X) называется центрированной системой

подмножеств

X,

если

пересечение

любого

конечного числа множеств из S непусто, т.е. A1,…,An

S ∩n

Ai

≠ .

i=1

Теорема 1. Для всякой центрированной системы S над X существует фильтр F S над X.

Доказательство.

Пусть

S

–

центрированная

система

подмножеств

X.

Обозначим

F= {B : P(X) | A1,…,An :S ∩n

Ai B}. Проверим, что F

–

фильтр.

По определению центрированной

i=1

системы B ≠

при

всех B F. Значит,

F.

Пусть

B F

и B C. Так

как

∩n

Ai B при

i=1

некоторых A1,…,An S,

то

∩n

Ai C

и

C F.

Наконец,

пусть

B,C F.

Тогда

при

некоторых

i=1

B1,…,Bk ,C1,…,Cl

S ∩k

Bi B и ∩l

Ci C. Следовательно, ∩k

Bi

∩ ∩l

Ci B ∩C а значит,

B ∩C F.

i=1

i=1

i=1

i=1

Фильтр U

на множестве

X,

максимальный

по

включению

(т.е. для

любого фильтра F

цепь, то есть F1, F2 :Φ (F1 F2

F1

F2 ). Положим F = Φ, то есть

F = F. Тогда

F

– тоже

FΦ

фильтр. В самом деле, Так как

F :Φ F, то

F .

Далее, пусть

A F и A B.

Из

A F

следует F :Φ A F и так как

F

–

фильтр, то

B F

и

B F .

Наконец,

пусть A,B F . Тогда

F1 :Φ A F1 F2 :Φ B F2 .

Либо

F1

F2, либо F2 F1.

Пусть,

например,

F1 F2 (второй случай

аналогичен). Тогда A,B F ,

A ∩B F . Отсюда получаем A ∩B F .

Итак,

F – фильтр, который,

2

2

очевидно, является верхней гранью Φ. По лемме Цорна в множестве P есть максимальный элемент U. Это

и будет ультрафильтр, содержащий фильтр F.

Теорема 3. Фильтр U на множестве X является ультрафильтром в том и только том случае, если для

любого A X A U X \ A U.

Доказательство. Необходимость. Пусть U – ультрафильтр и A X таково, что A U и X \ A U.

Рассмотрим следующую совокупность подмножеств X :

S = {A ∩B | B U}. Докажем,

что S –

центрированная система. Рассмотрим любые A ∩B1,…,A ∩Bn

S (где B1,…,Bn U). Так как U – фильтр,

значит,

X \ A U. Противоречие. Таким образом, S – центрированная система. По теореме 1 существует

фильтр F, содержащий S. Пусть B U. Тогда A ∩B S, поэтому A ∩B F, а значит, B A ∩B F.

Итак, U F и U = F Крометого, A A ∩B F = U. Мы получили противоречие.

Достаточность. Пусть F – фильтр со свойством A X A U X \ A U и F′ – такой фильтр,

что F′

F. Пусть A F′ \ F. Так как A F, то X \ A F, а значит, X \ A F′. Так как A F′ и

X \ A F′, то A ∩(X \ A) F′, т.е. F′, а это противоречит тому факту, что F′

– фильтр. Значит,

F′, удовлетворяющего таким условиям, не существует и F – ультрафильтр.

Тривиальным примером ультрафильтра является главный фильтр F(a), где a

– фиксированный

Пусть {Mi | i I}

– совокупность моделей одной и той же сигнатуры Ω. Рассмотрим вначале прямое

произведение моделей Mi . Обозначается оно ∏Mi , а определяется как множество наборов (ai )i I

(если I

i I

ясно из контекста, можем писать просто (ai )),

где ai Mi

для всех i I. (Если, например,

I = {1,2, 3}, то

∏Mi

– это множество троек

{(a1,a2,a3 ) | a1 : M1,a2 : M2,a3 : M3 }).

На множестве

∏Mi

легко ввести

i I

i I

операции и предикаты из Ω, а именно: если f

Φ – символ п-арной операции, то положим

f ((a1 ),(a2 ),…,(an )) = (f (a1,a

2,…,an )),

i

i

i

i

i

i

т.е. определим операции покомпонентно.

т-арного

Если

P Π

–

символ

отношения,

можно