Teoria dos conjuntos

Charles Morgan^{∗}

Capítulo 5. Combinátoria infinita.

5.1. Conjunto fechados e ilimitado e conjuntos parados.

Definição. Seja λ um ordinal do tipo limite. Um conjunto D ⊆ λ é ilimitado no λ se ∀α < λ ∃β ∈ D α < β. Um conjunto C ⊆ λ é fechado no λ se para todos ordinais δ < λ do tipo limite, C ∩ δ é ilimitado no δ implica que sup(C ∩ δ) ∈ C. Um conjunto que é fechado e ilimitado no λ é muitos vezes chamado “club” em inglês (“club” quer dizer “closed and unbounded.”)

Exemplos. {γ < λ | γ é um ordinal do tipo limite} e {γ < λ | γ é um limite dos ordinais do tipo limite} são fechado no λ. E são ilimitados se λ é um cardinal.

Você deveria pensar de um conjunto fechado e ilimitado como sendo “grande” em alguma sentido.

Proposição. Seja κ um cardinal regular e F um conjunto de funções finitárias sobre κ com F < κ (i.e., se f ∈ F temos que f : ^{n(f)}κ ⟶ κ para alguma n(f) < ω.) Então, C = {γ < κ | ∀f ∈ F f“^{n(f)}γ ⊆ γ } é fechado e ilimitado.

Demonstração. É claro que C é fechado: se λ < κ é um ordinal do tipo limite e C ∩λ é ilimitado, f ∈ F, f : ^{n(f)}κ ⟶ κ e (α_{0}, …, α_{n−1}) ∈ ^{n(f)}λ então existe um γ ∈ (C ∩λ)\max({α_{0}, …, α_{n−1} }), e temos que f(α_{0}, …, α_{n−1}) < γ < λ.

Para ver que C é ilimitado, defina G_{0}(X) = X, G_{n+1}(X) = G_{n}(X)∪⋃{β | ∃α_{0}, …, α_{n−1} ∈ G_{n}(X) ∃f ∈ F f(α_{0}, …, α_{n−1}) = β }, para cada, n < ω e G(X) = ⋃_{n∈ω} G_{n}(X) para cada subconjunto X do κ. Se ξ < κ é claro que ξ ⊆ G(ξ) ⊆ κ e G(ξ) < κ. Porque κ é regular podemos escolhar g(ξ) = min(κ \ sup(G(ξ))). Seja g_{n+1}(ξ) = g(g_{n}(ξ)) para qualquer ξ < κ, e seja g_{ω}(ξ) = sup{g_{n}(ξ) | n ∈ ω }. Então temos que g_{ω}(ξ) ∈ C e ξ < g_{ω}(ξ).

Definição. Se C é um conjunto fechado e ilimitado e g : κ ⟶ C enumera C na ordem crescente, seja C′ = g“{ωγ | γ < κ}. C′, ⊆ C, é o conjunto do puntos do tipo limite de C.

Lema. Seja C é um conjunto fechado e ilimitado e define f : κ ⟶ κ pelo f(γ) = min(C \ (γ + 1)). Então C′ = {γ < κ | f“γ ⊆ γ }, e logo C′ é fechado e ilimitado.

Demonstração. É claro que C′ = {γ < κ | f“γ ⊆ γ }, e, então, pela proposição prévia, é fechado e ilimitado.

Proposição. Seja κ um cardinal com ω < cf (κ), seja μ < cf (κ), e seja C_{α} fechado e ilimitado no κ para cada α < μ. Então D = ⋂{C_{α} | α < μ} é fechado e ilimitado no κ.

∗ versão 1.2, 19/12/00

Demonstração. É facil ver que D é fechado. Agora seja f_{α}(γ) = min(C_{α} \ γ + 1) para γ < κ e para todos α < μ. D é ilimitado porque, pela proposição prévia, {γ < κ | ∀α < μ f_{α}“γ ⊆ γ } é ilimitado (e fechado), e é um subconjunto do D pela lema.

Definição. Seja κ um cardinal com ω < cf (κ). Un conjunto S ⊆ κ é parado se S ∩ C ≠ ∅ para todos C que são fechado e ilimitado no κ. Un conjunto X ⊆ κ é não-parado se não é parado.

