Teoria dos Conjuntos: ordinais e cardinais

Ricardo Bianconi^{1}

1 Axiomas e Classes

Comecemos com umas idéias sobre Metamatemática. Serão considerados conceitos primitivos a noção de algoritmo e de finitude. Muitos dos teoremas a seguir são metateoremas, e suas demonstrações são descrições de algoritmos transformando sentenças ou demonstrações na linguagem da teoria dos conjuntos.

A linguagem adotada é de primeira ordem, contendo o símbolo de pertinência ∈. Conforme o texto evolua, abreviações serão introduzidas, tomando-se o cuidado para não escrevermos coisas inexpressíveis nessa linguagem. Quando necessário, usaremos as abreviações usuais, como ∃x ∈ y ψ para ∃x(x ∈ y ∧ ψ), ∀x ∈ y ψ para ∀x(x ∈ y → ψ), ∃!xψ(x) para ∃x ψ(x) ∧ ∀x∀y((ψ(x) ∧ ψ(y)) → x = y). Usaremos também os símbolos ∪ para a união e ∩ para a intersecção.

Consideremos os seguintes axiomas com suas explicações em português:

(A1) (Extensionalidade) ∀x∀y(x = y ↔ ∀t(t ∈ x ↔ t ∈ y)). Dois conjuntos são iguais se, e somente se, possuirem os mesmos elementos.

(A2) (Conjunto vazio) ∃x∀y(y ∉ x). Existe um conjunto sem elementos ∅.

(A3) (Par não ordenado) ∀x∀y∃z∀t(t ∈ z ↔ (t = x ∨ t = y)). Para cada x e y, existe um conjunto contendo exatamente esses dois elementos, {x, y}.

(A4) (União) ∀x∃y∀t(t ∈ y ↔ ∃w(w ∈ x ∧ t ∈ w)). Dada uma família de conjuntos x, existe um conjunto y contendo todos os elementos de cada conjunto em x, y = ⋃ x.

(A5) (Separação) Para cada fórmula φ(x̄, y), em que x̄ é uma n-upla de variáveis, temos um axioma ∀x̄∀u∃z∀y(y ∈ z ↔ (y ∈ u ∧ φ(x̄, y))). Ou seja, z = {y ∈ u : φ(x̄, y)}.

(A6) (Substituição) Para cada fórmula φ(x, y, ū) temos um axioma ∀u[∀x∀y∀z((φ(x, y, ū) ∧ φ(x, z, ū)) → y = z) → ∀s∃t∀y(y ∈ t ↔ ∃x(x ∈ s ∧ φ(x, y, ū)))]. Se φ define uma função (com parâmetros ū) então a imagem de um conjunto também é um conjunto.

(A7) (Partes) ∀x∃y∀t(t ∈ y ↔ ∀z(z ∈ t → z ∈ x)). Existe um conjunto y cujos elementos são todos os subconjuntos de x, y = P (x).

(A8) (Infinito) ∃x[∃y(y ∈ x∧∀z(z ∉ y))∧∀y(y ∈ x → ∃z(z ∈ x∧∀t(t ∈ z ↔ (t ∈ y∨t = y))))]. Ou seja, existe um conjunto x tal que ∅ ∈ x, e se y ∈ x então y ∪ {y} ∈ x.

