introdução aos números naturais

Prévia do material em texto

Nu´meros naturais e cardinalidade
Roberto Imbuzeiro M. F. de Oliveira∗
5 de Janeiro de 2008
Resumo
1 Axiomas de Peano e o princ´ıpio da induc¸a˜o
Intuitivamente, o conjunto N dos nu´meros naturais corresponde aos nu´meros
1, 2, 3, . . . . Os chamados axiomas de Peano descrevem as propriedades fun-
damentais destes nu´meros em termos abstratos, atrave´s de treˆs propriedades
intuitivas ba´sicas.
1. Existeˆncia de sucessor: todo elemento n ∈ N tem um sucessor, chamado
provisoriamente de s(n). Dois elementos distintos de N teˆm sucessores
tambe´m distintos. [Isto implica que a func¸a˜o s : N→ N que leva cada
natural em seu sucessor e´ injetiva.]
2. Existeˆncia de um primeiro elemento. Existe um elemento de N, chamado
de 1, tal que 1 6= s(n) para todo n ∈ N (isto e´, 1 na˜o e´ o sucessor de
nu´mero algum em N).
3. Princ´ıpio da induc¸a˜o: seja X ⊂ N um subconjunto tal que 1 ∈ X e
s(n) ∈ X para todo n ∈ X. Enta˜o X = N.
O u´ltimo axioma e´ o de mais dif´ıcil compreensa˜o. Um exemplo do seu
uso e´ dado logo a seguir.
Teorema 1. Para todo n ∈ N, s(n) 6= n.
∗IMPA, Rio de Janeiro, RJ, Brazil, 22430-040. rimfo@impa.br
1
Prova: Seja
X = {n ∈ N : s(n) 6= n}.
Veja que X e´ um subconjunto de N. Provaremos que X = N usando o
axioma 3.
1. 1 ∈ X, ja´ que, pelo segundo axioma, 1 6= s(1).
2. Se n ∈ X, enta˜o s(n) 6= n. Como s e´ injetiva, para todos x, y ∈ N com
x 6= y tem-se s(x) 6= s(y). Em particular, para n ∈ X como acima,
veˆ-se que s(s(n)) 6= s(n) (tome x = s(n), y = n). Donde conclu´ımos
que s(n) ∈ X. Portanto, s(n) ∈ X para qualquer n ∈ X.
2
2 Soma, produto e ordem
Agora mostramos como as operac¸o˜es ba´sicas sobre os naturais podem ser
definidas a partir dos axiomas. Comec¸amos com a adic¸a˜o. Ela e´ uma
operac¸a˜o que leva um par de nu´meros na sua soma, portanto e´ uma func¸a˜o
de N× N em N:
soma : N× N→ N.
Fato 1. Existe uma u´nica func¸a˜o soma como acima tal que para todo p ∈ N:
• soma(p, 1) = s(p); e
• seja n ∈ N. Enta˜o soma(p, s(n)) = s(soma(p, n)).
Fato 2. Existe uma u´nica func¸a˜o prod : N×N→ N tal que para todo p ∈ N:
• prod(p, 1) = p; e
• Seja n ∈ N. Enta˜o prod(p, s(n)) = soma(prod(p, n), p).
Em geral escreveremos p+n no lugar de soma(p, n) e pn ou p.n no lugar
de prod(p, n). Os seguintes fatos sa˜o essenciais.
Teorema 2 (Associatividade da soma). Para todos p, q, r ∈ N, soma(soma(p, q), r) =
soma(p, soma(q, r)). Ou seja, (p+ q) + r = p+ (q + r).
2
Prova: Fixe p, q ∈ N. Mostraremos que o conjunto
X = Xp,q ≡ {r ∈ N : (p+ q) + r = p+ (q + r)}
e´ igual a N. Como p, q sa˜o arbitra´rios, isto prova o teorema.
Note primeiro que 1 ∈ X, ja´ que, usando as duas propriedades da soma
(a primeira, a segunda e a primeira nesta ordem):
soma(soma(p, q), 1) = s(soma(p, q)) = soma(p, s(q)) = soma(p, soma(q, 1)).
Provaremos agora que n ∈ X implica que s(n) ∈ X; deste modo, X = N
seguira´ por induc¸a˜o. Veja que se n ∈ X, enta˜o
soma(soma(p, q), n) = soma(p, soma(q, n)).
Tomando o sucessor dos dois lados da igualdade,
s(soma(soma(p, q), n)) = s(soma(p, soma(q, n))). (1)
Note agora que, pela segunda propriedade da soma, o lado esquerdo de (1)
e´ igual a
soma(soma(p, q), s(n)),
enquanto o lado direito e´ igual a
soma(p, s(soma(q, n))) = soma(p, soma(q, s(n)))
onde a igualdade decorre da prop. 2 da soma usada mais uma vez. Segue
que:
soma(soma(p, q), s(n)) = soma(p, soma(q, s(n))),
logo s(n) ∈ X, como desejado. 2
Teorema 3 (Comutatividade da soma). Para todos m,n ∈ N, m + n =
n+m.
Prova: Fixe um n ∈ N e defina o conjunto dos elementos de N que comutam
com n.
Cn ≡ {m ∈ N : m+ n = n+m}.
Nosso objetivo e´ provar que Cn = N para todo n ∈ N.
Primeiro provaremos que 1 ∈ Cn para todo n, o que equivale a provar
que C1 = N. Para isso, usaremos induc¸a˜o. Veja que 1 ∈ C1 trivialmente, ja´
que 1 + 1 = 1 + 1.
3
Seja agora n ∈ C1; provaremos que s(n) ∈ C1 (donde seguira´ C1 = N).
Veja que 1 + n = n + 1 (pois n ∈ C1), logo s(1 + n) = s(n + 1) = n + s(1)
pela primeira propriedade da soma. Ale´m disso, s(1 + n) = 1 + s(n), pela
segunda propriedade. Unindo as duas igualdades, temos 1+s(n) = n+s(1).
Mas note que n+s(1) = n+(1+1) = (n+1)+1 por associatividade, e como
(n+ 1) = s(n), temos n+ s(1) = s(n) + 1. Segue, portanto, que s(n) ∈ C1,
como quer´ıamos demonstrar.
A partir do que provamos, o princ´ıpio da induc¸a˜o mostra que C1 = N.
Agora mostraremos que, dado um n ∈ N fixo, temos Cn = N. Novamente
usaremos induc¸a˜o, notando que 1 ∈ Cn segue do que vimos acima. Agora
note que, se m ∈ Cn, temos (pela segunda prop. da soma):
n+ s(m) = s(n+m) = s(m+ n) (ja´ que m ∈ Cn) = m+ s(n).
Ale´m disso, m + s(n) = m + (n + 1) = m + (1 + n), ja´ que 1 + n = n + 1
(ou seja, n ∈ C1, provado acima). Por sua vez a associatividade implica que
m+(1+n) = (m+1)+n = s(m)+n. Deduzimos que n+ s(m) = s(m)+n
(isto e´, s(m) ∈ Cn) sempre que m ∈ Cn. Como 1 ∈ Cn ⊂ N, o princ´ıpio da
induc¸a˜o implica que Cn = N, como desejado. 2
O Exerc´ıcio 1 abaixo prova que:
Proposic¸a˜o 4. Tambe´m valem a comutatividade e associatividade da mul-
tiplicac¸a˜o, assim como a distributividade.
3 Ordem
Definimos o que chamamos de ordem.
Definic¸a˜o 5 (Ordem). Se n,m ∈ N, dizemos que n < m (ou equivalente-
mente m > n) se existe algum p ∈ N tal que m = n+ p.
Proposic¸a˜o 6. [1 e´ menor que qualquer outro natural] Para todo n ∈ N, ou
1 = n ou 1 < n.
Prova: Seja X o seguinte subconjunto de N:
X = {n ∈ N : n = 1 ou 1 < n}.
Provaremos que X = N por induc¸a˜o. De fato, 1 ∈ X ja´ que 1 = 1. Ale´m
disso, se n ∈ X, temos duas alternativas:
4
1. A primeira alternativa e´ n 6= 1. Neste caso, 1 < n, ja´ que n ∈ X. Deste
modo, existe p ∈ N tal que 1 + p = n. Pelas regras da soma, vemos
que s(n) = s(1 + p) = 1+ s(p), logo existe um elemento p′ = s(p) ∈ N
tal que s(n) = 1 + s(p). Da´ı se deduz que se n ∈ X e n 6= 1, s(n) > 1,
logo s(n) ∈ X.
2. A segunda alternativa e´ n = 1. Neste caso, pelas propriedades da
soma s(1) = 1 + 1 e como acima veˆ-se que s(1) ∈ X.
Obviamente, se n ∈ X, n = 1 ou n 6= 1. Nos dois casos, vimos que s(n) ∈ X.
Logo ∀n ∈ X, s(n) ∈ X. Como 1 ∈ X, o Princ´ıpio da Induc¸a˜o mostra que
X = N, como quer´ıamos demonstrar. 2
Observac¸a˜o 7. A demonstrac¸a˜o acima lista todas as possibilidades para
n ∈ X e prova a afirmac¸a˜o desejada em cada um dos casos. Esta te´cnica
chama-se ana´lise de casos e e´ extremamente u´til, embora algo cansativa.
Proposic¸a˜o 8 (Cancelamento). Sejam dados quatro nu´meros a, b, c, d ∈ N.
Enta˜o a = b e´ equivalente a a + c = b + c e a ad = bd. Do mesmo modo,
a < b equivale a a+ c < b+ c e a ad < bd.
Prova: Provaremos apenas a equivaleˆncia entre a = b e a + c = b + c. O
resto fica como exerc´ıcio.
Seja
H = {c ∈ N : ∀a, b ∈ N “a+ c = b+ c”⇒ “a = b”}.
Provaremos que H = N pelo princ´ıpio da induc¸a˜o.
1 ∈ H porque para quaisquer a, b ∈ N, “a + 1 = b + 1”equivale a
“s(a) = s(b)”; e como pelos axiomas de Peano, naturais distintos teˆm suces-
sores distintos, veˆ-se que “s(a) = s(b)”e´ equivalente a a = b. Donde con-
clu´ımos que a = b equivale a a+ 1 = b+ 1, isto e´, 1 ∈ H.
Agora veja que se c ∈ H , para todos a, b ∈ N,
a+c = b+c⇔ s(a+c) = s(b+c) (s e´ injetiva) ⇔ a+s(c) = b+s(c) (prop. 2 da soma).
Em particular, a+ s(c) = b+ s(c)⇒ a+ c = b+ c⇒ a = b onde a segunda
equivaleˆncia corresponde ao fato que c ∈ H. Deduzimos que c ∈ H ⇒ s(c) ∈
H, o que, junto com o resultado do para´grafo anterior, implica que H = N.
2
5
Proposic¸a˜o 9 (Transitividade da ordem). Se a, b, c ∈ N satisfazem a < b e
b < c, enta˜o a < c.
Prova: Se a, b, c sa˜o como acima, existem p1, p2 ∈ N com b = a + p1, c =
b+ p2. Deduzimos que:
c = (a+p1)+p2 = a+(p1+p2) (por assoc.) = a+p, onde p ≡ p1+p2 ∈ N.
Donde a < c, como desejado. 2
Proposic¸a˜o 10 (Tricotomia da ordem). Se a, b ∈ N, enta˜o ha´ exatamente
treˆs possibilidades poss´ıveis e mutuamente excludentes: a < b, a= b ou
a > b.
Prova: Chame a de tricotoˆmico se para todo b ∈ N a tricotomia acima se
verifica. Provaremos por induc¸a˜o que T = N.
Prova de que 1 ∈ T : para todo b ∈ N temos a dicotomia fundamental:
ou b = 1, ou b 6= 1. O segundo caso implica que b > 1. Logo a tricotomia
na˜o vale se e somente se b > 1 ⇒ b 6= 1, pois neste caso “ou b = 1, ou
b > 1”e´ uma dicotomia equivalente a´ anterior. Mas veja que b > 1 implica
que 1 + p = b para algum p ∈ N, logo b = p + 1 = s(p) para o mesmo p.
Portanto, b e´ o sucessor de p, o que implica (pelos axiomas de Peano) que
b 6= 1.
Prova de ∀n ∈ T, s(n) ∈ T : Seja n ∈ T . Tome b ∈ N. Se b = 1,
sabemos pelos axiomas que s(n) 6= 1, logo s(n) > b sempre e esta e´ a u´nica
possibilidade. Se b 6= 1, enta˜o b = s(c) = c + 1 para algum c ∈ N (tambe´m
pelos axiomas). Pelas propriedade de cancelamento, vemos que b < n + 1,
b = n + 1 e b > n + 1 sa˜o respectivamente equivalentes a c < n, c = n e
c > n. Como n ∈ T , estas treˆs u´ltimas possibilidades sa˜o tricotoˆmicas, de
modo que b < n+1, b = n+1 e b > n+1 tambe´m o sa˜o. Donde deduzimos
que s(n) = n+ 1 ∈ T tambe´m. 2
4 A segunda forma da induc¸a˜o
Antes de prosseguir, provaremos uma forma modificada da propriedade de
induc¸a˜o, que usaremos posteriormente.
Teorema 11 (Segunda forma da induc¸a˜o). Seja X ⊂ N um subconjunto de
N com 1 ∈ X e
∀i ∈ N, se j ∈ X para todo j ≤ i, enta˜o i+ 1 ∈ X.
6
Enta˜o X = N.
Prova: Considere X como acima. Seja Y = {n ∈ N : ∀x ≤ n, x ∈ X}.
Note que N ⊃ X ⊃ Y . Provaremos pela induc¸a˜o tradicional que de fato
Y = N (em particular, X = Y = N).
Veja que 1 ∈ Y , ja´ que todo x ∈ N com x ≤ 1 e´ igual a 1, e ale´m disso
1 ∈ X. Agora suponha que n ∈ Y . Veja que enta˜o ∀j ≤ n, j ∈ X, de modo
que, por hipo´tese, n+ 1 = s(n) ∈ X. Para mostrar que s(n) ∈ Y , basta ver
que todo x < n tambe´m esta´ em x. Para isto, consideramos dois casos:
1. se x = 1, enta˜o x ∈ X por hipo´tese;
2. se x > 1, enta˜o x = a+ 1 para algum a ∈ N (isto e´, x e´ o sucessor de
algum a) e ale´m disso, como x < n+1, temos x+p = n+1 para algum
p ∈ N. Vemos que (usando assoc., comut, assoc e cancelamento)
n+1 = x+p = (a+1)+p = a+(1+p) = a+(p+1) = (a+p)+1⇒ n = a+p⇒ n > a.
Deste modo, usando um exerc´ıcio abaixo, sabemos que ou n > a+1 =
x, ou n = x. De qualquer maneira, veˆ-se que x ≤ n e, como n ∈ Y ,
x ∈ X.
Deduzimos que n ∈ Y implica x ∈ X para todo x ≤ s(n), logo s(n) ∈ Y .
2
5 O mı´nimo de um conjunto
Proposic¸a˜o 12 (Existeˆncia do elemento mı´nimo). Todo subconjunto na˜o-
vazio X de N possui um u´nico elemento x = minX, chamado de elemento
mı´nimo, tal que para todo y ∈ X\{x}, tem-se y > x.
Prova: Defina:
R ≡ {z ∈ N : ∀X ⊂ N “z ∈ X”⇒ “∃!x ∈ X : ∀y ∈ X\{x}, x < y”}.
Provaremos pela segunda forma da induc¸a˜o que R = N, o que implica o
teorema.
Veja que 1 ∈ R: se X contem 1, enta˜o minX = 1 e´ o u´nico min de X:
qualquer outro elemento de X e´ maior que 1, como vimos acima.
Suponha agora que n ∈ N e´ tal que para todo a ≤ n, a ∈ R. Provaremos
que n + 1 ∈ N. Para isto, basta mostrar que qualquer conjunto X ⊂ N
contendo n + 1 tem um u´nico mı´nimo. Seja enta˜o X como acima. Temos
duas possibilidades:
7
1. Existe a < n + 1 contido em X. Neste caso, pelo Exerc´ıcio 2, a ≤ n,
logo a ∈ R por hipo´tese da induc¸a˜o. Como a ∈ X, isto significa que
“∃!x ∈ X : ∀y ∈ X\{x}, x < y”, como desejado.
2. Para todo a ∈ X, a ≥ n + 1. Mas enta˜o todo y ∈ X\{n + 1} e´
diferente de n+ 1 e na˜o e´ menor que ele, donde (tricotomia) e´ maior:
y > n + 1. Conclu´ımos que neste caso x = n + 1 e´ o mı´nimo de X,
com as propriedades desejadas.
Logo n+ 1 ∈ R sempre que j ∈ R para todo j ≤ n. Portanto, R = N, como
desejado. 2
6 Cardinalidade de conjuntos finitos
Os seguintes conjuntos sa˜o fundamentais para a contagem de elementos de
outros conjuntos.
Definic¸a˜o 13. Se n ∈ N, chamamos de [n] ou In o seguinte conjunto:
In = [n] ≡ {m ∈ N : m ≤ n}.
Proposic¸a˜o 14 (Ordem e conjuntos). Para n,m ∈ N, n ≤ m se e somente
se [n] ⊂ [m]. Se n < m, enta˜o [n] ⊂ [m] mas [n] 6= [m].
Prova: Exerc´ıcio simples. 2
Definic¸a˜o 15. Dizemos que um conjunto na˜o-vazio X e´ finito se existe uma
func¸a˜o injetiva fk : X → [k] para algum k ∈ N. Seja UX ⊂ N o conjunto
de todos os k ∈ N para os quais existe uma fk deste tipo (UX 6= ∅ se X e´
finito). Chamamos minUX de nu´mero de elementos (ou cardinalidade) de
X (#X ou card(X)). Se X na˜o e´ finito, e´ dito infinito.
Note que #∅ ainda na˜o foi definida (deveria ser 0, claro, mas este nu´mero
ainda na˜o nos foi apresentado).
Proposic¸a˜o 16. Sejam X,Y conjuntos finitos. Se ha´ uma injec¸a˜o de X
em Y , enta˜o #X ≤ #Y . Se ha´ uma sobrejec¸a˜o, #X ≥ #Y . Se ha´ uma
bijec¸a˜o, #X = #Y .
Prova: Primeira afirmac¸a˜o: Seja ψ : X → Y uma injec¸a˜o e k = #Y .
Sabemos que existe uma injec¸a˜o f : Y → [k]. A compisic¸a˜o g = f ◦ψ e´ uma
injec¸a˜o de X em [k], logo #X ≤ k.
8
Segunda afirmac¸a˜o: Seja η : X → Y uma sobrejec¸a˜o e f : X → [k] uma
injec¸a˜o, onde k = #X. Isto significa que para todo y ∈ Y ,
Sy ≡ {i ∈ [k] : ∃x ∈ X “f(x) = i” ∧ “η(x) = y”}.
e´ na˜o vazio, ja´ que existe algum x com η(x) = y. Defina:
α : Y → [k]
y 7→ α(y) ≡ minSy.
Note que isto esta´ bem definido porque Sy 6= ∅ e´ um subconjunto de N.
Provaremos que α e´ uma injec¸a˜o, de modo que #Y ≤ k = #X c.q.d. De
fato, sejam y, z ∈ Y com α(y) = α(z). Enta˜o Sy ∩ Sz 6= ∅, ja´ que os dois
conjuntos teˆm o mesmo mı´nimo. Isto implica que existe algum x ∈ X com
η(x) = y e η(x) = z, donde vemos que y = z. Provamos, portanto, que
∀y, z ∈ Y α(z) = α(y)⇒ z = y,
ou seja, α e´ injetiva.
Terceira afirmac¸a˜o: Se ha´ uma bijec¸a˜o h : X → Y , enta˜o h e´ injetiva e
sobrejetiva, logo #X ≤ #Y e #X ≥ #Y . Dito de outro modo, #X 6> #Y
e #X 6< #Y . Deduzimos da tricotomia da ordem que #X = #Y . 2
Proposic¸a˜o 17. Suponha que A ⊂ [n] e´ na˜o vazio mas A 6= [n]. Enta˜o
#A < n.
Prova: Note (exerc´ıcio) que n > 1. Logo existe m ∈ N com n = m+1. Seja
agora v um elemento de [n]\A (ele existe porque sabemos que A 6= [n], logo
[n]\A 6= ∅). Seja
g : [n] → [n]
y 7→

