Дрозд Ю. Основи математичної логіки (на укр. языке)
Подождите немного. Документ загружается.
n n
A(n) A(n)
n
M ⊆ N
n
A (x
1
, x
2
, . . . , x
n
)
(a
1
, a
2
, . . . , a
n
) ∈ M A ` A (a
1
, a
2
, . . . , a
n
)
A
M
M ⊆ N
n
A A
0
(a
1
, a
2
, . . . , a
n
) ∈ M
A ` A (a
1
, a
2
, . . . , a
n
) (a
1
, a
2
, . . . , a
n
) /∈ M
A ` A
0
(a
1
, a
2
, . . . , a
n
)
f : N
n
→ N
Γ(f) =
a
1
, a
2
, . . . , a
n
, f (a
1
, a
2
, . . . , a
n
)
,
N
n+1
f
A M ⊆ N
n
A
0
M
0
n a = (a
1
, a
2
, . . . , a
n
) a ∈ M A `
A (a
1
, a
2
, . . . , a
n
) a ∈ M
0
A ` A
0
(a
1
, a
2
, . . . , a
n
)
T
1
, T
2
, . . . , T
m
, . . .
A (a
1
, a
2
, . . . , a
n
) A
0
(a
1
, a
2
, . . . , a
n
)
A(x, y) = A(x
1
, x
2
, . . . , x
n
, y) f
f (a
1
, a
2
, . . . , a
n
)
A(a
1
, a
2
, . . . , a
n
, b) b
f (a
1
, a
2
, . . . , a
n
) = b
f N
n
a ∈ M A(a) a /∈ M
A(a)
a ∈ M
M → N M N
n
χ
M
M ⊆ N
n
χ
M
(a
1
, a
2
, . . . , a
n
) =
(
0 (a
1
, a
2
, . . . , a
n
) ∈ M,
1 (a
1
, a
2
, . . . , a
n
) /∈ M.
1 0
M ⊆ N
n
χ
M
M χ
M
A M A
0
• χ
M
(a) = b
A ` (A(a) ∧ b = 1) ∨ (A
0
(a) ∧ b = 0);
• χ
M
(a) 6= b
A ` (A
0
(a) ∧ b = 1) ∨ (A(a) ∧ b = 0) ∨ b > 1.
χ
M
B
a ∈ M A ` B(a, 0),
a /∈ M A ` B(a, 1)
A(x)
M ⊆ N
n
M
¬A M
a ∈ M A ` A(a),
a /∈ M A ` ¬A(a).
M
A(x, y)
f : N
m
→ N f(a) = b A ` A(a, b) ∧
A(a, y) ⇒ y = b
N
n
A(x)
f(x)
b = f(a) A ` A(a, b);
b 6= f(a) A ` ¬A(a, b).
Γ(f)
b = f(a) A ` A(a, b)
b 6= f(a) f(a) = c A ` b 6= c A(a, b) ⇒ b 6=
c A ` A(a, y) ⇒ y = c A ` A(a, b) ⇒ b = c
(X ⇒ Y ) ⇒ ((X ⇒ ¬Y ) ⇒ ¬X A ` ¬A(a, b)
A ` A(a, b) A ¬A(a, b)
f(a) 6= b b = f(a) A `
¬A(a, b) b 6= f(a)
A
M ⊆ N
n
B A(a) ⇒
A
B(a) a = (a
1
, a
2
, . . . , a
n
)
B M
A(a) ≡
A
B(a) a
A `
∀x(A ⇒ B)
ω
f (x
1
, x
2
, . . . , x
m
) = c
y = c
M = {a
1
, a
2
, . . . , a
k
}
a
i
= (a
i
1
, a
i
2
, . . . , a
i
m
)
x
1
= a
11
∧ x
2
= a
12
∧ . . . ∧ x
m
= a
1m
∨
∨
x
1
= a
21
∧ x
2
= a
22
∧ . . . ∧ x
m
= a
2m
∨
∨ ··· ∨
x
1
= a
k1
∧ x
2
= a
k2
∧ . . . ∧ x
m
= a
km
.
F (x
1
, x
2
,
. . . , x
m
)
F (x
1
, x
2
, . . . , x
m
) = y
F F F
p
m
k
: N
m
→ N p
m
k
(x
1
, x
2
, . . . , x
m
) = x
k
y = x
k
res(x, y) [x/y]
f : N
m
→ N
F(x
1
, x
2
, . . . , x
m
, y) g
i
: N
n
→ N
G
i
(x
1
, x
2
, . . . , x
n
, y) i = 1, 2, . . . , m)
h = f (g
1
, g
2
, . . . , g
m
) : N
n
→ N
h (x
1
, x
2
, . . . , x
n
) =
= f
g
1
(x
1
, x
2
, . . . , x
n
) , g
2
(x
1
, x
2
, . . . , x
n
) , . . . , g
m
(x
1
, x
2
, . . . , x
n
)
,
H(x
1
, x
2
, . . . , x
n
, y) = ∃z
1
∃z
2
. . . ∃z
m
G(x
1
, x
2
, . . . , x
n
, z
1
)∧
G(x
1
, x
2
, . . . , x
n
, z
2
) ∧ . . . ∧ G(x
1
, x
2
, . . . , x
n
, z
m
) ∧ F(z
1
, z
2
, . . . , z
m
, y).
b = h (x
1
, x
2
, . . . , x
n
) c
i
= g
i
(x
1
, x
2
, . . . , x
n
)
b = f (c
1
, c
2
, . . . , c
m
)
A `F(c
1
, c
2
, . . . , c
m
, b) ∧
F(c
1
, c
2
, . . . , c
m
, y) ⇒ y = b
;
A `G
i
(a
1
, a
2
, . . . , a
n
, c
i
) ∧
F(a
1
, a
2
, . . . , a
n
, z
i
) ⇒ z
i
= c
i
i = 1, 2, . . . , m
H(a
1
, a
2
, . . . , a
n
, b) H(a
1
, a
2
, . . . , a
n
, y)
c
0
1
, c
0
2
, . . . , c
0
m
G
i
(a
1
, a
2
, . . . , a
n
, c
0
i
)
i F(c
0
1
, c
0
2
, . . . , c
0
m
, y)
A ` G
i
(a
1
, a
2
, . . . , a
n
, z) ⇒ z = c
i
,
c
0
i
= c
i
A ` F(c
1
, c
2
, . . . , c
m
, y) ⇒ y = b,
y = b A ` H(a
1
, a
2
, . . . , a
n
, y) ⇒ y = b
H h
M ⊆ N
n
A M ⊆
N
n
B
N ⊆ N
n
A ∨ B
M ∪N A ∧ B
M ∩ N
β(x, y, z) = res(x, y(z + 1) + 1).
B(x, y, z, t)
c
0
, c
1
, . . . , c
n
a, b β(a, b, k) = c
k
k = 0, 1, . . . , n
b n!
c
k
n!(m + 1) m = max[c
k
/n!]
d
k
= b(k+1)+1
1 d
k
d
l
k 6= l d
k
−d
l
= b(k−l)
b 1 b d
k
k −l 0 < |k −l| 6 n n! b
a a ≡ c
k
(mod d
k
) k = 0, 1, . . . , n c
k
< d
k
c
k
= res(a, d
k
) = β(a, b, k)
d
1
, d
2
, . . . , d
n
c
1
, c
2
, . . . , c
n
a a ≡ c
k
(mod d
k
) k = 1, 2, . . . , n
n = 2
b
1
, b
2
b
1
c
1
+ b
2
c
2
= 1 n
g : N
n
→ N h : N
n+2
→ N
f : N
n
→ N
g h a
1
, a
2
, . . . , a
n
f(a
1
, a
2
, . . . , a
n
, 0) = g (a
1
, a
2
, . . . , a
n
)
b
f(a
1
, a
2
, . . . , a
n
, b + 1) = h(a
1
, a
2
, . . . , a
n
, b, g(a
1
, a
2
, . . . , a
n
, b)).
f = Rec(g, h) g
h f
g : N
n+1
→ N
a
1
, a
2
, . . . , a
n
b g(a
1
, a
2
, . . . , a
n
, b) = 0
f : N
n
→ N µ
g a
1
, a
2
, . . . , a
n
f (a
1
, a
2
, . . . , a
n
) = min {b | g(a
1
, a
2
, . . . , a
n
, b) = 0 }.
f (x
1
, x
2
, . . . , x
n
) = µ
y
g(x
1
, x
2
, . . . , x
n
, y).
f y
f
f = µ
y
g g : N
n+1
→ N
G(x
1
, x
2
, . . . , x
n
, y, z) f (a, b) = 0
A ` G(a, b, 0) ∧ (G(a, b, z) ⇒ z = 0) f
F(x, y) = G(x, y, 0) ∧ ∀z
z < y ⇒ ¬G(x, z, 0)
.
f(a) = b A ` G(a, b, 0) ∧ (G(a, b, z) ⇒ z = 0)
b = 0 A ` ¬z < 0 A ` F(x, 0) A ` y 6=
0 ⇒ 0 < y A ` G(x, 0, 0) A ` y 6= 0 ⇒ ¬F(a, y)
A ` F(a, 0) ∧ (F(a, y) ⇒ y = 0)
b > 0 k < b f(a, k) 6= 0
A ` ¬G(a, k, 0) y < b ≡
A
y = 0 ∨ y = 1 ∨ y = b − 1
A ` y < b ⇒ ¬G(x, y, 0) A ` F(a, b) A ` y 6= b ⇒
y < b ∨ y < b G(a, b, 0) A ` b < y ⇒ ¬F(a, y)
A ` y 6= b ⇒ ¬F(a, y) A ` F(a, y) ⇒ y = b
f = Rec(g, h) g h
G(x, y) H(x, y, z, t) f
F(x, y, z) =
y = 0 ⇒ G(x, z)
∧
∧ ∃u∃v∀t∃w
(t = 0 ⇒ G(x, w)) ∧
t < y ⇒ ∃w
0
B(u, v, t, w)∧
∧ B(u, v, t + 1, w
0
) ∧ H(x, t, w, w
0
)
∧ B(u, v, y, z)
,
B(x, y, z, t) β(x, y, z)
c = f(a, b) b = 0 c = g(a) A ` G(a, c) ∧
(G(a, z) ⇒ z = 0) A ` F(a, 0, c) F(a, 0, z)
G(a, z) z = c A ` F(a, 0, z) ⇒ z = c
b 6= 0 c
m
= f(a, m) m = 1, 2, . . . , b
c
b
= c k, l β(k, l, m) = f(a, m)
m 6 b A ` B(k, l, m, c
m
) ∧ (B(k, l, m, w) ⇒ w = c
m
)
A ` G(a, c
0
) ∧ (G(a, w) ⇒ w = 0) m < b
c
m+1
= h(a, m, c
m
) A ` H(a, m, c
m
, c
m+1
) ∧ (H(a, m, c
m
, w) ⇒ w =
c
m+1
)
A ` ∀t∃w
(t = 0 ⇒ G(a, w)) ∧
t < b ⇒ ∃w
0
B(k, l, t, w)∧
∧ B(k, l, t + 1, w
0
) ∧ H(a, t, w, w
0
)
∧ B(k, l, b, c)
,
A ` F(a, b, c)
F(a, b, z) b 6= 0
∃u∃v∀t∃w
(t = 0 ⇒ G(a, w)) ∧
t < b ⇒ ∃w
0
B(u, v, t, w)∧
∧ B(u, v, t + 1, w
0
) ∧ H(a, t, w, w
0
)
∧ B(u, v, b, z)
.
d, d
0
∀t∃w
(t = 0 ⇒ G(a, w)) ∧
t < b ⇒ ∃w
0
B(d, d
0
, t, w)∧
∧ B(d, d
0
, t + 1, w
0
) ∧ H(a, t, w, w
0
)
∧ B(d, d
0
, b, z)
.
b
0
< b
∃w∃w
0
(b
0
= 0 ⇒ G(a, w)) ∧ B(d, d
0
, b
0
, w) ∧ B(d, d
0
, b
0
+ 1, w
0
)∧
∧ H(a, b
0
, w, w
0
)
.
e, e
0
(b
0
= 0 ⇒ G(a, e)) ∧ B(d, d
0
, b
0
, e) ∧ B(d, d
0
, b
0
+ 1, e
0
) ∧ H(a, b
0
, e, e
0
).
b
0
e(b
0
) e
0
(b
0
)
G f G(a, e(0))
e(0) = c
0
B(d, d
0
, b
0
+ 1, e
0
(b
0
)) B(d, d
0
, b
0
+
1, e(b
0
+ 1)) e
0
(b
0
) = e(b
0
+ 1) = β(d, d
0
, b
0
+ 1)
H(a, b
0
, e(b), e
0
(b
0
)) e
0
(b
0
) = h(a, b
0
, e(b
0
))
b
0
= 0 e
0
(0) = e(1) = h(a, 0, c
0
) = c
1
e
0
(1) = e(2) = h(a, 1, c
1
) =
c
2
. . . , e
0
(b−1) = h(a, b−1, c
b−1
) = c
b
= c B(d, d
0
, b, z)
β(d, d
0
, b) = c z = c A ` F(a, b, z) ⇒ z = c
F f
O(x) 0 S(x) = x + 1
f : N
n
→ N
O, S p
n
k
(k 6 n, n, k ∈
N)
f : N
n
→ N
O, S p
n
k
(k 6 n, n, k ∈ N)
M ⊆ N
n
M ⊆ N
n
χ
M
M (x
1
, x
2
, . . . , x
n
) χ
M
(x
1
, x
2
, . . . , x
n
)
(a
1
, a
2
, . . . , a
n
) ∈ M M (a
1
, a
2
, . . . , a
n
) = 0
(a
1
, a
2
, . . . , a
n
) /∈ M M (a
1
, a
2
, . . . , a
n
) = 1
f (x
1
, x
2
, . . . , x
n
)
f(x
k
1
, x
k
2
, . . . , x
k
n
)
k
i
∈ {1, 2, . . . , n }
f(p
n
k
1
, . . . , p
n
k
n
)
x + y xy
x + 0 = x = p
1
1
(x),
x + (y + 1) = (x + y) + 1 = S(x + y);
x · 0 = 0 = O(x),
x(y + 1) = xy + x.
S
∗
(x) =
(
0 x = 0,
x − 1 x 6= 0;
x −
.
y =
(
0 x 6 y,
x − y x > y;
|x − y|;
sg(x) =
(
0 x = 0,
1 x 6= 0;
res(x, y);
[x/y].
S
∗
(0) = 0, S
∗
(x + 1) = x
x −
.
0 = x, x −
.
(y + 1) = S
∗
(x −
.
y)
|x − y| = (x −
.
y) + (y −
.
x)
sg(0) = 0, sg(x + 1) = 1
res(0, y) = 0, res(x + 1, y) = S(res(x, y)) · sg(|y − S(res(x, y))|)
y 6= 0 res(x, y) + 1 < y res(x + 1, y) =
res(x, y) + 1 res(x, y) + 1 = y res(x + 1, y) = 0
res(x + 1, y) y = 0
[0/y] = 0, [(x + 1)/y] = [x/y] + (1 −
.
sg(|y −S(res(x, y)|)
sg(x) = 1 −
.
sg(x) =
(
1 x = 0,
0 x 6= 0.
x!, x
y
, [
x
√
y], min(x, y), max(x, y),
min (x
1
, x
2
, . . . , x
n
) , max (x
1
, x
2
, . . . , x
n
) .
[
x
√
y] x 6= 0
z z
x
6 y [
0
√
y] = 0
y
f(x
1
, x
2
, . . . , x
n
, y)
Q
z6y
f(x
1
, x
2
, . . . , x
n
, z) =
Q
y
k=0
f(x
1
, x
2
, . . . , x
n
, k);
P
z6y
f(x
1
, x
2
, . . . , x
n
, z) =
P
y
k=0
f(x
1
, x
2
, . . . , x
n
, k);
µ
z<y
f(x
1
, x
2
, . . . , x
n
, z) =
=
(
y, f(x, k) 6= 0 k < y,
min {k | f (x, k) = 0 } .
6
<