Teoria dos conjuntos

Charles Morgan*

Capítulo 2. Ordinais, relações bem-fundadas.

2.1. Relações bem-fundadas.

Vamos começar com algumas definições e rápidamente chegaremos na noção de um conjunto bemordenado.

Definição. Por qualquer X e qualquer relação binária < sobre X, (X, <) é um conjunto parcialmente ordenado (conjunto p.o.) se < é uma relação anti-simétrica e transitiva no X: ∀x ∈ Xx ≮ x and ∀x ∈ X ∀y ∈ X ∀z ∈ X (x < y & y < z ⟶ x < z). Falamos que < ordena parcialmente X ou < é um ordenando parcial ou ordem parcial de X.

(X, <) é um conjunto linearmente ordenado (conjunto l.o.) ou um conjunto totalmente ordenado (conjunto t.o.) se (X, <) é um conjunto parcialmente ordenado e ∀x ∈ X ∀y ∈ X (x < y ou x = y ou y < x) também.

Definição. Agora seja < qualquer relação binária sobre X. Se Y ⊆ X, então (Y, <) é um segmento inicial de (X, <) se ∀x ∈ X ∀y ∈ X (x < y & y ∈ Y ⟶ x ∈ Y). Muitas vezes falaremos apenas que Y é um segmento inicial de X quando é claro de qual relação < estamos falando. (Y, <) é um segmento inicial próprio de (X, <) se Y ≠ X também. Para todos s ∈ X e Y ⊆ X, falaremos que s é um sucessor de Y se s ∉ Y e {y ∈ X | y < s} ⊆ Y. E se Y ⊆ X e y ∈ X falaremos que y é <-mínimo no Y se y ∈ Y é ∀x ∈ X (x < y ⟶ x ∉ Y).

Teorema. As seguintes condições são equivalentes para qualquer X e qualquer relação binária sobre X.

(1) Cada segmento inicial próprio de X tem um sucessor.

(2) Cada subconjunto não-vazio de X tem um elemento <-mínimo.

(3) O princípo de indução sobre < é verdadeira:

∀x ∈ X ((∀y ∈ X (y < x ⟶ ϕ(y))) ⟶ ϕ(x)) ⟶ ∀x ∈ X ϕ(x).

Demonstração. (2) ⟹ (3). Suponhamos que ∀x ∈ X ((∀y ∈ X (y < x ⟶ ϕ(y))) ⟶ ϕ(x)) mas ¬∀x ∈ X ϕ(x)). Então {x ∈ X | ¬ϕ(x)} não é vazio e, para (2), tem um membro, vamos falar x_{0}, que é <-mínimo. Mas logo temos que ∀y < x_{0} ϕ(y) e então ϕ(x), uma contradição.

(3) ⟹ (2). Se Y ⊆ X e Y não tem um membro <-mínimo, então temos que ∀x ∈ X (∀y ∈ X(y < x & y ∉ Y)) ⟶ x ∉ Y. Aplicando (3), temos que ∀x ∈ X x ∉ Y. Então Y é vazio.

(2) ⟹ (1). Se Y é um segmento inicial próprio de X, então X \ Y (= {x ∈ X | x ∉ Y }) não é vazio, e (2) fala que tem um membro, s vamos falar, que é <-mínimo. Logo s é um sucessor de Y.

* versão 1.2, 1/12/00 (1) ⟹ (2). Para todos x, y ∈ X seja x <^{∗} y se tem x_{0}, …, x_{n−1} ∈ X e x < x_{0} < … < x_{n−1} < y. <^{∗} é o fechamento transitivo de <: é transitivo, <⊆<^{∗} e se R é uma relação binária transitiva com <⊆ R, então <^{∗}⊆ R.

(Para ver que <^{∗} é transitivo tome x <^{∗} y e y <^{∗} z e suponhamos que temos isso porque x < x_{0} < … < x_{n−1} < y e y < y_{0} < … < y_{m−1} < z para algumas x_{0}, …, x_{n−1}, y_{0}, …, y_{m−1} ∈ X. Logo, x < x_{0} < … < x_{n−1} < y < y_{0} < … < y_{m−1} < z, e então x < z. É claro que x < y ⟹ x <^{∗} y: tome n = 0 na definição de <^{∗}. E se x <^{∗} y existem x_{0} < … < x_{n−1} com x < x_{0} < … < x_{n−1} < y, então se <⊆ R temos x R x_{0} R … Rx_{n−1} Ry, e logo, se R é transitivo, temos x R y.)

Agora suponhamos que Y ⊆ X e Y não é vazio. {x ∈ X | x ∉ Y & ∀y ∈ X (y <^{∗} x ⟶ y ∉ Y)}, = Z, vamos falar, é um segmento inicial e não é próprio. Se s é um sucessor de Z temos que s ∈ Y e s é <-mínimo no Y.

Definição. Uma relação binária < sobre um conjunto X é bem-fundada se satisfaz as condições (1)-(3) do teorema em cima. Um ordenando total bem-fundado é chamado um bem-ordenando ou uma bem-ordem. (X, <) é então um conjunto bem-ordenado (um conjunto b.o.).

2.2 Ordinais.

