3 1 5 1.1........................... 5 1.1.1...................... 5 1.1.2........................ 6 1.1.3........................ 6 1.1.4....................... 6 1.1.5.......................... 7 1.1.6.......................... 7 1.1.7....................... 7 1.1.8.......................... 8 1.1.9.......................... 8 1.1.10................ 9 1.2......................... 9 1.2.1............................ 10 1.2.2............................ 11 1.3............................... 11 1.4...................... 16 1.5................................ 18 2 21 2.1............................ 21 2.2......................... 22 2.3........................... 23 2.4........................... 25 2.5............................... 27 2.5.1................... 27 2.5.2.......................... 28

5 1 1.1 A = {X : X / X} A A A / A A A: A A / A A / A: A A / A A A x, y,... X, Y x y x y x (,,,,,,, =) 1.1.1 x(x = x). x = x

6 1 1.1.2 z(z x z y) x = y. x, y x y x y 1.1.3 φ y z(z y (z x φ(z))). x φ y y {z x : φ(z)} {z x : φ(z)} φ z y 1. {z : φ(z)} z x 2. {z x : φ(z)} y(y {z x : φ(z)} y w) y((y x φ(y)) y w) 1.1.4 z(x z y z). x y z 3. z w(w z w = x w = y) x, y z z w = x w = y x, y z z {x, y} x = y {x}

1.1. 7 4. z {x, y} z = x z = y 1.1.5 y z w ( (z w w x) z y ). x x z y x z x 5. z x z = y w((z w w x) z = y) 6. {x, y} x y 1.1.6 φ y x!zφ(y, z) w( y x z wφ(y, z)). y x(... ) y(y x... )!zψ(z) zψ(z) z z (ψ(z) ψ(z ) z = z ) ψ x y φ(y, z) z f : y z f x 1.1.7 y z(z x z y). z x w(w z w x) z x x x y y z(z x z y) y P(x)

8 1 1.1.8 1. : x {y x : y y} x = y(y / x) x y(y x) 2. x y x {z y : w x(z w)} y x x z x {a, b} a b x F (x ) x F y F (x y x y = ) C x F!y(y x C). F F x C 1.1.9 x x {x} S(x) S( ) = { }, S 2 ( ) = S(S( )) = {, { }} S successor x( x y(y x S(y) x)). x 0 y x y S(y) x x, S( ), S 2 ( ), S 3 ( ),... ω {, S( ), S 2 ( ), S 3 ( ),... }

1.2. 9... 1 ω x y(y x S(y) x) x X ω = {y X : x(φ(x) y x)} φ(x) x y(y x S(y) x) ω φ(x) X 7. V (0) =, V (n + 1) = P(V n ) M = n N V (n) (M, ) 1.1.10 x y(y x z(z x z y)). x z x 8. a a a a x = {a} a x a a 9. a b a a, b 1.2 1 ω = {S n ( ) : n N}... N

10 1 1.2.1 x, y x, y {x, y} x, y x, y = a, b x = a y = b (1.1) x, y x, y = {{x}, {x, y}}. x, y 10. (1.1). {{x}, {x, y}} = {{a}, {a, b}} Case 1. x = y {{x}} 1 a = b {{a}} x = a 4 x, y, a, b Case 2. x y 2 2 a b {x} = {a}, {x, y} = {a, b} x = a x y, a b y = b A, B A B 11. 1. A B = { a, b : a A, b B}. 2. A 2 = A A. 3. R A B R A B 2 2 n A n n R A B 2 12. a A, b B a, b P(P(A B)) A B A B = { x P(P(A B)) : a A b B(x = a, b ) }

1.3. 11 1.2.2 f : A B { a, b A B : b = f(a)} 13. F A B x A! y B( x, y F ) F : A B F, A, B 14. F : A B, G : B C G F 15. G F = { a, c : b B( a, b F b, c G)}. 1. G F = { x A C : a A b B c C ( x = a, c a, b F b, c G )} 2. G F 16. F : A B, G : B C, H : C D H (G F ) = (H G) F 17. 2 1.3 2 X, Y X Y X/ X 2

