A maior rede de estudos do Brasil

Grátis
447 pág.
Curso de Analise Vol.1 - Elon L. Lima

Pré-visualização | Página 11 de 50

temos
In = {p ∈ N; 1 ≤ p ≤ n}.
Um conjunto X chama-se finito quando e´ vazio ou quando
existe, para algum n ∈ N, uma bijec¸a˜o
ϕ : In→ X.
No primeiro caso, diremos que X tem zero elementos. No segundo
caso, diremos que n ∈ N e´ o nu´mero de elementos de X, ou seja,
que X possui n elementos.
Os seguintes fatos decorrem imediatamente das definic¸o˜es:
a) cada conjunto In e´ finito e possui n elementos;
b) se f : X→ Y e´ uma bijec¸a˜o, um desses conjuntos e´ finito se,
e somente se, o outro e´.
[SEC. 3: CONJUNTOS FINITOS E INFINITOS 43
Intuitivamente, uma bijec¸a˜o ϕ : In → X significa uma
contagem dos elementos de X. Pondo ϕ(1) = x1 ,
ϕ(2) = x2, . . . , ϕ(n) = xn , temos X = {x1, x2, . . . , xn}. Esta
e´ a representac¸a˜o ordina´ria de um conjunto finito.
Para que o nu´mero de elementos de um conjunto na˜o seja uma
noc¸a˜o amb´ıgua, devemos provar que se existem duas bijec¸o˜es
ϕ : In→ X e ψ : Im→ X, enta˜o m = n. Considerando a func¸a˜o
composta f = ψ−1 ◦ ϕ : In → Im , basta enta˜o provar que se
existe uma bijec¸a˜o f : In→ Im , enta˜o tem-se m = n. Para fixar
ide´ias, suponhamos m ≤ n. Da´ı, Im ⊂ In . A unicidade do
nu´mero de elementos de um conjunto finito sera´, portanto, uma
consequ¨eˆncia da proposic¸a˜o mais geral seguinte:
Teorema 3. Seja A ⊂ In . Se existir uma bijec¸a˜o f : In → A,
enta˜o A = In .
Demonstrac¸a˜o. Usaremos induc¸a˜o em n. O resultado e´ o´bvio
para n = 1. Suponhamos que ele seja va´lido para um certo n e
consideremos uma bijec¸a˜o f : In+1 → A. Ponhamos
a = f(n + 1). A restric¸a˜o de f a In fornece uma bijec¸a˜o
f ′ : In → A − {a}. Se tivermos A − {a} ⊂ In , enta˜o, pela
hipo´tese de induc¸a˜o, concluiremos que A − {a} = In , donde
a = n + 1 e A = In+1 . Se, pore´m, na˜o for A − {a} ⊂ In ,
enta˜o deve-se ter n + 1 ∈ A − {a}. Neste caso, existe p ∈ In+1
tal que f(p) = n + 1. Enta˜o definiremos uma nova bijec¸a˜o
g : In+1 → A pondo g(x) = f(x) se x 6= p e x 6= n + 1, en-
quanto g(p) = a, g(n + 1) = n + 1. Agora, a restric¸a˜o de
g a In nos dara´ uma bijec¸a˜o g
′ : In → A − {n + 1}. Eviden-
temente, A − {n + 1} ⊂ In . Logo, pela hipo´tese de induc¸a˜o,
A− {n+1} = In , donde A = In+1 . Isto conclui a demonstrac¸a˜o.
Corola´rio 1. Se existir uma bijec¸a˜o f : Im → In enta˜o
m = n. Consequ¨entemente, se existem duas bijec¸o˜es ψ : In→ X
e ϕ : Im→ X, deve-se ter m = n.
De fato, podemos supor, para fixar as ide´ias, que m ≤ n.
Enta˜o Im ⊂ In . Tomando-se A = Im no Teorema 3, obtemos
Im = In e, portanto, m = n.
44 [CAP. II: CONJUNTOS FINITOS, ENUMERA´VEIS E NA˜O-ENUMERA´VEIS
Corola´rio 2. Na˜o pode existir uma bijec¸a˜o f : X → Y de um
conjunto finito X sobre uma parte pro´pria Y ⊂ X.
De fato, sendo X finito, existe uma bijec¸a˜o ϕ : In→ X. Seja
A = ϕ−1(Y). Enta˜o A e´ uma parte pro´pria de In e a restric¸a˜o
de ϕ a A fornece uma bijec¸a˜o ϕ ′ : A→ Y.
A composta g = (ϕ ′)−1 ◦ f ◦ ϕ : In → A seria enta˜o uma
bijec¸a˜o de In sobre sua parte pro´pria A, o que contradiria o
Teorema 3. Logo na˜o existe a bijec¸a˜o f.
Teorema 4. Se X e´ um conjunto finito enta˜o todo subconjunto
Y ⊂ X e´ finito. O nu´mero de elementos de Y na˜o excede o de X
e so´ e´ igual quando Y = X.
Demonstrac¸a˜o. Basta provar o teorema no caso em que
X = In . Isso e´ claro para n = 1 pois as u´nicas partes de I1
sa˜o ∅ e I1 . Suponhamos o teorema demonstrado para In e con-
sideremos um subconjunto Y ⊂ In+1 . Se for Y ⊂ In enta˜o, pela
hipo´tese de induc¸a˜o, Y sera´ um conjunto finito cujo nu´mero de
elementos e´ ≤ n e, portanto, ≤ n + 1. Se pore´m, n + 1 ∈ Y
enta˜o Y − {n + 1} ⊂ In e consequ¨entemente (salvo no caso tri-
vial Y = {n + 1}) existe uma bijec¸a˜o ψ : Ip → Y − {n + 1}, com
p ≤ n. Definiremos enta˜o uma bijec¸a˜o ϕ : Ip+1 → Y, pondo
ϕ(x) = ψ(x) para x ∈ Ip e ϕ(p + 1) = n + 1. Segue-se que Y e´
finito e seu nu´mero de elementos na˜o excede p+1. Como p ≤ n,
temos p+1 ≤ n+1. Resta apenas mostrar que se Y ⊂ In tem n
elementos enta˜o Y = In . Isto pore´m e´ claro pois, pelo Corola´rio
2, do Teorema 3, na˜o pode haver uma bijec¸a˜o de In sobre uma
sua parte pro´pria Y.
[SEC. 3: CONJUNTOS FINITOS E INFINITOS 45
Corola´rio 1. Seja f : X → Y uma func¸a˜o injetiva. Se Y for
finito enta˜o X tambe´m sera´. Ale´m disso, o nu´mero de elementos
de X na˜o excede o de Y.
De fato, f define uma bijec¸a˜o de X sobre sua imagem f(X),
a qual e´ finita, por ser uma parte do conjunto finito Y. Ale´m
disso, o nu´mero de elementos de f(X), que e´ igual ao de X, na˜o
excede o de Y.
Corola´rio 2. Seja g : X → Y uma func¸a˜o sobrejetiva. Se X for
finito enta˜o Y tambe´m sera´ e o seu nu´mero de elementos na˜o
excede o de X.
De fato, como vimos no Cap´ıtulo I (§4) g possui uma inversa
a` direita, isto e´, existe uma func¸a˜o f : Y → X tal que g◦f = idY .
Enta˜o g e´ inversa a` esquerda de f e, portanto, f e´ uma func¸a˜o
injetiva de Y no conjunto finito X. Segue-se do Corola´rio 1 que
Y e´ finito e seu nu´mero de elementos na˜o excede o de X.
Um conjunto X chama-se infinito quando na˜o e´ finito. Mais
explicitamente, X e´ infinito quando na˜o e´ vazio e, ale´m disso,
seja qual for n ∈ N, na˜o existe uma bijec¸a˜o ϕ : In→ X.
Por exemplo, o conjunto N dos nu´meros naturais e´ infinito.
De fato, dada qualquer func¸a˜o ϕ : In → N, com n > 1, seja
p = ϕ(1) + · · · + ϕ(n). Enta˜o p > ϕ(x) para todo x ∈ In ,
donde p /∈ ϕ(In). Logo, nenhuma func¸a˜o ϕ : In→ N e´ sobreje-
tiva.
Outra maneira de verificar que N e´ infinito e´ considerar o
conjunto P = {2, 4, 6, . . . } dos nu´meros pares e definir a bijec¸a˜o
f : N→ P , onde f(n) = 2n. Como P e´ uma parte pro´pria de N,
segue-se do Corola´rio 2 do Teorema 3 que N na˜o e´ finito.
Os fatos que acabamos de estabelecer para conjuntos finitos
fornecem, por exclusa˜o, resultados sobre conjuntos infinitos. Por
exemplo, se f : X→ Y e´ injetiva e X e´ infinito, enta˜o Y tambe´m e´.
Dada f : X→ Y sobrejetiva, se Y e´ infinito, enta˜o X e´ infinito. Ou
enta˜o, como acabamos de usar, se X admite uma bijec¸a˜o sobre
uma de suas partes pro´prias, enta˜o X e´ infinito. (No para´grafo
seguinte, mostraremos que a rec´ıproca tambe´m vale.)
Outros exemplos de conjuntos infinitos sa˜o Z e Q, pois am-
46 [CAP. II: CONJUNTOS FINITOS, ENUMERA´VEIS E NA˜O-ENUMERA´VEIS
bos conteˆm N. Segundo uma proposic¸a˜o devida a Euclides, o
conjunto dos nu´meros primos e´ infinito. Caracterizaremos agora
os subconjuntos finitos (e portanto os infinitos) de N.
Um conjunto X ⊂ N chama-se limitado quando existe um
p ∈ N tal que p ≥ n seja qual for n ∈ X.
Teorema 5. Seja X ⊂ N na˜o-vazio. As seguintes afirmac¸o˜es
sa˜o equivalentes:
(a) X e´ finito;
(b) X e´ limitado;
(c) X possui um maior elemento.
Demonstrac¸a˜o. Provaremos que (a)⇒(b), (b)⇒(c) e (c)⇒(a).
(a) ⇒ (b) – Seja X = {x1, . . . , xn}. Pondo p = x1+ · · ·+ xn ,
temos p > x, para todo x ∈ X, logo X e´ limitado.
(b)⇒ (c) – Supondo X ⊂ N limitado, segue-se que o conjunto
A = {p ∈ N;p ≥ n para todo n ∈ X} e´ na˜o-vazio. Pelo Princ´ıpio
da Boa Ordenac¸a˜o, existe p0 ∈ A, que e´ o menor elemento de
A. Afirmamos que deve ser p0 ∈ X. Com efeito, se fosse p0 /∈ X
enta˜o ter´ıamos p0 > n para todo n ∈ X. Como X 6= ∅, isto
obrigaria p0 > 1, donde p0 = p1 + 1. Se existisse algum n ∈ X
com p1 < n isto traria p0 = p1+1 ≤ n e (como estamos supondo
p0 /∈ X) p0 < n, um absurdo. Logo e´ p1 ≥ n para todo n ∈ X.
Mas isto significa p1 ∈ A, o que e´ absurdo em vista de p1 < p0
e p0 = menor elemento de A. Portanto deve ser p0 ∈ X. Como
p0 ≥ n para todo n ∈ X, conclu´ımos que p0 e´ o maior elemento
de X.
(c) ⇒ (a) – Se existe um elemento p ∈ X que e´ o maior de
todos, enta˜o X esta´ contido em Ip e por conseguinte X e´ finito,
pelo Teorema 4.
Um conjunto X ⊂ N chama-se ilimitado quando na˜o e´ li-
mitado. Isto significa que, dado qualquer p ∈ N, existe algum
n ∈ X tal que n > p. Os conjuntos ilimitados X ⊂ N sa˜o, como
acabamos de ver, precisamente os subconjuntos