Mathematical Logic I 12 Contents I Zorn

Mathematical Logic I 12 Contents I 2 1 3 1.1............................. 3 1.2.......................... 5 1.3 Zorn.................. 5 2 6 2.1.............................. 6 2.2.............................. 9 2.3....................... 13 3 15 3.1..................... 15 3.2..................... 17 3.3................... 19 3.4 Löwenheim-Skolem.................. 21 4 24 4.1.................... 24 4.2........................ 28 II 32 1

5 32 5.1 (Peano).................... 32 5.2 (numeral)........................ 33 6 PA 34 6.1......................... 35 6.2 (End Extension).................. 36 7 38 7.1.............................. 38 7.2.................. 41 7.3............................ 42 7.4......................... 44 7.5......................... 46 7.6..................... 49 8 53 8.1 ℵ 0 -........................... 53 8.2 ℵ 1 -........................... 53 9 53 10 53 11 53 11.1.......................... 53 11.2.......................... 56 2

I 1 1.1 1. X = (X, <) (well-ordered) A X 2. 1. X 2. X (a)+(b) (a) X (b) X 3. X I(a) = {x X : x < a} 4. 5. 3. (ordinal) n n N ω α, β α β α < β β α β < α α β α 2 I(b) β b α α α α = {β : β < α} 3

4 ( ). X = (X, < X ) Y = (Y, < Y ) X Y = X Y X + Y 1. X + Y X Y 2. X + Y x < y x < X y (x, y X) x < Y y (x, y Y ) x X, y Y 5. 1. 2. 1 + ω 1 ω 1 + ω = ω. 3. ω + 1 ω 4. 6. α α = β+1 succesor ordinal α = β + 1 (limit ordinal) 7. 1. n > 0 2. ω α β n α = β +n 8 ( ). X = (X, < X ) Y = (Y, < Y ) y Y X X Y 1. X Y X Y 2. (x, y) < (x, y ) y < Y y y = y, x < X x 9. 1. 2. 2 ω = ω ω 2. 4

1.2 A < A A = (A, <) α A = {a i : i < α} A = {a i : i < α} α A A A κ, λ 10. κ λ A, B κ = A, λ = B, A B = 1. κ + λ = A B, 2. κ λ = A B 11. 1. A, B 2. 3. 1 + ω = ω + 1 = ω 4. κ, λ κ + λ = κ λ = max{κ, λ}. 1.3 Zorn P (*) m < n P (m) P (n) 5

12. ( ) α β n α α α = α +0 α α = α 0 +1 α 0 < α α 0 β n 0 α 0 = β + n 0 α = α 0 + 1 = (β + n 0 ) + 1 = β + (n 0 + 1) β n 0 + 1 Zorn (**) A = X P(A) B i X (i < α) B i X i<α X 13. R 1 R Zorn X = {I R : I 1 } X 2 2.1 6

14. 1. {e,, 1 } e 1 ( ) 2. {0, 1, +,,, 1 } 3. {0, 1, +,,, 1, < } 0 L,L,... x,y,z,x 0,x 1,... 15. ( ) L L 0. L L 1. t 1,..., t n L F L n F (t 1,..., t n ) L 2. L 16. L = {c, F } c F x, c, F (x, c), F (x, F (x, c)), F (F (x, c), F (x, c)),... L 15 7

1. T 0 = { } {L }; 2. T k+1 = {F (t 1,..., t n ) : t 1,..., t n T k F L n }; 3. L = k N T k. 17. G A G G A {=,,,,,, } 18. ( ) 1. t s L t = s L 2. t 1,..., t n L P L n P (t 1,..., t n ) L 19. L = {c, F, < } c F < 1. F (x, c) = y, 2. F (x, y) < F (F (x, y), c) L t x 1,..., x n t t(x 1,..., x n ),,,,, 20. ( ) L L L- 0. L L 1. φ, ψ L x (φ), (φ) (ψ), (φ) (ψ), (φ) (ψ), x(φ), x(φ) 8

L L- φ x x x x x φ ( x(f (x, y) = x)) (F (x, x) = z) x x x φ x 1,..., x n φ φ(x 1,.., x n ) φ n 21. φ φ 2.2 α,β.... 22. L = {c i : i < α} {F i : i < β} {P i : i < γ} c i F i m i P i n i (M; {c M i } i<α, {Fi M } i<β, {Pi M } i<γ ) L- c M i 1. M 2. c M i M (i < α) 3. F M i M m i M (i < β) 4. P M i M n i (i < γ) c i M Fi M F i Pi M P i M 9

