Teoria Axiomatica de Conjuntos:

Uma Introducao

Marcelo Esteban ConiglioGTAL, Departmento de Filosofia

Universidade Estadual de CampinasP.O. Box 6133, 13081-970

Campinas, SP, BrazilE-mail: coniglio@cle.unicamp.br

Abstract

O presente texto corresponde as notas de aula do curso HF005-Teoriade Conjuntos, do Programa de Pos-Graduacao em Filosofia da UNICAMP,que ministrei no segundo semestre de 1997. Trata-se principalmente deuma adaptacao do livro Axiomatic Set Theory, de P. Suppes (Dover, 1972).Alguns topicos (principalmente, teoria de ordinais e de cardinais) foramadaptados do livro Set Theory: an Introduction to Large Cardinals, deF.R. Drake (North Holland, 1974).

Contents

Introducao 3

1 Teoria Cumulativa de Tipos 4

2 Axiomas Basicos da Teoria de Conjuntos 5

3 Axiomas Adicionais 9

4 Produtos Cartesianos 13

5 Relacoes em S 16

6 Relacoes de Ordem 19

7 Relacoes de Equivalencia 24

8 Funcoes 29

9 Equipolencia 33

10 Conjuntos Finitos 40

11 Axiomas Finais de ZF . O Axioma da Escolha 46

1

12 Introducao aos Ordinais 49

13 Inducao e Recursao Transfinita 54

14 Aritmetica Ordinal 62

15 Cardinais 73

2

Introducao

A Teoria de Conjuntos (TC) ocupa um lugar privilegiado dentre as disciplinasda Matematica moderna: todas as entidades estudadas na matematica (comalgumas excecoes) podem ser consideradas conjuntos. Portanto, as questoesacerca da natureza da matematica sao basicamente questoes acerca de conjun-tos.

A TC foi iniciada a partir das pesquisas de Georg Cantor em 1870 sobrea teoria das series infinitas em Analise; a partir destes trabalhos, Cantor foilevado a considerar conjuntos infinitos ou classes de carater arbitrario. Maso que sao os conjuntos? A nossa ideia intuitiva os define como colecoes deobjetos. Segundo Cantor, “um conjunto e uma colecao, considerada como umtodo, de objetos distintos e definidos da nossa intuicao ou pensamento. Osobjetos sao chamados de elementos do conjunto”. Os paradoxos surgidos logono inıcio do estudo da teoria mostraram que a concepcao “ingenua” de Cantornao podia formar uma base satisfatoria para a TC, e muito menos para aMatematica. Isto levou a uma reformulacao dos princıpios basicos da teoria.Os paradoxos apareceram principalmente pelo uso indiscriminado das nocoes deconjunto, numero cardinal e ordinal, etc. Um paradoxo consiste na derivacao nosistema logico de ϕ e ¬ϕ para alguma afirmacao ϕ, ou entao a derivacao de umaafirmacao da forma ϕ↔ ¬ϕ. O primeiro paradoxo foi descoberto pelo proprioCantor em 1895 e nao foi publicado imediatamente, mas foi redescoberto porBurali-Forti em 1897, que tambem nao conseguiu fornecer uma solucao. Oparadoxo surgiu com relacao a teoria dos ordinais, num estagio relativamenteavancado da teoria, e nao foi levado muito a serio. A aparicao em 1902 do celebreparadoxo de Russell fez mudar as coisas, pois ele surge no primeiro estagio dateoria: dado que, pelo axioma de compreensao, podemos definir os conjuntos{x : ϕ(x)}, onde ϕ(x) e uma formula denotando uma propriedade, entao elıcito formular o conjunto A = {x : x 6∈ x} (considerando ϕ(x) ≡def x 6∈ x).Logo, podemos nos perguntar se e o caso que A ∈ A ou nao e o caso que A ∈ A,obtendo: A ∈ A sse A 6∈ A!! Este fato causou uma verdadeira revolucao nomeio academico ligado a fundamentacao da matematica, obrigando Dedekind asuspender a publicacao do seu ensaio sobre a natureza dos numeros. Enquantoisso, Frege acabara de publicar sua obra prima, fruto de decadas de esforcos,admitindo por fim que um dos pilares do seu edifıcio tinha sido sacudido porRussell.

Os paradoxos tem uma origem antiga: o exemplo classico e o Paradoxo doMentiroso (Epimenides), que pode ser formulado simplesmente como: “Estafrase e falsa”. E claro que supor a verdade ou a falsidade da frase leva a umacontradicao. O paradoxo de Grelling-Nelson (1908) diz o seguinte: defina comoheterologicos os adjetivos tais que eles mesmos nao satisfazem a propriedadeque eles denotam. Por exemplo, “ingles”, “azul” ou “frio” sao heterologicos,enquanto que “polissilabico” ou “portugues” nao o sao; em sımbolos, dadoum adjetivo “S”, temos que “S” e heterologico sse “S” nao e (nao satisfaz) S.Logo, “heterologico” e heterologico sse “heterologico” nao e heterologico. Oparadoxo de Richard (1905) diz o seguinte: considere os numeros reais entre 0e 1 que podem ser definidos por um numero finito (nao limitado) de palavras

3

em portugues: por exemplo, “ponto cinco”, “o maior numero tal que elevadoao quadrado e multiplicado por tres e igual a dois”. Os numeros definidos destamaneira podem ser enumerados (so temos uma quantidade enumeravel de frasesde tamanho finito). Considere o seguinte numero: “o numero real entre 0 e 1cuja n-esima casa decimal e tres se a n-esima casa decimal do n-esimo numero ecinco, e e cinco em caso contrario”. Logo, esta frase define um numero diferentede todos os numeros da lista, uma contradicao (este paradoxo e baseado nometodo diagonal de Cantor para provar que o conjunto dos numeros reais naoe enumeravel). Ramsey distingue dois tipos de paradoxos: os semanticos eos logicos. Todos os paradoxos mencionados acima (com excecao do paradoxode Russell) sao semanticos; dentre os paradoxos logicos podemos mencionar oparadoxo de Russell, o de Cantor e o de Burali-Forti. O paradoxo de Cantor(1899) diz: considere U o conjunto de todos os conjuntos. Logo, o conjuntoP(U) das partes de U tem cardinal estritamente maior do que o cardinal deU , o que contradiz a hipotese de que U seja o maior conjunto. O paradoxo deBurali-Forti (1897) diz: o conjunto bem ordenado W de todos os ordinais temum ordinal maior que todo elemento de W , portanto maior que todo ordinal.

1 Teoria Cumulativa de Tipos

Todos os paradoxos vistos tem a mesma origem: a auto-referencia. No caso dosparadoxos em TC, podemos solucionar o problema considerando que os conjun-tos sao formados em etapas ou estagios; assim, um conjunto so pode ser criadoa partir de conjuntos que ja foram definidos ou criados anteriormente. Isto daorigem a teoria simples de tipos:

Nıvel 0: alguns indivıduos (urelemente), sem propriedades especıficas.Nıvel 1: todas as colecoes formadas por indivıduos.Nıvel 2: todas as colecoes formadas por elementos no nıvel 1, etc.

Assim, se os indivıduos sao os numeros naturais, entao 3 e um conjunto nonıvel 0, {1, 2} esta no nıvel 1, e {{2}, {4, 6}} esta no nıvel 2. As questoes sao:(a) qual e o problema em considerar {1, {1}} como conjunto? (b) o conjuntovazio ∅, assumindo que seja um indivıduo, seria diferente nas diferentes etapasem que pudesse aparecer? Com relacao a (a), e obvio que o modelo e restritivodemais, logo consideramos a teoria cumulativa de tipos:

Nıvel 0: alguns indivıduos.Nıvel 1: todas as colecoes formadas por indivıduos.Nıvel 2: todas as colecoes formadas por elementos no nıvel 0 ou 1.Em cada nıvel, considerar as colecoes cujos elementos estao em nıveisanteriores.

Logo, {1, {1}} aparece no nıvel 2, no nosso exemplo. Com relacao a (b), temosque assumir que uma vez que um conjunto aparece num nıvel, toda aparicaoposterior e a mesma. As questoes seguintes sao: quantos indivıduos deveriam

4

ser tomados? os nıveis tem final? Com relacao a primeira questao, parececlaro que ∅ deveria ser considerado o unico indivıduo; isto equivale a nao tomarindivıduos (logo, ∅ sera o unico conjunto do nıvel 1). Com relacao a segundaquestao, a resposta e “nao”. Se existisse um maximo nıvel α, e claro quepoderiamos criar um nıvel adicional α+1 com os conjuntos que temos definidos,uma contradicao.

2 Axiomas Basicos da Teoria de Conjuntos

A primeira axiomatizacao de TC foi dada por Zermelo em 1908, e modificadapor Fraenkel em 1922, dando origem ao sistema Zermelo-Fraenkel (ZF ). Ex-istem muitos outros sistemas, como o de von Neumann-Godel-Bernays (NGB)e o de Kelley-Morse (KM). Estes ultimos usam classes juntamente com con-juntos. Uma classe pode ser pensada como uma colecao “enorme”, de maneiraque os conjuntos viriam ser classes “pequenas”. Por exemplo,

V = {x : x = x}

e a colecao de todos os conjuntos, chamada de classe universal. V e umaclasse propria, isto e, ela nao e um conjunto, portanto nao aparece em nenhumnıvel da hierarquia cumulativa. Se todos os membros de uma classe aparecemantes de um dado nıvel, entao a classe e um conjunto nesse nıvel. Neste cursoestudaremos apenas ZF .

A formulacoes ZF de TC e realizada numa linguagem de primeira ordem,utilizando constantes para os (eventuais) indivıduos, duas relacoes binarias (=,∈), os conectivos ∨, ∧, ¬, → , ↔ , e os quantificadores ∀ (para todo) e ∃(existe), junto com um repertorio enumeravel de variaveis. As variaveis saodenotadas: a, b, . . . , x, y, z (com ou sem ındices). Como e usual, as formulas¬(x = y) e ¬(x ∈ y) serao denotadas por (x 6= y) e (x 6∈ y), respectivamente.

Comecamos enunciando o primeiro axioma de ZF :

Axioma de Extensionalidade:

[A1] (∀z)(z ∈ x↔ z ∈ y) → (x = y)

Aqui e evidenciada a intencao de que, quando uma colecao aparecer em dife-rentes nıveis, ela seja considerada como sendo a mesma; por outro lado, eestabelecido que o que interessa com relacao aos conjuntos sao os seus e-lementos, mais do que o que eles sao. Observe que a implicacao recıproca(x = y) → (∀z)(z ∈ x↔ z ∈ y) e logicamente valida.

Axioma de Compreensao ou Separacao:

[A2] (∃y)(∀x)(x ∈ y↔ (x ∈ a ∧ ϕ(x)))

Isto significa que estamos “separando” alguns elementos de a, exatamente aque-les que satisfazem a propriedade ϕ. Aqui, ϕ(x) e uma formula onde x aparece

5

livre, podendo aparecer outras variaveis livres em ϕ (os parametros do con-junto criado), mas a variavel y nao aparece livre em ϕ. O axioma decompreeensao tenta tomar, em cada estagio, todos os conjuntos ja criados,para formar os conjuntos do nıvel seguinte. O axioma e limitado, pois sotomamos os conjuntos formados pelas formulas ϕ. Observe que [A2] e umaxioma-esquema, isto e, cada formula ϕ determina um axioma. A condicaosobre y nao ocorrer livre em ϕ esta relacionada com a auto-referencia, e e fun-damental para evitar o paradoxo de Russell; caso contrario, podemos considerar(∃a)(∀x)(x ∈ a↔ x = b) (esta formula e demonstravel em ZF , como veremosdepois de incorporar outros axiomas) e ϕ(x, y) ≡def x 6∈ y em [A2]; logo, te-remos: x ∈ y↔ (x ∈ a ∧ x 6∈ y), e entao x ∈ a→ (x ∈ y↔ x 6∈ y) para todox. Portanto, tomando a como acima, teremos: x = b→ (x ∈ y↔ x 6∈ y) paratodo x, donde, tomando b no lugar de x, obtemos b ∈ y↔ b 6∈ y, contradicao.Como provaremos na Proposicao 11.1, o axioma [A2] sera dedutıvel dos outrosaxiomas de ZF (especificamente, [A2] e um caso particular do axioma [A7], aser introduzido na Secao 11). Porem, na primeira parte deste texto faremos umuso pesado do axioma [A2] sem precisar usar por enquanto o axioma mais forte[A7].

A partir de agora adotaremos a seguinte notacao: {x : ϕ} e um (meta)termos em que toda ocorrencia de x e limitada (ϕ e uma formula). Logo,

s = t denota (∃z)((∀x)(x ∈ z ↔ ϕ) ∧ z = t);t = s denota (∃z)((∀x)(x ∈ z ↔ ϕ) ∧ t = z);s ∈ t denota (∃z)((∀x)(x ∈ z ↔ ϕ) ∧ z ∈ t);t ∈ s denota (∃z)((∀x)(x ∈ z ↔ ϕ) ∧ t ∈ z)

onde z nao ocorre em ϕ nem em t.Assim, por exemplo, se s ≡def {x : ϕ(x)} e t ≡def {x : φ(x)} entao s ∈ t

denota a formula (∃z)((∀x)(x ∈ z ↔ ϕ) ∧ z ∈ t). Por sua vez, z ∈ t denota aformula (∃u)((∀x)(x ∈ u↔ φ) ∧ z ∈ u), portanto s ∈ t denota a formula

(∃z)((∀x)(x ∈ z ↔ ϕ) ∧ (∃u)((∀x)(x ∈ u↔ φ) ∧ z ∈ u)).

Se (∃y)(∀x)(x ∈ y↔ ϕ(x)) e demonstrado a partir dos axiomas, dizemos que{x : ϕ(x)} e legitimado. Logo, o axioma de separacao diz que o (meta)termo

{x : x ∈ a ∧ ϕ(x)}

e legitimado. Note que este (meta)termo depende de a (e das variaveis diferentesde x que ocorrem livres em ϕ(x)).

Observacao 2.1 Se si ≡def {x : ϕi(x)} e legitimado (i = 1, . . . , n), entao(∀x1) · · · (∀xn)φ(x1, . . . , xn) implica φ(s1, . . . , sn), onde φ(s1, . . . , sn) e a ex-pressao obtida de φ substituindo xi por si (eliminando a posteriori os si apli-cando as regras de reducao definidas acima). Portanto, se s ≡def {x : ϕ(x)} elegitimado, entao de x ∈ y↔ φ(x) deduzimos s ∈ y↔ (∃z)((∀x)(x ∈ z ↔ ϕ(x))∧φ(z)) e s ∈ y↔ φ(s) (lembrando que devemos eliminar s para obter formulas apartir dessas expresoes). �

6

Proposicao 2.2 Suponha que s ≡def {x : ϕ(x)} e legitimado; logo, sao demon-straveis:

x ∈ s↔ ϕ(x), (s = y) ↔ (∀x)(x ∈ s↔ x ∈ y) e(s = y) ↔ (∀x)(x ∈ y↔ ϕ(x)).

Demonstracao: Sejam α ≡def (∃y)(∀x)(x ∈ y↔ ϕ(x)) e β ≡def (∃y)((∀z)(z ∈y↔ ϕ(z))∧x ∈ y), isto e, β e x ∈ {x : ϕ(x)}; logo, α∧β implica β implica ϕ(x).Por outro lado, ϕ(x)∧(x ∈ y↔ ϕ(x)) implica x ∈ y, e entao ϕ(x)∧α implica β.Para provar a segunda equivalencia, considere φ(z, y) ≡def (z = y) ↔ (∀x)(x ∈z ↔ x ∈ y). Por [A1] vale (∀z)φ(z, y) e entao, pela Observacao 2.1 obtemosφ(s, y), i.e., (s = y) ↔ (∀x)(x ∈ s↔ x ∈ y). A ultima afirmacao e uma con-sequencia das duas primeiras. �

Desta maneira, se s ≡def {x : ϕ(x)} e t ≡def {x : φ(x)} sao legitimados,entao, para provar (s = t), basta provar ϕ(x) ↔ φ(x).

Axioma do Conjunto Vazio:

[VZ] (∃y)(∀x)(x 6∈ y)

Este axioma e redundante, pois pode ser deduzido de [A2]: considere ϕ(x) ≡def(x 6= x); como (x ∈ y↔ (x ∈ a ∧ x 6= x)) ∼ (x 6∈ y↔ (x 6∈ a ∨ x = x)) ∼ (x 6∈y↔ (x = x)) ∼ x 6∈ y, entao o axioma [VZ] se segue por [A2]. Assim, o termo{x : x 6= x}, que sera denotado ∅, e legitimado em ZF . Note que (s = ∅) sse(∀x)¬ϕ(x), se s ≡def {x : ϕ(x)}.

Corolario 2.3 [A1], [A2] ` x 6∈ ∅.

Demonstracao: Pela Proposicao 2.2,

` (∃y)(∀x)(x ∈ y↔ x 6= x) → (x ∈ ∅ ↔ x 6= x)

(note que o antecedente desta implicacao expressa que ∅ ≡def {x : x 6= x} elegitimado). Logo, [V Z] ` (x ∈ ∅ ↔ x 6= x), donde [A1], [A2] ` x 6∈ ∅. �

Axioma do Par:

[PR] (∃y)(∀x)(x ∈ y↔ ((x = a) ∨ (x = b)))

Este axioma afirma que existe o conjunto com a e b como unicos membros,legitimando o termo {x : (x = a) ∨ (x = b)}, que sera denotado {a, b} (noteque o nome do termo depende de a e b). Em funcao da hierarquia cumulativa,o par {a, b} pode ser formado em qualquer estagio depois que a e b foramformados; logo, nao tem ultimo estagio. O conjunto {a, a} sera denotado {a},sendo que contem a como unico elemento. Este axioma e redundante, comoprovaremos depois na Proposicao 11.2. O axioma [PR] permitira formar, juntocom o axioma [RF] da reuniao finita a ser introduzido a seguir, os conjuntosfinitos da forma {a1, . . . , an}.

7

Corolario 2.4 (a) [A1], [A2], [PR] ` x ∈ {a, b} ↔ (x = a) ∨ (x = b).(b) [A1], [A2], [PR] ` x ∈ {a} ↔ x = a.

Adotemos a notacao x ⊆ y e x ⊂ y para indicar as formulas

(∀z)(z ∈ x→ z ∈ y) e (x ⊆ y) ∧ (x 6= y),

respectivamente. E claro que s ⊆ t↔ (∀x)(ϕ(x) → φ(x)) se s ≡def {x : ϕ(x)}e t ≡def {x : φ(x)} sao legitimados.

Axioma da Reuniao Finita:

[RF] (∃y)(∀x)(x ∈ y↔ (x ∈ a ∨ x ∈ b))

Aqui estabelecemos que a ∪ b ≡def {x : (x ∈ a) ∨ (x ∈ b)} e legitimado. Esteaxioma sera redundante na presenca dos outros axiomas, como provaremos naProposicao 3.2. Por outro lado, a∩ b ≡def {x : (x ∈ a)∧ (x ∈ b)} e legitimado,por [A2]. Logo, podemos provar o seguinte:

Proposicao 2.5 (a ∪ b) ∩ c = (a ∩ c) ∪ (b ∩ c), e (a ∩ b) ∪ c = (a ∪ c) ∩ (b ∪ c).

Demonstracao: x ∈ (a∪b)∩c sse x ∈ (a∪b)∧x ∈ c sse (x ∈ a∨x ∈ b)∧x ∈ csse (x ∈ a∧x ∈ c)∨(x ∈ b∧x ∈ c) see (x ∈ a∩c)∨(x ∈ b∩c) sse x ∈ (a∩c)∪(b∩c).A outra afirmacao e provada analogamente. �

Por [A2], a− b ≡def {x : (x ∈ a) ∧ (x 6∈ b)} e legitimado.

Proposicao 2.6 a− (a ∩ b) = a− b.

Demonstracao: x ∈ a−(a∩b) sse x ∈ a∧x 6∈ (a∩b) sse x ∈ a∧¬(x ∈ a∧x ∈ b)see x ∈ a∧ (x 6∈ a∨x 6∈ b) sse (x ∈ a∧x 6∈ a)∨ (x ∈ a∧x 6∈ b) see x ∈ a∧x 6∈ bsee x ∈ a− b. �

Exercıcios 2.7 Provar na TC obtida ate agora o seguinte:(1) x ⊆ x; (x ⊆ y ∧ y ⊆ x) → (x = y); (x ⊆ y ∧ y ⊆ z) → (x ⊆ z).(2) ∅ ⊆ x; (x ⊆ ∅) → (x = ∅).(3) ¬(x ⊂ x); (x ⊂ y) → ¬(y ⊂ x).(4) a ∩ b e a− b sao legitimados.(5) a∩b = b∩a; (a∩b)∩c = a∩(b∩c); a∩∅ = ∅; a∩b ⊆ a; (a ⊆ b) ↔ (a∩b = a).(6) (a ⊆ b) ↔ (a ∪ b = b); a ∪ ∅ = a; a ⊆ a ∪ b.(7) a ∩ (a − b) = a − b; (a − b) ∪ b = a ∪ b; (a ∪ b) − b = a − b; a − (b ∪ c) =(a− b) ∩ (a− c); a− (b ∩ c) = (a− b) ∪ (a− c); (a ⊆ b) → (a− b = ∅).(8) Obter o paradoxo de Russell a partir de (∃y)(∀x)(x ∈ y).(9) Opinar sobre a verdade ou falsidade das seguintes afirmacoes:

(9.1) O termo {x : x = x} nao pode ser legitimado.(9.2) ϕ(x) → x ∈ {x : ϕ(x)}.(9.3) {x : x ∈ y} = y.(9.4) (∀x)(ϕ(x) → φ(x)) → ({x : ϕ(x)} ⊆ {x : φ(x)}).(9.5) (∀x)(ϕ(x) ↔ ¬φ(x)) → ({x : ϕ(x)} = {x : φ(x)}).

8

(10) Sejam s ≡def {x : ϕ(x)} e t ≡def {x : φ(x)} legitimados. Entaos ∈ t↔ (∃w)((∀x)(x ∈ w↔ ϕ(x)) ∧ φ(w)).

(11) x ∈ a↔ {x} ⊆ a.

Observacao 2.8 A partir das expressoes obtidas na Proposicao 2.2 e no E-xercıcio 2.7 (10), vemos que podemos iterar os termos {x : ϕ}, uma vez queeles sao legitimados. Assim, se os (meta)termos

si ≡def {x : φi(x)} (i = 1, . . . , n) e {x : ϕ(x, x1, . . . , xn, z1, . . . , zk)}

