Дрозд Ю. Основи математичної логіки (на укр. языке)
Подождите немного. Документ загружается.
T
A T ` A T ` ¬A
A T
T ∪ {¬A }
A A
T |= A T ∪ {¬A }
T ` A
T
T
∗
T
∗
T
T c
A
x T ∪ {∃xA ⇒ A
x
c
}
T∪{∃xA ⇒ A
x
c
}
¬(∃xA ⇒ A
x
c
) ∃xA ⇒ A
x
c
T ` (∃xA ⇒ A
x
c
) ⇒ ¬(∃xA ⇒ A
x
c
) (B ⇒ ¬B) ⇒ ¬B
T ` ¬(∃xA ⇒ A
x
c
)
y
T ` ¬(∃xA ⇒ A
x
y
)
¬(B ⇒ C) ≡ B ∧ ¬C T ` ∃xA T ` ¬A
x
y
T ` ∀y¬A
x
y
∀y¬A
x
y
≡ ∀x¬A ≡ ¬∃xA
T ` ¬∃xA T
T
T
A
1
, A
2
, . . . , A
n
, . . .
T
0
T
c
1
, c
2
, . . . , c
n
, . . . ∃xA
i
⇒ A
i
x
c
i
x
A
i
T
0
T
∗
T
∗
T c
i
T
∗
T
0
I T I
T T
∗
T
0
T m F
I(F ) (t
1
, t
2
, . . . , t
m
) = F (t
1
, t
2
, . . . , t
m
) ,
m P
I(P ) (t
1
, t
2
, . . . , t
m
) =
(
1, T
∗
` P (t
1
, t
2
, . . . , t
m
) ,
0, T
∗
` ¬P (t
1
, t
2
, . . . , t
m
) .
t
1
, t
2
, . . . , t
m
F (t
1
, t
2
, . . . , t
m
) P (t
1
, t
2
, . . . , t
m
)
A T φ : X → T
A
φ
= A
x
1
x
2
...x
m
t
1
t
2
...t
m
x
1
, x
2
, . . . , x
m
A
t
i
= φ(x
i
) A
φ
A T φ : X → T
val(I, φ, A) =
(
1 T
∗
` A
φ
,
0 T
∗
` ¬A
φ
.
A
A
¬B, B ∨ C, B ∧ C, B ⇒ C,
A = B ⇒ C
A
φ
= B
φ
⇒ C
φ
val(I, φ, C) = 1
val(I, φ, A) = 1 T
∗
` C
φ
C
φ
⇒
(B
φ
⇒ C
φ
) T
∗
` A
φ
val(I, φ, B) = 0 val(I, φ, A) =
1 T
∗
` ¬B
φ
¬B
φ
⇒ (B
φ
⇒ C
φ
) T
∗
` A
φ
val(I, φ, B) = 1 val(I, φ, C) = 0 val(I, φ, A
φ
) = 0
T ` B
φ
T ` ¬C
φ
B
φ
⇒ (¬C
φ
⇒
¬(B
φ
⇒ C
φ
)) T ` ¬A
φ
A = ∃xB B x, y
1
, y
2
,
. . . , y
m
B
∗
= B
y
1
,y
2
,...,y
m
t
1
,t
2
,...,t
m
t
i
= φ(y
i
) B
∗
x T
∗
∃xB
∗
⇒ B
∗
x
c
c A
φ
= ∃xB
∗
val(I, φ, A) = 1
ψ ∈ φ
x
val(I, ψ, B) = 1 T
∗
` B
ψ
B
ψ
= B
∗
x
t
t = ψ(x) B
∗
x
t
⇒ ∃xB
∗
T
∗
` A
φ
T
∗
` A
φ
T
∗
` B
∗
x
c
val(I, ψ, B) = 1
ψ ∈ φ
x
ψ(x) = c
A = ∀xB B x, y
1
, y
2
, . . . , y
m
B
∗
= B
y
1
,y
2
,...,y
m
t
1
,t
2
,...,t
m
t
i
= φ(y
i
)
x A
φ
= ∀xB
∗
val(I, φ, A) = 0
ψ ∈ φ
x
val(I, ψ, B) = 0 T
∗
` ¬B
ψ
B
ψ
= B
∗
x
t
t = ψ(x)
∀xB
∗
⇒ B
∗
x
t
(∀xB
∗
⇒ B
∗
x
t
) ⇒ (¬B
∗
x
t
⇒ ¬∀xB
∗
T
∗
` ¬A
φ
T ` ¬A
φ
T
∗
` ∃x¬B
∗
T
∗
∃x¬B
∗
⇒ B
∗
x
c
c T
∗
` B
∗
x
c
B
ψ
ψ ∈ φ
x
ψ(x) = c val(I, ψ, B) = 0 val(I, φ, A) = 0
A ∈ T
A T
∗
` A
val(I, A) = 1 I T
T
0
⊆ T T
T
R
∞
c Lnc n
SS . . . S
| {z }
n−1
ee . . . e
| {z }
n
n > 1
n n
T
0
c
T
0
I
I(c)
T
T
T
T T
c
1
, c
2
, . . . , c
n
, . . . ¬Ec
i
c
j
i < j
C
n
= ∃z(¬Ezc
1
∧ ¬Ezc
2
∧ . . . ∧ ¬Ezc
n
)
n T
∗
T
0
T
∗
¬Ec
i
c
j
C
n
n
0
max {n | C
n
∈ T
0
} max {j | ¬Ec
i
c
j
∈ T
0
i }
T I n
0
M n
0
a
1
, a
2
, . . . , a
n
0
b a
i
i = 1, 2, . . . , n
0
I c
n
I(c
n
) = a
n
n 6 n
0
I(c
n
) = b
n > n
0
¬Ec
i
c
j
(i < j 6 n
0
)
φ ψ φ
z
ψ(z) = b ¬Ezc
1
∧ ¬Ezc
2
∧ . . . ∧ ¬Ezc
n
n 6 n
0
1 val(I, C
n
) = 1
I T
0
T
∗
T
A
T
¬A
I T M N
M F
T a
1
, a
2
, . . . , a
m
∈ N m
F I(F ) (a
1
, a
2
, . . . , a
m
) ∈ N I(c) ∈ N
T
I
N
I N
I
N
(F ) (a
1
, a
2
, . . . , a
m
) = I(F ) (a
1
, a
2
, . . . , a
n
) ,
I
N
(P ) (a
1
, a
2
, . . . , a
m
) = I(P ) (a
1
, a
2
, . . . , a
m
)
F P I
N
T I
N I M
N I
val(I, φ, A) = val(I
N
, φ, A) A T
φ : X → N
I I
N
N I
I
I
N
T I
T
I M
I I M
T
N ⊆ M
N ⊆ M I
N
A ∈ T
I
T M M
0
M N I
N ⊇ M
0
M
k
⊆ M (k ∈ N), M
0
⊆ M
1
⊆
M
2
⊆ . . .
M
0
M
k
M
k+1
M
k
I(F ) (a
1
, a
2
, . . . , a
m
) F m
T a
1
, a
2
, . . . , a
m
M
k
M
k+1
I(c) c
T e(x, A, φ) A T
x φ : X → M
k
• ψ ∈ φ
x
val(I, ψ, A) = 1
e(x, A, φ) = ψ(x)
ψ(x)
A x val(I, ψ, A)
• val(I, ψ, A) = 0 ψ ∈ φ
x
e(x, A, φ) = a
0
a
0
M
0
M
k
N =
S
∞
k=0
M
k
M
k
N
F m T a
1
, a
2
, . . . , a
m
∈
N k a
1
, a
2
, . . . , a
m
∈ M
k
I(F )(a
1
, a
2
, . . . , a
m
) ∈
M
k+1
⊆ N val(I, φ, A) = val(I
N
, φ, A)
φ : X → N
A I
N
(P )
N I(P ) A = ¬B, A = B ⇒ C, A = B ∨C
A = B ∧ C
B C A = ∃xB
B x, y
1
, y
2
, . . . , y
m
k
φ(x) φ(y
i
) (i = 1, 2, . . . , m) M
k
val(I, φ, A) = 0 val(I, ψ, B) = 0 ψ ∈ φ
x
val(I
N
, ψ, B) = 0 ψ : T → N, ψ ∈ φ
x
val(I
N
, φ, A) = 0 val(I, φ, A) = 1 val(I, ψ, B) = 1
ψ ∈ φ
x
val(I, ψ, B) = 1 ψ ∈ φ
x
ψ(x) = e(x, B, φ) ∈ M
k+1
⊆ N val(I
N
, φ, A) = 1
A = ∀xB ∀xB ≡ ¬∃x¬B
M
0
M
M
0
N ⊆ M
0
M
0
R
0
R
M
M
T
I
I
∗
M I
M
∗
I
∗
M
∗
T
I
M M = {a
1
, a
2
, . . . , a
n
, . . . } T
c
1
, c
2
, . . . , c
n
, . . . I
I(c
n
) = a
n
n T
∗
I ¬Ec
i
c
j
i 6= j
a
n
T
∗
c ¬cc
n
n ∈ N T
∗
c
M ⊆ T
∗
c
M c
n
m
J M M
T
I J(c
n
) = a
n
n 6 m J(c) = a
m+1
T
∗
c
I
∗
M
∗
T
∗
c
b
n
= I
∗
(c
n
) b = I
∗
(c) N = {b
1
, b
2
, . . . , b
n
, . . . }
b /∈ N A T φ : X → N
val(I
∗
, φ, A) = val(I
∗
, A
x
1
,x
2
,...,x
k
c
i
1
,c
i
2
,...,c
i
k
) x
1
, x
2
, . . . , x
k
A φ(x
j
) = b
j
i
ψ : X → M val(I, ψ, A) = val(I, A
x
1
,x
2
,...,x
k
c
i
1
,c
i
2
,...,c
i
k
) ψ(x
j
) = a
i
j
b
n
∈ N a
n
∈ M
I
∗
(F ) I
∗
(P )
I
∗
(c
n
) = a
n
I
∗
I
T
M M
∗
M
M
T
A ∈ T M
T
T
M
N
∗
⊃ N
N
∗
A A > n
n ∈ N
a 6 n a ∈ {1, 2, . . . , n }
R
∗
⊃ R
R
∗
A A > c c ∈ R
α 0 < α < c
c ∈ R
0 < a < n n
m k ∈ {1, 2, . . . , mn } k/m 6 a <
(k + 1)/m
b = lim
m→∞
k/m
a 6= b |a −b|
C
A T
A
1
, A
2
, . . . , A
n
= A i
A
i
A
i
∈ T
j < i A
j
= ∃xB A
i
= B
x
c
x
c
T A A
k
k < i
A
i
A
i
T = T
1
∪ T
2
A
i
T
2
A
i
1
, A
i
2
, . . . , A
i
k
A
i
T
1
B
1
, B
2
, . . . , B
n
T
2
T
2
T
2
∃xB
∀x(A ⇒ B) ∃xA
∃xA, A
x
c
, ∀x(A ⇒ B), A
x
c
⇒ B
x
c
,
B
x
c
, B
x
c
⇒ ∃xB, ∃xB.
` ∀x(A ⇒
B) ⇒ (∃xA ⇒ ∃xB)
∀x∃yA, ∃yA, A
y
c
, ∀xA
y
c
,
∀xA
y
c
⇒ ∃y∀xA, ∃y∀xA.
x