Teoria dos conjuntos

Charles Morgan^{∗}

∗ versão 1.0, 12/2/01

Sumário

Prefácio Cápitulo 1. Introdução informal para os axiomas. Cápitulo 2. Ordinais, relações bem-fundadas. Cápitulo 3. Axioma de escolha. Cápitulo 4. Aritmética de cardinais Cápitulo 5. Combinatória infinita. Cápitulo 6. Uma olhada rápida à lógica matemática elementaria e aplicações dela para teoria de conjuntos. Cápitulo 7. O universo construível L de Gödel. Cápitulo 8. Forcing./ what did I call it?

Prefácio

Neste prefácio devo explicar porque estou escrevendo o livro e agradecer várias pessoas: Marco Antonio Fernandes e o Departemento de Matemática de UFBa (e Tania), CAPES, meus alunos no curso (particularmente Marival Julião de Araújo, Raimundo Leime Cergeuira e Taís Alves Dias de Azevedo), Regina e Davidson Fernandes dos Santos (e Bethânia), e Bia.

Capítulo 1. Introdução informal para os axiomas de ZF.^{∗}

1.1. Extensão. Nosso concepção de conjuntos vem dos conjuntos de objetos que conhecemos, como N, Q e R, e subconjuntos deles que podemos formar, que são determinados pelas propriedades dos objetos. Para dar duas exemplos muito simples:

{r ∈ R | 0 ≤ r} = {r ∈ R | r tem uma raiz quadrada em R}
{x | x ≠ x} = {n ∈ N | n é par, mas que 2 e um primo}.

(Esse último exemplo dá duas definicões de conjunto vazio, ∅).

A noção de conjunto é uma abstração da noção de propriedade. Então, se X, Y são conjuntos temos (∀x ( x ∈ X ⟺ x ∈ Y)) ⟹ X = Y.

Pode notar immediatemente que isso implica que o conjunto vazio é único:

1.2. Uniões. Logo que temos conjuntos como objetos podemos considerar conjuntos de conjuntos, por exemplo: {x_{i} | i ∈ I } por I alguma conjunto de indices. Temos o conjunto que consiste em todos objetos que pertencem para qualquer x_{i} por i ∈ I. O conjunto indexando I não é relevante para nós, então ⋃{x_{i} | i ∈ I } = ⋃_{i∈I} x_{i} pode ser escrito ⋃ X, onde X = {x_{i} | i ∈ I }.

Tipicamente vamos usar a, b, c, w, x, z, … como nomes de conjuntos, e podemos escrever ⋃ x = ⋃{z | z ∈ x} = {w | ∃z tal que w ∈ z e z ∈ x}. Ou simplesmente: ⋃ x = {w | ∃z ∈ x w ∈ z }.

(Para explicar isso de novo temos

⋃_{y∈x} y = ⋃{y | y ∈ x} = ⋃{z | ∃y ∈ x z ∈ y }.

Então já mudamos nosso pensamento de pensar sobre conjuntos e elementos como coisas diferentes para pensar sobre todos conjuntos como coisas do mesmo tipo onde conjuntos pertencem para outras conjuntos.)

1.3. Conjuntos de potência Se x é um conjunto então P(X) = {Z | Z ⊆ X }, o conjunto de todos os subconjuntos de x é também um conjunto.

Proposição. (Cantor) Não existe uma sobrejeção f : X ⟶ P(X) (uma função f : X ⟶ P(X) tal que por todos Z ∈ P(X) existe x ∈ X tal que f(x) = Z.

Demonstração. Se f fosse uma tal sobrejeção poderíamos considerar {x ∈ X | x ∉ f(x)}, = A, vamos falar. Como A ⊆ X temos que A ∈ P(X) e logo existe a ∈ X tal que A = f(a) desde que f é uma sobrejeção. Mas olhe, agora temos a ∈ A se e só se a ∉ A, uma contradição!

Corolário. A coleção de todos conjuntos não é um conjunto.

∗ versão 1.2, 2/12/00

Demonstração. Vamos chamar a coleção de todos conjuntos por U no momento. Se U fosse um conjunto P(U) seria um conjunto também. Mas P(U) seria o conjunto de todos os subconjuntos de U, então para todos x ∈ P(U) teríamos x ∈ U e logo teríamos P(U) ⊆ U. Então existe uma sobrejeção f : U ⟶ P(U) dado pelo x ↦ x se x ∈ P(U) e x ↦ ∅ se x ∉ P(U). Contradição!

Frase de propoganda: “Não existe um conjunto universal!”

Esse corolário é as veces chamado o paradoxo de Cantor. O paradoxo de Russell pode ser obtido por botando f igual à função de identidade na demonstração de proposição em cima para ver que não existe um coleção {x | x ∉ x}. (Isto é, se {x | x ∉ x}, = r, vamos falar, fosse um conjunto, então a pergunta de se c ∈ c ou c ∉ c daria a mesma contradição.) Claro, não são paradoxos de verdade, mas só fatos impressionantes/memoraveis.

O “paradoxo de Russell” mostra que não pode esperar para usar a extensão de todas propriedades matematicamente–algumas são inerentemente contradictória–e então dá uma razão porque vale a pena desenvolver a teoria dos conjuntos. Porém, eu deveria falar que a teoria de conjuntos começou e continua ser interessante e útil não para evitar paradoxos ou dar fundações ou saúde matemática, mas como uma parte da matemática (como as outras) com sua própria teoria, perguntas, etc., e com ligações matemáticas (no mesmo modo como as outras) com outros áreas.

1.4. Hierarquia cumulativa. Vamos ver o que podemos pegar com o conjunto vazio, conjuntos de potência e uniões, Começemos com V_{0} = ∅ e apliquemos P repetidamente.

V_{0} = ∅
V_{1} = P(V_{0}) = {∅}
V_{2} = P(V_{1}) = {∅, {∅}}
V_{3} = P(V_{2}) = {∅, {∅}, {{∅}}, {∅, {∅}}}
⋮

Depois de todo estes passos finitos, juntemos tudo que já temos: V_{ω} = ⋃{V_{n} | n é finito}.

Agora podemos começar aplicar P de novo: V_{ω+1} = P(V_{ω}), V_{ω+2} = P(V_{ω+1}), …

Pode “gerar” conjuntos em sua imaginação “para sempre.”

(Os “V”s são por von Neumann, a primeira pessoa a pensar nissa hierarquia.)

Definição. Um conjunto (puro) é um membro de alguma V_{α}.

(Na verdade, o uso conjunto “puro” hoje parece muita antiquada – quase-ninguem fala isso e só mencionei o uso caso você encontre tal coisa num livro.)

O universo de conjuntos (gerado de ∅) é a coleção V = {x | ∃α (α indexa um passo na iteração & x ∈ V_{α})}. Como giria podemos falar que V = “ ⋃′′{V_{α} | α indexa um passo na iteração}, mas como vimos, V não é um conjunto e este “união” não é uma união de um conjunto – temos que cada V_{α} é um conjunto mas não podemos tomar a união propriamente dita deles e formar V como um conjunto. Então temos que pensar sobre V como uma entidade não completado, e aí, V deve ser só uma abreviatura para nós – só vamos usa-la (mas tarde) nas coisas como “x ∈ V ” querendo dizer “existe α tal que x ∈ V_{α}.” Mas mesmo assim é útil ter um nome na mão por esta coleção de todos conjuntos. Proposição. Se α vem antes de β como um indice temos V_{α} ⊆ V_{β}. Demonstração. É óbvio se α = β. Se V_{β} foi gerado pelo processo de tomar uma união também é claro (porque V_{α} ∈ {V_{γ} | γ é antes de β como um indice} e então se x ∈ V_{α} temos que x ∈ ⋃{V_{γ} | γ é antes de β como um índice}). Todávia, se V_{β} = P(V_{γ}) por alguma γ temos que saber que V_{α} ⊆ V_{γ} ⟹ V_{α} ⊆ P(V_{γ}). Então vou interromper a demonstração por uma definição. 1.5 Conjuntos transitivos. Definição. Um conjunto x é transitivo se u ∈ v ∈ x ⟹ u ∈ x (se e só se u ∈ x ⟹ u ⊆ x, se e só se ⋃ x ⊆ x). Para acabar a demonstração basta mostrar que cada V_{α} é transitivo. Porque, como V_{α} ⊆ V_{γ} temos x ∈ V_{α} ⟹ x ∈ V_{γ}, e se V_{γ} é transitivo temos x ∈ V_{γ} ⟹ x ⊆ V_{γ}. Então x ∈ V_{α} ⟹ x ⊆ V_{β}. Mas x ∈ V_{α} ⟹ x ⊆ V_{β} se e só se V_{α} ⊆ P(V_{γ}), que é o que quisemos mostrar. Mas todos V_{α} são transitivos pela proxima proposição. Proposição. (i) ∅ é transitivo. (ii) Se x é transitivo então P(x) é transitivo. (iii) Uniões de conjuntos transitivos são transitivos. Demonstração. (i) e (iii) são cada um triviais. (Pode ver porque?) (ii) Se u ∈ v ∈ P(x), temos u ∈ v ⊆ x e então u ∈ x. Mas desde x é transitivo temos que u ⊆ x. Então u ∈ P(x). Então podemos ver que todo V_{α} é transitivo indutivamente usando a proposição. E assim acabo a demonstração que se α é antes de β temos V_{α} ⊆ V_{β}, por indução nos índices. NOTA! Para falar que x é transitivo não quer dizer que ∈ é uma relação transitivo sobre x ou qualquer coisa similar. Usaramos implicitamente o princípio indutivo que ∀α ((∀β < α Pr(β)) ⟶ Pr(α)) ⟶ ∀α Pr(α), onde Pr(.) é uma propriedade de nossos índices. Vamos usar este princípio mostrar a seguinte: Proposição. (∈-induction) ∀x ((∀u ∈ x ϕ(u)) ⟶ ϕ(x)) ⟶ ∀x ϕ(x), por qualquer propriedade ϕ. Demonstração. Mostremos por indução no α que ∀x ∈ V_{α} ϕ(x). Daremos este, ∀x ∈ V_{α} ϕ(x), o nome Pr(α). Para nosso princípio é bastante mostra que para cada α temos ∀β < α Pr(β)) ⟶ Pr(α). Assim, suponha que ∀β < α Pr(β). Tome x ∈ V_{α}. Tem dois casos. Ou V_{α} = P(V_{β}) para um β menor que α, quando x ⊆ V_{β} e para todos u ∈ x temos ϕ(u). Então usando o antecedente para x temos ϕ(x). Porque x era arbitrário temos ∀x ∈ V_{α} ϕ(x), i.e., Pr(α).

Ou V_{α} = ⋃_{β<α} V_{β}, quando existe β < α tal que x ∈ V_{β}. Como já sabemos Pr(β) temos ϕ(x). De novo, porque x era arbitrário temos ∀x ∈ V_{α} ϕ(x), i.e., Pr(α).

Como α era arbitrário temos ∀α ((∀β < α Pr(β)) ⟶ Pr(α)). E agora podemos deduzir que ∀α Pr(α), e então ∀α ∀x ∈ V_{α} ϕ(x), e assim ∀x ϕ(x).

Para evitar fazer muitas demonstrações como esta usemos um princípio, Fundação, equivalente para ∈-indução:

(⋆) Se A é uma propriedade dos conjuntos e existe x tal que A(x) então existe x tal que A(x) e para todos u ∈ x não temos A(u). Simbôlicamente: ∃x A(x) ⟹ ∃x A(x) & ∀y ∈ x ¬A(y)

Nota. Temos a idéia que para qualquer coisa tem que ser um passo o mais cedo em qual a coisa acontece.

Temos mais duas problemas:

(1) Que são as propriedades da hierarquia?

(2) Quanto longe persistir a hierarquia?

Resposta para (2) (parte (a)).

1.6 Infinidade. Precisamos de alguns números naturais. Aqui estão:

0 = ∅
1 = {0}

2 = {0, 1}
3 = {0, 1, 2}
⋮

Nota que se definirmos s(x) = x ∪ {x} temos s(n) = n + 1 para cada n.

Queríamos também um conjunto dos números naturais: N = ω = {0, 1, 2, …}. Assim gostaríamos que ω = ⋂{x | 0 ∈ x & ∀u ∈ x s(u) ∈ x}.

Mas são quaisquer conjuntos infinitos? Bem, sim – mas temos que estipular que existem.

Infinidade. ∃x (∅ ∈ x & ∀u ∈ x s(u) ∈ x).

(Nota. V_{ω} é um tal x.)

Outras noções de infinidade. (1) Infinito = não finito: “∃x ∀n ∈ ω x ≁ n” onde x ∼ u se e só se ∃f : x ⟶ y e f é uma bijeção. (Em palavras: Existe x não numa bijeção com qualquer número natural.) Mas para falar isso precisamos de funções que até agora não temos definidas.

(2) Infinidade do tipo Dedekind: “∃x∃u ⊆ x (x ≠ u & x ∼ u).” (Em palavras: Existe um conjunto com um subconjunto não igual ao conjunto mas do mesmo tamanho.)

Se um conjunto é infinito de tipo Dedekind é infinito. Na outra direção, se um conjunto é infinito, é infinito de tipo Dedekind, mas este precisa de uma pequena porção de axioma de Escolha (para mostrar que se x não é finito x conte um subconjunto enumerável).

Não se preocupa se a última frase não quis dizer muito para você agora… não é uma grande coisa e não vai ser importante para nós. Em qualquer caso, nosso axioma para estipular que temos conjuntos infinitos vai ser o primeiro que dei.

1.7. A língua da teoria dos conjuntos e propriedades. Propriedades são as propriedades que são definíveis numa língua, a língua de teoria dos conjuntos–LTC, com parâmetros entre conjuntos. Podemos escolhar a língua de teoria dos conjuntos para ser muito simples. LTC tem:

(i) variáveis: u, v, x, z, … (ii) símbolos para relações: =, ∈ (iii) ligações de lógica das proposições: & (e), v (ou), ⟶ (implica), ¬ (não), ⟷ (se e só se) (iv) quantificadores: ∀x (para todos x), ∃x (existe x).

Nota: se temos um conjunto a temos que {x | a ∈ x} é uma propriedade e não um conjunto.

Com sorte você entende esta língua informalmente, e então pode raciocinar usando-o. (Se quer entender melhor como fazer estes tipos das coisas mais formalmente deve dar uma olhada no livro do van Dalen.)

Vamos usar algumas abreviaturas naturais: x ≠ z em vez de ¬(x = z) x ∉ z em vez de ¬(x ∈ z)

∀x ∈ z ϕ(x) em vez de ∀x (x ∈ z ⟶ ϕ(x)) ∃x ∈ z ϕ(x) em vez de ∃x (x ∈ z & ϕ(x)) ∃!x ϕ(x) em vez de ∃x (ϕ(x)) & ∀z (ϕ(z) ⟶ z = x), e assim por diante. (Também muitas vezes usarei “ou” em vez de “ v ” para evitar confusão entre “ v ” e “v.”)

Introdução de símbolos por relações e funções. Se tenho um fórmula ϕ(x) em LTC, pois posso introduzir um símbolo novo R_{ϕ}(x) por uma relação e um axioma ∀x(R_{ϕ}(x) ⟷ ϕ(x)). Isso não muda o poder de expressão da língua (o que pode falar na língua). Por exemplo: poderia bota x ⊆ z se e só se ∀u ∈ x u ∈ z, onde ⊆ é nosso símbolo novo.