12 1 18. 1. x (T rans(x)) y z(z y x z x) 2. x Ord(x) T rans(x) y x(t rans(y)) x x x x 19. 1. 0 2. S( ) = { } 3. T rans(a) T rans(s(a)) T rans(a) x y S(a) (i) x y a T rans(a) x a S(a) (ii) x y = a x a S(a) x S(a) S(a) 4. Ord(a) Ord(S(a)) n S n (a) S n (0) n n 5. F F y x F F x α F α α y α y F T rans(f ) F F 20. ω ω = {x ω : Ord(x)} 0 S ω ω = ω ω ω = {x ω : x ω} ω = ω ω ω 21.. Ord(x) y x Ord(x) y z y x z x x z Ord(y) On = {x : Ord(x)} ( ) On

1.3. 13 22. On On Ord(On) On On α, β,... αφ(α) x(ord(x) φ(x)) 23. αφ(α) β ( φ(β) y β φ(y) ). φ(α) A = {x α : φ(x)} A x β α β y β A y α φ(y) φ(α) α 24. 23 ψ = φ β ( y βψ(y) ψ(β) ) αψ(α). 23 25. α β(α β α = β β α). α, β 23 α, β α α β β α y β α α y β α β α β α = y y α β α β α γ α β α γ β (i) β γ β α (ii) β = γ (iii) γ β γ α β α α α On

14 1 26. α. α 25 X α φ(x) := (x X) 23 X a X a X 27. α 3 28. 1. α α = S(β) β 2. α 29. α β α S(β) α S(β) (i) S(β) = α, (ii) α S(β), (iii) S(β) α α (i) (ii) α β α = β (iii) 30. (X, <) α f : (X, < ) (α, ) α f. α f : (X, <) (α, ) f : (X, <) (α, ) f(a) f (a) a X a a f(a) = min{β : x < a(f(x) < β)} = min{β : x < a(f (x) < β)} = f (a) α f : (X, <) (α, ) (X, <) a I a : I a = {x X : x < a}. X I a I a X X a X = I a {a} f : (I a, <) = (α, ) α f f(a) = S(α) f f X S(α) X X X = {I a : a X} X (I a, <) α a f a : I a α a 3 I α y x I y I (X, <) I X y < x I y I

1.3. 15 I a f a a < b f a f b {fa : a X} : X {α a : a X} α {α a : a α} 31 ( ). A A. g g : P(A) { } A, g(x) X. φ(α) ( f f : α 1 1 A x α ( A {f(y) : y x} f(x) = g(a {f(y) : y x}) )). A. φ(α) f f 1 f 2 φ f f 1 (x) f 2 (x) x α f 1 (x) = g(a {f(y) : y x}) = f 2 (x) α f f α α < β φ f α f β B. α φ(α). αφ(α) α f α F α F α P(A) G : {F α : α On} On, G(F α ) = α G On φ(α) α α φ α α = S(β ) f = f β β A f (β ) = g(a {f(y) : y β }) f f φ(α ) α 32. A α f : α A A < a < b f 1 (a) f 1 (b)