Então, um conjunto bem-ordenado é um conjunto que sobre qual podemos “contar,” um passo de cada vez. Os ordinais são conjuntos bem-ordenados que serão cruciais para nós. Em fato, veremos mas tarde que qualquer conjunto bem-ordenado é isomorfico para um ordinal para um isomorfismo que preservar ordem, então pode falar que se quer “contar” tem que usar os ordinais.

Definição. Um (número) ordinal é um conjunto que é bem-ordenado por ∈. (Frequentemente escrevemos < em vez de ∈ quando estamos tratando dos ordinais.)

Exemplos. 0, 1, 2, 3, …, ω, … são (os primeiros) ordinais. Exercício: se isso não está aparente para você, vai confirmá-lo.

Proposição. Se α é um ordinal e z ∈ α, logo z é um conjunto transitivo e então é um ordinal também.

Demonstração. Suponhamos que x ∈ y ∈ z ∈ α. Temos que mostrar que x ∈ z. Mas α é transitivo, então y ∈ α, então x ∈ α. α também é bem-ordenado por ∈, então ∈ é uma relação trasitiva sobre α. Porque temos x ∈ y e y ∈ z, então x ∈ z.

Definição. Se α é um ordinal defina s(α) = α ∪ {α}.

Proposição. Se α é um ordinal, então s(α) é um ordinal também.

Demonstração. Se z ∈ y ∈ s(α), então ou z ∈ y ∈ α ou z ∈ y ∈ {α}. No primeiro caso z ∈ α porque ∈ é transitivo sobre α, e no segundo caso z ∈ y = α. Então, em qualquer caso z ∈ s(α). Logo s(α) é transitivo. E é claro que s(α) é bem-ordenado por ∈.

Proposição. Se x ≠ ∅ é um conjunto dos ordinais, então ⋂ x é um ordinal também.

Demonstração. É claro que qualquer intersecção dos conjuntos transitivos é transitiva. E se α ∈ x, então ⋂ x ⊆ α e deve ser bem-ordenada por ∈ porque α é bem-ordenado por ∈.

Proposição. Se α, β são ordinais e α ⊆ β, então (a) α é um segmento inicial de β, e (b) α ≠ β ⟹ α ∈ β.

Demonstração. (a) Se γ ∈ β, δ ∈ α e γ ∈ δ (i.e., γ vem antes do δ no b.o. do β por ∈), então γ ∈ δ ∈ α, e então γ ∈ α pela transitividade do ∈ sobre α.

(b) Se α ≠ β, então, pela equivalente de ser bem-fundado, existe um sucessor, vamos falar s, de α como subconjunto do β. Nota que s é único porque ∈ é um l.o. do β. Também porque ∈ é um l.o. do β, γ ∈ α implica que γ ∈ s, então α ⊆ s. No outro lado, S = α ∪ {s} é um segmento inicial do β e, então, é transitivo e, logo, para qualquer γ ∈ s(∈ S) temos γ ∈ S. Porque s ∉ s (para o axioma de fundação), γ ∈ s implica γ ∈ α e s ⊆ α. Então α = s, ∈ β.

2.3. Tricotomia.

Teorema. Se α e β são ordinais um e exatamente um dos seguintes acontece: α ∈ β ou α = β ou β < α.

Demonstração. α ∩ β = α ou α ∩ β ⊂ α e α ∩ β ≠ α. Similarmente α ∩ β = β ou α ∩ β ⊂ β e α ∩ β ≠ β, dando quatro casos para considerar para nós.

(i) α ∩ β = α e α ∩ β = β. Logo α = β.

(ii) α ∩ β = α e α ∩ β ⊂ β e α ∩ β ≠ β. Então a última proposição de Seção (2.2) dá imediatemente que α ∈ β.

(iii) α ∩ β = β e α ∩ β ⊂ α e α ∩ β ≠ α. Então a última proposição de Seção (2.2) dá que β ∈ α.

(iv) α ∩ β ⊂ α, β, α ∩ β ≠ α e α ∩ β ≠ β. Nota que já mostramos que α ∩ β é um ordinal. Então a última proposição de Seção (2.2) dá que α ∩ β ∈ α e que α ∩ β ∈ β. Então α ∩ β ∈ α ∩ β, uma contradição! (Para o axioma de fundação.)

Corolário. Por todos ordinais α e β, α ⊆ β ou β ⊆ α.

Demonstração. α ∈ β ⟹ α ⊆ β porque β é transitivo; β ∈ α ⟹ β ⊆ α porque α é transitivo; α = β ⟹ α ⊆ β & β ⊆ α.

Notação. Escrevemos α ≤ β se α ∈ β ou α = β.

Corolário. A coleção de todos os ordinais é uma coleção que é bem-ordenada por ∈.

Demonstração. É facil ver que a coleção é parcialmente ordenada por ∈ pela a transitividade dos ordinais. A teorema da tricotomia da que ∈ ordena a coleção totalmente. Então, vamos ver que ∈ é bem-fundado na coleção.

Suponhamos que Z é um subconjunto da coleção dos ordinais e Z ≠ ∅. Seja α ∈ Z. Ou α é ∈-mínimo (quando acabamos), ou Y = α ∩ Z ≠ ∅. Y é um subconjunto não-vazio do α, então existe um β ∈ Y que é ∈-mínimo. Mas β deve ser ∈-mínimo no Z também, porque se γ ∈ β temos que β ∈ α e, pela transitividade do α, γ ∈ α. Então γ ∈ Z.

