i iii 1 ZFC Skolem

i iii 1 ZFC 1 1.1................... 2 1.2........................... 4 1.3 Skolem..................... 6 1.4...................... 8 11 2 13 2.1..................... 13 2.2........ 15 2.3......................... 19 21 3 Yet Another Walk Tutorial 23 3.1 Minimal walks, colorings and lines.................... 25 3.2 Walks and Trees.............................. 32 3.3 Trees and Lines.............................. 33 3.4 Basis theorem............................... 35 39 4 41 4.1 42 4.2.......................... 47 4.3............. 50 4.4............................ 54 59 G is for Girl 61

iii Gainax Panty & Stocking with Garterbelt OCaml J Garrigue

iv scheme C ocaml turtle graphics GUI Java Smalltalk Department of Polymathematics

v Science of Philosophy of Science

1 1 ZFC 1963, Paul Cohen, ZFC(Zermelo-Fraenkel ). Cohen, ZFC Forcing. Cohen, ZFC,..,.,, ZFC. ZFC Skolem,, 1.,. 1. (, ) (,. Löwenheim-Skolem )., [2]..,. [5], [3], [1].

2 1 ZFC, [4], [6]. K.,. Y.,. K. 1.1 Y,. *1,, K,, ZFC Y, K., Y ZFC, Cohen K., ZFC Gödel 1940, Cohen, ZFC..,, φ ZFC, Y K ZFC φ φ, ZFC + φ. Y,. ZFC φ *2., ZFC + φ ZFC, ZFC + φ φ., φ ZFC + φ 1, ZFC + φ φ., ZFC + φ φ,., ZFC φ ZFC + φ *1. 2 ℵ 0 = ℵ 1. *2 T φ, T φ, T φ.

1.1 3., ZFC + φ ZFC φ. ZFC + φ, ZFC φ K,. φ CH(Continuum Hypothesis), ZFC CH, ZFC + CH Y.. K *3,. 1. ( ) Y. K.., *4.., *5. T M, T φ φ, M φ φ., T φ, T φ,.. φ, φ x(x x = e) ( e ). φ, Y K Y φ φ, Z + ( 0), 1 + 1 = 2 0, φ. φ. φ. {e} φ.. φ. K.,,, ZFC., φ φ, φ φ Y,,, K *3. *4,,. *5.

4 1 ZFC 1.1 Y. ZFC + CH, ZFC + CH,, CH ZFC.. CH ZFC K., φ ZFC, φ ZFC ZFC φ, φ ZFC ZFC φ,., Gödel, Cohen 1.2 Y, ZFC K, V Y. (= 0), ( ) K. V. ( 1). V α, α. x P(x) x, V 1 =P( ) = { } = {0}, V 2 = P({0}) = {0, {0}} = {0, 1} Y K, V ZFC *6, *6 (V, ), V,,.

1.2 5., V, (ℵ 2 ). ℵ 1 Y V K Y V. K, Y K. V, ZFC,, *7.,, Y, ZFC Löwenheim-Skolem *8 Skolem *9 K. ZFC, Löwenheim-Skolem, ZFC.,, ZFC., ZFC, M M E (M, E), E V M -., x(x M x M), M (transitive). -. * 10. * 11,, ZFC - * 12. ( 2) Y V M, V ω. K V ω,.., ZFC *7, V. *8 Löwenheim-Skolem,. *9 ZFC, ZFC., ZFC..,. *10 Mostowski. [5] III,IV. *11 Gödel, ZFC - ZFC, ZFC - ZFC.. [5] VII 1. *12, -

6 1 ZFC 1.2 ZFC. Y ω 1 (= ℵ 1 ) M. K ω 1 M Y K M. ω 1 M Y, M K., M ZFC. ZFC ω 1. ω 1 M. Y, Skolem. K M ω 1 V ω 1. ZFC,., ZFC,. (absoluteness) 1.3 Skolem K ω 1,. {1, 2} N., 0 =, 1 = {0}, 2 = {0, 1}. N ZFC., N, N. Y, N K, Y, x(x y) y K N. x N(x y) N, N, N * 13 *13 N N.