Similarmente, se temos ϕ(x_{0}, …, x_{k−1}, z) e podemos mostrar (de algumas axiomas) que, escrevendo \overrightarrow{x} por x_{0}, …, x_{k−1}, ∀\overrightarrow{x} ∃!z ϕ(\overrightarrow{x}, z), podemos introduzir um símbolo f_{ϕ}(z) por uma função e um axioma ∀\overrightarrow{x}, y (ϕ(\overrightarrow{x}, y) ⟷ f(\overrightarrow{x}) = y). De novo isso não muda o que a língua pode expressar.

Vou dar alguns exemplos do uso deste língua. Como já encontramos a majoria dos axiomas de Zermelo-Fraenkel parece uma boa coisa usá-los como nesses exemplos.

1.8 Axiomas de teoria dos conjuntos de Zermelo-Fraenkel (ZF)

Os axiomas são (em breve):

Extensão Conjunto Vazio Pares (se temos dois conjuntos temos também o conjunto para quem pertencem exatamente os dois conjuntos) Infinidade Uniões Conjuntos de potência Compreensão (ou formação de subconjuntos) Coleção (até agora não discutido) ∈-indução ou Fundação: Se A não é vazio então A tem um componente que é mínimo em ∈ (∈-mínimo).

Zermelo produz todos além de Coleção e então o sistema sem Coleção e chamado theoria dos conjuntos de Zermelo (Z).

Exercício. Mostrar que Z e verdadeiro em V_{ω+ω}.

E agora de novo, usando LTC, e com algumas comentarios.

Extensão. ∀x ∀y (∀z (z ∈ x ⟷ z ∈ y) ⟶ x = y).

Conjunto Vazio. ∃x ∀y (y ∉ x). Por o axioma de extensão ∃!x ∀y (y ∈ x). Assim podemos introduzir um novo símbolo por um constante ∅ tal que ∀y y ∉ ∅. (Um constante é meramente uma função de 0 variáveis.)

Pares. ∀x ∀y ∃!z ∀u (u ∈ z ⟷ u = x v u = y). Podemos introduzir um simbolo por uma função {., .} com ∀u (u ∈ {x, y } ⟷ u = x v u = y).

(A par de dois conjuntos é único por extensão.)

Agora podemos ver que {∅} ∈ {∅, {∅}} e então 1 ∈ 2 (introduzindo os simbolos 1 e 2 por constantes no modo óbvio por estes conjuntos).

Uniões. ∀x ∃z (u ∈ z ⟷ ∃y ∈ x (u ∈ y)). De novo podemos introduzir um símbolo, ⋃ por uma função e temos ∀x (u ∈ ⋃ x ⟷ ∃y ∈ x u ∈ y).

Conjunto de potência. ∀x ∃!z (y ∈ z ⟷ ∀u ∈ y (u ∈ x)). De novo vamos introduzir um símbolo P com efeito que z ∈ P(x) ⟷ z ⊆ x.

Infinidade. ∃x (∅ ∈ x & ∀y ∈ x (y ∪ {y } ∈ x)). Assim podemos introduzir um símbolo novo por uma função e tomar que s(y) = y ∪ {y } e ω com u ∈ ω ⟷ ∀x ((∅ ∈ x & ∀y ∈ x (y ∪ {y } ∈ x)) ⟶ u ∈ x). Com dois passos mais podemos falar que ω = ⋂{x | ∅ ∈ x & ∀y ∈ x (y ∪ {y } ∈ x)}.

Compreensão e classes. Por uma propriedade de conjuntos quero dizer alguma fórmula ϕ(\overrightarrow{x}, \overrightarrow{a}) onde \overrightarrow{a} = a_{0}, …, a_{n−1} são nomes por alguns conjuntos específicos. A propriedade é verdadeira de b_{0}, …, b_{m−1} = \overrightarrow{b} se e só se ϕ(\overrightarrow{b}, \overrightarrow{a}) é verdadeiro. A extensão de uma propriedade é a coleção dos conjuntos de quais a propriedade é verdadeira. Este coleção é uma subcoleção de V, a coleção de todos conjuntos. Chamamos a extensão de uma propriedade uma classe. Assim uma classe é uma coisa de tipo \{x | ϕ(x, \overrightarrow{a})\}.

Axioma de Compreensão. Para todas fórmulas ϕ(x, \overrightarrow{y}) na língua de teoria dos conjuntos temos ∀x∀a_{0}, …, ∀a_{n−1} ∃y ∀z(z ∈ y ⟷ z ∈ x & ϕ(z, \overrightarrow{a})).

Nota, este “axioma” é na verdade uma esquema dos axiomas: temos uma axioma para todas fórmulas ϕ(x, \overrightarrow{y}) na LTC, e não um axioma só.