23. 1. < {(x, y) R : x < y} 2. M R (R, 0., 1, +, ) (R, 0, 1, +,, <) 3. L = {0, 1, +, } R L- + L- L t t M t 24. ( ) M L- L t(x 1,..., x n ) a 1,..., a n M t a 1,..., a n t M (a 1,..., a n ) : 0. (a) t x i (b) t c t M (a 1,..., a n ) = a i. t M (a 1,..., a n ) = c M. 1. t F (t 1 (x 1,..., x n ),..., t m (x 1,..., x n )) F t i t M (a 1,..., a n ) = F M (t M 1 (a 1,..., a n ),..., t M m (a 1,..., a n )). 10

25. M L- a 1,..., a n M φ = φ(x 1,..., x n ) L- M φ(a 1,..., a n ) M = φ(a 1,..., a n ) 1. φ t(x 1,..., x n ) = u(x 1,..., x n ))), M = φ(a 1,..., a n ) t M (a 1,..., a n ) = u M (a 1,..., a n ). φ P (t 1 (x 1,..., x n ),..., t m (x 1,..., x n )) M = φ(a 1,..., a n ) (t M 1 (a 1,..., a n ),..., t M m (a 1,..., a n )) P M. 2. φ φ 1 (x 1,..., x n ) φ 2 (x 1,..., x n ) M = φ(a 1,..., a n ) M = φ 1 (a 1,..., a n ) M = φ 2 (a 1,..., a n ). φ φ 1 (x 1,..., x n ) φ 2 (x 1,..., x n ) M = φ(a 1,..., a n ) M = φ 1 (a 1,..., a n ) M = φ 2 (a 1,..., a n ). φ φ 1 (x 1,..., x n ) φ 2 (x 1,..., x n ) M = φ(a 1,..., a n ) M = φ 1 (a 1,..., a n ) M = φ 2 (a 1,..., a n ). φ ψ(x 1,..., x n ) M = φ(a 1,..., a n ) M = φ(a 1,..., a n ). φ xψ(x, x 1,..., x n ) M = φ(a 1,..., a n ) b M M = ψ(b, a 1,..., a n ). φ xψ(x, x 1,..., x n ) M = φ(a 1,..., a n ) b M M = ψ(b, a 1,..., a n ). 26. ψ(x) c M = ψ(c) M = ψ(c M ) ψ = 11