Corolário. A coleção de todos ordinais não é um conjunto, é uma classe própria.

Demonstração. Seja a coleção um conjunto, x vamos falar, teríamos que x ∈ x porque seria um conjunto bem-ordenado por ∈. Isso seria uma contradição para o axioma de fundação (de novo).

Este corolário é às vezes chamado o paradoxo de Burali-Forti. Como você já entende, como o paradoxo de Cantor, não é um paradoxo de verdade. Ainda, como com V é útil ter um nome para a classe própria de todos os ordinais. Vamos escrever On por esta classe.

Corolário. Se x é um conjunto dos ordinais, então ⋃ x é também um ordinal.

Demonstração. É claro que ⋃ x é transitivo. E porque ⋃ x ⊆ On, tricotomia dá que ∈ ordena ⋃ x totalmente. Assim, suponhamos que ∅ ≠ Z ⊆ ⋃ x. Tome α ∈ Z. Como no corolário dois atrás, ou α já é ∈-mínimo, ou α ∩ Z tem um membro que é ∈-mínimo e que é ∈-mínimo no Z também.

2.4. Sucessors e limites. Seja α um ordinal. Temos duas coisas que podem acontecer.

Ou existe um elemento ∈-máximo do α, i.e., um β ∈ α tal que ∀γ ∈ α γ ≤ β. Neste caso α = {β } ∪ {γ | γ < β }, = {β } ∪ β, = s(β). Se existe β tal que α = s(β) falaremos que α e um ordinal do tipo sucessor.

Ou não existe um membro ∈-máximo na ápice de α, i.e., ∀β ∈ α ∃γ ∈ α β < γ. Neste caso α = {β | β < α} = {β | ∃γ ∈ α β ∈ γ } = ⋃ α. Se α = ⋃ α falaremos que α é um ordinal do tipo limite.

Deveria acertar que se α = s(β), então β = ⋃ α.

Exemplos. 1, 2, 3, … são ordinais do tipo sucessor. ω é um ordinal do tipo limite. (E pela nossa definição, 0 é um ordinal do tipo limite também, embora é um caso especial e típicamente tratado em si próprio.)

Em geral, se x é um conjunto dos ordinais, ⋃ x é o supremo dos ordinais no x, e se x é não vazio, ⋂ x é o infimo dos ordinais no x, e também o membro mínimo de x. (Esta última é verdadeira porque já vimos que x tem um membro que é ∈-mínimo quando ∅ ≠ x ⊆ On, α, vamos falar, e então ∀β ∈ x α ≤ β – i.e., ∀β ∈ x α ∈ β ou α = β, então α = ⋂ x.)

2.5. Teoremas de recursão. Agora queríamos definir + e . nos ordinais, num modo similar ao que é normal fazer nos números naturais. Mas antes que podemos fazer isso precisamos saber que podemos fazer definições utlizando recursão e como fazer essas definições. Então esta seção é devotada para este tema. Talvez à primeira vista vai parecer um pouco mais técnica que as últimas, mas será muito lucrativa para nós no fim.

Teorema de recursão fraca. Sejam X, Y dois conjuntos. Seja < uma relação bem-fundada sobre X, e seja g : X × P(()Y) ⟶ Y uma função. Então existe uma única função f : X ⟶ Y tal que f(x) = g(x, {f(z) | z < x}) para todos x ∈ X.

Demonstração. (Parte 1.) Falemos que ϕ : Z ⟶ Y é uma tentativa se Z é um segmento inicial de X e ϕ(x) = g(x, {ϕ(z) | z < x}) para todos x ∈ Z. Se ϕ_{0} : Z_{0} ⟶ Y e ϕ_{1} : Z_{1} ⟶ Y são duas tentativas, elas concordam no Z_{1} ∩ Z_{2}: ϕ_{1}|Z_{1} ∩ Z_{2} = ϕ_{2}|Z_{1} ∩ Z_{2}. Porque X_{1} ∩ X_{2} é claro um segmento inicial de X e se as tentativas não concordão existe um x_{0} que é <-mínimo no {x ∈ Z_{1} ∩ Z_{2} | ϕ_{1}(x) ≠ ϕ_{2}(x)}. Mas neste caso temos ϕ_{1}(x_{0}) = g(x_{0}, {ϕ_{0}(x) | x < x_{0} }) = g(x_{0}, {ϕ_{1}(x) | x < x_{0} }) = ϕ_{2}(x), uma contradição!

(Parte 2.) Agora seja f = ⋃{ϕ | ϕ é uma tentativa}, então f(x) = ϕ(x) se existe uma tentativa ϕ com x ∈ dom(ϕ). É claro que dom(f) = ⋃{dom(ϕ) | ϕ é uma tentativa} é um segmento inicial de X, e que f satisfaz f(x) = g(x, {f(z) | z < x}) para todos x ∈ dom(f). Então todo que ficar ser mostrado é que dom(f) = X.

Mas fosse dom(f) ≠ X existe x_{0} que é <-mínimo no {x ∈ X | x ∉ dom(f)}. Para um tal x defina f̄: dom(f) ∪ {x_{0} } ⟶ Y pelo f̄(x) = f(x) se x ∈ dom(f) e f̄(x_{0}) = g(x_{0}, {f(x) | x < x_{0} }). Seria claro que f̄ seria uma tentativa, mas não um subconjunto de f. Contradição! Então f : X ⟶ Y como desejamos.

