Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
\
{{0}, {0, 1}, {0, 1, 2}} = {0}.
A B A∩B = ∅ A B
A B
A \B A
B {0, 1, 2} \ {2, 3, 4} = {0, 1}.
R
R A A
R \A A = R \A
R
P
A A =
S
R
B, C ∈ R
B, C ∈ R
B = C B ∩C = ∅
R = {{0, 1}, {2}, {3, 4, 5}} A = {0, 1, 2, 3, 4, 5} R
A
a b
a b {{a, b}, {a}} (a, b)
(a
0
, b
0
) = (a
1
, b
1
)
a
0
= a
1
b
0
= b
1
(a
0
, b
0
) = (a
1
, b
1
)
{{a
0
, b
0
}, {a
0
}} = {{a
1
, b
1
}, {a
1
}}.
a
0
= b
0
{{a
0
}}
{a
1
, b
1
} = {a
1
}
a
1
= b
1
{{a
0
}} = {{a
1
}},
{a
0
} = {a
1
} a
0
= a
1
b
0
= a
0
=
a
1
= b
1
a
0
6= b
0
a
0
= a
1
b
0
= b
1
¤
(a, b)
n
n n = 2, 3, 4, . . .
(a
1
, a
2
, . . . , a
n
, a
n+1
) = ((a
1
, a
2
, . . . , a
n
), a
n+1
).
n
n (a
1
, a
2
, . . . , a
n
) (b
1
, b
2
, . . . , b
n
)
a
1
= b
1
a
2
= b
2
a
n
= b
n
A B
A B
A × B = {(a, b) | a ∈ A b ∈ B}.
A = {0, 1} B = {1, 2}
A × B = {(0, 1), (0, 2), (1, 1), (1, 2)}.
n n > 2
A
1
× A
2
× . . . × A
n+1
= (A
1
× A
2
× . . . × A
n
) × A
n+1
.
A
1
× A
2
× . . . × A
n
= {(a
1
, . . . , a
n
) | a
1
∈ A
1
. . . a
n
∈ A
n
}.
A
n
A × . . . × A
| {z }
n
n > 1 A
1
= A
R ⊆ A
1
× A
2
× . . . × A
n
A
1
× A
2
× . . . × A
n
(x
1
, . . . , x
n
) ∈ R x
1
, . . . , x
n
R
R(x
1
, . . . , x
n
)
R ⊆ A
n
n
A n = 1 n = 2
n = 3
R
0
⊆ A ×B R
1
⊆ B × C R
0
R
1
R
0
◦ R
1
= {(x, z) | (x, y) ∈ R
1
(y, z) ∈ R
2
}.
R ⊆ A
2
R a ∈ A
(a, a) ∈ R
R a, b ∈
A (a, b) ∈ R (b, a) ∈ R
R a, b, c ∈
A (a, b), (b, c) ∈ R (a, c) ∈ R
R
a, b ∈ A (a, b), (b, a) ∈ R a = b
R ⊆ A
R A
a ∈ A [a]
R
= {x ∈
A | (x, a) ∈ R}
R
A
{[a]
R
| a ∈ A} A
A ¤
R ⊆ A
2
A
A a, b ∈ A
(a, b) ∈ R (b, a) ∈
R
R = {(x, y) | x, y ∈ N x 6 y}
D = {(x, y) | x, y ∈ N x y}
R ⊆ A
2
A
R
−1
= {(y, x) | (x, y) ∈ R}.
R = {(1, 2), (2, 3)} R
−1
= {(2, 1), (3, 2)}
F ⊆ A ×B
A B a ∈ A
b ∈ B (a, b) ∈ F (a, b) ∈ F b
F a b
a F (a) b = F (a)
y (x, y) ∈ F
F (x) F (x) ↓
F (x) F (x) ↑
F
dom (F ) = {a | F (a) }.
range (F ) = {F (a) | F (a) }.
dom (F ) = A F A B
A B
f A
n
A
f n A n =
1 n = 2 n = 3
range (F ) = B F B
F A B
b ∈ B a ∈ A b = F (a)
F A B
F
−1
B A
F A B
A B
F
−1
B A
F : A → B F A B
F : A 99K B F
A B
F : A 99K B G : B 99K C
F ◦G
F ◦ G A C
f
x ∈ A B
x
S
x∈A
B
x
S
{B
x
| x ∈ A}
A = {a
0
, a
1
, . . . , a
n
}
A A
Λ
A a abba Λ
{a, b}
{ } A
∗
A A
+
A A
+
= A
∗
\ {Λ}
α |α| |Λ| = 0
L ⊆ A
∗
A
v w
(A
∗
)
2
A
∗
v w v w
vw v ◦w
•
Λ ◦ v = v ◦Λ = v
• u v w
u(vw) = (uv)w
L
0
L
1
L
0
L
1
= {uv | u ∈ L
0
, v ∈ L
1
}.
β α
γ
0
γ
1
α = γ
0
βγ
1
β α hγ
0
, β, γ
1
i
β α hγ
0
, β, γ
1
i
γ
0
Λ ◦ ◦ ◦ ◦
w
0
= Λ;
w
n+1
= w
n
w,
w
n
= w . . . w
| {z }
n
L
∗
= {w|w = w
1
w
2
. . . w
n
, n = 0, 1, 2, . . .
w
1
, . . . , w
n
∈ L}.
L Λ ∈ L
∗
L ⊆ A
∗
A
∗
A
∗
\ L
a b
a = b = 0
0
a b 0
0
r
0
= a r
1
= b
r
0
r
1
r
0
= r
1
q
1
+ r
2
, 0 6 r
2
< r
1
r
1
= r
2
q
2
+ r
3
, 0 6 r
3
< r
2
r
2
= r
3
q
3
+ r
4
, 0 6 r
4
< r
3
. . .
r
i+1
= 0
r
1
> r
2
> r
3
> . . .
r
i
a b
r
j
= r
j+1
q
j+1
+r
j+2
r
j
r
j+1
r
j+1
r
j+2
j (r
j
, r
j+1
) (r
j+1
, r
j+2
)
(a, b) (r
1
, r
2
) (r
2
, r
3
)
(r
i
, 0) (r
i
, 0) = r
i
(a, b) = r
i