27. ( ) L 22 L M N L- σ : M N 1. σ(c M i ) = c N i (i < α); 2. σ F M i 3. σ(pi M ) = Pi N = Fi N (σ,..., σ) (i < β); }{{} n i (i < γ). 2. F M i (a 1,..., a mi ) = b F N i (σ(a 1 ),..., σ(a ni )) = σ(b), ( a 1,..., a mi, b M); 3. (a 1,..., a ni ) P M i (σ(a 1 ),..., σ(a ni )) P N i ( a 1,..., a ni M). 28. σ : M N t(x 1,..., x n ) σ(t M (a 1,..., a n )) = t N (σ(a 1 ),..., σ(a n )) ( a 1,..., a n M) t 29. L- σ : M N 1. σ : M N ; 2. φ(x 1,..., x n ) a 1,..., a n M M = φ(a 1,..., a n ) N = φ(σ(a 1 ),..., σ(a n )). 30. ( ) M,N L- A M, B N σ : A B (*) L- φ(x 1,..., x n ) a 1,..., a n A M = φ(a 1,..., a n ) N = φ(σ(a 1 ),..., σ(a n )). 31. 30 (*) φ 12

2.3 32. T L- M = T M = φ ( φ T ) M = T M T 33. T L- 1. T M s.t. M = T 2. T S fin T M S s.t. M S = S Proof. 1 2 2 1 L C = {c i : i ω} L = L C L - x {φ i (x) : i ω} φ i i T = T { xφ i (x) φ i (c i ) : i ω} A. T n ω T n = {ψ 0,..., ψ n } { xφ i (x) φ i (c i ) : i = 0,..., n} T n ψ n T {ψ 0,..., ψ n } T N i = 0,..., n φ i (x) N, c i N = T n A T Zorn L - T T B. T L - φ φ T φ T T L - 13

L - closed term CT CT 2 t u t = u T. M = CT/ t CT [t] M = {[t] : t CT } c L c M := [c] m F L F M ([t 1 ],..., [t m ]) := [F (t 1,..., t m )] well-defined t M = [t] n F L P M = {([t 1 ],..., [t n ]) : P (t 1,..., t n ) T } M T C. L - φ M = φ φ T. φ l l = 0 φ P (t 1,..., t n ) M = P (t 1,..., t n ) (t M 1,..., t M n ) P M ([t 1 ],..., [t n ]) P M P (t 1,..., t n ) T l > 0 φ xψ(x) M = xψ(x) M = ψ([t]) ( [t] M) M = ψ(t) ( [t] M) ψ(t) T ( t CT ) xψ(x) T. ψ(t) T xψ(x) T T xψ(x) ψ(c) T T 14

3 3.1 34. ( ) I P(I) U P(I) 1. U U F U A 1,..., A }{{ n U A } 1... A n finite 2. U I U P(I) U,U 35. 1. I A I cofinite A A c = I \ A F = {A I : A } F 2. I F = {A I : A c } F 36. I U 1. A U, A B I B U; 2. A U, B U A B U. 37. a I U a = {A I : a A} I U a a {a} U a U a a B {a} B = 38. U P(I) 1. U 2. A I A U A c U. 15

39. U i P(I) (i < α) U = i<α U i Proof. A i,..., A n U U i U i A 1... A n 40. U P(I) A I U {A} U {A c } Proof. F 1 U F 2 U F 1 {A} =, F 2 {A c } = F = F 1 F 2 F = 37 41. I F P(I) F I U F s.t. U I Proof. P(I) κ P(I) {A i : i < κ} i κ U i P(I) 1. U 0 = F ; 2. i = α + 1 U i P(I) U α U i ; A α A c α U i 3. i U i = j<i U j. U = U κ A I A U A c U A = A α α A U α+1 A c U α+1 U α+1 U 16

42. N.F P(N) F = F 3.2 L I i I M i L- N = Π i I M i N (a i ) i I F L L- L- F N (a 1,..., a n ) = ( F M i (a 1 i,..., a n i ) ) i I a j = (a j i ) i I N (j = 1,..., n) j 43. I 2 F i (i I) F i I U i I L- M i N a N, i I a i i a = (a i ) i I 17

44. N a b {i I : a i = b i } U N M = i I M i/u a N [a] M = {[a] : a N} [a] = [(a i ) i I 45. M = i I M i/u F L L- F M ([a 1 ],..., [a n ]) = [F N (a 1,..., a n )]. L- M M i 46. well-defined a 1 b 1,..., a n b n F N (a 1,..., a n ) F N (b 1,..., b n ) A, B U A B U 47. t(x 1,..., x n ) L [a 1 ],..., [a n ], [b] M t M ([a 1 ],..., [a n ]) = [b] {i I : t M i (a 1 i,..., a n i ) = b i } U. Proof. t x t L F F M ([a 1 ],..., [a n ]) = [b] [F N (a 1,..., a n )] = [b] [ ( F M i (a 1 i,..., a n i ) ) i ] = [(b i) i ] {i I : F M i (a 1 i,..., a n i ) = b i } U. t. t = F (u) F u [a] M u M ([a]) = [d] {i I : u M i (a i ) = d i } U F M (u M ([a])) = [b] F M ([d]) = [b] {i I : F M i (d i ) = b i } U & {i I : u M i (a i ) = d i } U {i I : F M i (d i ) = b i & u M i (a i ) = d i } U {i I : F M i (u M i (a i )) = b i } U. 18

48. φ(x 1,..., x n ) L- [a 1 ],..., [a m ] M M = φ([a 1 ],..., [a n ]) {i I : M i = φ(a 1 i,..., a n i )} U. Proof. 0) φ φ 1) φ ψ M = ψ([a 1 ],..., [a n ]) M = ψ([a 1 ],..., [a n ]) {i I : M i = ψ(a 1 i,..., a n i )} / U {i I : M i = ψ(a 1 i,..., a n i )} c U {i I : M i = ψ(a 1 i,..., a n i ) } U {i I : M i = ψ(a 1 i,..., a n i )} U. 2)φ yψ(x 1,..., x n, y) M = yψ([a 1 ],..., [a n ], y) M = ψ([a 1 ],..., [a n ], [b]) for some b M 3) 49. φ L- {i I : M i = ψ(a 1 i,..., a n i, b i )} U for some b i s {i I : M i = yψ(a 1 i,..., a n i, y)} U M = φ {i I : M i = φ} U φ U M i φ 3.3 50. T L- 19