Agora vamos ver um teorema de recursão mais forte que trata das classes.

Definição. Sejam A e B uns classes. Então A × B = {(x, y) | x ∈ A & y ∈ B } é uma classe tambem, porque se A = {x | ϕ(x, ā)} e B = {x | ψ(x, b̄)} para dois fórmulas ϕ(x, ā) e ψ(x, b̄) na LTC, então A × B = {z | z = {{x}, {x, y }} & ϕ(x, ā) & ϕ(y, b̄)}.

Seja A uma classe. < uma Relação bem-fundada (nota o “R” maiúscula) sobre A se < é uma subclasse do A × A, ∀a ∈ A {b ∈ A | b < a} é um conjunto, é qualquer B com ∅ ≠ B ⊆ A tem elementos <-mínimos.

Sejam A, B uns classes. G : A ⟶ B é uma Função (nota o “F” maiúscula) se G é uma subclasse de A × B e para cada x ∈ A existe um único y ∈ B tal que (x, y) ∈ G. Se x ∈ A, y ∈ B e (x, y) ∈ G (naturalmente) vamos escrever G(x) = y. (Nota falar que G é uma (sub)classe quer dizer que existe um fórmula χ(z, c̄) na LTC tal que x ∈ G se e só se χ(x, barc) é verdadeiro.)

Lembrar que conjuntos são classes também e se A e B são conjuntos, então A × B é um conjunto, < é uma relação bem-fundada e G é uma função, respectivamente.

Teorema de recursão forte. Seja < uma Relação bem-fundada sobre uma classe A e seja G : A × V ⟶ V uma Função. Então existe uma Função única F : A ⟶ V tal que para todos x ∈ A temos que F (x) = G(x, {F (y) | y < x}).

Demonstração. (Parte 1.) O primeiro parte é exatamente como na teorema de recursão fraca. Defina ϕ ser uma tentativa se ϕ : B ⟶ V, onde B é um conjunto que é um segmento inicial de A e ϕ(x) = G(x, {ϕ(y) | y < x}). Logo quaisquer duas tentativas concordam na intersecção dos segmentos iniciais deles.

(Parte 2.) Seja F = ⋃{ϕ | ϕ é uma tentativa} (isto é (x, z) ∈ F se existe uma tentativa ϕ com ϕ(x) = z). Nota que a ultima vez este foi um conjunto, mas agora meromente temos que F ⊆ P(A × V) e não sabemos que F é um conjunto, pois não será se A não é. No outro lado ainda temos que F (x) = G(x, {F (y) | y < x}) para todos x ∈ dom(F). Suponhamos que dom(F) ≠ A, e escolhe a_{0} que é <-mínimo no conjunto A \ dom(F).