Em efeito o esquema fala que para todos x temos que cada x ∩ \{z | ϕ(z, \overrightarrow{a})\} é um conjunto. Então uma classe \{x | ϕ(x, \overrightarrow{a})\} é um conjunto (no sentido que ∃z ∀x (x ∈ z ⟷ ϕ(x, \overrightarrow{a})) se e só se \{x | ϕ(x, \overrightarrow{a})\} ⊆ V_{α} por alguma α. I.e., \{x | ϕ(x, \overrightarrow{a})\} é um conjunto se e só se é limitado na hierarquia.

É muito útil (como vamos ver logo) poder usar várias classes como abreviaturas informais–todo mondo faz isso e vamos fazer isso também. Só que você deveria ficar cauteloso para o fato de que as classes são só abreviaturas e seus usos sempre podem ser eliminados em favor de falar sobre as fórmulas de LTC que define elas.

Por exemplo, se A = \{x | ϕ(x, \overrightarrow{a})\} é uma classe, pode usar b ∈ A como abreviatura por ϕ(b, \overrightarrow{a}) sendo verdadeiro, mas não pode pensar sobre se A ∈ A. Este ultima não é falsa, mas não tem sentido. Similarmente, P (A) não tem sentido.

Se ainda tem perguntas ou dúvidas sobre como usar ou pensar de classes, espere um pouquinho e depois de termos usados classes um pouco acho que coisas aparecerão mas claras.

(Nota técnica: aqui tomamos fórmulas ϕ(x, \overrightarrow{y}) na LTC tal que as variáveis y_{0}, …, y_{n−1} são livres, i.e. podemos botar a_{0}, …, a_{n−1} na fórmula em vez de y_{0}, …, y_{n−1} sem problemas. Por exemplo, cada y_{i} não ocorre na forma ∃y_{i} … ou ∀y_{i}. Para mais informação sobre variáveis livres e uma definição indutiva formal do que são variáveis livres veja o livro de van Dalen ou a seção mais tarde sobre lógica matemática.)

Fundação. Para todas fórmulas ϕ(x, \overrightarrow{a}) na LTC ∃y ϕ(y, \overrightarrow{a}) ⟶ ∃y ϕ(y, \overrightarrow{a}) & ¬∃z ∈ y ϕ(z, \overrightarrow{a}).

Usando classes como abreviaturas este fala que se A é uma classe e não é vazio então A tem um componente que é mínimo em ∈ (∈-mínimo).

Quanto alto é a hierarquia? (b) Suponha que ∀x ∈ u ∃y ϕ(x, y, \overrightarrow{a}). Para cada x existe um primeiro α_{x} tal que ∃y ∈ V_{α_{x}} ϕ(x, y, \overrightarrow{a}) (isso por o axioma da fundação). Então temos uma função mandando u para {α_{x} | x ∈ u} dado por x ↦ α_{x}. Assim {α_{x} | x ∈ u} é um “conjunto” de níveis, e então existe um β tal que α_{x} < β para todos x ∈ u. Assim temos V_{α_{x}} ∈ V_{β} para todos x ∈ u. Se botarmos v = V_{β} temos ∃v ∀x ∈ u ∃y ∈ v ϕ(x, y, \overrightarrow{a}).

Ora! Precisamos de um axioma (bem, em verdade um esquema dos axiomas, mais uma vez) para fazer este “coleta” que dá para nós o conjunto de níveis que usamos em cima.

Axioma de Coleção. Para todas fórmulas ϕ(x, y, \overrightarrow{z}) na LTC (com \overrightarrow{z} variáveis livres) temos o seguinte:

∀\overrightarrow{a} ∀u(∀x ∈ u ∃y ϕ(x, y, \overrightarrow{a}) ⟶ ∃v∀x ∈ u ∃y ∈ v ϕ(x, y, \overrightarrow{a})).

Supreendentemente este esquema implica que a hierarquia persiste por um tempo muito longe.

Princípio de Reposição Para todas fórmulas ϕ(x, y, \overrightarrow{z}) na LTC (com \overrightarrow{z} variáveis livres) temos o seguinte:

∀\overrightarrow{a} (∀u ∃!v ϕ(u, v, \overrightarrow{a}) ⟶ ∀x ∃y ∀z (z ∈ y ⟷ ∃w ∈ x ϕ(w, z, \overrightarrow{a}))).

Usando classes como abreviaturas de novo este fala “Se F é uma operação definavel no V então para todos conjuntos x temos que F |x“x (a imagem da restrição de F para x) é também um conjunto.”

Algumas autores preferem usar o princípio de reposição em vez de Coleção para formular os axiomas de ZF. Eu acho que é melhor usar Coleção (acho mais simples entender que está acontecendo – em parte porque não precisa usar classes para fazer uma abreviatura), mas não faz diferençia formalmente pois a reposição segue de coleção e compreensão.

(Demonstração. Para cada \overrightarrow{a} o lado esquerda dá para todos x que temos ∀u ∈ x ∃(!)v ϕ(u, v, \overrightarrow{a}). Usando o axioma de coleção temos ∃s ∀u ∈ x ∃v ∈ s ϕ(u, v, \overrightarrow{a}). Mas o y que precisamos é uma subcoleção definível de s e então existe para o axioma de compreensão.

1.9. Algumas noções matemáticas úteis. Agora podemos introduzir várias nocões úteis, dando definições na LTC delas.

Definição. Pares ordenados. (x, y) = {{x}, {x, y }}.

Proposição. (a) Para todos x e y, (x, y) é um conjunto.

(b) Para todos x, y, u e v, (x, y) = (u, v) ⟶ x = u & y = v.

Demonstração. (a) Por o axioma de pares (aplicada três veces).

(b) Por o axioma dá extensãoalidade.

Nota: se x = y a definição da que (x, x) = {{x}} e temos que verificar este caso também.

Definição. Produto cartesiano de dois conjuntos. x × y = {(a, b) | a ∈ x & b ∈ y }.

Proposição. Para todos x e y, x × y é um conjunto.

Demonstração. Para todos x e y, x × y é uma subcoleção definível de P(P(⋃{x, y })) e então é um conjunto para os axiomas de compreensão, conjuntos de potência, uniões e pares.

Definição. Relações e funções. Uma relação no produto x × y é um subconjunto de x × y, i.e., um componente de P(x × y). Então vamos escrever, igualmente, Rel(x, y) por P(x × y) como uma ajuda à lembrança. Funções são algumas relações. A coleção de funções de x para y é xy = {f ∈ Rel(x, y) | ∀a ∈ x ∃!b ∈ y (a, b) ∈ f }.

Proposição. Para todos x e y, Rel(x, y) e ^{x}y são conjuntos.

(Poderiamos continuar assim, por exemplo definindo dom(z) = {a | ∃b (a, b) ∈ z } ⊆ ⋃ ⋃ z e im(z) = {b | ∃a (a, b) ∈ z } ⊆ ⋃ ⋃ z, e depois provar, dado que Rel(z) ⟷ ∀x ∈ z ∃a, b (x = (a, b)), temos Rel(z) ⟷ z ⊆ dom(z) × im(z).)

Vamos falar que f : x ⟶ y quando f ∈ ^{x}y, dom(f) = x e im(f) ⊆ y. Queriamos usar a notação f(a) quando f ∈ ^{x}y, a ∈ x e (a, b) ∈ f. Se estamos juntando um nome por uma função definível para a língua deveríamos dar um sentido para qualquer f(x). Então botamos f(a) = b se a ∈ dom(f), e f(a) = ∅ se a ∉ dom(f). Aqui estamos usando f em dois sentidos, um como o nome de um conjunto (a função de x para y), e o outro como um novo símbolo numa extensão por funções definível para LTC. Logo que precisamos botar f(a) (f no segundo sentido) igual 0 se a ∉ dom(f) (f no primeiro sentido). Na prática rapidamente vemos ignorar estas distinções.

Agora podemos definir injetivo, sobrejetivo e bijetivo for funções f ∈ ^{x}y, e então podemos escrever o axioma de infinidade por exemplo:

Infinidade. ∃x ∀n ∈ ω¬∃f ∈ ^{x}n f é bijetivo.

Agora podemos introduzir também o axioma de escolha.

Axioma de Escolha. ∀x ((∀y ∈ x y ≠ ∅) ⟶ ∃f ∈ ^{x} ⋃ x ∀y ∈ x f(y) ∈ y).

Isto fala que para todos conjuntos de conjuntos não-vazios tem uma função que escolha um membro de cada um. Não vou falar mas nisso aqui, porque veremos mas sobre este axioma no cápitulo 3.

Outras coisas similares. Podemos fazer algumas outras definições úteis similares. Se I e {y_{i} | i ∈ I } são conjuntos temos:

Produtos cartesianos gerais. Π_{i∈I}y_{i} = {f : I ⟶ ⋃{y_{i} | i ∈ I } | ∀i ∈ I f(i) ∈ Y_{i} }.

Uniões disjuntas. Σ_{i∈I}y_{i} = {(i, a) | a ∈ y_{i} }. (Às veces pode ver ˙⋃_{i∈I}y_{i} em vez de Σ_{i∈I}y_{i}.)

Quociente de um conjunto por um relação de equivalência. R é um relação de equivalência no x se R é reflexivo, ∀y ∈ x (y, y) ∈ R, R é simétrico ∀y, z ∈ x (y, z) ∈ R ⟷ (z, y) ∈ R e R é transitivo, ∀w, y, z ∈ x (w, y) ∈ R & (y, z) ∈ R ⟷ (w, z) ∈ R. Se R é um relação de equivalência no x temos x/R = {y ∈ P(x) | ∃a ∈ x ∀b (b ∈ y ⟷ (a, b) ∈ R)}.

Proposição. Cada Π_{i∈I}y_{i}, Σ_{i∈I}y_{i} e x/R é um conjunto.

Teorema. A coleção de todos conjuntos, V, é fechado sob

(i) subconjuntos definíveis, (ii) uniões, (iii) produtos indexados por conjuntos, (iv) uniões disjuntos indexados por conjuntos,

(v) espaços de funções (vi) conjuntos de potência (vii) quocientes e também contem N – i.e., um objeto N com uma função s : N ⟶ N que satisfaz os aximas de Peano (que dão as regras que esperamos de conduta da função de sucessor nos números naturais).

Usando este teorema podemos construir mais ou menos qualquer objeto matemática (e é facil augmentar a teorema para monstrar como fazer outras consrtuções matemáticas na teoria dos conjuntos). Estes não são coisas muitas grandes como pode ver para os exemplos seguintes.

Podemos definir + e . nos números naturais indutivemente, primeiro +: n + (m + 1) = s(n + m); e depois .; n.(m+1) = n.m+n. Depois pode definir Z como N ×{0} ˙∪{0}×{1} ˙∪ N ×{2} (⊆ N ×3), com (i, y) < (j, z) se i < j, ou i = j = 0 e z < y, ou i = j = 2) e y < z, por exemplo. (Mas claro também pode esolhar qualquer outro esquema razoavel.) Pode dar as regras para +, . si mesmo. Podemos definir Q como Z × N / ∼ onde ∼ é a relação (a, b) ∼ (c, d) se a.d = b.c. Depois pode definir R pela cortes de Dedekind. Ou também poderia definir, por exemplo, {r ∈ R | 0 < r < 1} pelo expansões binarias, ou pela frações contínuas e tomar R = Z ×{r ∈ R | 0 < r < 1}. (Pode achar informação sobre frações contínuas em qualquer livro bom que tratar da teoria elementar dos números, como, por exemplo, Alan Baker, A Consise Introduction to the Theory of Numbers, Cambridge University Press, páginas 41-42.) Como pode ver estes construçõs são mais ou menos trivias e também tem muito liberdade em fazer-las

Teoria dos conjuntos: Exercícios 1.

1. Escrever uma demonstração do axioma de extensão que o conjunto vazio (se existe) é único. Um ponto estúpido? Suponha que (X, τ) e (Y, σ) são espaços topológicos. Mostre que τ ∩ σ ≠ ∅. Isso é matemática?

2. É a união de uma coleção de conjuntos não vazios também não vazia? É a intersecção de uma coleção de conjuntos não vazios também um conjunto? Deduza do axioma de compreensão que a intersecção de uma classe não vazia de conjuntos é um conjunto.

3. Mostre que o axioma de compreensão com o axioma de infinidade implica que o conjunto vazio existe.

4. Mostre que se ⋃ x ⊆ x, então ⋃(⋃ x) ⊆ x. É o inverso verdadeiro? Mostre que as três fórmulas

seguintes são equivalentes: (i) x ⊆ P(x),  (ii) ⋃ x ⊆ x,  (iii) x = ⋃{y ∪ {y } | y ∈ x}.

5. Quantos membros tem cada V_{n} por n finito? Mostre que V_{ω} é enumerável. Mostre que a função x ⟶ #x, onde #x é definida por indução por “#x é o número que na expansão binária de qual os 1s ocorrem nos lugares i exatamente por estes i que são iguais para #y por alguma y ∈ x” é uma bijeção entre V_{ω} e N.

6. Se x é um conjunto (puro) existe um primeiro lugar α onde x ∈ V_{α} e existe um primeiro lugar β tal que x ⊆ V_{β}. Qual é a relação entre α e β?

7. Seja x um conjunto, e sejam α o primeiro lugar tal que ⋃{P(y) | y ∈ x} ∈ V_{α} e β o primeiro lugar onde P(⋃ x) ∈ V_{β}. Qual é a relação entre α e β?

8. Existe um conjunto x com x ∈ x? Existe uma seqüência de conjuntos … x_{3} ∈ x_{2} ∈ x_{1} ∈ x_{0}?

9. Um conjunto que satisfaz as condições (i)-(iii) de (4) é chamado transitivo. Suponha que x = {x}. (Não considere se tem tal coisas!) É x transitivo?

10. Escrever uma demonstração, usando indução, mostrando que cada V_{α} é transitivo. (Que acontece nos passos limites?)

11. Considere o princípio que cada conjunto pertence a um conjunto transitivo. (Por que isso é implicado pela hierarquia de V_{α}s?)

(i) Mostre que este princípio e a axioma de compreensão implicam o axioma des uniões. (ii) Mostre que este princípio, o axioma de compreensão e o axioma de fundação implicam o princípio de indução no ∈. (O axioma de fundação fala: ∀x(x ≠ ∅ ⟶ ∃y ∈ x (y ∩ x = ∅)).)

12. Sejam todos os membros de x transitivos, mostre que ∈ é uma relação transitiva no x.

13. Mostre que o axioma de pares poderia ser substituido em ZF pelo princípio que para cada conjunto x e cada conjunto y existe um conjunto x ∪ {y }.

14. Mostre que o princípio de reposição, o axioma de conjunto vazio e o axioma de conjuntos de potência mostram o axioma de pares.

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.

(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.

∗ versão 1.2, 1/12/00

(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).

Teoria dos conjuntos: Exercícios 2.

1. Escrever os axiomas para uma ordem parcial e uma ordem total usando ≤ em vez de <, e mostre a equivalençia com os axiomas exprimidos usando <.

2. Mostre que se Y ⊆ X e < é uma relação bem-fundada sobre X, então a restrição de < para Y é também bem-fundada.

3. Mostre que se <_{0} é bem-fundado sobre X_{0} e <_{1} é bem-fundado sobre X_{1}, então <_{0} × <_{1} é bemfundado sobre X_{0} × X_{1}, onde (a_{0}, a_{1})(<_{0} × <_{1})(b_{0}, b_{1}) se e só se a_{0} <_{0} b_{0} e a_{1} <_{1} b_{1}. Mostre que se <_{0} e <_{1} são bem-ordens, então <_{0} × <_{1} é uma bem-ordem também.

4. Suponhamos que < é uma bem-ordem sobre X. Construir de < uma bem-ordem sobre P_{<ω}(X) – o conjunto do todos os subconjuntos finitos de X.

5. (Uma olhada de “teoria de conjuntos descritivo.”) Vamos escrever ^{<ω}ω para ⋃{^{n}ω | n ∈ ω }, o conjunto de todos seqüências finitos dos números naturais. Defina < para u < v se e só se v é uma subseqüência inicial própria de u. (Nota a direção disso!)

(i) Mostre que f : ^{ω}ω ⟶ ω é continuo (com referência para a topologia produto sobre ^{ω}ω que vem de a topologia discreta sobre ω) se e só se < é uma relaçao bem-fundada sobre o conjunto {u ∈ ^{<ω}ω | f não é constante sobre {g ∈ ^{<ω}ω | g prolonga a seqüência u}}.

(ii) Seja T ⊆ ^{<ω}ω tal que u ∈ T e u < v implica v ∈ T. (Falamos que T é uma árvore.) Escreva u_{i} para i^{o}-membro de u, e defina uma relação ≺ sobre T por: u ≺ v se e só se ou u < v, ou existe um i mínimo com u_{i} ≠ v_{i}, e u_{i} < v_{i} para este i (na ordem usual sobre ω). Mostre que < é uma relação bem-fundada sobre T se e só se ≺ é uma bem-ordem de T.

6. Se X ⊆ On é um conjunto mostre que ou ⋃ X ∈ X ou ⋃ X = ⋂{α | ∀β ∈ X β < α}.

7. Ache um subconjunto de R (com a ordem usual) que é isomorfico para ω +ω. (Se você fez pergunta (5): ache T ⊆^{ω} ω tal que existe um isomorfismo entre (T, ≺) e ω + ω que preserva a ordem.)

8. Defina ordens lineares sobre ω que são isomorficas sob isomorfismos que preservão as ordens com: (i) ω^{2}, (ii) ω^{ω}, (iii) Q com a ordem usual.

9. Mostre que α + β = α′ + β′ e β′ > β implica α′ < α, mas o inverso e falso.

10. Quando é α + β um ordinal do tipo limite? E α.β?

11. Sejam α, β ∈ {1, ω, ω.ω }. Quantos possibilidades são para (i) α + β, (ii) α × β?

12. Mostre que sejam α, β ∈ On, então αβ = βα se e só se α^{2}β^{2} = β^{2}α^{2}.

13. Seja α ∈ On. Mostre que existe k < ω e ordinais γ_{0}, …,γ_{k} e nmeros naturais n_{0}, …,n_{k} tal que α = ω^{γ_{k}}.n_{k} + … + ω^{γ_{0}}.n_{0}. (Uma pista: começe para mostrando que α = ω^{β} + δ para alguma ordinal β e alguma δ < ω^{β} e depois analise δ.)

14. Suponhamos que f : On ⟶ On é aumentando estritomente (∀α < β f(α) < f(β)) e contínuo nos limites (seja λ um ordinal do tipo limite, então f(λ) = ⋃{f(α) | α < λ}). Mostre que existe um ζ ∈ On tal que f(ζ) = ζ. Mostre que a função f definida para f(α) = α^{ω} é aumentanda estritomente e contínua nos limites. Qual ordinal é o primeiro tal que f(ζ) = ζ?

Capítulo 3. O axioma de escolha.^{∗}

Agora vamos tratar do ultimo axioma do nosso sistema de teoria dos conjuntos, o axioma de escolha. Vamos mostrar a equivalência entre o axioma de escolha e dois outros princípios muitos úteis.

Axioma de Escolha. (AE) Se x é um conjunto de conjuntos não vazios, então existe uma função que escolha um membro de cada dos conjuntos quem pertencem a x: f : x ⟶ ⋃ x ∀y ∈ x f(x) ∈ x.

Princípio de Bem-Ordenando. (BO) Seja x um conjunto. Então existe uma bem-ordem do x.

Lema de Zorn. (LZ) Seja (X, ≤) um conjunto parcialmente ordenado tal que qualquer subconjunto C que é totalmente ordenado pelo ≤ (i.e. qualquer cadeia no (X, ≤)) tem um limite superior. Então X tem um membro máximo.

Teorema. (AE) ⟺ (BO) ⟺ (LZ).

Demonstração. (LZ) ⟹ (BO). Seja X um conjunto e considerar o conjunto dos bem-ordenandos dos subconjuntos de X. É um conjunto parcialmente ordenado sob a relação de sendo um segmento inicial: (Y, ≤) ≺ (Y′, ≤′) se e só se (Y, ≤) é um segmento inicial de (Y′, ≤′). É claro que qualquer a união de qualquer cadeia é um supremo para a cadeia. Então o lema de Zorn fala que existe um elemento máximo, seja (Z, ≤). Se Z ≠ X podemos escolhar x ∈ X \ Z e ter uma bem-ordem do Z ∪ {x} pelo botando z < x para todos z ∈ Z. Então Z = X e ≤ é um bem-ordem do X.

(BO) ⟹ (AE). Seja x um conjunto de conjuntos não vazios. Seja < uma bem-ordem do x. Podemos tomar f(y) = o membro <-mínimo de y para cada y ∈ x.

(AE) ⟶ (LZ). Seja (X, ⪯) um conjunto parcialmente ordenado tal que qualquer cadeia tem um limite superior. Pelo axioma de escolha podemos achar uma função f : P_{≠∅}(X) ⟶ X tal que ∀A ⊆ X (A ≠ ∅ ⟶ f(A) ∈ A). Vamos usar f para ajudar nós escolhar pela recuraão uma cadeia no (X, ≺) do qual um limite superior será máximo no x.

Para qualquer B ⊆ X defina ↑ (B) = {x ∈ X | ∀b ∈ B b ≺ x}. Seja ⋆ um conjunto que não pertence a x. Pela teorema de recursão (forte) defina uma Função F : On ⟶ X ∪ {⋆} tal que F (α) = f(↑({F (β) | β < α})) se ↑({F (β) | β < α}) ≠ ∅, and F (α) = ⋆ senão.

Se β < α e F (α) ≠ ⋆, então F (β) ≺ F (α). Logo, fosse ⋆ ∉ rge(F) teríamos que F seria uma injeção, e então F^{−1} : im(F) ⟶ On seria uma sobrejeção. Mas im(F) ⊆ X(∪{⋆}) é em qualquer caso um conjunto. Então pelo princípio de reposição teríamos que On seria um conjunto também. Uma contradição! Logo ⋆ ∈ im(F).

Então seja α_{0} mínimo tal que F (α_{0}) = ⋆. Temos que {F (β) | β < α_{0} } é um cadeia no (X, ≺) e ↑({F (β) | β < α_{0} }) = ∅. Se x_{0} é um limite superior de {F (β) | β < α_{0} } então x_{0} é máximo no X. (x_{0} é, então, também o elemento máximo do {F (β) | β < α_{0} } e α_{0} é um ordinal do tipo sucessor.)

∗ versão 1.0, 3/12/00

Nota. Nos exercísios deixei varias conseqüências do axioma para vocês mostrar. Entre elas é um outro equivalente do axioma de escolha: que qualquer produto cartesiano geral é não vazio.

Nota. Taís me perguntou no fim de uma aula se existe alguma coisa para a teoria dos conjuntos parecida à dicotomia entre geometria euclidiana e não-euclidiana. Para dar uma resposta razoável para esta pergunta vale a pena parar um momento para pensar sobre axiomatisação e abstração na matemática mas geralmente. Fazemos abstrações (do qual axiomatisações são um tipo) muito na matemática. Tem ao menos três razões para fazer isso. Ajuda nós entender melhor que estamos fazendo nas situações mais concretos. Este parece ser uma coisa que muitos vezes sentimos ou acreditamos é um bom para nós em se mesmo, e talvez as vezes faz sentir mais seguro. Abstrações muitos vezes esclarecem como tratar outras problemas numa área. E abstrações muitos vezes ajudam nós abrir novos áreas da matemática, criando materias interesantes novos com teoria nova e problemas novos. Quando fazemos essas abstrações nunca temos garantias que qualquer dos razão vai dar certo para nós. Porém nossa experiência é que muitos vezes vale a pena. Simultâneo para abratração temos um processo continuo das coisas abstraitos virando mais concreto com uso. Por exemplo 2^{1/2}, os reis R e mesmo o cardinal ω_{1} que vamos encontrar no cápitulo proximo se tornam mais concreto quando viramos acostumados para eles.

O descobrimento do geometrias não-euclidianas não foi só um resposta para uma pergunta formal sobre os axiomas de Euclid, mas foi importante porque dou muito introspecção na geometria em se mesmo, do dois na área “velha” e não sentido mais amplo que ajudou criar. Até agora parece que precisamos dos axiomas do ZF para explicar nossas idéias sobre conjuntos. Isso é que ninguem tenha tido sucesso iluminando a teoria dos conjuntos ou criando uma vista nova sobre o assunto pelo mudando ou trocando os axiomas do ZF. Não falo que não é possível, mas talvez tem menos probabilidade agora de uma revelações desta natureza depois de um século da pesquisa no assunto (muito intensificada nas ultimas 40 anos) que na epoca do descobrimento do geometrias não-euclidianas – talvez porque agora estamos mais sensível para este perguntas de axiomatizações e modelos (cf. Cápitulo 6).

Embora, talvez um analogia da dicotomia seria ZF com AE e ZF sem AE. ZF com AE é o sistema o mais importante para nós, dando para nós coisas que esperemos dos conjunto, como que produtos cartesianos não são vazio e que cada espaço vectorial tem uma base. Mas estudiando ZF sem AE com alguma outro axioma (como por exemplo o axioma de determinacidade^{†}) pode também dá para nós introspecções úteis sobre a natureza da coleção dos conjuntos, e sobre a teoria ZF com AE. Mas falarei mais sobre este pergunta na §6.

† Veja, por exemplo, Alexander Kechris, Classical Descriptive Set Theory, Springer, 1995, ou Yiannis Moschovakis, Descriptive Set Theory, North Holland, 1980.

Teoria dos conjuntos: Exercícios 3.

1. Demonstrar que os seguintes são equivalentes do axioma de escolha.

(a) Se f : y ⟶ x é uma sobrejeção, então existe uma função g : x ⟶ y tal que g(f(z)) = z para todos z ∈ y.

(b) Para qualquer conjunto x dos conjuntos não vazios existe um conjunto transversal t, i.e., um conjunto t ⊆ ⋃ x tal que ∀y ∈ x y ∩ t = 1.

(c) Para qualquer x, y ou existe uma injeção do x para y, ou existe uma injeção do y para x.

(d) m . m = m para qualquer cardinal m. (Pista: se x é um conjunto considerar os cardinalidades do x e o conjunto dado pelo aplicando o Lema de Hartog para x, i.e., {α ∈ On | α ≺ x}.)

2. Use equivalentes do axioma da escolha para monstrar os seguintes.

(a) Qualquer ordem parcial sobre um conjunto pode ser estendido para uma ordem total sobre o conjunto.

(b) Qualquer espaço vetorial tem uma base.

(c) Quaisquer duas bases dum espaço vetorial tem a mesmo cardinalidade.

(d) Qualquer campo pode ser embutido num campo álgebraicamente fechado.

(e) Qualquer produto de espaços topologicos compactos é compacto.

(e) Existe um conjunto dos reais que não é medidável no sentido de Lebesgue.

3. O axioma de escolha é usado mostrar:

(a) Qualquer conjunto não finito tem um subconjunto enumerável?

(b) Um união de um conjunto enumerável dos conjuntos que são enumeráveis é enumerável? Se sim, explicar como.

4. Para qualquer x vamos escrever P_{<ω}(x) para o conjunto dos subconjuntos de x que são finitos. Mostre que se x é infinito, então x ∼ P_{<ω}. Tem conjuntos x para qual você não precisa do axioma de escolha para mostrar isso?

5. (a) Mostre que (ℵ_{α+1})^{ℵ_{β}} = (ℵ_{α})^{ℵ_{β}}.ℵ_{α+1} para qualquer α, β ∈ On. (Pista: Considerar os casos α ≤ β e β < α individualmente.)

(b) Deduzir que (ℵ_{n})^{ℵ_{β}} = 2^{ℵ_{β}}.ℵ_{n} para qualquer n ∈ ω.

(c) Quando é (ℵ_{ω})^{ℵ_{β}} = 2^{ℵ_{β}}.ℵ_{ω}?

6. (a) Seja I um conjunto e sejam {X_{i} | i ∈ I } e {Y_{i} | i ∈ I } conjuntos tal que não existe uma sobrejeção do X_{i} para Y_{i} para qualquer i ∈ I. Mostre que nao existe uma sobrejeção do ⋃{X_{i} | i ∈ I } para Π{Y_{i} | i ∈ I }. Deduzir que se κ é um cardinal e {μ_{α} | α < κ} e {ν_{α} | α < κ} são conjuntos dos cardinais tal que μ_{α} < ν_{α} para todos α < κ, então temos que Σ{μ_{α} | α < κ} < Π{μ_{α} | α < κ}.

(b) Mostre que qualquer cardinal κ é a soma de cf (κ) cardinais cada um com cardinalidade menos que κ, e logo que κ < κ^{cf (κ)}.

7. Mostrar que se κ é regular e 2^{μ} ≤ κ para todos μ < κ, então Σ{κ^{μ} | μ < κ} = κ.

8. Mosrar que 2^{ℵ_{1}} = ℵ_{2} implica que ℵ_{ω}^{ℵ_{0}} ≠ ℵ_{ω_{1}}.

Capítulo 4. Aritmética dos cardinais.^{∗}

4.1. Noções basicos sobre cardinais.

Somos habitudos comparar o tamanho dos conjuntos pelo vindo se tem uma injeção de um para o outro, ou um bijeção entre os dois.

Definição. Sejam x, y conjuntos. Seja x ⪯ y se existe uma injeção (uma immersão) do x para y (i.e. uma função f tal que para todos z_{0}, z_{1} ∈ x temos que f(z_{0}) = f(z_{1}) ⟹ z_{0} = a_{1}). E seja x ⪯^{∗} y ou se x = ∅ ou se existe uma sobrejeção do y para x (i.e. uma função g tal que para todos z ∈ x existe u ∈ y tal que g(u) = z). Defina x ∼ y se existe uma bijeção f : x ⟶ y (i.e. uma função f do x para y tal que f é uma injeção e uma sobrejeção.

Nossos dois lemas primeiros são claros.

Lema. Se x ⪯ y, então x ⪯^{∗} y

Demonstração. Se x = ∅ tem nada para mostrar. Senão seja f : x ⟶ y uma injeção e seja u qualquer elemento arbitrário do x. Logo, se definimos g : y ⟶ x pelo g(z) = f^{−1}(z) se z ∈ im(f), e g(z) = u é senão, é claro que g é uma sobrejeção.

Lema. O axioma de escolha implica que se x ⪯^{∗} y, então x ⪯ y.

Demontração. Se g : y ⟶ x é uma sobrejeção, seja s_{v} = {u ∈ y | g(u) = v } para todos v ∈ x e seja z = {s_{v} | v ∈ x}. Aplicamos o axioma de escolha para z. Esse dá para nós uma função f : z ⟶ ⋃ z, = y, tal que f(s_{v}) ∈ s_{v} para todos s_{v} ∈ z. Logo a função h : x ⟶ y definida pelo h(v) = f(s_{v}) é uma injeção, porque se temos v_{0}, v_{1} ∈ x e h(v_{0}) = h(v_{1}), então v_{0} = g(h(v_{0})) = g(h(v_{1})) = v_{1}.

Nota. Precisamos do axioma de escolha para establecer este fato. Porém, a teorema seguinte não usa o axioma de escolha.

Teorema. (Schröder-Bernstein) Se x ⪯ y e y ⪯ x, então x ∼ y.

Demonstração. Suponhamos que i : x ⟶ y e j : y ⟶ x são injeções. Defina k : P(x) ⟶ P(x) pelo k(a) = (x \ j“y) ∪ j·i“a para cada a ∈ x. É claro que se a ⊆ b ⊆ x, então k(a) ⊆ k(b).

Tome c = ⋃{a ⊆ x | a ⊆ k(a)}. Então c ⊆ ⋃{k(a) | a ⊆ x & a ⊆ k(a)} ⊆ k(c), porque a ⊆ k(a) ⊆ k(c) quando a ⊆ c. Logo k(c) ⊆ k(k(c)). Então k(c) ⊆ c, e c = k(c). (Nota que até aqui só usamos que k é cresente sobre P(x) e nada mais.)

Defina f : x ⟶ y pelo f(u) = i(u) se u ∈ c, e f(u) = j^{−1}(u) se u ∉ c. Sejam u_{0}, u_{1} ∈ x. Se do dois u_{0}, u_{1} ∈ c é claro que f(u_{0}) = f(u_{1}) implica u_{0} = u_{1}. Similarmente, se u_{0}, u_{1} ∉ c temos que f(u_{0}) = f(u_{1}) implica u_{0} = u_{1} também. E se u_{0} ∈ c e u_{1} ∉ c e f(u_{1}) = v, então v ∉ im(i) e f(u_{0}) ≠ f(u_{1}). Finalmente, se v ∈ y e não existe u ∈ c tal que f(u) = v, então j(v) ∉ c e v = f(j(v)).

∗ versão 1.0, 3/12/00

Definição. Uma noção de cardinalidade é uma Função, card : V ⟶ V, tal que card(x) = card(y) se e só se x ∼ y.

Mesmo sem o axioma de esolha existe uns tais noções. Vamos usar um, paraqual escrevemos x em vez de card(x):

x = α onde α ∈ On é mínimo tal que existe uma bem-ordem de x bijetivo com α,

se existe tais αs, e

x = V_{α} ∩ {y | y ∼ x} onde α é mínimo tal que existe y ∈ V_{α} com y ∼ x, senão.

Nota. Fazemos este definição caso não tem uma bem-ordem do x porque seria indesejável usar a classe de equivalência do x sob ∼, uma classe própria e portanto difícil usar nossas argumentações, em se mesma.

Com o axioma de escolha o princípio (BO) fala que qualquer conjunto pode ser bem-ordenado, então para qualquer conjunto existe um existe um ordinal com qual tem uma bijeção (cf. §2.6). Logo, com o axioma de escolha a cardinalidade de qualquer conjunto é um ordinal.

Exercício. Mostrar que x ∉ On se não existe uma bem-ordem do x.

Definição. (Para qualquer noção de cardinalidade.) Um conjunto m é um cardinal se existe x ∈ V tal que card(x) = m.

m ≤ n se existe x e y tal que card(x) = m e card(y) = n e x ⪯ y.
m + n = card(x × {0} ∪ y × {1}), onde card(x) = m e card(y) = n.
m . n = card(x × y), onde card(x) = m e card(y) = n.
m^{n} = card(^{y}x), onde card(x) = m e card(y) = n.

Proposição. + é comutativo e associativo; . é comutativo, associativo e distributivo sobre +; e m^{n + k} = m^{n} . m^{k} e (m^{n})^{k} = m^{n . k}.

Demonstração. Todos são imediatos das definições.

Algumas outras conseqüências são mostrável sem o axioma de escolha, mas tipicamente usam ⪯ e/ou ⪯^{∗}.

Exemplo. Se k + r = m . n, então ou m ⪯ k ou n ⪯^{∗} r.

4.2. Lema de Hartog.

Como vimos, com o axioma de escolha vamos medir cardinalidade pelos ordinais, então vale a pena establecer algumas relações entre ordinais e cardinais.

Lema de Hartog. Seja x um conjunto. Então {α ∈ On | α ⪯ x} é um conjunto, e, logo, pertence a On. ({α ∈ On | α ∼ x} é um conjunto também.) Além disso, {α ∈ On | α ⪯ x} ⪯̸ x e o ordinal mínimo com este propriedade.

Demonstração. Seja W = {(y, <) | y ⊆ x & < é uma bem-ordem do y }. Então W é um conjunto (porque é um subconjunto do P(x) × P(x × x)). Como vimos na §2.6, pela teorema de recursão forte e o princípio de reposição, existe uma Função, F, levando bem-ordems para os ordinais. Então F “W = {α ∈ On | α ⪯ x} é um conjunto pelo princípio de reposição.

É claro que {α ∈ On | α ⪯ x} é um segmento inicial do On, porque se β < α ⪯ x enão a composição do função de identidade com a injeção do α para x é uma injeção do β para x. Logo {α ∈ On | α ⪯ x} pertence a On. Seja {α ∈ On | α ⪯ x} = β. Fosse β ⪯ x teríamos que β ∈ β, uma contradição! E é claro que se γ < β temos γ ⪯ x.

De agora vamos sempre usar nossa noção, x, de cardinalidade.

Proposição. (i) Seja κ ∈ On um cardinal. κ = κ. (ii) Seja κ ∈ On um cardinal. ∀α < κ κ ⊀ α. (iii) Sejam α, β ∈ On. Então α ≤ β ≤ α implica que β = α.

Demonstração. (i) Lembrar que falar que κ é um cardinal quer dizer que existe alguma x com uma bem-ordem e κ é mínimo tal que x ∼ κ. Escolha um tal x. κ ∼ κ e se α < κ e α ∼ κ então α ∼ x, uma contradição para a minimalidade do κ, do dois porque ∼ é uma relação de equivalência. Logo porque κ se mesmo é bem-ordenado (pelo ∈) temos κ = κ. (ii) Se α < κ e i : κ ⟶ α uma injeção, então im(i) ⊆ α é isormorfico pelo um isomorfismo que preserva ordem para um ordinal único, vamos falar β, ≤ α. Então β < κ e β ∼ κ. (iii) β ≤ α implica β ⊆ α, logo β ⪯ α. Mas α ∼ α ⪯ β, então α ∼ β pela teorema de Schröder-Bernstein.

Nota. Se κ ∈ ω ∪ {ω } temos que ∀α < κ κ ≁ α, e logo κ é um cardinal.

Definição. Seja κ ∈ On um cardinal. Defina κ^{+} = {α ∈ On | α ⪯ κ}.

Corolário do Lema de Hartog. Então κ^{+} ∈ On, κ^{+} é um cardinal, κ < κ^{+}, e κ^{+} ⪯̸ κ. É não existe β ∈ On tal que β < κ^{+} e β tem estes propriedades.

Demonstração. É claro que κ ∈ κ^{+}. Aplice o lema de Hartog para x = κ para ver que κ^{+} é um ordinal e κ^{+} ⪯̸ κ. Se β < κ^{+} temos que β ⪯ κ, e logo κ^{+} ≁ β. Então β ≤ κ e κ^{+} é um cardinal. Conseqüentemente, não existe um ordinal com cardinalidade máximo porque α ≤ α < α^{+} para qualquer α ∈ On.

Definição. Seja κ ∈ On um cardinal. Então κ^{+} é o sucessor cardinal do κ. Falamos que κ é um cardinal do tipo sucessor se existe um cardinal μ tal que κ = μ^{+}, e que κ é do tipo limite senão.

Agora vamos enumerar os ordinais que são cardinais. Os primeiros ω são 0, 1, 2, …, os números naturais. Depois usamos os ordinais em se mesmo para enumerar os ordinais infinitos que são cardinais.

Definição. Pela recursão definamos ℵ : On ⟶ V (On) pelo ℵ_{α} = ω ∪ {γ ∈ On | ∃β < αγ ⪯ ℵ_{β} }. Também escrevemos ω_{α} em vez do ℵ_{α} para qualquer α ∈ On. (ℵ é “alef,” a primeira letra do alfabeto hebraico.)

Proposição. (i) ℵ_{0} = ω. (ii) ℵ_{α} ∈ On é um cardinal para cada α ∈ On (iii) Se κ ∈ On é um cardinal infinito então existe cada α ∈ On tal que κ = ℵ_{α}. (iv) ∀α, β ∈ On, α < β implica ℵ_{α} < ℵ_{β}.

(v) ℵ_{α} é um cardinal do tipo sucessor se α é um ordinal do tipo sucessor, e é um cardinal do tipo limite se α é um ordinal do tipo limite.

Demonstração. (i), (ii) quando α é um ordinal do tipo sucessor, (iv), e (v) são imediatos das definições, usando o lema de Hartog.

(ii) Se λ é um ordinal do tipo limite temos que ℵ_{λ} = ⋃{ℵ_{α}^{+} | α < λ} é um conjunto pelos axiomas de reposição e uniões, e enão e um ordinal. E é um cardinal porque se γ < ℵ_{λ} então existe α < λ tal que γ ∈ ℵ_{α}^{+} = ℵ_{s(α)}, e então γ < ℵ_{α}^{+} < ℵ_{λ}, e logo γ ≁ ℵ_{λ}.

(iii) Seja κ ∈ On um cardinal infinito. Então κ = {γ ∈ On | γ < κ} = {γ ∈ On | γ ⪯ κ & κ ⪯̸ γ } = ω ∪ {γ ∈ On | ∃μ < κ μ é um cardinal & γ ∼ μ}. Logo, se temos que para todos cardinais μ < κ são alefs, então κ é um alef. Então qualquer cardinal κ ∈ On é um alef pelo princípio de indução sobre os ordinais.

Nota. Sem o axioma de escolha pode ser que, por exemplo, 2^{ℵ_{0}} não é um ordinal.

4.3. Cardinais com o axioma de escolha.

Agora vamos assumir o axioma de escolha. Então cada conjunto pode ser bem-ordenado. Logo todos os cardinais são ordinais e a classe dos cardinais é bem-ordenado (como uma subclasse de On).

Proposição. Para todos conjuntos x, y, x ⪯ y se e só se x ≤ y.

Demonstração. x ⪯ y se e só se x ⪯ y. Fosse y < x teríamos que x ⊀ y. Então x ≤ y pela tricotomia.

Corolário. (AE) implica que para quaisquer x, y ou existe uma injeção i : x ⟶ y, ou existe uma injeção j : y ⟶ x.

Demonstração. Comparar x e y no On.

Teorema de produtos. (AC) Seja κ um cardinal. (Equivalentemente, seja κ um alef.) Então κ.κ = κ.

Demonstração. Primeiro nota que a teorema é verdadeira para ω: definando (k, l) ≺ (m, n) se ou k + l < m + n ou k + l < m + n e k < m, ou (k, l) ≺′ (m, n) se ou max{k, l} < max{m, n}, ou max{k, l} = max{m, n} e l < n, ou max{k, l} = max{m, n}, l = n e k < m é claro que ≺ e ≺′ são bem-ordems de ω × ω e exitems bijeções entre elas e (ω, ∈).

Agora usamos indução. Suponhamos que a teorema é verdadeira para todos cardinais infinito menos que κ. Defina uma ordem do κ × κ pelo (α, β) ≺ (γ, δ) se α ∪ β < γ ∪ δ, ou α ∪ β = γ ∪ δ e β < δ, ou α ∪ β = γ ∪ δ, β = δ e α < γ. Nota que {(α, β) | (α, β) ⪯ (γ, γ)} = (γ + 1) × (γ + 1) para qualquer γ < κ

Eu afirmo que esta ordem é uma bem-ordenando. É claro que ≺ é uma ordem parcial. E se (α, β) ⊀ (γ, δ) e (γ, δ) ⊀ (α, β) então α ∪ β = γ ∪ δ, β = δ e α = γ, logo (α, β) = (γ, δ), e temos que ≺ é uma ordem total. Para ver que ≺ é bem-fundada, seja Z ⊆ κ × κ com ∅ ≠ ∅. Seja ρ mínimo tal que existe (α, β) ∈ Z tal que α ∪ β = ρ. Primeiro seja Z_{1} = {(α, β) ∈ Z | α ∪ β = ρ}. Seja β_{0} mínimo tal que existe α com (α, β_{0}) ∈ Z_{1}. Agora seja Z_{2} = {(α, β ∈ Z_{1} | β = β_{0} }. Seja α_{0} mínimo tal que (α_{0}, β_{0}) ∈ Z_{2}. Logo (α_{0}, β_{0}) é ≺-mínimo no Z.

Então existe um único ρ ∈ On tal que (κ × κ, ≺) é isomorfico para (ρ, ∈) pelo uma bijeção que preserva ordem. Seja f : (ρ, ∈) ⟶ (κ × κ, ≺) o isomorfismo. Suponhamos que κ < ρ e que f(κ) = (α, β). Seja γ = α∪β. Então (α, β) ⪯ (γ, γ) e temos uma injeção f|κ : κ ⟶ (γ+1)×(γ+1). Porque κ é infinito temos que γ × γ é infinito, logo γ é infinito. Mas γ < κ, então γ + 1 < κ e γ + 1 < κ. Então, pela hipótese da indução, s(γ).s(γ) = s(γ). Então κ ≺ s(γ) × s(γ) ∼ s(γ) ≺ κ. Uma contradição. Logo ρ = κ.

Então, pelo indução nos ordinais temos mostrado que κ.κ = κ para todos cardinais κ.

Corolário. Seja κ um cardinal infinito e sejam x_{α} conjuntos tal que x_{α} ≤ κ para todos α < κ.

Então ⋃{x_{α} | α < κ} ≤ κ.

Demonstração. Vamos aplicar o axioma de escolha para Y = {y_{α} | α < κ}, onde para cada α < κ pegamos y_{α} = {f | f : x_{α} ⟶ κ é uma injeção}. Logo existe uma função g : Y ⟶ ⋃ Y tal que g_{α} : x_{α} ⟶ κ é uma injeção para todos α < κ. Defina h : ⋃{x_{α} | α < κ} ⟶ κ × κ pelo

h(z) = (α, g_{α}(z)) onde α é mínimo tal que z ∈ x_{α}. Logo ⋃{x_{α} | α < κ} ≤ κ pelo teorema.

Corolário. (i) Sejam κ, μ cardinais e ao menos um infinito. Então κ + μ = max{κ, μ}. (ii) Sejam κ, μ cardinais e ao menos um infinito (i.e., um aleph) e nenhum dos dois 0. Então κ.μ = max{κ, μ}. (iii) Sejam κ, μ cardinais 2 ≤ κ ≤ 2^{μ} e μ um aleph. Então κ^{μ} = 2^{μ}.

Demonstração. (i) Se κ ≤ μ, então μ ≤ κ + μ ≤ μ + μ = 2.μ ≤ μ.μ = μ. (ii) Se 0 < κ < μ, então μ ≤ κ.μ ≤ μ.μ = μ. (iii) 2^{μ} ≤ κ^{μ} ≤ (2^{μ})^{μ} = 2^{μ.μ} = 2^{μ}.

Corolário. ℵ_{α} + ℵ_{β} = ℵ_{α∪β} = ℵ_{α}.ℵ_{β}

Demonstração. ℵ_{α∪β} = ℵ_{max({ α∪β })} = max({ℵ_{α}, ℵ_{β} }).

Então temos fixado + e . nos cardinais. Mas exponciação fica um mistério, e na verdade é aqui onde o assunto começe viver. Cantor soube, como nós, que ℵ_{1} ≤ 2^{ℵ_{0}} e, mais geralmente que ℵ_{α+1} ≤ 2^{ℵ_{α}} para cada α ∈ On, mas não pode mostrar qualquer cardinal entre eles (pares). Então ele conjeturou que o hipótese do continuo (HC), que ℵ_{1} = 2^{ℵ_{0}} foi verdadeiro, e mesmo que o hipótese do continuo geral (HCG) , que ℵ_{α+1} = 2^{ℵ_{α}} foi verdadeiro. Isso é talvez a regra o mais simples posível. Mas como veremos na §6 não tem razão supor que é verdadeiro, porque não é possível mostrar HC dos axiomas do ZF + AE (Cohen, 1963), nem mostrar que é falso (Gödel, 1938). 4.4. Cofinalidade. Agora vamos ver um sentido em qual o HCG é muito simples: ele determina todos os outras regras da exponenciação. Para fazer isso precisamos de um conceito que é muito útil apesar disso também Definição. Sejam α, β ∈ On e f : α ⟶ β uma função. f é cofinal (ou leva α cofinalmente para/no β) se ∀γ < β ∃δ < α (γ ≤ f(δ)). Definição. Seja β ∈ On. A cofinalidade de β, cf (β), (é o mínimo α tal que do qual existe uma função cofinal para β. Logo, cf (β) ≤ β e é um cardinal para qualquer β. E se β é um ordinal do tipo sucessor, então cf (β) = 1 (usando a fun=ção f(0) = ⋃ β). Proposição. Existe uma função cofinal f : cf (β) ⟶ β que é cresente estritamente (σ < τ < cf (β) ⟶ f(σ) < f(τ)), para qualquer β ∈ On. Demonstração. Seja g : cf (β) ⟶ β qualquer função cofinal, e defina f pelo recursão pelo f(τ) = max({g(τ), sup{f(σ) | σ < τ }}) para τ < cf (β). Proposição. Se α ∈ On é do tipo limite e f : α ⟶ β é cofinal e cresente estritamente, então cf (α) = cf (β). Demonstração. Seja g : cf (α) ⟶ α qualquer função cofinal. Então f · g : cf (α) ⟶ β é cofinal. Logo cf (β) ≤ cf (α). E se h : cf (β) ⟶ β é cofinal, então k : cf (β) ⟶ α é cofinal, onde k(τ) = o mínimo σ tal que h(τ) < f(σ). Corolário. cf (cf (β)) = cf (β) para qualquer β ∈ On. Demonstração. Imediato pelas duas proposições prévias. Corolário. Seja α um ordinal do tipo limite. Logo cf (ℵ_{α}) = cf (α). Demonstração. Imediato pela última proposição usando a função ℵ. Definição. Seja β ∈ On é um cardinal infinito. Se cf (β) = β falamos que β é regular. Se cf (β) < β falamos que β é singular. Exemplos. ω é regular. ℵ_{ω} é singular (veja o corolário segundo para ver que cf (ℵ_{ω}) = ω). Até agora não tivemos usado o axioma de escolha nesta seção.

Proposição. (AE) implica κ^{+} é regular para qualquer cardinal κ. Demonstração. Fosse f : α ⟶ κ^{+} cofinal onde α < κ^{+}, então κ^{+} = ⋃{f(γ) | γ < α}. Mas f(γ), α < κ, então f(γ), α < κ^{+} e teríamos que κ^{+} seria a união de κ conjuntos cada um com cardinalidade ≤ κ. Uma contradição pelo primeiro Corolário do teorema dos productos na §4.3. (Nota. Sem (AE) é possível que cf (ω_{1}) = ω.) Um pergunta natural agora é se existem cardinais do tipos limites e regulares também. Se ℵ_{α} é um tal cardinal, então ℵ_{α} = α. Mas isso não é bastante. Por exemplo, se α = ⋃{ℵ_{0}, ℵ_{ω}, ℵ_{ω_{ω}}, …} temos que ℵ_{α} = α mas cf (α) = ω. Então o primeiro cardinal do tipo limite que é regular é mais grande. Definição. κ é inacessível fracamente se é do tipo limite e regular. Definição. (AC) κ é inacessível fortemente se é regular ∀μ < κ 2^{μ} < κ. Proposição. Se κ é inacessível fortemente, é inacessível fracamente. E (HCG) implica que se κ é inacessível fracamente, é inacessível fortemente. Agora vamos usar a noção de cofinalidade ajudar mostrar como (HCG) simplifica a exponenciação dos cardinais. Propsição. Seja κ um cardinal infinito e cf (κ) ≤ μ. Então κ^{μ} ⪯̸^{∗} κ. Demonstração. A demonstração é uma variante do demonstração do Cantor que P(x) ⪯̸^{x} que vimos na §1.1. Seja f : μ ⟶ κ qualquer função cofinal e g : κ ⟶ ^{μ}κ qualquer função. Vamos mostrar que g não pode ser uma sobrejeção. Defina h : μ ⟶ κ pelo h(α) = o membro mínimio de κ \ {(g(β))(α) | β < f(α)}. Se γ < kappa pode escolhar α < μ tal que γ < f(α) porque f é cofinal. Assim tem h(α) ≠ g(γ)(α). Então h ∉ im(g). Corolário. (AE) Seja κ um cardinal infinito e cf (κ) ≤ μ. Então κ < κ^{μ}. Demonstrção. É claro que κ ⪯ κ^{μ}, então pelo proposição e tricotomia κ < κ^{μ}. Corolário. (AE) Seja κ um cardinal infinito, então κ < cf (2^{κ}). Demonstrção. Se cf (2^{κ}) ≤ κ temos que 2^{κ} < (2^{κ})^{κ} = 2^{κ.κ} = 2^{κ}, uma contradição. Proposição. (AE + HCG) Sejam κ, μ cardinais, 2 ≤ κ, μ é ao menos um do κ, μ infinito. Então,

(i) κ ≤ μ ⟶ κ^{μ} = μ^{+}, (ii) cf (κ) ≤ μ < κ ⟶ κ^{μ} = κ^{+}, e (iii) μ < cf (κ) ⟶ κ^{μ} = κ, Demonstrção. (i) Já vimos (sem (HCG)) que κ^{μ} = 2^{μ}. (HCG) fala que 2^{μ} = μ^{+}. (ii) O primeiro corolário em cima fala que κ < κ^{μ}. Mas κ^{μ} ≤ κ^{κ} = 2^{κ}, = κ^{+} pelo (HCG). (iii) μ < cf (κ) fala que qualquer função f : μ ⟶ κ não é cofinal, então ^{μ}κ = ⋃{^{μ}α | α < κ}, e μα ≤ max({α, μ})^{+} ≤ κ. Sem o (HCG) exponenciação pode ser muito mais complicada. Tem muitos coisas que são independente do ZF + AE – não podem ser mostrados nem podem ser mostrados os contrários. (Veja §6 para ganhar um pouco mais explicação disso.) Embora existe algumas resultados que podem ser mostrados do ZF + AE, e várias perguntas abertas importantes. Por exemplo temos os seguintes.

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

E tem o mesmo resultado para outros cardinais κ com ω < cf (κ) < κ. No contraste, a situação é muito diferente para cardinais κ singular com ω = cf (κ).

Teorema. (Gitik-Magidor, 1989) Para qualquer δ < ω_{1} e possível que 2^{ℵ_{n}} = ℵ_{n+1} para todos n < ω, mas 2^{ℵ_{ω}} = ℵ_{δ+1}.

Ainda tem algumas limitações quando cf (κ) = ω.

Teorema. (Shelah, 1989) Se 2^{α_{n}} < ℵ_{ω} para cada n < ω, então 2^{ℵ_{ω}} < min({ℵ_{ω_{4}}, ℵ_{(2^{ω})^{+}} }).

Uma das perguntas mais destacadas neste parte do teoria dos conjuntos é se o “4” na teorema de Shelah em cima pode ser melhorizado, (Talvez para “1,” mas em qualquer modo seria muito importante.)

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 κ.

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.

∗ versão 1.2, 19/12/00

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ć.

Capítulo 6. Lógica matemática: uma introdução super-rápida e algumas aplicações à teoria dos conjuntos.^{∗}

6.1. Línguas (formais) da ordem primeira. Neste cápitulo vamos dar uma olhada muito breve sobre lógica matemática para explicar que foi significado no fim do §4.4. quando falamos que algumas coisas, por exemple (HCG), não são mostrável na sistema ZF nem são mostrável os contrários. Este consideração da lógica matématica ajuderá explicar o que quer dizer falar que pode demonstrar que alguma coisa não é mostrável. O chave para isso é a relação entre que é demonstrável e que é verdadeiro. Este não é nada místico, nem filosofico, mas é uma coisa matemática porque pelo verdadeiro queremos dizer verdadeiro num modelo duma coleção dos axiomas. Botâ-lo num outro modo, é a relação matemática entre sintaxe e semântica. Este assunto é chamado a teoria de modelos. Talvez vai paracer formal no início mas é muito efetivo. Um exemplo recente do poder do assunto é o trabalho célebre de Udi Hrushovski na área da teoria dos números/geometria algebraica aritmética usando métodos da teoria dos modelos. Para pegar mais sobre a teoria de modelos veja o livro de van Dalen para uma explicação mais completo da material desta seção, e posso recomendar os livros Wilfrid Hodges, A shorter model theory, Cambridge University Press(?), 1996(?), ou Bruno Poizat, A course in model theory, Springer, 2000 (ou a versão original em francês, Bruno Poizat, Cours de théorie de modèles, Nur al-Mantiq wal Ma’rifah, Lyons, 1985, que pode pegar do Poizat se mesmo). Infelizmente não tem qualquer livro no português sobre o assunto. E tem um esboço bom e acessível do trabalho de Hrushovski no Ehud Hrushovski, Geometric Model Theory, Documenta Mathematica, Extra Volume, ICM 1998, I, pp. 281-302. (Endereço do email de Poizat e site do artigo de Hrushovski.)

Definição. Uma língua L para lógica da ordem primeira é feito de:

(i) um conjunto enumerável dos variávais v_{0}, v_{1},… (escritos como x, y, z,… quando queremos); (ii) um conjunto dos símbolos para funções f, g,… do várias “áridades” – um símbolo para uma função 0-ária é um símbolo para um constante c; (iii) um conjunto dos símbolos para relações R, S,… do várias áridades, e um símbolo especial = (que é binária); (iv) algumas ligações lógicas: &, ou, ⟶, ¬, ⊥;

(v) quantificadores ∀, ∃; (vi) sinais de pontuação como (, ), ..

Os termos de L são definidos pela uma definição recursiva.

(i) Qualquer variável v é um termo; (ii) se f é um símbolo para um função n-ária e t_{0},…, t_{n−1} são termos, então f(t_{0}, …, t_{n−1}) é um termo também.

Definamos os variáveis livres de um termo t, VL(t) pelo (i) VL(v) = {v } se v é um variável, e (ii) VL(f(t_{0}, …, t_{n−1})) = VL(t_{0}) ∪ … VL(t_{n−1}).

Os fórmulas de L são definidos pela uma definição recursiva junto com a definição dos variáveis livres.

∗ versão 1.1, 15/12/00

(i) Se R é um símbolo para uma relação n-ária e t_{0},…, t_{n−1} são termos, então R(t_{0}, …, t_{n−1}) é um fórmula. VL(R(t_{0}, …, t_{n−1})) = VL(t_{0}) ∪ … VL(t_{n−1}). (Estes fórmulas são chamados fórmulas atômicos.) (ii) Se ϕ e ψ são fórmulas, então ϕ & ψ, ϕ ou ψ, ϕ ⟶ ψ, ¬ϕ, ⊥ são fórmulas também. VL(ϕ & ψ) = VL(ϕ ou ψ) = VL(ϕ ⟶ ψ) = VL(ϕ) ∪ VL(ψ), VL(¬ϕ) = VL(ϕ) e VL(⊥) = ∅. (iii) Se ϕ é um fórmula e x ∈ VL(ϕ), então ∀x ϕ e ∃x ϕ é um fórmula também. VL(∀xϕ) = VL(∃xϕ) = VL(ϕ) \ {x}.

Então os variáveis livres de um fórmula ϕ são os variáveis “sobre qual ϕ fala alguma coisa.” Um fórmula ϕ é um frase se VL(ϕ) = ∅. Escreva ϕ(x̄) se x̄ é o fio x_{0},…, x_{n−1} e ϕ é um formula tal que VL(ϕ) ⊆ {x_{0}, …, x_{n−1} }.

Nota. Podemos definir todos as ligações e quantificadores usando so ou, ¬ e ∃ – que economizer no tempo mas tarde – se definimos ϕ & ψ = ¬(¬ϕ ou ¬ψ), ϕ ⟶ ψ = (¬ϕ ou ψ), ⊥= ¬(ϕ ou ¬ϕ) e ∀x ϕ = ¬∃x (¬ϕ).

Também precisamos uma definição de como substituir um termo em vez de um variável num termo ou num fórmula. Temos que ter cuidado com isso para preservar o sentido pretentido dum fórmula, porque se, por exemplo, ϕ é ∃y (y = x) e t = f(y) queremos que o resultado da substitução do t em vez de x não é ∃y (y = f(y)) mas ∃z (z = f(y)).

Então s[t/x], ϕ[t/x], o resulatado da substitução do t para x, é definido pela recursão:

v_{i}[t/x]  = t se x = v_{i}, e
= v_{i} senão;
f(s_{0}, …, s_{n−1})[t/x] = f(s_{0}[t/x], …, s_{n−1}[t/x]);
R(s_{0}, …, s_{n−1})[t/x] = R(s_{0}[t/x], …, s_{n−1}[t/x]);
(¬ϕ)[t/x]  = ¬(ϕ[t/x]);
⊥ [t/x]  =⊥;
(ϕ & ψ)[t/x]  = ϕ[t/x] & ψ[t/x];
(ϕ ou ψ)[t/x]  = ϕ[t/x] ou ψ[t/x];
(ϕ ⟶ ψ)[t/x]  = ϕ[t/x] ⟶ ψ[t/x];
(∀y ϕ)[t/x]  = ∀yϕ se x = y,
= ∀y (ϕ[t/x]) se y ≠ x e y ∉ VL(s), e
= ∀z ((ϕ[z/y])[t/x]) se y ≠ x e y ∈ VL(s), onde z

é uma escolha de alguma coisa z ∉ VL(s) ∪ VL(ϕ);

(∃y ϕ)[t/x]  = ∃yϕ se x = y,
= ∃y (ϕ[t/x]) se y ≠ x e y ∉ VL(s), e
= ∃z ((ϕ[z/y])[t/x]) se y ≠ x e y ∈ VL(s), onde z

é uma escolha de alguma coisa z ∉ VL(s) ∪ VL(ϕ).

A relação |– de derivação sintática vem de pensar sobre arvores de dedução com hipóteses nas folhas e a conclusão na base, feito das deduções “primativas.”

Formalmente definimos |– pela recursão. A definição é para fórmulas ϕ (uma conclusão) pela recursão na estrutura de ϕ e para qualquer conjunto dos fórmulas Γ (os hipóteses), na mesma hora.

No inicio temos Γ|– ϕ se ϕ ∈ Γ;

e: se Γ|– ϕ e Γ|– ψ,  então Γ|– ϕ & ψ;
se Γ|– ϕ & ψ,  então Γ|– ϕ;
se Γ|– ψ & ψ,  então Γ|– ψ;
ou: se Γ|– ϕ,  então Γ|– ϕ ou ψ;
se Γ|– ψ,  então Γ|– ϕ ou ψ;
se Γ|– ψ ou ψ, Γ ∪ {ϕ}|– χ e Γ ∪ {ψ }|– χ,  então Γ|– χ;
implicação: se Γ ∪ {ϕ}|– ψ,  então Γ|– ϕ ⟶ ψ;
se Γ|– ϕ ⟶ ψ e Γ|– ϕ,  então Γ|– ψ;
não/falso: se Γ ∪ {ϕ}|– ⊥,  então Γ|– ¬ϕ;
se Γ|– ⊥,  então Γ|– ϕ para qualquer ϕ;
se Γ|– ϕ e Γ|– ¬ϕ,  então Γ|– ⊥;
se Γ ∪ {¬ϕ}|– ⊥,  então Γ|– ϕ;
tudo: se Γ|– ϕ(x) e x ∉ ⋃{VL(ψ) | ψ ∈ Γ},  então Γ|– ∀x ϕ(x);
se Γ|– ∀x ϕ(x) e t é um termo,  então Γ|– ϕ[t/x];
existe: se Γ|– ϕ[t/x],  então Γ|– ∃x ϕ(x);
se Γ|– ∃x ϕ(x) e Γ ∪ {ϕ(y)}|– ψ e y ∉ VL(ψ), então Γ|– ψ.
igualidade: se s é um termo,  então Γ|– s = s;
se Γ|– s = t e Γ|– ϕ[s/x],  então Γ|– ϕ[t/x].

E porque na definição da introdução do tudo não falamos só que “se Γ|– ϕ(x) e x ∉ ⋃{VL(ψ) | ψ é usado na demonstração do ϕ(x) do Γ & ψ ∈ Γ}, então Γ|– ∀x ϕ(x),” temos que juntar que:

se Δ ⊆ Γ e Δ|– ϕ, então Γ|– ϕ.

Definição. Γ é consistente se Γ |̸– ⊥. Equivalentemente Γ é consistente se não existe um ϕ tal que Γ|– ϕ & ¬ϕ. As vezes escrevemos Con(Γ) para querer dizer que Γ é consistente.

Depois de todos estas definições eu deveria dar algumas exemplos. Porque agora estou muito atrasado vou evitar fazer isso.

Definição. Sejam L uma língua da primeria ordem, Γ uma coleção das frases e ϕ uma frase no L. d é uma derivação do ϕ de Γ se d é um liste (ou fio) finito dos fórmulas, ϕ_{0}, …, ϕ_{n} para alguma n < ω, com ϕ = ϕ_{n} e tal que para cada m ≤ n temos ou ϕ_{m} ∈ Γ ou ϕ_{m} pode ser obtido pela aplicando uma das cláusulas basicas da definição do |– para {ϕ_{i} | i < m}.

6.2. Modelos é as teoremas de completude e de compacidade.

Vamos escrever Γ ⟹ ϕ para nossa noção matemática informal de ϕ segue do Γ. (Por exemple muitos vezes no curso até agora temos mostrado que ZF ⟹ ϕ para ϕ uma frase sobre conjuntos.) É claro da definição do |– que se Γ|– ϕ, então Γ ⟹ ϕ. Agora vamos introduzir uma noção de “segue semânticamente.”

Definição. Seja L uma língua da ordem primeira como no §6.1. M é uma estrutura para L se M = (M, f^{M}, g^{M}, …, R^{M}, S^{M}, …) onde M é um conjunto, f^{M}, g^{M},… são funções tal que f^{M} : ^{n}M ⟶ M se f é n-ário, e R^{M}, S^{M},… são relações sobre M com R^{M} ⊆ ^{n}M se R é n-ário.

Agora vamos definir quando uma estrutura pensa que uma frase é verdadeira.

Definição. Seja L uma língua da ordem primeira e M é uma estrutura para L. Seja ϕ uma frase no L. Definamos ϕ é verdadeiro no M, escrevendo M ⊧ ϕ pela recursão sobre a forma do ϕ.

M ⊧ R(a_{0}, …, a_{n−1}) se e só se (a_{0}, …, a_{n−1}) ∈ ^{n}M;
M ⊧ ϕ & ψ  se e só se M ⊧ ϕ e M ⊧ ψ;
M ⊧ ϕ ou ψ  se e só se M ⊧ ϕ ou M ⊧ ψ;
M ⊧ ¬ϕ  se e só se M |̸= ϕ;
M ⊧ ϕ ⟶ ψ  se e só se M |̸= ϕ ou M ⊧ ψ;
M ⊧ ∃x ϕ(x)  se e só se existe a ∈ M e M ⊧ ϕ(a);
M ⊧ ∀x ϕ(x)  se e só se para cada a ∈ M temos que M ⊧ ϕ(a).

Nota. Sejam L uma língua da ordem primeira e M é uma estrutura para L. Então M |̸=⊥ pela definição do ⊧.

Por exemplo, se L = {e, ., ^{−1} }, a língua da teoria dos grupos, e M ⊧ (∀x x.x^{−1} = e = x^{−1}.x) & (∀x x.e = x = e.x) & (∀x∀y ∀z (x.y).z = x.(y.x)) (logo M é um grupo), então pode ser ou não que M ⊧ ∀x∀y x.y = y.x, mas certamente M |̸= ∃x x.x^{−1} ≠ e.

Definição. Γ ⊧ ϕ se para todos estruturas M para a língua L temos que se M ⊧ ψ para cada ψ ∈ Γ, então M ⊧ ϕ.

Definição. M é um modelo de um conjunto de frases Γ para uma língua L se M é uma estrutura para L e M ⊧ ϕ para cada ϕ ∈ Γ. Escrevemos M ⊧ Γ.

É claro pela definição do ⊧ que se Γ ⟹ ϕ então Γ ⊧ ϕ. Logo temos o seguinte.

Proposição. (Teorema de saúde (“soundness” no inglês).) Se Γ|– ϕ, então Γ ⊧ ϕ.

Corolário. Se Γ, um conjunto das frases, tem um modelo, então Γ é consistente.

Demonstração. Se Γ não é consistente, então Γ|– ⊥, logo Γ ⊧⊥. Mas não existe estruturas M qualquer tal que M ⊧⊥, pelo definição de ⊧, então não existe qualquer estrutura M tal que M ⊧ Γ.

Mas também temos o inverso para a proposição.

Teorema de completude. Se Γ ⊧ ϕ, então Γ|– ϕ.

Isso é mais profundo, porque fala que tem uma tradução dum procedimento infinito (confirmindo que cada modelo do Γ, cada um do qual pode ser infinito, é um modelo do ϕ também) para um procedimento finito (uma derivação do ϕ de Γ). Para demonstrar a teorema é conveniente introduzir um par das definições.

Definição. Uma coleção das frases Δ numa língua L é uma teoria de tipo Henkin se sempre que ∃xϕ(x) ∈ Δ, existe um constante c ∈ L tal que Δ|– ∃xϕ(x) ⟶ ϕ(c). Então c é uma testemunha para a frase ∃xϕ(x).

Observação. Se Δ, numa língua L, é uma teoria de tipo Henkin, e Δ′ é uma coleção de frases na mesma língua L, Δ ⊆ Δ′, então Δ′ é uma teoria do tipo Henkin.

Definição. Se Δ é uma coleção das frases numa língua L e Δ ⊆ Δ′, uma coleção das frases numa lingua L′ com L ⊆ L′, falamos que Δ′ é uma extensão conservadora de Δ se Δ|– ϕ se e só se Δ′|– ϕ para cada ϕ ∈ L. (E então Δ′ é consistente se Δ é consistente, porque ⊥∈ L e, logo, Δ′|– ⊥ se e só se Δ|– ⊥.)

Proposição. Se Δ é uma coleção das frases numa língua L, existe uma coleção das frases Δ′ numa lingua L′ tal que L ⊆ L′, Δ ⊆ Δ′, Δ′ é uma teoria do tipo Henkin e com Δ′ uma extensão conservadora de Δ (e com L′ = L + ω também).

Demonstração. Seja Γ qualquer coleção das frases numa língua K. Juntar constantes distintos c_{ϕ} para K para cada fórmula ϕ(x) com variável livre x no K para chegar no K^{∗} = K ∪ {c_{ϕ} | ϕ(x) ∈ L}. Seja Γ^{∗} = Γ∪{∃xϕ(x) ⟶ ϕ(c_{ϕ}) | Γ|– ∃xϕ(x)}. Vamos mostrar que Γ^{∗} é uma extensão conservadora de Γ.

Suponhmos que Γ^{∗}|– ψ para ψ ∈ K. Então existe n < ω e fórmulas ϕ_{i} para i < n tal que Γ ∪ {∃xϕ_{i}(x) ⟶ ϕ_{i}(c_{ϕ_{i}}) | i < n}|– ψ. Seja Γ^{m} = Γ ∪ {∃xϕ_{i}(x) ⟶ ϕ_{i}(c_{ϕ_{i}}) | i < m} para cada m ≤ n. Mostraramos que se Γ^{m+1}|– ψ temos que Γ^{m}|– ψ, para qualquer m < n, e,logo, pela indução, que Γ = Γ^{0}|– ψ. Se n = 0 não tem nada fazer. Então suponhamos que n ≠ 0 e seja m < n.

Se Γ^{m+1} = Γ^{m} ∪ {∃xϕ_{m}(x) ⟶ ϕ_{m}(c_{ϕ_{m}})}|– ψ, temos que Γ^{m}|– (∃xϕ_{m}(x) ⟶ ϕ_{m}(c_{ϕ_{m}})) ⟶ ψ. Então, temos que Γ^{m}|– ∃y(∃xϕ_{m}(x) ⟶ ϕ_{m}(y)) ⟶ ψ pela definição de |– , especificamente a regra para introdução dos quantificadores existenciais, porque c_{ϕ_{m}} ∉ K e, logo, não aparece nos fórmulas ϕ e ψ. Logo Γ^{m}|– (∃xϕ_{m}(x) ⟶ ∃y ϕ_{m}(y)) ⟶ ψ, e então Γ^{m}|– ψ.

Agora sejam Δ_{0} = Δ e L_{0} = L, sejam Δ_{i+1} = Δ_{i}^{∗}, L_{i+1} = L_{i}^{∗} para cada i < ω, e sejam Δ′ = ⋃{Δ_{i} | i < ω } e L′ = ⋃{L_{i} | i < ω }. Temos que Δ′ é uma extensão conservadora de Δ. E Δ′ é uma teoria de tipo Henkin porque se ∃xϕ(x) ∈ Δ temos que ∃xϕ(x) ∈ Δ_{i} para alguma i < ω e então (∃xϕ(x) ⟶ ϕ(c_{ϕ})) ∈ Δ_{i+1} ⊆ Δ.

Demonstração de teorema de completude. Seja Γ uma coleção das frases numa língua L, e ϕ um fórmula na língua L. Para demonstrar a teorema mostramos que se Γ |̸– ϕ tem um modelo de Γ ∪ {¬ϕ} (e então Γ |̸= ϕ).

Pela proposição, seja Γ′ uma teoria do tipo Henkin tal que Γ ∪ {¬ϕ} ⊆ Γ′ numa língua L′ com L ⊆ L′ e L′ = L + ω. Considerar o conjunto das coleções das frases Δ tal que Δ é na língua L′, Δ é consistente, e Γ′ ⊆ Δ, ordenado pelo Δ ≤ Δ^{∗} se Δ ⊆ Δ^{∗}. Cada cadeia na ordem tem um limite superior, então podemos usar a Lema de Zorn para escolhar uma teoria Γ_{max} que é maximal tal que Γ_{max} é na língua L′, Γ_{max} é consistente, e Γ′ ⊆ Γ_{max}. Nota que Γ_{max} é do tipo Henkin (pela observação). Também, se Γ_{max}|– ψ, temos que ψ ∈ Γ_{max} pela maximalidade de Γ_{max}; se ∃xψ(x) ∈ Γ_{max}, então temos um constante c ∈ L tal que ψ(c) ∈ Γ_{max}; se ψ ou χ ∈ Γ_{max} temos que ψ ∈ Γ_{max} ou χ ∈ Γ_{max}; e ¬ψ ∈ Γ_{max} se e só se ψ ∉ Γ_{max}.

Agora vamos usar os termos se mesmos na língua L′ como os elementos dum modelo para Γ_{max}. Deveria ficar certa cá que entende como estamos usando termos, coisas síntacticas, como objetos para formar uma estrutura semântica. Seja A = {t ∈ L′ | t é um termo no L′ }. Se f é um símbolo para uma função n-ária no L′, seja f^{A} : ^{n}A ⟶ A definido pelo f^{A}(t_{0}, …, t_{n−1}) = f(t_{0}, …, t_{n−1}), um termo também. E se R é um símbolo para uma relação n-ária no L′, define um subconjunto R^{A} do ^{n}A pelo (t_{0}, …, t_{n−1}) ∈ R^{A} se e só se (t_{0}, …, t_{n−1}) ∈ R.

Estamos perto ao fim da demonstração mas poderia ser que temos termos s, t tal que ‘s = t’ ∈ Γ_{max}, então temos que pegar o quociente de A sob este relação para chegar numa estructura para L′. Logo seja s ∼ t se ‘s = t’ ∈ Γ_{max} para s, t ∈ A, e seja [s] = {t ∈ A | t ∼ s} para s ∈ A. Formamos uma estrutura M pelo tomando M = {[s] | s ∈ A}, f^{M}([t_{0}], …, [t_{n−1}]) = [f(t_{0}, …, t_{n−1})] se f é um símbolo para uma função n-ária no L′, e ([t_{0}], …, [t_{n−1}]) ∈ R^{M} se e só se (t_{0}, …, t_{n−1}) ∈ R^{A} onde R é um símbolo para uma relação n-ária no L′. Temos que M = (M, f^{M}, …, R^{M}, …) é uma estructura para L′, e M ⊧ ψ se e só se ψ ∈ Γ_{max} para ψ ∈ L′ pela indução sobre a estrutura das frases, usando as observações que seguem da maximalidade de Γ_{max} na ultima frase do paragráfo primeiro desta demonstração. Logo N = (M, f^{M}, …, R^{M}, … | f ∈ L) é uma estructura para L e N ⊧ Γ ∪ {¬ϕ}.

Corolário. (Existência de modelos). Se Γ, um conjunto das frases, é consistente, então Γ tem um modelo. Além disso, se Γ é numa língua L e L = κ, então Γ tem um modelo N com N = ω + κ.

Demonstração. Se Γ não tem um modelo, então temos que M ⊧ Γ implica M ⊧ ϕ para qualquer ϕ. Logo Γ ⊧ ϕ para qualquer ϕ, logo Γ ⊧⊥. Então Γ|– ⊥ pela teorema.

Além disso, na demonstração da teorema chegamos num modelo N do Γ do qual os elementos são classes de equivalência dos termos da língua L′. Então N ≤ L′^{<ω} = L′ = L + ω = κ + ω.

Corolário. (Compacidade). Se Γ é um conjunto das frases e cada subconjunto finito Δ ⊆ Γ tem um modelo, então Γ tem um modelo também.

Demonstração. Se Γ não tem um modelo, então temos que Γ|– ⊥ pelo corolário sobre a existência de modelos. Mas se Γ|– ϕ temos que existe um Δ ⊆ Γ finito tal que Δ|– ϕ, para qualquer ϕ, porque demonstrações são finitárias. Então existe alguma Δ ⊆ Γ finito tal que Δ|– ⊥. Logo Δ não tem um modelo, uma contradição para o hipótese!

Exemplo. Seja L = {0, +, ., s, <, exp, =} uma língua da ordem primeira onde exp é binaría, seja N = (ω, 0^{N}, +^{N}, .^{N}, s^{N}, <^{N}, exp^{N}, =^{N}) onde exp(x, y) = x^{y}, e seja Γ o conjunto das frases que são verdadeiras sobre aritmética, i.e., para N (ou poderia tomar Γ ser os axiomas para a aritmética de Peano). Juntar um constante novo c para L, chegando no L′ = L ∪ {c}, e considerar Γ′ = Γ∪{s(s(… (s(0)))) < c | n < ω &s(s(… (s(0)))) é s aplicado n vezes para 0}. As frases novas no Γ′ \ Γ falam que n < c para cada n < ω porque n = 0 + 1 + 1 + … + 1 n vezes.

Afirmo que Γ′ tem um modelo. Demonstração: se Δ ⊆ Γ′ é finito temos que Δ \ Γ é finito, então existe alguma m_{Δ} < ω tal que para cada frase da forma n < c (i.e. da forma s(s(… (s(0)))) < c com n aplicacões do s, formalmente) tal que n < c ∈ Δ temos que n ≤ m_{Δ}. Logo Δ tem um modelo N = (ω, 0^{N}, +^{N}, .^{N}, s^{N}, <^{N}, exp^{N}, =^{N}, c_{Δ}^{N}), onde c_{Δ}^{N} é qualquer número natural maior que m_{Δ}. Logo Γ′ tem um modelo pelo teorema de compactidade, e o modelo é um modelo para aritmética que é não-normal porque tem números naturais infinitos, então o modelo não é N.

Exemplo. (Analyse “não-padrão”.) Nos origems de calcúlo, que pode argumentar razoávelmente foi o início de todo matemática moderna, Newton e Liebniz e os seguidaores deles falavam e racionaciavam sobre quantidades infinitamentes pequenhos e infinitamentes grandes para chegar nos resultados deles. No seculo 19^{o} ninguem conseguiu no fornecendo uma formalização satisfatória destas raciocinações, e com tempo caiem do favor, sendo reposto para o método do ϵ-δ de Kronecker como sendo “mais seguro.” Agora, pela teorema de compacidade podemos recobrir a possibilidade de usar estas intuições originais de Newton e Liebniz.

Seja L = {+, −, ., <, 0, 1} e seja T o conjunto das frases verdadeiras sobre os reis com a estrutura esperada, (R, +^{R}, −^{R}, .^{R}, <^{R}, 0^{R}, 1^{R}), nesta língua. Seja L′ = L∪{c}, onde c é um símbolo novo para um constante, e seja Γ = T ∪{O < c < y & y.(1+1 …+1) | 1+1+…+1 é a suma de 1 n vezes & n < ω }. Como no exemplo prévio Γ tem um modelo, vamos falar R^{∗}, em qual existe um c tal que 0 < c e c < 1/n para cada número natural n, isso é tal que c é infintessimal. Nota que porque ∀x ∃yx.y = 1 ∈ T temos elementos infinitos do R^{∗} também.

Corolário. (Extensão por definicões.) Suponhamos que L é uma língua, Γ um conjunto das frases para L. (i) Se ϕ(x̄) é um fórmula, sejam L′ = L ∪ {R_{ϕ} } e Γ′ = Γ ∪ {∀x̄ (ϕ(x̄) ⟷ R_{ϕ}(x̄))}. Então para cada ψ ∈ L temos que Γ′ ⊧ ψ se e só se Γ ⊧ ψ. (ii) Se ϕ(x̄, y) é um fórmula e Γ|– ∀x̄ ∃!y ϕ(x̄, y), sejam L′ = L ∪ {f_{ϕ} } e Γ′ = Γ ∪ {∀x̄ ∀y (ϕ(x̄, y) ⟷ f_{ϕ}(x̄) = y)}. Então para cada ψ ∈ L temos que Γ′ ⊧ ψ se e só se Γ ⊧ ψ.

Demonstração. “⟸” é trivial em cada caso. “⟹”: Seja M um modelo para Γ. É trivial expandir M para uma estrutura M′ para L′ que é um modelo, no caso (i), para Γ′ pelo interpretando R_{ϕ} ser o que ϕ escolha no M, i.e., pelo tomando R_{ϕ}^{M′} = {ā ∈ M | M ⊧ ϕ(ā)}, e, similarmente, no caso (ii) pelo tomando f_{ϕ}^{M′}(ā) = o único b tal que M ⊧ ϕ(ā, b). Agora, se temos ψ ∈ L e Γ′ ⊧ ψ então temos que M′ ⊧ ψ (pela teorema de saúde), logo M ⊧ ψ, logo Γ ⊧ ψ (pela teorema de completude).

Nota. Pelo corolário temos que podemos fazer uma seqüência finita das extensões duma língua por definicões.

6.3. Modelos de fragmentos da teoria dos conjuntos.

Nesta seção veremos que tem modelos de vários fragmentos de ZF. Isso é, que podemos mostrar dos axiomas de ZF que existem modelos destes fragmentos. Na verdade os modelos dos fragmentos que consideramos são razoávelmente fácil definir.

ZF\{Infinidade} (= ZF-I). (V_{ω}, ∈) ⊧ ZF - I. Pode ver isso fácilmente, confirmando os axiomas um por um. (E é claro que (V_{ω}, ∈) |̸= Infinidade.) Logo ZF|– Con(ZF-I).

ZF\{Reposição ou coleção} (= Z). Pode mostrar fácilmente, confirmando os axiomas um por um, que para cada ordinal λ do tipo limite tal que ω < λ temos (V_{λ}, ∈) ⊧ Z. No outro lado, como vimos na §1.7, (V_{ω+ω}, ∈) |̸= “Coleção ” porque, por exemplo, {ω + n | n ∈ ω } é a imagem duma Função sobre o conjunto ω, mas não é um membro do V_{ω+ω}. (Ou porque tem mais que ω + ω bem-ordems que são membros do V_{ω+ω}, então V_{ω+ω} |̸= Φ se Φ é a teorema que fala que cada bem-ordem é isomorfico para um ordinal numa moda que preserva a ordem.) (Logo ZF|– Con(Z).)

ZF\{Conjuntos de potência} (= ZF-P). Se κ é um cardinal regular seja H_{κ} = {x | FT(x) < κ}. De novo, pode confimar que H_{κ} ⊧ ZF-P. Nota que H_{ω_{1}} |̸= “Conjuntos de potência” porque, por exemplo, V_{ω+1} = P(V_{ω}) ∉ H_{ω_{1}} (equivalentemente, V_{ω+2} ⊈ H_{ω_{1}}). (Logo ZF|– Con(ZF-P).)

Pode perguntar se tem modelos de outros fragmentos de ZF. Já vimos nos exercícios 11, 13 e 14 do capítulo 1 várias dependencias entre axiomas, e este reduze o número das perguntas interessantes. Todavia, ainda podemos perguntar se existem modelos de ZF\{Fundação}, e mesmo se existem modelos de todo de ZF. Embora na proxima seção mostraramos que não podemos demonstrar que existem tais modelos como uma conseqüência da teorema de incompletude.

6.4. Teorema de incompletude.

A teorema de incompletude, tanto quanto a teorema de completude, é uma teorema geral sobre coleções de frases numa língua da ordem primeira. Aplica para uma variedade ampla de coleções de frases (ou teorias) e não tem nada a ver especificamente com a teoria dos conjuntos (além de, com certeza, ZF sendo um destas coleções. outros).

Teorema de incompletude. (Gödel, 1931) Se T é uma teoria razoável (numa língua L), então T |̸– Con(T).

Nota lingüística. O nome da teorema de incompletude vem do fato que mostra que T é uma teoria incompleto, isso é que não tem a propreidade que ou demonstra ϕ ou demonstra ¬ϕ para todas frases ϕ no L. Na contramão, a teorema de completude tem tal nome porque mostra que dedução na l’ogica da primeira ordem é completo no sentido que se ϕ é verdadeiro no cada modelo do T, então tem um derivação de ϕ do T na lógica da primeira ordem. Então, apesar de soar um pouco estranho talvez, não tem problemas nenhums falar, por exemplo, que a teorema de completude e a teorema de incompletude são verdadeiras para uma teoria T.

Razoável aqui quer dizer que: (a) podemos exprimir Con(T) no L, (b) T é consistente, (c) podemos fazer bastante combinatoria no T para codificar as manipulações de lógica dentro de T e decodificâlos, e (d) T é recursivo – devo explicar que este quer dizer.

Precisamos de (a) porque T só pode demonstra frases no L, logo sem (a) a conclusão da teorema seria incomprehensível. Também precisamos de (b) para esperar mostrar a teorema porque se T não é consistente temos que T |– ⊥, e, então T demonstra qualquer frase. Especificamente, T |– Con(T). Explicamos (c) e (d) mais completamente abaixo, mas esta formulação vaga de (c) jd́á uma pista para como exprimir Con(T) no L.

Exemplos de teorias ‘razoáveis.’ Se são consistentes, a coleção de todos os verdadeiros sobre (N, +, ., s, exp, 0, 1) e a aritmetica de Peano são razoáveis. Se são consistentes, ZF e ZF-I-P-Fundação são razoáveis. Muitas teorias de analyse onde tem a função de sine, e então pode definir os números naturais, são razoável se é consistente.

Explicação de (c) na definição de razoável. Se T é razoável podemos mostrar de T que podemos achar representações de várias coisas síntaticais sobre L e T pelo termos no L: os símbolos do L, os termos no L, os fórmulas no L e as demonstrações do T no L. Se a é um pedaço da sintaxe escrevemos #(a) para o termo que representa a. As vezes chamamos estes termos códigos.

Também, podemos achar um fórmula Dem(x, y) e uma função definivel Subst(x, y) no L tal que d é uma demonstração de ϕ do T se e só se T |– Dem(#(d), #(ϕ)), e ϕ[a/x] = ψ se e só se T |– Subst(#(ϕ), a) = #(ψ).

Primeiro suponhamos que T é razoável neste sentido, e mostramos como demonstrar a teorema. Depois veremos como fazer a codificação para algumas teorias especificas.

Demonstração da teorema de incompletude. Observe que se ϕ(x) é um fórmula temos que T |– “Subst(#(ϕ), #(ϕ)) = #(ψ)” se ψ = ϕ[#(ϕ)/x], isto é, se ψ é o fórmula que ganhamos se substituimos o termo que representa ϕ se mesmo em vez do variável livre x do ϕ. Considere o fórmula ¬∃y Dem(y, Subst(z, z)), = χ(z), vamos falar. Então, para qualquer fórmula ϕ, temos que T |– χ(#(ϕ)) se e só se não existe um demonstração de ϕ(#(ϕ) do T. Logo, porque χ se mesmo é um fórmula, temos que T |– χ(#(χ)) se e só se não existe um demonstração de χ(#(χ) do T.

Mas agora se T |– χ(#(χ)) temos que d demonstra χ(#(χ)) para alguma demonstração d, e então T |– Dem(#(d), #(χ(#(χ))). Logo T |– ∃yDem(y, #(χ(#(χ))). Logo T |– ¬(χ(#(χ))). Então T é inconsistente.

E se T |– ¬(χ(#(χ))) temos que T |– ∃yDem(y, #(χ(#(χ))). Assumindo que T é consistente existe uma demonstração d tal que T |– Dem(#(d), #(χ(#(χ))). Logo T |– χ(#(χ)) e temos que T é inconsistente de novo.

Se escrevemos Con(T) para ¬∃y Dem(#(y), #(z ≠ z)) e se formalizamos a argumentação dentro do T temos que T |– Con(T) ⟶ (χ(#(χ)). Logo T |– Con(T) implica T |– (χ(#(χ)), e então T não é consistente. (Fim da demonstração da teorema.)

T deve ser recursivo porque precisamos ter que “d é uma demonstração de ϕ de T ” e “ϕ[a/x] = ψ” são recursivos, e então temos que existem fórmulas no L que definem Dem e Subst, e porque para fazer a formalização também precisamos saber que para asserções sobre demonstrações e substituções podemos usar os fórmulas no L para escrever frases equivalentes no L.

Codificação.

Ainda ser feitos sobre minha explicação da teorema de incompletude:

• Falar exactamente qual manipulações precisamos ter o poder fazer no (c).

• Explicar como fazer a formalização de argumentação dentro do T (em cima so falo que “pode”).

• Explicar porque faço tudo essa codificação recursivamente/Explicar mas exactamente porque precisamos que T é recursivo.

• Dar referências. (G.Takeuti, Proof Theory, North Holland, 1969, pp. 73-81.)

Seja L = {f^{i} | i < ω } ∪ {R^{i} | i < ω } ∪ {=}. Porque fórmulas são fios finitos dos símbolos e demonstrações são arvores finitos dos fórmulas precisaramos que T dá para nós o poder manipular fios de codigos para símbolos e codigos para fios dos símbolos. Então uma parte da definição de “razoável” é que podemos definir funções f_{n} para cada n < ω e π_{m}^{n} para cada m < n < ω no L tal que podmemos mostrar do T que π_{m}^{n}(f_{n}(x_{0}, …, x_{n−1})) = x_{m}. Então f_{n} funciona como se ele permite nós fazer “n-tuplos” e π_{m}^{n} funciona como se ele permite nós recobrir o m^{o} elemente dum “n-tuplo” para cada n < ω e m < n. Para evitar confusão é bom pedir que rge(f_{n}) ∩ rge(f_{m}) = ∅ se m ≠ n. Preciso disso nesta presentação ou não?

Definimos #(t), #(ϕ) para termos t e fórmulas ϕ ∈ L pela indução na estrutura do t, ϕ.

Então sejam ⟨t_{i} | i < ω ⟩ termos na língua L. Sejam #(&) = t_{1}, #(¬) = t_{3}, #(∃) = t_{5}, #(() = t_{7}, #()) = t_{9}, #(,) = t_{11} #(=) = t_{13}, #(v_{i}) = t_{2i}, #(f^{i}) = t_{4i+15}, e #(R^{i}) = t_{4i+17} para i < ω.

Já vimos que #(v_{i}) = t_{2i}. Se i < ω, f^{i} é um símbolo para uma função k-ária e s_{0},…, s_{k−1} são termos no L, temos que #(f^{i}(v_{j_{0}}, …, v_{j_{k−1}})) = f_{k+3}(t_{4i+15}, t_{7}, #(s_{2j_{0}}), …, #(s_{2j_{k−1}}), t_{9}).

Se i < ω, R^{i} é um símbolo para uma relção k-ária e s_{0}, …, s_{k−1} são termos no L temos que #(R^{i}(v_{j_{0}}, …, v_{j_{k−1}})) = f_{k+3}(t_{4i+17}, t_{7}, #(s_{2j_{0}}), …, #(s_{2j_{k−1}}), t_{9}). Se ϕ é um fórmula temos que #(¬ϕ) = f_{4}(t_{3}, t_{7}, #(ϕ), t_{9}). Se ϕ e ψ são fórmulas temos que #(ϕ & ψ) = f_{3}(#(ϕ), t_{1}, #(ψ)). E se ϕ(x) é um fórmula com x um variável livre, temos que #(∃xϕ(x)) = f_{2}(t_{5}, #(ϕ(x))).

Então para um fórmula ϕ ∈ L temos #(ϕ) é um termo de L. Se d é uma demonstração de ϕ do T, então d é um arvore finito, então um fio dos fios, então podemos definir #(d), um termo no L também. Hmmm. Nunca expliquei que são arvores (finitos), nem dei as ilustrações para derivação para mostrar que demonstrações são arvores.

Exemplos. No ZF(−I−P−Fnd) podemos simplesmente usar f_{n}(x_{0}, …, x_{n−1}) = (x_{0}, …, x_{n−1}) e t_{i} = i para i < ω, porque se x_{0},…, x_{n−1} ∈ V_{ω} temos que (x_{0}, …, x_{n−1}) ∈ V_{ω} também.

No aritmética de Peano temos que fazer um pouco mais. f_{n}(x_{0}, …, x_{n−1}) = . . .. Deveria acabar com este parte da demonstração.

6.5. Aplições da teorema de incompletude para ZF.

Teorema. Se ZF é consistente não podemos demonstrar, apenas do ZF, que existe um modelo de ZF.

Demonstração. É fácil ver que ZF é “razoável” porque podemos fazer as manipulações dos fios finitos no ZF e os axiomas do ZF são um conjunto recursivo. Então a teorema é imediata da teorema de incompletude. (Hmmm. Deveria explicar como os axiomas são um conjunto e, então podem ser recursivos ou não.)

Teorema. ZF|– Con(ZF−{Fundação}) ⟶ Con(ZF).

Demonstração. Seja U um modelo de ZF−{Fundação}. Podemos construir a hierarquia dos V_{α}s sem usando fundação – lembrar que vimos depois a construção da hierarquia dos V_{α}s na §2.7 que o axioma de fundação é equivalente para falar que ∀x ∃α ∈ On x ∈ V_{α}. Então, construir a hierarquia dentro do U e seja V o resultado. Usando o fato, que pode confirmir simplesmente pela indução na estrutura de fórmulas, que se x ∈ V e ϕ(y) é um fórmula, então x∩{y | ϕ(y)}∩V = x∩{y | ϕ^{V} (y)}∩U, onde ϕ^{V} (y) é ϕ com todos os quantificadores correndo sobre V, podemos confirmar que V ⊧ ZF. Então Con(ZF−{Fundação}) implica Con(ZF). Logo ZF|– Con(ZF−{Fundação}) ⟶ Con(ZF).

Corolário. Não podemos mostrar do ZF que existe um modelo do ZF−{Fundação}.

Demonstração. Imediato da teorema e da teorema de incompletude.

6.6. Construtabilidade e forçando. Agora podemos explicar mais exatamente o que quer dizer as observações no fim de §4.3, por exemplo, que não pode mostrar do ZF que AE é verdadeiro nem que não é verdadeiro.

Teorema. (Gödel, 1938) Con(ZF) ⟹ Con(ZF + AE + HCG).

Teorema. (Cohen, 1963) Con(ZF) ⟹ Con(ZF + ¬AE), e Con(ZF) ⟹ Con(ZF + AE + 2^{ℵ_{0}} = ℵ_{α+1}) para qualquer ordinal α.

Mas exprimindo coisas neste modo, como sobre consistência, talvez não dá uma impressão certa do material da teoria dos conjuntos em geral e destas teoremas especificamente. É melhor entender estas teoremas no mesmo modo que as demonstrações delas: como falandas que se temos um modelo em qual tal e tal coisas são verdadeiras, então podemos mudar para um outro modelo onde tal e tal outras coisas são verdadeiras. Isso é um exemplo de uma tema central na teoria dos conjuntos, porque a teoria se interesse, após das coisas inicias nos capítulos 1-4, nas relações entre modelos da teoria (do ZF) e nas coisas quem acontecem dentro coleções especificos dos modelos do ZF. (Embora, claro, inclusive se interesse nas propriedades de modelos especificos (coleções do tamanho um) e da coleção de todos modelos (as conseqüências síntaticas do ZF, pela a teorema do completude).) Este não deveria ser uma surpresa grande: a teoria dos grupos se interesse nas relacões entre grupos também com propriedades de coleções dos grupos, e a teoria dos espaços topologicos se interesse nas relações entre espaços também com propriedades de (coleções dos) espaços. Só tem que lembrar que nestes exemplos últimos os modelos das teorias são grupos e espaços respectivamente, enquanto no caso da teoria dos conjuntos os modelos não são chamados ‘conjuntos’ mas ‘modelos da teoria dos conjuntos,’ ou, como falamos na seção §1.4, ‘universos’ (modelos são universos porque se M ⊧ ZF temos que M ⊧ ∀x ∃α ∈ On^{M} x ∈ V_{α}^{M}).

Construtabilidade. A idéia inicial da demonstração da teorema de Gödel é parecida para a idéia da demonstraçao que damos no fim de §6.5 que se temos um modelo de ZF−Fundação podemos chegar num modelo de ZF. Este vez, começamos com qualquer modelo M de ZF e definimos dentro de M um modelo mas magro, L, com L ⊆ M e, neste caso, com do ZF + AE + HCG, On^{L} = On^{M}. Fazemos isso pelo definindo L como um hierarquia, como V, mas nas niveis do tipo sucessor augmentando a coleção até este nivel só com subconjuntos definíveis dele em vez de todos os subconjuntos.

Definição. Pela recursão sobre On^{M} define L_{0} = ∅, L_{λ} = ⋃{L_{α} | α < λ} para ordinais λ do tipo limite, e L_{α+1} = {x ⊆ L_{α} | ∃ϕ(y_{0}, …, y_{n−1}, z) ∈ LST tal que x = {a | ∃b_{0}, …, b_{n−1} ∈ L_{α} (L_{α}, ∈ ∩(L_{α} × L_{α})) ⊧ ϕ(b_{0}, …, b_{n−1}, a)}}. Seja L = ⋃{L_{α} | α ∈ On^{M} }.

A teorema de Gödel é, na verdade, que para qualquer M temos que L ⊧ ZF + AE + HCG. E além disso que se M, N são modelos de ZF com On^{M} ⊆ On^{N}, temos que L_{On^{M}}^{N} = L^{M}, então, especificamente, L ⊧ V = L. Mas a demonstração que o modelo L tem estas propriedades é mais súbtil. Para ver mais sobre isso veja capítulo 7.

Forçando. Para mostrar que podemos mudar dum modelo de ZF + AE + HCG para um modelo do ZF + AE em qual, por exemplo, HC fale usamos uma técnica, forçando, para expandir o modelo para chegar, neste caso, num modelo com mais subconjuntos de ω. A técnica é muito parecida para fazer uma extensão álgebraica para um campo na álgebra: fazemos um extensão formal pelo um não-conhecido, e depois tomamos um quociente. (No fato, pode mostrar que isso não é só uma analogia boa, mas tem um sentido técnico em qual forçando e fazendo extensões álgebraicas são instâncias da mesma construção categorica.)

Os livros de Kunen^{1} e Kanamor^{2} são do dois lugares ótimos para pegar mais informação sobre forçando, e sobre as proximas pasos na teoria dos conjuntos mais geralmente. Talvez um cápitulo 8 destes notas também.

6.7. Modelos de todo do ZF.

Notar que a conseqüência da teorema de incompletude no §6.5 não fala que não existem modelos de ZF, só que não pode mostrar dos axiomas de ZF sozinhos que existem modelos. Já vimos no §6.3 que V_{λ} ⊧ ZF − {Coleção} para qualquer ordinal λ do tipo limite com ω < λ e que V_{ω} ⊧ ZF − {Infinidade}. Pode confirmir pelas mesmas demonstrações juntos a seguinte.

Teorema. Se κ é um cardinal que é inacessível fortemente, temos V_{κ} ⊧ ZF.

Observação. (Paradoxo de Skolem). Se ZF é consistente pelo corolário ultimo na §6.2 ele tem um modelo, falamos M, enumerável. Logo P(ω)^{M}, ω_{1}^{M}, … são enumeráveis. Isso não é um paradoxo na verdade porque apesar de podemos contar, por exemplo, P(ω)^{M} fora do modelo e ver que este conjunto, que é um conjunto de subconjuntos do ω é enumerável, (para “pessoas”“morando”) dentro M não tem qualquer bijeção do ω para P(ω)^{M}, e, logo, dentro do M não pode enumerar P(ω).

Não obstante que, pela teorema de incompletude aplicada para a teoria ZF, não pode mostrar dos axiomas de ZF que existem cardinais que são inacessíveis fortementes, a afirmação que existem tais cardinais é uma afirmação interessante e as vezes útil sobre (modelos de) ZF. Embora que formalmente isso e suposições similares são fortelecendos do ZF, na prática – o punto o mais importante – não parece qualquer razão supor que são diferentes de, por exemplo, fortelecendo a teoria da aritmética de Peano com a suposição que esta teoria não é inconsistente. No contrário, na verdade, a exploração das suposições deste tipo forma uma parte muito produtiva da teoria dos conjuntos e, logo, da matemática. (Veja, particularmente, o livro de Kanamori.) Acabamos este capítulo com um exemplo deste fenômeno sobre exponenciação dos cardinais.

Definição. Para qualquer δ < ω_{1}, a declaração que um cardinal κ é κ+δ+1-forte é um fortelecendo de falar que κ é inacessível fortemente e que κ é compacto fracamente. (Quer dizer que existe um injeção i : V ⟶ M tal que M ⊆ V, On^{M} = On^{V}, se ϕ(x) ∈ LTC e a ∈ V temos que V ⊧ ϕ(a) se é so se M ⊧ ϕ(i(a)), i(α) = α para cada α < κ, κ < i(κ) e V_{κ+δ+1} ⊆ M. Não deveria esperar entender agora porque este definição é mais ou menos natural, nem mesmo como formulá-la como uma suposição sobre conjuntos e não sobre classes como fizemos aqui. Veja o livro do Kanamori para estes detalhes.)

A razão para introduzuir a definição aqui é que podemos usá-la para dar a declaraç certa da teorema seguinte annunciada no fim da seção §4.4 – do qual a demonstração é uma raciocinação esperto que usa forçando.

Teorema. (Gitik-Magidor, 1989) Seja ω ≤ δ < ω_{1}. Con(ZF + AE + ∃κ tal que κ é κ + δ + 1-forte) ⟹ Con(ZF + AE + 2^{ℵ_{n}} = ℵ_{n+1} para todos n < ω, e 2^{ℵ_{ω}} = ℵ_{δ+1}.)

1 Ken Kunen, Set theory: an introduction to independence proofs, North-Holland, 1980. Não é ainda impresso, mas

pode consultar uma cópia na biblioteca.

2 Aki Kanamori, The Higher Infinite, Springer, 1996.

Bibliografia:

Need to rewrite this completely.

Infelizmente é difícil recomendar quaisquer livros em português para vocês. Há traduções dos livros de Halmos e Lifshutz. O de Halmos, enquanto na época (no inicio dos anos 60) não foi tão ruim, agora é muito antiquado. O de Lifshutz não serve.

Em inglês tem mais possibilidades. Entre elas eu aconselharia:

Keith Devlin, Fundamentals of Contemporary Set Theory, (Springer, 1979). (Acho muito bom sobre ordinais e cardinais, mas não tão bom, talvez, na parte da introdução dos axiomas.) Herb Enderton, Elements of Set Theory, (Academic, 1977). (Bom, claro, mas talvez não muito vivaz.) Andras Hajnal e Peter Hamburger, Set Theory. (Cambridge University Press, LMS Lecture Notes Series, vol. 48, 1999). (Claro e também interessante.) Judy Roitman, Introduction to Modern Set Theory. (Wiley, 1990) (Também uma boa escolha.)

Tenho uma fotocópia do livro de Devlin que vocês podem usar e uma cópia, que botarei na biblioteca, do livro de Hamburger e Hajnal deverá chegar logo – espero no fim de semana.

Tem na biblioteca, também, uma ótima introducão para lógica matemática–para mim a melhor,

Dirk van Dalen, Logic and Structure, (Springer, 4^{o} ed. 1996?). (Ótimo. Muito interessante em se mesmo, e boa para clarificar as coisas em (5) em cima sobre quais só teremos tempo de tocar levemente.)

Kunen, Kanamori, Kechris,…