Exemplos. A proposição fala que qualquer união do menos que cf (κ) conjuntos não-parados é não parado. Seja μ < cf (κ) um cardinal do tipo regular. Então {α < κ | cf (α) = μ} é parado, porque se C é fechado e ilimitado no κ o elemento μ^{o} na enumeração crescente do C tem cofinalidade μ.

Conjuntos parados são do tamanho “medio” como subconjuntos do κ e conjuntos não-parados são “pequenos” – não obstante podem ter cardinalidade κ.

Proposição. Seja κ = μ^{+} e S parado no κ. Então existe S_{α} para α < κ com S = ⋃{S_{α} | α < κ} e S_{α} ∩ S_{β} = ∅ para cada par α, β < κ com α ≠ β.

Demonstração. Seja f_{γ} : γ ⟶ μ uma injeção para cada γ < κ. Defina S_{α}^{ξ} = {γ | α < γ < κ & f_{γ}(α) = ξ } ⊆ κ. Então S_{α}^{ξ} ∩ S_{β}^{ξ} = ∅ se α ≠ β para cada ξ < μ porque cada f_{γ} é uma injeção. Também temos que ⋃_{ξ<μ} S_{α}^{ξ} = {γ | α < γ < κ} é parado no κ. Porque uma união do menos que κ subconjuntos do κ não-parados é não-parada, deve ser que para cada α existe um ξ_{α} < μ tal que S_{α}^{ξ_{α}} é parado. Porque μ < κ existe um ξ < κ tal que {α < κ | ξ = ξ_{α} } = κ. Seja A = {α < κ | ξ = ξ_{α} } é α_{0} = min(A). Defina S_{α} = S_{α}^{ξ} para α ∈ A \ {α_{0} }, e defina S_{α_{0}} = S \ ⋃{S_{α}^{ξ} | α ∈ A \ {α_{0} }} (logo S_{α_{0}}^{ξ} ⊆ S_{α_{0}}). Temos que S_{α} ⊆ S é parado para cada α ∈ A e S_{α} ≠ S_{β} onde α, β ∈ A e α ≠ β.

Fato. Com um pouco mais trabalho podemos mostrar a proposição para todos cardinais regulares e não só para cardinais do tipo sucessor como cá.

Proposição. (Intersecções diagonais) Seja κ um cardinal do tipo regular e seja C_{α} fechado e ilimitado no κ para cada α < κ. Então D = {β | ∀α < β (β ∈ C_{α})} (= {β | β ∈ ⋂_{α<β} C_{α})}) é fechado e ilimitado no κ.

Demonstração. É facil ver que D é fechado: se λ é um ordinal do tipo limite e D ∩ λ é ilimitado no λ temos que ∀α < λ ∃β (α ≤ β < λ & ∀γ < β β ∈ C_{γ}). Logo ∀α < λ ∃β (α ≤ β < λ & β ∈ C_{α}). Logo C_{α} ∩ λ é ilimitado no λ para todos α < λ. Então λ ∈ ⋂{C_{α} | α < λ}.

Para ver que D é ilimitado, defina g(γ) = min(⋂_{α<γ} C_{α} \ γ) para todos γ < κ. (Nota que esta intersecção é ilimitada pela proposição que uma intersecção de menos que κ conjuntos fechados e ilimitados é fechado e ilimitado, então g(γ) é bem-definido.) Agora sejam β < κ, β_{0} = β, β_{n+1} = g(β_{n}) para n < ω, e β_{ω} = sup{β_{n} | n < ω }. Então β_{ω} ∈ D.

Proposição. (Lema de Fodor) Seja κ regular, ω < κ, seja S um subconjunto parado do κ e seja f : S ⟶ κ tal que f(α) ∈ α para cada α ∈ S. Então existe γ < κ tal que {α ∈ S | f(α) = γ } é parado no κ.

