Akito Tsuboi June 22, 2006 1 T ϕ T M M ϕ M M ϕ T ϕ 2 Definition 1 X, Y, Z,... 1
1. X, Y, Z,... 2. A, B (A), (A) (B), (A) (B), (A) (B) Exercise 2 1. (X) (Y ) 2. ((X) (Y )) (Z) 3. (((X) (Y )) (Z)) Exercise 3 ((X) (Y )) ( (Z)) Remark 4 (, ) X Y Z X Y Z X Y Z A A X, Y,... true( 1) false 0 A and or (not) { 1 X = 1 and Y = 1 A X Y A = 0 otherwise 2 X Y 0 0 0 0 0 1 1 0 0 1 1 1,, 2
X Y 0 0 0 0 1 1 1 1 0 1 1 1, X 1 0 0 1, X Y 0 1 0 0 1 1 1 0 0 1 1 1 0, 1 0, 1 (X Y ) Z (X Y ) Z 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 Definition 5 X,Y,... ϕ ϕ (tautology) X ( X) Exercise 6 ( ( X)) (X) Remark 7 Remark 8 X, Y,.. 3
3 3.1 L,L,... x,y,z,x 0,x 1,...,,,,, = (,),[,] Definition 9 ( ) L L 0. L L 1. t 1,..., t n L F L n F (t 1,..., t n ) L 2. L 2 Example 10 L = {c, F } c F x, c, F (x, c), F (x, F (x, c)), F (F (x, c), F (x, c)),... L Definition 11 ( ) 1. t s L t = s L 4
2. t 1,..., t n L P L n P (t 1,..., t n ) L Example 12 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 ) x 1,..., x n t F (x, c) t t t(x) t(x, y) Definition 13 ( ) L L L- 0. L L 1. ϕ, ψ L x (ϕ), (ϕ) (ψ), (ϕ) (ψ), (ϕ) (ψ), x(ϕ), x(ϕ) 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 Definition 14 ϕ ϕ 5
3.2 1, 3.3 A X,Y,... L Example 15 X ( X) ( x)(x = x) L X ( x)(x = x) ( ( x(x = x))) X ( x)p (x) ( x)p (x) ( ( x)p (x)) 1 1 + 1 = 2 6
Remark 16 Remark 17 X, Y,.. L 3.4 Definition 18 ϕ x x ϕ x x ϕ x x ϕ x ϕ Example 19 1. ( x)(x = y) x y 2. [( x)(x = x)] [( y)(x = y)] x x x x 2, 1. ( x)(ϕ ψ) (ϕ ( x)ψ) ϕ x 7
2. ( x)ϕ(x, y,...) ϕ(t, y,...) t t ϕ(t, y,...) Remark 20 1,2 x y, z,... x x 1 ϕ x x(x = 1 x = 1) (x = 1 x(x = 1) x = 1 y z 1 2 x t ϕ(x) ( y)[x = y] ( x)ϕ(x) ϕ(x) x y + 1 ( y)[y + 1 = y] 3.5 = x, y t(u 0,..., u n ) u 0,..., u n ϕ(u 0,..., u n ) u 0,..., u n 1. x = x; 2. x = y t(x, u 1,..., u n ) = t(x, u 1,..., u n ); 8
3. x = y [ϕ(x, u 1,..., u n ) ϕ(y, u 1,..., u n )]. Exercise 21 3 ϕ x = y [( y)(x = y + 1) ( y)(y = y + 1)] 4 1. (Modus Ponens) ϕ ϕ ψ ψ 2. (Generalization) ϕ ( x)ϕ Definition 22 ϕ 0,..., ϕ n i n ϕ i 1. ϕ i 2. ϕ i ϕ j ϕ i xϕ j (j < i) 3. ϕ i ϕ j ϕ k Modus Ponens ϕ k ϕ j ϕ i j, k < i ψ ψ Example 23 L P P (x) ( y)p (y) ( y)p (y) y( P (y)) P (x) y( P (y)) y( P (y)) P (x) (X Y ) (Y X) X y( P (y)), Y P (y) ( y( P (y)) P (x)) (P (x) y( P (y)) Modus Ponens P (x) y( P (y)) 9
Remark 24 ϕ ψ ψ θ ϕ θ ϕ ψ ψ θ ϕ θ (ϕ ψ) [(ψ θ) (ϕ θ)] tautology ϕ ψ Modus Ponens (ψ θ) (ϕ θ) ψ θ Modus Ponens ϕ θ Exercise 25 xp (x) yp (y) ϕ ϕ ϕ ϕ 1. ϕ ϕ ψ ψ; 2. ϕ ( x)ϕ Definition 26 ( ) Γ ϕ ϕ 0,..., ϕ n Γ ϕ i n ϕ i 10
1. ϕ i 2. ϕ i Γ 3. ϕ i ϕ j ϕ i xϕ j (j < i) 4. ϕ i ϕ j ϕ k Modus Ponens ϕ k ϕ j ϕ i j, k < i Γ ϕ Γ ϕ Remark 27 ϕ Γ = Γ ϕ Γ ϕ Γ Γ 0 Γ 0 ϕ Γ ϕ ϕ Γ ϕ 0,..., ϕ n, ϕ Γ Γ 0 Lemma 28 Γ {ϕ} θ Γ ϕ θ Proof : Γ ϕ θ ϕ 0,..., ϕ n, (ϕ θ) ϕ, ϕ 0,..., ϕ n, (ϕ θ), θ Γ {ϕ} θ : Γ {ϕ} θ n n = 1 θ θ Γ {ϕ} θ Γ ϕ θ Γ θ ϕ ϕ θ ϕ ϕ Γ n + 1 Modus Ponens ψ ψ θ θ Γ {ϕ} Γ ϕ ψ, Γ ϕ (ψ θ). (ϕ ψ) ((ϕ (ψ θ)) (ϕ θ)) Modus Ponens Γ ϕ θ Generalization θ xψ ψ x ψ 11
ψ n Γ ϕ ψ Generalization Γ x(ϕ ψ) ϕ x(ϕ ψ) (ϕ xψ) Modus Ponens Γ ϕ xψ Proposition 29 Γ ϕ(x) c Γ Γ ϕ(c) Γ ( x)ϕ(x) Proof Γ ϕ(x) Γ ( x)ϕ(x) Γ ϕ(c) Γ ϕ(x) Γ Case 0. - ϕ(c) Γ Γ c ϕ(x) ϕ(c) ϕ(x) Γ generalization Γ ( x)ϕ(x) - ϕ(c), = ϕ(x) Case 1. - Modus Ponens ψ(c) Γ ψ(c) ϕ(c), Γ ψ(c) Γ ψ(x), Γ ψ(x) ϕ(x) Modus Ponens Γ ϕ(x) - Generalization ϕ(x) ( y)ψ(x, y) ψ(c, y) ( y)ψ(c, y) Γ ψ(c, y) Γ ψ(x, y) Generalization Γ ( y)ψ(x, y) Exercise 30 c Γ ϕ 0 (c),..., ϕ n (c) Γ ϕ 0 (x),..., ϕ n (x) Γ x 5 α,β.... 12
Definition 31 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 Remark 32 1. < {(x, y) R : x < y} 2. M R (R, 0., 1, +, ) (R, 0, 1, +,, <) 3. L = {0, 1, +, } R L- + L- 13
L t t M t Definition 33 ( ) 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 t M (a 1,..., a n ) = a i. (b) t c 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 )). Definition 34 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 ). 14
ϕ ϕ 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 ). Example 35 1. M 2 (GL 2 (R)) 2 M M M { }- (M, M) = x y(x y y x) 2. M M (M, M) = x y(x y = y x) 3. L = { } R Q L- L- ϕ x y(x = y y) R = ϕ Q = ϕ Exercise 36 M L- M 1. c L P L M = P (c) M = P (c M ). c M P M 2. ϕ(x 1,..., x n ) L- t 1,..., t n L M = ϕ(t 1,..., t n ) M = ϕ(t M 1,..., t M n ). 15
Definition 37 M L- ϕ L- M = ϕ M ϕ T L- M ϕ T M = T M T Remark 38 M ϕ M ϕ ϕ ϕ ϕ ϕ 6 1. 2. x(ϕ ψ) (ϕ xψ) ϕ x xϕ(x,...) ϕ(t,...) t t ϕ 3. 4. ϕ ψ ϕ ψ (Modus Ponens) ϕ xψ (Generalization) Remark 39 1. ϕ ϕ ϕ Γ Γ ϕ Γ ϕ 16
2. xϕ ( x( ϕ)) Proposition 40 Γ c Γ ϕ 1 (c, x),..., ϕ n (c, x) Γ ϕ 1 (c, x),..., ϕ n (c, x) c z ϕ 1,..., ϕ n ϕ 1 (z, x),..., ϕ n (z, x) Γ ϕ(c) Γ ϕ(x) x Γ ϕ(c) 7 Definition 41 1. Γ L Γ Γ ψ ψ ψ ψ (( ψ) θ)) Γ L- θ 2. Γ consistent Γ Lemma 42 ϕ L- 1. Γ {ϕ} θ Γ ϕ θ 2. Γ {ϕ} Γ ϕ Proof 1. Γ {ϕ} θ n n = 1 θ θ Γ {ϕ} θ Γ ϕ θ Γ θ ϕ ϕ θ ϕ ϕ Γ n + 1 Modus Ponens ψ ψ θ θ Γ {ϕ} Γ ϕ ψ, Γ ϕ (ψ θ). (ϕ ψ) (ϕ (ϕ ψ)) Γ ϕ ψ Γ ϕ (ϕ ψ). 17
Γ (ϕ ψ) θ. Γ ϕ θ Generalization 2. Γ {ϕ} Γ {ϕ} ϕ Γ ϕ ϕ. (ϕ ϕ) ϕ Γ ϕ Theorem 43 Γ L Γ Γ 1. L 2. c i i N L L = L {c i : i N} 3. Γ L - L Γ 4. Γ L - Γ 5. Γ L - M 6. M = Γ 7. M L M M = Γ 8 43 L Γ L L C = {c i : i N} L = L C Remark 44 ϕ(x, ȳ) x, ȳ L ϕ(c i, ȳ) L 18
Claim A Γ L L ϕ(c 1,..., c n, ȳ) ϕ(x 1,..., x n, ȳ) L 40 c 1,..., c n z 1,..., z n L 8.1 Γ L x {ϕ i (x) : i N} ϕ i (x) C c 0,..., c i 1 L Γ n (n N) Γ n = Γ { x(ϕ i (x)) ϕ(c i ) : i < n}. Claim B Γ n n = 1 n Γ 1 = Γ { x(ϕ i (x)) ϕ i (c i )} 42 Γ [ x(ϕ 0 (x)) ϕ 0 (c 0 )] [ x(ϕ 0 (x)) ϕ 0 (c 0 )] x(ϕ 0 (x)) ϕ 0 (c 0 ) Γ x(ϕ 0 (x)) Γ ϕ(c 0 ) 40 c 0 Γ Γ x( ϕ 0 (x)). Γ x(ϕ 0 (x)) Γ (Claim B 19
Γ ω = n ω Γ n Γ ω L Γ ω L Γ Zorn Claim C ϕ L ϕ Γ ( ϕ) Γ Γ Γ Γ {ϕ}, Γ { ϕ} 42 Γ ϕ; Γ ( ϕ). Γ Claim C Remark 45 Γ L - ϕ Γ ϕ = ϕ Γ ϕ ϕ ψ Γ ψ Γ 8.2 M Γ L - M L T erm t u t = u Γ Claim A t 1, t 2, t 3 T erm t 1 t 2, t 2 t 3 (t 1 = t 2 ), (t 2 = t 3 ) Γ Γ (t 1 = t 2 t 2 = t 3 ) t 1 = t 3 Γ t 1 = t 3 Remark 45 t 1 t 3 Claim D 20
Remark 46 [t] C t T erm x(t = x) L x(t = x) t = c n Γ x(t = x) Γ t = c n Γ [t] = [c] M M M = T erm/ = {[t] : t T erm} [t] t L c L P L n F L n c M = [c], P M = {([t 1 ],..., [t n ]) (M ) n : P (t 1,..., t n ) Γ }, F M ([t 1 ],..., [t n ]) = [t] (F (t 1,..., t n ) = t) Γ. well-defined 8.3 M Γ Claim A L ϕ M = ϕ ϕ Γ. ϕ,,,,, n Case 0: n = 0 ϕ P (t 1,..., t n ) t = u P M M = P (t 1,..., t n ) ([t 1 ],..., [t n ]) P M P (t 1,..., t n ) Γ. t = u Case n+1: ϕ ϕ ϕ 1 ϕ 2 M = ϕ 1 ϕ 2 M = ϕ 1 M = ϕ 2 ϕ 1 Γ ϕ 2 Γ ϕ 1 ϕ 2 Γ Γ 21
,, ϕ xψ(x) M = xψ(x) xψ(x) Γ : xψ(x) / Γ Γ xψ(x) Γ x ψ(x) Γ ψ(x) x L Γ n {ϕ i (x)} i N ψ(x) n ϕ n (x) x ψ(x) ψ(c n ) Γ Γ ψ(c n ) Γ M = ψ(c n ) M = x ψ(x) M = xψ(x) : xψ(x) Γ Γ t T erm ψ(t) Γ M = ψ(t) ( t T erm) [t] M M = xψ(x) 8.4 M M M Γ L - L C (M, P M, F M, c M, c M 0, c M 1,...) Γ C L (M, P M, F M, c M ) L- M Γ Γ Γ L M Γ 9 22
Lemma 47 ϕ( x) L- 1. ϕ( x) L- M M = xϕ( x) 2. T ϕ T M M = xϕ( x) Proof M M M T ϕ( x) ψ 1,..., ψ m T ψ 1... ψ m ϕ( x) x(ψ 1... ψ m ϕ) L- M M T M = ψ 1... ψ m M = xϕ( x) Remark 48 Definition 49 Definition 50 T L- ϕ L- L- M M = T M = ϕ T = ϕ T = = ϕ Theorem 51 T = ϕ T ϕ. Proof ( ) ( ): T ϕ Γ = T { ϕ} ( 42) Γ M M = T M = ϕ T = ϕ Theorem 52 T L- 1. T 23
2. T T 0 Proof 1 2 2 1: 1 T T ψ ( ψ) T T 0 = {ψ 1,..., ψ m } T 0 T 0 2 Example 53 L = {0, 1, 2,..., +,, <} N L- N N M N L- T c T = T {c > 0, c > 1, c > 2, c > 3,...} T T 0 T 0 T 0 = {ϕ 1,..., ϕ m } {c > 0,..., c > n} ϕ i T N = ϕ 1... ϕ m c n + 1 N = c > 1... c > n T M M = T M N L- M c M N Definition 54 C L- C T L- L- M M C M = T. Example 55 L {e,, 1 } 1. L- G T 2. F T F ( ) M M = T T T = T {θ n : n = 1, 2,...} 24
θ n n T T G = T G T ( ) Remark 56 L L- Theorem 57 (Löwenheim-Skolem) 1. T 2. T κ M κ M = T Proof 1 2 κ {c i : i < κ} T T = T {c i c j : i < j < κ} T 0 = {ϕ 1,..., ϕ m } {c i1,..., c in } ϕ i T N = T d 1,..., d n N N c N i j = d j N N = T 0. T M T T M = T. c i M κ Remark 58 Upward Löwenheim-Skolem 10 - R r R c r 25
f : R n R F f X R m P X R L c R r r F f R f P R X X T = {ϕ : R = ϕ, ϕ L- } R T c T = T {c 0} { c < c r : r R, r > 0} c 0 T Claim A T T 0 T 0 = {ϕ 1,..., ϕ m } {c 0} { c < r 1,..., c < r n } r i d = min{r 1,..., r n }/2 c d R T 0 Claim T R T T R L- R R R Lemma 59 R R R R Proof σ : R R R σ(r) = c r m F f L R = F f (r 1,..., r m ) = s R = F f (c r1,..., c rm ) = c s F f (c r1,..., c rm ) = c s T R = F f (c r1,..., c rm ) = c s R R = F f (c R r1,..., c R rm ) = c s R = F f (σ(r 1 ),..., σ(c rm )) = σ(s). σ R R R R R F R f f F f f X R m R P X X a R r R, r > 0 a c c R 0 2c R, 3c R,... R R 0 R 26
Remark 60 N N R = x y N(y < x < y + 1) R = x y N (y < x < y + 1) d = 1/c d R = n < d < n + 1 n N n N N Definition 61 a, b R a b a b Proposition 62 a R f : R R 1. f a 2. ε f (a + ε) f (a) Proof 1 2: f a n 0 R = x( x a < δ n f(x) f(a) < 1/n) δ n > 0 R R = x( x a < δ n f (x) f (a) < 1/n). x a + ε R = (a + ε) a < δ n f (a + ε) f (a) < 1/n. (a + ε) a < δ n R = f (a + ε) f (a) < 1/n n f (a + ε) f (a) 2 1: f a 1 ɛ > 0 g : N R R = x N [ g(x) a < 1/x f(g(x)) f(a) > ɛ ] R R = x N [ g (x) a < 1/x f (g (x)) f (a) > ɛ ] 27
x b N N R = g (b) a < 1/b f (g (b)) f (a) > ɛ g (b) a < 1/b < r ( r R, r > 0) g (b) a f (g (b)) f (a) 2 Proposition 63 f : R R 1. f 2. a, b R a b f (a) f (b). Proof 1 2: 1 n N {0} δ n R + R = x, y( x y < δ n f(x) f(y) < 1/n). R R = x, y( x y < δ n f (x) f (y) < 1/n). a, b R a b R = a b < δ n f (a) f (b) < 1/n n R = f (a) f (b) < 1/n n = 1, 2,.. f (a) f (b) 2 1: 1 ɛ > 0 g : N R, h : N R R = x N[ g(x) h(x) < 1/x f(g(x)) f(h(x)) > ɛ] R = x N [ g (x) h (x) < 1/x f (g (x)) f (h (x)) > ɛ]. k N N x R = g (k) h (k) < 1/k f (g (k)) f (h (k)) > ɛ. 1/k < 1/n (n = 1, 2,...) a = g (k), b = h (k) a b, f (a) f (b) 28
Exercise 64 1. a R R = a < n n N a b b R 2. f : [a, b] R f 29