Uma Introduç˜ao `a Teoria dos Conjuntos

Notas de Minicurso
Uma Introdução à Teoria dos Conjuntos
Andresa Baldam Marchiolli
Eduardo Rogério Fávaro
Íris Andrade Rodrigues
Márcia Mayumi Tukamoto
Maria Gorete Carreira Andrade (Orientadora)
Departamento de Matemática - IBILCE - UNESP
São José do Rio Preto
Conteúdo
1 Enumerabilidade de conjuntos
1.1 Conjuntos Equipotentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Conjuntos finitos e enumeráveis . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
4
7
2 Noções de Cardinalidade
12
2.1 Números Cardinais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Aritmética dos Cardinais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 O Axioma da Escolha e o Lema de Zorn
16
3.1 Axioma da Escolha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Lema de Zorn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Algumas aplicações do Lema de Zorn . . . . . . . . . . . . . . . . . . . . . . . . 23
2
Introdução
Nestas notas apresentamos uma breve introdução à Teoria dos Conjuntos.
O enfoque dos do primeiro capı́tulo é para os conceitos de equipotência e enumeralidade de
conjuntos.
No segundo capı́tulo apresentamos algumas noções de cardinalidade com ênfase para a
aritmética dos cardinais.
O Capı́tulo 3 é dedicado ao Axioma da Escolha e o Lema de Zorn, apresentando algumas
aplicações deste último.
Como se trata de notas para um minicurso de 4 horas, algumas proposições do Capı́tulo 2
não são demonstradas. As demonstrações podem ser encontradas nas referência bibliográficas.
Nos preocupamos, por outro lado, em apresentar uma série de exemplos para a Teoria, para
que o leitor perceba as diferenças entre o enumerável e o não enumerável e a percepção dos
diversos “tipos de infinitos”.
Finalmente, queremos nos desculpar pelos eventuais erros de digitação que com certeza essas
notas contém.
3
Capı́tulo 1
Enumerabilidade de conjuntos
1.1
Conjuntos Equipotentes
Definição 1.1.1. Sejam A e B dois conjuntos quaisquer. Se existe uma função bijetora f :
A −→ B, dizemos que o conjunto A é equipotente ao conjunto B e denotamos por A ≈ B.
Dizemos também que eles tem igual potência ou mesmo número de elementos.
Observação 1.1.2. A relação de equipotência é uma relação de equivalência. De fato:
1. Como para todo cunjunto A, a aplicação idA : A −→ A dada por idA (x) = x para todo
x ∈ A, é bijetora então todo conjunto é equipotente a si mesmo. Logo vale a propriedade
reflexiva para essa relação entre conjuntos.
2. Se A é equipotente a B, isto é, se existe f : A −→ B bijetora, então, como f −1 : B −→ A
é também bijetora, B também é equipotente a A. Portanto vale a propriedade simétrica.
3. Se A é equipotente a B e se B é equipotente a C, então existe f : A −→ B e g : B −→ C
bijetoras. Daı́ g ◦f : A −→ C também é bijetora e portanto A é equipotente a C. Portanto
vale a propriedade transitiva.
Exemplo 1.1.3. N é equipotente a Z. De fato, considere o esquema:
···
···
−3 −2 −1 0 1 2 3 · · ·
l
l
l l l l l
5
3
1 0 2 4 6 ···
Podemos definir a função
f : Z −→ N
(
k 7−→ f (k) =
2k
se k > 0
.
−2k − 1 se k < 0
Temos que f é bijetora e assim N ≈ Z.
4
Exemplo 1.1.4. N × N ≈ K = {2m 3n |m, n ∈ N}.
Para ver isso, defina f : N × N → K por f (m, n) = 2m .3n .
Temos que f está bem definida e, como mdc(2, 3) = 1, f é injetora, pois 2m .3n = 2r .3s ⇔
m = r e n = s ⇔ (m, n) = (r, s). Além disso, f também é sobrejetora, pois para todo y =
2m .3n ∈ K, existe x = (m, n) ∈ N × N | f (x) = y.
Portanto, f é bijetora e temos N × N ≈ K.
Exemplo 1.1.5. [a, b] ≈ [0, 1] para todos x, y ∈ R. De fato, a função
f : [a, b] −→ [0.1]
x 7−→ f (x) =
x−a
b−a
é uma bijeção entre [a, b] e [0, 1].
Exemplo 1.1.6. R e ] − 1, 1[ são equipotentes Para ver isso observe que a função
f :] − 1, 1[ −→ R
x 7−→
x
1 + |x|
é uma bijação. Sua inversa é dada por
g : R −→ ] − 1, 1[
y
.
y 7−→
1 − |y|
Exemplo 1.1.7. ]0, 1[≈ [0, 1] ≈]0, 1].
Para justificar isso, considere os conjuntos A = {0, 1, 1/2, 1/3, ...} e B = {1/2, 1/3, 1/4, ...}.
Temos que [0, 1] − A =]0, 1[−B e [0, 1] = ([0, 1] − A =) ∪ A, ]0, 1[= (]0, 1[−B) ∪ B. Definimos
f : [0, 1] →]0, 1[ por

 x,
se x ∈ [0, 1] − A;

1
f (x) =
,
se x = 0;
2

 1
, se x = n1 , n ≥ 1.
n+2
Claramente f é bijetora, e assim ]0, 1[≈ [0, 1] Analogamente prova-se que ]0, 1[≈]0, 1] tomandose A = {1, 1/2, 1/3, ...} e B = {1/2, 1/3, ...}. Pela propriedade transitiva, ]0, 1[≈]0, 1].
Exemplo 1.1.8. Segue dos exemplos anteriores que para todos a, b ∈ R, [a, b] ≈]a, b] ≈ [a, b[≈
]a, b[≈ R.
Exemplo 1.1.9. Se A ≈ C e B ≈ D então A × B ≈ C × D. Isto segue do fato que existem
funções bijetoras f : A → C e g : B → D. Daı́, definindo h : A × B → C × D por h(a, b) =
(f (a), g(b)), verifica-se facilmente que h é bijetora.
5
Exemplo 1.1.10. Para n ≥ 1, temos R ≈ Rn ≈ C ≈ Cn . De fato, temos R ≈]0, 1[. Assim,
pelo exemplo anterior, R2 ≈]0, 1[×]0, 1[.
Agora defina ψ :]0, 1[×]0, 1[−→]0, 1[ por ψ(0, x1 x2 ..., 0, y1 , y2 ...) = 0, x1 y1 x2 y2 x3 y3 ... Claramente ψ está bem definida.
ψ é injetora pois ψ(0, x1 x2 ... , 0, y1 , y2 ...) = ψ(0, z1 z2 ... , 0, w1 , w2 ...) ⇒ 0, x1 y1 x2 y2 x3 y3 ... =
0, z1 w1 z2 w2 z3 w3 ... ⇒ x1 = z1 , y1 = w1 , ..., xn = zn , yn = wn , ... ⇒ 0, x1 x2 ... = 0, z1 z2 ... e 0, y1 y2 ... =
0, w1 w2 ... ⇒ (0, x1 x2 ... , 0, y1 y2 ...) = (0, z1 z2 ... , 0, w1 w2 ...).
ψ é sobrejetora. Para todo z ∈ ]0, 1[, temos z = 0, z1 z2 z3 .... Sejam x = 0, z1 z3 z5 ... e
y = 0, z2 z4 z6 .... Então ψ(x, y) = ψ(0, z1 z3 z5 ... , 0, z2 z4 z6 ...) = 0, z1 z2 z3 ... = z. Assim, existe
(x, y) ∈]0, 1[×]0, 1[ tal que ψ(x, y) = z.
ψ
Logo ψ é bijetora e temos R ≈]0, 1[≈]0, 1[×]0, 1[≈ R × R = R2 .
Agora, por indução sobre n, mostra-se que R ≈ Rn . Pela propriedade transitiva
R ≈ R2 ≈ ... ≈ Rn , ∀n ≥ 1.
Considere agora a aplicação ψ : C → R2 dada por ψ(x + iy) = (x, y). ψ é claramente
bijetora e assim C ≈ R2 .
Daı́, C ≈ R2 ≈ R4 ≈ R2 × R2 ≈ C × C ≈ C2 .
Por indução sobre n mostra-se que C ≈ Cn . Daı́ pela propriedade transitiva temos
C ≈ Cn ≈ Rn ≈ ... ≈ R2 ≈ R.
Exemplo 1.1.11. Sejam S um con junto e P (S) = {A; A ⊆ S} o conjunto das partes de S.
Então S não é equipotente a P (S).
De fato, vamos supor S ≈ P (S). Logo existe f : S −→ P (S) bijeção. Seja A = {x ∈ S; x 6∈
f (x)}. Denotemos f (x) = Bx ⊆ S. Dai A = {x ∈ S; x 6∈ Bx }. Portanto A ∈ P (S). Como f
é bijetora, existe p ∈ S tal que f (p) = A. Se p ∈ A então p 6∈ f (p) = Bp = A (absurdo!). Se
p 6∈ A então p ∈ f (p) = Bp = A (absurdo!). Logo não existe f : S −→ P (S) bijetora.
Exemplo 1.1.12. Seja C(A) = {f : A −→ {0, 1} | f é função}. Temos que C(A) ≈ P(A).
De fato, basta (
definir F : P(A) −→ C(A) por F (S) = f | f : A −→ {0, 1} onde, para cada
1, se a ∈ S ;
a ∈ A, f (a) =
Temos que:
0, se a ∈/ S .
(i) F está bem definida. De
( fato se S1 = S2 temos que
( as funções f1 : A → {0, 1} e f2 : A →
1 se a ∈ S1
1 se a ∈ S2 = S1
{0, 1} dadas por f1 (a) =
e f2 (a) =
são iguais. Assim
0 se a ∈
/ S1
0 se a ∈
/ S2 = S1
F (S1 ) = F (S2 ).
(ii) f é injetora pois se S1 6= S2 temos que S1 * S2 ou S2 * S1 . Suponhamos S1 * S2 . Logo
existe s ∈ S1 talque s 6∈ S2 . Daı́, como F (S1 ) = f1 e F (S2 ) = f2 , temos f1 (s) = 1 (pois
s ∈ S1 ) e f2 (s) = 0 (pois s 6∈ S2 ). Assim f1 (s) 6= f2 (s) e temos então f1 6= f2 . Portanto
F (S1 ) 6= F (S2 ).
−1
(iii) f é sobrejetora. De fato, ∀f ∈ C(A), f : A → {0, 1} é uma função. Seja
( S = f ({1}) =
1 se a ∈ S
{x ∈ A|f (x) = 1}. Temos que S ⊂ A e assim S ∈ P(A). Agora f (a) =
, pela
0 se 6=∈ S
6
definição de S. Logo F (S) = f.. Portanto existe S ∈ P(A) tal que F (S) = f .
Assim F é bijetora e temos P(A) ≈ C(A).
Exemplo 1.1.13. O conjunto C(N) é equipotente a um subconjunto de ]0, 1[.
Para ver isso, considere a aplicação F : C(N) −→]0, 1[ definida por F (f ) = 0, f (0)f (1)f (2)....
F está bem definida e é injetora pois F (f1 ) = F (f2 ) ⇔ 0, f1 (0)f1 (1)... = 0, f2 (0)f2 (1)... ⇔
f1 (n) = f2 (n), ∀ n ∈ N ⇔ f1 = f2 .
Daı́ F : C(N) → F (C(N)) ⊂]0, 1[ é bijetora e assim C(N) ≈ F (C(N)) ⊂]0, 1[.
Exemplo 1.1.14. Se A ≈ B então P (A) ≈ P (B). De fato, como A ≈ B existe f : A → B
bijetora. Definimos ψ : P(A) → P(B) por ψ(S) = {f (s)|s ∈ S}.
Claramente ψ(S) ⊂ B e assim ψ(S) ∈ P(B). Além disso, ψ está bem definida pois S =
T ⇒ ψ(S) = ψ(T ). Temos que ψ é injetora. De fato se S1 6= S2 existe s ∈ S1 tal que s 6∈ S2
(ou vice versa). Logo f (s) ∈ ψ(S1 ) e f (s) 6∈ ψ(S2 ) (Se f (s) pertencesse a ψ(S2 ), existiria
s2 ∈ S2 tal que f (s2 ) = f (s). Como f é injetora terı́amos s = s2 ∈ S2 (absurdo)). Portanto
ψ(S1 ) 6= ψ(S2 ). Temos também que ψ é sobrejetora. De fato ∀ T ∈ P(B) temos que T ⊂ B.
Como f é bijetora temos que se S = f −1 (T ), ψ(S) = {f (s)|s ∈ S} = f (S) = f (f −1 (T )) = T.
Assim existe S ∈ P(A) tal que ψ(S) = T .
Portanto ψ é bijetora e temos P(A) ≈ P(B).
1.2
Conjuntos finitos e enumeráveis
Definição 1.2.1. Um conjunto F diz-se finito se existe n ∈ N tal que F é equipotente a
{1, 2, 3, . . . , n}. Caso contrário, F é dito infinito.
Definição 1.2.2. Um conjunto A diz-se enumerável quando é finito ou quando existe uma
bijeção f : N −→ A. No segundo caso, A diz-se infinito enumerável e, pondo-se x1 = f (1), x2 =
f (2), . . . , xn = f (n), . . ., tem-se A = {x1 , x2 , . . . , xn , . . .}. Cada bijeção f : N −→ A chama-se
uma enumeração (dos elementos) de A.
Teorema 1.2.3. Todo subconjunto A ⊆ N é enumerável.
Demonstração. Se A é finito não há nada a demonstrar. Se A é infinito consideramos x1
o menor elemento de A, x2 o menor elemento de A − {x1 } assim por diante, xn o menor
elemento de A − {x1 , . . . , xn−1 }. Observe que x1 < x2 < . . . < xn . Continuando esse processo
indutivamente, definimos xn+1 com sendo o menor elemento de An = A − {x1 , x2 , . . . , xn }. Daı́
temos A = {x1 , x2 , . . . , xn , . . .} pois, se existisse x ∈ A com x 6= xk para todo k ∈ N terı́amos
x ∈ An para todo n ∈ N. Logo x seria um número natural maior que todos os elementos do
conjunto infinito {x1 , x2 , . . . , xn , . . .}, o que é um absurdo pois um subconjunto infinito de N é
ilimitado superiormente.
Exemplo 1.2.4. Todo conjunto finito é enumerável.
7
Exemplo 1.2.5. N e Z são enumeráveis.
Teorema 1.2.6. Seja X ⊆ N. Se A é um conjunto tal que existe ua função f : A −→ X
bijetora, então A é enumerável.
Demonstração. Pelo Teorema 1.2.3, temos que X é enumerável. Dai existe g : X −→ N bijeção.
Logo, g ◦ f : A −→ N é um bijeção, o que mostra que A é enumerável.
Proposição 1.2.7. Um conjunto A é enumerável se, e somente se, existe L ⊆ N e f : L −→ A
sobrejetora.
Demonstração. Se A é enumerável, por definição existe f : N −→ A bijetora, em particular,
sobrejetora. Logo, basta tomar L = N. Reciprocamente, suponha que existem L ⊆ N e
f : L −→ A sobrejetora. Daı́, para cada a ∈ A, existe l ∈ L tal que f (l) = a. Para cada a ∈ A,
seja
La = {l ∈ L; f (l) = a}.
Para cada a ∈ A, escolhemos um único xa ∈ La . Fazemos M = {xa ; a ∈ A} ⊆ L ⊆ N. Seja
g : M −→ A
xa 7−→ g(xa ) = f (xa ) = a.
Por constução, g é bijetora. Logo, A é enumerável.
Proposição 1.2.8. Seja A e B dois conjuntos Se existe f : A −→ B sobrejetora e A é
enumerável, então B é enumerável.
Demonstração. Como A é enumerável, existe uma bijeção g : N −→ A. Dai, f ◦ g : N −→ B é
sobrejetora. Pela Proposição 1.2.7, segue que B é enumerável.
Proposição 1.2.9. Todo subconjunto de um conjunto enumerável é enumerável.
Demonstração. Seja B ⊆ A, B 6= ∅ com A enumerável. Provemos que B é enumerável. Para
isso, basta definirmos f : A −→ B sobrejetora. Como B 6= ∅, fixe b ∈ B. Definimos
f : A −→ B
(
a 7−→ f (a) =
a se
a∈B
.
b se a ∈ A \ B
Temos que f é sobrejetora. Logo, pelo Proposiçào 1.2.8, B é enumerável.
Exemplo 1.2.10. O conjunto dos números racionais positivos Q∗+ é enumerável.
De nfato, considere o oconjunto K = {2m 3n ∈ N; m ∈ N, n ∈ N∗ } ⊆ N.
m
Q∗+ =
; m ∈ N, n ∈ N∗ . Definimos
n
f : K −→ Q∗+
m
2m 3n 7−→
.
n
8
Veja que
Se provarmos que f esta bem definida e é sobrejetora, teremos mostrado que Q∗+ é enumerável.
Temos que f está bem definida, pois, 2m1 3n1 = 2m2 3n2 =⇒ 2m1 −m2 = 3n2 −n1 =⇒ log2 (2m1 −m2 ) =
log2 3n2 −n1 =⇒ m1 − m2 = (n2 − n1 ) log2 3. Como log2 3 6∈ Q e m1 − m2 , n2 − n1 ∈ Z ⊆ Q,
m2
m1
=
.
segue que n2 − n1 = 0, e assim m1 − m2 = 0. Logo
n1
n2
Exemplo 1.2.11. Q∗− é enumerável. De fato, a aplicação f : Q∗+ −→ Q∗− definida por f (x) =
−x é bijetora.
Exemplo 1.2.12. O conjunto N × N é enumerável.
N × N ≈ K = {2m 3n |m, n ∈ N} ⊂ N.
De fato,
já vimos que
Proposição 1.2.13. A reunião enumerável de subconjuntos enumeráveis é enumerável.
Demonstração. Seja (Ai )i∈N uma famı́lia de subconjuntos enumeráveis. Logo existe uma famı́lia
(Mi )i∈N
de N e funções fi : Mi −→ Ai bijetoras para cada
[ de subconjuntos
[
[ i ∈ N. Sejam
M =
Mi e A =
Ai . Como Mi ⊆ N, para cada i ∈ N, segue que M =
Mi ⊆ N. Logo
i∈N
i∈N
i∈N
M é enumerável. Seja a ∈ A fixo. Temos N × M ⊆ N × N. Logo N × M é enumerável. Seja
f : N × M −→ A
(
(r, s) 7−→ f (r, s) =
fr (s) se s ∈ Mr
a
se s 6∈ Mr
.
Afirmamos que f é sobrejetora. De fato, para cada x ∈ A, existe r ∈ N tal que x ∈ Ar . Como
fr : Mr −→ Ar é sobrejetora, existe s ∈ Mr tal que fr (s) = x. Daı́, f (r, s) = x. Portando, dado
x ∈ A, existe (r, s) ∈ N × N tal que f (r, s) = x, o que mostra que f é sobrejetora. Portanto, A
é enumerável.
Exemplo 1.2.14. Q é enumerável.
Primeira justificativa Basta ver que Q = Q∗− ∪ {0} ∪ Q∗+ .
Segunda justivicativa Considere a função
f : N × N∗ −→ Q
p
(p, q) 7−→
.
q
Como f é sobrejetora e N × N é enumerável, segue que Q é enumerável.
Exemplo 1.2.15. Se A e B são enumeráveis, então o produto cartesiano A × B é enumerável.
De fato, sabemos que:
A enumerável ⇒ ∃ L ⊂ N∗ e f : L → A bijetora
B enumerável ⇒ ∃ M ⊂ N∗ e g : M → M bijetora
Definimos h : L × M → A × B por h(l, m) := (f (l), g(m)).
Temos que h é injetora, pois h(l, m) = h(r, s) ⇒ (f (l), g(m)) = (f (r), g(s)) ⇒ f (l) =
f (r) e g(m) = g(s). Como f e g são injetoras, concluimos que l = r e m = s, então (l, m) =
(r, s).
9
Temos também que h é sobrejetora, pois ∀ (a, b) ∈ A × B temos que a ∈ A e b ∈ B.
Então, como f e g são sobrejetoras, ∃ l ∈ L e m ∈ M tal que f (l) = a e g(m) = b. Daı́,
h(l, m) = (f (l), g(m)) = (a, b). Então ∃ (l, m) ∈ L × M tal que h(l, m) = (a, b).
Portanto, h é bijetora. Como L × M ⊂ N∗ × N∗ temos que L × M é enumerável. Logo,
A × B é enumerável.
Exemplo 1.2.16. Se A1 , ..., An são enumeráveis, então A1 × ... × An é enumerável.
Para justificar isso usamos indução sobre n. Para n = 2 é verdadeiro pelo exemplo anterior.
Por hipótese de indução suponhamos que: A1 , ..., Ak enumerável ⇒ A1 ×...×Ak enumerável.
Se n = k + 1, A1 × ... × Ak × Ak+1 = (A1 × ... × Ak ) × Ak+1 é enumerável, pois por hipótese
de indução temos que A1 × ... × Ak é enumerável.
Exemplo 1.2.17. Seja Pn (x) = {a0 + a1 x + ... + an xn | ai ∈ R} o conjunto dos polinômios
com grau menor ou igual a n e coeficientes inteiros. Temos que Pn (x) é enumerável.
De fato, seja f : Pn (x) → Z×Z×...×Z (n+1 vezes) definida em p(x) = a0 +a1 x+...+an xn
por f (p(x)) := (a0 , a1 , ..., an ).
É fácil ver que que f é bijetora. Como Z × Z × ... × Z é enumerável, temos que Pn (x) é
enumerável.
Exemplo 1.2.18. Seja P (x) o conjunto de todos os polinômios com coeficientes em Z . Então
P (x) é enumerável.
∞
[
Pn (x). Como Pn (x) é enumerável e reunião enuPara ver isso, observe que P (x) =
n=0
merável de conjuntos enumeráveis é enumerável, concluimos que P (x) é enumerável.
Exemplo 1.2.19. O conjunto A = {f | f : N → N é função} não é enumerável.
De fato, suponhamos que A = {f | f : N → Né função} seja enumerável. Então A =
{f0 , f1 , f2 , ..., fn , ...} com cada fi : N → N, i = 0, 1, ..., n, ....
Seja f : N → N definida da seguinte maneira:
(
f (n) =
1, se fn (n) 6= 1;
0, se fn (n) = 1.
Temos que f (n) 6= fn (n), ∀ n ∈ N. Portanto, f 6= fn , ∀ n ∈ N e f ∈ A, o que nos dá um
absurdo. Logo, A não é enumerável.
Exemplo 1.2.20. R não é enumerável.
De fato, vamos supor que R seja enumerável. Como R ≈]0, 1[, então o intertvalo ]0, 1[
também é enumerável. Assim ]0, 1[= {a1 , a2 , . . . , an , . . .} com cada ak é escrito na representação
decimal infinita dada por ak = 0, xk1 xk2(. . . xkn . . .. Seja b = 0, b1 b2 . . . o elemento do intervalo
1, se xjj 6= 1
]0, 1[ definido da seguinte forma: bj =
. Temos que bj 6= xjj , ∀j = 0, 1, 2, . . . ,
0, se xjj = 1
e assim b 6= ak para todo k. Portanto b ∈
/ ]0, 1[, o que é um absurdo. Daı́ R não pode ser
enumerável.
10
Exemplo 1.2.21. Qualquer coleção de intervalos abertos da reta disjuntos entre si é enumerável.
Para justificar isso, seja C = {]ai , bi [ | ai , bi ∈ R, ai < bi , i ∈ I} uma coleção de intervalos
abertos tais que ]ai , bi [∩]aj , bj [= ∅ se i 6= j.
Para cada intervalo ]ai , bi [ vamos escolher um único qi ∈ Q tal que ai < qi < bi . (Em
todo intervalo da reta existem números racionais). Seja M = {qi | i ∈ I} ⊂ Q. Como Q é
enumerável, temos que M é enumerável.
Definimos f : M −→ C por f (qi ) :=]ai , bi [.
f está bem definida pois se qi = qj e f (qi ) 6= f (qj ) teriamos ]ai , bi [6=]aj , bj [. Logo ]ai , bi [∩]aj , bj [=
∅ o que é um absurdo pois qj ∈]ai , bi [∩]aj , bj [. Daı́ f (qi ) = f (qj ).
f é sobrejetora pois para todo ]ai , bi [∈ C temos que existe qi ∈ M, ai < qi < bi tal que
f (qi ) =]ai , bi [.
Portanto, como M é enumerável, temos que C é enumerável.
Exemplo 1.2.22. Todo conjunto infinito contém um subconjunto enumerável infinito.
De fato, seja A um conjunto infinito. Vamos definir f : N → A da seguinte maneira:
Como A 6= ∅, ∃x0 ∈ A e colocamos f (0) = x0 .
Agora, A − {x0 } =
6 0 (pois A é infinito). Logo existe x1 ∈ A − {x0 } e definimos f (1) = x1 , e
assim sucessivamente, A − {x1 , ..., xn } =
6 ∅ pois A é infinito, logo existe xn+1 ∈ A − {x1 , ..., xn }
e definimos f (n + 1) = xn+1 .
Seja M = {x1 , ..., xn , ...} ⊂ A. Temos que M ≈ N pois f : N −→ M dada por f (n) = xn é
bijetora.
Assim M é enumerável infinito e M ⊂ A.
Nota A função f é chamada função escolha e a demonstração de que f está bem definida decorre
do Axioma da Escolha, que estudaremos no Capı́tulo 3.
11
Capı́tulo 2
Noções de Cardinalidade
2.1
Números Cardinais
Na teoria dos Conjuntos de Zermelo-Fraenkel, a noção de número cardinal é um conceito
primitivo da teoria, e para caracteriza-lá é necessário um axioma.
Axioma dos Números Cardinais “A cada conjunto A está associado um objeto |A|
chamado número cardinal de A, ou cardinalidade de A, tal que |A| = |B| se, e somente se, A é
equipotente a B.”
Outras notações para número cardinal de A: Ā¯, c(A), card(A), #A.
Definimos os cardinais finitos (números cardinais de conjuntos finitos) da seguinte maneira:
#∅ = 0
#{0} = 1
#{0, 1} = 2
..
.
#{0, 2, . . . , n − 1} = n
Observação 2.1.1. Se #A = n então #P(A) = 2n .
Vamos denotar por:
χ0 = #N
χ1 = #P(N)
χ2 = #P(P(N))
..
.
c = #R
Observação 2.1.2. Todos os conjuntos enumeráveis infinitos tem número cardinal χ0 .
12
Definição 2.1.3. Dados dois números cardinais u e v, escrevemos u ≤ v se existem conjuntos
A e B tais que u = #A, v = #B e existe uma aplicação f : A −→ B injetora (A é equipotente
a um subconjunto de B).
Observação 2.1.4. A definição não depende da escolha de A e B.
Proposição 2.1.5. A relação ≤ é uma relaçào de ordem parcial para qualquer conjunto de
cardinais, isto é, valem as propriedades
(i) u ≤ u (reflexiva)
(ii) Se u ≤ v e v ≤ w então u ≤ w (transitiva)
(iii) Se u ≤ v e v ≤ u então u = v (anti-simétrica) .
2
Observação 2.1.6. Se u ≤ v e u 6= v escrevemos u < v.
Teorema 2.1.7. (Cantor) #A < #P(A). Logo dado qualquer número cardinal, sempre existe
um número cardinal maior que o número cardinal dado.
Demonstração. A aplicação f : A −→ P(A) definida por f (x) = {x} é injetora. Portanto,
#A ≤ #P(A). Mas vimos que A não é equipotente a P(A). Assim #A 6= #P(A). Logo
#A < #P(A).
Teorema 2.1.8. #R = #P(N). Isto é c = χ1 .
Demonstração. Temos que χ1 = #P(N) = #P(Q), pois N ≈ Q.
Seja ψ : R −→ P(Q) definida por ψ(a) = {x ∈ Q | x < a}(subconjunto formado por todos os
números racionais menores que a). Temos que ψ é injetora. De fato, sejam a, b ∈ R com a < b.
Logo existe c ∈ Q | a < c < b. Assim c ∈
/ ψ(a) e c ∈ ψ(b). Daı́ ψ(a) 6= ψ(b). Temos então
demonstrado que c ≤ χ1 .
Mas P(Q) ≈ P(N) ≈ C(N) = {f : N −→ {0, 1} | f é fumção} (ver Exemplo 1.1.12).
Sabemos que qualquer elemento x do intervalo ]0, 1[ pode ser escrito unicamente na forma
0, x1 x2 x3 . . . (representação decimal de x). Usando esse fato definimos F : C(N) −→]0, 1[ por
F (f ) = 0, f (1)f (2)f (3) . . .. Assim F (f ) é uma representação decimal constituida de zeros e uns.
Temos que F é injetora. De fato, se f, g ∈ C(N) com f 6= g, existe n ∈ N tal que f (n) 6= g(n).
Logo (0, f (1)f (2)f (3) . . . f (n) . . .) 6= (0, g(1)g(2)g(3) . . . g(n) . . .) Portanto F (f ) 6= F (g). Assim
#C(N) ≤ #]0, 1[. Mas #c(N) = #P(N) = χ1 e #]0, 1[= #R = c. Portanto χ1 ≤ c e temos
então c = χ1 .
Hipótese do Continuum (Contı́nuo) Não existe número cardinal x tal que χ0 < x < χ1 = c
(P. Cohen demonstrou em 1963 que esta hipótese não pode ser demonstrada, nem refutada
e é independente dos axiomas da teoria dos conjuntos)
Hipótese do Continuum
χr < x < χr+1 = 2χr .
generalizada Não existe número cardinal x tal que
13
2.2
Aritmética dos Cardinais
I - Adição:
Sejam u e v dois números cardinais e A e B dois conjuntos tais que A ∩ B = ∅ e u = #A e
v = #B. Definimos u + v = #(A ∪ B).
Observação 2.2.1. Se A ∩ B 6= ∅ podemos considerar A0 = A × {1} e B 0 = B × {2} e temos
u = #A = #A0 e v = #B = #B 0 . Além disso A0 ∩B 0 = ∅. Definimos então u+v = #(A0 ∪B 0 ).
Proposição 2.2.2. (i) A operação adição está bem definida, isto é, u + v não depende da
escolha dos representantes disjuntos A e B.
(ii) u + v = v + u (comutativa).
(iii) (u + v) + w = u + (v + w) (associativa).
2
Exemplo 2.2.3. Consideremos os conjuntos A = {1, 2, 3, 4, 5} e B = {4, 5, 6, 7}. Assim:
u = 5, v = 4 e u + v = 9.
Exemplo 2.2.4. χ0 + χ0 = χ0 .
De fato, temos χ0 = #N = #(N × {1}) = #(N × {2}). Assim
χ0 + χ0 = #((N × {1}) ∪ (N × {2})) = χ0 ,
pois (N × {1}) ∪ (N × {2}) é enumerável, visto que é união de conjuntos enumeráveis.
Exemplo 2.2.5. Por indução sobre n pode-se mostrar que n.χ0 = χ0 + χ0 + ... + χ0 = χ0
|
{z
}
n vezes
II - Multiplicação
Sejam u e v dois números cardinais e A, B conjuntos tais que u = #A e v = #B. Definimos:
u.v = #(A × B).
Proposição 2.2.6. (i) A operação multiplicação está bem definida, isto é, u.v não depende da
escolha dos representantes disjuntos A e B.
(ii) u.v = v.u (comutativa).
(iii) (u.v).w = u.(v.w) (associativa).
(iii) (u + v).w = u.w + v.w (distributiva com relação à adição).
2
Exemplo 2.2.7. χ0 .χ0 = χ0
De fato, seja A = N. Temos que χ0 = #A. Daı́ χ0 .χ0 = #(N × N). Mas (N × N) é
enumerável. Portanto #(N × N) = χ0
Exemplo 2.2.8. Podemos provar por indução sobre n que para n ≥ 1, χn0 := χ0 .χ0 . . . . .χ0 = χ0 .
|
{z
}
n vezes
14
Exemplo 2.2.9. χ0 .χ1 = χ1
De fato, temos que χ0 = #N, χ1 = #R = #P(N) = #P(N × N), pois N × N ≈ N . Assim
χ0 .χ1 = #(N × P(N))
Definimos F : N × P(N) −→ P(N × N) por F (n, S) = {n} × S.
Claramente F está bem definida. Além disso, F é injetora pois se F (n, S) = F (m, T ) temos
{n} × S = {m} × T. Daı́ {n} = {m} e S = T, o que nos dá (n, S) = (m, T ). (Observe que F
não é sobrejetora). Logo #(N × P(N)) ≤ P(N × N). Isto é,
χ0 .χ1 ≤ χ1
(1)
Por outro lado, considerando a aplicação h : R → N × R definida por temos h(x) = (0, x,
temos que h é claramente injetora. Assim #R ≤ (N × R). Isto é,
χ1 ≤ χ0 .χ1
(2)
De (1) e (2) temos χ1 = χ0 .χ1 .
Exemplo 2.2.10. Segue do Exemplo 1.1.10 que #R = #R2 = ... = #Rn = #C = #Cn = χ1 .
Daı́ temos que, para n ≥ 1, χn1 = χ1 .
III - Potenciação
Sejam u e v dois números cardinais e A e B tais que conjuntos u = #A e v = #B. Seja
AB = {f : A −→ B | f é função}. Definimos: uv = #(AB ) = #A#B
Proposição 2.2.11. (i) A operação potenciação está bem definida, isto é, uv não depende da
escolha dos representantes disjuntos A e B.
(ii) (u.v)w = uw .v w .
(iii) uv+w = uv .uw .
w
(iii) uv.w = uv .
2
Exemplo 2.2.12. Seja A um conjunto. Então #P(A) = 2#A .
De fato, vimos no Exemplo 1.1.12 que P(A) ≈ C(A). Mas C(A) = {0, 1}A .
#P(A) = #C(A) = #{0, 1}A = 2#A
Logo
Exemplo 2.2.13. χ1 = 2χ0 (daı́ pelo Teorema 2.1.8, #R = 2χ0 ). Mais geralmente χn = 2χn−1 .
De fato, χ1 = #P(N) = 2χ0 , (pelo exemplo anterior).
Suponha agora χn = 2χn−1 . Seja A = #P(P(. . . P(N))) (n+1 vezes). Temos que χn = #A.
Então χn+1 = #P(A) = 2#A = 2χn .
15
Capı́tulo 3
O Axioma da Escolha e o Lema de Zorn
3.1
Axioma da Escolha
O Axioma da Escolha (ou Axioma de Zermelo) é um dos axiomas mais importântes da
teoria dos conjuntos. Foi introduzido por Zermelo em 1904, quando provava uma conjectura
de Cantor (todo conjunto pode ser bem ordenado), e para provar essa conjectura assumiu o
axioma da Escolha como uma propriedade dos conjuntos.
Axioma da Escolha Dada uma famı́lia não vazia C de conjuntos não vazios, disjuntos dois a
dois, existe um conjunto E (denominado conjunto escolha) que contém exatamente um elemento
de cada conjunto da famı́lia C.
Observação 3.1.1. Seja C = {Aλ }λ∈L , L 6= ∅ Aλ 6= ∅ para todo λ ∈ L. O axioma da escolha
diz que existe o conjunto E formado por um elemento de cada Aλ . Não há um critério bem
definido para qual elemento de Aλ irá fazer parte de E. Os teoremas cujas demonstrações usam
o axioma da Escolha são todos existênciais: afirmam a existência de um objeto que pertence a
um conjunto e que satisfaz a uma certa propriedade. Logo, esse objeto não é construido, e sim
existe porque não pode deixar de existir.
Exemplo 3.1.2. Se A é um conjunto infinito então existe uma função injetora f : N −→ A.
Aidéia para provar isso é definir f da seguinte forma: como A 6= ∅, existe x0 ∈ A e fixamos
f (0) = x0 . Como A é infinito temos que A \ {x0 } é não vazio. Logo existe x1 ∈ A \ {x0 } e
fixamos f (1) = x1 . Ainda, A \ {x0 , x1 } é não vazio , e assim existe x2 ∈ A \ {x0 , x1 } e fixamos
f (2) = x2 , e assim sucessivamente tal que f (n) = xn e xn ∈ A \ {x0 , . . . , xn−1 }. Assim temos
que f é uma função bem definida e injetora.
Os argumentos acima tornam-se rigorosos matematicamente devido ao Axioma da Escolha.
Considere C = (Cn )n∈N = ({(x, Bn ), x ∈ Bn })n∈N onde Bn = A\{x0 , . . . , xn−1 }. Temos que C
é uma famı́lia não vazia de conjuntos não vazios disjuntos dois a dois. Pelo axioma da Escolha,
existe E = {(xn , Bn ), xn ∈ Bn }: conjunto escolha para C. Ou seja, E contém exatamente um
16
elemento de cada conjunto Cn de C. Assim, definimos f : N −→ A | f (0) = x0 , . . . , f (n) = xn ,
onde (xn , Bn ) ∈ E ∩ Cn . Desta forma f está bem definida e é injetora.
Definição 3.1.3. Dada uma famı́lia de conjuntos, o produto cartesiano da famı́lia é o conjunto
Y
[
Ai = {f : I −→
Ai ; f é função e f (i) ∈ Ai }
i∈I
i∈I
Definição 3.1.4. Seja S um conjunto não vazio, P(S) o conjunto das partes de S. Uma função
escolha para S é uma função γ : P(S) \ {∅} −→ S tal que γ(A) ∈ A para todo A ∈ P(S) \ {∅}.
Teorema 3.1.5. As formulações abaixo são equivalentes ao Axioma da Escolha:
F1. Dada uma famı́lia não vazia de conjuntos não vazios de C = (Ai )i∈I indexada por I, existe
[
uma função f : I −→
Ai tal que f (i) ∈ Ai para todo i ∈ I. Tal função é chamada
i∈I
função escolha para a famı́lia C.
F2. O produto cartesiano de uma famı́lia não vazia de conjuntos não vazios é não vazia.
F3. Todo conjunto não vazio tem uma função escolha.
Demonstração.
1. Primeiro demonstraremos que o Axioma da Escolha é equivalente a afirmação F1.
Suponha que o Axioma da escolha seja válido. Seja C = (Ai )i∈I uma famı́lia não vazia de
conjuntos não vazios. Considera C 0 = (Ai × {i})i∈I . Temos que C 0 satisfaz as hipóteses do
Axioma da Escolha. Logo existe um conjunto escolha E para C 0 . Definimos
[
f : I −→
Ai
i∈I
i 7−→ xi ,
onde (xi , i) é o único elemento de E ∩ (Ai × {i}). Logo, f está bem definida e f (i) ∈ Ai ,
para todo i ∈ I. Reciprocamente, suponha que a afirmação F1 é vãlida. Seja C = (Ai )i∈I
uma famı́lia
[ não vazia de conjuntos não vazios disjuntos dois a dois. Por hipótese, existe
f : I −→
Ai função escolha para a famı́lia C. Seja E = f (I), o conjunto imagem de f .
i∈I
Por construção, para cada i ∈ I, f (i) é o único elemento que também está em Ai . Logo,
E é um conjunto escolha para C.
2. Provemos que a afirmação F1 ié equivalente à afirmação F2.
Analizando a definição de profuto cartesiano de famı́lia, temos que dada uma famı́lia C
de conjuntos, uma função escolha para C é um elemento do produto da mesma. Logo,
existe uma função esolha para C se, e somente se o produto cartesiano da famı́lia C é não
vazio.
17
3. Provemos que as afirmações F3 e F3 sã equivalentes. Suponha que F2 seja válı́da.
Seja S um conjunto não vazio. Consideremos I = P(S) \ {∅} = {α ⊆ S; α 6= ∅} e a
famı́lia C = (Aα )α∈I onde Aα = α para todo α ∈ I. Como C = (Aα )α∈I satisfaz as
Q
hipóteses de F2, temos α∈I Aα 6= ∅,,[
então existe uma função f : I −→ ∪α∈I Aα tal que
f (α) ∈ Aα para todo α ∈ I. Como
Aα = S e f (Aα ) = f (α) ∈ S para todo α ∈ I,
α∈I
segue que f : P(S) \ {∅} −→ S é uma função escolha para S. Portanto, F2 é válido.
Reciprocamente, suponha que todo conjunto não vazio tem uma função escolha. Seja
[
C = (Ai )i∈I uma famı́lia não vazia de conjuntos não vazios. Considere S =
Ai . Temos
i∈I
que S é um conjunto não vazio . Logo por hipótese, existe γ : P(S) \ {0} −→ S uma
função escolha para S, isto é γ(A) ∈ A para todo A ∈ P(S){0}. Desse modo, a função
[
f : I −→
Ai
i∈I
i 7−→ f (i) = γ(Ai )
está bem definida e f (i) ∈ Ai para todo i ∈ I. Logo, f pertence ao produto cartesiano
de C, o que mostra que o produto cartesiano de C é não vazio.
3.2
Lema de Zorn
Na Matemática, um teorema de existência afirma a existência de um objeto que pertence a
um certo conjunto e que satisfaz certas propriedades. Muitos teoremas de existência podem ser
formulados de modo que a propriedade crucial seja a maximalidade ou minimalidade. O Lema
de Zorn é considerado o teorema mais importante deste tipo, e é aplicado para se demonstrar
outros teoremas em diversas áreas da Matemática tais como, Álgebra, Topologia e Análise.
Antes de enunciar o Lema de Zorn vamos recordar algumas definições.
Definição 3.2.1. Seja R uma relação sobre um conjunto A. Dizemos que R é uma relação de
ordem se, e somente se,
(i) R é reflexiva, isto é, aRa, ∀a ∈ A
(ii) R é transitiva, isto é, ∀ a, b, c ∈ A com aRb e bRc, tem-se aRc
(iii) R é anti-simétrica, isto é, ∀ a, b tal que aRb e bRa, tem-se a = b
Neste caso dizemos que A é parcialmente ordenado, e denotamos R por ≤. Quando a ≤ b,
dizemos que a precede b.
Definição 3.2.2. Um conjunto A é totalmente ordenado se, para todos a, b ∈ A, tem-se a ≤ b
ou b ≤ a, onde ≤ é uma relação de ordem sobre A.
Definição 3.2.3. Sejam S 6= ∅ um conjunto parcialmente ordenado pela relação ≤ e ∅ =
6 A ⊆ S.
Dizemos que um elemento x ∈ S é um limite superior (limite inferior) de A se, e somente se,
a ≤ x (x ≤ a), para todo a ∈ A.
18
Definição 3.2.4. Sejam A um conjunto parcialmente ordenado e m ∈ A. Dizemos que m é um
elemento maximal (minimal) de A se, e somente se, m não precede (m não é precedido por)
nenhum elemento de A \ {m}, isto é,
∀ x ∈ A | m ≤ x (x ≤ m) ⇒ x = m
Definição 3.2.5. Seja S um conjunto parcialmente ordenado. Uma cadeia em S é um subconjunto de S totalmente ordenado pela ordem induzida.
Vamos enunciar agora o Lema de Zorn.
Lema 3.2.6. (Lema de Zorn): Se S é um conjunto não vazio e parcialmente ordenado tal
que toda cadeia em S tem um limite superior, então S tem um elemento maximal.
2
Nosso objetivo agora é demonstrar a equivaência entre o Axioma da Escolha, o Lema de
Zorn e o Teorema da Boa Ordem de Zermelo. Para isso necesitamos de algumas definições e
resultados.
Definição 3.2.7. Sejam A uma coleção de subconjuntos de um outro conjunto S e A0 ∈ A.
Dizemos que uma subcoleção B de A é uma torre se, e somente se,
(i) A0 ∈ B
(ii) B 0 ∈ B ⇒ A0 ⊂ B 0
(iii) B 0 ∈ B ⇒ ϕ(B 0 ) ∈ B
[
D ∈ B, onde ϕ : A → A é tal
(iv) Se C for totalmente ordenada por inclusão, então
D∈C
que ϕ(A0 ) ⊃ A0 e ϕ(A0 ) − A0 contém no máximo, um elemento, para todo A0 ∈ A.
Observação 3.2.8. (1) Existe torre. Por exemplo, a coleção {A0 } formada de um único
elemento é uma torre.
(2) Se B0 for a intersecção de todas as torres (relativas a A0 e ϕ), então B0 é uma torre. Além
disso, B0 é torre mı́nima.
De fato,
\
(i) Temos que A0 ∈ B, ∀ B tal que B é torre. Logo, A0 ∈
B.
B é torre
\
0
0
(ii) Se B ∈
B então B ∈ B, ∀ B tal que B é torre. Logo, A0 ⊆ B 0 .
B é torre
\
0
(iii) Se B ∈
B então B 0 ∈ B, ∀ B tal que B é torre. Assim, ϕ(B 0 ) ∈ B ∀ B tal
B é torre
\
que B é torre. Portanto, ϕ(B 0 ) ∈
B.
B é torre
[
(iv) Se C é uma coleção totalmente ordenada, então
D ∈ B, ∀ B tal que B é torre.
D∈C
[
\
Logo,
D∈
B.
D∈C
B é torre
19
Definição 3.2.9. Um elemento E ⊂ B0 ∈
\
B é denominado normal se ele for com-
B é torre
parável (em relação á inclusão de conjuntos) com qualquer elemento de B0 .
\
Exemplo 3.2.10. A0 é normal, pois A0 ⊆ B 0 , B 0 ∈ B0 =
B .
B é torre
\
Lema 3.2.11. Se B0 =
B então B0 é totalmente ordenada por inclusão.
B é torre
Demonstração. Se D for normal, o conjunto B = {C ∈ B0 | C ⊆ D ou ϕ(D) ⊆ C} é torre. De
fato,
(i) A0 ∈ B, pois como D ⊆ B0 e B0 é torre, pelo item (ii) da Definição 4.29, A0 ⊆ D.
(ii) Se E ∈ B então E ∈ B0 . Portanto, A0 ⊆ E.
(iii) Seja C ∈ B. Então C ⊆ D ou ϕ(D) ⊆ C. Daı́,temos as seguintes situações
• Se ϕ(D) ⊆ C então ϕ(D) ⊆ C ⊆ ϕ(C). Logo, ϕ(C) ∈ B.
• Se C ⊆ D, como ϕ(C) ∈ B0 e D é normal, temos ϕ(C) ⊆ D ou D ⊆ ϕ(C). Mas, se ϕ(C) ⊆ D,
então ϕ(C) ∈ B. Por outro lado, se D ⊆ ϕ(C), temos que C ⊆ D ⊆ ϕ(C) Logo, ϕ(C) = D.
Assim, (ϕ(C) ⊆ D) ou C = D e daı́ ϕ(C) = ϕ(D) (ϕ(D) ⊆ ϕ(C)), e de qualquer modo,
ϕ(C) ∈ B.
(iv) Seja E uma subcoleção
ordenada por inclusão. Se para cada C ∈ E
[ de B, totalmente [
tivermos C ⊆ D, então
C ⊆ D e assim,
C ∈ B. Se para algum C ∈ E tivermos
C∈E
C∈E [
[
ϕ(C) ⊆ C, então, como D ⊆ ϕ(D), temos ϕ(D) ⊆
C. Assim,
C ∈ B.
C∈E
C∈E
Portanto, B é uma torre. Forçosamente B = B0 , pois B ⊆ B0 e B0 é minimal.
Agora, seja B 0 o conjunto de todos os elementos normais de B0 . B 0 é torre. De fato, as
condições (i), (ii), (iv) da definição são imediatas. Vejamos a condição (iii) da definição.
Seja A ∈ B 0 . Vimos que a coleção B = {C ∈ B0 | C ⊆ A ou ϕ(A) ⊆ C} = B0 .
Assim, se X ∈ B0 então, X ⊆ A ou ϕ(A) ⊆ X. Logo, ϕ(A) é comparável com qualquer
elemento de B0 . Portanto, ϕ(A) ∈ B 0 .
Dessa forma, como B 0 ⊆ B0 temos B 0 = B0 . Assim, todo elemento de B0 é normal.
Portanto, B0 é totalmente ordenada.
Lema 3.2.12. Seja A uma coleção não vazia de subconjuntos de S, com
[ a propriedade que, se
C for uma subcoleção de A totalmente ordenada por inclusão, então
B ∈ A. Suponhamos
B∈C
também que ϕ : A → A seja tal que ϕ(D) ⊇ D e que ϕ(D) − D contenha, no máximo, um
elemento, para todo D ∈ A. Nestas condições, A contém um conjunto D tal que ϕ(D) = D.
Demonstração. [
Utilizaremos o Lema anterior.
Seja D =
B. Temos que D ∈ B0 , pois B0 é totalmente ordenada e é torre. E daı́,
B∈B0
[
temos também que ϕ(D) ∈ B0 . Então, ϕ(D) ⊆
B∈B0
D ⊆ ϕ(D). Logo, ϕ(D) = D.
20
B = D. E, pela definição de ϕ, temos que
Corolário 3.2.13. Seja S um conjunto parcialmente ordenado, no qual todo subconjunto totalmente ordenado tem supremo. Se f : S → S é uma função tal que f (x) ≥ x, para todo x ∈ S,
então existe pelo menos um x ∈ S para o qual f (x) = x.
Demonstração. Sejam x0 ∈ S e σ a coleção dos A ⊆ S com as seguintes propriedades:
(i) x0 ∈ A;
(ii) A é totalmente ordenado.
[
Se τ for qualquer subcoleção de σ, totalmente ordenada por inclusão, teremos
B ∈ σ.
B∈τ
De fato,
[
(a) Como τ ⊆ σ então x0 ∈ B, ∀ B ∈
B.
B∈τ
[
(b) Sejam x, y ∈
B. Então, x ∈ B1 e y ∈ B2 , para algum B1 , B2 ∈ τ . Como τ é totalmente
B∈τ
ordenada por inclusão, temos B1 ⊆ B2 ou B2 ⊆ B1 . Sem perda de generalidade, suponhamos
B1 ⊆ B2 . Então x, y[∈ B2 . Daı́, como B2 ∈ τ ⊆ σ, B2 é totalmente
ordenado, então x ≤B y ou
[
y ≤B x. Portanto,
B é totalmente ordenada e assim
B ∈ σ.
B∈τ
B∈τ
Definimos ϕ : σ → σ da seguinte forma:
(
ϕ(A) =
A ∪ {f (x)}
se x = sup(A) ∈ A
A ∪ {sup(A)} se sup(A) ∈ A
Temos ϕ(A) ⊇ A e ϕ(A) − A tem no máximo um elemento, para todo A ∈ σ.
Assim, ϕ e σ satisfazem as condições do lema anterior. Logo, existe A0 ∈ σ tal que ϕ(A0 ) =
A0 . Mas, pela definição de ϕ, se sup(A0 ) ∈/ A0 então ϕ(A0 ) 6= A0 . Logo, sup(A) = x ∈ A, e
assim f (x) = x (pois f (x) ≥ x, ∀ x ∈ S).
Teorema 3.2.14. As seguintes afirmações são equivalentes:
(1) Axioma da Escolha;
(2) Qualquer conjunto parcialmente ordenado, no qual todo subconjunto ordenado possui
supremo, contém um elemento maximal;
(3) Qualquer conjunto parcialmente ordenado contém um subconjunto totalmente ordenado
maximal;
(4) Lema de Zorn: Qualquer conjunto parcialmente ordenado, não vazio, no qual todo
subconjunto totalmente ordenado tem limite superior, contém um elemento maximal;
(5) Teorema da Boa Ordem de Zermelo: Qualquer conjunto pode ser bem ordenado.
Demonstração. (1) ⇒ (2) Seja S um conjunto parcialmente ordenado no qual os seus subconjuntos parcialmente ordenados tem supremo. Seja γ uma função escolha para S, isto é, uma
função γ : P(S) → S tal que γ(A) ∈ A, para todo A ∈ P(S) − ∅.
Definimos f : S → S da seguinte forma: Se Ax := {y ∈ S | y ≥ x}, então
(
f (x) :=
f (x) = γ(Ax ), se Ax 6= ∅;
f (x) = x,
se Ax = ∅.
21
f satisfaz as hipóteses do Corolário anterior. Logo, existe x ∈ S tal que f (x) = x. Esse x
deve ser de tal forma que Ax = ∅, ou seja, x é um elemento maximal.
(2) ⇒ (3) Seja S um conjunto parcialmente ordenado. Seja S 0 a coleção dos subconjuntos
totalmente ordenados de S. S 0 é parcialmente ordenada por inclusão e S 0 tem a propriedade
de que qualquer de seus subconjuntos totalmente
ordenados tem supremo, pois se A for um
[
subconjunto totalmente ordenado então
C é supremo de A. Daı́, por (2), S 0 tem um
C∈A
elemento maximal de A. Assim, A é um subconjunto totalmente ordenado maximal de S.
(3) ⇒ (4) Seja S um conjunto, no qual todo subconjunto totalmente ordenado tem um limite
superior. Seja A um subconjunto totalmente ordenado maximal de S. Então, se x é um limite
superior de A, x é um elemento maximal de S.
(4) ⇒ (5) Seja S um conjunto qualquer. Denotemos por S a coleção de todos os subconjuntos
bem ordenados de S, com as respectivas ordens, isto é,
S = {A ⊆ S; (A, ≤A ) é bem ordenado}
Dados A, B ∈ S, definimos:


 A⊆B
A≤B⇔
x, y ∈ A, x ≤A y ⇔ x ≤B y


∀ x ∈ A, ∃ b ∈ B : x ≤B b
Assim, S é parcialmente ordenado pela relação ≤.
[
Sejam σ uma famı́lia totalmente ordenada de S e A∗ =
A. Vamos bem ordenar A∗ .
A∈σ
Sejam x, y ∈ A∗ . Então x ∈ A e y ∈ B, para algum A, B ∈ σ. Sendo σ totalmente ordenada
por inclusão, temos A ⊆ B ou B ⊆ A. Assim, existe C ∈ σ (C = B ou A) tal que x, y ∈ C.
Definimos x ≤∗ y se, e somente se, x ≤c y.
Temos que A∗ é bem ordenada por ≤∗ e A ≤ A∗ , para todo A ∈ σ. Assim, todo subconjunto
totalmente ordenado de S tem um limite superior. Portanto, por (4), S tem um elemento
maximal M . Mostremos que M = S.
Suponhamos o contrário, ou seja, S−M 6= ∅. Então existe x ∈ S−M . Fazendo A = M ∪{x}
e bem ordenando A, considerando a ordem de M para dois elementos quaisquer de M e pondo
x ≥ y, para todo y ∈ M , segue que A ≥ M , o que contradiz o fato de M ser maximal. Logo,
M = S e assim S é bem ordenado.
(5) ⇒ (1) Seja S um conjunto. Por (5), S pode ser bem ordenado, então o consideraremos
bem ordenado. Definimos γ : P(S) − {∅} → S por γ(A) = menor elemento de A. Temos que
γ é uma função escolha para S, pois γ(A) ∈ A, para todo A ∈ P(S) − {∅}.
22
3.3
Algumas aplicações do Lema de Zorn
Aplicação 1: Todo espaço vetorial sobre um corpo K tem um base.
Demonstração. Lembramos que uma base B de um espaço vetorial V é um conjunto de vetores
n
X
L.I. que gera o espaço, isto é, se
αi vi = 0, com αi ∈ K e vi ∈ B, então αi = 0, ∀ i e dado
i=1
v ∈ V, existem αi ∈ K e vi ∈ B tais que v =
n
X
αi vi .
i=1
Nestas condições, uma base de um espaço vetorial é um conjunto de vetores L.I. maximal
relativamente a esta propriedade (isto é, um conjunto L.I. maximal no sentido que acrescido de
qualquer vetor do espaço, o conjunto B passa as ser L.D.).
De fato, se B é L.I. maximal, dado x ∈ V, o conjunto B 0 = B ∪ {x} é L.D., de modo que x
é combinação linear de elementos de b e, em consequência, B gera v.
Reciprocamente, se B é L.I. e gera V, então B é L.I. maximal, pois se B ⊂ B 0 e x ∈ B 0 − B,
n
X
daı́ x =
αi vi com αi ∈ K e vi ∈ B. Assim B’ é L.D.. Logo não existe x ∈ B 0 − B e B 0 = B.
i=1
Agora vamos demonstrar que V tem uma base.
Se V = {0}, então ∅ é base de V,de modo que podemos supor V 6= {0}.
Considere B = {B ⊆ V : B 6= ∅ e B é L.I.}. B é parcialmente ordenado (por inclusão),
isto é, ⊂ é uma relação de ordem sobre B.
[
Aα é tal que D ∈ B e Aα ⊂ D,
Seja {Aα }α∈L uma cadeia de elementos de B. Então D =
α∈L
∀α ∈ L, de modo que {Aα } é um limite superior.
Portanto, pelo Lema de Zorn, B tem um elemento maximal B e tal elemento é uma base
de V.
Definição 3.3.1. Sejam A e B conjuntos. Se A ⊂ B mas A 6= B, dizemos que A é um
subconjunto próprio de B ou que B contém A propriamente.
Aplicação 2: Seja X um conjunto parcialmente ordenado. Então existe um subconjunto
totalmente ordenado de X o qual não é um subconjunto próprio para nenhum outro subconjunto
totalmente ordenado de X. Ou seja, X possui um subconjunto ordenado maximal.
Demonstração. Seja A a classe de todos subconjuntos totalmente ordenados de X. Temos que
A parcialmente ordenado (pela relação de inclusão). Queremos mostrar, pelo Lema de Zorn,
que A possui um elemento maximal.
Suponhamos B = {Bi : i ∈ I} uma subclasse totalmente ordenada de A (isto é, B é um
cadeia de elementos
de A.)
[
Seja A =
Bi . Temos que Bi ⊂ X, ∀Bi ∈ B, daı́ A ⊂ X.
i∈I
Agora, mostremos que A é totalmente ordenado.
23
Sejam a, b ∈ A, então ∃Bj , Bk ∈ B tal que a ∈ Bj , b ∈ Bk . Mas B é totalmente ordenado
pela inclusão, ou seja, Bj ⊂ Bk ou Bk ⊂ Bj . Vamos supor que Bj ⊂ Bk . Consequentemente,
a, b ∈ Bk . Como Bk é totalmente ordenado temos a ≤ b ou b ≤ a. Assim, A é um subconjunto
totalmente ordenado de X e dessa forma, A ∈ A. Mas Bi ⊂ A, ∀Bi ∈ B, assim A é um limite
superior de B.
Logo, pelo Lema de Zorn, A tem um elemento maximal, isto é, um subconjunto totalmente
ordenado de X o qual não é um subconjunto próprio para nenhum outro subconjunto totalmente
ordenado de X.
Aplicação 3: Seja R uma relação de A para B, isto é, R ⊂ A×B, e suponhamos que o domı́nio
de R é A. Então existe um subconjunto f ∗ de R tal que f ∗ é uma função de A em B.
Demonstração. Seja A a classe de subconjuntos de R tal que cada f ∈ A é uma função de um
subconjunto de A em B.
Seja A parcialmente ordenado pela inclusão. Daı́ se f : A1 → B é um subconjunto de
g : A2 → B então A1 ⊂ A2 .
Agora suponhamos B = ({fi : Ai → B})i∈i um subconjunto totalmente ordenado de A (isto
[
[
Ai → B. definida por f (a) = fi (a)
fi :
é, B é uma cadeia de elementos de A). Seja f =
i∈I
i∈I
se a ∈ Ai . Temos que f está bem definida pois B é totalmente ordenado. Além disso, como
fi ⊂ R, ∀fi ∈ B, segue que f ⊂ R. Assim, f é um limite superior de B.
Logo, pelo Lema de Zorn, A possui elemento maximal f ∗ : A∗ → B.
Resta provar que A∗ = A.
Suponhamos A∗ 6= A. Então ∃a ∈ A tal que a 6∈ A∗ . Por hipótese, o domı́nio de R é A,
então existe um par ordenado (a, b) ∈ R. Daı́, f ∗ ∪ {(a, b)} é uma função de A∗ ∪ {a} em B.
Mas isto contradiz o fato que f ∗ é um elemento maximal em A.
Assim A = A∗ e a aplicação fica completa.
24
Bibliografia
[1] Izar, S., Tadini, W.M.; Teoria Axiomática dos Conjuntos, Ed. UNESP, 1994.
[2] Lipshutz, L., Topologia Geral, Coleção Schaum, Ed. Macgraw-Hill, 1973.
[3] Lipshutz, L., Teoria dos Conjuntos, Coleção Schaum, Ed. Macgraw-Hill, 1972.
25