Demonstração. Se a conclusão fale, escolhar para cada γ ∈ κ um conjunto C_{γ} que é fechado e ilimitado no κ e tal que C_{γ} ∩ f^{−1}“{γ } = ∅. Seja D = {β | ∀γ < β (β ∈ C_{γ})}. A proposição prévia fala que D é fechado e ilimitado no κ. Mas D ∩ S = ∅, porque se β ∈ D temos que f(β) ≠ α para cada α < β. Uma contradição para a suposição que S é parado.

5.2 Teorema de Silver.

Agora vamos utilisar estes conceitos dos conjuntos fechados e ilimitados e dos conjuntos parados para mostrar o teorema de Silver sobre exponenciação nos cardinais sigulares com cofinalidade maior que ω que foi mencionado no fim da §4.4. É útil ter mais uma definição.

Definição. Seja F ⊆ ^{ω_{1}}ω_{ω_{1}} chamado (uma família) diferente finalmente se ∀f, g ∈ F (f ≠ g ⟶ {α | f(α) = g(α)} ≤ ω.

Teorema. (Silver, 1975) Se 2^{ℵ_{α}} = ℵ_{α+1} para todos α < ω_{1}, ent̃ao 2^{ℵ_{ω_{1}}} = ℵ_{ω_{1}+1}

Demonstração. Pelo hipotese da teorema, suphonamos que P(ω_{α}) = {X_{β}^{α} | β < ω_{α+1} } para todos α < ω_{1}. Então para cada X ⊆ ω_{ω_{1}} e α < ω_{1} existe uma β < ω_{α+1} tal que X ∩ ω_{α} = X_{β}^{α}. Logo podemos definir para cada X ⊆ ω_{ω_{1}} uma função f_{X} : ω_{1} ⟶ ω_{ω_{1}} pelo f_{X}(α) = β se X ∩ ω_{α} = X_{β}^{α} tal que f_{X}(α) < ω_{α+1}. Nota que F = {f_{X} | X ∈ P(ω_{ω_{1}})} é diferente finalmente porque X ≠ Y implica que existe α < ω_{1} tal que f_{X}(α) ≠ f_{Y} (α), e f_{X}(α) ≠ f_{Y} (α) implica f_{X}(γ) ≠ f_{Y} (γ) para cada γ ≥ α.

Agora dar uma ordem parcial para F pelo f < g se e só se {α < ω_{1} | g(α) ≤ f(α)} é um conjunto não-parado no ω_{1}. Pelo o lema de Zorn seja ≺ qualquer ordem total que estende <. (Veja Exercício 3.2.a.) Logo se f ≺ g temos que {α < ω_{1} | f(α) < g(α)} é um parado no ω_{1}. Seja F_{g} = {f ∈ F | f ≺ g }. Vamos mostrar que F_{g} ≤ ω_{ω_{1}} para cada g ∈ F, que dará a teorema.

Para fazer isso vamos usar duas lemas.

Lema. Se G é diferente finalmente e ∀g ∈ G {α | g(α) < ω_{α} } é parado, então G ≤ ω_{ω_{1}}.

Demonstração. Suphonamos que f ∈ G. Seja g : {α < ω_{1} | α = ⋃ α} ⟶ ω_{1} definido pelo g(α) = o mínimo γ < α tal que f(α) < κ_{γ}. Pela lema de Fodor existe um subconjunto parado S_{f} de {α < ω_{1} | α = ⋃ α} e um γ_{f} < ω_{1} tal que g(α) = γ_{f} para todos α ∈ S_{f}. Logo, se ω_{ω_{1}} < G existe um subconjunto G′ ⊆ G, um γ < ω_{1}, um conjunto parado S ⊆ ω_{1} tal que ω_{ω_{1}} < G′ e ∀f ∈ G′ (γ_{f}, S_{f}) = (γ, S). Porque G é diferente finalmente deve ser que ∀f, g ∈ G′ (f ≠ g ⟶ f|S ≠ g|S). Mas temos ^{S}ω_{γ} = ω_{γ}^{ω_{1}} ≤ max({ω_{γ}^{ω_{γ}} , ω_{1}^{ω_{1}} }) = max({2^{ω_{γ}} , 2^{ω_{1}} }) = max({ω_{γ}^{+}, ω_{2} }) ≤ κ. Uma contradição! Então G ≤ κ, como desejamos.

O outro lema reduze crumente o que ficar da demonstração para a situação desta lema última.

Lema. Se f : ω_{1} ⟶ ω_{ω_{1}} é tal que f(α) < ω_{α+1} para cada α ∈ ω_{1}, G é diferente finalmente e ∀g ∈ G {α | g(α) < f(α)} é parado, então G ≤ ω_{ω_{1}}.

Demonstração. Para cada α < ω seja h_{α} : f(α) ⟶ ω_{α} uma injeção. Para cada g ∈ G defina g′ : ω_{1} ⟶ ω_{ω_{1}} pelo g′(α) = h_{α}(g(α)) e seja G′ = {g′ | g ∈ G }. Então G′ satisfaz o hipotese da lema prévia. Mas porque todos as funções h_{α} são injeções, g′ = k′ ⟶ g = k. Então G′ = G′ ≤ ω_{ω_{1}}.

Então F_{g} ≤ ω_{ω_{1}} para cada g ∈ F, e, logo, F ≤ ω_{ω_{1}+1}. Então F = 2^{ω_{ω_{1}}} = ω_{ω_{1}+1}.

Corolário para a demonstração. Seja κ um cardinal do tipo limite e singular com cf (κ) = θ < κ e c : θ ⟶ κ cofinal. Se existe um subconjunto parado T ⊆ θ tal que 2^{c(μ)} = c(μ)^{+} para todos μ < θ, então 2^{κ} = κ^{+}.

5.3. Teorema de Ramsey.

Vamos ver na seção proxima um outro uso das noções dos conjuntos fechados e ilimitados e conjuntos parados. Este aplicação será na teoria dos grafos.

Definição. Um grafo é um par (X, A) onde X é um conjunto (dos vértices ou nós) e onde A ⊆ X × X \ {(x, x) | x ∈ X } (dos arestes). Um outro modo de falar a mesma coisa é falar que um grafo é um conjunto X com uma relação binária A tal que A é símetrico e anti-reflexivo.^{1} Somos interesados nos grafos só até isomorfismo onde (X, A) ≅ (Y, B) se existe uma bijeção f : X ⟶ Y tal que (x, y) ∈ A ⟺ (f(x), f(y)) ∈ B.

Tem muitos exemplos dos grafos, do dois finitos e infinitos. Entre eles são grafos completos: grafos da forma (X, B) onde para cada par {x, y } dos membros do X com x ≠ y tem (x, y) ∈ B. Escrevemos K_{κ} para o grafo completo do tamanho κ. (Claro que é único até isomorfismo.) Por exemplo, temos que K_{3} é um triangulo e K_{4} é um quadro com os diagonais.

Definição. H = (Y, B) é um subgrafo do G = (X, A) se Y ⊆ X e B = A ∩ (Y × Y). Então H tem todos os arestes que G tem entre vértices no Y.

Definição. Uma coloração de um grafo G = (X, A) com γ cores é uma função f : A ⟶ γ.

A teorema do Ramsey na forma o mais simples fala que para qualquer coloração finita f do grafo infinito enumerável K_{ω} existe um subgrafo G = (X, A) do K_{ω} tal que G ≅ K_{ω} é todos os arestes do G tem o mesmo cor: {f(e) | e ∈ A} = 1. Falamos que G é monocromático. Tem, também um versão finito da teorema que pode, deduzir deste versão infinito: para qualquer n < ω e r < ω existe m < ω tal que para qualquer coloração f do K_{m} existe um subgrafo G do K_{m} tal que G ≅ K_{n}. Na verdade vale a pena mostrar uma extensão pequena da teorema que tem mas ou menos a mesma demonstração.

Definição. Para qualquer conjunto x e qualquer cardinal κ seja [x]^{κ} = {y ⊆ x | y = κ}.

Teorema de Ramsey. (1930) Sejam n, r < ω. Se f : [ω]^{n} ⟶ r, existe X ∈ [ω]^{ω} (então um subconjunto infinito do ω) e existe um p < r tal que f“[X]^{n} = {p}. (I.e., para qualquer coloração do conjunto dos subconjuntos do tamanho n do ω com r cores existe um subconjunto infinito X do ω tal que todos os subconjuntos do X do tamanho r ganham o mesmo cor.)

Primeiramente, observe a lema seguinte que vamos usar várias vezes na demonstração.

Lema. Sejam n, r < ω e f : [ω]^{n+1} ⟶ r. Suponhamos que Z ∈ [ω]^{ω}, x ∈ [Z]^{n}, e para cada p < r seja x_{p} = {s ∈ Z | s ∉ x & f(x ∪ {s}) = p}. Então ao menos um dos conjuntos x_{p} é infinito.

1 Para pegar mais informação sobre a teoria de grafos posso recomendar para você os livros de Bela Bollobas, Graph

Theory: An introductory course, Springer, 1979 (na biblioteca) ou Bela Bollobas, Combinatorics, Cambridge University Press, 1986? (não na biblioteca).

Demonstração da lema. Se cada x_{p} fosse finito teríamos que Z \ x = ⋃{x_{p} | p < r} seria uma união finita dos conjuntos finitos, logo finito. Uma contradição!

bf Demonstração da teorema de Ramsey. A demonstração é pela indução sobre n. Então o caso primeiro é n = 1, e neste caso temos uma f : [ω]^{1} ⟶ r. Seja y_{p} = {m ∈ ω | f({m}) = p} para cada p < r. Então pela lema (ao menos) um dos conjuntos y_{p} é infinito, como precisamos.

Agora suponhamos que temos mostrado a teorema para n e qualquer r < ω. Sejam r < ω e f : [ω]^{n+1} ⟶ r. Vamos definir uma coloração g : [ω]^{n} ⟶ r usando f. Então se x ∈ [ω]^{n} seja, usando a lema, g(x) = p se p é mínimo tal que existe um conjunto infinito dos s < ω tal que f(x ∪ {s}) = p.

Vamos definir uma seqüência dos conjuntos infinitos X_{i} para i < ω com X_{0} = ω e X_{i+1} ⊆ X_{i} e definir a_{i} = min(X_{i}). Para i < n seja X_{i+1} = X_{i} \ {a_{i} }. Na contramão suphamos que temos ⟨a_{i} | i ≤ j ⟩ e ⟨X_{i} | i ≤ j ⟩ para alguma n − 1 ≤ j < ω. Seja ⟨y_{k} | k < l⟩ uma enumeração do [{a_{i} | i < j }]^{n} para alguma l < ω. Vamos definir um conjunto infinito Y_{k} para k ≤ l com Y_{0} = X_{j} \(a_{j} +1) e Y_{k+1} ⊆ Y_{k} e definirimos X_{j+1} = Y_{k}. Seja, pela lema de novo, q_{k} < r mínimo tal que existe um subconjunto infinito Y do Y_{k} tal que para todos b ∈ Y temos que f(y_{k} ∪ {b}) = q_{k}, e seja Y_{k+1} = {b ∈ Y_{k} | f(y_{k} ∪ {b}) = q_{k} }.

Seja X = {a_{i} | i < ω }. Pelo teorema para n temos que existe um conjunto Z ∈ [X]^{ω} e um cor q < r tal que g“[Z]^{n} = {q }. Vamos mostrar que f“[Z]^{n+1} = 1 também. Sejam x_{0}, x_{1} ∈ [Z]^{n+1} com b_{0} = max(x_{0}) e b_{1} = max(x_{1}), e sejam y_{0} = x_{0} \ {b_{0} } e y_{1} = x_{1} \ {b_{1} }. Então f(x_{0}) = g(y_{0}) e f(x_{1}) = g(y_{1}). Mas g(y_{0}) = g(y_{1}), porque y_{0}, y_{1} ∈ [Z]^{n}, logo f(x_{0}) = f(x_{1}).

5.4. Teorema de Todorcevic.

Embora, para cardinais do tipo sucessor já nos 30s Sierpinski mostrou que a analogia da teorema de Ramsey foi falsa, ao menos sob HCG. Primeiro mostramos um lema que vai ser útil.

Definição. Seja κ um cardinal. A ordem lexicografico sobre P(κ) é dado pelo x < y se quando z é mínimo tal que z ∈ (x \ y) ∪ (y \ x) temos z ∈ y.

Nota. É claro que < é uma ordem linear. Falamos a ordem lexicografico porque é lexicografico sob o isomorfismo χ : P(κ) ⟶ ^{κ}2 onde χ_{x}(n) = 1 se e só se n ∈ x para x ∈ P(κ).

Lema. Seja κ um cardinal infinito e seja seja < a ordem lexicografico sobre P(κ). Não existe um subconjunto do P(κ) bem-ordenado pelo < com cardinalidade maior que κ.

Demonstação. Suphamos que κ < Y e Y ⊆ P(κ) é bem-ordenado pelo <. Então existe um ordinal ρ tal que (Y, <) ≅ (ρ, ∈) pelo um isomofismo que preserva ordem e κ^{+} ≤ ρ. Seja Y_{0} o segmento inicial do Y tal que (Y_{0}, <) ≅ (κ^{+}, ∈) pelo um isomofismo g que preserva ordem. Seja γ_{α} o mínimo γ < κ tal que ∀β < α γ_{β} < γ e existe x ∈ Y_{α} γ ∈ x, seja Y_{α+1} = {x ∈ Y_{α} | γ_{α} ∈ x}, e seja Y_{λ} = ⋂{Y_{α} | α < λ} para λ < κ do tipo limite. E seja a_{α} ∈ Y_{α} se Y_{α} ≠ ∅.

Então a função f : β ⟶ Y_{0} definida pelo f(α) = a_{α} para α < β e β = {α | Y_{α} ≠ ∅} é cofinal para Y_{0} e temos que g · f mostra cf (κ^{+}) ≤ cf (β) ≤ κ. Uma contradição!

Proposição. (Sierpinski) Existe uma coloração f do [P(κ)]^{2} com 2 cores tal que não existe um subconjunto X do P(κ) da cardinalidade maior que κ com f“[X]^{2} = 1.

Demonstração. Seja < a ordem lexicografico sobre P(κ). Sejam ≺ qualquer bem-ordem do P(κ). Defina f : [P(κ)]^{2} ⟶ 2 pelo se f({x, y }) = 0 se x < y e x ≺ y ou y < x e y ≺ x e f({x, y }) = 1 se x < y e y ≺ x ou y < x e x ≺ y.

Se H ⊆ P(κ) é tal que f“[H]^{2} = {0} então < é uma bem-ordem do H. E se H ⊆ P(κ) é tal que f“[H]^{2} = {1} então {κ \ x | x ∈ H } é bem-ordenado pelo <. Então, em qualquer caso H ≤ κ pela lema.

Definição. Um cardinal κ é compacto fracamente se para qualquer coloração f do [κ]^{2} com 2 cores existe um x ∈ [κ]^{κ} tal que f“[x]^{κ} = 1.

Exemplo. ω é compacto fracamente pela teorema de Ramsey.

Proposição. Se κ é compacto fracamente, então κ é inacessível fortemente.

Demonstração. Se κ não é inacessível fortemente ou existe μ < κ tal que κ ≤ 2^{μ} ou κ é singular. Se μ < κ e κ ≤ 2^{μ} temos que existe uma coloração do [2^{μ}]^{2} com 2 cores sem um subconjunto monocromatico do 2^{μ} do tamanho μ^{+} pela teorema de Sierpinski. Mas μ^{+} ≤ κ, então a restrição desta coloração para [κ]^{2} não tem um subconjunto monocromatico do cardinalidade κ.

Se κ é singular, seja g : cf (κ) ⟶ κ cofinal e cresente estritamente. Defina f : [κ]^{2} ⟶ 2 pelo f(γ, δ) = 0 se e só se existe α < cf (κ) tal que g(α) ≤ γ, δ < f(α + 1). Porque para cada α < cf (κ) temos que {γ < κ | g(α) ≤ γ < g(α + 1)} < κ, não existe x ∈ [κ]^{κ} tal que f“[x]^{2} = {0}. E não existe x ∈ [κ]^{cf (κ)^{+}} tal que f“[x]^{2} = {1}.

Muito mais tarde Stevo Todorčević mostrou uma teorema linda que fortelece muito o resultado de Sierpinski. Este teorema servirá como uma outra ilustração do uso conjuntos fechados e ilimitados e de conjuntos parados. (A demonstração que damos aqui é uma variação por Dan Velleman da demonstração de Todorčević.)

Teorema. (Todorčević 1986^{2}) Existe uma coloração f do [ω_{1}]^{2} com ω_{1} cores tal que f“[x]^{2} = ω_{1} para cada x ∈ [ω_{1}]^{ω_{1}}. Em outras palavras, existe uma coloração do K_{ω_{1}} com ω_{1} cores tal que qualquer subgrafo isomorfico para K_{ω_{1}} deve ter arestes com todos os cores.

Demonstração. Seja {r_{α} | α < ω_{1} } ⊆ ^{ω}2. Também seja e_{α} : α ⟶ ω uma injeção para cada α < ω_{1}. Defina σ(α, β) = o mínimo n < ω tal que r_{α}(n) ≠ r_{β}(n) para α < β < ω, e seja f(α, β) = o mínimo δ < ω_{1} tal que α ≤ δ < β e e_{β}(δ) ≤ σ(α, β) se existe um tal δ, e = 0 senão.

Para demonstrar a teorema é bastante mostrar que se Z ∈ [ω_{1}]^{ω_{1}}, então existe um conjunto C fechado e ilimitado tal que C ⊆ f“[Z]^{2}. Para ver isso lembrar que pelo proposição imediatemente depois da definição do parado temos que existe conjuntos parados S_{i} ⊆ ω_{1} para cada i < ω_{1}, com ω_{1} = ⋃{S_{i} | i < ω_{1} } e S_{i} ∩ S_{j} = ∅ se i, j < ω_{1} e i ≠ j. Se definimos g(α) = i se e só se α ∈ S_{i} temos que g · f“[Z]^{2} = g“C_{Z} onde C_{Z} é fechado e ilimitado para cada Z ∈ [ω_{1}]^{ω_{1}}. Mas para cada i < ω_{1} temos que existe α_{i} ∈ S_{i} ∩ C_{Z} porque S_{i} e parado. Logo se i < ω existe {x, y } ∈ [Z]^{2} tal que f({x, y }) = α e g(α) = i. Então g · f mostrar a teorema.

2 Stevo Todorčević, Partitioning pairs of countable ordinals, Acta Mathematica, 159 (1987), pp. 261-294. Este artigo

ótimo tem muitos outras coisas extremementes interessantes. Recomendâ-lo muito – e o volume de Acta Mathematica é na biblioteca também!

Então, seja Z ∈ [ω_{1}]^{ω_{1}} e para cada g ∈ ⋃{^{n}2 | n < ω } = ^{<ω}2 seja B_{g} = {α ∈ Z | g ⊆ r_{α} }. Também seja C = {δ < ω_{1} | ∀g ∈ ^{<ω}2, ou B_{g} ⊆ δ ou (B_{g} = ω_{1} & δ = ⋃(B_{g} ∩ δ))}. Suponhamos que λ é um ordinal do tipo limite e ⋃ C ∩ λ = λ. Se g ∈ ^{<ω}2 e B_{g} ⊈ λ, temos que B_{g} ⊈ δ para cada δ < λ, e, logo, temos B_{g} = ω_{1}, porque C ∩ λ ≠ ∅, e λ = ⋃ C ∩ λ = ⋃(⋃{B_{g} ∩ δ | δ ∈ C ∩ λ}) = ⋃ B_{g} ∩ λ. Então C é fechado. Não é difícil ver que C também é ilimitado no ω_{1}. ^{<ω}2 = ω, então existe δ < ω_{1} tal que ⋃(⋃{B_{g} | B_{g} < ω_{1} }) < δ. Seja {B_{n} | n < ω } = {B_{g} | B_{g} = ω_{1} }. Logo dado α < ω_{1} pode escolhar recursivemente β_{ω.n+m} ser o membro mínimo do B_{m} tal que α, δ, e β_{ω.n′+m′} < β_{ω.n+m} se n′ < n ou n′ = n e m′ < m. É claro que α < γ = ⋃{β_{ω.n+m} | n, m ∈ ω } ∈ C. Vamos ver que C ⊆ f“[Z]^{2}.

Suponhamos que δ ∈ C e β ∈ Z com δ < β. Vamos achar α ≤ δ tal que f(α, β) = δ. Seja n = e_{β}(δ) e g = r_{β}|n. Então β ∈ B_{g}, e logo B_{g} ⊈ δ e temos que B_{g} = ω_{1}.

Para cada γ ∈ B_{g} tal que β < γ sejam m_{γ} = σ(β, γ) e h_{γ} = r_{γ}|(m_{γ} + 1). Nota que h_{γ}|m_{γ} = g|m_{γ}, mas h_{γ}(m_{γ}) ≠ g(m_{γ}). Porque B_{g} = ω_{1} existe um subconjunto B ∈ [B_{g}]^{ω_{1}} e existe m < ω e h : m ⟶ ω tal que m = m_{γ} e h = h_{γ} para cada γ ∈ B. Logo B_{h} = ω_{1} e pela definição do C temos que δ = ⋃ δ ∩ B_{h}.

Seja F = {ϵ < δ | e_{β}(ϵ) ≤ m}. F é finito porque e_{β} é uma injeção. Então existe α ∈ B_{h} ∩ δ tal que F ⊆ α. Agora temos que α ∈ B_{h}, logo h ⊆ r_{α}, e que h|m = r_{β}|m e h(m) ≠ r_{β}(m). Logo σ(α, β) = m. Se α ≤ ϵ < δ temos que m < e_{β}(ϵ), mas e_{β}(δ) = m. Logo δ é mínimo tal que α ≤ δ < β e e_{β}(δ) ≤ m, então δ = f(α, β).

Seria muito interesante ter resultados similares para outro grafos além de K_{ω_{1}}. Pode ver o artigo recente de András Hajnal e Péter Komjáth, Some remarks on the simultaneous chromatic number, (até agora não publicado, mas disponível do Péter Komjáth – kope@cs.elte.hu – pelo internet) para alguma informação sobre este problema da geralização, mas ainda tem muitas oportunidades para melhoramentos do trabalho deles.

Por exemplo, falemos que G = (X, A) tem número cromático ω_{1} se ω_{1} é o cardinal κ mínimo tal que existe f : κ ⟶ X tal que f(x) ≠ f(y) se {x, y } ∈ A. É claro que K_{ω_{1}} tem número cromático ω_{1}.

O princípio ♢^{+} fala que existe {B_{α,n} | α < ω_{1} & n < ω } tal que B_{α,n} ⊆ α para cada α < ω_{1} e n < ω, e se B ⊆ ω_{1}, então existe um conjunto, C, fechado e ilimitado tal que ∀γ ∈ C ∃n < ω (B∩γ = B_{γ,n}). Então ♢^{+} fala que tem um sistema {B_{α,n} | α < ω_{1} & n < ω } que prediz qualquer subconjunto B do ω_{1} certamente num grande (fechado e ilimitado) número dos lugares. ♢^{+} é uma fortalecendo do (HC), então não demonstraável no ZF (embora que é verdadeiro se V = L, por exemple). Ele implica (HC) porque se x ⊆ ω existe C tal que ∀γ ∈ C \ ω existe n < ω com x = x ∩ γ = B_{γ,n}. Então 2^{ω} = P(ω) ≤ {B_{α,n} | α < ω_{1} & n < ω } = ω_{1}.

Hajnal e Komjáth mostram que ♢^{+} implica que se G = (ω_{1}, A) tem número cromático ω_{1}, então existe f : A ⟶ ω_{1} tal que se X ∈ [ω_{1}]^{ω_{1}} e (X, A ∩ (X × X)) tem número cromático ω_{1} temos que f“(A ∩ (X × X)) = ω_{1}. Mas ainda esta em aberta se pode mostrar este resultado no ZF + AE, logo geralizando a teorema de Todorčević.