sao legitimados entao, usando a Proposicao 2.2, {x : ϕ(x, z1, . . . , zk)} e legi-timado, onde ϕ e obtida de ϕ substituindo xi por si e , a posteriori, (w ∈ si),(si ∈ w), (si = w), (si ∈ sj) e (si = sj) pela expressao correspondente (we uma variavel que ocorre livre ou limitada em ϕ). Por exemplo, os termosa∪b ≡def {x : x ∈ a∨x ∈ b} e s ≡def {a} ≡ {x : x = a} sao legitimados, logo{a} ∪ b e legitimado, obtido como {x : x ∈ s∨ x ∈ b} ≡ {x : x = a∨ x ∈ b}.Se, por outro lado, queremos formar {s1} ∪ s2, onde si ≡def {x : φi(x)} saolegitimados (i = 1, 2) entao teremos t1 ≡def {s1} ≡ {x : x = s1} ≡ {x :(∀y)(y ∈ x↔ φ1(x)}, logo t1 ∪ s2 ≡def {x : x ∈ t1 ∨ x ∈ s2} ≡ {x : (∀y)(y ∈x↔ φ1(x)) ∨ φ2(x)}. E nesse sentido que devemos entender, por exemplo, o(meta)termo (a ∪ b) ∩ c ≡def {x : x ∈ (a ∪ b) ∧ x ∈ c} ≡ {x : (x ∈ a ∨ x ∈b) ∧ x ∈ c} na Proposicao 2.5. �

3 Axiomas Adicionais

Nesta secao definiremos tres axiomas adicionais da TC dada por ZF .

Axioma das Partes:

[A3] (∃y)(∀x)(x ∈ y↔ (∀z)(z ∈ x→ z ∈ a))

Este axioma garante en ZF que o conjunto {x : x ⊆ a} pode ser formado,uma vez que a foi formado. A notacao utilizada para este (meta)termo seraP(a). Como todo subconjunto de a sera formado ao menos no nıvel de a, entaoP(a) aparecera so no nıvel seguinte. Logo, este axioma e verdadeiro na teoriacumulativa de tipos, assumindo que nao existe um maximo nıvel.

Proposicao 3.1 (1) a ∈ P(a); ∅ ∈ P(a) na TC introduzida ate agora.(2) Se s ≡def {x : φ(x)} e t ≡def {x : ϕ(x)} sao legitimados em ZF , entaos ∈ P(t) sse s ⊆ t sse (∀x)(φ(x) → ϕ(x)); em particular, s ∈ P(s) e ∅ ∈ P(s).(3) ZF ` P(∅) = {∅}.(4) ZF ` P(P(∅)) = {∅, {∅}}.(5) ZF ` a ⊆ b↔ P(a) ⊆ P(b).(6) ZF ` P(a) ∪ P(b) ⊆ P(a ∪ b).(7) ZF ` P(a ∩ b) = P(a) ∩ P(b).(8) ZF ` P(a− b) ⊆ (P(a)− P(b)) ∪ {∅}.

9

Demonstracao: (1) a ∈ P(a) sse a ⊆ a. Pelo Exercıcio 2.7 (10),

∅ ∈ P(a) ∼ (∃w)((∀x)(x ∈ w↔ x 6= x) ∧ (∀x)(x ∈ w→ x ∈ a)).

Logo, ∅ ∈ P(a) ∼ (∃w)((∀x)(x 6∈ w) ∧ (∀x)(x ∈ w→ x ∈ a). Mas (∀x)(x 6∈ w)implica (∀x)(x ∈ w→ x ∈ a); portanto, pelo axioma do conjunto vazio obtemos∅ ∈ P(a).(2) Basta considerar ψ(x, y) ≡def (x ∈ P(y) ↔ x ⊆ y) e usar a Observacao 2.1.(3) P(∅) = {x : (∀y)(y ∈ x→ y 6= y)} = {x : x = ∅} = {∅} (= {y : (∀z)(z 6∈y)}).(4) Por (3) temos que (y ∈ P(∅)) ↔ (∀z)(z 6∈ y). Assim,

P(P(∅)) = {x : (∀y)(y ∈ x→ (∀z)(z 6∈ y))}≡def {x : φ(x)}.

Por outro lado,

{∅, {∅}} = {x : x = ∅ ∨ x = {∅}}= {x : (∀y)(y 6∈ x) ∨ (∀y)(y ∈ x↔ (∀z)(z 6∈ y))}≡def {x : ϕ(x)}.

Devemos provar entao a equivalencia de φ(x) e ϕ(x), as formulas que definem osmeta-termos P(P(∅)) e {∅, {∅}}, respectivamente. Partindo de ϕ(x), se assum-imos α(x) ≡def (∃y)(y ∈ x) entao obtemos φ(x), pois ϕ(x) ∼ (α(x) → φ(x)).Assumindo ¬α(x) entao tambem obtemos φ(x), porque nesse caso x = ∅, e∅ ∈ P(s) para todo s legitimado, por (2). Assim,

ϕ(x), (x = ∅) ∨ (x 6= ∅) implica ψ,

portanto ϕ(x) implica φ(x), pelo Princıpio do Terceiro Excluıdo. Analogamente(analisando os casos em que x = ∅ ou x 6= ∅) provamos que φ(x) implica ϕ(x).(5) Suponha que a ⊆ b, e seja x ∈ P(a). Se y ∈ x entao y ∈ a, logo y ∈ b. Assimy ∈ x implica y ∈ b, donde x ∈ P(b), isto e, P(a) ⊆ P(b). Reciprocamente,suponha que P(a) ⊆ P(b). Como a ∈ P(a), entao a ∈ P(b), donde a ⊆ b.(6), (7) e (8): Sao deixados como exercıcio. �

Axioma da Reuniao:

[A4] (∃y)(∀x)(x ∈ y↔ (∃z)((x ∈ z) ∧ (z ∈ a))

Este axioma legitima em ZF o meta-termo⋃a ≡def {x : (∃z)((x ∈ z) ∧ (z ∈ a))},

definindo a reuniao da colecao de conjuntos a; os elementos de⋃a sao exata-

mente os elementos dos elementos de a. Como os elementos dos elementos dea ocorrem em nıveis anteriores ao de a, entao

⋃a ocorre no nıvel de a (e pos-

sivelmente no nıvel anterior). Isto e valido na estrutura cumulativa de tipos.

10

Observe que, pelo axioma do par, existe {a, b}; logo, pelo axioma da reuniao,existe

⋃{a, b}. E facil provar que este conjunto e exatamente a ∪ b. Vemos

assim que o axioma da reuniao finita resulta agora redundante.

Proposicao 3.2 (1) [A1], [PR], [A4] `⋃{a, b} = a ∪ b. Portanto, o axioma

[RF] e deduzido dos outros axiomas introduzidos ate agora.(2) Se s ≡def {x : φ(x)} e t ≡def {x : ϕ(x)} sao legitimados entao⋃

{s, t} = s ∪ t = {x : φ(x) ∨ ϕ(x)}.

Demonstracao: (1) Por definicao,⋃{a, b} = {x : (∃z)(z ∈ {a, b} ∧ x ∈ z)}

= {x : (∃z)((z = a ∨ z = b) ∧ x ∈ z)}= {x : (∃z)((z = a ∧ x ∈ z) ∨ (z = b ∧ x ∈ z))}= {x : x ∈ a ∨ x ∈ b}= a ∪ b.

(2) Considere ψ(a, b) ≡def (∀x)(x ∈⋃{a, b} ↔ x ∈ a ∪ b) (lembrando que

devemos eliminar os meta-termos para obter uma formula). Por (1) temos(∀a)(∀b)ψ(a, b) e entao, pela Observacao 2.1, deduzimos ψ(s, t), pois s e t saolegitimados. �

Observe que, por [A2], sempre podemos definir a intersecao de uma familia naovazia de conjuntos:

Proposicao 3.3 [A2], (∃x)(x ∈ a) ` (∃w)(∀x)(x ∈ w↔ (∀y)(y ∈ a→ x ∈ y)).Em outras palavras, se a 6= ∅, entao

⋂a ≡def {x : (∀y)(y ∈ a→ x ∈ y)} e

legitimado.

Demonstracao: Por [A2] temos que existe s = {x : x ∈ b ∧ (∀y)(y ∈a→ x ∈ y)}. Mas b ∈ a e (∀y)(y ∈ a→ x ∈ y) implicam que x ∈ b, logos = {x : (∀y)(y ∈ a→ x ∈ y)}. �

Provaremos algumas propriedades basicas da intersecao e a reuniao arbitrariade conjuntos. Antes disso, precissamos ampliar a nossa notacao permitindo(meta)termos da forma {t : ϕ}, onde t e um (meta)termo da forma {x : φ}.Definimos {t : ϕ} como sendo {x : (∃u1) · · · (∃un)((x = t) ∧ ϕ)} onde u1,. . . , un sao algumas das variaveis livres comuns a t e ϕ (no contexto ficaraclaro quais variaveis serao livres, funcionando como parametros). Por exemplo,podemos formar o termo s ≡def {a ∩ c : c ∈ b}, com variaveis livres a e b,a partir do termo t ≡def a ∩ c (com variaveis livres a e c). Logo, s denota otermo {x : (∃c)((x = a ∩ c) ∧ c ∈ b)}; aqui, c e b sao as variaveis livres deϕ(c, b) ≡def c ∈ b. E imediato que se t e legitimado, entao ϕ implica t ∈ {t : ϕ}.

Proposicao 3.4 Na TC introduzida ate agora temos o seguinte:(1)

⋃∅ = ∅.

(2)⋃{a} = a.

(3) Se s ≡def {x : φ(x)} e legitimado, entao⋃{s} = s; em particular,

⋃{∅} =

∅.

11

(4)⋃

(a ∪ b) = (⋃a) ∪ (

⋃b).

(5)⋂{a, b} = a ∩ b.

(6) Se s ≡def {x : φ(x)} e t ≡def {x : ϕ(x)} sao legitimados, entao⋂{s, t} =

s ∩ t.(7) Se a 6= ∅ e b 6= ∅, entao existe

⋂(a ∪ b), e

⋂(a ∪ b) = (

⋂a) ∩ (

⋂b).

(8) Se a 6= ∅, entao⋂a ⊆

⋃a.

(9) a ∩ (⋃b) =

⋃{a ∩ c : c ∈ b}.

(10) Se b 6= ∅, entao existe⋂{a ∪ c : c ∈ b}, e a ∪ (

⋂b) =

⋂{a ∪ c : c ∈ b}.

Demonstracao: (1) x ∈⋃∅ sse (∃z)(x ∈ z ∧ z ∈ ∅) see (∃z)(x ∈ z ∧ z 6= z)

sse (∃z)(z 6= z). Logo, x 6∈⋃∅ para todo x.

(2) x ∈⋃{a} sse (∃z)(x ∈ z ∧ z ∈ {a}) sse (∃z)(x ∈ z ∧ z = a) sse x ∈ a.

(3) E consequencia de (2), considerando ψ(a) ≡def (∀x)(x ∈⋃{a} ↔ x ∈ a), a

Observacao 2.1, e o fato de s ser legitimado.(4) x ∈

⋃(a∪ b) sse (∃z)(x ∈ z ∧ z ∈ a∪ b) sse (∃z)(x ∈ z ∧ (z ∈ a∨ z ∈ b)) sse

(∃z)((x ∈ z∧z ∈ a)∨(x ∈ z∧z ∈ b)) sse (∃z)(x ∈ z∧z ∈ a)∨(∃z)(x ∈ z∧z ∈ b)sse x ∈ (

⋃a) ∪ (

⋃b) (lembre que (∃z)(φ(z) ∨ ϕ(z)) ∼ (∃z)φ(z) ∨ (∃z)ϕ(z)).

(5) x ∈⋂{a, b} sse (∀y)(y ∈ {a, b} → x ∈ y) sse (∀y)((y = a ∨ y = b) → x ∈ y)

sse (∀y)((y = a→ x ∈ y)∧(y = b→ x ∈ y)) sse (∀y)(y = a→ x ∈ y)∧(∀y)(y =b→ x ∈ y) sse x ∈ a ∧ x ∈ b sse x ∈ a ∩ b (lembre que (∀y)(φ(y) ∧ ϕ(y)) ∼(∀y)φ(y) ∧ (∀y)ϕ(y)).(6) Considere ψ(a, b) ≡def (∀x)(x ∈

⋂{a, b} ↔ x ∈ x ∈ a ∩ b). Por (5),

vale (∀a)(∀b)ψ(a, b), donde deduzimos ψ(s, t) para s e t legitimados, pela Ob-servacao 2.1.(7) A prova e similar a do item (5).(8) E imediato.(9) x ∈

⋃{a ∩ c : c ∈ b} sse (∃z)(x ∈ z ∧ (∃c)(z = (a ∩ c) ∧ c ∈ b) sse (∃c)(x ∈

(a ∩ c) ∧ c ∈ b) sse (∃c)((x ∈ a ∧ (x ∈ c ∧ c ∈ b)) sse x ∈ a ∧ (∃c)(x ∈ c ∧ c ∈ b)sse x ∈ a∩ (

⋃b) (lembre que (∃c)(ϕ∧φ(c)) ∼ ϕ∧ (∃c)φ(c) se c nao ocorre livre

em ϕ).(10) x ∈ a∪ (

⋂b) sse x ∈ a∨ (∀c)(c ∈ b→ x ∈ c). Por outro lado, x ∈

⋂{a∪c :

c ∈ b} sse (∀y)(y ∈ {a ∪ c : c ∈ b} → x ∈ y).Seja x ∈ a ∪ (

⋂b) e y ∈ {a ∪ c : c ∈ b}; logo, existe c′ ∈ b tal que y = a ∪ c′.

Se x ∈ a, entao x ∈ (a ∪ c′) = y. Se (∀c)(c ∈ b→ x ∈ c), entao, tomando c′

no lugar de c, obtemos x ∈ c′ e entao x ∈ y. Em todo caso, provamos quex ∈ a ∪ (

⋂b) implica y ∈ {a ∪ c : c ∈ b} → x ∈ y, donde x ∈ a ∪ (

⋂b)

implica x ∈⋂{a ∪ c : c ∈ b}. Reciprocamente, seja x ∈

⋂{a ∪ c : c ∈ b}, e

c ∈ b. Como a ∪ c ∈ {a ∪ c : c ∈ b}, entao x ∈ a ∪ c, donde x ∈ a ∨ x ∈ c.Desta maneira, x ∈

⋂{a ∪ c : c ∈ b} implica c ∈ b→ (x ∈ a ∨ x ∈ c) e

entao x ∈ a ∨ (c ∈ b→ x ∈ c). Portanto, x ∈⋂{a ∪ c : c ∈ b} implica

(∀c)(x ∈ a ∨ (c ∈ b→ x ∈ c)) que implica x ∈ a ∨ (∀c)(c ∈ b→ x ∈ c) (lembreque (∀c)(α ∨ β(c)) ∼ α ∨ (∀c)β(c), se c nao ocorre livre em α). �

Finalmente formularemos o axioma da regularidade. Este axioma, devido a Zer-melo (1930) (existe uma versao previa de von Neumann em 1925) e fundamental

12

para evitar situacoes da forma x ∈ x ou, em geral,

x1 ∈ x2 ∈ · · · ∈ xn ∈ x1.

Alem disso, este axioma evita “descensos infinitos” da forma

· · · ∈ xn ∈ xn−1 ∈ · · · ∈ x2 ∈ x1

(isto significa que a relacao x ∈ y e bem fundada, como estudaremos depois).

Axioma da Regularidade:

[A5] (∃y)(y ∈ x) → (∃y)(y ∈ x ∧ (∀z)¬(z ∈ x ∧ z ∈ y))

Este e o unico axioma expressando a ideia que os conjuntos ocorrem en nıveisou tipos, e e precisso utilizar a teoria cumulativa de tipos para entende-lo. Comefeito, consideremos um conjunto x nao vazio. Comecemos a analizar os nıveisde baixo para cima, ate encontrar o primeiro nıvel em que foram formadoselementos de x. Por exemplo, se x = {{∅}, {{∅}}, {{{∅}}}}, entao o primeironıvel em que aparecem elementos de x e o nıvel 2, assumindo que nao temosindivıduos. Assim se y ∈ x esta no nıvel mınimo, entao os elementos de y (seexistirem) devem necessariamente ter sido criados em nıveis anteriores, logo naopodem pertencer a x, isto e: y∩x = ∅ (o que se confirma no nosso exemplo). Osaxiomas de extensionalidade e regularidade sao os unicos que exigem conjuntossatisfazendo certas propriedades; os outros axiomas estabelecem a existencia desuficientes conjuntos em alguma direcao.

Definicao 3.5 S e o sistema axiomatico da TC que consiste dos axiomas [A1]-[A5] mais [PR].

Proposicao 3.6 (1) S ` a 6∈ a.(2) S ` ¬(a ∈ b ∧ b ∈ a).

Demonstracao: (1) a ∈ a implica a ∈ {a} ∩ a. Por [A5] existe x ∈ {a} talque {a} ∩ x = ∅. Mas x ∈ {a} sse x = a e entao {a} ∩ a = ∅, o que contradiza ∈ {a} ∩ a.(2) Se a ∈ b ∧ b ∈ a, entao a ∈ {a, b} ∩ b e b ∈ {a, b} ∩ a. Por [A5] existex ∈ {a, b} tal que {a, b} ∩ x = ∅. Mas x ∈ {a, b} sse x = a ou x = b. Os doiscasos levam a uma contradicao. �

A partir de agora, desenvolveremos um estudo da TC obtida atraves do sis-tema S. O sistema completo ZF da TC sera introduzido na Secao 11. Porem, eimportante observar que uma parte interessante da TC “finita” pode ser desen-volvida utilizando apenas o sub-sistema S de ZF , como veremos nas proximassecoes.

4 Produtos Cartesianos

Estamos em condicoes de comecar a desenvolver as primeiras aplicacoes dofragmento S de ZF introducido ate agora. Antes de estudar a teoria de relacoes

13

e funcoes na proxima secao, e necessario definir o conceito de par ordenado, apartir do qual sao introduzidos os produtos cartesianos de conjuntos.

Definicao 4.1 (Kuratowski) (i) 〈a, b〉 ≡def {{a}, {a, b}}.(ii) 〈a1, . . . , an+1〉 ≡def 〈〈a1, . . . , an〉, an+1〉 para n ≥ 2.

E claro que o axioma [PR] assegura a existencia de 〈a, b〉 para todo a e b. Ob-serve que a definicao de 〈a, b, c〉 como sendo {{a}, {a, b}, {a, b, c}} nao funciona(porque?).

Proposicao 4.2 S ` 〈a, b〉 = 〈c, d〉 ↔ (a = c) ∧ (b = d).

Demonstracao: x ∈ 〈a, b〉 sse x = {a} ou x = {a, b}, e x ∈ 〈c, d〉 sse x = {c}ou x = {c, d}. Suponha que 〈a, b〉 = 〈c, d〉; a prova de que a = c e b = d serafeita por analise de casos.Caso 1: a = b. Logo, 〈a, b〉 = {{a}} = {{c}, {c, d}} e entao, pelo Corolario 2.4,{c} = {a} = {c, d} donde, usando novamente o Corolario 2.4, obtemos quec = a = d.Caso 2: a 6= b. Dado que {a} ∈ 〈c, d〉, entao {a} = {c} ou {a} = {c, d} (usandoo Corolario 2.4).Caso 2.a: {a} = {c}. Logo a = c, e entao 〈c, d〉 = {{a}, {a, d}}. Como{a, b} ∈ 〈c, d〉 e {a, b} 6= {a} (pelo Corolario 2.4 e a hipotese a 6= b), entao{a, b} = {a, d}. Daqui obtemos, de a 6= b, que b = d.Caso 2.b: {a} = {c, d}. Logo c = a = d e entao 〈c, d〉 = {{a}}. Mas{a, b} ∈ 〈c, d〉, donde {a, b} = {a}, e entao a = b, o que contradiz a hipotesea 6= b. Daqui inferimos que vale o caso 2.a.Claramente, a = c, b = d implica 〈a, b〉 = 〈c, d〉, pelas regras da igualdade. �

Uma vez que possuimos a definicao de par ordenado, podemos criar o con-junto de todos os pares ordenados 〈x, y〉, onde x ∈ a e y ∈ b, fixados a e b.

Definicao 4.3 O produto cartesiano de a e b e dado por a × b ≡def {〈x, y〉 :x ∈ a ∧ y ∈ b}.

Provaremos agora que o termo a× b e legitimado.

Proposicao 4.4 a × b = {x : x ∈ P(P(a ∪ b)) ∧ (∃y)(∃z)(x = 〈y, z〉 ∧ (y ∈a) ∧ (z ∈ b))}. Portanto, a × b e legitimado por [A2] (dado que os termosenvolvidos na definicao sao legitimados pelos outros axiomas de S).

Demonstracao: Temos que {x : x ∈ P(P(a∪ b))∧ (∃y)(∃z)(x = 〈y, z〉 ∧ (y ∈a) ∧ (z ∈ b))} e legitimado por [A2]. Provaremos em S que

(∃y)(∃z)(x = 〈y, z〉 ∧ (y ∈ a) ∧ (z ∈ b)) →→ x ∈ P(P(a ∪ b)) ∧ (∃y)(∃z)(x = 〈y, z〉 ∧ (y ∈ a) ∧ (z ∈ b))

e entao (dado que a implicacao recıproca e sempre verdadeira) teremos provadoo resultado. Seja entao x = 〈y, z〉 tal que y ∈ a, z ∈ b. Portanto, {y} ⊆ a ∪ be {y, z} ⊆ a ∪ b, donde {y} ∈ P(a ∪ b) e {y, z} ∈ P(a ∪ b). Desta maneira,x = {{y}, {y, z}} ⊆ P(a ∪ b) e entao x ∈ P(P(a ∪ b)). �

14

Proposicao 4.5 S ` a× b = ∅ ↔ a = ∅ ∨ b = ∅.

Demonstracao: Suponha que a × b = ∅. Assuma que ¬(a = ∅ ∨ b = ∅), istoe, a 6= ∅ e b 6= ∅. Logo, (∃y)(y ∈ a) e (∃z)(z ∈ b). Daqui 〈y, z〉 ∈ a × b, umacontradicao. Portanto, inferimos que a = ∅ ∨ b = ∅. Reciprocamente, suponhaque a = ∅ ∨ b = ∅; logo, ¬(∃y)(y ∈ a) ∨ ¬(∃z)(z ∈ b) e entao ¬(∃y)(∃z)((y ∈a) ∧ (z ∈ b) ∧ x = 〈y, z〉) para todo x. Portanto, x 6∈ a× b para todo x, dondea× b = ∅. �

Proposicao 4.6 S ` a× b = b× a↔ (a = ∅ ∨ b = ∅ ∨ a = b).

Demonstracao: Suponha que a × b = b × a; assumindo a 6= ∅, b 6= ∅ e a 6= bprovaremos uma contradicao. Com efeito, de a 6= b inferimos que existe x ∈ a,x 6∈ b ou existe x ∈ b, x 6∈ a, por [A1]. Assumamos x ∈ a, x 6∈ b (o raciocıniopara a outra possibilidade e simetrico). Seja y ∈ b (assumimos b 6= ∅). Portanto,〈x, y〉 ∈ a× b = b× a, e entao (x ∈ b) ∧ (y ∈ a), donde x ∈ b, uma contradicao.Reciprocamente, suponha que (a = ∅∨b = ∅∨a = b). Temos que (a = ∅∨b = ∅)implica a × b = ∅ = b × a, pela Proposicao 4.5. Por outro lado, a = b implicaa× b = b× a, pelas regras da igualdade. �

Proposicao 4.7 (i) S ` (a 6= ∅ ∧ a× b ⊆ a× c) → (b ⊆ c).(ii) S ` (b ⊆ c) → (a× b ⊆ a× c).

Demonstracao: (i) O caso b = ∅ e trivial. Assuma entao b 6= ∅ e seja y ∈ b.Fixe x ∈ a (assumimos a 6= ∅); logo 〈x, y〉 ∈ a × b, e a × b ⊆ a × c, donde〈x, y〉 ∈ a× c. Daqui (x ∈ a) ∧ (y ∈ c), e entao y ∈ c; isto e, b ⊆ c.(ii) O caso a× b = ∅ e trivial. Seja z ∈ a× b; logo, z = 〈x, y〉 para x ∈ a e y ∈ b.Mas b ⊆ c, donde y ∈ c e entao z = 〈x, y〉 ∈ a× c. Portanto a× b ⊆ a× c. �

Proposicao 4.8 (i) S ` a× (b ∩ c) = (a× b) ∩ (a× c).(ii) S ` a× (b ∪ c) = (a× b) ∪ (a× c).(iii) S ` a× (b− c) = (a× b)− (a× c).

Demonstracao: (i) 〈x, y〉 ∈ a × (b ∩ c) sse (x ∈ a) ∧ (y ∈ (b ∩ c)) sse (x ∈a) ∧ ((y ∈ b) ∧ (y ∈ c)) sse ((x ∈ a) ∧ (y ∈ b)) ∧ ((x ∈ a) ∧ (y ∈ c)) sse(〈x, y〉 ∈ a× b) ∧ (〈x, y〉 ∈ a× c) sse 〈x, y〉 ∈ (a× b) ∩ (a× c).(ii), (iii): Sao deixados como exercıcio. �

Proposicao 4.9 S ` (a ⊆ a× a) → a = ∅.

Demonstracao: Se z ∈ a entao, de a ⊆ a× a, inferimos

z = {{x}, {x, y}} ∈ a× a para algum x, y ∈ a. (∗)

Suponha entao a 6= ∅. Pelo axioma de regularidade aplicado a a ∪ (⋃a) 6= ∅,

existe c ∈ a ∪ (⋃a) tal que c ∩ (a ∪ (

⋃a)) = ∅. Observe que os elementos de

a ∪ (⋃a) sao conjuntos nao vazios, por (∗). Daqui, c 6= ∅. Se c ∈ a, entao

c ⊆⋃a (isto e uma consequencia imediata da definicao de

⋃a, e e deixado

como exercıcio). Daqui ∅ 6= c = c ∩ (⋃a), o que contradiz c ∩ (a ∪ (

⋃a)) = ∅.

Portanto c ∈⋃a donde, por (∗), teremos que c = {x} ou c = {x, y} para

x, y ∈ a. Nos dois casos c ∩ a 6= ∅, uma contradicao. �

15

5 Relacoes em S

Nesta secao trataremos a teoria elementar de relacoes em S, utilizando os re-sultados sobre produtos cartesianos provados na secao anterior.

Definicao 5.1 Introduzimos as notacoes seguintes:rel(r) para (∀x)(x ∈ r→ (∃y)(∃z)(x = 〈y, z〉))

“r e uma relacao (um conjunto de pares ordenados)”;u r v para 〈u, v〉 ∈ r

“u esta em relacao r com v”;dom(r) para {x : (∃y)(x r y)}

(o domınio de r);im(r) para {y : (∃x)(x r y)}

(a imagem de r);r|z para {u : u ∈ r ∧ (∃x)(∃y)(u = 〈x, y〉 ∧ x ∈ z)}

(r com domınio restrito a z);r−1 para {u : (∃x)(∃y)(u = 〈x, y〉 ∧ y r x)}

(a relacao inversa de r);r“z para {y : (∃x)(x ∈ z ∧ x r y)}, isto e, im(r|z)

(a imagem de z por r);r(z) para {y : (∃u)((∀w)(z r w↔ w = u) ∧ y ∈ u)}

(o unico valor de r em z, se existir, ou ∅ em caso contrario).

Proposicao 5.2 (a) (rel(r) ∧ (s ⊆ r)) → rel(s); em particular, rel(∅).(b) (rel(r) ∧ rel(s)) → rel(r ∪ s) ∧ rel(r ∩ s) ∧ rel(r − s).

Demonstracao: (a) z ∈ s implica z ∈ r implica z = 〈x, y〉 para algum x e y;logo, rel(s).(b) z ∈ r ∪ s implica z ∈ r ou z ∈ s; nos dois casos, z = 〈x, y〉 para algum x, y.Os outros casos sao similares. �

Proposicao 5.3 Os meta-termos da Definicao 5.1 sao legitimados.

Demonstracao: dom(r): Por [A2], existe {x : x ∈⋃ ⋃

r ∧ (∃y)(x r y)}.Provaremos que a condicao x ∈

⋃ ⋃r pode ser eliminada. Com efeito, suponha

que (∃y)(x r y). Logo 〈x, y〉 ∈ r, isto e, {{x}, {x, y}} ∈ r. Daqui {x} ∈⋃r e

entao x ∈⋃ ⋃

r.im(r): A prova e analoga a anterior.r|z: E legitimado por [A2].r−1: Por [A2] existe {u : u ∈ im(r)× dom(r) ∧ (∃x)(∃y)(u = 〈x, y〉 ∧ y r x)}.Provaremos que a condicao u ∈ im(r)×dom(r) e implicada pela outra condicao.Seja entao u satisfazendo: (∃x)(∃y)(u = 〈x, y〉 ∧ y r x). Logo, u = 〈x, y〉 talque y r x, donde y ∈ dom(r) e x ∈ im(r), e entao u = 〈x, y〉 ∈ im(r)× dom(r).r“z: Temos que r“z = im(r|z), sendo portanto legitimado.r(z): Por [A2], existe {y : y ∈

⋃im(r)∧ (∃u)((∀w)(z r w↔ w = u)∧ y ∈ u)}.

Como antes, veremos que a condicao de separacao y ∈⋃im(r) e redundante.

Com efeito, suponha que y satisfaz (∃u)((∀w)(z r w↔ w = u) ∧ y ∈ u), e seja

16

u satisfazendo (∀w)(z r w↔ w = u) ∧ y ∈ u. Tomando w = u obtemos que zr u, donde u ∈ im(r). Mas y ∈ u, portanto y ∈

⋃im(r). �

Proposicao 5.4 (a) dom(r ∪ s) = dom(r) ∪ dom(s).(b) dom(r ∩ s) ⊆ dom(r) ∩ dom(s).(c) dom(r)− dom(s) ⊆ dom(r − s).(d) im(r ∪ s) = im(r) ∪ im(s).(e) im(r ∩ s) ⊆ im(r) ∩ im(s).(f) im(r)− im(s) ⊆ im(r − s).

Demonstracao: (a) Temos que x ∈ dom(r∪s) sse (∃y)(x (r∪s) y) sse (∃y)((xr y) ∨ (x s y)) sse (∃y)(x r y) ∨ (∃y)(x s y) sse x ∈ dom(r) ∨ x ∈ dom(s) ssex ∈ dom(r) ∪ dom(s).(b)-(f): As provas sao analogas, e sao deixadas como exercıcio. �

Com relacao a r−1 temos as seguintes propriedades:

Proposicao 5.5 (a) (r−1)−1 ⊆ r; rel(r) → r ⊆ (r−1)−1.(b) (r ∪ s)−1 = r−1 ∪ s−1.(c) (r ∩ s)−1 = r−1 ∩ s−1.(d) (r − s)−1 = r−1 − s−1.

Demonstracao: (a) z ∈ (r−1)−1 implica que z = 〈x, y〉 tal que x (r−1)−1

y. Mas x (r−1)−1 y implica y r−1 x implica x r y, isto e, z = 〈x, y〉 ∈ r.Reciprocamente, se rel(r), seja z ∈ r; entao z = 〈x, y〉 tal que x r y, e a provae como acima, revertendo as implicacoes.(b) 〈x, y〉 ∈ (r ∪ s)−1 sse 〈y, x〉 ∈ r ∪ s sse (〈y, x〉 ∈ r) ∨ (〈y, x〉 ∈ s) sse〈x, y〉 ∈ r−1 ∨ 〈x, y〉 ∈ s−1 see 〈x, y〉 ∈ r−1 ∪ s−1.(c) Analoga a prova anterior.(d) 〈x, y〉 ∈ (r − s)−1 sse 〈y, x〉 ∈ r − s sse (〈y, x〉 ∈ r) ∧ (〈y, x〉 6∈ s) sse〈x, y〉 ∈ r−1 ∧ 〈x, y〉 6∈ s−1 see 〈x, y〉 ∈ r−1 − s−1. �

Definicao 5.6 A composicao de r e s e definida como

r ◦ s ≡def {〈x, y〉 : (∃z)((x r z) ∧ (z s y))}.

Proposicao 5.7 r ◦ s e legitimado em S.

Demonstracao: Provaremos que

r◦s = {u : u ∈ dom(r)×im(s)∧(∃x)(∃y)(∃z)((u = 〈x, y〉)∧(x r z)∧(z s y))},

donde o resultado segue por [A2]. Assim, suponha que u = 〈x, y〉 tal que xr z, z s y para algum z. Logo x ∈ dom(r) e y ∈ im(s), donde u = 〈x, y〉 ∈dom(r)× im(s). �

A composicao satisfaz as seguintes propriedades:

17

Proposicao 5.8 (a) r ◦ (s ∪ t) = (r ◦ s) ∪ (r ◦ t).(b) r ◦ (s ∩ t) ⊆ (r ◦ s) ∩ (r ◦ t).(c) (r ◦ s)− (r ◦ t) ⊆ r ◦ (s− t).(d) (r ◦ s)−1 = s−1 ◦ r−1.(e) r ◦ (s ◦ t) = (r ◦ s) ◦ t

Demonstracao: (a) Temos que

x (r ◦ (s ∪ t)) ysee (∃z)((x r z) ∧ (z (s ∪ t) y))see (∃z)((x r z) ∧ ((z s y) ∨ (z t y)))see (∃z)(((x r z) ∧ (z s y)) ∨ ((x r z) ∧ (z t y)))see (∃z)((x r z) ∧ (z s y)) ∨ (∃z)((x r z) ∧ (z t y))see (x (r ◦ s) y) ∨ (x (r ◦ t) y)see x ((r ◦ s) ∪ (r ◦ t)) y.

(b) Temos que

x (r ◦ (s ∩ t)) yimplica (∃z)((x r z) ∧ (z (s ∩ t) y))implica (∃z)((x r z) ∧ ((z s y) ∧ (z t y)))implica (∃z)(((x r z) ∧ (z s y)) ∧ ((x r z) ∧ (z t y)))implica (∃z)((x r z) ∧ (z s y)) ∧ (∃z)((x r z) ∧ (z t y))implica (x (r ◦ s) y) ∧ (x (r ◦ t) y)implica x ((r ◦ s) ∩ (r ◦ t)) y,

lembrando que (∃z)(φ ∧ ψ) → ((∃z)φ ∧ (∃z)ψ). A recıproca desta propriedadelogica nao e verdadeira em geral, donde nao vale em geral a igualdade em (b).(c) A prova e analoga a anterior.(d) x (r ◦ s)−1 y sse y (r ◦ s) x sse (∃z)((y r z)∧ (z s x)) sse (∃z)((z r−1 y)∧ (xs−1 z)) sse x (s−1 ◦ r−1) y.(e) E deixada como exercıcio. �

A restricao satisfaz as seguintes propriedades:

Proposicao 5.9 (a) r|z = r ∩ (z × im(r)).(b) r|(a ∩ b) = (r|a) ∩ (r|b).(c) r|(a ∪ b) = (r|a) ∪ (r|b).(d) r|(a− b) = (r|a)− (r|b).(e) (r ◦ s)|a = (r|a) ◦ s.

Demonstracao: Exercıcio. �

Finalmente, a imagem r“z satisfaz as seguintes propriedades:

Proposicao 5.10 (a) r“(a ∪ b) = r“a ∪ r“b.(b) r“(a ∩ b) ⊆ r“a ∩ r“b.

18

(c) r“a− r“b ⊆ r“(a− b).(d) (a ⊆ b) → (r“a ⊆ r“b).(e) (r“a = ∅) ↔ (dom(r) ∩ a = ∅).

Demonstracao: (a) Temos quey ∈ r“(a ∪ b)sse (∃x)((x r y) ∧ (x ∈ a ∪ b))sse (∃x)((x r y) ∧ (x ∈ a)) ∨ (∃x)((x r y) ∧ (x ∈ b))sse (y ∈ r“a) ∨ (y ∈ r“b)sse y ∈ (r“a ∪ r“b).

(b) A prova e analoga, usando agora (∃x)(φ ∧ ψ) → ((∃x)φ ∧ (∃x)ψ).(c) Analoga a anterior.(d) y ∈ r“a implica (∃x)((x r y) ∧ (x ∈ a)) implica (∃x)((x r y) ∧ (x ∈ b))implica y ∈ r“b.(e) y ∈ r“a implica (∃x)((x r y)∧ (x ∈ a)). Portanto, se (x r y)∧ (x ∈ a), entaox ∈ dom(r) ∩ a. Isto e, r“a 6= ∅ implica dom(r) ∩ a 6= ∅. Reciprocamente, sex ∈ dom(r)∩a, entao x r y para algum y, e x ∈ a, donde (∃x)((x r y)∧(x ∈ a)).Portanto y ∈ r“a, isto e: dom(r) ∩ a 6= ∅ implica r“a 6= ∅. �

Exemplo 5.11 Assumindo os numeros naturais como indivıduos, sejam

r = {〈1, 2〉, 〈1, 3〉, 〈2, 1〉, 〈2, 3〉}, s = {〈2, 1〉, 〈3, 5〉}.

Portanto,

dom(r) = {1, 2}, im(r) = {1, 2, 3},r“({1}) = {2, 3}, r“({3}) = ∅,s−1 = {〈1, 2〉, 〈5, 3〉}, r ◦ s = {〈1, 1〉, 〈1, 5〉, 〈2, 5〉},s ◦ r = {〈2, 2〉, 〈2, 3〉}, r|{2} = {〈2, 1〉, 〈2, 3〉},im(r|{2}) = {1, 3} = r“{2}, (r−1)“{3} = {1, 2}. �

6 Relacoes de Ordem

Um tipo muito importante de relacoes e a classe das relacoes de ordem. Elasocorrem em quase todas as areas da matematica, sendo que o seu estudo cons-titui, em si, uma area relevante dentro da Matematica.

Definicao 6.1 Introduzimos as notacoes seguintes:ref(r, a) para (∀x)(x ∈ a→ (x r x))

(r e reflexiva em a);irr(r, a) para (∀x)(x ∈ a→ ¬(x r x))

(r e irreflexiva em a);sim(r, a) para (∀x)(∀y)(((x ∈ a) ∧ (y ∈ a) ∧ (x r y)) → (y r x))

(r e simetrica em a);asim(r, a) para (∀x)(∀y)(((x ∈ a) ∧ (y ∈ a) ∧ (x r y)) → ¬(y r x))

(r e asimetrica em a);

19

anti(r, a) para (∀x)(∀y)(((x ∈ a) ∧ (y ∈ a) ∧ (x r y) ∧ (y r x)) → (x = y));(r e antisimetrica em a);

tran(r, a) para(∀x)(∀y)(∀z)(((x ∈ a) ∧ (y ∈ a) ∧ (z ∈ a) ∧ (x r y) ∧ (y r z)) → (x r z))(r e transitiva em a);

con(r, a) para (∀x)(∀y)(((x ∈ a) ∧ (y ∈ a) ∧ (x 6= y)) → ((x r y) ∨ (y r x)))(r e conectada em a);

fcon(r, a) para (∀x)(∀y)(((x ∈ a) ∧ (y ∈ a)) → ((x r y) ∨ (y r x)))(r e fortemente conectada em a).

As definicoes usuais (r e reflexiva, r e simetrica, etc.) sao obtidas considerandoa = dom(r)∪im(r) ≡def F (r); assim, ref(r) denota ref(r, F (r)), sim(r) denotasim(r, F (r)), etc. Sera muito util definir a relacao identidade sobre um conjuntoa, dada pelo termo I(a) = {〈x, x〉 : x ∈ a}.

Proposicao 6.2 O termo I(a) e legitimado em S.

Demonstracao: O termo s ≡def {z : z ∈ PP(a)∧ (∃x)(z = 〈x, x〉∧ (x ∈ a))}e legitimado por [A2]. Basta entao provar que (∃x)(z = 〈x, x〉∧(x ∈ a)) implicaz ∈ PP(a). Com efeito, z = 〈x, x〉 implica z = {{x}}. Por outro lado, x ∈ aimplica {x} ∈ P(a), portanto z ⊆ P(a), isto e, z ∈ PP(a). Logo I(a) = s,sendo portanto legitimado. �

Proposicao 6.3 Seja r uma relacao. As seguintes propriedades sao demons-traveis em S:(a) asim(r) → irr(r).(b) asim(r) → anti(r).(c) (sim(r) ∧ tran(r)) → ref(r).

Demonstracao: (a) Seja x ∈ F (r); como r e asimetrica, entao (x r x) implica¬(x r x), donde obtemos ¬(x r x).(b) Sejam x, y ∈ F (r) tais que (x r y)∧(y r x). Logo, obtemos ¬(y r x), pois r easimetrica, donde deduzimos uma contradicao. Portanto (x, y ∈ F (r))∧asim(r)implica ¬((x r y) ∧ (y r x)), e a posteriori ¬((x r y) ∧ (y r x)) ∨ (x = y), istoe, ((x r y) ∧ (y r x)) → (x = y).(c) Suponha que x ∈ F (r). Se x ∈ dom(r), entao x r y para algum y ∈ F (r).Como sim(r), entao y r x, donde (x r y)∧(y r x). Portanto x r x, pois tran(r).Por outro lado, se x ∈ im(r), entao y r x para algum y ∈ F (r), e a prova eanaloga. �

Podemos definir cinco tipos de ordens:

Definicao 6.4 Sejam r uma relacao e a um conjunto. Definimos o seguinte:(a) qo(r, a) denota ref(r, a) ∧ tran(r, a) (r e uma quase ordem em a).(b) op(r, a) denota ref(r, a)∧ anti(r, a)∧ tran(r, a) (r e uma ordem parcial ema).(c) os(r, a) denota anti(r, a) ∧ tran(r, a) ∧ fcon(r, a) (r e uma ordem simplesem a).

20

(d) ope(r, a) denota asim(r, a) ∧ tran(r, a) (r e uma ordem parcial estrita ema).(e) ose(r, a) denota asim(r, a) ∧ tran(r, a) ∧ con(r, a) (r e uma ordem simplesestrita em a).(f) qo(r) denota qo(r, F (r)), etc.

Se r satisfaz alguma das definicoes de ordem introduzidas na Definicao 6.4,entao escreveremos x ≤ y ou ainda x < y (se r e irreflexiva) no lugar de x r y,quando nao existir risco de confusao.

Exemplos 6.5 (1) Dado um conjunto b, entao a = P(b) e parcialmente orde-nado pela relacao x ≤ y sse x ⊆ y ⊆ b. Com efeito, ≤ e parcial, pois nem todopar de subconjuntos x, y de b deve ser necessariamente comparavel pela relacaode inclusao.(2) O conjunto N dos numeros naturais e ordenado pela relacao: n ≤m sse n|m(n divide a m). Com efeito, n ≤ n para todo n, pois n = 1.n, donde n|n. Poroutro lado, n|m e m|n significa: existem k, h em N tais que m = kn, n = hm,portanto m = k(hm) = (kh)m. Se m = 0, entao n = h.0 = 0 = m. Se m 6= 0,entao de m = (kh)m inferimos 1 = kh, e entao k = 1 = h, donde n = m.Finalmente, se n ≤m e m ≤ r, entao m = kn e r = hm para certos k, h ∈ N.Portanto r = hm = h(kn) = (hk)n para hk ∈ N donde n|r, isto e, n ≤ r.Observe que 1|n para todo n, pois n = n.1; logo 1 ≤ n para todo n, isto e, 1 eo mınimo elemento de N com a ordem divide a. Por outro lado, 0 = 0.n paratodo n, e entao n|0 para todo n, isto e, n ≤ 0 para todo n. Daqui 0 e o maximoelemento de N com a ordem divide a. Observe que a ordem nao e conectada:2 6≤ 3 e 3 6≤ 2, pois 2 e 3 sao co-primos. Os numeros primos positivos saoos elementos minimais, isto e, se n ≤ p e p e primo, entao n = 1 (o mınimoelemento com relacao a ≤ ) ou n = p. Reciprocamente, se p e minimal, entaop deve ser necessariamente primo. �

Proposicao 6.6 Em S temos o seguinte:(a) op(r) → qo(r).(b) os(r) → op(r).(c) os(r) → os(r−1).(d) qo(r) ∧ qo(s) → qo(r ∩ s).

Demonstracao: (a) Imediato das definicoes.(b) So falta provar a reflexividade da r. Mas x ∈ F (r) implica ((x r x) ∨ (x rx)), isto e, x r x, pois fcon(r).(c) E claro que tran(r) → tran(r−1). Com efeito, ((x r−1 y)∧(y r−1 z)) implica((y r x) ∧ (z r y)) implica z r x (pois tran(r)) implica x r−1 z. Da mesmamaneira provamos que anti(r) → anti(r−1) e fcon(r) → fcon(r−1).(d) Seja x ∈ F (r ∩ s), logo x ∈ F (r) ∩ F (s), donde ((x r x) ∧ (x s x)), poisref(r)∧ ref(s). Portanto x (r∩ s) x, isto e, ref(r∩ s). Suponha agora que ((x(r ∩ s) y) ∧ (y (r ∩ s) z)). Daqui obtemos ((x r y) ∧ (y r z)), donde x r z, poistran(r). Analogamente x s z, e entao x (r ∩ s) z; isto e, tran(r ∩ s). �

21

Observe que a reuniao de duas quase-ordens nao resulta necessariamente numaquase-ordem. Por exemplo

r = {〈1, 1〉, 〈2, 2〉, 〈1, 2〉}, s = {〈2, 2〉, 〈3, 3〉, 〈2, 3〉}

sao duas quase-ordens, mas a uniao, embora reflexiva, nao e transitiva. Asituacao muda se F (r) ∩ F (s) = ∅.

Proposicao 6.7 S ` (qo(r) ∧ qo(s) ∧ (F (r) ∩ F (s) = ∅)) → qo(r ∪ s).

Demonstracao: E claro que r ∪ s e reflexiva. Suponha que ((x (r ∪ s) y) ∧ (y(r ∪ s) z)). Como F (r)∩F (s) = ∅, entao so vale uma das seguintes afirmacoes:

((x r y) ∧ (y r z)), ((x s y) ∧ (y s z)).

Nos dois casos, obtemos x (r ∪ s) z, pois tran(r) ∧ tran(s). �

Proposicao 6.8 S ` ((r ⊆ s)∧ (s ⊆ (a×a))∧ ose(r, a)∧ ose(s, a)) → (r = s).

Demonstracao: Suponha que x s y mas ¬(x r y). Como asim(s), entaox 6= y, donde y r x, pois con(r, a). Portanto y s x, pois r ⊆ s, o que contradizasim(s). �

O significado da proposicao precedente e o seguinte: uma ordem simples estritaem a ordena todos os elementos de a numa ordem estrita, isto e: x 6< x paratodo x ∈ a. Portanto, se r, s sao duas ordens estritas simples em a tal que sestende r, entao elas devem necessariamente coincidir, pois r ja ordenou todosos elementos de a.

Introduziremos agora a importante nocao de boa ordem. Uma boa ordemem a e uma ordem simples estrita r tal que todo subconjunto nao vazio de atem um elemento mınimo segundo r. De fato, a conectividade de r implicara atransitividade e asimetria de r. Antes da definicao, analizaremos alguns exem-plos.

Exemplos 6.9 (a) O conjunto N dos numeros naturais e bem ordenado pelarelacao < usual (menor que). De fato, ∅ 6= A ⊆ N possui um elemento mınimo.(b) N nao e bem ordenado pela ordem simples estrita > (maior que). Comefeito, ∅ 6= A ⊆ N tem elemento mınimo com relacao a > significa que existen ∈ A tal que n > m para todo m ∈ A. Em particular, o proprio N deveria terum primeiro elemento relativo a >, isto e, deveria existir n ∈ N tal que n > mpara todo m ∈ N; mas isto nao e verdade (n 6> n+ 1).(c) Considere A = {(n − 1)/n : n ∈ N ∧ n 6= 0} ∪ {1} ordenado pela relacao< usual (em Q, o conjunto dos numeros racionais). Logo, A e bem ordenado.Com efeito,

(n− 1)/n < (m− 1)/m sse m(n− 1) < n(m− 1) sse

mn−m < nm− n sse −m < −n sse n < m.

22

Portanto, ∅ 6= B ⊆ A tem primeiro elemento (n − 1)/n, onde n e o mınimo mtal que (m− 1)/m ∈ B. Se B = {1}, entao claramente 1 e o primeiro elementode B.(d) Seja A como no item (c). Logo, > (a ordem maior que de Q) nao e umaboa ordem em A, pois B = A − {1} nao tem primeiro elemento. Com efeito,se x = (n− 1)/n fosse mınimo, entao (n− 1)/n > n/(n+ 1) donde n > n+ 1,uma contradicao. �

Definicao 6.10 Definimos o seguinte:(a) min(x, r, a) denota x ∈ a ∧ (∀y)(y ∈ a→ ¬(y r x)) (x e um elementor-minimal de a).(b) pe(x, r, a) denota x ∈ a∧ (∀y)((y ∈ a∧ x 6= y) → x r y) (x e um r-primeiroelemento de a).(c) bo(r, a) denota con(r, a)∧ (∀b)((b ⊆ a∧ b 6= ∅) → (∃x)min(x, r, b)) (r e umaboa ordem em a).

Observacao 6.11 Um elemento minimal nao tem antecessores, enquanto queum primeiro elemento precede todo outro elemento diferente dele mesmo. Se re asimetrica, entao todo primeiro elemento e minimal. Com efeito, seja x ∈ aprimeiro elemento de r. Se y ∈ a, entao ¬(y r x) se y = x, pois r e irreflexiva.Se y 6= x, entao x r y, pois x e primeiro elemento. Logo ¬(y r x), pois r easimetrica, e entao x e minimal. Observe que r = {〈1, 1〉} em a = {1} temtrivialmente 1 como primeiro elemento, mas 1 nao e minimal, pois 1 r 1; vemosque a hipotese de asimetria e fundamental. A recıproca nao vale em geral: 1e minimal em r = {〈1, 2〉} sobre a = {1, 2, 3}, mas 1 nao e primeiro elemento,pois ¬(1 r 3). Se r e conectada e asimetrica, as duas nocoes coincidem. Comefeito, se x e minimal e y 6= x, entao ¬(y r x), pois x e minimal. Mas r econectada, portanto x r y. Daqui x e primeiro elemento. �

Proposicao 6.12 S ` bo(r, a) → (asim(r, a) ∧ tran(r, a)).

Demonstracao: Sejam x, y ∈ a tais que x r y, y r x. Logo, {x, y} nao temelemento minimal. Com efeito, y nao e minimal, pois x r y. Analogamente,y r x implica que x nao e minimal; isto contraria o fato de r ser uma boaordem. Portanto, r deve ser asimetrica. Sejam agora x, y, z ∈ a tais que x ry, y r z, ¬(x r z). Como r e asimetrica, entao x 6= z. Logo, z r x, pois r econectada. Mas entao {x, y, z} nao tem elemento minimal: x r y implica que ynao e minimal; y r z implica que z nao e minimal. Finalmente, z r x implicaque x nao pode ser minimal. Daqui, inferimos que r e transitiva. �

Proposicao 6.13(a) ` bo(r, a) ↔ (asim(r, a) ∧ con(r, a) ∧ (∀b)(b 6= ∅ ∧ b ⊆ a→ (∃x)pe(x, r, b))).(b) ` bo(r, a) ∧ a 6= ∅ → (∃!x)pe(x, r, a). Aqui, a notacao (∃!x)ϕ(x) indica:

(∃x)(ϕ(x) ∧ (∀y)(ϕ(y) → (y = x))) (“existe um unico x tal que ϕ(x)”).(c) ` bo(r, a) ∧ b ⊆ a→ bo(r, b).

23

Demonstracao: (a) Assuma bo(r, a); pela Proposicao 6.12, obtemos asim(r, a).Claro que con(r, a), pela definicao de boa ordem. Se ∅ 6= b ⊆ a, entao existex ∈ b tal que min(x, r, b). Pela Observacao 6.11, pe(x, r, b). Reciprocamente,suponha que (∀b)(b 6= ∅ ∧ b ⊆ a→ (∃x)pe(x, r, b)), asim(r, a) e con(r, a). Logo,con(r, a). Dado ∅ 6= b ⊆ a, seja x ∈ b tal que pe(x, r, b). Pela Observacao 6.11obtemos min(x, r, b), pois asim(r, a).(b) Se ∅ 6= a, entao, de a ⊆ a, obtemos (∃x)pe(x, r, a), pelo item (a). Sejamx, y ∈ a tais que pe(x, r, a), pe(y, r, a). Se x 6= y, entao x r y, y r x. Masasim(r, a), pela Proposicao 6.12. Logo x = y.(c) Suponha que bo(r, a) e b ⊆ a. E claro que con(r, b). Se ∅ 6= c ⊆ b, entao∅ 6= c ⊆ a, donde min(x, r, c) para algum x ∈ c. Portanto bo(r, b). �

Definicao 6.14 si(y, x, r) denota (x r y) ∧ (∀z)((x r z) → (z = y ∨ (y r z)))(“y e um r-sucessor imediato de x”).ue(x, r, a) denota (x ∈ a) ∧ (∀y)(((y ∈ a) ∧ y 6= x) → y r x) (“x e um r-ultimoelemento de a”).

Proposicao 6.15 S ` pe(x, r, a) ↔ ue(x, r−1, a).

Demonstracao: Imediata. �

Proposicao 6.16 S ` (bo(r, a) ∧ (F (r) ⊆ a) ∧ (x ∈ a) ∧ ¬ue(x, r, a))→ (∃!y)si(y, x, r).

Demonstracao: Por [A2] podemos formar b = {y : y ∈ F (r)∧(x r y)}. Dadoque F (r) ⊆ a, entao obtemos que b = {y : x r y} ⊆ a. Pela Proposicao 6.13(c),temos que bo(r, b). Como x nao e um ultimo r-elemento de a, entao b 6= ∅.Portanto, existe um unico r-primeiro elemento y de b, pela Proposicao 6.13(b).Temos que x r y, pois y ∈ b. Por outro lado, se (x r z) e z 6= y, entao y r z, peladefinicao de b e a definicao de primeiro elemento. Portanto, y e um r-sucessorimediato de x. Por outro lado, z e um r-sucessor imediato de x sse z e umprimeiro elemento de b. Portanto, y e unico. �

7 Relacoes de Equivalencia

As relacoes de equivalencia sao utilizadas com frequencia na Matematica. Saorelacoes reflexivas, simetricas e transitivas. Dois exemplos basicos sao a relacaode identidade e a relacao de paralelismo entre retas. Como veremos depois,uma relacao de equivalencia num conjunto a classifica os seus elementos deacordo com algum criterio. Esta e uma ferramenta muito util nas construcoesmatematicas, pois permite simplificar os domınios, analizando as classes dosobjetos no lugar dos proprios objetos. Os objetos pertencentes a uma mesmaclasse sao considerados identicos.

Definicao 7.1 equiv(r) denota rel(r) ∧ ref(r) ∧ sim(r) ∧ tran(r) (“r e umarelacao de equivalencia”).equiv(r, a) denota a = F (r) ∧ equiv(r) (“r e uma relacao de equivalencia ema”).

24

Proposicao 7.2 (a) S ` equiv(r) → (r ◦ r−1 = r).(b) S ` qo(r) → equiv(r−1 ∩ r).

Demonstracao: (a) Se x (r ◦ r−1) y entao existe z tal que x r z, z r−1 y.Daqui obtemos y r z e entao z r y, pois sim(r), donde x r y, pois tran(r). Istoe, r◦r−1 ⊆ r. Por outro lado, x r y implica (x r y)∧(y r−1 y), donde x (r◦r−1)y. Portanto r = r ◦ r−1.(b) E imediato que r−1 ∩ r = {〈x, y〉 : (x r y) ∧ (y r x)}. Daqui o resultado etrivial. �

Definicao 7.3 r[x] = {y : x r y}.

Dado que r[x] = {y : y ∈ F (r)∧ (x r y)}, entao r[x] e legitimado. E imediatoque r[x] = r“{x}. A notacao usual em Matematicas para r[x] e simplesmente[x], isto e, r e subentendida.

Proposicao 7.4 S ` (x, y ∈ F (r) ∧ equiv(r)) → (r[x] = r[y] ↔ (x r y)).

Demonstracao: Assuma r[x] = r[y], isto e, (x r z) ↔ (y r z). Como y r y,entao x r y. Suponha agora x r y, e seja z tal que x r z. De sim(r) obtemosy r x, e entao inferimos: (y r x), (x r z) implica y r z, pois tran(r). De x r yprovamos analogamente (y r z) → (x r z). Isto e, r[x] = r[y]. �

Proposicao 7.5 S ` equiv(r) → (r[x] = r[y] ∨ (r[x] ∩ r[y] = ∅)).

Demonstracao: Suponha que r[x] 6= r[y]; se x 6∈ F (r) ou y 6∈ F (r) entaoclaramente r[x] ∩ r[y] = ∅. Se x, y ∈ F (r), entao seja z ∈ r[x] ∩ r[y]. Logo(x r z) e (y r z), donde obtemos x r y e posteriormente, pela Proposicao 7.4,r[x] = r[y], uma contradicao . Portanto, r[x] ∩ r[y] = ∅. �

Veremos a continuacao a estreita relacao entre particoes e relacoes de equiva-lencia.

Definicao 7.6 par(Π, a) denota

(⋃

Π = a) ∧ (∀b)(∀c)(((b ∈ Π) ∧ (c ∈ Π) ∧ b 6= c) → b ∩ c = ∅)∧∧(∀x)(x ∈ Π → (∃y)(y ∈ x))

(“Π e uma particao de a”).

Por exemplo, se a = {1, 2, 3, 4, 5}, entao Π = {{1, 4}, {2}, {3, 5}} e uma particaode a, enquanto que

Π1 = {{1}, {2, 3, 4}}, Π2 = {{1, 2}, {2, 3}, {4}, {5}}

nao sao particoes de a (porque?). Observe que ∅ e a unica particao possıvel doconjunto ∅.

Proposicao 7.7 S ` a 6= ∅ → par({a}, a).

25

Demonstracao: Temos que⋃{a} = a. Dado que nao existem b, c ∈ {a}

com b 6= c, entao a segunda condicao de par(Π, a) e trivialmente satisfeita.Finalmente, seja x ∈ {a}; e claro que x = a. Dado que a 6= ∅, entao existey ∈ a, e a terceira condicao de par(Π, a) e satisfeita por Π = {a}. �

Um conceito importante entre particoes e a relacao mais fina que. Intuitiva-mente, uma particao Π1 e mais fina que Π2 se todo elemento de Π1 esta contidoem algum elemento de Π2, e dai a denominacao mais fina resulta obvia. Porexemplo, considere as seguintes particoes de a = {1, 2, 3, 4, 5}:

Π1 = {{1}, {2, 3}, {4, 5}}, Π2 = {{1}, {2, 3}, {4}, {5}},

Π3 = {{1}, {2}, {3}, {4}, {5}}, Π4 = {{1, 2, 3}, {4}, {5}}.

E imediato que Π2 e mais fina que Π1 e Π4, enquanto que Π3 e mais fina do queas outras particoes. Por outro lado, Π1 e Π4 nao sao comparaveis pela relacao“mais fina que”.

Definicao 7.8 mf(Π1,Π2) denota Π1 6= Π2 ∧ (∀x)(x ∈ Π1 → (∃y)((y ∈ Π2) ∧(x ⊆ y))) (“a particao Π1 e mais fina do que a particao Π2”).

Proposicao 7.9 Todo conjunto tem uma particao mais fina do que todas asoutras particoes do conjunto.

Demonstracao: Seja Π = {y : y ∈ P(a) ∧ (∃x)((x ∈ a) ∧ y = {x})}.Temos que Π e legitimado por [A2], e podemos escrever Π = {{x} : x ∈ a}.Provaremos par(Π, a). Primeiro de tudo, temos

⋃Π = a. Com efeito, seja

x ∈⋃

Π; logo, existe y ∈ Π tal que x ∈ y. Mas y = {z} com z ∈ a, peladefinicao de Π. Daqui, x ∈ y, y = {z} implica x = z e logo x ∈ a. Isto e,⋃

Π ⊆ a. Por outro lado, seja x ∈ a; logo y = {x} ∈ Π tal que x ∈ y, dondex ∈

⋃Π, isto e, a =

⋃Π. Sejam b, c ∈ Π com b 6= c. Logo b = {x}, c = {y}

tal que x, y ∈ a. Portanto, b 6= c implica x 6= y, e entao b ∩ c = ∅. Finalmente,b ∈ Π implica que b = {x} para algum x ∈ a; daqui x ∈ b e logo (∃z)(z ∈ b).Isto prova que par(Π, a). Suponha agora que par(Π1, a) e Π1 6= Π. Seja y ∈ Π;logo y = {x} com x ∈ a. Como

⋃Π1 = a, entao existe z ∈ Π1 tal que x ∈ z,

donde y = {x} ⊆ z, isto e, mf(Π,Π1). �

Vemos entao que Π3 no exemplo acima e de fato a particao mais fina sobre a.Provaremos a continuacao que toda relacao de equivalencia sobre um con-

junto a origina uma particao sobre a.

Definicao 7.10 Π(r) = {b : (∃x)(x ∈ F (r) ∧ b = r[x])}.

E imediato que Π(r) = {b : (b ∈ P(F (r))) ∧ (∃x)(x ∈ F (r) ∧ b = r[x])},portanto Π(r) e legitimado por [A2]. O resultado procurado e o seguinte:

Proposicao 7.11 S ` equiv(r, a) → par(Π(r), a).

26

Demonstracao: Temos que equiv(r, a) implica equiv(r)∧(a = F (r)). Podemosescrever Π(r) = {r[x] : x ∈ a}. Seja y ∈

⋃Π(r); logo existe x ∈ a tal que

y ∈ r[x], donde x r y, isto e, y ∈ a. Daqui⋃

Π(r) ⊆ a. Por outro lado, sejax ∈ a. Logo (x ∈ r[x]) ∧ (r[x] ∈ Π(r)), donde x ∈

⋃Π(r). Isto e,

⋃Π(r) = a.

Sejam r[x], r[y] ∈ Π(r). Se r[x] 6= r[y] entao r[x]∩r[y] = ∅, pela Proposicao 7.5.Finalmente, dado r[x] ∈ Π(r), temos que x ∈ r[x], isto e, (∃y)(y ∈ r[x]),provando assim que par(Π(r), a). �

Podemos relacionar a inclusao de relacoes de equivalencia com a relacao “maisfina que” das particoes associadas.

Proposicao 7.12 S ` (equiv(r, a)∧ equiv(s, a)) → (r ⊂ s↔mf(Π(r),Π(s)).

Demonstracao: Assuma equiv(r, a)∧equiv(s, a). Suponha r ⊂ s; como r 6= s,existem x, y ∈ a tais que x s y mas ¬(x r y). Desta maneira, y ∈ s[x] − r[x]e entao r[x] 6= s[x]. Seja z ∈ r[x]; portanto x r z, donde x s z, pois r ⊂ s.Daqui z ∈ s[x], e entao r[x] ⊂ s[x]. Assim r[x] 6= s[w] para todo w ∈ a, poispar(Π(s), a). Daqui r[x] ∈ Π(r) − Π(s) e entao Π(r) 6= Π(s). Seja y ∈ Π(r);logo y = r[x] para algum x ∈ a, e entao r[x] ⊆ s[x], com s[x] ∈ Π(s), poisr ⊂ s. Isto e, mf(Π(r),Π(s)). Reciprocamente, suponha mf(Π(r),Π(s)). LogoΠ(r) 6= Π(s). Se x r y entao y ∈ r[x]; mas r[x] ⊆ s[z] para algum z, dondey ∈ s[z], isto e, y s z. Mas x ∈ r[x] ⊆ s[z], portanto x ∈ s[z], donde x s z. Dey s z obtemos z s y e entao x s y; logo r ⊆ s. Finalmente, suponha que r = s.Logo, r[x] = s[x] para todo x ∈ a, donde Π(r) = Π(s), contradicao. Portantor ⊂ s. �

Provaremos agora que uma particao origina uma relacao de equivalencia.

Definicao 7.13 r(Π) = {〈x, y〉 : (∃b)((b ∈ Π) ∧ x, y ∈ b)}.

E imediato que r(Π) e legitimado, pois

r(Π) = {z : z ∈ (⋃

Π)×(⋃

Π)∧(∃x)(∃y)(z = 〈x, y〉∧(∃b)((b ∈ Π)∧x, y ∈ b))}.

Proposicao 7.14 S ` par(Π, a) → equiv(r(Π), a).

Demonstracao: E imediato que par(Π, a) implica F (r(Π)) = a. Se x ∈ a,entao existe b ∈ Π tal que x ∈ b; daqui x r(Π) x, isto e, ref(r(Π), a) . A provada simetria de r(Π) e imediata. Sejam x, y ∈ a tais que x r(Π) y, y r(Π) z; entaox, y ∈ b e y, z ∈ c para b, c ∈ Π. Logo y ∈ b ∩ c, donde b = c. Daqui x, z ∈ c,c ∈ Π, e entao x r(Π) z. Isto e, tran(r(Π), a), portanto equiv(r(Π), a). �

Vamos agora relacionar particoes com relacoes de equivalencia. Provaremosque, partindo de uma relacao de equivalencia r, entao a particao Π(r) e tal quea relacao de equivalencia gerada, r(Π(r)), coincide com r. Analogamente, arelacao r(Π) gerada por uma particao Π e tal que Π(r(Π)) = Π.

Proposicao 7.15 S ` (par(Π, a) ∧ equiv(r, a)) → (Π = Π(r) ↔ r(Π) = r).

27

Demonstracao: Assuma par(Π, a) ∧ equiv(r, a). Suponha Π = Π(r). Deequiv(r, a) obtemos x r y sse (∃z)(x, y ∈ r[z]). Mas b ∈ Π sse (∃z)(b = r[z]),por hipotese. Logo

x r y sse (∃b)(x, y ∈ b ∧ b ∈ Π) sse x r(Π) y,

isto e, r = r(Π). Reciprocamente, suponha r = r(Π). Se b ∈ Π, entao existex ∈ a tal que x ∈ b. Portanto y ∈ b sse x r(Π) y sse x r y sse y ∈ r[x].Daqui b = r[x] ∈ Π(r). Por outro lado, seja r[x] ∈ Π(r). Como x ∈ a, entaoexiste b ∈ Π tal que x ∈ b. Portanto b = r[x], como acabamos de provar. Logor[x] ∈ Π. Isto e, Π = Π(r). �

Finalmente provaremos que a relacao “mais fina que” e de fato uma ordemparcial estrita. Considere PAR(a) = {Π : par(Π, a)}. Temos que PAR(a) elegitimado, pois

PAR(a) = {Π : Π ∈ PP(a) ∧ par(Π, a)}

Considere agora

<a= {u : u ∈ PAR(a)× PAR(a) ∧ (∃Π1)(∃Π2)(u = 〈Π1,Π2〉 ∧mf(Π1,Π2)}

Temos que <a e legitimado por [A2], e Π1 <a Π2 sse mf(Π1,Π2) para todaΠ1,Π2 ∈ PAR(a).

Proposicao 7.16 (a) S ` (Π1 <a Π2) ↔ (r(Π1) ⊂ r(Π2)).(b) S ` ope(<a, PAR(a)).

Demonstracao: (a) Sejam Π1,Π2 ∈ PAR(a). Logo,

Π1 <a Π2 sse mf(Π1,Π2) sse

mf(Π(r(Π1)),Π(r(Π2))) ∧ equiv(r(Π1), a) ∧ equiv(r(Π2), a)(por 7.14, 7.11, 7.15) sse

r(Π1) ⊂ r(Π2) (por 7.12).

(b) Sejam Π1,Π2 ∈ PAR(a) tais que Π1 <a Π2; por (a) temos que r(Π1) ⊂r(Π2). Se Π2 <a Π1 entao r(Π2) ⊂ r(Π1), uma contradicao. Logo, <a easimetrica. Se Π1 <a Π2, Π2 <a Π3, entao r(Π1) ⊂ r(Π2) e r(Π2) ⊂ r(Π3),donde r(Π1) ⊂ r(Π3). Portanto Π1 <a Π3, por (a). Isto e, <a e uma ordemparcial estrita em PAR(a). �

Exemplo 7.17 Fixemos k ∈ Z, onde Z denota o conjunto dos numeros inteiros.Definimos em Z a relacao seguinte:

nRkm sse k|(n−m) sse existe z ∈ Z tal que n−m = z.k .

28

Observe que n Rk m sse n e m tem o mesmo resto na divisao por k. Com efeito,assumamos que n Rk m; logo, n − m = z.k. Por outro lado, n = z1.k + r1,m = z2.k + r2, onde 0 ≤ r1, r2 < k. Se r1 ≥ r2, entao

n−m = (z1.k + r1)− (z2.k + r2) = (z1 − z2).k + (r1 − r2) = z.k

onde 0 ≤ r1 − r2 < k. Pela unicidade do algoritmo da divisao, temos quer1 − r2 = 0, donde r1 = r2. Analogamente, se r1 ≤ r2, entao

m− n = (z2.k + r2)− (z1.k + r1) = (z2 − z1).k + (r2 − r1) = (−z).k

onde 0 ≤ r2 − r1 < k. Pela unicidade do algoritmo da divisao, temos quer2 − r1 = 0, donde r1 = r2. Reciprocamente, se n e m tem o mesmo resto nadivisao por k, entao n = z1.k+ r1, m = z2.k+ r1, portanto n−m = (z1− z2).k,donde k|(n−m), isto e, n Rk m. Provaremos a seguir que Rk e uma relacao deequivalencia (observe que F (Rk) = Z).

Se n ∈ Z, entao n − n = 0 = 0.k, donde n Rk n, isto e, Rk e reflexiva.Se n Rk m, entao n −m = z.k, donde m − n = (−z).k, com −z ∈ Z; isto e,m Rk n. Finalmente, assumamos que n Rk m, m Rk w. Logo, n −m = z1.k,m−w = z2.k, donde n−w = (n−m)+(m−w) = z1.k+z2.k = (z1 +z2).k, comz1 + z2 ∈ Z. Daqui n Rk w, e Rk e uma relacao de equivalencia. O conjuntoΠ(Rk) e usualmente denotado por Zk. Observe que Rk = R−k para todo k ∈ Z.Para ilustrar estas definicoes, considere k = 6; logo, os unicos restos possıveisda divisao de n por 6 sao: 0, 1,. . . , 5. Daqui inferimos que as unicas classesde equivalencia possıveis para R6 sao n ≡def R6[n], com 0 ≤ n ≤ 5, portantoZ6 = {0, . . . , 5}, sendo que, para 0 ≤ n ≤ 5, n e o conjunto dos numeros inteirosm tais que o resto da divisao de m por 6 e n. Analogamente, Z3 = {0, 1, 2},onde agora n = {m : o resto da divisao de m por 3 e n} (n = 0, 1, 2). Observeque, se 6|(n−m), entao 3|(n−m), pois 3|6; daqui, R6 e mais fina do que R3.Dado que 3 = 1.3+0, 4 = 1.3+1, 5 = 1.3+2, entao R6[3] ⊆ R3[0], R6[4] ⊆ R3[1]e R6[5] ⊆ R3[2], donde

R3[0] = R6[0] ∪R6[3], R3[1] = R6[1] ∪R6[4], R3[2] = R6[2] ∪R6[5].

Em geral, Rm e mais fina do que Rn sse n|m. Temos portanto que R0 produz aparticao mais fina de Z, pois m|0 para todo m. Para verificar isto diretamente,observe que n R0 m sse n − m = z.0 = 0 sse n = m, donde R0[n] = {n}para todo n ∈ Z. Por outro lado, R1 produz a particao menos fina {Z}. Comefeito, 1|n para todo n, donde Rn e mais fina do que R1. E claro que n R1

m sse 1|(n −m), condicao que resulta verdadeira para todo n,m ∈ Z, e entaoR1[0] = Z. �

8 Funcoes

O importante conceito de funcao, cuja definicao foi discutida ate finais do seculo19, pode ser introduzido elegantemente na linguagem da TC. Informalmente,uma funcao e uma relacao em que cada elemento do domınio tem associadoum unico elemento na imagem; isto nao proibe, e claro, que dois elementosdiferentes do domınio possam ter associados o mesmo elemento na imagem.

29

Definicao 8.1 fun(f) denota rel(f)∧ (∀x)(∀y)(∀z)(((x f y)∧ (x f z)) → y =z) (“f e uma funcao”).

E claro que fun(f) equivale a: rel(f) ∧ (∀x)(x ∈ dom(f) → (∃!y)(x f y)).Usaremos a notacao f(x) para indicar o unico y tal que x f y. Por exemplo, sef = {〈1, 2〉, 〈2, 2〉, 〈3, 5〉}, entao f(1) = 2, f(2) = 2, f(3) = 5. A notacao f(x)(introduzida na Definicao 5.1) e legitimada pela Proposicao 5.3. A composicaof • g de duas funcoes f , g e definida de maneira que (f • g)(x) = f(g(x)).Isto significa que f • g e a composicao (como relacoes) g ◦ f introduzida naDefinicao 5.6.

Lema 8.2 (a) S ` fun(f) → (∀x)(∀y)((x f y) → y = f(x)).(b) S ` (fun(f) ∧ x ∈ dom(f)) → (x f f(x)).

Demonstracao: (a) Assuma fun(f). Se x f y, provaremos:

z ∈ y↔ (∃u)((∀w)((x f w) ↔ w = u) ∧ z ∈ u)

(lembrando que a formula a direita do primeiro “ ↔ ” significa “z ∈ f(x)”).Daqui, teremos, por [A1], que y = f(x). Com efeito, temos o seguinte:fun(f), x f y, x f w implica w = y; x f y, w = y implica x f w, portantofun(f), x f y implica (∀w)(x f w↔ w = y), donde fun(f), x f y, z ∈ y implica(∀w)(x f w↔ w = y)∧z ∈ y. Daqui obtemos (∃u)((∀w)((x f w) ↔ w = u)∧z ∈u), isto e: fun(f), x f y implica z ∈ y→ z ∈ f(x).Por outro lado, x f y, (∀w)((x f w) ↔ w = u) implica (x f y)∧ (x f u), donde,usando fun(f), obtemos y = u. Daqui, provamos: fun(f), x f y, z ∈ f(x)implica z ∈ y, isto e: fun(f), x f y implica z ∈ f(x) → z ∈ y, portanto fun(f),x f y implica y = f(x).(b) Assuma fun(f) ∧ x ∈ dom(f). Provaremos que x f f(x). Com efeito,fun(f), x f u implica u = f(x), por (a). Logo, fun(f), x f u implica x ff(x). Portanto fun(f), (∃u)(x f u) implica x f f(x). Mas x ∈ dom(f) implica(∃u)(x f u), portanto: fun(f), x ∈ dom(f) implica x f f(x). �

Proposicao 8.3 (a) S ` (fun(f)∧ fun(g)) → ((x (g ◦ f) y) → y = f(g(x))).(b) S ` (fun(f)∧fun(g)∧x ∈ dom(g)∧g(x) ∈ dom(f)) → (x (g◦f) f(g(x))).

Demonstracao: (a) Se x (g ◦ f) y, entao x g z, z f y para algum z. PeloLema 8.2(a) obtemos z = g(x) e y = f(z), donde y = f(g(x)), pelas regras daigualdade.(b) Pelo Lema 8.2(b), temos que g(x) f f(g(x)), pois g(x) ∈ dom(f). Comox ∈ dom(g), entao x g g(x), novamente por 8.2(b). Daqui obtemos: x g g(x),g(x) f f(g(x)), e entao x (g ◦ f) f(g(x)), pela Definicao 5.6. �

Vemos assim que f • g ≡def g ◦ f satisfaz a propriedade desejada x (f • g) y ssey = f(g(x)) (sob certas condicoes razoaveis estabelecidas na Proposicao 8.3(b)).Uma propriedade fundamental e que a composicao de funcoes e uma funcao.

Proposicao 8.4 (a) S ` (fun(f) ∧ fun(g)) → (fun(f ∩ g) ∧ fun(f • g)).(b) S ` (fun(f) ∧ fun(g) ∧ x ∈ dom(f • g)) → (f • g)(x) = f(g(x)).

30

Demonstracao: (a) Sejam x, y, z tais que , x (f ∩ g) y, x (f ∩ g) z. Daquiobtemos x f y, x g y, x f z, x g z. Como fun(f), fun(g), entao y = z,donde fun(f ∩ g). Por outro lado, suponha que x (f • g) y, x (f • g) z. PelaProposicao 8.3(a) obtemos y = f(g(x)), z = f(g(x)), donde y = z e entaofun(f • g).(b) Assuma fun(f), fun(g), x ∈ dom(f • g). Pelo item (a) obtemos fun(f •g), x ∈ dom(f • g), donde x (f • g) ((f • g)(x)), pelo Lema 8.2(b). PelaProposicao 8.3(a) obtemos (f • g)(x) = f(g(x)). �

Daqui em diante, quando nao houver risco de confusao, escreveremos f ◦ g nolugar de f • g, se f e g sao funcoes. Algumas das propriedades provadas naProposicao 5.10 podem ser fortalecidas, no caso em que f e funcao.

Proposicao 8.5 (a) S ` (f • g)|z = f • (g|z).(b) S ` fun(f) → (f−1“(a∩b) = f−1“(a)∩f−1“(b))∧(f−1“(a−b) = f−1“(a)−f−1“(b)).

Demonstracao: (a) E uma reformulacao da Proposicao 5.9(e).(b) Assuma fun(f). Pela Proposicao 5.10(b),(c), basta provar

f−1“(a) ∩ f−1“(b) ⊆ f−1“(a ∩ b),

e f−1“(a− b) ⊆ f−1“(a)− f−1“(b).Se x ∈ f−1“(a) ∩ f−1“(b), entao existem y ∈ a, w ∈ b tais que x f y, x fw. Como fun(a), entao y = w, portanto y ∈ a ∩ b tal que x f y, dondex ∈ f−1“(a ∩ b).Seja agora x ∈ f−1“(a − b). Logo, existe y ∈ a − b tal que x f y, e entaox ∈ f−1“(a). Se x ∈ f−1“(b), entao existe z ∈ b tal que x f z. Como fun(f),obtemos y = z donde y ∈ b, uma contradicao. Portanto x ∈ f−1“(a)− f−1“(b).

�

Definicao 8.6 inj(f) denota fun(f) ∧ fun(f−1) (“f e injetora”).

Proposicao 8.7 (a) S ` (inj(f) ∧ x, y ∈ dom(f)) → (f(x) = f(y) ↔ x = y).(b) S ` (inj(f) ∧ x ∈ dom(f) ∧ y ∈ im(f)) → (f−1(y) = x↔ y = f(x)).(c) S ` (inj(f) ∧ x ∈ dom(f)) → f−1(f(x)) = x.(d) S ` (inj(f) ∧ y ∈ im(f)) → f(f−1(y)) = y.(e) S ` (inj(f) ∧ inj(g)) → inj(f ∩ g).(f) S ` (inj(f) ∧ inj(g) ∧ dom(f) ∩ dom(g) = ∅ ∧ im(f) ∩ im(g) = ∅)

→ inj(f ∪ g).

Demonstracao: (a) Assuma inj(f) ∧ x ∈ dom(f) ∧ y ∈ dom(f). Se f(x) =f(y), entao obtemos que f(x) f−1 x, f(x) f−1 y. Mas fun(f−1), portantox = y. Reciprocamente, x = y implica f(x) = f(y), pelas regras da igualdade.(b) Assuma inj(f)∧x ∈ dom(f)∧y ∈ im(f). Como fun(f−1)∧y ∈ dom(f−1),entao x = f−1(y) implica y f−1 x, pelo Lema 8.2(b). Daqui, x f y e entao, peloLema 8.2(a), obtemos y = f(x); isto e, x = f−1(y) → y = f(x). Simetricamenteprovamos y = f(x) → x = f−1(y).

31

(c) Assuma inj(f) ∧ x ∈ dom(f). Logo f(x) ∈ im(f) e f(x) = f(x). Pelo item(b) obtemos x = f−1(f(x)).(d) Analogo ao item (c).(e) Imediato a partir da Proposicao 8.4 (a).(f) x (f ∪g) y, x (f ∪g) z implica que (x f y)∧ (x f z) ou (x g y)∧ (x g z), masnao ambas simultaneamente. Daqui y = z, e fun(f ∪ g). Da mesma maneira(lembrando que (f ∪ g)−1 = f−1 ∪ g−1), x (f ∪ g)−1 y, x (f ∪ g)−1 z implica (xf−1 y) ∧ (x f−1 z) ou (x g−1 y) ∧ (x g−1 z), mas nao ambas simultaneamente.Daqui y = z, e fun((f ∪ g)−1). Portanto inj(f ∪ g). �

Definicao 8.8 (a) fun(f, a, b) denota fun(f) ∧ (dom(f) = a) ∧ (im(f) ⊆ b)(“f e uma funcao de a em b”).(b) sobre(f, a, b) denota fun(f)∧(dom(f) = a)∧(im(f) = b) (“f e uma funcaosobrejetora de a em b”).(c) inj(f, a, b) denota inj(f) ∧ (dom(f) = a) ∧ (im(f) ⊆ b) (“f e uma funcaoinjetora de a em b”).(d) bij(f, a, b) denota inj(f, a, b) ∧ sobre(f, a, b) (“f e uma funcao bijetora dea em b”).(e) ab = {f : fun(f, b, a)} (“ab e o conjunto de todas as funcoes de b em a”).

Observacao 8.9 Podemos a partir de agora utilizar a notacao usual f : a−→bpara denotar fun(f, a, b). De fato, utilizaremos as duas notacoes indistinta-mente. �

Proposicao 8.10 (a) S ` (fun(f, a, b) ∧ fun(g, b, c)) → fun(g ◦ f, a, c).(b) S ` inj(f, a, b) → (bij(f, a, im(f)) ∧ bij(f−1, im(f), a)).(c) S ` bij(f, a, b) → bij(f−1, b, a).(d) S ` (bij(f, a, b) ∧ bij(g, b, c)) → bij(g ◦ f, a, c).(e) S ` bij(f, a, b) → ((f ◦ f−1 = I(b)) ∧ (f−1 ◦ f = I(a))).(f) S ` fun(f, a, b) → ((I(b) ◦ f = f) ∧ (f ◦ I(a) = f)).

Demonstracao: (a) Notar que g ◦ f e utilizado para denotar g • f , isto e, f ◦ g(como relacoes). Assuma entao f : a−→b, g : b−→c. Daqui obtemos:

fun(f), dom(f) = a, im(f) ⊆ b, fun(g), dom(g) = b, im(g) ⊆ c.

Pela Proposicao 8.4(a) obtemos fun(g ◦ f). Por definicao de composicao,dom(g ◦ f) ⊆ dom(f), im(g ◦ f) ⊆ im(g); isto e, dom(g ◦ f) ⊆ a, im(g ◦ f) ⊆ c.Seja x ∈ a; pela Proposicao 8.3(b) temos que x (g◦f) (g(f(x)), pois a = dom(f)e b = dom(g), donde x ∈ dom(f) ∧ f(x) ∈ dom(g). Daqui x ∈ dom(g ◦ f), istoe, dom(g ◦ f) = a. Portanto fun(g ◦ f, a, c).(b) Observe que dom(f−1) = im(f), im(f−1) = dom(f). Assuma inj(f, a, b).Logo, temos o seguinte:

fun(f), fun(f−1), dom(f−1) = im(f), im(f−1) = a.

Daqui obtemos imediatamente inj(f−1, im(f), a), sobre(f−1, im(f), a), isto e,bij(f−1, im(f), a). A formula bij(f, a, im(f)) e obtida trivialmente.

32

(c) Por (b) inferimos bij(f, a, b) → bij(f−1, b, a), pois im(f) = b.(d) Assuma bij(f, a, b), bij(g, b, c). Daqui obtemos:

fun(f, a, b), fun(f−1, b, a), fun(g, b, c), fun(g−1, c, b).

Por (a) e pela Proposicao 5.8(d) obtemos fun(g ◦ f, a, c), fun((g ◦ f)−1, c, a).Daqui dom(g ◦ f) = a, im(g ◦ f) = c, fun(g ◦ f), fun((g ◦ f)−1), e entaobij(g ◦ f, a, c).(e) Por (a) temos fun(f ◦ f−1, b, b), fun(f−1 ◦ f, a, a). Seja x ∈ b; x f ◦ f−1 yimplica x f−1 z, z f y para algum z ∈ a. Daqui z f x, z f y e entao y = x, istoe: (f ◦ f−1)(x) = x para todo x ∈ b, donde f ◦ f−1 = I(b). Seja agora x ∈ a;x f−1 ◦ f y implica x f z, z f−1 y para algum z ∈ b. Daqui z f−1 x, z f−1 y,donde x = y, isto e: (f−1 ◦f)(x) = x para todo x ∈ a. Portanto f−1 ◦f = I(a).(f) Por (a), fun(I(b) ◦ f, a, b) ∧ fun(f ◦ I(a), a, b). Seja x ∈ a; logo (I(b) ◦f)(x) = I(b)(f(x)) = f(x), donde I(b) ◦ f = f . Por outro lado, (f ◦ I(a))(x) =f(I(a)(x)) = f(x), donde f ◦ I(a) = f . �

Proposicao 8.11 (a) O termo ab e legitimado em S.(b) a∅ = {∅}.(c) a 6= ∅ → ∅a = ∅.(d) ab = ∅ ↔ a = ∅ ∧ b 6= ∅.(e) a{x} = {{〈x, y〉} : y ∈ a}.(f) a ⊆ b→ ac ⊆ bc.

Demonstracao: (a) Claramente ab = {f : f ∈ P(b × a) ∧ fun(f, b, a)},legitimado portanto por [A2].(b) a∅ ⊆ P(∅ × a) = P(∅) = {∅}. Por outro lado fun(∅, ∅, a) e satisfeita tri-vialmente, e entao a∅ = {∅}.(c) Seja a 6= ∅, e suponha que fun(f, a, ∅). Seja x ∈ a; logo, x ∈ dom(f),portanto f(x) ∈ ∅, uma contradicao.(d) Assuma f ∈ ab. Se b 6= ∅, seja x ∈ b; portanto f(x) ∈ a, donde a 6= ∅,provando assim: ab 6= ∅ → (b 6= ∅ → a 6= ∅). Mas b 6= ∅ → a 6= ∅ equivalea ¬(a = ∅ ∧ b 6= ∅). Reciprocamente, suponha ¬(a = ∅ ∧ b 6= ∅), isto e,a 6= ∅ ∨ b = ∅. Se a 6= ∅, seja y ∈ a. Logo, e imediato que f = {〈x, y〉 : x ∈ b}e legitimado, e fun(f, b, a). Daqui ab 6= ∅. Por outro lado, b = ∅ implica queab = {∅} 6= ∅, por (b). Portanto ¬(a = ∅ ∧ b 6= ∅) → ab 6= ∅.(e) Seja b = {{〈x, y〉} : y ∈ a}; e claro que b e legitimado, e b ⊆ a{x}. Sejaf ∈ a{x}; como dom(f) = {x}, entao f(x) ∈ a tal que f = {〈x, f(x)〉}; daquif ∈ b.(f) Imediato das definicoes. �

9 Equipolencia

A nocao de equipolencia foi apontada por Cantor como um conceito fundamen-tal, pois permite generalizar a nocao de numero natural para cardinais. Essen-cialmente, dois conjuntos sao equipolentes se existe uma bijecao entre eles, oque equivale a afirmar que possuem o mesmo cardinal.

33

Definicao 9.1 a ≈ b denota (∃f)bij(f, a, b) (“a e b sao equipolentes”).

Exemplo 9.2 Sejam a = {1, 2, 3}, b = {3, 4, 5}. Entao

f = {〈1, 3〉, 〈2, 4〉, 〈3, 5〉}, g = {〈1, 5〉, 〈2, 4〉, 〈3, 3〉}

sao duas bijecoes entre a e b, cada uma delas garantindo a ≈ b. �

A intuicao por tras de a ≈ b e que “a e b tem o mesmo numero de elementos”,o que pode ser percebido nos exemplos em que a e b sao finitos (todas estas saonocoes por enquanto intuitivas, mas serao formalizadas em ZF ). E tambemclaramente intuitivo que um conjunto finito nao pode ser equipolente com umsubconjunto proprio. No caso de a ser infinito, esta propriedade deixa de serverdadeira: o conjunto P dos numeros naturais pares e um subconjunto propriodo conjunto N dos numeros naturais, embora f(n) = 2.n seja uma bijecao entreN e P. Vemos assim que a parte e menor do que a totalidade nao tem maisvalidade no caso infinito.

Proposicao 9.3 (a) S ` a ≈ a.(b) S ` (a ≈ b) → (b ≈ a).(c) S ` ((a ≈ b) ∧ (b ≈ c)) → (a ≈ c).

Demonstracao: (a) Pode ser provado facilmente que a relacao I(a) intro-duzida previamente a Proposicao 6.2 e uma bijecao entre a e a.(b), (c) Sao consequencias imediatas da Proposicao 8.10(c),(d), respectiva-mente. �

Os seguintes resultados serao uteis para a definicao da artimetica cardinal.

Proposicao 9.4 As seguintes formulas sao teoremas de S:(a) ((a ≈ b) ∧ (c ≈ d) ∧ (a ∩ c = ∅) ∧ (b ∩ d = ∅)) → (a ∪ c ≈ b ∪ d).(b) ((a ≈ b) ∧ (c ≈ d)) → (a× c ≈ b× d).(c) a× b ≈ b× a.(d) a× (b× c) ≈ (a× b)× c.(e) (a× {x} ≈ a) ∧ ({x} × a ≈ a).(f) (∃c)(∃d)((a ≈ c) ∧ (b ≈ d) ∧ (c ∩ d = ∅)).

Demonstracao: (a) Sejam f , g tais que bij(f, a, b), bij(g, c, d). Por hipotesetemos que dom(f) ∩ dom(g) = ∅, im(f) ∩ im(g) = ∅, portanto inj(f ∪ g), pelaProposicao 8.7(f). E imediato provar bij(f ∪ g, a ∪ c, b ∪ d).(b) Sejam f , g tais que bij(f, a, b), bij(g, c, d). E imediato que h ⊆ (a×c)×(b×d)dado por

h = {〈〈x, y〉, 〈f(x), g(y)〉〉 : (x ∈ a) ∧ (y ∈ c)}

e legitimado, estabelecendo uma bijecao h(〈x, y〉) = 〈f(x), g(y)〉 entre a × c eb× d.(c) E imediato que f(〈x, y〉) = 〈y, x〉 e uma bijecao entre a× b e b× a.(d) f(〈x, 〈y, z〉〉) = 〈〈x, y〉, z〉 e uma bijecao entre a× (b× c) e (a× b)× c.

34

(e) f1(〈y, x〉) = y, f2(〈x, y〉) = y sao bijecoes.(f) Sejam c = a × {∅}, d = b × {{∅}}. Logo a ≈ c, b ≈ d, pelo item (e), ec ∩ d = ∅. �

Os seguintes resultados serao utilizados para a exponenciacao cardinal.

Proposicao 9.5 Em S as seguintes formulas sao teoremas:(a) ((a ≈ b) ∧ (c ≈ d)) → (ac ≈ bd).(b) (b ∩ c = ∅) → (ab∪c ≈ ab × ac).(c) (a× b)c ≈ ac × bc.(d) (ab)c ≈ ab×c.

Demonstracao: (a) Se ac = ∅ entao a = ∅ e c 6= ∅, donde b = ∅ e d 6= ∅.Logo bd = ∅ e entao ac ≈ bd. Suponha agora que ac 6= ∅. Sejam f , g tais quebij(f, a, b), bij(g, c, d). Dada h ∈ ac, entao f ◦ h ∈ bc, pela Proposicao 8.10(a).A partir dai, obtemos da mesma maneira f ◦ h ◦ g−1 ∈ bd. Definimos entaouma funcao f ′(h) = f ◦ h ◦ g−1 tal que f ′ : ac−→bd. Dado h′ ∈ bd, entaoh = f−1 ◦ h′ ◦ g e o unico elemento de ac tal que h′ = f ◦ h ◦ g−1 = f ′(h),pela Proposicao 8.10(e),(f). Portanto f ′ e uma bijecao com inversa f ′−1(h′) =f−1 ◦ h′ ◦ g.(b) ab∪c = ∅ implica a = ∅, b ∪ c 6= ∅ implica a = ∅ e: b 6= ∅ ou c 6= ∅ implicaab = ∅ ou ac = ∅ implica ab × ac = ∅. Logo ab∪c ≈ ab × ac. Suponha agora queab∪c 6= ∅. Dado f ∈ ab∪c, entao 〈f |b, f |c〉 ∈ ab × ac. Defina

h = {〈f, 〈f |b, f |c〉〉 : f ∈ ab∪c},

legitimado por [A2]. E claro que h : ab∪c−→ab × ac e uma funcao. Por outrolado, se 〈f1, f2〉 ∈ ab × ac, entao f1 ∪ f2 ∈ ab∪c tal que h(f1 ∪ h2) = 〈f1, f2〉. Seh(f) = 〈f1, f2〉, entao f = f1 ∪ f2, donde h−1 : ab × ac−→ab∪c e uma funcao.Daqui infere-se que bij(h, ab∪c, ab × ac).(c) Se (a × b)c = ∅ entao a × b = ∅ e c 6= ∅, donde a = ∅ ou b = ∅, e c 6= ∅.Daqui ac = ∅ ou bc = ∅ donde ac × bc = ∅, e entao (a× b)c ≈ ac × bc. Suponhaagora que (a× b)c 6= ∅. Dada f ∈ (a× b)c, considere

fa = {〈x, y〉 : (∃z)(〈x, 〈y, z〉〉 ∈ f)}, fb = {〈x, z〉 : (∃y)(〈x, 〈y, z〉〉 ∈ f)}.

Isto e, se π1 ∈ aa×b e π2 ∈ ba×b sao dadas por π1(〈x, y〉) = x e π2(〈x, y〉) = y(as projecoes canonicas), entao fa = π1 ◦ f e fb = π2 ◦ f . E claro que fa ∈ ac,fb ∈ bc, h = {〈f, 〈fa, fb〉〉 : f ∈ (a× b)c} e legitimado, e h : (a× b)c−→ac × bc

e uma funcao. Dada 〈f1, f2〉 ∈ ac × bc, entao f = {〈x, 〈f1(x), f2(x)〉〉 : x ∈ c}e legitimado, f ∈ (a× b)c, e h(f) = 〈f1, f2〉. E claro que h(f ′) = h(f) implicaf = f ′, portanto fun(h−1, ac × bc, (a× b)c) e assim bij(h, (a× b)c, ac × bc).(d) ab×c = ∅ implica a = ∅, b× c 6= ∅ implica a = ∅, b 6= ∅, c 6= ∅ implica ab = ∅,c 6= ∅ implica (ab)c = ∅. Logo (ab)c ≈ ab×c. Suponha agora que ab×c 6= ∅. Sejaf ∈ ab×c. Para cada y ∈ c, seja

fy = {〈x, z〉 : 〈〈x, y〉, z〉 ∈ f}.

E claro que fy e legitimado, fy ∈ ab, e fy(x) = f(〈x, y〉). Alem disso, hf ={〈y, fy〉 : y ∈ c} ∈ (ab)c, onde hf (y) = fy. Portanto h = {〈f, hf 〉 : f ∈ ab×c}

35

e legitimado, e h : ab×c−→(ab)c e uma funcao, onde h(f) = hf . Dada f ′ ∈(ab)c, entao f(〈x, y〉) = f ′(y)(x) e uma funcao, f ∈ ab×c, e h(f) = f ′. Alemdisso, h(f1) = h(f2) implica f1 = f2, portanto fun(h−1, (ab)c, ab×c) e assimbij(h, ab×c, (ab)c). �

Observacao 9.6 Neste ponto da nossa exposicao sobre a Teoria Axiomaticade Conjuntos assumiremos que o leitor ja assimilou o fato de que os enuncia-dos dos teoremas, assim como as respectivas demonstracoes, sao realizados nomarco formal de ZF (ou de certos fragmentos, tais como S). Para simplificara exposicao, a partir daqui os enunciados e demonstracoes dos teoremas de ZFserao feitos numa linguagem coloquial, omitindo os detalhes mais formais. �

Antecipando a definicao de 2 = {∅, {∅}}, provamos o seguinte resultado util,introduzindo a ideia que os subconjuntos de um conjunto a sao as funcoescaracterısticas sobre a.

Proposicao 9.7 Temos que P(a) ≈ 2a.

Demonstracao: Seja b ⊆ a. Definimos a funcao gb : a−→2 pela regra: gb(x) ={∅} se x ∈ b, e gb(x) = ∅ se x 6∈ b. Logo, h(b) = gb define uma funcaoh : P(a)−→2a. Por outro lado, h(b) = h(c) implica gb = gc, isto e, gb(x) = gb(x)para todo x ∈ a. Portanto: gb(x) = {∅} sse gc(x) = {∅}, donde x ∈ b sse x ∈ c.Por [A1] obtemos b = c, e entao h e injetora. Por outro lado, se g ∈ 2a, considereb = {x : x ∈ a ∧ g(x) = {∅}}. Logo b e legitimado por [A2], e claramenteh(b) = g. Daqui h e sobrejetora, e entao h e uma bijecao entre P(a) e 2a. AssimP(a) ≈ 2a. �

Vamos definir a continuacao o conceito de ser menor ou igual em termos detamanho (obviamente estes conceitos sao ainda difusos).

Definicao 9.8 a � b denota (∃c)(c ⊆ b ∧ a ≈ c).

Proposicao 9.9 (a) a ≈ b implica a � b.(b) a ⊆ b implica a � b.(c) a � a ∪ b.(d) a � b e b � c implica a � c.

Demonstracao: (a) Temos que a ≈ c com c = b ⊆ b. Logo a � b.(b) A funcao I(a) produz: a ≈ c com c = a ⊆ b. Logo a � b.(c) E uma consequencia direta de (b).(d) Suponha que a ≈ a1 (via f) com a1 ⊆ b, e b ≈ b1 (via g) com b1 ⊆ c. Logog ◦ f e uma bijecao de a em g“a1 ⊆ c. Daqui a � c. �

O seguinte resultado, cuja demonstracao e mais complicada, foi conjecturadopor Cantor e provado independientemente por Schroder e Bernstein em 1890.A seguinte prova e devida a Fraenkel e Whitaker.

36

Teorema 9.10 (Cantor-Schroder-Bernstein)Se a � b e b � a, entao a ≈ b.

Demonstracao: Seja f uma bijecao de a em b1 ⊆ b, e g uma bijecao de b ema1 ⊆ a. Observe que o resultado (a ≈ b) estara provado se encontramos umconjunto d ⊆ a tal que g|(b − f“d) e uma bijecao de b − f“d em a − d. Comefeito, nesse caso teriamos que h = (f |d) ∪ (g−1|(a− d)) e uma bijecao entre ae b, como pode ser facilmente conferido usando a Proposicao 8.7(f). O nossoobjetivo e portanto achar um conjunto d com a propriedade mencionada acima.Para isso considere o conjunto

u = {c : c ⊆ a ∧ g“(b− f“(c)) ⊆ a− c}.

Dado que c ⊆ a sse c ∈ P(a), entao u e legitimado por [A2].Fatos: (1) Dados x, y ⊆ z, entao: x ⊆ z − y sse y ⊆ z − x, e x = z − y ssey = z − x.(2) Sejam z, y conjuntos. Se x ⊆ y para todo x ∈ z, entao

⋃z ⊆ y.

(3) Se c1 ⊆ c2 ⊆ a, entao a− g“(b− f“c1) ⊆ a− g“(b− f“c2).(4)

⋃u ⊆ a− g“(b− f“

⋃u) (onde u e deinido como acima).

Com efeito:(1) Suponha que x ⊆ z−y. Seja w ∈ y; logo, w ∈ z, pois y ⊆ z. Se w ∈ x, entaow ∈ z − y, isto e, w 6∈ y, uma contradicao. Portanto w 6∈ x, donde w ∈ z − x eentao y ⊆ z − x. Simetricamente, y ⊆ z − x implica x ⊆ z − y. Para a segundaparte, suponha que x = z − y; logo x ⊆ z − y e entao, pela primeira parte,y ⊆ z − x. Seja w ∈ z − x; se w 6∈ y, entao w ∈ z − y = x. Mas w 6∈ x, porhipotese. Esta contradicao mostra que w ∈ y, isto e: z − x = y. A prova deque y = z − x implica x = z − y e simetrica.(2) Assuma que x ⊆ y para todo x ∈ z, e seja w ∈

⋃z. Logo w ∈ x para algum

x ∈ z, pela definicao de⋃z. Mas x ⊆ y, por hipotese; logo w ∈ y. Daqui⋃

z ⊆ y.(3) Se c1 ⊆ c2 ⊆ a, entao f“c1 ⊆ f“c2 ⊆ b donde b − f“(c2) ⊆ b − f“(c1). Por-tanto

g“(b− f“(c2)) ⊆ g“(b− f“(c1)) ⊆ a

e entao a− g“(b− f“c1) ⊆ a− g“(b− f“c2).(4) Seja c ∈ u; logo g“(b− f“(c)) ⊆ a− c e entao, por (1),

c ⊆ a− g“(b− f“(c)). (∗)

Por outro lado⋃u ⊆ a, por (2). Alem disso, c ⊆

⋃u: com efeito, se x ∈ c

entao (x ∈ c) ∧ (c ∈ u) portanto x ∈⋃u. De c ⊆

⋃u ⊆ a infere-se que

a− g“(b− f“(c)) ⊆ a− g“(b− f“⋃u), por (3). Portanto c ⊆ a− g“(b− f“

⋃u)

para todo c ∈ u, por (∗), donde⋃u ⊆ a− g“(b− f“

⋃u), por (2). Isto conclui

a prova dos Fatos.Considere w = a− g“(b− f“

⋃u). Por (4) temos que

⋃u ⊆ w ⊆ a, logo

w = a− g“(b− f“⋃u) ⊆ a− g“(b− f“w),

37

por (3). Por (1) obtemos g“(b− f“w) ⊆ a− w, isto e, w ∈ u. Daqui w ⊆⋃u,

donde w =⋃u. Isto e,

a− g“(b− f“⋃u) =

⋃u.

Pela segunda parte de (1) obtemos g“(b− f“⋃u) = a−

⋃u. Vemos assim que

d =⋃u satisfaz a propriedade requerida. �

Proposicao 9.11 Se a � b e c � d, entao:(i) Se b ∩ d = ∅ entao a ∪ c � b ∪ d;(ii) a× c � b× d;(iii) ac � bd se nao e o caso que: a = b = c = ∅ e d 6= ∅.

Demonstracao: Sejam f1 e f2 bijecoes de a em b1 ⊆ b e de c em d1 ⊆ d,respectivamente.(i) Temos que a ∪ c = (a− c) ∪ c, com (a− c) ∩ c = ∅. Como b ∩ d = ∅, entaof1“(a− c) ∩ d1 = ∅. Portanto h = (f1|(a− c)) ∪ f2 e uma bijecao entre a ∪ c ef1“(a− c) ∪ d1 ⊆ b ∪ d.(ii) Pela Proposicao 9.4(b), a× c ≈ b1 × d1 ⊆ b× d.(iii) a ≈ b1 e c ≈ d1 implicam que ac ≈ bd11 ⊆ bd1 , pela Proposicao 9.5(a). Aprova estara terminada se encontrarmos uma injecao de bd1 em bd. O unicocaso em que isto nao e possıvel e quando bd = ∅ e bd1 6= ∅, e e por isso quea hipotese adicional (nao e o caso que a = b = c = ∅ e d 6= ∅) foi colocada.Com efeito, se bd = ∅, entao d 6= ∅ e b = ∅, pela Proposicao 8.11(d). Nesse casoa = ∅. Agora, se d1 = ∅ (o que equivale a ter bd1 6= ∅), entao c = ∅, dondea = b = c = ∅ e d 6= ∅, contrariando a nossa hipotese. Logo d1 6= ∅ e entaobd1 = ∅, pela Proposicao 8.11(d). Ou seja: bd = ∅ implica bd1 = ∅, e entaoac = ∅, donde ac � bd. Suponha finalmente que bd 6= ∅. Os casos bd1 = ∅ oud = ∅ implicam trivialmente que ac � bd. Suponha entao que bd1 6= ∅ e d 6= ∅.Dado que bd 6= ∅ e d 6= ∅, entao b 6= ∅. Fixemos x0 ∈ b. Para f ∈ bd1 e x ∈ d,defina

h(f)(x) ={f(x) se x ∈ d1

x0 se x ∈ d− d1.

Ou seja: h(f) = f ∪ {〈x, x0〉 : x ∈ d − d1}. Claramente h(f) ∈ bd e entaoh : bd1−→bd e uma funcao. Observe que f ∩ {〈x, x0〉 : x ∈ d − d1} = ∅ (pois〈x, y〉 ∈ f implica x ∈ d1 implica 〈x, y〉 6∈ {〈x, x0〉 : x ∈ d − d1}). Daquih(f) = h(g) implica f = g, isto e, h e injetora. Seja g e uma bijecao entre ac

e bd11 (lembre que ac ≈ bd11 ). Daqui h ◦ g e uma bijecao de ac em h“(bd11 ) ⊆ bd,isto e, ac � bd. �

Definicao 9.12 a ≺ b denota a � b ∧ ¬(b � a).

Proposicao 9.13 (i) Nao e o caso que a ≺ a.(ii) Se a ≺ b entao nao e o caso que b ≺ a.(iii) Se a ≺ b e b ≺ c entao a ≺ c.

38

Demonstracao: (i) Pela Definicao 9.12, a ≺ a sse a � a e nao e o caso quea � a, uma contradicao. Logo nao e o caso que a ≺ a.(ii) Assuma a ≺ b; isto implica que a � b e nao b � a. Por outro lado, b ≺ aequivale a b � a e nao a � b. Portanto nao podemos ter b ≺ a, pois a � b, porhipotese.(iii) Assuma a ≺ b e b ≺ c. Logo a � b e b � c, donde a � c. Se c � a, entaoc � b, contrariando b ≺ c. Portanto nao podemos ter c � a, donde a ≺ c. �

Estabeleceremos algumas relacoes entre � e ≺.

Proposicao 9.14 (i) Se a � b entao nao b ≺ a.(ii) Se a � b e b ≺ c entao a ≺ c.(iii) Se a ≺ b e b � c, entao a ≺ c.(iv) a � b sse a ≈ b ou a ≺ b.

Demonstracao: (i) Pela Definicao 9.12, b ≺ a implica que nao a � b. Portantoa � b implica b 6≺ a.(ii) Assuma a � b e b ≺ c. Daqui a � b e b � c, donde a � c. Se c � a entaoc � b, contrariando b ≺ c. Portanto nao e o caso que c � a, donde a ≺ c.(iii) Assuma a ≺ b e b � c. Como antes, obtemos a � c. Se c � a entao b � a,pois b � c; mas isto contraria a ≺ b. Portanto c 6� a, donde a ≺ c.(iv) Assuma que a � b. Se a 6≺ b entao, pela Definicao 9.12, inferimos queb � a ou a 6� b. Daqui obtemos que b � a e entao, pelo Teorema 9.10, a ≈ b.provamos desta maneira que a � b implica a ≈ b ou a ≺ b. Reciprocamente,suponha que a ≈ b. Logo a � b. Se a ≺ b, entao a � b, pela Definicao 9.12.Isto prova que a ≈ b ou a ≺ b implica a � b. �

Observe que o item (iv) da proposicao acima justifica a denominacao intuitivade menor ou igual para a relacao �.

Teorema 9.15 (Cantor) a ≺ P(a).

Demonstracao: A funcao f(x) = {x} de a em P(a) e injetora, portantoa � P(a). Suponha que a ≈ P(a) via uma funcao g : a−→P(a). Considere

b = {y : (y ∈ a) ∧ (y 6∈ g(y))}.

E claro que b e legitimado por [A2], e b ∈ P(a). Como g e sobrejetora, deveexistir algum x ∈ a tal que g(x) = b. Portanto:

x ∈ g(x) sse x 6∈ g(x).

Daqui inferimos que nao pode existir uma tal g, isto e, a 6≈ P(a). Por outrolado, observe que Teorema 9.10 pode ser refraseado como: a � b implica (a 6≈ bimplica b 6� a). Logo, de a � P(a) e a 6≈ P(a) inferimos, pelo Teorema 9.10,que P(a) 6� a. Pela Definicao 9.12, a ≺ P(a). �

39

10 Conjuntos Finitos

Estudaremos nesta secao os conjuntos finitos. A definicao intuitiva de conjuntofinito e a seguinte: um conjunto a e finito se a tem n elementos, para algumnumero natural n. Esta ideia e correta, mas utiliza o conceito de numerosinteiros. Dedekind propos em 1888 uma definicao nao numerica extremamenteelegante: um conjunto a e finito se a nao e equipolente com nenhum subconjuntoproprio. Em outras palavras, os conjuntos finitos sao exatamente aqueles emque a parte e menor do que o todo. E evidente que esta definicao pode serfacilmente introduzida em ZF . O problema que envolve esta definicao e que,para provar que todo conjunto finito (no sentido de Dedekind) e finito (nosentido usual), devemos usar o Axioma da Escolha [AE]. Este axioma, a serintroduzido posteriormente, e o mais questionado dos axiomas da TC, existindoinclusive TCs que rejeitam este princıpio (de fato, na literatura sao diferenciadosos sistemas ZF e ZFC, sendo que ZFC consiste de ZF com o acrescimo doAxioma da Escolha). Tarski propos em 1924 a seguinte definicao de finitude aqual, embora seja menos intuitiva, tem a vantagem que nao requer [AE] paraprovar a equivalencia com a definicao usual de finitude.

Definicao 10.1 (i) min(x, u) denota x ∈ u ∧ (∀y)(y ∈ u→ ¬(y ⊂ x))(“x e um elemento minimal de u”).(ii) max(x, u) denota x ∈ u ∧ (∀y)(y ∈ u→ ¬(x ⊂ y))(“x e um elemento maximal de u”).

Por exemplo, se b = {1, 2, 3, 4} e u ⊆ P(b), u = {{1, 2, 4}, {2}, {2, 4}, {1, 3}},entao {1, 2, 4} e {1, 3} sao os elementos maximais de u, enquanto que {2} e{1, 3} sao os elementos minimais de u. Por outro lado, seja b = N e

Nn = N−{1, . . . , n−1} = {n, n+1, n+2, . . .} (n ∈ N); u = {Nn : n ∈ N} ⊆ P(b).

Dado que Nn ⊂ Nm se n > m, entao u nao tem elementos minimais. Esta ea situacao que caracteriza os conjuntos b infinitos, segundo a descoberta deTarski.

Definicao 10.2 (Tarski) fin(b) denota a formula(∀u)((u ⊆ P(b) ∧ (u 6= ∅)) → (∃z)min(z, u))

(“b e finito se toda famılia nao vazia de subconjuntos de b possui um elementominimal”).

As primeiras propriedades simples da finitude sao as seguintes:

Proposicao 10.3 (i) ∅ e finito.(ii) {x} e finito.(iii) Se b e finito e c ⊆ b, entao c e finito.(iv) Se c e finito entao c ∩ b e c− b sao finitos.

Demonstracao: (i) Observe que P(∅) = {∅}, portanto u = {∅} e a unicafamılia nao vazia de subconjuntos de ∅. E claro que ∅ e um elemento minimalde u, portanto fin(∅).

40

(ii) Temos que P({x}) = {∅, {x}}. Logo, as unicas famılias nao vazias desubconjuntos de {x} sao u1 = {∅}, u2 = {{x}}, e u3 = {∅, {x}}. E imediato quetodo conjunto da forma {z} tem um elemento minimal (o proprio z), portantou1 e u2 possuem elemento minimal. Finalmente, ∅ e o elemento minimal de u3.Isto prova fin({x}).(iii) Assuma que b e finito, e seja c ⊆ b. Seja u ⊆ P(c), u 6= ∅. Logo u ⊆ P(b),u 6= ∅. Dado que fin(b), entao u possui um elemento minimal z. Daqui fin(c).(iv) Suponha que c e finito. Para todo b temos que c − b ⊆ c e c ∩ b ⊆ c. Peloitem (iii) obtemos que fin(c− b) e fin(c ∩ b). �

A seguinte propriedade exige uma demonstracao um pouco mais complicada.

Proposicao 10.4 Se c e b sao finitos, entao c ∪ b e finito.

Demonstracao: Assuma fin(c) e fin(b). Seja u ⊆ P(c∪b), u 6= ∅. Provaremosque u tem um elemento minimal. Considere

w = {a : a ⊆ c ∧ (∃d)((d ⊆ b) ∧ a ∪ d ∈ u)}.

Temos que w 6= ∅. Com efeito, seja z ∈ u. Dado que z = (z ∩ c)∪ (z− c), entaoa = z ∩ c e d = z − c satisfazem: a ⊆ c; d ⊆ b (pois z ⊆ c ∪ b); a ∪ d ∈ u. Logoa e um elemento de w. Daqui w ⊆ P(c), w 6= ∅. Como c e finito, deve existira∗ ∈ w minimal. Logo

(1) a∗ ∈ w, a∗ ⊆ c.

Considere agoraw1 = {d : d ⊆ b ∧ (a∗ ∪ d ∈ u)}.

Por (1) temos que a∗∪d ∈ u para algum d ⊆ b, logo d ∈ w1. Portanto w1 ⊆ P(b),w1 6= ∅. Como b e finito existe um elemento minimal d∗ ∈ w1, donde

(2) d∗ ∈ w1, d∗ ⊆ b, a∗ ∪ d∗ ∈ u.

Provaremos que a∗∪d∗ e um elemento minimal de u. Suponha que s ∈ u tal ques ⊆ a∗∪d∗. Daqui s∩a∗ ⊆ a∗ ⊆ c e s∩d∗ ⊆ d∗ ⊆ b. Dado que s ⊆ a∗∪d∗, entao

(3) s = s ∩ (a∗ ∪ d∗) = (s ∩ a∗) ∪ (s ∩ d∗).

Como s ∈ u obtemos que s ∩ a∗ ∈ w, e s ∩ a∗ ⊆ a∗. Dado que a∗ e minimal,inferimos s∩a∗ = a∗. Por (3) obtemos que a∗ ∪ (s∩d∗) ∈ u, donde s∩d∗ ∈ w1.Logo s∩d∗ = d∗, pois d∗ e minimal. Usando (3) vemos que s = a∗∪d∗. Portantoa∗ ∪ d∗ e um elemento minimal de u. Isto prova que c ∪ b e finito. �

Corolario 10.5 Se b e finito, entao b ∪ {x} e finito.

Podemos definir um princıpio de inducao para conjuntos finitos. Antes disso,provaremos que existe uma caracterizacao da finitude em termos de conjuntosmaximais.

41

Proposicao 10.6 (a) Toda famılia nao vazia de subconjuntos de um conjuntofinito possui um elemento maximal.(b) Se toda famılia nao vazia de subconjuntos de um conjunto b possui umelemento maximal, entao b e finito.

Demonstracao: (a) Dado a finito, seja u ⊆ P(a), u 6= ∅. Considere v ={a − x : x ∈ u}. Claro que v e legitimado por [A2], v ⊆ P(a), e v 6= ∅ (poisu 6= ∅). Como a e finito, existe a−x ∈ v minimal, onde x ∈ u. Provaremos quex e maximal em u. Para isto, observe que

(1) para todo w, y ⊆ a temos que: y ⊂ w sse a− w ⊂ a− y.

A prova e simples, e e deixada como exercıcio. Suponha entao que x nao emaximal em u. Logo, deve existir y ∈ u tal que x ⊂ y. Por (1) obtemosa − y ⊂ a − x, onde a − y ∈ v. Isto contradiz a minimalidade de a − x em v,portanto x e maximal.(b) A prova e analoga a do item anterior. Assim, considere u ⊆ P(b), u 6= ∅.Logo

v = {b− x : x ∈ u}

e uma famılia nao vazia de subconjuntos de b. Por hipotese, existe um elementomaximal b − x em v, com x ∈ u. Utilizando (1) vemos que x e minimal em u,portanto b e finito. �

Teorema 10.7 Seja ϕ(b) uma formula em que b ocorre livre e nem c nem xocorrem livres (outras variaveis podem ocorrer livres em ϕ). Suponha o seguinte:

(i) c e finito;(ii) ϕ(∅);(iii) (∀x)(∀b)(((x ∈ c) ∧ (b ⊆ c) ∧ ϕ(b)) → ϕ(b ∪ {x})).

Entao ϕ(c).

Demonstracao: Considere u = {b : b ⊆ c ∧ ϕ(b)}. Logo u ⊆ P(c) e u 6= ∅pois ∅ ∈ u, pela hipotese (ii). Dado que c e finito, por (i), entao existe b ∈ umaximal, pela Proposicao 10.6(a). Provaremos que b = c, e logo ϕ(c) comoqueriamos. Por reducao ao absurdo, suponha que b 6= c. Como b ⊆ c, deveexistir x ∈ c− b. Por (iii), temos que ϕ(b∪ {x}) e entao b∪ {x} ∈ u, sendo queb ⊂ b ∪ {x}. Isto contradiz a maximalidade de b em u. Daqui b = c e ϕ(c). �

Em particular, obtemos a seguinte formulacao conjuntista do princıpio de inducaopara conjuntos finitos:

Teorema 10.8 Suponha o seguinte:(i) c e finito;(ii) ∅ ∈ w;(iii) (∀x)(∀b)(((x ∈ c) ∧ (b ⊆ c) ∧ b ∈ w) → b ∪ {x} ∈ w).

Entao c ∈ w.

42

Demonstracao: Basta considerar no Teorema 10.7 a formula ϕ(b) como sendo“b ∈ w”. �

Observe que o Teorema 10.7 e uma consequencia do Teorema 10.8 considerandow = {b : (b ∈ P(c)) ∧ ϕ(b)} (legitimado por [A2]). Daqui, os Teoremas 10.7e 10.8 sao equivalentes. De fato, as propriedades (ii) e (iii) do Teorema 10.8caracterizam os conjuntos finitos, como provaremos a seguir.

Proposicao 10.9 c e finito sse c pertence a todo w satisfazendo as condicoes(ii) e (iii) do Teorema 10.8.

Demonstracao: Se c e finito, entao a conclusao vale pelo Teorema 10.8. Reci-procamente, assuma que c ∈ w para todo w satisfazendo as condicoes (ii) e (iii)do Teorema 10.8. Seja w o conjunto de todos os subconjuntos finitos de c (we legitimado por [A2]; confira!). Pela Proposicao 10.3(i) temos que ∅ ∈ w. Seb ∈ w e x ∈ c entao b ∪ {x} ∈ w pelo Corolario 10.5. Portanto w satisfaz ascondicoes (ii) e (iii) do Teorema 10.8, donde c ∈ w. Isto e, c e finito. �

Proposicao 10.10 Se c e finito e f e uma funcao com domınio c e imagem b,entao b e finito.

Demonstracao: Seja w = {a : (a ⊆ c) ∧ fin(f“a)}. Provaremos pelo Teo-rema 10.8 que c ∈ w, donde im(f) = f“c resultara ser finito. Observe que∅ ⊆ c e f“∅ = ∅ (finito); entao ∅ ∈ w. Seja x ∈ c e a ∈ w; logo a ∪ {x} ⊆ c.Como f e funcao, entao f“{x} = {f(x)}, logo f“{x} e finito, pela Propo-sicao 10.3(ii). Daqui f“(a ∪ {x}) = f“a ∪ f“{x} e finito, pela Proposicao 10.4,e entao a ∪ {x} ∈ w. Pelo Teorema 10.8 temos que c ∈ w, portanto im(f) efinito. �

Proposicao 10.11 Se c e finito, entao P(c) e finito.

Demonstracao: Considere w = {b : b ⊆ c ∧ fin(P(b))}. Temos que ∅ ∈ w.Suponha b ∈ w e x ∈ c. Se x ∈ b entao b∪{x} ∈ w. Se x 6∈ b, entao b∪{x} ⊆ c.Defina

f = {〈a, a ∪ {x}〉 : a ∈ P(b)}.

Temos que f e legitimado por [A2], e f e funcao com domınio P(b) (finito). PelaProposicao 10.10 temos que a imagem de f e finita. Seja z = P(b∪{x})−P(b).Provaremos que im(f) = z. Com efeito, dado a ∈ P(b), temos que a∪ {x} ∈ z,pois x 6∈ b. Logo im(f) ⊆ z. Por outro lado, se d ∈ z, entao x ∈ d, d − {x} ∈P(b) e d = (d − {x}) ∪ {x}. Daqui f(d − {x}) = d, portanto d ∈ im(f).Provamos entao que z = im(f) e finito. Mas P(b ∪ {x}) = z ∪ P(b), portantoP(b ∪ {x}) e finito, pela Proposicao 10.4. Desta maneira b ∪ {x} ∈ w, dondec ∈ w, isto e, P(c) e finito. �

Proposicao 10.12 Se c e finito e todo x ∈ c e finito, entao⋃c e finito

43

Demonstracao: Considere w = {b : b ⊆ c∧ fin(⋃b)} (legitimado por [A2]).

Claramente ∅ ∈ w. Seja b ∈ w e x ∈ c. Logo x e finito, por hipotese, e⋃b e

finito, pela hipotese de inducao (b ∈ w). E facil provar que⋃(b ∪ {x}) = (

⋃b) ∪ x

(exercıcio). Portanto⋃

(b∪{x}) e finito, pela Proposicao 10.4, e entao b∪{x} ∈w (claramente b ∪ {x} ⊆ c). Pelo Teorema 10.8 obtemos c ∈ w, isto e,

⋃c e

finito. �

Proposicao 10.13 Se P(c) e finito, entao c e finito.

Demonstracao: Seja b = {{x} : x ∈ c} (legitimado por [A2]). Como P(c) efinito e b ⊆ P(c), entao a Proposicao 10.3(iii) assegura que b e finito. Como todoelemento de b e da forma {x} (portanto finito) entao a Proposicao 10.12 nosgarante que

⋃b e finito. Mas e facil provar que

⋃b = c. Com efeito: se y ∈

⋃b,

entao existe x ∈ c tal que y ∈ {x}, isto e, y = x donde y ∈ c. Reciprocamente,se x ∈ c entao x ∈ {x} onde {x} ∈ b, portanto x ∈

⋃b. Logo, c e finito. �

Proposicao 10.14 (i) Se c e finito e c ≈ b entao b e finito.(ii) Se c e finito e b � c entao b e finito.

Demonstracao: (i) Seja f uma bijecao de c em b. Como c e finito entao im(f)e finito, pela Proposicao 10.10. Mas im(f) = b.(ii) Se b � c, entao b ≈ a onde a ⊆ c. Se c e finito, entao a e finito. Logo a ≈ be a e finito, donde b e finito, pelo item (i). �

A Lei de Tricotomia estabelece: para todo par de conjuntos c,b, temos que valeuma e so uma das seguinte possibilidades: c ≺ b, b ≺ c, ou c ≈ b. Pode serprovado que a Tricotomia equivale ao Axioma da Escolha. Porem, se um dosconjuntos e finito, nao precisamos de [AE] para provar esta propriedade.

Proposicao 10.15 Se c e finito entao c ≺ b, b ≺ c, ou c ≈ b.

Demonstracao: Faremos inducao sobre os subconjuntos de c. Dado b, con-sidere

w = {a : a ⊆ c ∧ ((a ≺ b) ∨ (b ≺ a) ∨ (a ≈ b))}.Claramente ∅ ∈ w pois, se b = ∅, entao ∅ ≈ b e, se b 6= ∅, entao ∅ ≺ b. Sejaa ∈ w e x ∈ c; queremos provar que a∪ {x} ∈ w. O caso em que x ∈ a e obvio.Assumamos que x 6∈ a. Como a ∈ w, entao temos tres casos:Caso 1: a ≺ b. Logo, existe y ∈ b − im(f), onde f e uma funcao injetora de aem b. Portanto, g = f ∪ {〈x, y〉} e uma funcao injetora de a ∪ {x} em b, dondea∪{x} � b. Daqui inferimos a∪{x} ≺ b ou a∪{x} ≈ b, pela Proposicao 9.14(iv).Nos dois casos, a ∪ {x} ∈ w.Caso 2: b ≺ a. Como a � a ∪ {x}, entao b ≺ a ∪ {x}, pela Proposicao 9.14(iii).Portanto a ∪ {x} ∈ w.Caso 3: b ≈ a. Como a ⊆ a∪{x}, entao a ≈ a∪{x} ou a ≺ a∪{x}. No primeirocaso b ≈ a ∪ {x}; no segundo caso b ≺ a ∪ {x}. Nos dois casos a ∪ {x} ∈ w.Em virtude do Teorema 10.8, c ∈ w, isto e, c ≺ b, b ≺ c, ou c ≈ b. �

44

Corolario 10.16 Se c e finito e b nao e finito, entao c ≺ b.

Demonstracao: Temos que c ≺ b, b ≺ c ou c ≈ b. Os dois ultimos casosimplicam a existencia de uma bijecao f de a ⊆ c em b. Mas a e finito, portantob = im(f) e finito, o que contradiz a hipotese. Logo, so pode ser c ≺ b. �

Provaremos agora que um conjunto finito (no sentido Tarski) e um conjuntofinito (no sentido Dedekind). Como mencionamos anteriormente, toda provaconhecida da afirmacao recıproca precisa do [AE].

Definicao 10.17 Dedfin(c) denota ¬(∃b)(b ⊂ c ∧ c ≈ b)(“c e Dedekind-finito se nao e equipolente com nenhum subconjunto proprio”).

Teorema 10.18 Se c e finito, entao c e Dedekind-finito.

Demonstracao: Seja c finito, e suponha que c nao e Dedekind-finito. Logo,existe b ⊂ c tal que c ≈ b (via uma bijecao f de c em b). Considere

u = {a : a ⊆ c ∧ f“a ⊂ a}.

Como c ⊆ c e f“c = b ⊂ c, entao c ∈ u, logo u 6= ∅. Como c e finito e u ⊆ P(c)e nao vazio, existe um elemento minimal d em u. Dado que f“d ⊂ d e d eminimal, entao

(1) f“d 6∈ u.

Por outro lado f“d ⊂ d implica que existe x ∈ (d−f“d). Note que f“(f“d) ⊆ f“d.Se f(x) ∈ f“(f“d), entao f(x) = f(y) com y ∈ f“d. Mas f e injetora,portanto f(x) = f(y) implica x = y, isto e, x ∈ f“d, uma contradicao.Logo f(x) ∈ f“d − f“(f“d), donde f“(f“d) ⊂ f“d. Daqui (e do fato de terf“d ⊂ d ⊆ c) inferimos f“d ∈ u, em contradicao com (1). Portanto a suposicaoinicial e falsa e entao c e Dedekind-finito. �

Proposicao 10.19 Sejam c e b finitos.(i) c× b e finito.(ii) cb e finito.

Demonstracao: (i) Sejam c e b finitos. Se c = ∅ ou b = ∅ entao c × b = ∅ efinito. Se c e b sao nao vazios, entao

c× b =⋃a, a = {c× {y} : y ∈ b}.

Dado que c ≈ c × {y}, entao todo elemento de a e finito. Claramente a ≈ b,donde a e finito. Pela Proposicao 10.12 o conjunto

⋃a e finito, isto e, c × b e

finito.(ii) Temos que cb ⊆ P(b× c). Como b× c e finito, pelo item (i), entao P(b× c)e finito, donde cb e finito. �

45

11 Axiomas Finais de ZF . O Axioma da Escolha

Para definir a nocao de ordinal precisaremos de acrescentar axiomas adicionaisao sistema S. A seguir completaremos a definicao do sistema ZF , estudando asconsequencias da incorporacao dos mesmos. O primeiro axioma a ser incorpo-rado ao nosso sistema atual e o Axioma da Infinidade, que assegura a existenciade un conjunto infinito.

Axioma da Infinidade:

[A6] (∃w)((∅ ∈ w) ∧ (∀x)(x ∈ w→ x ∪ {x} ∈ w))

Por definicao temos que ∅ ∈ w, portanto

{∅} = ∅ ∪ {∅} ∈ w;{∅, {∅}} = {∅} ∪ {{∅}} ∈ w;{∅, {∅}, {∅, {∅}}} = {∅, {∅}} ∪ {{∅, {∅}}} ∈ w; etc.

Dado que {x} e logo x∪{x} so aparece num nıvel posterior ao nıvel em que foicriado x, entao [A6] exige a existencia de uma sequencia crescente infinita denıveis na estrutura cumulativa de tipos, sendo que w aparece so depois de todosesses nıveis. Este axioma e a primeira tentativa de afirmar que os nıveis naotem fim. Portanto, esta afirmacao pode ser aceita por alguns matematicos e re-jeitada por outros. E fundamental perceber que este axioma separa claramentea Aritmetica (que pode ser realizada sem assumir a existencia de sequenciasinfinitas) de outras disciplinas da Matematica avanzada, tais como Analise, quefazem um uso essencial do Axioma da Infinidade.

A seguir introduziremos um axioma importantıssimo, o Axioma de Substi-tuicao. Nao so obteremos o Axioma de Separacao como um corolario, senaoque poderemos assegurar a existencia de ordinais e cardinais transfinitos.

Axioma de Substituicao: Seja ψ(x, y) uma formula com x e y livres, masonde b nao ocorre livre (outras variaveis podem ocorrer livres em ψ). Seja z umavariavel nova, e FUNψ a formula (∀x)(∀y)(∀z)(ψ(x, y) ∧ ψ(x, z) → (y = z)).

[A7] FUNψ → (∃b)(∀y)(y ∈ b↔ (∃x)(x ∈ a ∧ ψ(x, y)))

A hipotese FUNψ indica que ψ define uma funcao parcial, isto e: para cada x,existe no maximo um y tal que ψ(x, y). Assumindo FUNψ, entao [A7] asseguraque o termo s dado por

s = {y : (∃x)((x ∈ a) ∧ ψ(x, y))}

e legitimado; ele representa a imagem de a sob a funcao parcial definida porψ(x, y); se o termo r dado por

r = {〈x, y〉 : ψ(x, y)}

46

e legitimado, entao s e r“(a) = im(r|a). Dado que r nao e necessariamente legi-timado, devemos esperar que [A7] acrescente novos conjuntos. Observe que [A7]e um esquema de axioma, definindo um axioma particular para cada formulaψ. Ele afirma que, dado a, podemos substituir os seus elementos por outrosconjuntos, desde que coloquemos no maximo um conjunto para cada elementode a.

Em termos da teoria cumulativa de tipos, isto afirma que os nıveis nao temfim. De fato, e a afirmacao mais forte em ZF nessa direcao. Assim, [A7] afirmaque toda colecao de nıveis colocados em correspondencia com os elementos deum conjunto pode ser considerada como completada, portanto existem nıveissuperiores. Mais precisamente, seja f(x) o nıvel em que aparece y tal queψ(x, y) (se nao existir y entao f(x) pode ser tomado como o primeiro nıvel).Logo, a colecao de nıveis f(x) esta em correspondencia com os elementos de a,portanto existe um nıvel em que todos os y tais que ψ(x, y) para algum x ∈ aja foram criados. Nesse nıvel pode ser criado b = {y : (∃x)((x ∈ a)∧ψ(x, y))}.

Observe que [A7] fornece um axioma para cada formula ψ apropriada; istolimita o poder de [A7], da mesma maneira que acontece con [A2]. Por outrolado, [A2] e um caso particular de [A7]:

Proposicao 11.1 Seja φ(x) uma formula em que x ocorre livre mas b naoocorre livre. Logo,

[A7] ` (∃b)(∀x)(x ∈ b↔ ((x ∈ a) ∧ φ(x))).

Em outras palavras, [A2] e implicado por [A7].

Demonstracao: Seja y uma variavel nova (isto e, y nao ocorre em φ(x) ey 6= b). Considere ψ(x, y) dada por

ψ(x, y) ≡def φ(x) ∧ (x = y).

Pelas regras da igualdade, provamos a formula

(∗) (∃x)((x ∈ a) ∧ ψ(x, y)) ↔ (y ∈ a) ∧ φ(y).

Por outro lado, e facil provar que ψ(x, y) e ψ(x, z) implica y = z. Logo FUNψ

donde, por [A7], inferimos que (∃b)(∀y)(y ∈ b↔ (∃x)((x ∈ a) ∧ ψ(x, y)). Por(∗) obtemos

(∃b)(∀y)(y ∈ b↔ ((y ∈ a) ∧ φ(y))),

isto e, [A2]. �

Provaremos agora que o axioma [PR] pode ser deduzido dos axiomas [A3] e[A7], conforme anunciado na Secao 2.

Proposicao 11.2 [A3], [A7] ` [PR].

Demonstracao: Primeiro obtemos o seguinte:

47

Fato 1: [A7] ` (∃c)(∀u)(u 6∈ c).Com efeito, basta tomar ψc(x, y) ≡def (x 6= x) ∧ (x = y) em [A7], e a umavariavel qualquer (exercıcio).Fato 2: [A3], [A7] ` (∃d)(∀x)(x ∈ d↔ (∀w)(w ∈ x→ (∀u)(u 6∈ w)).Com efeito, basta tomar c como no Fato 1 e depois aplicar [A3] no conjunto c,obtendo o conjunto d com as propriedades requeridas (exercıcio).Fato 3: Dados a e b considere a formula

ψa,b(x, y) ≡def ((∀w)(w 6∈ x) ∧ y = a)∨ ((∃w)(w ∈ x) ∧ (∀w)(w ∈ x→ (∀u)(u 6∈ w)) ∧ y = b).

Entao FUNψa,b(exercıcio).

Fato 4: Usando apenas logica classica temos que

(∃x)((∀w)(w ∈ x→ (∀u)(u 6∈ w)) ∧ ψa,b(x, y)) ↔ (y = a ∨ y = b)

(exercıcio).

Logo, pelo Fato 3 e por [A7] temos que

(∃z)(∀y)(y ∈ z ↔ (∃x)(x ∈ d ∧ ψa,b(x, y))).

Finalmente, tomando d como no Fato 2 obtemos, pelo Fato 4, que

(∃z)(∀y)(y ∈ z ↔ (y = a ∨ y = b)).

�

Definicao 11.3 O sistema ZF da Teoria de Conjuntos consiste do axioma[A1] junto com os axiomas [A3]-[A7]. 1

Uma vez que introduzimos a totalidade dos axiomas de TC, discutiremos o Ax-ioma da Escolha ([AE]), que originou uma das principais discussoes dentro daTeoria de Conjuntos. O sistema obtido de ZF acrescentando [AE] e usualmentedenotado por ZFC. Uma possıvel formulacao de [AE] e a seguinte:

Axioma da Escolha:

[AE] ((∀x)(x ∈ z → x 6= ∅) ∧ (∀x)(∀y)(((x, y ∈ z) ∧ (x 6= y))→ x ∩ y = ∅)) → (∃u)(∀x)(∃v)(x ∈ z → u ∩ x = {v})

Isto e: dado um conjunto z cujos elementos sao nao vazios e dois a dois disjuntos,entao existe um conjunto de escolhas u, que tem exatamente um membro emcomum com cada elemento de z. Observe que, embora u “escolha” um e-lemento de cada membro de z, o axioma nada diz respeito a existencia de umprocedimento efetivo para realizar esta escolha.

1Dado que, pela Proposicao 11.1 o axioma [A2] e derivavel em ZF , continuaremos a utiliza-lo no resto do texto, embora nao seja parte da axiomatica de ZF .

48

O carater altamente nao construtivo deste axioma foi alvo de crıticas porparte das escolas matematicas construtivistas. Porem, a quantidade de aplicacoesfundamentais de [AE] dentro de TC como na Matematica em geral fazem de[AE] um axioma praticamente imprescindıvel. Em TC e necessario [AE], porexemplo, para obter a Lei de Tricotomia para conjuntos. Existe uma serie deimportantes resultados matematicos relacionados com o Axioma de Escolha,por exemplo: o Teorema de Hahn-Banach, o Teorema de Ideais Primos paraAlgebras de Boole, a existencia de bases em espacos vetoriais, e o Teorema deTychonoff (o produto de espacos topologicos compactos e compacto). Estesdois ultimos resultados sao de fato equivalentes a [AE], assim como os seguintesPrincıpios:Princıpio da Boa Ordem: Todo conjunto admite uma boa ordem.Lema de Zorn: Seja A um conjunto ordenado tal que todo subconjunto total-mente ordenado (ou cadeia) B tem um limitante superior. Entao, A tem umelemento maximal.

A nao-construtividade embutida em [AE] pode ser entendida atraves doseguinte exemplo intuitivo, devido a Bertrand Russell:

Exemplo 11.4 Considere uma colecao z de pares de sapatos identicos. Nessecaso, e possıvel escolher sem problemas um unico elemento (sapato) de cada parde sapatos de z, por exemplo atraves do algoritmo “pegue apenas os sapatosque correspondam ao pe direito”. Por outro lado, se agora consideramos umacolecao z′ de pares de meias identicas (nao existindo nenhuma diferenca entrea meia do pe direito e a do pe esquerdo), nao existe um metodo imaginavelque permita escolher apenas uma meia de cada par de z′. Porem, o Axioma daEscolha garante que e possıvel fazer isto! �

12 Introducao aos Ordinais

Embora os axiomas de ZF nao mencionam explicitamente a existencia dos nıveisda teoria cumulativa de tipos, eles sao fortes o suficiente como para permitira sua definicao. Os ordinais permitirao indexar os nıveis (alem de ter muitasoutras aplicacoes).

Definicao 12.1 (von Neumann) transi(x) denota(∀y)(∀z)((y ∈ z) ∧ (z ∈ x) → (y ∈ x))

(“x e transitivo”);conec(x) denota (∀y)(∀z)(y, z ∈ x→ ((y ∈ z) ∨ (z ∈ y) ∨ (y = z)))(“x e conectado com relacao a ∈”);ord(x) denota transi(x) ∧ conec(x)(“x e um ordinal”);x < y denota ord(x) ∧ ord(y) ∧ x ∈ y(“x e um ordinal menor que y”);x ≤ y denota ord(x) ∧ ord(y) ∧ (x < y ∨ x = y).

Teorema 12.2 Utilizando os axiomas [A1], [A2], [A4], [A5], [PR] provamos oseguinte:

49

(i) Se x e ordinal e y ∈ x, entao y e ordinal.(ii) ∅ e ordinal.(iii) Se x e ordinal, entao x ∪ {x} e ordinal.

Demonstracao: (i) Fixe um ordinal x, e y ∈ x. Sejam u, v ∈ y. Como x etransitivo e y ∈ x, entao u, v ∈ x. Como x e conectado com relacao a ∈, entaou ∈ v ou v ∈ u ou u = v. Daqui y e conectado. Para provar que y e transitivodevemos utilizar o axioma da regularidade. Sejam entao u ∈ z, z ∈ y. Comoy ∈ x e x e transitivo, obtemos que u ∈ x. Logo, de conec(x) deduzimos: y ∈ uou y = u ou u ∈ y. Queremos eliminar as duas primeiras possibilidades.Caso 1: y ∈ u. Temos entao: u ∈ z, z ∈ y, y ∈ u. Considere a = {u, y, z}Logo:

y ∈ u ∩ a, z ∈ y ∩ a, u ∈ z ∩ a.

Logo, a 6= ∅ nao tem nenhum elemento disjunto com a, contrariando o axiomada regularidade. Portanto, nao podemos ter y ∈ u.Caso 2: y = u. Temos entao: u ∈ z, z ∈ y, y = u; isto e, y ∈ z, z ∈ y. Mas, naProposicao 3.6(2) provamos que [A5] implica: ¬(a ∈ b ∧ b ∈ a). Portanto naopodemos ter y = u.Assim u ∈ y, donde transi(y). Daqui y e ordinal.(ii) Todas as hipoteses sao falsas, logo ∅ e trivialmente um ordinal.(iii) Seja y = x ∪ {x}. Observe que

(∗) z ∈ y sse z ∈ x ou z = x.

Para provar que y e transitivo sejam u ∈ z e z ∈ y; queremos obter u ∈ y. Por(∗) temos dois casos a partir da hipotese z ∈ y:Caso 1: z ∈ x. Logo u ∈ z, z ∈ x implica u ∈ x, pois transi(x). Daqui u ∈ y,por (∗).Caso 2: z = x. Logo u ∈ z, z = x implica u ∈ x. Portanto u ∈ y, por (∗).Provamos assim transi(y). Para provar que y e conectado considere u ∈ y,z ∈ y; queremos obter z ∈ u ou u ∈ z ou z = u. Por (∗) inferimos a partir deu, z ∈ y:Caso 1: u ∈ x.Caso 1.1: z ∈ x. Daqui u ∈ x, z ∈ x implica z ∈ u ou u ∈ z ou z = u, poisconec(x).Caso 1.2: z = x. Logo u ∈ x, x = z implica u ∈ z, donde z ∈ u ou u ∈ z ouz = u.Caso 2: u = x.Caso 2.1: z ∈ x. Daqui z ∈ x, x = u implica z ∈ u, logo z ∈ u ou u ∈ z ouz = u.Caso 2.2: z = x. Logo u = x, x = z implica u = z, portanto z ∈ u ou u ∈ zou z = u.Provamos entao que y e conectado, sendo portanto um ordinal. �

Definicao 12.3 Introduzimos a notacao seguinte:0 denota ∅;

50

1 denota {∅};2 denota {∅, {∅}};3 denota {∅, {∅}, {∅, {∅}}};em geral, n denota {0,1,2, ...,n− 1};x+ 1 denota x ∪ {x} (o sucessor de x).

Podemos provar agora a lei de tricotomia para ordinais (nao confundir com a leide tricotomia enunciada anteriormente!). Esta propriedade e de fundamentalimportancia.

Teorema 12.4 Se x e y sao ordinais, entao: x ∈ y ou y ∈ x ou x = y.

Demonstracao: Provaremos primeiro o seguinteFato: Se x e y sao ordinais e x ⊂ y, entao x ∈ y.Com efeito: Seja z = y−x. Logo z 6= ∅, portanto existe u ∈ z tal que u∩z = ∅,pelo axioma da regularidade. Logo u ∈ y, u 6∈ x. Como u ∩ z = ∅, entao v ∈ uimplica v 6∈ z, isto e, v 6∈ y ou v ∈ x ou, equivalentemente, (v ∈ y→ v ∈ x). Ouseja: v ∈ u implica (v ∈ y→ v ∈ x). Como y e transitivo e u ∈ y, entao v ∈ uimplica v ∈ y. Como tambem temos (v ∈ y→ v ∈ x), entao deduzimos v ∈ x.Ou seja: v ∈ u implica v ∈ x, donde u ⊆ x. Por outro lado, seja w ∈ x; comox ⊆ y, entao w ∈ y. Dado que u ∈ y e y e conectado, entao u = w ou u ∈ wou w ∈ u. Se u = w, entao de w ∈ x inferimos u ∈ x, contradicao (u ∈ y − x).Se u ∈ w entao: u ∈ w, w ∈ x implica u ∈ x (pois x e transitivo), contradicao.Portanto so podemos ter w ∈ u. Assim: w ∈ x implica w ∈ u, donde x ⊆ u.Desta maneira u = x. Como u ∈ y, entao x ∈ y, provando o Fato.Sejam entao x e y ordinais. E muito simples provar que z = x ∩ y e tambemum ordinal (exercıcio). Se z 6= x e z 6= y, entao z ⊂ x e z ⊂ y, donde z ∈ x ez ∈ y, pelo Fato. Daqui z ∈ x ∩ y, isto e, z ∈ z, contradicao. Logo z = x ouz = y. Se z = x, entao x ⊆ y. Se x = y, vale a tricotomia. Se x ⊂ y, entaox ∈ y, pelo Fato, donde vale a tricotomia. O caso z = y e similar. �

Corolario 12.5 (“Paradoxo” de Burali-Forti) O termo {x : ord(x)} naoe legitimado.

Demonstracao: Suponha que definimos On = {x : ord(x)}. Provaremosque On e um ordinal, portanto On ∈ On, uma contradicao. Com efeito, peloTeorema 12.2(i) obtemos que On e transitivo. Pelo Teorema 12.4 inferimos queOn e conectado. Daqui ord(On). �

Desde o ponto de vista da teoria cumulativa de tipos, esperamos ter so umordinal em cada nıvel (isto sera provado depois). Logo, On nao poderia serjamais completado.

Definicao 12.6 Usaremos as letras gregas α, β, γ, etc., eventualmente comsubındices (mas nao φ, ψ, as quais sao reservadas para denotar formulas),como variaveis para indicar ordinais. Alem disso,

(∀α)φ(α) denotara (∀α)(ord(α) → φ(α));(∃α)φ(α) denotara (∃α)(ord(α) ∧ φ(α)), e

51

{α : φ(α)} denotara {α : ord(α) ∧ φ(α)}.A definicao da quantificacao (∀α) e (∃α) e correta, pois existem ordinais.

Definicao 12.7 suc(x) denota ord(x) ∧ ((∃y)(x = y + 1) ∨ (x = 0))(“x e zero ou um ordinal sucessor”);lim(x) denota ord(x) ∧ ¬suc(x)(“x e um ordinal limite”);int(x) denota suc(x) ∧ (∀y)(y < x→ suc(y))(“x e um enteiro nao negativo”).

Se x e um ordinal sucessor da forma x = y + 1, entao y ∈ x, pela definicaode y + 1. Pelo Teorema 12.2(i), temos que y e tambem um ordinal. Portantoy+1 e um ordinal sse y e um ordinal. Nao existe razao para considerar 0 comosucessor ou limite, mas ele e incluido no conjunto dos sucessores. Observe quevale a seguinte propriedade:

[LIM] lim(x) ↔ ord(x) ∧ (x 6= 0) ∧ (∀y)(y ∈ x→ y + 1 ∈ x).

Com efeito, lim(x) implica ord(x) e ¬ord(x)∨(¬(∃y)(x = y+1)∧x 6= 0). Logoord(x), x 6= 0 e (∀y)(x 6= y + 1). Seja y ∈ x; como ord(y), entao ord(y + 1)donde, por tricotomia, y + 1 < x ou y + 1 = x ou x < y + 1. Nao podemos terx = y+1. Por outro lado, x < y+1 implica: x = y (portanto x ∈ x, contradicao)ou x ∈ y (portanto x ∈ y e y ∈ x, contradicao). Logo y+1 < x, isto e, y+1 ∈ x.Reciprocamente, suponha ord(x), x 6= 0, (∀y)(y ∈ x→ y+1 ∈ x). Se x = y+1,entao y ∈ x, donde y + 1 ∈ x, isto e, x ∈ x, contradicao. Logo x 6= y + 1 paratodo y donde x e ordinal limite.Provaremos que um princıpio fraco de inducao matematica para os inteiros evalido no sistema S (lembre da Definicao 3.5).

Teorema 12.8 (Inducao Matematica) Para cada formula ψ da linguagemde ZF, temos que:

S ` (ψ(0) ∧ (∀α)(ψ(α) → ψ(α+ 1))) → (∀α)(int(α) → ψ(α)).

Demonstracao: Suponhamos que a conclusao do princıpio de inducao e falsa;provaremos que a hipotese e falsa. Assim, assumamos que existe um ordinalβ tal que int(β) ∧ ¬ψ(β). Observe que, dados ordinais γ e β, entao γ ≤ β sseγ = β ou γ ∈ β sse γ ∈ β + 1. Portanto, por [A2] podemos criar o conjunto

y = {γ : γ ≤ β ∧ ¬ψ(γ)} = {γ : (γ ∈ β + 1) ∧ ¬ψ(γ)}.

Por outro lado y 6= ∅, pois β ∈ y. Pelo axioma da regularidade existe γ0 ∈ y talque γ0 ∩ y = ∅. Dado que γ0 ≤ β e int(β), entao suc(γ0). Com efeito: γ0 = βimplica int(γ0), logo suc(γ0). Por outro lado, γ0 < β implica suc(γ0), peladefinicao de int(β). Dado que suc(γ0), entaoCaso 1: γ0 = 0. Daqui ¬ψ(0), pois γ0 ∈ y.Caso 2: γ0 = γ1+1 para algum γ1 (que resulta ser um ordinal, pela observacaoapos a Definicao 12.7). Como γ1 ∈ γ0 e γ0 ∩ y = ∅, entao γ1 6∈ y. Daqui ψ(γ1),pois γ1 ≤ β. Isto e: ψ(γ1) ∧ ¬ψ(γ1 + 1).

52

Vemos que cualquer dos casos acima contraria a hipotese do princıpio de inducao.�

O princıpio de inducao 12.8 e mais fraco do que a inducao utilizada frequente-mente em matematicas, pois 12.8 e restrito as propriedades dos inteiros que po-dem ser expressadas mediante formulas da linguagem. O conjunto das formulase enumeravel, enquanto que o conjunto das propriedades dos inteiros positivose o conjunto P(N), que nao e enumeravel.

Queremos provar que a colecao dos inteiros e um conjunto. Isto sera provadoa partir do axioma do infinito (de fato, o seguinte teorema e equivalente a [A6]).

Teorema 12.9 Seja Z o sistema composto dos axiomas [A1]-[A6] mais [PR],isto e, Z e obtido de ZF substituindo o axioma de substituicao [A7] pelos a-xiomas [A2] e [PR]. Logo

Z ` (∃y)(∀z)(z ∈ y↔ int(z)).

Demonstracao: Pelo axioma [A6] existe um conjunto w tal que 0 ∈ w e sex ∈ w entao x+1 ∈ w. Considere a formula ψ(x) dada por x ∈ w. Por inducaomatematica obtemos:

(∀x)(int(x) → x ∈ w).

Portanto inferimos que int(x) sse (x ∈ w) ∧ int(x) para todo x. Por otro lado,de [A2] deduzimos

(∃y)(∀x)(x ∈ y↔ ((x ∈ w) ∧ int(x))).

Isto significa que existe y = {x : (x ∈ w) ∧ int(x)} = {x : int(x)}. �

Definicao 12.10 ω denota {z : int(z)}(o conjunto dos inteiros nao negativos).

Teorema 12.11 (i) Z ` ord(ω).(ii) Z ` lim(ω).

Demonstracao: (i) Considere y ∈ x e x ∈ ω. Logo y ∈ x e int(x); daqui ye um ordinal (pois y ∈ x e x e um ordinal), e y < x. Logo suc(y). Se z ∈ y,entao z ∈ x, logo suc(z). Daqui int(y), isto e, y ∈ ω. Isto prova que ω etransitivo. Sejam agora x, y ∈ ω. Logo ord(x) e ord(y). Pela lei de tricotomiapara ordinais obtemos x ∈ y ou y ∈ x ou x = y. Isto prova que ω e conectadopara ∈.(ii) Observe que ω 6= 0, pois 0 ∈ ω. Alem disso ω e um ordinal, por (i).Claramente

(∀y)(int(y) → int(y + 1)),

isto e, (∀y)(y ∈ ω→ (y+ 1 ∈ ω)). Pela propriedade [LIM] obtemos que ω e umordinal limite. �

53

13 Inducao e Recursao Transfinita

Introduziremos a seguir a importante nocao de fecho transitivo de um conjunto,que sera utilizada para provar que a relacao de pertinencia ∈ e bem fundada.O fato de ∈ ser bem fundada permitira a introducao de definicoes e demon-stracoes por recursao transfinita em ZF, uma poderosa ferramenta na teoria deconjuntos.

Definicao 13.1 FT (x) denota {y : (∀z)(x ∈ z ∧ transi(z) → y ∈ z)}(“FT (x) e o fecho transitivo de x”).

Por definicao, FT (x) e o menor conjunto transitivo z tal que x ∈ z, isto e, FT (x)e a intersecao de todos os conjuntos transitivos z tais que x ∈ z. Ele e formadointuitivamente da maneira seguinte: dado x, procuramos nos nıveis anterioresos elementos y de x, e recomecamos o processo, isto e, procuramos os elementosz de y, e depois os elementos w de z etc., obtendo o “historico” de x atravesdestas componentes. E claro que precisamos provar a existencia de FT (x)para todo x. Ela e garantida pelos axiomas da infinidade e da substituicao.Enunciamos este resultado, omitindo a demonstracao.

Teorema 13.2 Em ZF o termo FT (x) e legitimado, isto e:

Z ` (∀x)(∃w)(∀y)(y ∈ w↔ (∀z)(x ∈ z ∧ transi(z) → y ∈ z)).

Podemos agora definir a classe de formulas a partir das quais podemos fazerinducao, isto e, as formulas ψ(x, y) que expressam relacoes bem fundadas.

Definicao 13.3 Seja φ(x, y) uma formula onde x e y ocorrem livres. BF (φ)denota

(∀x)((x 6= ∅ → (∃v)(v ∈ x ∧ (∀z)(z ∈ x→ ¬φ(z, v))))∧∧(∃u)(x ⊆ u ∧ (∀w, y)(y ∈ u ∧ φ(w, y) → w ∈ u)))

(“a relacao φ(x, y) e bem fundada”).

A primeira parte da formula anterior afirma que todo conjunto nao vazio deveter um elemento φ-minimal; intuitivamente, nao temos φ-ciclos nem φ-cadeiasdescendentes infinitas, isto e: nao podemos ter φ(x, x1), φ(x1, x2), ..., φ(xn, x)nem

φ(x1, x), φ(x2, x1), φ(x3, x2), . . . , φ(xn, xn−1), . . . .

A segunda parte afirma que todo conjunto pode ser estendido a um conjuntou que e φ-fechado, isto e: todo conjunto φ-relacionado com um membro de udeve pertencer a u.

Proposicao 13.4 Em ZF provamos que as relacoes x < y e x ∈ y sao bemfundadas.

Demonstracao: Nas duas relacoes, a primeira parte e uma consequencia diretado axioma da regularidade. A segunda parte segue do Teorema 13.2, tomandou como sendo FT (x). Com efeito: seja y ∈ x; se x ∈ z e z e transitivo, entaoy ∈ z. Logo y ∈ FT (x), donde x ⊆ FT (x). Se y ∈ FT (x) e w ∈ y, considere z

54

transitivo tal que x ∈ z. Logo y ∈ z, donde w ∈ z, pois z e transitivo. Daquiw ∈ FT (x), portanto FT (x) satisfaz as condicoes requeridas. �

Podemos agora legitimar a nocao de prova por φ-inducao transfinita, assumindoque φ e bem fundada. Assim, para provar que (∀y)ψ(y) basta assumir a ver-dade de ψ(z) para todos os φ-antecessores z de y. A hipotese de inducao e(∀z)(φ(z, y) → ψ(z)).

Teorema 13.5 (Inducao Transfinita) Em S provamos o seguinte:

[BF (φ) ∧ (∀y)((∀z)(φ(z, y) → ψ(z)) → ψ(y))] → (∀y)ψ(y).

Demonstracao: Suponha que (∀y)ψ(y) e falsa e BF (φ) e verdadeira. Encon-traremos v0 tal que

(1) (∀z)(φ(z, v0) → ψ(z)) ∧ ¬ψ(v0),

contrariando a hipotese do teorema. Seja entao v tal que ¬ψ(v); ele existe,pela suposicao ¬(∀y)ψ(y). Como BF (φ), podemos estender {v} a um conjuntoφ-fechado u, isto e:

(2) (v ∈ u) ∧ (z ∈ u ∧ φ(w, z) → w ∈ u).

Considere u′ = {z : (z ∈ u)∧¬ψ(z)}, legitimado por [A2]. Como v ∈ u, entaov ∈ u′, portanto u′ 6= ∅. Pela primeira parte de BF (φ) existe um elementov0 de u′ que e φ-minimal. Logo, fixe z tal que φ(z, v0); isto implica z 6∈ u′,pois v0 e φ-minimal em u′, portanto z 6∈ u ou ψ(z). Dado que v0 ∈ u (poisv0 ∈ u′) e φ(z, v0), entao z ∈ u, por (2). Daqui ψ(z), provando desta maneira:φ(z, v0) → ψ(z) para todo z. Como v0 ∈ u′, entao ¬ψ(v0). Desta maneiraprovamos (1) como queriamos. �

As provas por inducao transfinita sao importantes, mas sao mais uteis quandocombinadas com a definicao por recursao transfinita. Suponha que queremosdefinir a soma de ordinais de maneira a ter

α+ 0 = α;(∗) α+ (β + 1) = (α+ β) + 1;

α+ λ =⋃δ<λ(α+ δ) se λ e um ordinal limite.

Embora +1 e⋃

sejam operacoes conhecidas, vemos que a segunda e a terceiraclausula de (∗) utilizam + nos dois lados da definicao. Usualmente este tipo dedefinicao circular seria rejeitada. Porem, devemos observar que os ordinais dolado direito utilizam + em ordinais menores aos do lado esquerdo (o membroa ser definido). Podemos pensar que, fixado α, definimos sucessivamente α+ βpara ordinais β cada vez maiores, utilizando os valores α + γ com γ < β. OTeorema da Definicao por Recursao Transfinita estabelece que, partindo de umarelacao φ(x, y) bem fundada, entao podem ser realizadas este tipo de definicoes

55

que utilizam os φ-antecessores, e a definicao e unica. Ou seja, podemos definirnovas operacoes por inducao sobre uma relacao bem fundada. Observe quea definicao (∗), embora consista de varias clausulas, elas podem ser juntadasnuma so clausula mediante disjuncao de conjuncoes. Assim uma definicao podeser pensada como sendo introduzida por uma formula. Isto coincide com a ideiade definicao de funcoes por recursao: se h(

→x) e g(x, y;

→x) sao funcoes recursi-

vas de numeros naturais, entao podemos definir por recursao sobre x a funcaof(x;

→x) (onde

→x consiste de parametros) da maneira seguinte:

f(0;→x) = h(

→x);

f(x+ 1;→x) = g(f(x;

→x), x;

→x).

Desta maneira f e definida a partir de g, que utiliza o valor anterior de f .Definiremos um analogo (mais geral) para TC, onde agora g utilizara todos osvalores anteriores de f .

Definicao 13.6 Seja G(x1, ..., xn, y) uma formula com ao menos x1,..., xn, ylivres. Definimos

G′〈x1, ..., xn〉 = {z : (∃y)((∀w)(G(x1, ..., xn, w) ↔ y = w) ∧ (z ∈ y))}.

Isto e, G′〈x1, ..., xn〉 e o unico y tal que G(x1, ..., xn, y) (se existir), ou ∅ em casocontrario. Logo G′〈x1, ..., xn〉 e sempre um conjunto.

Definicao 13.7 Seja F (x1, ..., xn, y) uma formula com ao menos x1, ..., xn, ylivres, e φ(u, v) com u, v livres. Definimos

ANT (F, x1, ..., xn, φ(u, v)) = {〈〈z, x2, x3, ..., xn〉, F ′〈z, x2, ..., xn〉〉 : φ(z, x1)}.

O termo ANT (F, x1, ..., xn, φ(u, v)) define o conjunto dos valores de F previosa x1 (a variavel de recursao).

Lema 13.8 Se φ(u, v) e bem fundada, entao ANT (F, x1, ..., xn, φ(u, v)) e le-gitimado em ZF.

Estabeleceremos a seguir o teorema de recursao transfinita. A partir de agoraG(x, x1, ...., xn, y) e uma formula definindo uma operacao que e iterada navariavel x1, com x2,..., xn como parametros para definir uma operacao y =F ′〈x1, ...., xn〉. Em ANT (F, x1, ..., xn, φ(u, v)) estao disponıveis os valores an-teriores de F , e permanecem no primeiro lugar de G na iteracao, da mesmamaneira que e feito na definicao da funcao recursiva

f(x+ 1;→x) = g(f(x;

→x), x;

→x).

Teorema 13.9 (Recursao Transfinita) Sejam G(x, x1, ..., xn, y) e φ(u, v)formulas. Entao existe uma formula F (x1, ..., xn, y) tal que

BF (φ(u, v)) → (∀x1)[(∃!y)F (x1, ..., xn, y) ∧ (∀y)(F (x1, ..., xn, y) ↔↔ y = G′〈ANT (F, x1, ..., xn, φ(u, v)), x1, x2, ..., xn〉)]

e demonstravel em ZF.

56

Veremos a seguir dois exemplos de aplicacao do princıpio de definicao por re-cursao transfinita: a funcao de posto e a hierarquia cumulativa de von Neumann.

Definicao 13.10 ρ(x) =⋃{ρ(y) + 1 : y ∈ x}

(“ρ(x) e o posto de x”).

Proposicao 13.11 Em ZF provamos o seguinte:(i) ρ(x) e definido para todo conjunto x.(ii) ρ(x) e um ordinal para todo conjunto x.(iii) Se α e um ordinal, entao ρ(α) = α.(iv) se x ∈ y, entao ρ(x) < ρ(y).

Demonstracao: (i) Usaremos o principio de recursao transfinita. Para isto,considere φ(u, v) como sendo u ∈ v; logo, a relacao φ (isto e, a relacao ∈) e bemfundada, pela Proposicao 13.4. Seja G(X,x1, y) a formula

G(X,x1, y) ≡def (x1 = x1) ∧ (y =⋃{w + 1 : w ∈ im(X)}).

Logo, a operacao F (x, y) definida no Teorema 13.9 satisfaz:

F ′〈x〉 = G′〈ANT (F, x,∈), x〉 =⋃{w + 1 : w ∈ im(ANT (F, x,∈))}.

Por outro lado:ANT (F, x,∈) = {〈z, F ′〈z〉〉 : z ∈ x}

donde im(ANT (F, x,∈)) = {F ′〈z〉 : z ∈ x}. Daqui

F ′〈x〉 =⋃{F ′〈z〉+ 1 : z ∈ x}.

Isto significa que a operacao F e a funcao posto.(ii) Considere a formula ψ(x) dada por ord(ρ(x)). Provaremos por inducaotransfinita sobre a relacao ∈ que ψ(x) e verdadeira para todo x. Assim fixemosy, e suponhamos que

(∀z)(z ∈ y→ ord(ρ(z))

(a hipotese de inducao) e verdadeira. Queremos provar que ρ(y) e um ordinal.Se z ∈ y, entao ord(ρ(z)), logo ord(ρ(z) + 1). Alem disso, ρ(y) =

⋃{ρ(z) + 1 :

z ∈ y}, logo x ∈ ρ(y) sse existe z ∈ y tal que x ∈ ρ(z)+1. Sejam entao x ∈ ρ(y)e w ∈ x; logo w ∈ x e x ∈ ρ(z) + 1 para algum z ∈ y, e ρ(z) + 1 e um ordinal(portanto e transitivo). Daqui w ∈ ρ(z) + 1 e entao w ∈ ρ(y). Logo, ρ(y) etransitivo. Se u, v ∈ ρ(y), entao u ∈ ρ(z) + 1 e v ∈ ρ(z′) + 1 para z, z′ ∈ y.Dado que ρ(z) + 1 e ρ(z′) + 1 sao ordinais, entao u e v sao ordinais, portantou ∈ v ou v ∈ u ou u = v, pela lei de tricotomia para ordinais. Daqui ρ(y) econectado, sendo portanto um ordinal.(iii) Considere ψ(x) a formula (ord(x) → x = ρ(x)). Provaremos por inducaotransfinita sobre a relacao bem fundada < que ψ(x) vale para todo x. As-sumamos entao, fixado y, a hipotese de inducao (∀z)(z < y→ ψ(z)), isto e,

(∀z)[(ord(z) ∧ ord(y) ∧ z ∈ y) → (ord(z) → z = ρ(z))]

57

ou, equivalentemente,

(∗) (∀z)[(ord(y) ∧ ord(z) ∧ z ∈ y) → z = ρ(z)].

Queremos provar que (ord(y) → y = ρ(y)). Suponha entao que y e um ordinal.Logo, se z ∈ y entao z e um ordinal, e vale a hipotese de (∗) para z, portantoz = ρ(z). Daqui

ρ(y) =⋃{ρ(z) + 1 : z ∈ y} =

⋃{z + 1 : z ∈ y}.

Seja x ∈ ρ(y); logo x ∈ z + 1 para algum z ∈ y. Temos dois casos:(a) x ∈ z. Logo x ∈ z, z ∈ y implica x ∈ y (pois y e um ordinal portanto etransitivo).(b) x = z. Logo x = z, z ∈ y implica x ∈ y.Vemos que em todos os casos x ∈ ρ(y) implica x ∈ y, donde ρ(y) ⊆ y. Suponhaagora que x ∈ y; logo x ∈ x+ 1 tal que x ∈ y, donde x ∈ ρ(y). Isto e, y ⊆ ρ(y),portanto y = ρ(y) como queriamos provar.(iv) Seja x ∈ y. Como ρ(x) ∈ ρ(x) + 1 e x ∈ y, entao ρ(x) ∈

⋃{ρ(z) + 1 : z ∈

y} = ρ(y). Dado que ρ(x) e ρ(y) sao ordinais, pelo item (ii), entao inferimosque ρ(x) < ρ(y). �

Definicao 13.12 A Hierarchia Cumulativa de von Neumann e definida damaneira seguinte:

Vα =⋃β<α

P(Vβ) =⋃{P(Vβ) : β < α}.

Exemplo 13.13 Aplicando a definicao acima temos que

V0 =⋃{P(Vβ) : β < 0} =

⋃∅ = ∅;

V1 =⋃{P(Vβ) : β < 1} =

⋃{P(V0)} =

⋃{P(∅)} =

⋃{{∅}} = {∅};

V2 =⋃{P(Vβ) : β < 2} =

⋃{P(V0),P(V1)} =

⋃{{∅}, {∅, {∅}}}

= {∅, {∅}};V3 =

⋃{P(Vβ) : β < 3} =

⋃{P(V0),P(V1),P(V2)}

=⋃{{∅}, {∅, {∅}}, {∅, {∅}, {{∅}}, {∅, {∅}}}} = {∅, {∅}, {{∅}}, {∅, {∅}}}.

�

Teorema 13.14 Em ZF provamos o seguinte:(i) Vα e definido para todos os ordinais α.(ii) Seja α um ordinal. Logo Vα e transitivo, e Vα+1 = P(Vα).(iii) Seja λ um ordinal limite. Logo Vλ =

⋃β<λ Vβ.

(iv) Seja α um ordinal. Entao x ∈ Vα sse ρ(x) < α.(v) (∀x)(∃α)(x ∈ Vα) (aqui, α denota um ordinal).

Demonstracao: (i) Aplicaremos o principio de recursao transfinita 13.9. Con-sidere a formula

G(X,x1, y) ≡def (x1 = x1) ∧ (y =⋃{P(w) : w ∈ im(X)}).

58

A operacao F (x, y) definida por recursao transfinita sobre ∈ a partir de Gsatisfaz o seguinte:

F ′〈x〉 =⋃{P(w) : w ∈ im(ANT (F, x,∈))}.

Mas im(ANT (F, x,∈)) = {F ′〈y〉 : y ∈ x}, logo

F ′〈x〉 =⋃{P(F ′〈y〉) : y ∈ x}.

Se α e um ordinal, entao β < α sse β ∈ α, logo F ′〈α〉 representa Vα sobre osordinais α, isto e, Vα esta legitimado para todo ordinal α.(ii) Faremos inducao transfinita sobre a relacao < e a seguinte formula:

ψ(x) ≡def ord(x) → (transi(Vx) ∧ Vx+1 ⊆ P(Vx)).

Fixado um ordinal y, assuma que a hipotese de inducao e verdadeira, isto e,(∀z)(z < y→ ψ(z)) ou, equivalentemente,

(∗) (∀z)(z ∈ y→ (transi(Vz) ∧ Vz+1 ⊆ P(Vz)))

(pois, se y e ordinal, entao z < y sse z ∈ y). Queremos provar que Vy e transi-tivo e Vy+1 ⊆ P(Vy). Pela definicao de Vy temos que

(∗∗) x ∈ Vy sse x ∈ P(Vz) para algum z ∈ y sse x ⊆ Vz para algum z ∈ y.

Fato 1: Seja u transitivo e w ∈ u. Logo w ⊆ u.Com efeito, se z ∈ w, entao: z ∈ w, w ∈ u, transi(u) implica z ∈ u, isto e:z ∈ w implica z ∈ u. Daqui w ⊆ u, provando o Fato 1.Seja entao x ∈ Vy e w ∈ x. Por (∗∗) temos que x ⊆ Vz para algum z ∈ y.Dado que w ∈ x, entao w ∈ Vz. Por (∗) temos que Vz e transitivo, e w ∈ Vz,logo w ⊆ Vz, pelo Fato 1. Portanto w ∈ Vy, por (∗∗). Isto significa que Vy etransitivo se y e um ordinal. Falta provar que Vy+1 ⊆ P(Vy). Por (∗) temos queVz+1 ⊆ P(Vz) para todo z ∈ y, logo Vz+1 = P(Vz) para todo z ∈ y (a inclusaoP(Vz) ⊆ Vz+1 e imediata da Definicao 13.12). Logo

Vy+1 =⋃{P(Vz) : z ∈ y + 1} =

⋃({P(Vz) : z ∈ y} ∪ {P(Vy)})

=⋃

({Vz+1 : z ∈ y} ∪ {P(Vy)}).

Seja x ∈ Vy+1; logo x ∈ u tal que u ∈ {Vz+1 : z ∈ y}∪ {P(Vy)}, pela definicaode

⋃. Temos dois casos:

(a) u = P(Vy). Logo, x ∈ P(Vy).(b) u = Vz+1 para algum z ∈ y. Provaremos primeiro o seguinteFato 2: Se α e β sao ordinais, entao α < β + 1 implica Vα ⊆ Vβ .Com efeito, se α < β, entao: γ ∈ α implica γ ∈ β. Logo, se w ∈ Vα, entaow ∈ P(Vγ) para algum γ ∈ α, pela Definicao 13.12. Daqui w ∈ P(Vγ) ondeγ ∈ β, portanto w ∈ Vβ , isto e, Vα ⊆ Vβ . O caso α = β e obvio. Isto prova oFato 2.

59

Continuando com o caso (b), temos que x ∈ u = Vz+1, onde z ∈ y. Logo existew ∈ z+1 tal que x ∈ P(Vw), pela Definicao 13.12. Mas w ∈ z+1, z ∈ y implicaw ∈ y, pois y e ordinal. Daqui w < y + 1 e entao Vw ⊆ Vy, pelo Fato 2. Dadoque x ∈ P(Vw), entao x ⊆ Vw, donde x ⊆ Vy, isto e, x ∈ P(Vy).Vemos que os dois casos (a) e (b) nos levam a conclusao de que x ∈ P(Vy).Portanto Vy+1 ⊆ P(Vy). Desta maneira provamos ψ(y) a partir da hipotese deinducao. Logo, ψ(x) vale para todo x, isto e: Vα e transitivo e Vα+1 = P(Vα),se α e um ordinal.(iii) Seja λ um ordinal limite. Por (ii) temos que

Vλ =⋃{P(Vβ) : β < λ} =

⋃{Vβ+1 : β < λ}.

Se β < λ entao β + 1 < λ, por [LIM], donde Vβ ⊆ Vλ e Vβ+1 ⊆ Vλ, pelo Fato2. Portanto Vβ ∈ P(Vλ) e Vβ+1 ∈ P(Vλ). Isto significa que existem os conjuntos

a = {Vβ : β < λ} = {x : x ∈ P(Vλ) ∧ (∃β)(β < λ ∧ x = Vβ)},

b = {Vβ+1 : β < λ} = {x : x ∈ P(Vλ) ∧ (∃β)(β < λ ∧ x = Vβ+1)}.

Dado que β < λ implica Vβ ⊆ Vλ, entao⋃a ⊆ Vλ, pela definicao de

⋃. Por

outro lado, como β < λ implica β + 1 < λ entao b ⊆ a, donde Vλ =⋃b ⊆

⋃a,

isto e, Vλ =⋃a como queriamos.

(iv) Considere ψ(x) ≡def (∀α)(x ∈ Vα ↔ ρ(x) < α) (aqui, α e uma variavel deordinais). Provaremos por inducao sobre ∈ que ψ(x) vale para todo x. Seja y,e suponhamos que

(HI) (∀z)(z ∈ y→ ψ(z)).

Queremos provar que vale ψ(y). Fixemos entao um ordinal α.Parte 1: (y ∈ Vα → ρ(y) < α).Assumamos que y ∈ Vα. Se z ∈ y, entao z ∈ Vα, pois Vα e transitivo por (ii).Por (HI) temos que ρ(z) < α, portanto ρ(z) + 1 ≤ α. Suponha que existe z ∈ ytal que α = ρ(z) + 1. Logo, por (ii)

y ∈ Vα = Vρ(z)+1 = P(Vρ(z)).

Daqui y ⊆ Vρ(z); mas z ∈ y, logo z ∈ Vρ(z), e ρ(z) e um ordinal. Por (HI)obtemos que ρ(z) < ρ(z), uma contradicao. Logo ρ(z)+1 < α para todo z ∈ y.Portanto

ρ(y) =⋃{ρ(z) + 1 : z ∈ y} ⊆ α

donde ρ(y) ≤ α. Suponha que α = ρ(y). Dado que y ∈ Vα, entao existe β ∈ αtal que y ∈ P(Vβ), pela Definicao 13.12. Dado que β ∈ α = ρ(y), entao existez ∈ y tal que β ∈ ρ(z)+1. Mas y ∈ P(Vβ), entao y ⊆ Vβ, e z ∈ y, donde z ∈ Vβ.Por (HI) temos que ρ(z) < β. Por outro lado provamos que β ∈ ρ(z) + 1, eentao temos dois casos:

(a) β ∈ ρ(z): logo β ∈ ρ(z) e ρ(z) ∈ β, contradicao.

60

(b) β = ρ(z): logo ρ(z) ∈ β e β = ρ(z), contradicao.

Os dois casos nos levam a uma contradicao, portanto ρ(y) < α. Isto conclui aprova da Parte 1.Parte 2: (ρ(y) < α→ y ∈ Vα).Assumamos que

ρ(y) =⋃{ρ(z) + 1 : z ∈ y} < α.

Suponha que y 6∈ Vα =⋃{P(Vβ) : β < α}. Aplicando a definicao de

⋃obtemos:

(∗ ∗ ∗) para todo β < α existe z ∈ y tal que z 6∈ Vβ

pois y 6∈ P(Vβ) sse y 6⊆ Vβ . Por hipotese ρ(y) < α donde, por (∗∗∗), existe z ∈ ytal que z 6∈ Vρ(y). Dado que z ∈ y e ρ(z) < ρ(z) + 1 entao, por (HI), temos quez ∈ Vρ(z)+1. Mas z ∈ y implica ρ(z) < ρ(y), pela Proposicao 13.11(iv). Logoρ(z)+1 < ρ(y)+1, donde Vρ(z)+1 ⊆ Vρ(y), pelo Fato 2. De z ∈ Vρ(z)+1 obtemosz ∈ Vρ(y), uma contradicao. Portanto y ∈ Vα. Provamos desta maneira a Parte2, obtendo portanto ψ(y). Por inducao transfinita temos que ψ(x) vale paratodo x.(v) Dado x, entao ρ(x) e um ordinal, portanto ρ(x) + 1 e tambem um ordinal,e ρ(x) < ρ(x) + 1. Pelo item (iv) inferimos que x ∈ Vρ(x)+1. �

O teorema anterior e a afirmacao mais forte que podemos fazer em ZF comrelacao a teoria cumulativa de tipos. Provamos desta maneira que os objetosque estudamos na linguagem (reprsentados pelas variaveis livres) pertencem defato a uma estrutura cumulativa. O ordinal ρ(x)+1 indica o nıvel da hierarquiaem que o conjunto x aparece pela primeira vez; portanto o seu posto ρ(x) de-nota exatamente o nıvel em que ele e concebido. Por outro lado, Vα e a colecaode todos os conjuntos que apareceram antes do nıvel α. Logo Vα+1−Vα consistedos conjuntos criados no nıvel α. O fato que ρ(x) + 1 = Min{β : x ∈ Vβ} efacil de ser provado. Com efeito:

(a) ρ(x) < ρ(x) + 1 implica x ∈ Vρ(x)+1;(b) x ∈ Vβ implica ρ(x) < β implica ρ(x) + 1 ≤ β.

Assim, 0 aparece no nıvel 1 (pois o nıvel 0 e vazio); 1 e concebido no nıvel 1 (istoe, ρ(1) = 1 ' 1), logo so aparece no nıvel 2; em geral, n e concebido no nıvelρ(n) = n ' n, portanto aparece pela primeira vez no nıvel seguinte n + 1. Jaω aparece no nıvel ω+1, pois ele e criado no nıvel ω (“infinito”), enquanto queVω consiste de todos os conjuntos que apareceram em nıveis finitos. Em geral,se α e um ordinal, entao α e concebido no nıvel α, logo aparece no nıvel α+ 1,isto e: α ∈ Vα+1 − Vα. Cada nıvel (diferente do nıvel 0) contem exatamenteum ordinal, e cada ordinal denota um nıvel. Neste sentido forte, os ordinaisdescrevem os nıveis da hierarquia cumulativa de tipos.

61

14 Aritmetica Ordinal

Continuaremos estudando nesta secao os ordinais. Primeiro de tudo provaremosque os ordinais sao exatamente os conjuntos bem ordenados, dai a denominacaode ordinais. Lembremos da Definicao 6.10 que bo(r, x) denota que r e uma boaordem em x, e min(v, r, u) denota v ∈ u ∧ (∀w)(w ∈ u→ ¬(w r v)) (v e umelemento r-minimal de u). Introduzimos a seguinte notacao:

Definicao 14.1 bf(r, x) denota (∀u)(u ⊆ x ∧ u 6= ∅ → (∃v)min(v, r, u)(“r e bem fundada sobre x”)

Usando esta definicao, e imediato que bo(r, x) ↔ bf(r, x) ∧ con(r, x), em quecon(r, x) denota que r e conectada em x (lembre da Definicao 6.1). Como foiprovado nas Proposicoes 6.12 e 6.13, uma boa ordem r em x equivale a umaordem estrita r em x tal que todo subconjunto de x nao vazio tem r-primeiroelemento.

Lema 14.2 Seja E(x) = {〈y, z〉 : y, z ∈ x ∧ y ∈ z}. Em S vale o seguinte:(i) Se x e um ordinal, entao E(x) e uma boa ordem em x.(ii) Se r e bem fundada em z, entao φ(x, y) ≡def (x, y ∈ z) ∧ (x r y) e bemfundada (lembre da Definicao 13.3).

Demonstracao: (i) Se x e um ordinal, entao y E(x) z sse y < z para todoy, z ∈ x. Dado que y < z e uma relacao bem fundada, entao E(x) e bemfundada em x. Se y, z ∈ x entao y e x sao ordinais. Pela lei de tricotomia paraordinais temos que E(x) e conectada em x.(ii) Seja r bem fundada em z, e considere φ(x, y) ≡def (x, y ∈ z) ∧ (x r y). Sex 6= ∅, queremos provar o seguinte:

(∗) (∃ v ∈ x)(∀ w ∈ x)(w ∈ z ∧ v ∈ z → ¬(w r v),

pois ¬φ(w, v) ↔ [w ∈ z∧v ∈ z → ¬(w r v)]. Considere u = x∩z ⊆ z. Se u = ∅,entao tomando v ∈ x arbitrario (estamos assumindo que x e nao vazio) obtemos(∗) trivialmente, pois v 6∈ z. Se u 6= ∅ entao, dado que u ⊆ z, temos que existev ∈ u (portanto v ∈ x) tal que ¬(w r v) para todo w ∈ u, pois r e bem fundadaem z. Seja w ∈ x; se w ∈ z e v ∈ z, isto e, se w ∈ z, entao inferimos w ∈ u,donde ¬(w r v). Isto prova (∗), e logo φ(x, y) satisfaz a primeira metade dadefinicao de relacao bem fundada. Para a segunda metade, seja x arbitrario;queremos provar que existe u tal que

(∗∗) x ⊆ u ∧ (∀ w, y)(y ∈ u ∧ φ(w, y) → w ∈ u).

Se x = ∅, entao u = ∅ satisfaz trivialmente (∗∗). Se x 6= ∅ considere

u = x ∪ {w : w ∈ z ∧ (∃ y ∈ z)(w r y)}.

Temos que u 6= ∅ e x ⊆ u. Sejam w e y tais que y ∈ u e φ(w, y), logo: y, w ∈ ze w r y. Daqui w ∈ u, pela definicao de u, portanto vale (∗∗) e entao φ(x, y) ebem fundada. �

62

Lema 14.3 Em ZF provamos o seguinte: se bf(r, z), entao existe

h(x) = {h(y) : y ∈ z ∧ y r x}

para todo x ∈ z.

Demonstracao: Usaremos recursao transfinita para definir os conjuntos h(x).Considere a formula

G(X,x1, y) ≡def (x1 = x1) ∧ (y = im(X)).

Seja F (x, y) a operacao definida a partir de G(X,x1, y) por recursao transfinitana relacao bem fundada φ(x, y) ≡def (x, y ∈ z) ∧ (x r y) (temos que φ(x, y) ebem fundada pelo Lema 14.2(ii)). Por definicao

ANT (F, x, φ(u, v)) = {〈y, F ′〈y〉〉 : φ(y, x)}

portanto, fixado x ∈ z,

F ′〈x〉 = G′〈ANT (F, x, φ(u, v)), x〉= im(ANT (F, x, φ(u, v))= {F ′〈y〉 : φ(y, x)}= {F ′〈y〉 : x, y ∈ z ∧ y r x}= {F ′〈y〉 : y ∈ z ∧ y r x}.

Desta maneira, F (x, y) representa a operacao h(x) desejada para todo x ∈ z. �

Teorema 14.4 (Caracterizacao dos Ordinais) Em ZF prova-se: se r e umaboa ordem em z, entao existe um ordinal α tal que

h : z−→ α, h(x) = {h(y) : y ∈ z ∧ y r x}

e um isomorfismo de conjuntos bem ordenados, isto e: h e uma bijecao tal que:x r y sse h(x) < h(y). O ordinal α e o isomorfismo h sao unicos.

Demonstracao: Seja r uma boa ordem em z; logo, bf(r, z) donde existe h(x)para todo x ∈ z, pelo Lema 14.3. Seja

r∗ = (r|z) ∪ {〈y, z〉 : y ∈ z}

lembrando que r|z = {〈x, y〉 : x ∈ z ∧ x r y}. Provaremos que r∗ e bemfundada em z + 1. Seja entao u ⊆ z + 1, u 6= ∅.Caso 1: u ⊆ z. Como bf(r, z), existe v ∈ u tal que ¬(w r v) para todo w ∈ u.Pela construcao de r∗, temos que ¬(w r∗ v) para todo w ∈ u pois r coincidecom r∗ em z × z.Caso 2: u = {z} ∪ u1 tal que u1 ⊆ z. Se u1 = ∅ entao v = z satisfaz: v ∈ ue ¬(w r∗ v) para todo w ∈ u. Se u1 6= ∅ entao u1 ⊆ z e nao vazio, logo existev ∈ u1 tal que ¬(w r v) para todo w ∈ u1. Como ¬(z r∗ v), pela construcao de

63

r∗, entao ¬(w r∗ v) para todo w ∈ u.Isto prova que bf(r∗, z + 1). Pelo Lema 14.3 inferimos que existe

h∗(x) = {h∗(y) : (y ∈ z + 1) ∧ (y r∗ x)}

para todo x ∈ z + 1.Fato 1: h∗(x) = h(x) para todo x ∈ z.Com efeito: seja ψ(x) ≡def (x ∈ z → h∗(x) = h(x)). Fixemos y tal que

(HI) (∀w)(φ(w, y) → ψ(w)),

onde φ(u, v) ≡def (u, v ∈ z)∧(u r v) e uma relacao bem fundada, pelo Lema 14.2(ii).Suponhamos que y ∈ z; logo, pela construcao de r∗:

h∗(y) = {h∗(w) : (w ∈ z + 1) ∧ (w r∗ y)}= {h∗(w) : w ∈ z ∧ w r y}= {h∗(w) : φ(w, y)}.

Por (HI) temos que ψ(w) para todo w tal que φ(w, y). Como φ(w, y) implica w ∈z, entao obtemos que h∗(w) = h(w) para todo w tal que φ(w, y). Daqui h∗(y) =h(y). Por inducao transfinita sobre φ(x, y) inferimos que ψ(x) e verdadeira paratodo x como queriamos, provando o Fato 1.A partir do Fato 1 e da definicao de r∗ obtemos

h∗(z) = {h∗(y) : (y ∈ z + 1) ∧ (y r∗ z)} = {h∗(y) : y ∈ z} = {h(y) : y ∈ z}.

Seja α ≡def h∗(z). Provaremos que α e um ordinal. Seja x ∈ h(y), y ∈ z. Logox = h(w) tal que w ∈ z, pelas definicoes de h(y) e φ(w, y), portanto x ∈ α;daqui α e transitivo. Sejam h(x), h(y) ∈ α. Como x, y ∈ z, entao y = x ouy r x ou x r y. Se x = y entao h(x) = h(y). O caso em que y r x implicah(y) ∈ h(x). Se x r y entao h(x) ∈ h(y). Vemos assim que α e conectado. Daquiobtemos que α e um ordinal, portanto h(x) e um ordinal para todo x ∈ z, e αe bem ordenado pela relacao E(α) = <, pelo Lema 14.2(i). A propriedade x ry sse h(x) < h(y) e imediata, logo h : z−→ α e um isomorfismo de conjuntosbem ordenados. Para provar a unicidade de α, suponha que 〈z, r〉 e isomorfoa 〈β,<〉 via g : z−→ β para um outro ordinal β. Logo g ◦ h−1 : α−→ β e umisomorfismo.Fato 2: Sejam α e β ordinais, e f : α−→ β un isomorfismo, isto e: f e umabijecao tal que γ < δ sse f(γ) < f(δ) para todo γ, δ ∈ α. Logo f(γ) = {f(δ) :δ < γ}, donde f(γ) = γ para todo γ ∈ α.Com efeito, se δ < γ < α, entao f(δ) ∈ f(γ). Por outro lado, seja θ ∈ f(γ);entao θ = f(δ) para δ ∈ α, pois f e sobrejetora. Daqui f(δ) < f(γ) implica δ <γ, e entao θ = f(δ) com δ < γ, isto e: f(γ) = {f(δ) : δ < γ}. Considerando aformula

ψ(x) ≡def x ∈ α→ f(x) = x

entao e agora muito simples provar por inducao sobre ∈ que ψ(x) vale paratodo x (exercıcio!), concluindo a prova do Fato 2.

64

Temos que g ◦ h−1 : α−→ β e um isomorfismo. Pelo Fato 2, g ◦ h−1(x) = xpara todo x ∈ α. Mas g ◦ h−1 e sobrejetora, portanto α = β, e g ◦ h−1 = I(α).Daqui g = h (compondo a direita com h). Isto mostra que α e h sao unicospara cada 〈z, r〉. �

Pelo Lema 14.2(i) vemos que todo ordinal α e bem ordenado pela relacao <.Reciprocamente, pelo Teorema 14.4, se z e um conjunto bem ordenado por umarelacao r entao existe um unico ordinal α e um unico isomorphismo h : z−→ αde conjuntos bem ordenados tal que 〈z, r〉 ' 〈α,<〉. O ordinal α associado com〈z, r〉 e dito o tipo ordinal de 〈z, r〉. Observe que o tipo ordinal α de z dependeda relacao r: com efeito, z pode possuir duas estruturas de boa ordem r1 e r2nao isomorfas, de maneira a ter associados dois tipos ordinais, α1 para 〈z, r1〉 eα2 para 〈z, r2〉 com α1 6= α2.

Exemplo 14.5 Considere em N a estrutura usual r1 de boa ordem: n r1 msse n < m. Logo, h1 : N−→ ω dada por h1(n) = n e o unico isomorfismo de〈N, r1〉 em 〈ω,<〉 tal que ω e o tipo ordinal de 〈N, r1〉. Por outro lado, considerea seguinte relacao r2 em N:

n r2 m se n,m > 0 e n < m;n r2 0 para todo n > 0.

Isto e: r2 coincide com a boa ordem usual < para todos os numeros naturaispositivos, e 0 e colocado como r2-ultimo elemento de N. E muito simples verque r2 e uma boa ordem em N (conferir!). Considere h2 : N−→ ω + 1 dada por

h2(n) ={

n− 1 se n > 0ω se n = 0

.

Temos que h2 e um isomorfismo entre 〈N, r2〉 e 〈ω + 1, <〉 (conferir!), portantoω + 1 e o tipo ordinal de 〈N, r2〉, sendo que ω 6= ω + 1. Isto mostra que o tipoordinal de um conjunto bem ordenado depende da boa ordem especificada. �

Definicao 14.6 Sejam α e β ordinais. Definimos a soma ordinal α+ β comosendo

α+ β =

α se β = 0

(α+ γ) + 1 se β = γ + 1⋃γ<β (α+ γ) se β e limite ordinal

.

Para provar que a soma esta bem definida, precisamos introduzir uma relacaobem fundada apropriada.

Lema 14.7 Considere a formula

φ(u, v) ≡def (ord(u) ∧ ord(v)) ∧ [(∃z)(v = z + 1 ∧ u = z) ∨ (lim(v) ∧ u ∈ v)].

65

Entao φ(u, v) e uma relacao bem fundada.

Demonstracao: Seja x 6= ∅. Pelo axioma da regularidade, existe v ∈ x talque (∀ z ∈ x)(z 6∈ v). Logo, v 6= z + 1 para todo z ∈ x, e entao nao vale(∃z)(v = z + 1 ∧ u = z) para todo u ∈ x. Se v e um ordinal limite entao, dadoque z 6∈ v para todo z ∈ x, inferimos que nao vale (lim(v) ∧ u ∈ v) para todou ∈ x. Desta maneira obtemos: u ∈ x→ ¬φ(u, v), donde

x 6= ∅ → (∃ v ∈ x)(∀ w ∈ x)¬φ(w, v).

Para provar a segunda parte da Definicao 13.3 de relacao bem fundada, sejax arbitrario, e considere u = FT (x), o fecho transitivo de x. Seja y ∈ u e wtal que φ(w, y). Se z e um conjunto transitivo tal que x ∈ z entao y ∈ z, poisy ∈ FT (x). Dado que φ(w, y), entao w ∈ y (e uma consequencia direta dadefinicao de φ), logo w ∈ z (pois z e transitivo). Daqui w ∈ FT (x) = u, donde

(∃u)(x ⊆ u ∧ (∀ w, y)(y ∈ u ∧ φ(w, y) → w ∈ u)).

Isto prova que φ(u, v) e uma relacao bem fundada. �

Lema 14.8 Seja b um conjunto de ordinais, isto e: (∀x)(x ∈ b→ ord(x)).Logo

⋃b e um ordinal.

Demonstracao: Seja a =⋃b. Considere x ∈ a e y ∈ x. Logo, existe z ∈ b

tal que x ∈ z. Por hipotese z e um ordinal, e y ∈ x, x ∈ z; portanto y ∈ zcom z ∈ b, donde y ∈ a. Isto mostra que a e transitivo. Por outro lado, sejamx, y ∈ a; logo existem z, w ∈ b tais que x ∈ z e y ∈ w. Por hipotese z e w saoordinais, logo x e y sao ordinais. Portanto x = y ou x ∈ y ou y ∈ x pela leide tricotomia para ordinais. Isto prova que a e conectado para ∈, portanto a eum ordinal. �

Proposicao 14.9 A soma ordinal esta bem definida em ZF, isto e, para cadaordinal α e β, existe um unico conjunto α + β definido de acordo com a Defi-nicao 14.6.

Demonstracao: Para provar que a soma ordinal esta bem definida usaremosrecursao transfinita sobre a relacao bem fundada φ(u, v) do Lema 14.7. Con-sidere a seguinte formula:

G(X,x1, x2, y) ≡def [x1 = 0∧y = x2]∨ [(∃z)(x1 = z+1)∧y = (⋃im(X))+1]

∨ [lim(x1) ∧ y =⋃im(X)].

Logo, definimos por recursao transfinita sobre φ(u, v) uma operacao F (x1, x2, y).Temos que, se x1 e um ordinal, entao

ANT (F,0, x2, φ(u, v)) = {〈〈w, x2〉, F ′〈w, x2〉〉 : φ(w,0)} = ∅,

ANT (F, z + 1, x2, φ(u, v)) = {〈〈w, x2〉, F ′〈w, x2〉〉 : φ(w, z + 1)}

66

= {〈〈z, x2〉, F ′〈z, x2〉〉},

ANT (F, x1, x2, φ(u, v)) = {〈〈w, x2〉, F ′〈w, x2〉〉 : φ(w, x1)}= {〈〈w, x2〉, F ′〈w, x2〉〉 : w ∈ x1}

segundo o caso: x1 = 0, x1 = z+ 1 ou x1 e um ordinal limite, respectivamente.Obtemos assim em cada caso:

im(ANT (F,0, x2, φ(u, v))) = ∅,

im(ANT (F, z + 1, x2, φ(u, v))) = {F ′〈z, x2〉},

im(ANT (F, x1, x2, φ(u, v))) = {F ′〈w, x2〉 : w ∈ x1},

respectivamente. Portanto, se α e β sao ordinais, entao

F ′〈0, α〉 = G′〈ANT (F,0, α, φ(u, v)),0, α〉 = α,

F ′〈γ + 1, α〉 = G′〈ANT (F, γ + 1, α, φ(u, v)), γ + 1, α〉 = (⋃{F ′〈γ, α〉}) + 1

= (F ′〈γ, α〉) + 1,

F ′〈β, α〉 = G′〈ANT (F, β, α, φ(u, v)), β, α〉 =⋃{F ′〈γ, α〉 : γ ∈ β}

segundo o caso: β = 0, β = γ + 1 ou β e um ordinal limite, respectivamente.Desta maneira F ′〈β, α〉 = α + β e definido de acordo com 14.6; isto e, semprepodemos definir o conjunto α+ β. �

Proposicao 14.10 Sejam α e β ordinais. Entao α+ β e um ordinal.

Demonstracao: Considere a formula

ψ(x) ≡def ord(x) → (∀z)(ord(z) → ord(z + x)).

Provaremos por inducao sobre φ(u, v) (Lema 14.7) que ψ(x) vale para todo x;logo teremos que α + β e um ordinal para todo ordinal α e β. Seja y um con-junto satisfazendo

(HI) (∀w)(φ(w, y) → ψ(w)).

Queremos provar que vale ψ(y). Suponhamos entao que y e um ordinal, e sejaz um ordinal. Provaremos que z + y e um ordinal. Temos tres casos:(a) y = 0. Logo z + y = z, portanto z + y e um ordinal.(b) y = w + 1. Logo temos que φ(w, y), portanto vale ψ(w), por (HI). Como ye um ordinal e w ∈ y, entao w e um ordinal, logo ord(z) → ord(z+w). Mas z eum ordinal, portanto z+w e um ordinal. Daqui inferimos que z+y = (z+w)+1e um ordinal.

67

(c) y e um ordinal limite. Se w ∈ y entao vale φ(w, y), donde vale ψ(w) por(HI). Dado que w ∈ y implica que w e um ordinal, entao, como antes, obtemosque z + w e um ordinal para todo w ∈ y. Pelo Lema 14.8 deduzimos que

z + y =⋃{z + w : w ∈ y}

e um ordinal.Portanto, em todos os casos possıveis temos que z + y e um ordinal, provandoque (HI) implica ord(y) → (∀z)(ord(z) → ord(z+y)), isto e, ψ(y). Por inducaotransfinita inferimos que ψ(x) vale para todo x. �

Proposicao 14.11 Sejam α, β e γ ordinais. Entao β < γ implica que α+β <α+ γ.

Demonstracao: Considere a formula

ψ(x) ≡def ord(x) → (∀y)(y < x→ (∀z)(ord(z) → (z + y < z + x))).

Por inducao sobre a formula φ(u, v) do Lema 14.7 provaremos que ψ(x) valepara todo x. Suponha que temos

(HI) (∀w)(φ(w, x) → ψ(w)).

Queremos provar ψ(x). Suponha que x e um ordinal.(1) Se x = 0 entao y < x e falso para todo y, portanto

(∀y)(y < x→ (∀z)(ord(z) → (z + y < z + x)))

e trivialmente verdadeiro.(2) Se x = w + 1, considere y < x e z um ordinal.(2.1) Se y = w entao z + w < (z + w) + 1 = z + (w + 1) = z + x.(2.2) Se y ∈ w entao, dado que φ(w, x), obtemos ψ(w) por (HI), portantoz + y < z + w (pois y < w). Mas z + w < z + x (caso 2.1), logo z + y < z + x.(3) Se x e um ordinal limite, seja y < x e z um ordinal. Como (z+y) ∈ (z+(y+1)) (caso 2.1) e y+1 ∈ x, pois x e limite, entao z+y ∈

⋃{z+w : w ∈ x} = z+x.

Em todos os casos temos que (∀y)(y < x→ (∀z)(ord(z) → (z + y < z + x))) everdadeiro. Portanto (HI) implica ψ(x) donde ψ(x) vale para todo x. �

Proposicao 14.12 α+ (β + γ) = (α+ β) + γ para todo ordinal α, β e γ.

Demonstracao: Considere a formula

ψ(z) ≡def ord(z) → (∀ x, y)(ord(x) ∧ ord(y) → ((x+ y) + z = x+ (y + z))).

Por inducao na relacao φ(u, v) do Lema 14.7 provaremos que ψ(x) vale paratodo x. Seja z tal que

(HI) (∀w)(φ(w, z) → ψ(w)).

68

Suponha que z e ordinal, e sejam x, y ordinais.(1) Se z = 0, entao (x+ y) + z = x+ y = x+ (y + 0) = x+ (y + z).(2) Se z = w + 1, entao temos φ(w, z), donde vale ψ(w) por (HI). Daqui

(x+ y) + z = (x+ y) + (w + 1) = ((x+ y) + w) + 1=HI (x+ (y + w)) + 1 = x+ ((y + w) + 1)= x+ (y + (w + 1)) = x+ (y + z).

(3) Se z e limite, entao provaremos primeiro os seguintesFatos: Seja γ ordinal limite.(a) Se x ∈ α+ θ tal que θ ∈ β + γ entao existe δ < γ tal que x ∈ α+ (β + δ).(b) β + γ e um ordinal limite.Com efeito, seja x ∈ α + θ tal que θ ∈ β + γ. Logo θ ∈ β + δ tal que δ ∈ γ.De θ < β + δ inferimos que α + θ < α + (β + δ), pela Proposicao 14.11. Logox ∈ α+(β+δ) para algum δ ∈ γ, provando o item (a). Para provar (b), observeque β + γ =

⋃{β + δ : δ ∈ γ} e nao vazio. Seja u ∈ β + γ, logo u ∈ β + δ

para algum δ ∈ γ. Daqui u + 1 ∈ (β + δ) + 1 = β + (δ + 1), onde δ + 1 ∈ γ.Assim u+ 1 ∈ β + γ, donde β + γ e um ordinal limite, por [LIM]. Isto concluia demonstracao dos Fatos.Por causa dos Fatos(b) obtemos que y+z e um ordinal limite, e pelos Fatos(a)

x+ (y + z) =⋃{x+ w : w ∈ y + z} ⊆

⋃{x+ (y + w) : w ∈ z}.

Alem disso, se w ∈ z entao (y + w) ∈ (y + z) pela Proposicao 14.11, logo:

u ∈ x+ (y + w) para w ∈ z implica u ∈ x+ w′ com w′ ∈ y + z

implica u ∈⋃{x+ w : w ∈ y + z},

donde ⋃{x+ (y + w) : w ∈ z} ⊆

⋃{x+ w : w ∈ y + z}

e assim

x+ (y + z) =⋃{x+ w : w ∈ y + z} =

⋃{x+ (y + w) : w ∈ z}.

Mas, para todo w ∈ z temos que φ(w, z) e satisfeita, logo vale ψ(w) por (HI),donde x+ (y + w) = (x+ y) + w para todo w ∈ z. Portanto

x+(y+z) =⋃{x+(y+w) : w ∈ z} =

⋃{(x+y)+w : w ∈ z} = (x+y)+z.

Acabamos de provar que (HI) implica ψ(z). Por inducao transfinita obtemosque ψ(z) vale para todo z. �

Lema 14.13 Seja α um ordinal limite. Entao α =⋃α.

Demonstracao: Seja x ∈ α; logo, x+1 ∈ α. Portanto x ∈ x+1 com x+1 ∈ α,donde x ∈

⋃α. Daqui obtemos que α ⊆

⋃α. Reciprocamente, seja x ∈

⋃α;

logo x ∈ y para algum y ∈ α; dado que α e transitivo, entao x ∈ α. Portanto⋃α ⊆ α. Desta maneira, temos que α =

⋃α. �

69

Proposicao 14.14 Seja α um ordinal. Vale o seguinte:(i) 0 + α = α.(ii) α+ 1 = α+ 1.

Demonstracao: (i) Por inducao na relacao φ(u, v) do Lema 14.7, provaremosque (∀x)ψ(x), onde

ψ(x) ≡def ord(x) → (0 + x = x).

Seja x um conjunto satisfazendo

(HI) (∀z)(φ(z, x) → ψ(z)).

Assuma que x e um ordinal. Temos tres casos para analizar:(a) x = 0. Logo 0 + x = 0 + 0 = 0 = x.(b) x = z + 1. Logo φ(z, x) e ord(z), portanto 0 + z = z, por (HI). Daqui

0 + x = 0 + (z + 1) = (0 + z) + 1 = z + 1 = x.

(c) x e um ordinal limite. Se z ∈ x, entao φ(z, x) e ord(z), portanto 0 + z = z,por (HI). Daqui

0 + x =⋃{0 + z : z ∈ x} =

⋃{z : z ∈ x} =

⋃x = x

pelo Lema 14.13. Vemos que nos tres casos possıveis 0 + x = x. Portanto (HI)implica ψ(x) donde, por inducao transfinita, obtemos que ψ(x) e verdadeirapara todo x.(ii) Temos que 1 = 0 + 1, pela definicao de 1. Logo

α+ 1 = α+ (0 + 1) = (α+ 0) + 1 = α+ 1.

�

Definiremos agora o produto de ordinais.

Definicao 14.15 Sejam α e β ordinais. Definimos o produto ordinal α·β comosendo

α · 0 = 0;α · (β + 1) = (α · β) + α;α · β =

⋃γ<β α · γ se β e ordinal limite.

Como foi feito com a soma ordinal, podemos provar que α ·β pode ser definido,e α · β e um ordinal. A relacao funcional G(X,x1, x2, y) utilizada para definirF (x1, x2, y) tal que F ′〈β, α〉 = α · β e dada neste caso por

G(X,x1, x2, y) ≡def [x1 = 0∧y = 0]∨[(∃z)(x1 = z+1)∧y = (⋃im(X))+x2]

∨ [lim(x1) ∧ y =⋃im(X)]

(confira os detalhes!).

70

Proposicao 14.16 Seja α um ordinal. Logo 0 · α = 0.

Demonstracao: Por inducao na relacao φ(u, v) do Lema 14.7, provaremos que(∀x)ψ(x), onde

ψ(x) ≡def ord(x) → (0 · x = 0).

Seja x um conjunto satisfazendo

(HI) (∀z)(φ(z, x) → ψ(z)).

Assuma que x e um ordinal. Temos tres casos para analizar:(a) x = 0. Logo 0 · x = 0 · 0 = 0.(b) x = z + 1. Logo φ(z, x) e ord(z), portanto 0 · z = 0, por (HI). Daqui

0 · x = 0 · (z + 1) = (0 · z) + 0 = 0 + 0 = 0.

(c) x e um ordinal limite. Se z ∈ x, entao φ(z, x) e ord(z), portanto 0 · z = 0,por (HI). Daqui

0 · x =⋃{0 · z : z ∈ x} =

⋃{0 : z ∈ x} =

⋃{0} = 0.

Vemos que nos tres casos possıveis 0 ·x = 0. Portanto (HI) implica ψ(x) donde,por inducao transfinita, obtemos que ψ(x) e verdadeira para todo x. �

Proposicao 14.17 Seja α um ordinal. Entao α · 1 = α = 1 · α.

Demonstracao: Por inducao na relacao φ(u, v) do Lema 14.7, provaremos que(∀x)ψ(x), onde

ψ(x) ≡def ord(x) → (1 · x = x).

Seja x um conjunto satisfazendo

(HI) (∀z)(φ(z, x) → ψ(z)).

Assuma que x e um ordinal. Temos tres casos para analizar:(a) x = 0. Logo 1 · x = 1 · 0 = 0 = x.(b) x = z + 1. Logo φ(z, x) e ord(z), portanto 1 · z = z, por (HI). Daqui

1 · x = 1 · (z + 1) = (1 · z) + 1 = z + 1 = z + 1 = x.

(c) x e um ordinal limite. Se z ∈ x, entao φ(z, x) e ord(z), portanto 1 · z = z,por (HI). Daqui

1 · x =⋃{1 · z : z ∈ x} =

⋃{z : z ∈ x} =

⋃z = z

pelo Lema 14.13. Daqui 1 · x = x em todos os casos. Assim (HI) implicaψ(x) donde, por inducao transfinita, inferimos que (∀x)ψ(x). A segunda partee provada diretamente:

x · 1 = x · (0 + 1) = (x · 0) + x = 0 + x = x

pelo Lema 14.14(i). �

71

Proposicao 14.18 Se α > 0 e β e ordinal limite, entao α · β e um ordinallimite.

Demonstracao: Por definicao temos que

α · β =⋃{α · γ : γ ∈ β},

portanto α · β 6= 0. Seja x ∈ α · β; logo x ∈ α · γ para algum γ ∈ β, dondex+ 1 ∈ (α · γ) + 1. Dado que α < 1 sse α = 0 entao, pela lei de tricotomia dosordinais, temos dois casos para serem analizados:(a) α = 1. Logo

(α · γ) + 1 = (α · γ) + 1 = (α · γ) + α = α · (γ + 1).

Mas γ + 1 ∈ β, pois γ ∈ β e β e ordinal limite. Daqui x+ 1 ∈ α · β.(b) 1 < α. Pelo Lema 14.14(ii) e a Proposicao 14.11 inferimos:

(α · γ) + 1 = (α · γ) + 1 < (α · γ) + α = α · (γ + 1).

Daqui x + 1 ∈ α · (γ + 1) onde γ + 1 ∈ β, pois γ ∈ β e β e um ordinal limite.Portanto x + 1 ∈ α · β. Nos dois casos possıveis para α obtemos: x ∈ α · βimplica x+ 1 ∈ α ·β. Isto prova que α ·β e um ordinal limite, pela propriedade[LIM] (introduzida logo apos a Definicao 12.7). �

Por inducao transfinita pode ser provado o seguinte:

Proposicao 14.19 Sejam α, β e γ ordinais. Em ZF vale o seguinte:(a) α · (β + γ) = (α · β) + (α · γ).(b) α · (β · γ) = (α · β) · γ.

Definiremos agora a exponenciacao ordinal.

Definicao 14.20 Sejam α e β ordinais. A exponenciacao ordinal αβ e definidada maneira seguinte:

α0 = 1;αβ+1 = αβ · α;αβ =

⋃γ∈β α

γ se β e ordinal limite e 0 < α;αβ = 0 se β e ordinal limite e α = 0.

Podemos provar como antes que a definicao acima e legitimada em ZF por re-cursao transfinita em φ(u, v) (Lema 14.7) utilizando

G(X,x1, x2, y) ≡def [x1 = 0∧y = 1]∨ [(∃z)(x1 = z+1)∧y = (⋃im(X)) ·x2]

∨ [lim(x1) ∧ x2 6= 0 ∧ y =⋃im(X)]

∨ [lim(x1) ∧ x2 = 0 ∧ y = 0]

para definir uma operacao F (x1, x2, y) tal que F ′〈β, α〉 = αβ (confira os deta-lhes!). Por inducao transfinita pode ser provado o seguinte:

72

Proposicao 14.21 Sejam α, β e γ ordinais. Em ZF valem as seguintes pro-priedades:(a) αβ e um ordinal.(b) α1 = α.(c) Se β > 0 entao 0β = 0.(d) 1α = 1.(e) αβ+γ = αβ · αγ.(f) (αβ)γ = αβ·γ.

Observacao 14.22 Se bem as operacoes de soma, produto e exponenciacaoordinal possuem propriedades analogas as propriedades das mesmas operacoesnumericas, existem algumas diferencias notorias. Certas asimetrias (nao comu-tatividade da soma e o produto, por exemplo) aparecem por causa das propriasdefinicoes, feitas por recursao transfinita numa so das variaveis. Podemosdestacar os seguintes exemplos em que as operacoes sao “mal comportadas”:

1 + ω = ω 6= ω + 1; logo a soma ordinal nao e comutativa.

2 · ω = ω 6= ω · 2, logo o produto ordinal nao e comutativo.

(1 + 1) · ω = 2 · ω = ω 6= (1 · ω) + (1 · ω);

logo o produto ordinal nao e distributivo a direita da soma ordinal. �

15 Cardinais

Finalmente estudaremos a nocao de numero cardinal. Os cardinais foram in-troduzidos originalmente por Frege e Russell para indicar o “tamanho” dosconjuntos. A ideia intuitiva e que dois conjuntos a e b “tem o mesmo tamanho”(ou seja, o cardinal de a e igual ao cardinal de b) se existe uma bijecao entreeles, isto e, se sao equipolentes. Portanto a definicao natural de cardinal de umconjunto a, denotado por

=a, e a colecao de todos os conjuntos b equipolentes

com a. Isto e, a partir da relacao de equivalencia ≈ (equipolencia), definimos

=a = {b : a ≈ b}.

Portanto o cardinal de um conjunto a, na concepcao de Frege e Russell, e a classede equivalencia de a na relacao ≈. O problema que apresenta esta definicao eque

=a e uma classe propria, isto e, o cardinal de a nao pode ser legitimado em

ZF (nem em ZFC); se=a fosse legitimado, podemos provar que

⋃ =a e o conjunto

de todos os conjuntos, uma contradicao. A solucao para este problema e definiro cardinal de um conjunto a partir da teoria de ordinais. A definicao e feitade maneira a escolher um conjunto (ordinal) equipolente a x; de fato, o ordinalescolhido sera o menor ordinal equipolente com x. Como ja parece evidente, ateoria de cardinais faz um uso pesado do Axioma da Escolha [AE]. A partir de[AE] poderemos provar a Lei de Tricotomia que estabelece que a relacao � etotal entre conjuntos (isto e, dados x e y, entao x � y ou y � x), assim como

73

demonstrar que todo conjunto e similar a um ordinal (o teorema da boa ordem:todo conjunto x admite uma boa ordem). Na primeira parte desta exposicaonao utilizaremos [AE], mas ele devera ser considerado posteriormente, fato quesera oportunamente informado. Comecamos reformulando a nocao de conjuntofinito, agora utilizando a representacao dos numeros naturais em ZF.

Definicao 15.1 FIN(x) denota (∃n)(n ∈ ω ∧ x ≈ n)(“x e n-finito”);INFIN(x) denota ¬FIN(x)(“x e infinito”);ENUM(x) denota x ≈ ω(“x e enumeravel”).

Antes de provar as seguintes propriedades precisamos do seguinte resultado.

Lema 15.2 Seja α um inteiro. Entao α ≺ α+ 1.

Demonstracao: Seja α um inteiro, e f : α−→ α+ 1 dada por f(x) = x; logof e injetora, portanto α � α+ 1, pela definicao de �. Provaremos por inducaomatematica que (∀x)ψ(x), onde

ψ(x) ≡def int(x) → (x 6≈ x+ 1).

E imediato que 0 6≈ 1 = 0+1, portanto vale ψ(0). Suponha que vale ψ(y); paraprovar ψ(y+1), suponha que y+1 e um inteiro, logo y e um inteiro, pois y ∈ y+1,portanto y 6≈ y+1. Suponhamos que existe uma bijecao f : y+1−→(y+1)+1;daqui inferimos que f |y e uma bijecao entre y e ((y + 1) + 1)− {f(y)}.Fato: Seja z um conjunto, e v ∈ z + 1. Portanto (z + 1)− {v} ≈ z.Com efeito, se v = z entao (z + 1)− {v} = z, e a equipolencia e imediata. Poroutro lado, se v ∈ z entao definimos g : ((z + 1) − {v})−→z como g(u) = u seu 6= z, e g(z) = v. E claro que g e uma bijecao; isto conclui a prova do Fato.Vemos entao que, por um lado, f |y e uma bijecao estabelecendo que y ≈ ((y +1) + 1)− {f(y)} enquanto que, por outro lado, ((y + 1) + 1)− {f(y)} ≈ y + 1,em virtude do Fato; portanto y ≈ y+ 1, uma contradicao. Daqui obtemos quey+1 6≈ (y+1)+1. Desta maneira ψ(y) implica int(y+1) → y+1 6≈ ((y+1)+1),isto e, provamos que ψ(y) → ψ(y + 1). Por inducao matematica obtemos que(∀x)(int(x) → ψ(x)) ou, equivalentemente, (∀x)ψ(x), isto e, α 6≈ α + 1 paratodo inteiro α. Como α � α + 1, entao deduzimos que α ≺ α + 1 para todointeiro α. �

Proposicao 15.3 (i) Em S vale o seguinte: se x e y sao inteiros, entao x � ysse x ≤ y.(ii) Em Z vale o seguinte: ω e infinito.

Demonstracao: (i) Provaremos por inducao matematica que para todo x valeψ(x), onde

ψ(x) ≡def int(x) → (∀y)(int(y) → (x � y→ x ≤ y)).

74

E imediato que ψ(0) e verdadeira (confira!). Seja x tal que ψ(x) e verdadeira.Para provar ψ(x+1), assuma que x+1 e um inteiro; logo x e um inteiro, donde

(∗) (∀y)(int(y) → (x � y→ x ≤ y))

pois vale ψ(x). Suponha que y e um inteiro tal que x+ 1 � y. Como x ≺ x+ 1(pelo Lema 15.2), entao x ≺ y; por (∗) inferimos que x < y (nao poderiamoster x = y, senao x ≈ y, o que contradiz x ≺ y), portanto x+ 1 ≤ y. Logo ψ(x)implica ψ(x+ 1). Por inducao matematica obtemos que ψ(x) vale para todo x,provando assim a primeira metade de (i). A outra implicacao e imediata: x ≤ yimplica x � y para todo ordinal x e y.(ii) Suponhamos que ω e n-finito, isto e, existe um inteiro n tal que ω ≈ n.Daqui inferimos que ω ≈ n e n ≺ n + 1, pelo Lema 15.2, logo ω ≺ n + 1. Masn+1 = n + 1, logo n+1 � ω (pois n + 1 ⊆ ω). Portanto n+1 � ω, ω ≺ n+1implica n + 1 ≺ n + 1, uma contradicao. Daqui obtemos que ω e infinito. �

Definicao 15.4 inic(α) denota ord(α) ∧ (∀β)(β < α→ (α 6≈ β))(“α e um ordinal inicial”).

Pela Proposicao 15.3(i) vemos que todo ordinal n-finito n e um ordinal inicial:se β ≈ n entao β � n e n � β, donde β ≤ n e n ≤ β. Pela tricotomia dosordinais inferimos que β = n, e entao β 6< n. Por 15.3(ii) e pela definicao de ωe imediato que ω e tambem um ordinal inicial. Por outro lado, e simples provarque

ω ≈ ω + 1 ≈ ω + 2 ≈ · · · ≈ ω + ω = ω · 2 ≈ ω · 3 ≈ · · ·

junto comω ≈ ω2 ≈ ω3 ≈ · · · ≈ ωω ≈ ωω

ω ≈ · · · etc.

(confira!). Pode ser provado que nenhuma das operacoes sobre ordinais consegueproduzir um ordinal inicial superior a partir de ω. Para superar esta barreiradevemos considerar o conjunto das partes P(x); uma maneira possıvel e atravesda funcao aleph de Hartogs:

Definicao 15.5 ℵ(x) denota {α : α � x}(“o aleph de x”).

Proposicao 15.6 Em ZF provamos que ℵ(x) e legitimado, e ℵ(x) e um ordinalinicial para todo conjunto x.

Demonstracao: Dado um conjunto x, considere o seguinte conjunto:

z = {r : (∃y)(y ⊆ x ∧ r ⊆ y × y ∧ bo(r, y))}.

Dado que z ⊆ P(x × x), entao z e legitimado por [A2]. Por outro lado, lem-brando que F (r) denota o conjunto dom(r)∪im(r), considere a seguinte formula:

75

isom(r, α) ≡def (∃h)(bij(h, F (r), α) ∧ (∀x)(∀y)(x, y ∈ F (r)→ (((x r y) ↔ h(x) < h(y)))).

O teorema de caracterizacao dos ordinais prova que se r e uma boa ordem sobrea = F (r), entao (∃!α)isom(r, α) (onde (∃!) indica existencia e unicidade). Logo,a formula

ψ(r, α) ≡def bo(r, F (r)) ∧ isom(r, α)

satisfaz a condicao FUNψ do axioma de substituicao [A7], portanto existe oconjunto

b = {α : (∃r)(r ∈ z ∧ ψ(r, α))} = {α : (∃r)(r ∈ z ∧ isom(F (r), α)}.

Pela definicao de z e dado que (∃!α)isom(F (r), α) para todo r ∈ z, sendo queF (r) ⊆ x, vemos que b = ℵ(x), portanto o conjunto ℵ(x) e legitimado para todoconjunto x. Para provar que ℵ(x) e um ordinal basta provar que e transitivo,pois ℵ(x) e um conjunto de ordinais. Considere entao α ∈ ℵ(x) e β < α. Logo:β ⊆ α e α � x, donde β � x. Daqui β ∈ ℵ(x) e ℵ(x) e transitivo, sendoportanto um ordinal. Suponha que existe β < ℵ(x) tal que ℵ(x) ≈ β. Dadoque β ∈ ℵ(x), entao obtemos que β � x, donde ℵ(x) � x. Daqui ℵ(x) ∈ ℵ(x),uma contradicao. Logo ℵ(x) e um ordinal inicial. �

Observe que, se α e um ordinal, entao α ∈ ℵ(α), pois α � α. Portanto α < ℵ(α).Isto significa que, para cada ordinal α, existe um ordinal inicial ℵ(α) maior doque α. Pelo Teorema de Cantor-Schroder-Bernstein ℵ(α) deve ser o seguinteordinal inicial. Com efeito, suponha que β e um ordinal inicial diferente deℵ(α) tal que α < β. Pela lei de tricotomia para ordinais temos que β < ℵ(α) ouℵ(α) < β. Suponhamos que β < ℵ(α), logo β ∈ ℵ(α) e entao β � α. Por outrolado, α < β implica α ⊆ β donde α � β. Pelo Teorema de Cantor-Schroder-Bernstein inferimos que β ≈ α, sendo que α < β e β e um ordinal inicial,contradicao. Portanto ℵ(α) < β, isto e: ℵ(α) e o mınimo ordinal inicial maiorque α.

Definicao 15.7 Por recursao transfinita definimos a seguinte sequencia de or-dinais iniciais infinitos:

ℵ0 = ω;ℵα+1 = ℵ(ℵα);ℵλ =

⋃β<λ ℵβ se λ e um ordinal limite.

Como foi feito anteriormente, podemos provar que a definicao por recursaotransfinita 15.7 e legitimada em ZF, e que ℵα e um ordinal inicial infinito paratodo ordinal α (conferir!). Reciprocamente, por inducao transfinita podemosprovar que se α e ordinal inicial infinito, entao existe um ordinal β tal queα = ℵβ. Logo: inic(α) ∧ INFIN(α) ↔ (∃β)(α = ℵβ) e um teorema em ZF.

Definicao 15.8 Um cardinal e um ordinal inicial.

76

Portanto, todo cardinal infinito e da forma ℵα para algum ordinal α. Umanotacao alternativa para ℵα e ωα. Por inducao transfinita podemos provar oseguinte resultado, que utilizaremos para definir as operacoes aritmeticas entrecardinais:

Proposicao 15.9 Em ZF vale o seguinte: Se α e um cardinal e ω ≤ α, entaoα ≈ (α× α).

Se α e um ordinal, entao para todo ordinal β: β ≈ α implica que β � α,portanto β ∈ ℵ(α). Desta maneira existe por [A2] o conjunto

aα = {β : β ∈ ℵ(α) ∧ β ≈ α} = {β : β ≈ α}.

Temos que α ≈ α, portanto aα 6= ∅. Daqui inferimos que existe o conjunto

=α =

⋂aα =

⋂{β : β ≈ α}.

O conjunto=α e dito o cardinal de α. Pode ser provado que

=α e um cardinal, e

que α ==α se α e um cardinal. Se x e um conjunto e x ≈ α para algum ordinal

α entao β ≈ x sse β ≈ α para todo ordinal β, portanto existe

=x ≡def

⋂{β : β ≈ x} =

=α.

Definicao 15.10 Seja x um conjunto. O cardinal de x e definido como

=x =

⋂{β : β ≈ x} se x ≈ α para algum ordinal α

∅ em caso contrario.

Teorema 15.11 (Princıpio da Boa Ordem) Em ZFC (isto e, em ZF mais oaxioma da escolha) provamos o seguinte: todo conjunto x admite uma boa ordemr em x.

Daqui temos que para todo conjunto x existe=x =

⋂{β : β ≈ x}. Com

efeito, se x e um conjunto, entao existe uma boa ordem r em x; pelo teoremade caracterizacao dos ordinais existe um unico ordinal α isomorfo a 〈x, r〉; emparticular x ≈ α. Pela Definicao 15.10 obtemos que

=x =

⋂{β : β ≈ x}.

Devemos observar que, de fato, o axioma da escolha e equivalente ao princıpioda boa ordem. Por outro lado, o cardinal de um conjunto e determinado pelasdiferentes possibilidades que existem para definir uma boa ordem r em x; cadar determina um ordinal α isomorfo a 〈x, r〉, portanto o mınimo desses ordinaiscorresponde a unica boa ordem sobre x que o faz um cardinal.

Proposicao 15.12 Seja b um conjunto e β um ordinal tal que b � β. Con-sidere a seguinte relacao em b: x r y sse f(x) < f(y) onde f e uma funcaoinjetora de b em β. Logo r e uma boa ordem em b tal que, se α e o tipo ordinalde 〈b, r〉, entao α ≤ β.

77

Demonstracao: E imediato que r e uma boa ordem em b, pois r e computadaa partir da copia f“b de b em β na relacao de boa ordem ∈. Seja h : b−→α oisomorfismo entre b e o tipo ordinal α de b dado por

h(x) = {h(y) : y r x} = {h(y) : f(y) < f(x)}.

Logo, h(x) < h(y) sse x r y sse f(x) < f(y). Definimos uma funcao g : α−→ βdada por g(γ) = f(x) onde x e o unico elemento de b tal que γ = h(x). Logo ge uma funcao satisfazendo

γ = h(x) < h(y) = δ sse g(γ) = f(x) < f(y) = g(δ)

portanto g e um isomorfismo entre α e g“α. Logo g(γ) = γ para todo γ ∈ α(pelo Fato 2 na demonstracao do Teorema 14.4) e entao α ≤ β. �

Corolario 15.13 Sejam b e c conjuntos. Em ZFC vale o seguinte: se b ⊆ c

entao=b ≤ =

c.

Demonstracao: Seja x ∈=b =

⋂{β : β ≈ b}. Queremos provar que x ∈

=c =

⋂{β : β ≈ c}. Seja entao β um ordinal equipolente com c, e considere

f : c−→ β uma bijecao. Logo f |b e uma bijecao entre b e f“b ⊆ β, donde b � β.Considere o ordinal α ≤ β da Proposicao 15.12. Logo α ≈ b donde x ∈ α, pois

x ∈=b . Mas α ⊆ β, portanto x ∈ β. Provamos assim que x ∈ =

c , e entao=b ⊆ =

c ,

donde=b ≤ =

c . �

Definicao 15.14 Uma famılia de conjuntos indexada por um conjunto I e umconjunto

(xi)i∈I = {〈i, xi〉 : i ∈ I}onde xi e um conjunto para cada i ∈ I. Mais formalmente, uma famılia (xi)i∈Ie uma funcao x : I−→a tal que I e a sao conjuntos, com I 6= ∅. Se i ∈ Ientao x(i) e denotado por xi. Por outro lado,

⋃i∈I xi denota o conjunto

{z ∈⋃a : (∃i)(i ∈ I ∧ z ∈ xi)}.

Isto e,⋃i∈I xi =

⋃im(x). O produto cartesiano de (xi)i∈I e dado por∏

i∈Ixi = {f : fun(I,

⋃i∈I

xi) ∧ (∀i)(i ∈ I → f(i) ∈ xi)}.

Definicao 15.15 Seja (κi)i∈I uma famılia indexada de cardinais.(i) A soma cardinal

⊕i∈I κi e o cardinal κ construıdo da maneira seguinte: se

(ai)i∈I e uma famılia de conjuntos dois a dois disjuntos (isto e, ai ∩ aj = ∅ sei 6= j) tal que

=ai = κi para todo i ∈ I entao κ e o cardinal do conjunto

⋃i∈I ai.

Se I = {0,1} escreveremos κ0 ⊕ κ1.(ii) O produto cardinal

⊙i∈I κi e o cardinal κ construıdo da maneira seguinte:

se (ai)i∈I e uma famılia de conjuntos tal que=ai = κi para todo i ∈ I entao κ e

o cardinal do conjunto∏i∈I ai. Se I = {0,1} escreveremos κ0 � κ1.

(iii) Se κ, θ sao cardinais, definimos a exponenciacao cardinal κθ como sendoo cardinal µ dado pelo cardinal do conjunto xy, onde

=x = κ e

=y = θ.

78

Vemos que sem o axioma da escolha nao podemos assegurar que existem estasoperacoes para I infinito, pois nada garante a existencia dos conjuntos ai taisque

=ai = κi para todo i ∈ I nem a existencia da soma e o produto cardinal. O

axioma da escolha nos assegura que estas operacoes existem e sao bem definidas,isto e, independem dos conjuntos escolhidos para a sua realizacao. Observemosque κθ e um caso particular de produto cardinal, em que I = θ e κi = κpara todo i ∈ θ. Algumas propriedades das operacoes entre cardinais sao asseguintes (no caso em que a propriedade requer do axioma da escolha, isto eindicado acrescentando “([AE])” no inıcio do enunciado).

Proposicao 15.16 As operacoes entre cardinais satisfazem as propriedadesseguintes:(i) κ⊕ λ = λ⊕ κ, κ� λ = λ� κ.(ii) κ⊕ (λ⊕ θ) = (κ⊕ λ)⊕ θ, κ� (λ� θ) = (κ� λ)� θ.(iii) Se κ ≤ λ entao κ⊕ θ ≤ λ⊕ θ e κ� θ ≤ λ� θ.(iv) κ� (λ⊕ θ) = (κ� λ)⊕ (κ� θ).(v) ([AE]) κ� (

⊕i∈I λi) =

⊕i∈I(κ� λi).

(vi) ([AE]) Se κi = κ para todo i ∈ I, entao⊕

i∈I κi ==I � κ.

(vii) κ⊕ λ e o cardinal do ordinal κ+ λ, e κ� λ e o cardinal do ordinal κ · λ.

Suponha que β e um cardinal. Estamos interessados em encontrar o mınimocardinal α tal que existe uma particao de β em α pedacos de cardinalidade es-tritamente menor do que β. Esse cardinal mınimo α e a cofinalidade de β, e seradenotado cf(β). No caso em que β e um cardinal tal que cf(β) = β dizemos queβ e regular. Por exemplo, ω nao pode ser particionado numa quantidade finitade subconjuntos finitos; para cobrir todo ω por uma particao de subconjuntosfinitos precissamos de ω subconjuntos; portanto ω e um cardinal regular.

Definicao 15.17 Sejam α e β ordinais.α cf β denota α ≤ β ∧ (∃f)(fun(f, α, β) ∧ β =

⋃im(f))

(“α e cofinal em β”).cf(β) denota

⋂{α : α cf β}

(“a cofinalidade de β”).

Dado que α cf β implica que α ≤ β (donde α ∈ β + 1) entao Cβ = {α : α cfβ} ⊆ β+1, portanto Cβ e legitimado por [A2]. Por outro lado β cf β, portantoCβ 6= ∅ e entao existe cf(β) para todo ordinal β. Se α cf β e f : α−→ βtal que

⋃im(f) = β entao, para cada γ ∈ β existe δ ∈ α tal que γ ∈ f(δ),

pela definicao de⋃

. Ou seja, para cada γ ∈ β existe δ ∈ α tal que γ < f(δ).Em outras palavras, a imagem de f nao e limitada em β, portanto f e umasequencia em β (indexada por α) convergendo a β (a convergencia e dada pelauniao

⋃). Observe que se β = α+ 1 entao cf(β) = 1. Com efeito, 1 cf (α+ 1)

via f(0) = α.

Proposicao 15.18 Sejam α e β ordinais limites. Em ZF vale o seguinte:(i) α cf β e uma relacao transitiva.(ii) cf(β) e um cardinal.

79

Definicao 15.19 Seja κ um cardinal. Dizemos que κ e regular se cf(κ) = κ.Em caso contrario, isto e, se cf(κ) < κ, entao κ e dito singular.

Proposicao 15.20 Em ZFC vale o seguinte:(i) ω e regular.(ii) ℵα+1 e regular para todo α.(iii) Se λ e um ordinal limite entao cf(ℵλ) = cf(λ).

Observe que, pela proposicao anterior, cf(ℵω) = cf(ω) = ω. Por exemplo, ℵωpode ser atingido pela sequencia

ℵ0 < ℵ1 < ℵ2 < · · · −→ℵω

provando que ℵω e singular. Tambem temos que cf(ℵℵω) = ω, considerando,por exemplo, a sequencia

ℵℵ0 < ℵℵ1 < ℵℵ2 < · · · −→ℵℵω .

Finalmente, discutiremos brevemente a Hipotese do Contınuo (HC). Temosduas maneiras para passar de um cardinal a outro superior: considerar ℵ(κ) > κou, pelo teorema de Cantor, considerar 2κ > κ. A Hipotese do Contınuo afirmao seguinte:

(HC) 2ℵ0 = ℵ1.

Dado que R ≈ 2ℵ0 entao (HC) afirma que todo subconjunto de R nao enu-meravel e equipolente com R, isto e, nao existem subconjuntos de R de cardi-nalidade intermediaria entre ℵ0 e a cardinalidade de R. Portanto (HC) afirmaque 2κ e ℵ(κ) coincidem no primeiro valor ℵ0. A Hipotese Generalizada doContınuo (HGC) afirma que estas funcoes coincidem em todo cardinal κ. Emoutras palavras, para cada cardinal infinito κ nao existe um cardinal estrita-mente entre κ e 2κ. Em termos da funcao ℵ temos que (HGC) afirma que

(HGC) 2ℵα = ℵα+1

para todo ordinal α. Com a ajuda de (HGC) resolvemos todas as questoesacerca das potencias cardinais:

Teorema 15.21 Assumamos (HGC). Em ZFC temos que ℵℵβα e determinado,

sendo que(i) ℵℵβ

α = ℵβ+1 se α ≤ β;(ii) ℵℵβ

α = ℵα se ℵβ < cf(ℵα);(iii) ℵℵβ

α = ℵα+1 se cf(ℵα) ≤ ℵβ ≤ ℵα.

Em 1936 Kurt Godel demonstrou que, se a teoria ZF e consistente, entao ZFCcom o acrescimo de (HC) e consistente. Por outro lado, Cohen demonstrou em1964 (mediante a tecnica de forcing) que, se a teoria ZF e consistente, entaoZFC com o acrescimo da negacao de (HC) tambem e consistente, portanto a

80

Hipotese do Contınuo e indecidıvel na teoria ZFC. Tambem foi provado porCohen que, se a teoria ZF e consistente, entao ZF com o acrescimo da negacaode [AE] tambem e consistente. Vemos assim que, em particular, tanto ZFcom o acrescimo de [AE] quanto ZF com o acrescimo da negacao de [AE] saoconsistentes, desde que ZF seja consistente. Assim, ambas teorias de conjuntossao validas, e a inclusao do Axioma da Escolha ou da sua negacao acaba sendouma questao de escolha.

Devemos observar, finalmente, que os famosos teoremas de incompletude deGodel se aplicam a ZF , portanto existem sentencas de ZF que sao indecidıveisem ZF . Em particular, se ZF e consistente, entao ZF nao pode provar a suapropria consistencia.

References

[1] C.A. di Prisco, Una Introduccion a la Teorıa de Conjuntos, ColecaoCLE, vol. 20, (UNICAMP), 1997.

[2] F.R. Drake, Set Theory: an Introduction to Large Cardinals,North Holland, 1974.

[3] H.B. Enderton, Elements of Set Theory, Academic Press, 1977.

[4] T. Jech, Set Theory, Springer Verlag (segunda edicao), 2002.

[5] P. Suppes, Axiomatic Set Theory, Dover, 1972.

81