1IME-USP - Caixa Postal 66281 CEP 05315-970 S. Paulo - SP; (e-mail: bianconi@ime.usp.br); (homepage: http://www.ime.usp.br/∼bianconi).

(A9) (Regularidade) ∀x(∃z(z ∈ x) → ∃z(z ∈ x ∧ ∀y(y ∈ z → y ∉ x))). Ou seja, se x ≠ ∅ então existe um y ∈ x tal que x ∩ y = ∅.

(A10) ou (AE) (Escolha) ∀u[[∀x(x ∈ u → ∃y(y ∈ x)) ∧ ((∀x∀y(x ∈ u ∧ y ∈ u ∧ x ≠ y) → ∀z(z ∉ x ∨ z ∉ y))] → ∃v∀x ∈ u ∃!y(y ∈ x ∧ y ∈ v)]. Ou seja, se u é uma família de conjuntos não vazios e dois a dois disjuntos, então existe um conjunto v contendo exatamente um elemento de cada x ∈ u.

Chamaremos de ZF^{∗} o sistema com os axiomas (A1) até (A8), de ZF o sistema com os axiomas (A1) até (A9) e de ZFC o sistema com os axiomas (A1) até (A10).

Definição 1.1 Só para manter o texto completo, uma demonstração formal de uma fórmula φ em qualquer um dos sistemas acima é uma seqüência finita de fórmulas θ_{1}, …, θ_{n} em que θ_{n} = φ e cada uma das θ_{i} ou é uma tautologia proposicional, ou um axioma do sistema em questão, ou um axioma lógico da forma ∀xψ(x) → ψ(t) (t uma variável), ou existem j, k < i, e θ_{k} é θ_{j} → θ_{i} (Modus Ponens), ou existe j < i e θ_{j} é χ → ψ(v) (ou, respectivamente, ψ(v) → χ), com v não livre em χ, e θ_{i} é χ → ∀yψ(y) (ou, respectivamente, ∃yψ(y) → χ), em que y é uma variável que possa substituir v (Generalização).

Definição 1.2 Classes para nós são apenas fórmulas φ(x), e função de classes são fórmulas ψ(x, y) tais que podemos provar em ZF^{∗}, ZF, ou ZFC, que ∀x∀y∀z((ψ(x, y) ∧ ψ(x, z)) → y = z). Para facilitar a leitura, podemos escrever uma classe como A = {x : φ(x)}, sendo que provar que x ∈ A significa provar φ(x), e que F : A → B é função de classes , e y = F (x) significando que foi provado que ψ(x, y) define esta função de classes, com x ∈ A e y ∈ B. Se valer ∀x∃yψ(x, y), para a definição da função de classes F, denotaremos F : V^{∗} → V^{∗}, isto é, V^{∗} denota a classe universo de ZF^{∗}.

O nosso primeiro objetivo é provar que se ZF^{∗} é consistente então ZF também será consistente. Para isto, obteremos uma classe V de modo que se relativizarmos os axiomas de ZF a V (trocando cada quantificador ∃xψ por ∃x(x ∈ V ∧ψ^{V}) e ∀xψ por ∀x(x ∈ V → ψ^{V}), em que ψ^{V} é a relativização de ψ), então cada um destes será teorema de ZF^{∗} (isto é, ZF^{∗} prova (An)^{V}, para cada n = 1, …, 9). Porisso, se ZF fosse inconsistente, poderíamos transformar a prova de uma inconsistência a partir de ZF numa prova dessa inconsistência relativizada a V, e daí tal inconsistência seria teorema de ZF^{∗}. Tal classe V poderia ser intuitivamente encarada como um “modelo” de ZF. Mas não estamos supondo nenhuma metateoria dos conjuntos, apenas fazemos demonstrações puramente sintáticas. Tal procedimento será usado constantemente.

Definição 1.3 Vamos usar as seguintes abreviações: x ∪ y = ⋃{x, y}; ⋂ x = {t : ∀y ∈ x(t ∈ y)}; x ∩ y = ⋂{x, y}; (a, b) = {{a}, {a, b}}; x × y = {(a, b) : a ∈ x, b ∈ y}; x ⊆ y se, e somente se, ∀t(t ∈ x → t ∈ y); R é uma relação binária em x se, e somente se, R ⊆ x×x; f : a → b (f é uma função cujo domínio é a e contra-domínio b) significa que f ⊆ a × b e ∀x ∈ a ∃!y ∈ b ((a, b) ∈ f), e escrevemos y = f(x); ab = {f : f : a → b}.

Fica subentendido que a leitora ou o leitor deve sempre verificar que todos estes conceitos podem ser expressos na linguagem da Teoria dos Conjuntos. (Por exemplo, z = x ∪ y significa ∀t(t ∈ z ↔ (t ∈ x ∨ t ∈ y)).)

Exercício 1.1 Seja U uma classe, e suponha que de ZF^{∗} provam-se as fórmulas de ZF^{U}, que são os axiomas de ZF relativizados a U, e suponha que de ZF prova-se ψ. Mostre que ZF^{U} prova ψ^{U}.

Exercício 1.2 Prove o Teorema da Dedução: seja T um conjunto de sentenças; mostre que T prova φ → ψ se, e somente se, T ∪ {φ} prova ψ.

Exercício 1.3 Mostre que ZF^{∗} mostra a existência do conjunto dos naturais ω, que é o menor conjunto que satisfaz o axioma do infinito. Denotaremos por x+1 o conjunto x∪{x}. Mostre em ZF^{∗} que ∀y(y ∈ ω → y ⊆ ω). Conclua (ainda em ZF^{∗}) que ∀y((y ⊆ ω∧y ≠ ∅) → ∃w(w ∈ y∧w∩y = ∅)). Mostre que ∀x((x ∈ ω ∧ x ≠ ∅) → ∃w(x = w ∪ {w})).

Exercício 1.4 Mostre que os outros axiomas de ZF provam os axiomas (A3) (par não ordenado) e (A5) (da separação).

2 Ordinais e recursão em ZF^{∗}

Os resultados a seguir serão demonstrados a partir de ZF^{∗}.

Teorema 2.1 (Princípio da indução em ω) Seja ψ(x, ū) uma fórmula. Então (ZF^{∗} prova que) ∀ū((ψ(0, ū) ∧ ∀x ∈ ω (ψ(x, ū) → ψ(x + 1, ū)) → ∀x ∈ ω ψ(x, ū)).

Prova:

Suponha que ψ(0) e que ∀x ∈ ω (ψ(x) → ψ(x + 1)). (Observe-se que nesta prova estamos usando o Teorema da Dedução, exercício 1.2.)

Defina y = {x ∈ ω : ¬ψ(x)}. Se y ≠ ∅ então, pelo exercício 1.3 existe x ∈ y tal que x ∩ y = ∅. Observe que 0 ∉ y, portanto existe w ∈ ω tal que x = w ∪ {w}, w ∉ y, isto é, vale ψ(w). Mas daí concluimos que vale ψ(w + 1), e como x = w + 1, obtemos a contradição desejada. QED

Teorema 2.2 (Recursão em ω) Sejam U uma classe e G : U → U uma função de classes, e a ∈ U. Então existe uma função de classes F : ω → U tal que:

1. F (0) = a;

2. ∀n ∈ ω (F (n + 1) = G(F (n))).

Prova:

Seja F = {z : ∃x ∈ ω ∃y ∈ U (z = (x, y) ∧ ∃f (f é uma função cujo domínio é x + 1, f(0) = a e ∀z ∈ x (f(z + 1) = G(f(z)) ∧ f(x) = y))}.

Tomando-se ψ(x) a fórmula ∃!f (f é uma função cujo domínio é x + 1, f(0) = a e ∀z ∈ x(f(z + 1) = G(f(z))), então trivialmente vale ψ(0), e podemos verificar facilmente que ∀x ∈ ω(ψ(x) → ψ(x + 1)). Por indução em ω, vale ∀xψ(x).

Com isto, podemos provar que F é função de classes. Se (x, y_{1}), (x, y_{2}) ∈ F, como vale a sentença ψ(x), então concluimos que y_{1} = y_{2}. QED

Com este teorema, podemos mostrar em ZF^{∗} que existem as funções sucessor, soma e produto em ω. Por isso, podemos interpretar a aritmética de Peano em ZF^{∗}, obtendo os Teoremas de Incompletude de Gödel. Em particular, podemos escrever uma fórmula Consis (ZF^{∗}) dizendo que ZF^{∗} é consistente. Portanto, se ZF^{∗} for consistente então ZF^{∗} não prova Consis (ZF^{∗}).^{2}

Definição 2.3 Um conjunto A é transitivo se ∀x ∈ A ∀y ∈ x (y ∈ A). (Isto é se x ∈ A então x ⊆ A.)

Exercício 2.1 Mostre que ω e que cada n ∈ ω é transitivo (em ZF^{∗}).

Teorema 2.4 Para cada conjunto A existe um único conjunto B (denotado T C(A) e chamado de fecho transitivo de A), tal que:

1. A ⊆ B;

2. B é transitivo;

3. para todo C transitivo, tal que A ⊆ C, B ⊆ C.

Prova:

A unicidade é fácil; se B_{1} e B_{2} satisfazem as condições do teorema, então B_{1} ⊆ B_{2} e B_{2} ⊆ B_{1}, donde B_{1} = B_{2}.

Para a existência, seja G a função de classes dada por G(x) = ⋃ x. Usando o Teorema da Recursão para ω, obtemos uma função de classes F tal que F (0) = A e ∀n ∈ ω (F (n + 1) = G(F (n)) = ⋃ F (n). Pelo axioma da substituição, existe um conjunto b tal que b = {y : ∃x ∈ ω (F (x) = y)}. Seja B = ⋃ b. Então A ⊆ B, pois A = F (0) ∈ b; se x ∈ B então existe n ∈ ω tal que x ∈ F (n), donde x ⊆ F (n+1) ⊆ B; se C é transitivo, e A ⊆ C, então S = {n ∈ ω : F (n) ⊆ C} satisfaz 0 ∈ S, e se n ∈ S então F (n) ⊆ C, e se x ∈ F (n) então x ⊆ F (n + 1) e x ⊆ C (pois C é transitivo), donde F (n + 1) ⊆ C, implicando que n + 1 ∈ S. Por indução, S = ω, e portanto B ⊆ C. QED

2 Veja o livro Computability and Logic de G. Boolos e ??? Geoffrey.

Façamos um aparte aqui, e provaremos o seguinte teorema (que não será usado na prova de consistência do axioma de regularidade).

Teorema 2.5 (Recursão em ∈, supondo ZF) Assumindo ZF, para cada fórmula ψ(x), se ∀x[(∀y ∈ x ψ(y) → ψ(x)) → ψ(x)] então ∀xψ(x).

Prova:

Suponha que ∀x[(∀y ∈ x ψ(y) → ψ(x)) → ψ(x)], e que para algum a valha ¬ψ(a). Então a ≠ ∅, pois (∀y ∈ ∅ ψ(y) → ψ(∅)) → ψ(∅). Seja b = T C(a). Então a ⊆ b, e portanto b ≠ ∅. Seja c = {x ∈ b : ¬ψ(x)}. Como a ⊆ b temos que c ≠ ∅. Pelo axioma da regularidade, existe d ∈ c tal que d ∩ c = ∅. Mas daí vale ∀z ∈ d ψ(z) e portanto ψ(d), contradizendo o fato que d ∈ c. QED

Voltemos a ZF^{∗}.

Definição 2.6 Seja A um conjunto e R ⊆ A × A, satisfazendo ∀x, y ∈ A ((x, y) ∈ R ∨ (y, x) ∈ R) e ∀Z ⊆ A (Z ≠ ∅ → ∃x ∈ Z ∀y ∈ Z(x ≠ y → (y, x) ∉ R)). Ou seja R é total em A (cada par de elementos pode ser comparada por R) e todo subconjunto não vazio de A tem um elemento R-mínimo. Neste caso dizemos que R bem ordena A, ou que R é uma boa ordem em A.

Definição 2.7 Dadas R_{1}, uma ordem total de A, e R_{2}, uma ordem total de B, dizemos que (A, R_{1}) ≈ (B, R_{2}) (isto é, (A, R_{1}) é ordem isomorfo a (B, R_{2})) se existir uma função bijetora f : A → B tal que ∀x, y ∈ A (x R_{1} y ↔ f(x) R_{2} f(y)).

Definição 2.8 Dizemos que x é um ordinal (e denotamos x ∈ Ord ou Ord(x)) se, e somente se, x é transitivo e “∈” bem ordena x.

Exercício 2.2 Prove os seguintes fatos sobre ordinais e boas ordens em ZF^{∗} (não use o axioma da regularidade!):

1. Um segmento inicial de um conjunto A bem ordenado por R é um subconjunto Y ⊆ A tal que se x ∈ A e y ∈ Y e x R y, então x ∈ Y. Mostre que se Y é segmento inicial de A, então ou Y = A ou exite x ∈ A tal que Y = {y ∈ A : y ≠ x ∧ y R x}.

2. Mostre que se X e Y são segmentos iniciais de A, então ou X ⊆ Y ou Y ⊆ X.

3. Mostre que se (A_{i}, R_{i}) são conjuntos bem ordenados (i = 1, 2), então ou existe uma inclusão (isto é, uma função injetora crescente) de A_{1} como segmento inicial de A_{2} ou de A_{2} como segmento inicial de A_{1}.

4. Mostre que ∅ ∈ Ord (e escrevemos ∅ = 0 neste contexto), e que se α ∈ Ord então α ∪ {α} ∈ Ord. (Escrevemos α + 1 = α ∪ {α}.)

5. Mostre que se S é um conjunto de ordinais então ⋃ S ∈ Ord.

6. Mostre que se α, β ∈ Ord então exatamente uma das condições ocorre: ou α ∈ β ou α = β ou β ∈ α. Denotamos α < β caso α ∈ β.

7. Mostre que se α, β, γ ∈ Ord, e α ∈ β e β ∈ γ então α ∈ γ.

8. Mostre que se α, β ∈ Ord, então α ∈ β ↔ α ⊆ β ∧ α ≠ β.

9. Mostre que se α ∈ Ord e a ∈ α, então a ∈ Ord.

10. Mostre que a classe Ord = {α : Ord(α)} é bem ordenada pela inclusão. (Isto é, se U é uma classe e U ⊂ Ord e U ≠ ∅, então existe α_{0} ∈ U tal que, para todo β ∈ U ou β = α_{0} ou α_{0} ∈ β.)

11. Mostre que se A é bem ordenado então A é ordem isomorfo a um único ordinal.

12. Um ordinal α ≠ 0 é dito ordinal sucessor se existir um ordinal β tal que α = β + 1; caso contrário, α é chamado de ordinal limite. Mostre que se α é ordinal limite, então α = ⋃ α, e mostre que β = ⋃(β + 1).

Teorema 2.9 (Indução em Ord) Seja ψ(x) uma fórmula tal que ∀α ∈ Ord (∀β ∈ α ψ(β) → ψ(α)) então ∀α ∈ Ord ψ(α).

Prova: Suponha que ∀α ∈ Ord (∀β ∈ α ψ(β) → ψ(α)), mas que exista γ ∈ Ord tal que ¬ψ(γ). Seja

X = {α ∈ γ : ¬ψ(α)}. Então X é um conjunto, X ⊆ γ, e X ≠ ∅ (pois, caso contrário, a hipótese acima implicaria que ψ(γ)). Seja α_{0} o elemento mínimo de X. Então α_{0} ∈ X, donde ¬ψ(α_{0}). Por outro lado, ∀β ∈ α_{0} (β ∉ X ∧ β ∈ γ). Mas daí, a hipótese implica que ψ(α_{0}), contradição. QED

Observemos que o teorema acima pode ser reescrito da seguinte forma mais útil:

Teorema 2.10 (Indução em Ord II, “O Retorno”) Seja ψ(x) uma fórmula tal que valem ψ(0), ∀α ∈ Ord (ψ(α) → ψ(α + 1)), e ∀δ(δ ∈ Ord ∧ δ “limite” (∀α < δ ψ(α) → ψ(δ)) então vale ∀α ∈ Ord ψ(α). QED Teorema 2.11 (Definição por recursão em Ord) Suponha que F : V^{∗} → V^{∗} seja uma função de classes e seja a um conjunto. Então existe uma única funcão de classes G : Ord → V^{∗} tal que

1. G(0) = a;

2. G(α + 1) = F (G(α));

3. G(δ) = ⋃_{α<δ} G(α).

Prova:

Seja ψ(g, α) uma fórmula dizendo que g é uma função cujo domínio é o ordinal α + 1 e tal que ∀β < α (g(β + 1) = F (g(β))), e se β for ordinal limite então g(β) = ⋃_{γ<β} g(γ) e que g(0) = a.

Observemos que se valer ψ(g, α) e se β ≤ α, então valerá ψ(g|_{β+1}, β).

Interromperemos a demonstração do teorema para mostrar o seguinte lema.

Lema 2.12 ∀α ∈ Ord ∃!g ψ(g, α).

Prova do Lema:

Por indução em α ∈ Ord.

Para α = 0, basta tomar g = {(0, a)}. Certamente tal g é o único conjunto satisfazendo ψ(g, 0). Suponha que seja válido para α, e seja g o único elemento satisfazendo ψ(g, α). Tomemos

g^{∗} = g ∪ {(α + 1, F (g(α)))}. Então vale ψ(g^{∗}, α + 1), e se valer ψ(g′, α + 1), para algum g′, então, por hipótese de indução, valerá ψ(g′|_{α+1}, α + 1), portanto g′|_{α+1} = g. Mas, daí, g′(α + 1) = F (g(α)) = g^{∗}|_{α+1}, provando a unicidade de g^{∗}.

Agora, suponha que δ ∈ Ord seja limite, e que o lema valha para todo α < δ. Então, para cada α < δ existe uma única g_{α} tal que ψ(g_{α}, α). Seja S = {g_{α} : α < δ}. Então S é um conjunto (pelo axioma da substituição). Pela observação antes deste lema, se α < β < δ, então g_{α} = g_{β}|_{α+1}. Seja g^{∗} = ⋃ S. Então g^{∗} é função, e, usando a hipótese de indução, g^{∗}(0) = a, ∀α < δ (g^{∗}(α + 1)) = F (g^{∗}(α))), e para todo ordinal limite γ < δ, g^{∗}(γ) = ⋃_{α<γ} g^{∗}(α). Também temos que g^{∗} é única com tais propriedades. Definimos g = g^{∗} ∪ {(δ, ⋃_{α<δ} g^{∗}(α))}. Pelos mesmos argumentos usados anteriormente, provamos que tal g é a única função satisfazendo ψ(g, δ). QED

Continuação da prova do teorema 2.11:

Agora basta definirmos G = {(α, x) : ∃g(ψ(g, α) ∧ g(α) = x)}. O lema implica que G é uma função de classes que verifica as hipóteses do teorema. QED

Teorema 2.13 (Recursão em Ord com parâmtetros) Sejam F : V^{∗}×V^{∗} → V^{∗} e H : V^{∗} → V^{∗} funções de classe. Então existe uma única função de classes G : V^{∗} × Ord → V^{∗}, tal que:

1. G(x, 0) = H(x); 2. G(x, α + 1) = F (G(x, α));

3. G(x, δ) = ⋃_{α<δ} G(x, α).

Prova:

Análoga ao teorema anterior. QED

Exercício 2.3 Use o teorema acima para definir soma, produto e exponenciação de ordinais, bem como suas propriedades de associatividade, e distributiva.

3 Cardinais

Seja (P, ≤) um conjunto parcialmente ordenado. Um conjunto C ⊂ P é uma cadeia se for linearmente ordenado. Um elemento a ∈ P é um elemento maximal se, para todo x ∈ P, se a ≤ x então a = x.

Lema 3.1 (Lema de Zorn) Seja (P, ≤) um conjunto parcialmente ordenado e não vazio, tal que toda cadeia (não vazia) em P seja limitada superiormente em P. Então P tem (pelo menos) um elemento maximal.

Prova:

Teorema 3.2 Todo conjunto X pode ser bem ordenado, ou seja, existe uma relação R ⊂ X × X que bem-ordena X.

Prova: Seja f : P (X) \ ∅ → X uma função tal que f(x) ∈ x ∈ X (que existe, pelo axioma da escolha). Por indução transfinita nos ordinais, definimos a função g tal que, para cada α ordinal, g(α) = f(x \ {g(β) : β < α}, se x \ {g(β) : β < α} ≠ ∅, e definimos g(x) = z, caso contr´;ario, sendo z um conjunto qualquer, não pertencente a X.

Seja h : X → {z} ∪ Ord a função h(x) = α ∈ Ord se g(α) = x e h(x) = z, caso tal α não exista. Seja Y = {x ∈ X : h(x) ∈ Ord} e Z a imagem de Y por h. Então Z é ordinal (por que?) e se Y ≠ X, obtemos uma contradição (qual?). QED

Definição 3.3 Um ordinal α ∈ Ord tal que não exista nenhuma função bijetora f : α → β, para nenhum ordinal β < α é chamado de cardinal. Dado um conjunto X, a cardinalidade de X, |X|, é o cardinal α tal que existe função bijetora f : X → α.

Por exemplo, 0 = ∅ é o cardinal correspondente ao conjunto vazio, 1 = {0} = {∅} é o cardinal correspondente aos conjuntos unitários, n + 1 = {0, 1, …, n} é o cardinal dos conjuntos de n + 1 elementos, ℵ_{0} = ω é o primeiro cardinal infinito, e os conjuntos de cardinalidade ℵ_{0} são ditos enumeráveis.

Lema 3.4 (Cantor) Dado o conjunto X, não existe função sobrejetora f : X → P (X).

Prova: Suponha, por absurdo, que exista tal f. Defina Y = {x ∈ X : x ∉ f(x)}. Então Y ∈ P (X) e, portanto deve existir y ∈ X tal que Y = f(y), pois f é sobrejetora. Então se y ∈ Y, por definição, y ∉ f(y) = Y, contradição. Por outro lado, se y ∉ Y, novamente por definição, y ∈ f(y) = Y, outra contradição. Portanto, não pode existir tal f. QED

Em particular, não existe bijeção entre ω e P (ω). Ou seja, existem cardinais maiores que ℵ_{0}. Como um cardinal é um ordinal e a classe dos ordinais é bem ordenada, dado um cardinal κ, existe o cardinal sucessor de κ, denotado κ^{+}, que é o primeiro cardinal maior que κ. Dado um ordinal α, temos |α| ≤ α, por definição. Seja Card a classe dos cardinais.

Lema 3.5 (A função de Hartogs) Existe uma função bijetora e crescente ℵ : Ord → Card\ω. Denotamos ℵ(α) por ℵ_{α}.

Prova: Usamos indução em Ord; ℵ_{0} = 0 = ∅. Suponha definido ℵ_{α}. Definimos ℵ_{α+1} = ℵ_{α}^{+}. Observe que ℵ_{α} < ℵ_{α+1} e que não existe nenhum cardinal entre os dois. Suponha que δ seja ordinal limite e que tenhamos definido ℵ_{α}, para todo α < δ, tal que, se α < β < δ, ℵ_{α} < ℵ_{β} e se λ é um cardinal menor que algum ℵ_{α}, com α < δ, então existe γ < α, tal que λ = ℵ_{γ} (ou seja, até agora a função é crescente e não deixa lacunas nos cardinais). Seja κ = sup_{α<δ} ℵ_{α}, como ordinal. Afirmo que κ é cardinal. De fato, se γ < κ é um ordinal, existe β < δ, tal que γ < ℵ_{β}, pois a seqüência (ℵ_{α} : α < δ) é estritamente crescente. Seja ℵ_{δ} = κ. Por fim, seja κ um cardinal infinito. Então κ ≤ ℵ_{κ} (prove por indução). Portanto existe α ≤ κ, tal que κ = ℵ_{α}. QED

Observe que no final da prova não usamos a desigualdade estrita. Na verdade, existem cardinais κ, tais que, vistos também como ordinais, vale κ = ℵ_{κ}. Por exemplo, considere a seqüência κ_{0} = ℵ_{ω}, κ_{n+1} = ℵ_{κ_{n}}, n ∈ ω, e κ = sup_{n} κ_{n}. Então κ = ℵ_{κ} (prove isto).

Definição 3.6 (Aritmética cardinal) Sejam κ, μ, ν_{i}, cardinais, i ∈ I, sendo que I é um conjunto não vazio. Definimos κ + μ = |κ × {0} ∪ μ × {1}|; κμ = |κ × μ|; ^{κ}μ como sendo o conjunto das funções f : μ → κ; κ^{μ} = |^{κ}μ|; ∑_{i∈I} ν_{i} = | ⋃_{i∈I} ν_{i} × {i}|; ∏_{i∈I} ν_{i} = | ×_{i∈I} ν_{i}| (produto cartesiano).