y, y 6∈ {v, n};
v, y = n;
n, y = v.
Ou seja, g troca v e n de lugar, mantendo todos os outros elementos de [n]
parados. Note que g e´ bijec¸a˜o de [n], logo sua restric¸a˜o g |A e´ injetiva. Ale´m
disso, a imagem de A por g esta´ contida em [m], ja´ que
∀a ∈ A : a 6= v ⇒ g(a) 6= g(v) = n⇒ g(a) ∈ [n]\{n} = [m] (por Exerc´ıcio 2).
De fato, Exerc´ıcio 2 entra na u´ltima igualdade acima porque
∀x ∈ N : “x ∈ [n]”\{n} ⇔ “x ≤ n”∧“x 6= n”⇔ “x < n” (tric.) ⇔ “x ≤ m” (pelo ex.).
Deduzimos que (exerc´ıcio) g |A pode ser tomada como uma func¸a˜o injetiva
de A em [m], logo #A ≤ m < n. 2
9
Proposic¸a˜o 18. Um conjunto finito X tem cardinalidade [n] se e somente
se existe uma bijec¸a˜o entre X e [n].
Prova: Se: Suponha que #X = n. Neste caso, existe uma func¸a˜o injetiva
fn : X → [n]. Considere a imagem A = f(X) de X, isto e´, o conjunto dos
a ∈ [n] para os quais existe x ∈ X com f(x) = a. Afirmamos que A = [n],
o que significa que A e´ sobrejetiva e portanto uma bijec¸a˜o, como queremos
demonstrar.
De fato, suponha (para chegar a uma contradic¸a˜o) que A 6= [n]. Como
A ⊂ [n], a Proposic¸a˜o 17 implica que #A < n, de modo que existe uma
func¸a˜o injetiva g : A→ [m] para algumm < n. Defina enta˜o r(x) ≡ g(f(x)),
para x ∈ X. r define uma func¸a˜o de X em [m], ja´ que f(x) ∈ A para todo
x ∈ X e g(a) ∈ [m] para todo a ∈ A. Ale´m disso, r e´ injetiva, ja´ que f e
g o sa˜o. A existeˆncia de r : X → [m] injetiva implica que #X ≤ m < n
(transitividade), o que contradiz o fato que #X = n ja´ que, pela tricotomia,
#X < n⇒ #X 6= n. A contradic¸a˜o implica que f : X → [n] e´ sobrejetiva,
logo bijetiva.
Somente se: Como ha´ uma bijec¸a˜o entre X e [n], temos #X = #[n] pela
Proposic¸a˜o 16. Logo basta mostrar que #[n] = n para todo n ∈ N.
Faremos isto por induc¸a˜o. Seja W o conjunto dos n ∈ N satisfazendo#[n] = n. Note que 1 ∈ W (exerc´ıcio). Para n ∈ W , [n] ⊂ [n + 1] mas
n + 1 6∈ [n] (ja´ que n + 1 > n), de modo que n = #[n] < #[n + 1] pela
Proposic¸a˜o 17. Ale´m disso, #[n+1] ≤ n+1, ja´ que a func¸a˜o u definida por
u(j) = j (j ∈ [n+1]) e´ injetiva. Segue que #[n+1] ≤ n+1 e #[n+1] > n,
donde #[n+ 1] = n+ 1 pelo Exerc´ıcio 2. Logo n ∈W ⇒ n+ 1 ∈W . 2
7 Cardinalidade de conjuntos na˜o necessariamente
finitos
Ha´ uma noc¸a˜o de cardinalidade de conjuntos infinitos que permite que se
associe algum valor a expresso˜es como #X < #Y . Na˜o definiremos o que e´
a cardinalidade de um conjunto, mas apenas comparac¸o˜es de cardinalidades.
Definic¸a˜o 19. Sejam X,Y conjuntos. Diremos que #X ≤ #Y se existe
uma func¸a˜o injetiva de X em Y . Se existe uma func¸a˜o sobrejetiva, diremos
que #X ≥ #Y . Por fim, diremos que #X = #Y se ha´ uma bijec¸a˜o entre
X e Y . Tambe´m escreveremos que #X < #Y se #X ≤ #Y e #X 6= #Y ,
etc.
E´ um fato na˜o trivial de teoria de conjuntos que:
10
Teorema 20 (Cantor). Para quaisquer X,Y como acima:
“#X = #Y ”⇔ “#X ≤ #Y ” ∧ “#Y ≤ #X”.
Na˜o provaremos este resultado no curso, mas o usaremos a seguir.
Definic¸a˜o 21. Um conjunto na˜o-vazio X e´ dito enumera´vel se e somente
se #X = #N.
Veja que todo conjunto enumera´vel e´ infinito.
Definic¸a˜o 22. Dado um conjunto X, o conjunto das partes de X (P(X))
e´ o conjunto cujos elementos sa˜o os subconjuntos A ⊂ X.
Teorema 23. Para todo conjunto X, #P(X) > #X. Em particular, P(N)
e´ infinito e na˜o-enumera´vel.
Prova: Precisamos mostrar que nenhuma func¸a˜o f : X → P(X) e´ sobreje-
tiva, isto e´:
∀f : X → P(X), ∃A ∈ P(X), ∀x ∈ X, f(x) 6= A.
Seja enta˜o f : X → P(X) dada. Defina:
A ≡ {x ∈ X : x 6∈ f(x)}.
Esmiuc¸ando: sabemos que f(x) e´ um subconjunto de X para todo x ∈ X;
botamos um dado x em A se e somente se x 6∈ f(x). Isto garante a seguinte
propriedade: para todo x ∈ X,
x ∈ A⇔ x 6∈ f(x),
de modo que, em particular, A 6= f(x) (ja´ que A = f(x) implicaria x ∈ A⇔
x ∈ f(x)). A existeˆncia de A e´ exatamente o que pretend´ıamos demonstrar.
2
8 Exerc´ıcios
Exerc´ıcio 1. Prove alguma das seguintes propriedades: a comutatividade
da multiplicac¸a˜o, associatividade da multiplicac¸a˜o e distributividade.
Exerc´ıcio 2. Mostre que para todos n,m ∈ N, n < m implica s(n) ≤ m.
Mais ainda, se m = s(k) para algum k, enta˜o n ≤ k.
11
Exerc´ıcio 3. Sejam a, b ∈ N tais que ∃c ∈ N\{1} com a = bc. Prove que
a > b.
Exerc´ıcio 4. Se a, b ∈ N, dizemos que a | b (a divide b) se existe f ∈ N com
af = b. Mostre que a | a para todo a ∈ N. Prove ainda que, se a, b, c ∈ N, a
divide b e b divide c, enta˜o a | c.
Exerc´ıcio 5. Sejam 2 ≡ s(1) e 3 ≡ s(2). Mostre que 2 < 3 mas 2 na˜o
divide 3.
Exerc´ıcio 6. Chame p ∈ N de primo se p = 1 e os divisores de p sa˜o apenas
1 e p. Demonstre que todo n ∈ N tem um divisor primo.
Exerc´ıcio 7. Mostre que 2 = s(1), 3 = s(2) e 5 = s(s(3)) sa˜o primos, mas
4 = s(3) na˜o e´.
Exerc´ıcio 8. Mostre que para todo n,m ∈ N com n 6= 1, n | m⇒ n 6 |m+1.
Exerc´ıcio 9. Prove que #[1] = 1 a partir da definic¸a˜o de cardinalidade.
Mostre tambe´m que dois conjuntos finitos X, Y teˆm a mesma cardinalidade
se e somente se ha´ uma bijec¸a˜o entre eles. Mostre ainda que #X ≤ #Y
equivale a haver uma injec¸a˜o de X a Y , enquanto #X ≥ #Y e´ equivalente
a existir uma sobrejec¸a˜o.
Exerc´ıcio 10. Prove que se A e B sa˜o conjuntos finitos, #(A ∪ B) ≤
#A+#B.
Exerc´ıcio 11. Prove que N na˜o e´ finito.
Exerc´ıcio 12. (Trabalhoso) Prove que todo conjunto infinito contem um
subconjunto enumera´vel.
12