6 1 6.1 ( ). Γ φ Γ = φ Γ = ψ Γ = ψ φ Γ = φ?? θ xθ?? { x(α β), xα} = xβ x α α xα x x x y (α α ) α α α x y {x y, α} = α A s (A, s) = x ys(x) = s(y) t s(t) = s(t ) t t x y α t 1 t 2 α t 1 t 2 (A, s) = α s(t 1 ) = s(t 2 ) s(t 1) = s(t 2) (A, s) = α P t 1... t n α 6.1 (). t φ x (A, s) = φ x t (A, s x s(t) ) = φ : φ φ u u t s(u x t ) = s x s(t) (u) φ P u 1u 2 u n φ u 1 u 2 1
2 6 (A, s) = (P u 1 u 2 u n ) x t (s((u 1 ) x t ), s((u 2 ) x t ),, s((u n ) x t )) P A (s x s(t) (u 1), s x s(t) (u 2),, s x s(t) (u n)) P A (A, s x s(t)) = P u 1 u 2 u n φ ψ ψ θ φ yψ x φ s s x s(t) φ φ x t φ φ yψ x φ t φ x y t t ψ x A d s(t) = s y d (t) x y φx t = yψ x t (A, s) = φ x t d, (A, s y d ) = ψx t, d, (A, (s y d )x s(t)) = ψ d, (A, (s x s(t)) y d ) = ψ (A, s x s(t)) = φ t φ x (A, s) = xφ (A, s) = φ x t A d (A, s x d ) = φ d s(t) (A, s x s(t) ) = φ(a, s) = φx t 6.1. (φ ψ) φ ψ 6.2. Γ A s Γ Γ 2 1 1 Andreas Blass 1947-2
6 2 1929 1930 2 1949 3 6.2 ( ). (a) Γ = φ Γ φ (b)?? (a) (b)?? (b) Γ Γ xφ φ x c, c xψ ψ x c c L C = {c 0, c 1, } L C Γ Γ L C β L C Γ β β Γ (β β ) L β β β L Γ L C φ x Γ xφ φ x c, c 4 L C (φ, x) (φ 1, x 1 ), (φ 2, x 2 ), 2 Leon Henkin (1921-2006) 3 4 L 0 = L C 0 L 0 L 1 = L 0 C 0 C 1 L 1 ω 3
2 6 θ 1 x 1 φ 1 (φ 1 ) x 1 c i1, c i1 φ 1 k {θ 1, θ 2,, θ k } θ k+1 x k+1 φ k+1 (φ k+1 ) x k+1 c ik+1, c ik+1 φ 1, φ k, φ k+1, θ 1,, θ k Θ = {θ 1, θ 2, } Γ Θ Γ m 0 Γ {θ 1,, θ m+1 } mraa Γ {θ 1,, θ m } θ m+1 θ m+1 xφ φ x c Γ {θ 1,, θ m } xφ, Γ {θ 1,, θ m } φ x c c m Γ {θ 1,, θ m } xφ, Γ Θ φ φ ( φ) φ φ ( φ) φ Θ Γ Θ L C A E A 4
6 2 (a) A L C (b) E A (u, t) E A u t (c) n- P n- P A (t 1, t 2,, t n ) P A P t 1 t 2 t n (d) n- f f A f A (t 1, t 2,, t n ) = ft 1 t 2 t n (e) c c A = c s : V A v s(v) = v 6.2. t s(t) = t φ (A, s) = φ φ φ φ E : t s(t) = t φ k (A, s) = φ φ k = 0 φ φ P t 1 t 2 t n (A, s) = φ (A, s) = P t 1 t 2 t n (s(t 1 ), s(t 2 ),, s(t n )) P A (t 1, t 2,, t n ) P A P t 1 t 2 t n φ u t (A, s) = φ (A, s) = uet (s(u), s(t)) E A (u, t) E A u t k k + 1 φ φ ψ α β xψ ψ, α β k φ ψ 5
2 6 φ α β (A, s) = (α β) (A, s) = α (A, s) = β, α β, α β α β (α β) (α β) (α β) α [α β] α β (A, s) = (α β) φ xψ (A, s) = xψ xψ xψ ( xψ) c xψ ψ x c c (A, s) = xψ (A, s x c ) = ψ (A, s) = (ψ ) x c (A, s) = (ψ x c ) ψ x c ψ x c ( xψ) θ xψ ϕ ϕ ψ t t ϕ x (A, s) = xψ (A, s x t ) = ψ t (A, s x t ) = ϕ ψ ϕ (A, s) = (ϕ x t ) ϕ x t xϕ xψ A s d x(x d) c d c c d 6
6 2 c d A A = c d c A = d A c = d c d A/E A E A c, d c d 6.3. E A A (1) E A A (2) n- P t i u i i = 1, 2,, n i n t i E A u i (t 1, t 2,, t n ) P A (u 1, u 2,, u n ) P A (3) n- f t i u i i = 1, 2,, n i n t i E A u i f A (t 1, t 2,, t n )E A f A (u 1, u 2,, u n ) :?? A t [t] A/E (a) A/E = {[t] : t A } t [t] (b) n- P ([t 1 ], [t 2 ],, [t n ]) P A/E (t 1, t 2,, t n ) P A (c) n- f f A/E ([t 1 ], [t 2 ],, [t n ]) = [f A (t 1, t 2,, t n )] (d) c c A/E = [c A ] 6.4. φ (A/E, S) = φ φ S S(v) = [v] S s r R v R(v) = [r(v)] 6.2 7
2 6 : 6.2 (A/E, S) = φ (A, s) = φ φ r (A/E, R) = φ (A, r) = φ R r t t R(t) = [r(t)] u r x u R x [u] φ φ P t 1 t 2 t n P n- (A/E, R) = P t 1 t 2 t n (R(t 1 ), R(t 2 ),, R(t n )) P A/E ([r(t 1 )], [r(t 2 )],, [r(t n )]) P A/E (r(t 1 ), r(t 2 ),, r(t n )) P A (A, r) = P t 1 t 2 t n φ t t (A/E, R) = t t R(t) = R(t ) [r(t)] = [r(t )] r(t)e A r(t ) (A, r) = (t t ) φ xψ (A/E, R) = φ u (A/E, R[u]) x = ψ u (A, ru) x = ψ (A, r) = xψ (A, r) = φ 6.4 L L L C A/E L 8
6 3 3???? [?] 5 Γ Γ Γ Γ Γ Γ Γ α Γ Γ =, α, α Γ ( ) Γ 0 Γ 1 ( ) Γ = (α 0 α 1 ), Γ = α 0, α 1, ( ) Γ = (α 0 α 1 ), i = 0, 1 Γ i = α i, ( ) Γ = xβ(x), Γ = β(v j ), v j ( ) Γ = xβ(x), Γ = β(v k ), v k v 0, v 1, v 2, xβ(x) 5 Weak König Lemma (WKL 0 ) Dénes König 1884-1944 9
3 6 Γ, Γ, Γ, Γ Γ, Γ, Γ 0 Γ 1 Γ Γ Γ Γ ( ) Γ 0 Γ 1 Γ p (a) (b) p Γ A A N P j (i 1, i 2,, i n ) P A j P j (v i1, v i2,, v in ) p 6.5. s s(v i ) = i p α (A, s) = α : α α P j (v i1, v i2,, v in )(A, s) = α 1 α P j (v i1, v i2,, v in ) p P j (v i1, v i2,, v in ) p (A, s) = P j (v i1, v i2,, v in ) (A, s) = α 2 α α 0 α 1 α α 0 α 1 p (A, s) = α 0 (A, s) = α 1 (A, s) = α 3 α α 0 α 1 α α 0 α 1 p (A, s) = α 0 (A, s) = α 1 (A, s) = α 4 α xβ(x) α β(v j ) p (A, s) = β(v j ) (A, s) = α 5 α xβ(x) α j- p β(v j ) p i β(v i ) p i (A, s) = β(v i ) (A, s) = α 6.3 ( 1936). Γ Γ : Γ = Γ Γ Γ 10
6 4 4 6.3 ( ). (a) Γ = φ Γ Γ 0 Γ 0 = φ (b) Γ Γ 0 Γ :?? 6.4. Σ :???? k 2 k k 2 = df v 1 v 2 v 1 v 2, 3 = df v 1 v 2 v 3 (v 1 v 2 v 2 v 3 v 1 v 3 ) Γ = Σ { 2, 3, } Γ Γ Γ Σ 6.4. L L EC EC 1. 6.4 6.4 2. 6.4 6.1. A = (N, 0, S, <, +, ) B A 11
4 6 A A A A Th A Th A = {σ : A = σ} 6.6. B Th A B A : : c Σ = {0 < c, S0 < c, SS0 < c, } Σ Th A Σ 0 Σ 0 Σ k c k Th A c Σ Th A B B Th A A B B A h : B A m = h(c A ) 0 < c, S0 < c,, SS }{{ S} 0 < c B h m + 1 m m?? 6 6 Per Lindström 1936-2009 12