Agora temos que ∀b < a_{0} ∃ϕ (ϕ é uma tentativa e b ∈ dom(ϕ). Por isto podemos aplicar o axioma de coleção que dá ∃v ∀b < a_{0} ∃ϕ ∈ v (ϕ é uma tentativa e b ∈ dom(f). Então w = v ∩ {ϕ | ϕ é uma tentativa} é um conjunto pelo axioma de compreensão. Claro f = ⋃ w é uma tentativa e podemos considerar f̄ = f ∪ {(a_{0}, G(a_{0}, {f(b) | b < a_{0} }))} que é uma tentativa mas não é um subconjunto do f. Assim, como na teorema de recursão fraca temos uma contradição! Então dom(F) = A.

Talvez você quer saber porque a demostração tem algumas mudanças de nossa demonstração anterior. Bem, você tería que saber que G(a_{0}, {F (a) | a < a_{0} }) faria sentido antes de definir F̄ = F ∪ {(a_{0}, G(a_{0}, {F (a) | a < a_{0} }))}. E Para saber isso temía que saber que {F (a) | a < a_{0} } é um conjunto, que é uma conseqüência de aplicar o princípio de reposição para o conjunto {a | a < a_{0} }. Então pode ver que não é possível evitar usar ou coleção ou reposição.

Eu deveria prevenir que não pode evitar usar coleção na teorema de recursão mesmo se A é um conjunto se G não é, e mesmo se < é uma bem-ordem sobre A e não apenas uma relação bemfundada.

2.6 Teoremas de comparação.

Definição. Uma função f : (X, <_{X}) ⟶ (Y, <_{Y}) é um isomorfismo que preservar ordem se f é uma bijeção entre X e Y e ∀x, y ∈ X (x <_{X} y ⟷ f(x) <_{Y} f(y)).

Nota. Se f : (X, <_{X}) ⟶ (Y, <_{Y}) é uma função que preservar ordem, f injetivo, ento s tem que saber que f tambm uma sobrejeo para saber que f um isomorfismo.

Teorema. Para qualquer conjunto bem-ordenado (X, <) existe um ordinal único α para qual existe um isomorfismo (único) do (X, <) para α que preserva ordem.

Demonstração. Definir, pela teorema de recursão, uma função f : X ⟶ V (On) que satisfaz f(x) = {f(y) | y < x}.

(i) ∀x ∈ X f(x) ∈ On. Senão, escolhe um x_{0} que é <-mínimo no conjunto {x ∈ X | f(x) ∉ On}. Suponhamos que x ∈ X e para todos y < x temos que f(y) ∈ On. Então f(x) ⊆ On pela definição de f, e f(x) é bem-ordenado pela ∈. Mas também, se z ∈ y ∈ f(x), temos que y = f(v) para alguma v < x. Logo z ∈ {f(u) | u < v } e existe u < v < x tal que z = f(u). Conseqüentemente, z ∈ f(x), e f(x) é transitivo. Então f(x) ∈ On. Logo, pelo princípio de indução para <, temos que ∀x ∈ X f(x) ∈ On.

(ii) im(f) é um conjunto (pelos axiomas de coleção e compreensão ou pelo princípio de reposição), e (i) mostra que im(f) ⊆ On, então im(f) é bem-ordenado pelo ∈. Suponhamos que z ∈ y ∈ im(f), então existe x ∈ X tal que z ∈ y = f(x), e logo existe v ∈ X tal que v < x ez = f(v). Então z ∈ im(f) e im(f) ∈ On.

Finalmente se g : X ⟶ β é um outro isomorfismo que preserva ordem, então f · g^{−1} seria um isomorfismo de β para α que preserva a ordem dada pelo ∈. Então β = α e f · g^{−1} é igual para a funcão de identidade pela (o primerio corolário para) tricotomia.

Teorema de Comparação. Sejam (X, <_{X}) e (Y, <_{Y}) dois b.o.conjuntos. Então existe um isomorfismo que preservar ordem entre um deles e um segmento inicial do outro.

Demonstração. A teorema anterior fala que existem α, β ∈ On e isomorfismos f : (X, <_{X}) ⟶ α e g : (Y, <_{Y}) ⟶ β que preservam ordem. Agora vamos aplicar tricotomia. Se α = β temos que g^{−1} · f é um isomorfismo que preserva ordem entre (X, <_{X}) e (Y, <_{Y}). Se α ∈ β temos que g^{−1} · f é um isomorfismo que preserva ordem entre (X, <_{X}) e um segmento inicial próprio de (Y, <_{Y}) (do qual g^{−1}(α) é um sucessor). E se β ∈ α temos que f^{−1} · g é um isomorfismo que preserva ordem entre (Y, <_{Y}) e um segmento inicial próprio de (X, <_{X}) (do qual f^{−1}(β) é um sucessor).

2.7. A Hierarquia do V_{α}s

Agora podmeos definir rigorosomente (dos axiomas) a hierarquia dos V_{α}s. Defina, pela teorema de recursão, uma Funcão V : On ⟶ V (a colecão de todos conjuntos) tal que V_{α} = ⋃{P(V_{β}) | β < α}.

Proposição. ∀α V_{α} é transitivo.

Demonstração. Se não escolhe α (<-)mínimo tal que V_{α} não é transitivo. Já vimos (na primeira proposição de Seção (1.5)) que P(X) é transitivo se X é transitivo. Logo ∀β < α P(V_{β}) é transitivo. Mas V_{α} = ⋃{P(V_{β}) | β < α} é uma união dos conjuntos transitivos e, então, é transitivo também.

Proposição. Se α ≤ β temos que V_{α} ⊆ V_{β}.

Demonstração. Se α = β é trivial. Se α < β, então V_{α} ⊆ P(V_{α}), porque V_{α} e, logo, P(V_{α}) são transitivos, e P(V_{α}) ⊆ V_{β}.

Corolário. Se α é um ordinal do tipo sucessor, então V_{s(α)} = V_{α+1} = P(V_{α}).

Demonstração. V_{s(α)} = ⋃{P(V_{β}) | β ≤ α} = ⋃{P(V_{β}) | β ≤ α}∪P(V_{α}). Mas V_{β} ⊆ V_{α} se β < α, e então P(V_{β}) ⊆ P(V_{α}) se β < α. Logo ⋃{P(V_{β}) | β ≤ α} ⊆ P(V_{α}).

Corolário. Se λ é um ordinal do tipo limite, então V_{λ} = ⋃{V_{α} | α < λ}.

Demonstração. ⋃{V_{α} | α < λ} ⊆ V_{λ} = ⋃{P(V_{α}) | α < λ} = ⋃{V_{s(α)} | α < λ} ⊆ ⋃{V_{α} | α < λ} porque s(α) < λ se α < λ.

Teorema. O axioma de fundação é equivalente para “∀x ∃α ∈ On x ∈ V_{α}.”

Demonstração. “⟹” Se não, seja x_{0} ∈-mínimo tal que ∀β ∈ On x ∉ V_{β}. Logo ∀x ∈ x_{0} ∃β x ∈ V_{β}. Se aplicamos o axioma de coleção temos ∃v ∀x ∈ x_{0} ∃β ∈ v x ∈ V_{β}. Seja u = v ∩ On . Logo ∀x ∈ x_{0} ∃β ≤ sup(u) x ∈ V_{β}, e este dá que ∀x ∈ x_{0} x ∈ V_{sup(u)}. Segui que x_{0} ⊆ V_{sup(u)}, e então que x_{0} ∈ V_{s(sup(u))}. Contradição

“⟸” Seja A ≠ ∅ uma classe com A ⊆ ⋃{V_{α} | α ∈ On}. Tome α mínimo tal que A ∩ V_{α} ≠ ∅. Então qualquer a ∈ A ∩ V_{α} é ∈-mínimo no A.

Definição. Defina uma Função rk : V ⟶ V (On) pela rk(x) = ⋃{s(rk(y)) | y ∈ x}, usando a teorema de recursão.

Proposição. (i) ∀x ∈ V rk(x) ∈ On. (ii) rk(x) = o α mínimo tal que x ⊆ V_{α}. (iii) rk(x) = o α mínimo tal que x ∈ V_{α}.

Demonstração. Exercísio. (Usar indução sobre (V, ∈).)

2.8. Fechos transitivos.

Defina para cada conjunto, pela recursão sobre (ω, ≤), uma função t(n, x) tal que t(0, x) = x e t(n + 1, x) = t(n, x) ∪ ⋃ t(n, x). No fim, defina FT(x) = ⋃{t(n, x) | n ∈ ω }. FT(x) o fecho transitivo de x

Proposição. Para cada x, FT(x) é o conjunto transitivo mínimo z com x ⊆ z. (Isto é, se y é transitivo e x ⊆ y, então FT(x) ⊆ y.)

Demonstração. Seja u ∈ v ∈ FT(x). Então existe n < ω tal que u ∈ v ∈ t(n, x). Então u ∈ ⋃ t(n, x) ⊆ t(n + 1, x) ⊆ FT(x). Logo, FT(x) é transitivo.

Seja y transitivo com x ⊆ y. Vamos mostrar pela indução sobre ω que cada t(n, x) ⊆ y. É claro quando n = 0. Suponhamos que t(n, x) ⊆ y. Se z ∈ t(n + 1, x) temos ou z ∈ t(n, x), quando z ∈ y, ou z ∈ ⋃ t(n, x). Então existe alguma v ∈ t(n, x) tal que z ∈ v. Mas se z ∈ v ∈ t(n, x) ⊆ y, temos que z ∈ y pela transitividade de y. Então temos t(n + 1, x) ⊆ y, e logo FT(x) = ⋃ t(n, x) ⊆ y.

Proposição. O axioma de fundação para conjuntos (cada conjunto não vazio tem um membro ∈-mínimo) implica o axioma de fundação para classes (cada classe não vazia tem um membro ∈-mínimo).

Demonstração. Seja A, ≠ ∅, uma classe. Seja x ∈ A. Ou x é ∈-mínimo (acabamos) ou x∩A ≠ ∅. Então FT(x) ∩ A ≠ ∅. Seja y ∈-mínimo no conjunto FT(x) ∩ A. (Sabemos que é um conjunto pela propsição prévia.) Temos que y ∈ A. Agora suponhamos que z ∈ y. Então z ∉ FT(x) ∩ A. Mas z ∈ y ∈ FT(x) é FT(x) é transitivo, então z ∈ FT(x). Logo z ∉ A, e temos mostrado que y é ∈-mínimo no A.

2.9. Aritmética dos ordinais: Adio dos ordinais.

Vamos usar recursão para definir adição e multiplicação sobre On.

Definição. Defina, para α fixo e β variável, α + β = α ∪ {α + γ | γ < β }

Proposição. Sejam α, β ∈ On. Então α + β ∈ On.

Demonstração. Se não, seja β_{0} mínimo com α + β_{0} ∉ On. Então para todos γ < β_{0} temos que α + γ ∈ On, então α + β_{0} = α ∪ {α + γ | γ < β_{0} } ⊆ On e, logo, é bem-ordendado pelo ∈.

Agora vamos ver que α + β_{0} é transitivo, então pertence a On, dando uma contradição para a suposição que não pertence a On. Sejam z ∈ y ∈ α ∪ {α + γ | γ < β_{0} }. Então, ou y ∈ α, quando z ∈ α, porque α é um ordinal, ou existe γ < β tal que y = α + γ ∈ On, logo, de novo, z ∈ {α + δ | δ < γ }. Em cada caso temos que z ∈ α + {α + γ | γ < β_{0} }, dando a contradição desejeda. Logo α + β_{0} ∈ On.

Lema. ∀α, β, γ, δ ∈ On: (i) β < γ ⟹ α + β < α + γ; (ii) α ≤ δ ⟹ α + β ≤ δ + β.

Demonstração. (i) Se β < γ, então α + β ∈ α + γ. (ii) Suponhamos que o Lema é falso para alguma par α e δ, e seja β_{0} mínimo tal que α + β ≰ δ + β. Então ∀β < β_{0} temos que α+β ≤ δ+β e logo ou α+β = δ+β ou α+β < δ+β, i.e. α+β = δ+β ou existe γ < β tal que α+β = δ+γ, ou α+β ∈ δ. Logo α+β_{0} = α∪{α+β | β < β_{0} } ⊆ δ∪{δ+γ | γ < β_{0} } = δ + β_{0}.

Proposição. (i) α + 0 = α; (ii) α + s(β) = s(α + β); (iii) se λ é um ordinal do tipo limite, então α + λ = ⋃{α + γ | γ < λ}.

Demonstração. (i) Trivial. (ii) α + s(β) = α ∪ {α + γ | γ < s(β)} = α ∪ {α + γ | γ < s(β)} = α ∪ {α + γ | γ < β } ∪ {α + β } = (α + β) ∪ {α + β } = s(α + β). (iii) Se x ∈ ⋃{α + γ | γ < λ} então existe γ < λ tal que x ∈ α ∪ {α + β | β < γ }. Então x ∈ α∪{α+β | β < λ}. Mas sabemos que λ = ⋃ λ = ⋃{γ | γ < λ}, então se x ∈ α∪{α+β | β < λ} ou x ∈ α ou x = α+β para alguma β < λ e existe γ < λ tal que β < γ. Logo x ∈ ⋃{α+γ | γ < λ}.

Teorema. Sejam α, β ∈ On e seja ≺ a ordem anti-lexicográfico sobre α × {0} ∪ β × {1} definido pelo (γ, i) ≺ (δ, j) se e s se ou i < j ou i = j e γ < δ. Então esta ordem é isomorfico para (α + β in)

Demonstração. Defina uma função f : α×{0}∪β×{1} ⟶ α+β pelo f(γ, 0) = γ e f(δ, 1) = α+δ. É claro que a f é sobrejetivo e também que ≺ é uma ordem total sobre dom(f). Vamos ver que (γ, i) ≺ (δ, j) implica f(γ, i) < f(δ, j).

Se i < j então i = 0 e j = 1, f(γ, i) = γ e f(δ, j) = α + δ e temos que γ < α ≤ α + δ. Se i = j = 0, então f(γ, i) = γ e f(δ, j) = δ e temos γ < δ. E se i = j = 1 temos que α + γ < α + δ pelo lemma anterior.

Nota. 1 + ω = ω, enquanto ω + 1 = s(ω), então + não é comutativo em geral.

Proposição. Se x ⊆ On é um conjunto não vazio, então α + ⋃ x = ⋃{α + β | β ∈ x}. (+ é contínuo no segundo lugar/variável.)

Demonstração. β ∈ x implica que β ≤ ⋃ x, e então ∀β ∈ x (α + β ≤ α + ⋃ x). Logo ⋃{α + β | β ∈ x} ⊆ α + ⋃ x.

Seja ρ = ⋃{α + β | β ∈ x} Se ρ ∈ α + ⋃ x, então ou ρ ∈ α ou existe γ ∈ ⋃ x tal que ρ = α + γ. Se ρ ∈ α, então ∀β ∈ x α + β ≤ ρ < α, uma contradição. E se ρ = α + γ com γ ∈ ⋃ x, então existe β ∈ x tal que γ < β e então ρ < α + β e ρ < ⋃{α + β | β ∈ x} = ρ, uma contradição de novo. Logo, ρ ∉ α + ⋃ x e temos que ρ = α + ⋃ x.

Podemos definir subtração também, mas pela falta de comutatividade de adição não é tão útil como adição.

Definição. α − β = {γ | β + γ < α}. Alternativemente pode definir α − β pela recursão: α − β = 0 se β > α e α − β = {α − γ | γ < β } se β ≤ α.

Proposição. Sejam α, β ∈ On e β ≤ α. Então β + (α − β) = α.

Demonstração. β + (α − β) = β ∪ {β + γ | γ < α − β } = β ∪ {β + γ | β + γ < α} ⊆ α. Suponhamos que β + (α − β) < α. Então (α − β) ∈ {γ | β + γ < α} = α − β. Uma contradição. Logo β + (α − β) = α.

Nota. (α − β) + β ≠ α em geral. Por exemplo, ω − 1 = ω, logo (ω − 1) + 1 = s(ω) ≠ ω.

2.10 Aritmética dos ordinais: Multiplicação dos ordinais.

Pela teorema sobre recursão, definamos α.β = {α.γ + δ | γ < β & δ < α}.

Proposição. ∀α, β ∈ On (α.β ∈ On).

Demonstração. Suponhamos que α.γ ∈ On para cada γ < β. Então α.γ+δ ∈ On para cada γ < β pela proposição que ξ + ζ ∈ On se ξ, ζ ∈ On, e temos que α.β ⊆ On e logo é bem-ordenado pelo ∈. Também para cada γ < β a função f_{γ} : α ⟶ {α.γ + δ | δ < α} dado pelo f_{γ}(δ) = α.γ + δ tem f_{γ}“α = {α.γ +δ | δ < α}, e logo {α.γ +δ | δ < α}, A_{γ} vamos falar, é um conjunto pelo princípio de reposição. Então α.β = ⋃ A_{γ}γ < β é uma união dos conjunto e é um conjunto também. Finalmente, se x ∈ y ∈ α.β, então existe γ < β e δ < α tal que x ∈ y = α.γ + δ. Então ou x ∈ α.γ ou existe σ < δ tal que x = α.γ + σ. No primeiros caso existe ϵ < γ e τ < α tal que x = α.ϵ + τ. Então em cada caso temos que x ∈ α.β. Porque agora temos que ∀β (∀γ < β (α.γ ∈ On) ⟶ α.β ∈ On) temos que ∀β ∈ On α.β ∈ On.

Lema. ∀α ∈ On (i) 0.α = 0; (ii) 1.α = α; (iii) ∀β, γ ∈ On (β < γ) ⟹ α.β < α.γ; e (iv) ∀δ β ∈ On, (α ≤ δ ⟹ α.β ≤ δ.β).

Demonstração. (i)–(iii) são óbvios. (iv) Suponhamos que α, δ ∈ On, β ∈ On e para todos γ < β temos que α.γ ≤ δ.γ. Usando o lema sobre adição na Seção (2.8), temos para todos γ < β e todos ϵ < α que α.γ+ϵ ≤ δ.γ+ϵ. Então ou α.γ+ϵ = δ.γ+ϵ, quando α.γ+ϵ ∈ δ.β, ou α.γ+ϵ ∈ δ.γ+ϵ ∈ δ.β, e α.γ + ϵ ∈ δ.β, pela transitividade de δ.β. Em cada caso temos que α.β ⊆ δ.β e então α.β ≤ δ.β. Mas este mostrar que (∀γ < β α.β ≤ δ.γ) ⟶ α.β ≤ δ.β. Então, porque < é bem-fundado sobre os ordinais, ∀β ∈ On α.β ≤ δ.β.

Proposição. (i) α.0 = 0; (ii) α.s(α) = α.β + α; e (iii) se λ ∈ On é do tipo limite, então α.λ = ⋃{α.γ | γ < λ}.

Demonstração. (i) Trivial. (ii) α.s(β) = {α.γ + δ | γ ≤ β & δ < α} = {α.γ + δ | γ < β & δ < α} ∪ {α.β + δ | δ < α} = α.β + α.

Se λ é um ordinal do tipo limite, ⋃{α.β | β < λ} = {α.γ + δ | (∃β < λ γ < β) & δ < α} = {α.γ + δ | γ ∈ ⋃ λ & δ < α} = {α.γ + δ | γ < λ & δ < α}, com o último passo porque λ é do tipo limite.

Teorema. Sejam α, β ∈ On e seja ≺ a ordem anti-lexicografico sobre α × β, definido pelo (δ_{0}, γ_{0}) ≺ (δ_{1}, γ_{1}) ou se γ_{0} < γ_{1} ou se γ_{0} = γ_{1} e δ_{0} < δ_{1}. Então (α × β, ≺) é isomorfico para (α.β, ∈) pelo um isomorfismo que preserva ordem.

Demonstração. Defina f : α × β ⟶ α.β pelo f(δ, γ) = α.γ + δ. É claro que f é uma sobrejeção. Se (δ_{0}, γ_{0}) ≺ (δ_{1}, γ_{1}) ou γ_{0} < γ_{1} quando α.γ_{0} + δ_{0} < α.s(γ_{0}) ≤ α.γ_{1} ≤ α.γ_{1} + δ_{1}, ou γ_{0} = γ_{1} e δ_{0} < δ_{1}, quando α.γ_{0} + δ_{0} < α.γ_{0} + δ_{1} pela lema sobre adição. Logo, f preserva ordem, é então é um isomorfismo.

Nota. 2.ω = ω, 3.ω = ω, …, mas ω.ω ≠ ω. Nota também que (ω + 1).ω = ω.ω

Teorema. Seja α, β ∈ On, β > 0. Então existe únicos σ, τ com τ < β tal que α = β.σ + τ.

Demonstração. Sejam σ = {γ | β.s(γ) ≤ α} e τ = α − β.σ, = {δ | β.σ + δ < α}. Então α = β.σ + τ. Para ver que τ < β, observe que se não ou β = τ, quando α = β.σ + β = β.s(σ) ou β ∈ {δ | β.σ + δ < α} e, então, β.σ + β = β.s(σ) < α. Logo em qualquer caso β.s(σ) ≤ α e σ ∈ σ, uma contradição!

Proposição. Se x ⊆ On então α. ⋃ x = ⋃{α.β | β ∈ x}. (Que quer dizer que . é continuo no segundo lugar/variável.)

Demonstração. α. ⋃ x = {α.γ+δ | δ < α & (∃β ∈ x γ < β)} = {α.γ+δ | ∃β ∈ x (γ < β & δ < α)} = ⋃{α.β | β ∈ x}.

Nota. Na teorema prévio σ = ⋃{γ | β.γ ≤ α}.

Aritmética dos ordinais: 2.11 Exponenciação dos ordinais.

Agora podemos fazer mais uma definição pelo teorema sobre recursão, da exponciação.

Definição. Seja α, β ∈ On. Então α^{β} = {0} ∪ {α^{γ}.δ + ϵ | γ < β & δ < α & ϵ < α^{γ} }.

Proposição. Seja α, β ∈ On. Então α^{β} ∈ On.

Lema. ∀α, β, γ δ ∈ On temos (i) α^{β}.α^{γ} = α^{β+γ}; (ii) (α^{β})^{γ} = α^{β.γ}; (iii) β < γ ⟹ α^{β} < α^{γ}; e (iv) α ≤ δ ⟹ α^{β} ≤ δ^{β}.

Proposição. Seja α ∈ On. (i) α^{0} = 1; (ii) α^{s(β)} = α^{β}.α para cada β ∈ On; e (iii) se λ é um ordinal do tipo limite, então α^{λ} = ⋃{α^{γ} | γ < λ}.

As demonstraçes são similares para as demonstraçes dos equivalentes para .. Pode confirmá-las se quiser.

Nota. ∀n ∈ ω n^{ω} = ω, mas ω^{ω} ≠ ω, enquanto ω.ω^{ω} = ω^{ω}. E se definimos ϵ_{0} = ⋃{ω, ω^{ω}, ω^{ω^{ω}}, …}, então ω^{ϵ_{0}} = ϵ_{0}.

Quando você voltar para esta Seção mas tarde você deveria lembrar que todos estes fatos são para exponenciação dos ordinais, que é muito diferente da teoria da exponenciação dos cardinais que veremos no Capítulo (4).