1.3 Skolem 7 N 1 2 = {0, 1}, 2 1 = {0}. N N 1 K. V N. = N = 1., N., N Y, 1 N, 1 N K.,., M ZFC * 14., M = Y, M M M M. a, a M a M. M M, M. a, M = K., M. 1,2,..., ω ω = ω M,., α M M, V, V α M M. ZFC.,,,.. ZFC, Y,, K [5] [2], ω 1. Skolem, M ZFC M ω 1, M, Y M ω 1, ω M 1 M, V ω 1 K. ( 3). ω1 M ωm 5 ωm ω, V ω 1 Y, ω1 M M ω 1, M ω(= ω M ) ω1 M. V ω ω M 1, K. V M, M V Y Skolem, [5] IV. *14 ZFC, ZFC.

8 1 ZFC 1.3 M V 1.4 Y ZFC. M, OK., K M M M., G. G. M[G]. G M. M[G] M, G ZFC Y M[G] M G K R x R[x],. R {x} R[x]. M {G} ZFC M[G]. ( 4). G M, M M Y,? K M M[G]. On, M On = M[G] On. M[G] Y, M[G] ZFC., G K. (poset), (dense subset), (filter).

1.4 ジェネリック拡大と基数の保存 9 ふ[G 図 1.4 ジェネリック拡大 図 1.5 M の基数と M [G] の基数 だそこに関してはテクニカルだけど概念自体が難解ということはないので教科書を読み進 めるのにそれほど苦労はないと思う. 定義も言ってないからもう雰囲気だけ感じてほしい んだけど, ジェネリックというのは poset のフィルターで, その poset の全ての稠密部分 集合と交わるようなもののこと. どのような poset を考えるかによって M[G] で何が成り 立つようになるかが変わってくる. G はたとえば実数を ω2m 個なり ω7m 個なりコーディ ングした集合だけど, 別の poset を用いることで実数以外にも色んなジェネリックを付け 加えることができる. たとえば無限ツリー構造における無限長のパス (path) とか. ま, そ のへんもおいおいね. さて, 一つ言っておきたいのは, 単に実数をたくさん加えただけじゃ必ずしも M [G] で 連続体仮説の否定が成り立つとは保証されないということかな. 難しいのはそこ. どうし てだかわかる Y いえ. そうなんですか K なぜかというと, M と M [G] でどの順序数が ω1 かが変わってしまうかもしれないか ら. たとえば図 5 を見て. この図では, ω1m が M [G] では基数ではなくただの可算順序数 M [G] に 崩壊 してしまっている. あと ω2m =ω1 になったりしてるね Y ω1m が V にとっては可算順序数になってしまうのと同じですよね K うん. ジェネリック拡大の際, 何が起こるとこういうことになるかわかる

Y ω M 1 M[G], M[G] ωm 1 ω. M K. ω2 M, M[G] ωm[g] 1, M, M[G] Y K Cohen, M M[G]..., poset ccc(countable chain condition, )., M[G]. Y K,,. M, M[G]

11 [1]... 2011. [2].. 20 4.. 2007. [3].. 2007. http://math.cs.kitami-it.ac.jp/~fuchino/shizuoka/lss07_fuchinox.pdf [4].. http://d.hatena.ne.jp/tri_iro/20070105/ 1168660699 [5],./... 2008. [6].. http://www.math.tohoku.ac.jp/~y-keita/old/usuba_tokodai.pdf

13 2 2.1 20 f(x) = { 0 (x 1) 1 (x > 1) ε δ *1 *1

14 2 *2 7 * 3 *4 *2 *3 *4

2.2 15 *5 20 *6 *7 2.2 19 *5 *6 *7

16 2 *8 P P x P x P 0 100 *8 ZFC

2.2 17 RCA 0 RCA 0 D = {(x, y) R 2 x 2 + y 2 1} f : D D f(p) = p p D f RCA 0 * 9 * 10 1, 5, 7, 3, 5, 9, 2, 0, 5, 5, 5, 7, 3, 8, 9, 4, 5, 3, 7, 8, 3, 5, 6, *9 *10

18 2 * 11 { 0 (x 1) f(x) = 1 (x > 1) ( ) n 10 n r n 0 r > 1 f(r) = 1 r < 1 f(r) = 0 1.000000000 0.99999999999 r = 1 r r r * 12 k {a n } k K {b n } *11 *12 r 0 1

2.3 19 * 13 2.3 forcing semantics sheaf semantics * 14 poset pull back forcing Grothendieck *13 *14 δ : C Ĉ = SetsCop aĉ Sh(C J) J C limit colimit

sheaf semantics SGL poset forcing coq intros coq ε δ

21 [1] Saunders MacLane Ieke Moerdijk Sheaves in Geometry and Logic: A First Introduction to Topos Theory Springer; 1st ed 1992 Corr 2nd printing 1994 (1992/04)

23 3 Yet Another Walk Tutorial Todorcevic minimal walk walk walk constructivity *1 coherency *2 walk Todorcevic Todorcevic expository (Todorcevic [7] [8] ) minimal walk walk walk walk J.T. Moore 2 work five element basis([6]) L-space problem ([5]) walk walk Moore walk five element basis Todorcevic [7] Moore [6] walk Aronszajn Countryman Shelah walk ( [4] Todorcevic ) walk theory *1 ω ω 2 ω ω ω ωω... = ϵ 0 recursive *2 (coherent)

24 3 Yet Another Walk Tutorial Aronszajn Specker Baumgartner Countryman walk ZFC combinatorics Erdös Rado Galvin(Shelah pcf ) combinatorics walk Todorcevic Todorcevic dis Todorcevic self-contained walk T walk explicit ZFC α β γ otp(x) X L X L cofinal y L x X y x ω ω 1 ω 2 index ω = N ω 1 x 0, x 1,..., x n x i σ τ σ τ σ τ σ τ = [X] n X n X <ω X α X <α α X C-sequence C α α < ω 1 fix 1. C α+1 = {α}. 2. α C α α cofinal otp(c α ) = ω. 3. α C α * 3 *3

3.1 Minimal walks, colorings and lines 25 3.1 β α minimal walk 1 walk 2 walk interaction 3 interaction 4 walk Basis Problem 3.1 Minimal walks, colorings and lines 3.1.1 (step). α < β < ω 1 β α step min(c β \ α)(< β) 3.1.2 (walk). α β < ω 1 β α walk( minimal walk) β α step β 0 = β; β i+1 = min(c βi \ α); (unless β i = α), ordinal β i i n last step β n = α 3.1.3 (full code). α β < ω 1 ρ 0 (α, β) ω <ω ρ 0 (α, β) = otp(c β0 α),..., otp(c βn 1 α) β i (i n) β α walk n = 0 α = β ρ 0 (α, α) =

26 3 Yet Another Walk Tutorial 3.1.1. α β β i walk i walk β α β i walk β i α walk 3.1.2. α β γ β γ α walk ρ 0 (β, γ) ρ 0 (α, γ) Proof. walk 3.1.3. α < α β < ω 1 β i (i n), β j(j m) β α, α walk j = min{j β j+1 < α β j } 1. β i = β i( i j) 2. β j = β j = α β β proper 3. β j = β j > α C βj α C βj α proper initial segment Proof. (1). By induction. β 0 = β = β 0. β i = β i = η, β i+1 α β i+1 C η \ α β i+1 = min(c η \ α ) = min(c η \ α) = β i+1. (2). (3). β j+1 C βj α β j+1 α C βj α C βj α proper initial segment. 3.1.1. ρ 0 (α, β) ρ 0 (α, β) ( α < α β < ω 1 ) α < β γ β α walk γ α walk walk 3.1.4. α β γ β γ α walk gcw α (β, γ) β α walk γ α walk Remark 3.1.1. α β γ ξ = gcw α (β, γ) ρ 0 (α, β) = ρ 0 (ξ, β) ρ 0 (α, ξ), ρ 0 (α, γ) = ρ 0 (ξ, γ) ρ 0 (α, ξ) gcw Todorcevic full lower trace gcw full lower trace gcw gcw gcd gcd gcw gcw α (β, γ) β γ α walk walk γ walk β

3.1 Minimal walks, colorings and lines 27 3.2 gcw α (β, γ) γ β walk γ β γ walk gcw α (β, γ) 3.1.4. gcw α γ i (i n) γ α walk i = min{j γ j+1 < β γ j } gcw α (β, γ) = { β, if β = γ i, gcw α (γ i+1, β), if β > γ i. 3.1.5 (full lower trace). α β β α full lower trace F (α, β) β i (i n) β α walk n 1 F (α, β) = {α} i=0 ξ C βi α F (ξ, β). F (α, β) α {α} gcw α full lower trace α gcw α full lower trace 3.1.5. β γ α < β gcw α (β, γ) F (β, γ) full lower trace common walk ρ 0 (α, β) = ρ 0 (min(f (β, γ) \ α), β) ρ 0 (α, min(f (β, γ) \ α)),

28 3 Yet Another Walk Tutorial ρ 0 (α, γ) = ρ 0 (min(f (β, γ) \ α), γ) ρ 0 (α, min(f (β, γ) \ α)), Proof. full lower trace gcw α ( 1.3 full lower trace γ α walk γ β walk walk γ β!) Todorcevic γ 1 = min(c γ \α) γ 1 = min(c γ \β) α 1 = min(f (β, γ)\α) α 1 F (ξ, β) ξ C γ β α 1 F (β, γ 1) ρ 0 (α, β) = ρ 0 (α 1, β) ρ 0 (α, α 1 ) α ξ β ρ 0 (α, β) = ρ 0 (min(f (ξ, β) \ α), β) ρ 0 (α, min(f (ξ, β) \ α)). α 1 = min(f (ξ, β) \ α) α β ξ ρ 0 (α, γ) = ρ 0 (α 1, γ) ρ 0 (α, α 1 ) α γ 1 < β γ 1 C γ β F (γ 1, β) F (β, γ) α 2 = min(f (γ 1, β) \ α) α 2 α 1 ρ 0 (α, γ 1 ) = ρ 0 (α 2, γ 1 ) ρ 0 (α, α 1 ). walk: γ α γ γ 1 α 2 α 1 α walk: γ α 1 α α β γ 1 3.1.6. α β γ F β = F (α, β) F γ = F (α, γ) F β = F γ ρ 0 (, β) F β = ρ 0 (, γ) F γ ρ 0 (, β) α = ρ 0 (, γ) α Proof. ϵ < α ξ ϵβ = min(f β \ ϵ) ξ ϵγ = min(f γ \ ϵ) ξ ϵβ = ξ ϵγ ξ ϵ ρ 0 (ϵ, β) = ρ 0 (ξ ϵ, β) ρ 0 (ϵ, ξ ϵ ), ρ 0 (ϵ, γ) = ρ 0 (ξ ϵ, γ) ρ 0 (ϵ, ξ ϵ ). ξ ϵ F β = F γ ρ 0 (ϵ, β) = ρ 0 (ϵ, γ)

3.1 Minimal walks, colorings and lines 29 ρ 0 (, β) α α fix ρ 0 (, β) α F β fin α + 1 ρ 0 ρ 0 ρ-function 3.1.6 (maximal weight function). α β maximal weight ρ 1 (α, β) β α walk lower traces C βi α max 3.1.7 (number of steps function). α β number of steps ρ 2 (α, β) β α walk 3.1.8 (last step function). α β last step ρ 3 (α, β) walk last step lower trace weight maximal weight β α walk β i (i n) ρ 3 (α, β) = { 1, if C βn 1 α = ρ 2 (α, β) 0, otherwise. ρ-function a : [ω 1 ] 2 X X ω 1 finite-to-one property coherency 3.1.9. ρ [ω 1 ] 2 1. ρ finite-to-one x β < ω 1 {α < β ρ (α, β) = x} 2. ρ coherent β γ {ξ β ρ (ξ, β) ρ (ξ, γ)} 3.1.1. ρ 0 coherent Proof. β < γ C γ β order type n C β n + 1 α α < β α C β α order type n + 1 α < β C γ α order type n α α < β ρ 0 (α, β) ρ 0 (α, γ) coherency 3.1.2. ρ 1 finite-to-one coherent Proof. β γ

30 3 Yet Another Walk Tutorial finite-to-one n < ω A β ρ 1 (η, β) > n η A α β cofinal α = β first step lower trace η A C β η > n α < β β 1 = min(c β \ α) β 1 ρ 1 (ξ, β 1 ) > n ξ A ρ 1 ρ 1 (ξ, β) ρ 1 (ξ, β 1 ) > n coherency A = {ξ < β ρ 1 (ξ, β) ρ 1 (ξ, γ)} otp(a) = ω α = sup A γ 1 = min(c γ \ α) n = C γ α finite-to-one B = {ξ A ξ > max(c γ α) and ρ 1 (ξ, γ 1 ) > n} B A ξ B ρ 1 (ξ, γ) = max{n, ρ 1 (ξ, γ 1 )} = ρ 1 (ξ, γ 1 ) γ 1 β ξ B ρ 1 (ξ, γ 1 ) = ρ 1 (ξ, β) ρ 1 (ξ, β) = ρ 1 (ξ, γ 1 ) = ρ 1 (ξ, γ) ξ B A 3.1.3. ρ 3 coherent 3.1.10 (coloring line). (X, < X ) ρ : [ω 1 ] 2 X ω 1 < α < β ρ (δ αβ, α) < X ρ (δ αβ, β), δ αβ = min{η min(α, β) ρ (η, α) ρ (η, β)} (ω 1, < ) C(ρ ) 3.1.1 (Todorcevic). X = 2, 3,..., or ω X ρ finite-to-one coherent C(ρ ) 2 chain Proof. α β γ δ ρ (, α) : α + 1 X ρ α diff(α, β) = {ξ α ρ (ξ, α) ρ (ξ, β)} coherency diff(α, β) finite n αβ = max{ρ (ξ, α), ρ (ξ, β) ξ diff(α, β)},

3.1 Minimal walks, colorings and lines 31 F αβ = {ξ α max{ρ (ξ, α), ρ (ξ, β)} n αβ } finite-to-one property F αβ finite diff(α, β) F αβ C(ρ ) 2 c : C(ρ ) 2 ω ω <ω ω <ω c(α, β) = (n αβ, ρ α [F αβ ], ρ β [F αβ ]) ρ α [{ξ 0 < ξ 1 <... < ξ n }] ρ α (ξ 0 ),..., ρ α (ξ n ) c C(ρ ) 2 c 1 (n, σ, τ) ( chain ) Claim 3.1.1. α < γ n αβ = n γδ = n ρ α [F αβ ] = ρ γ [F γδ ] ρ β [F αβ ] = ρ δ [F γδ ] β < δ ξ αγ = min{ξ α ρ (ξ, α) ρ (ξ, γ)} ξ = min{ξ αγ, ξ βδ } Claim 3.1.2. ξ αγ = ξ βδ = ξ F αβ ξ αγ = F γδ ξ αγ η Fαβ c ξ αγ (η α, β diff )ρ (η, α) = ρ (η, β) > n η < ξ αγ ρ (η, α) = ρ (η, γ) ρ (η, γ) > n η Fγδ c ξ F αβ ξ βδ = F γδ ξ βδ F αβ ξ αγ = F γδ ξ αγ ξ αγ ξ βδ η < ξ αγ F αβ ρ α ρ γ F ρ β (η) = ρ α (η) = ρ γ (η) = ρ δ (η). η < ξ αγ F αβ diff(α, β) diff(γ, δ) ρ β (η) = ρ δ (η) ρ β ξ αγ = ρ δ ξ αγ ξ βδ ξ αγ ξ βδ ξ βδ ξ αγ ρ (ξ, β) < ρ (ξ, δ) Case 1: ξ F αβ F γδ F αβ ξ = F γδ ξ ρ α (ξ) = ρ γ (ξ) α < γ Case 2: ξ F αβ \ F γδ ξ / F γδ ρ γ (ξ) = ρ δ (ξ) > n ξ F αβ ρ β (ξ) n ρ β (ξ) n < ρ δ (ξ) Case 3: ξ F γδ \ F αβ Case 2 ρ α (ξ) > ρ γ (ξ) Case 4: ξ / F αβ F γδ ξ diff(α, β) diff(γ, δ) ρ β (ξ) = ρ α (ξ) < ρ γ (ξ) = ρ δ (ξ)

32 3 Yet Another Walk Tutorial 3.2 Walks and Trees walk theory walk 3.2.1 (Trees). T = (T, T ) T x T pred(x) = {y T y < T x} < T order type x ht(x) α node α T α T T α = α T ω 1 - ω 1 node ω <ω 1 3.2.2 (Aronszajn ). T Aronszajn T cofinal chain ω 1 - C chain x, y C x y y x T α chain C T cofinal {ht(x) x C} α cofinal König cofinal chain cofinal chain x α T α x β (β < α) node x α (T 2 ) step cofinal chain ω 1 Aronszajn ω ω 1 3.2.1 (Aronszajn). Aronszajn Aronszajn minimal walk Aronszajn ρ-function 3.2.3 (coloring tree). ρ : [ω 1 ] 2 X T (ρ ) = {ρ β α α β < ω 1 } T (ρ ) T 3.2.1. T (ρ 0 ) Aronszajn Proof. T (ρ 0 ) t T dom(t) T (ρ 0 ) ω 1 T (ρ 0 ) ω 1 - ( level )

3.3 Trees and Lines 33 T (ρ 0 ) cofinal branch *4 ρ 0α ω <ω T (ρ 0 ) cofinal branch b : ω 1 ω <ω α < ω 1 β > α ρ 0β α = b α b ρ 0β b ω 1 ω <ω ρ 0α 3.2.4. ω 1 - T X a : T X x, y T x y a 3.2.1. T (ρ 0 ) Aronszajn Remark 3.2.1. Aronszajn Aronszajn ( ZFC ) MA ℵ1 Aronszajn 3.3 Trees and Lines L = (L, ) L L reverse order(l, ) 3.3.1. L. L Aronszajn, ω 1 ω 1 3.3.2 (tree line). T 2 2 2 <α *5 2 T 2 <α lex x < lex y x y or x( (x, y)) < y( (x, y)) (x, y) = min{ξ x(ξ) y(ξ)} (T, lex ) 3.3.3 (line tree). L L binary partition tree T 1. T node L convex set T 0 = {L} 2. I T α immediate successor I I 0, I 1 2 I 0 I left partition I 1 right partition I = 1 I T maximal node *4 branch chain *5 2 <α

34 3 Yet Another Walk Tutorial 3. α I T α I = b cofinal branch b T α 4. I T maximal node I = 1 binary partition tree 3.3.1. 1. 2 T Aronszajn (T, lex ) Aronszajn 2. L Aronszajn binary partition tree Aronszajn Proof([4] ). (1 2): L T = (T, lex ) Case 1. L T ω 1 isomorphic copy X L T ω 1 α < ω 1 {y X y > T x} x T α 2 x, x x < lex x X (, x ) ( ) X ω 1 ω 1 proper initial segment ω 1 proper initial segment x α T α x X x α {x α α < ω 1 } T chain T Aronszajn L T ω 1 Case 2. L T X L T dense set D X D α = sup{ht(x) x X} X T α x T α {y X y > T x} x x X 2 node y 0, y 1 y 0 < lex y 1 y 0 node L T (x, y 1 ) height D D density (2 1): L binary partition tree T L 1 2 Claim 3.3.1. 1. T L 2. α < ω 1 Tα L ω L T L (1) ω 1 ω 1 T L B T L B α < ω 1 B Tα L = {I α } I α T L node L convex set α I α+1 I α left partition right partition (a) J 0 = {α < ω 1 I α+1 left part. } (b) J 1 = {α < ω 1 I α+1 right part. }

3.4 Basis theorem 35 (i = 0, 1) α J i x α I α \I α+1 X i = {x α α J i } Case (a) X 0 ω 1 Case (b) X 1 ω 1 L Aronszajn (b) (b) α Tα L α T L α L I T α x I I x I I T L α L Aronszajn I coinitial cofinal K I I K I T L α K = I K I X = {x I I T L α } K X T L α I T L α disjoint K X x I, x J X (x I < x J ) (x I, x J ) X (x I, x J ) K x I I x J J binary partition tree I, J T L α cofinal branch branch I T L α I J I left partition I0 J disjoint right partition I 1 I disjoint I (x I, x J ) (x I, ) I0 (, x J) I1 K I coinitiality cofinality (x I, x J ) K X L Aronszajn (b) L T L L T L maximal node binary partition tree node I T L maximal I L T L maximal node Aronszajn ad-hoc Aronszajn walk Aronszajn Aronszajn C(ρ ) Aronszajn 3.4 Basis theorem walk theory basis problem

36 3 Yet Another Walk Tutorial Sorgenfrey long line βn ω ω Q ω ω *6 basis 3.4.1. C D C D C basis L C K D L isomorphic copy basis 3.4.1. C {ω 1 } C basis well-order one element basis L L { ω 1 } one element basis 3.4.2. X σ-dense X ℵ 1 3.4.2. C (R, ) D R σ-dense D C basis D basis PFA Baumgartner [2] σ-dense C one element basis Proof. X R ℵ 1 x X X condensation point x V X V X condensation point X X \ X ω X X σ-dense Remark 3.4.1. R copy X condensation point X X X X σ-dense X X dense *6 Ramsey ( ) Ramsey ω 1 Ramsey walk Ramsey

3.4 Basis theorem 37 subset D X D Cantor D Q X R x X L x = {p D p < x} L x D = Q Q Dedekind cut : x L x R X R R basis basis canonical basis ω 1 ω 1 X [R] ℵ1 basis irreducibility 3.4.3. L K L K L K L C minimal K L L K K C 3.4.1. ω 1, ω 1 mininal PFA σ-dense set X R minimal Proof([4] ). ω 1 ω 1 X ω 1 f : X ω 1 f X X ω 1 increasing order ω 1 X ω 1 X = ω 1 PFA σ-dense set Y Y X σ-dense X Y ( subspace ) Y σ-dense X X X Y X Y 4 decompose WO AWO SEP Aronszajn A 3 basis Aronszajn Countryman ( Countryman [3] Coutryman ) 3.4.4. L Countryman Cartesian square L 2 ( (x, y) (z, w) iff x z y w ) chain chain 2 3.4.2. Countryman Aronszajn

38 3 Yet Another Walk Tutorial Proof. ω 1 ω 1 X Countryman Case 1. ω 1 Countryman ω1 2 = n C n C n chain α < ω 1 y- α X α X α X α = n<ω C n X α C n X α n = n α < ω f : ω 1 ω α n α α < β n α = n β chain C n x- C n chain (δ, β) C n X β (γ, α) C n X α γ δ α < β γ δ (γ, α) (δ, β) Case 2. ω 1 Countryman Case 1 Case 3. X Countryman X 2 = n C n X D X y- y X C ny X y n y C ny X y x- projection X d y D C ny (, d y ), C ny (d y, ) f : ω 1 ω D α (n y, d y ) y 0 < y 1 f f(y 0 ) = f(y 1 ) = (n, d) C n chain (x 0, y 0 ) C n (d, ) (x 1, y 1 ) C n (, d) 3.4.1 (Shelah). Countryman Proof. Section 1 C(ρ 1 ) Countryman ( C(ρ 0 ) Countryman ) Remark 3.4.2. Aronszajn T Countryman T coherent (T, lex ) Countryman T (ρ 3 ) Countryman MA ℵ1 basis 3.4.2 (MA ℵ1 ). C(ρ 1 ) minimal MA ℵ1 (Martin s Axiom) Baire 3.4.5. MA ℵ1 ccc compact Hausdorff ℵ 1 ccc(countable chain condition) Remark 3.4.3. MA ℵ1 MA ℵ1

39 H(ℵ 2 ) Σ 1 ϕ ϕ ccc H(ℵ 2 ) Bagaria [1] 3.4.3 (MA ℵ1 ). {C(ρ 1 ), C(ρ 1 )} Countryman basis Countryman set-theoretic MA ℵ1 canonical basis MA ℵ1 PFA basis (Shelah 30 )Moore 3.4.4 (five element basis). PFA {C(ρ 1 ), C(ρ 1 )} Aronszajn two element basis five element basis [1] J. Bagaria, Axioms of generic absoluteness, Logic Colloquium, 2002 [2] J. Baumgartner, All ℵ 1 dense sets of reals can be isomorphic, Fund. Math, 1973 [3] R.S. Countryman, Spaces having a σ-monotone basis, preprint, 1970 [4] K. Kunen, J. Vaughan, Handbook Of Set-Theoretic Topology, North-Holland, 1985 [5] J.T. Moore, A solution to the L space problem, J. Amer. Math. Soc. 19, 2006 [6] J.T. Moore, A five element basis for the uncountable linear orders, Ann. Math., Vol. 163, 2006 [7] S. Todorcevic, Walks On Ordinals And Their Characteristics, Birkhaeuser, 2007 [8] S. Todorcevic, Coherent sequences, Handbook of set theory, 2010

41 4 G R E : (2012/12) ISBN-10: 4621065041 ISBN-13: 978-4621065044 2012/12

42 4 4.1 20 4 4 1 2 3 *1 4 3 4 7 8 *1 subitize subitus

4.1 43 20 20 in on under above - -

44 4 *2 0 1 0 *2

4.1 45 4 * 3 ε δ ε - - x sin( 1 x ) x jump jump into fly land BMI Basic Metaphor of Infinity *3

46 4 [7] 1 2 1 1 5 1 5 2 1 2 5 2 5 4 *4 * 5 *4 *5

4.2 47 4.2 *6 [6] *6

48 4 [3] *7 * 8 *7 := [< 1/2, 1/2, 1/3,... >] *8

4.2 49 0 Q R R *9 R Q *9

50 4 N R R 4.3 e iπ = 1 [4] 0 +

4.3 51

52 4

4.3 53 * 10 * 11 *10 *11 [1] p. 143

54 4 * 12 non-standard 4.4 *12

4.4 55 * 13 *13

56 4 * 14 * 15 *14 [3] *15

4.4 57 x {x} x 1 * 16 * 17 *16 [5] n + 1 K {x 0,..., x n } K n f(x) {x 0,..., x n} {f(x 0 ),..., f(x n)} n V F : V K n+1 f (f(x 0 ),..., f(x n)) V F *17

1 + 2 = 3 =

59 [1] S. Shapiro (1997), Philosophy of Mathematics: Structure and Ontology, Oxford [2] G R E [3] A W [4] [5] [6] G [7] E

61 G is for Girl actress act act L L

62 G is for Girl G G G Girl G G mono Ω

. 2 6 forcing Free! The dark side of Forcing http://proofcafe.org/forcing/ 2013 8 11