16 1 1.4 < 0 S(α) α + 1 x(δ(x)!yφ(x, y) x y G G δ G(x) = y δ(x) φ(x, y) G A G A = {(a, b) : a A G(a) = b} 33. G On F F (α) = G(F α). 31 ψ(x, y) f Y (f : S(x) Y f(x) = y z S(x)(f(z) = G(f z))) α!yψ(α, y) ψ F A. α!y ψ(x, y). yψ(α, y) y f α f f α y α α f = β<α f β α f f (α) = G({f (β) : β α}) ψ(α) F ψ F S(α) = f α F (α) = f α (α) = G(f α α) = G(F α) G F 34 ( ). 1. (a) α + 0 = α, (b) α + S(β 0 ) = S(α + β 0 ), (c) α + β = sup{α + γ : γ < β} = {α + γ : γ < β} β. 2. (a) α 0 = 0,

1.4. 17 (b) α S(β 0 ) = (α β 0 ) + α, (c) α β = sup{α γ : γ < β} β 35. 33 G G(α, x) = α {S(y) : y ran(x)} 33 F (α, β) = G(α, F β) 4 F (α, 0) = G(α, ) = α F On On β F (α, S(β 0 )) = α {S(F (α, γ)) : γ β 0 } = {S(F (α, γ)) : γ β 0 } = S(F (α, β 0 )). F (α, β) = {S(F (α, δ)) : δ < β} = sup{f (α, γ) : γ < β}. F (α, β) α + β 36. 1. α + β ({0} α) ({1} β) 2. α β α β. 1 β β β = β 0 +1 α+β = (α+β 0 ) {α+β 0 } α+β 0 ({0} α) ({1} β) = ( ({0} α) ({1} β 0 ) ) { 1, β 0 } < { 1, β 0 } (α + β 0, ) = (({0} α) ({1} β 0 ), <) (α + β, ) = ( ({0} α) ({1} β), < ) β γ β f γ f γ : α + γ = ({0} α) ({1} γ {f γ : γ β} 37. 1. 1 + ω = ω: 1 + ω = sup{1 + n : n ω} = sup{n : n ω} = ω. 2. ω + 1 ω: ω S(ω) = ω + 1. 3. 2 ω = ω: 2 ω = sup{2 n : n ω} = sup{n : n ω} = ω. 4. ω 2 ω: ω ω + 1 sup{ω + n : n ω} = ω + ω. 4 F β β F (α, ) β

18 1 1.5 38. 1. A, B A B A B f(a 1 1 B). onto On 2. α Card(α) α - Card(x) Ord(x) β(β x x β). 3. A A κ A A 39. A α α A κ, λ,... κ + λ κ + λ 40 ( ). 1. κ + λ = ({0} κ) ({1} λ), 2. κ λ = κ λ. 3. κ λ = F, F f : λ κ f 41. m, n ω m + n 42. κ, λ ω κ + λ = κ λ = max{κ, λ}. 43 ( ). κ < 2 κ. 2 = {0, 1}. 2 κ κ F : 2 κ 1 1 κ α κ f α 2 κ f 2 κ (F (f) = α) f f α g : κ 2 2 κ κ 2 g(α) = 1 f α (α). g = f β β g(β) = 1 f β (β) f β (β)

1.5. 19 44. 1. κ + = min{λ : κ < λ}. κ 2. λ λ = κ + 3. ℵ 0 = ω, ℵ α = sup{(ℵ β ) + : β < α}. α 4. cf(κ) = min{ X : X κ, κ = X}. cf(κ) = κ κ 45. 1. κ + 2. cf(2 κ ) > κ.. 1. κ + κ + = X X κ + κ α X κ + α κ κ + κ κ κ + κ κ = κ 2. cf(2 κ ) κ 2 κ P(κ) cf(2 κ ) κ 2 κ P i (i < κ) P(κ) = {P i : i < κ} κ = {X i : i < κ}, X i = κ (i κ), X i X j = (i j) κ P i < 2 κ A i X i A i / {x X i : x P i } {A i : i < κ} P i A 0 A 1 A 2 X 0 X 1 X 2 46. κ cf(κ) > κ.

20 1. κ = i<cf(κ) α i α i < κ κ cf(κ) κ f : κ κ cf(κ) i < cf(κ) g i : α i κ g i (x) = (f(x)) i = [f(x) i ] κ cf(κ) cf(κ) i ran(g i ) X i < κ α i κ ran(g i ) h = (α 0, α 1,... ) f h = f(i) i α i = (h) i = (f(i)) i ran(g i ) α i

21 2 2.1 L L- M, N X L M X M 47. M, N L- σ : M N 1. c L σ(c M ) = c N ; 2. P L σ(p M ) = P N ; 3. F L n σ(f M (a 1,..., a n )) = F N (σ(a 1 ),..., σ(a n )) a 1,..., a n M 48. 1. n n + 1 2. σ : M N σ 1 : N M 49. σ : M N F φ(x 1,..., x k ) a 1,..., a k M M = φ(a 1,..., a n ) N = φ(σ(a 1 ),..., σ(a n )). φ 50. 1. { < } 2. {e,, 1 }

22 2 51. σ : M N φ(x 1,..., x k ) a 1,..., a k M M = φ(a 1,..., a n ) N = φ(σ(a 1 ),..., σ(a n )).. φ n n = 0 φ 49 n + 1 φ φ yψ(y, x 1,..., x k ) a 1,..., a k M M = yψ(y, a 1,..., a k ) M = ψ(b, a 1,..., a k ) N = ψ(b, σ(a 1 ),..., σ(a k )) N = yψ(y, σ(a 1 ),..., σ(a k )) σ 1 52. σ : M N σ : M = N σ : M = N σ M N M = N 2.2 L T L- T T T L + ℵ 0 53 ( ). T 1. T 2. T T 0. 1 2 2 1 T T T T 0 T T 0 T 0 54. φ M = φ N = φ M N M N

2.3. 23 55. M = N M N σ : M = N 51 φ M = φ N = φ φ M N M N M = N 56. M L- κ κ + {c α : α < κ + } T T = {φ : M = φ} {c α c β : α β}. {φ : M = φ} M L- {c α c β : α β} T T 0 I κ + T 0 = {φ 1,..., φ m } {c α c β : α, β I, α β}. M {φ 1,..., φ m } {c α c β : α, β I, α β} c α (α I) M I M T N T {φ : M = φ} N M T {c α c β : α, β I, α β} N κ + M N M = N 57 ( - ). M L- κ L κ L- N N M. 56 2.3 L- T T M, N M N T φ T = φ T = φ

24 2 58. 1. φ G = φ G = φ 2. K 59. M, N = T M, N M M, N N, M = N T. M, N = T M, N M = N M N M M N N M N T 60. 0 S T {0, S}- x, y(s(x) = S(y) x = y) S x(s(x) 0) 0 S y(y 0 x(s(x) = y) 0 S(x) x(s n (x) = x) (n = 1, 2,...) S T N S(m) = m + 1 T M, N T κ > M + N M M, N N, M = N = κ 59 T A. M = N. M (N, S) 0 M S M M Z S S 1 κ N 61. K K V {0}

2.4. 25 1. V 0, +, ; 2. a K 1 f a K T K T K M, N = T K M, N K κ = ( M + N ) + M, N = T K M M, N N, M = N = κ. M N κ M = N 59 T K 2.4 62. M L- A M n L- φ(x 1,..., x n, y 1,..., y m ) b 1,..., b m M A = { a 1,..., a n M n : M = φ(a 1,..., a n, b 1,..., b m )} A A φ(x 1,..., x n, b 1,..., b m ) A b 1,..., b m B A B 63. M 2 M L M 64. 1. A = {a 1,..., a m } M A x = a 1 x = a m 2. R y = x 2 y = ax 2 + bx + c {a, b, c} 65. A M n B M B σ : M M A σ- σ(a) = A

26 2. n = 1 A φ(x, b 1,..., b m ) b 1,..., b m B a M a A M = φ(a, b 1,..., b m ) M = φ(σ(a), σ(b 1 ),..., σ(b m )) M = φ(σ(a), b 1,..., b m ) ( σ B = id B ) σ(a) A. σ 1 σ(a) = A 66. N 1 S a a+1 {S}- M M A M M 65 67. (Q, <) (R, <) < r A = {a R : R = a < r} (R, <) A Q (Q, <) A Q (Q, <) φ(x, b 1,..., b m, d 1,..., d n ) b 1 < < b m < r < d 1 < < d n s, t Q b m < s < r < t < d 1 Q σ 1. σ b m 2. σ d 1 3. σ(s) = t. s A Q σ(s) = t / A Q σ b 1,..., b m, d 1,..., d n A Q σ- b 1,..., b m, d 1,..., d n 68. (N, <, S) < S : a a + 1 (N, <) 65 (N, <, S) E N (N, <) E φ(x) ℵ 1 N N N N N N

2.5. 27 A. N = x[φ(x) φ(s(x)]. x N N N N σ : N N σ N = id N, σ(a) = S(a) (a / N) B. σ σ σ(s(a)) = S(σ(a)) 1. a N σ(a) = a 2. a / N σ(s(a)) = S(S(a)) = S(σ(a)) A,B N φ σ- 2.5 2.5.1 Kenneth Appel and Wolfgang Haken R 69. {R}- G 2 1. R x y(r(x, y) R(y, x)). 2. R x R(x, x). G R(x, y) x, y

28 2 (G, R G ) v G c v C i (i = 0, 1, 2, 3) 1 T 1. {c v c w : v, w G, v w} 2. {R(c v, c w ) : v, w G, G = R(v, w)} 3. { R(c v, c w ) : v, w G, G = R(v, w)} 4. x i 3 C i(x) 5. i j x(c i(x) C j (x)) 6. x y(r(x, y) i 3 (C i(x) C i (y))) 1,2,3 G 4,5 4 5 T T ( ) 2.5.2 70. (A, <) < A < 71. A 2 < (i) < < (ii) (A, < )

2.5. 29 70. A n = A n = 1 n + 1 A a A {a} a A {a} A < a A c a < T 1. {c a c b : a, b A, a b} 2. {c a < c b : A = a < b} 3. < T M a A c a M A M < A