1. T M s.t. M = T 2. T S fin T M S s.t. M S = S Proof. 1 2 2 1 T I S I M S = S L- φ T A φ = {S I : M S = φ} A φ I A φ F Claim 1 F P(I) A φ1,..., A φn F M {φ1,...,φ n } φ i {φ 1,..., φ n } A φ1... A φn A φ1... A φn. 1 F I U M = S I M S/U Claim 2 M = T. φ T M = φ {S I : M S = φ} U A φ U 51. N {0, 1, +,, <}- c T = {φ : N = φ} {c > n : n N} c > n c > 1 } + {{ + 1 } T n T 0 T 0 T 0 {φ : N = φ} {c > n 1,..., c > n k } c n = max{n 1,..., n k } + 1 N T 0 T N N {0, 1, +,, <} N N N c N 20

52. L- M 3 x 1 x 2 x 3 [x 1 x 2 x 2 x 3 x 1 = x 3 ] n L- n L- φ n M = φ n φ n+1 M n M = φ M L- φ φ n n L- M n T = {φ } {φ n : n N} T M M φ κ M = φ κ M κ φ κ Löwenheim-Skolem 3.4 Löwenheim-Skolem 53. M L- N M M 1. c L c M N 2. F L F M N N M N N L- c N = c M, n- F N = F M N n, m- P N = P M N m 54. {e,, 1 }- 55. M L- 1. A M L c a a A L(A) M L(A) c M A = a 21

2. N M elementary substructure (*) L(N)- φ M = φ N = φ M N 3. N M N M M N 56. M L- T M L(M)- T T elementary diagram T M a M c N a σ σ : M = σ(m) N σ 57. 1. (*) 2. M L- 58. κ M κ Proof. T M L(M) κ {c i : i < κ} L(M) {c i : i < κ}- T = T {c i c j : i < j < κ} T c i M T N N M T N κ κ 59. (Tarski-Vaught ) M L- N M 22

1. N M; 2. L(N)- φ(x) M = φ(x) M = φ(a) a N Proof. 1 2 2 1: L- φ(x 1,..., x n ) (*) M = φ(a 1,..., a n ) N = φ(a 1,..., a n ) ( a 1,..., a n N) φ(x 1,..., x n ) (*) φ(x 1,..., x n ) yψ(y, x 1,..., x n ) M = yψ(y, a 1,..., a n ) M = ψ(b, a 1,..., a n ) ( b N) N = ψ(b, a 1,..., a n ) ( b N) N = ψ(y, a 1,..., a n ) A A 60. M L- A M N M 1. A N; 2. N A + L + ℵ 0 Proof. A 0 = A M A i (i < ω) i > 0 L(A i 1 )- φ(x) M A i A i A + L + ℵ 0. A i A + L + ℵ 0 L(A i )- A + L + ℵ 0 A i A i+1 A i N = i ω A i Tarski-Vaught N M 23

61. Löwenheim-Skolem T L- T κ L + ℵ 0 T N κ Proof. M T 58 M M κ A M κ 60 A N M A + L + ℵ 0 (= κ) N A N κ N κ L- M,N L- elementarily equivalent M N 62. L M L- κ N M, N = κ N. 4 4.1 63. {M i : i ω} L- M i T i ω M i T T i ω M i = {n Z : n i} M i {<}- M 0 M 1 M 2 ({<}- ) M i = < i ω M i = Z 64. α α L- (M i ) i<α (*) i < j < α M i M j. elementary chain 24

65 ( ). (M i ) i<α M = i<α M i L- M i M Proof. M c M c M i m P P M = i<α P M i n F F M = i<α F M i M i M n ω ( ) n i < α n L(M i )- φ M = φ M i = φ n = 0 φ φ xψ(x) ( ): M = ψ(x) ψ(x) d M M d M j M j i < j M j = ψ(d) M j = xψ(x). M i M j M i = φ ( ) 66. 1. M L A M x = x 1,..., x n L(A)- Φ( x) M φ 1 ( x),..., φ n ( x) Φ( x) M = x[φ 1 ( x) φ n ( x)] Φ( x) L(A)- φ( x) φ( x) Φ( x) φ( x) Φ( x) Φ( x) M A n n 2. A S M (A) M S(A) n A S n (A) 25

3. p S(A) A p domain dom(p) 4. p(x) φ(x) p(x) M 67. 1. N {<, +, 1}- Φ(x) = {x > 1, x > 1 + 1, x > 1+1+1,...} N N 2. Q x Q Φ(x) = {f(x) 0 : f Q- } Φ(x) Q Φ(x) Q 68. M L- L(A)- Φ( x) M Φ( x) A Proof. Φ(x) Zorn 69. p(x) M c T = T h(m, a) a M p(c) T p(c) {φ(c) : φ(x) p(x)} 70. A M M L(A)- p( x) p( x) M M 71. M L- κ M M (*) M p dom(p) M, dom(p) < κ M 26

Proof. S M dom(p) < κ p S c p T = T h(m, a) a M p S p(c p ) c p p T M c p T M M T h(m, a) a M M M c p p M S M domain M domain κ domain M 72. M L- κ M dom(p) < κ p κ- (κ-saturated) 73. M L- κ M M M κ + - Proof. M 0 = M (M i ) i<κ + 1. A M i, A < κ + A M i+1 2. δ M δ = i<δ M i 71 65 M = M κ + κ + - A M κ A M i M i M A M i+1 M A M i+1 M 74. L M κ + - M M 2 κ 27

75. M L- ā = a 1,..., a n M A M tp M (ā/a) = {φ( x) : φ( x) M = φ( x) L(A)- } M ā A M A p( x) M tp(ā/a) = p( x) ā M M κ- κ A M tp(ā/a) (ā M) 76. M N ℵ 0 - L- tp M (ā) = tp N ( b) a M b M tp M (ā, a) = tp N ( b, b) p( x, x) = tp M (ā, a) tp M (ā) = tp N ( b) p( b, x) N b N tp(ā, a) = tp( b, b) M N elementarily equivalent ā, b 4.2 L T L- 77. Σ(x) L- 1. L- φ(x) Σ(x) T isolate (a) T { φ(x)} (b) T M φ(x) Σ(x) T = x[φ(x) Σ(x)] 28

2. Σ(x) M Σ(x) M omit T Σ(x) T isolate T Σ(x) 78. T Σ(x) isolate Σ(x) T Proof. L {c i : i ω} L i = L {c j : j < i} L {c i : i ω} φ i (x) i ω φ i L i - L i - T 0 = T T i i ω (*) T i+1 = T i { xφ i (x) φ i (c i )} { σ i (c i )}, σ i (x) Σ(x) T i+1 T i+1 σ i Σ σ i Σ T i+1 i T i T θ( c) T = x[θ(x, c) ( xφ i (x) φ i (c i )) Σ(x)] c T T = x[ ȳθ(x, ȳ) Σ(x)]. Σ T isolate T i T = i ω T i M = T M M = {c M i : i ω} (*) Tarski-Vaught M M c i σ i (c i ) σ i Σ M Σ 79. Σ i (x)(i ω) T isolate Σ i (x) T 29

80. M N M elementary end extension (i) M N, (ii) a M, b N, b < a b M N M M M elementary end extension Proof. c L(M) T T = T h(m, a) a M {c > a : a M} T M elementary extension Claim 1 φ(x) L(M)-formula T {φ(c)} consisitent M = yφ(y) T {φ(c)} consistent T M = φ(c) a M M = y[y > a φ(y)] c M = y[y > a φ(y)]. a M M = yφ(y) b M (partial) type Σ b (x) Σ b (x) = {x < b} {x d : d M, d < b} Claim 2 Σ b (x) T isolate Σ b (x) φ(x, c) isolate 1. T {φ(x, c)} x < b; 2. T {φ(x, c)} x d ( d < M b) x < b φ(x, c) T consistent Claim 1 M = y x < b φ(x, y). 30

b M M M = x < b y φ(x, y). (1) M = y φ(d, y) (for some d M with d < b) (2) consisitent T {φ(x, c)} {x = d}. 2 31