Curso de Analise Vol.1 - Elon L. Lima

ja´ sugere que o produto deve gozar da
propriedade distributiva
m · (n+ p) = m · n+m · p.
Demonstremos este fato. Seja X o conjunto dos nu´meros
p ∈ N tais que (m+n) · p = m · p+n · p sejam quais forem m,
n ∈ N. Acabamos de observar que 1 ∈ X. Ale´m disso, se p ∈ X,
concluiremos que
(m+ n) · (p+ 1) = (m+ n) · p+m+ n
= m · p+ n · p+m+ n = m · p+m+ n · p+ n
= m · (p+ 1) + n · (p+ 1).
(Nas igualdades acima usamos, sucessivamente, a definic¸a˜o de
produto, a hipo´tese de que p ∈ X, a associatividade e a comuta-
tividade da adic¸a˜o e, novamente, a definic¸a˜o de produto).
Segue-se que p+1 ∈ X. Assim, X = N, ou seja, (m+n) ·p =
m · p+ n · p, quaisquer que sejam m, n, p ∈ N.
As principais propriedades da multiplicac¸a˜o sa˜o:
Associatividade: m · (n · p) = (m · n) · p;
Comutatividade: m · n = n ·m;
Lei do corte: m · p = n · p⇒ m = n;
Distributividade: m(n+ p) = m · n+m · p;
Monotonicidade: m < n⇒ m · p < n · p.
Omitiremos as demonstrac¸o˜es.
[SEC. 2: BOA ORDENAC¸A˜O E O SEGUNDO PRINC´IPIO DE INDUC¸A˜O 39
2 Boa ordenac¸a˜o e o Segundo Princ´ı-
pio de Induc¸a˜o
Seja X um conjunto de nu´meros naturais. Diz-se que um
nu´mero p ∈ X e´ o menor elemento de X (ou elemento mı´nimo
de X) quando se tem p ≤ n para todo n ∈ X. Por exemplo, 1 e´
o menor elemento do conjunto N de todos os nu´meros naturais.
Com maior raza˜o, qualquer que seja X ⊂ N com 1 ∈ X, 1 e´ o
menor elemento de X.
Dado X ⊂ N, se p ∈ X e q ∈ X sa˜o ambos os menores
elementos de X enta˜o p ≤ q e q ≤ p, donde p = q. Assim, o
menor elemento de um conjunto e´ u´nico.
Analogamente, se X ⊂ N, um nu´mero p ∈ X chama-se o
maior elemento de X (ou elemento ma´ximo de X) quando se tem
p ≥ n para todo n ∈ X. Nem todo conjunto de nu´meros naturais
possui um elemento ma´ximo. Por exemplo, o pro´prio N na˜o tem
um maior elemento ja´ que, para todo n ∈ N tem-se n+ 1 > n.
Se existir o elemento ma´ximo de um conjunto X ⊂ N, ele e´
u´nico. Com efeito, se p ∈ X e q ∈ X sa˜o ambos ma´ximos enta˜o
p ≥ q e q ≥ p, donde p = q.
Um resultado de grande importaˆncia, ate´ mesmo como me´todo
de demonstrac¸a˜o, e´ o fato de que todo conjunto na˜o-vazio de
nu´meros naturais possui um menor elemento. Este fato e´ conhe-
cido como o Princ´ıpio da Boa Ordenac¸a˜o.
Teorema 1. (Princ´ıpio da Boa Ordenac¸a˜o). Todo subconjunto
na˜o-vazio A ⊂ N possui um elemento mı´nimo.
Demonstrac¸a˜o. Usando a notac¸a˜o In = {p ∈ N, 1 ≤ p ≤ n},
consideremos o conjunto X ⊂ N, formado pelos nu´meros n ∈ N
tais que In ⊂ N − A. (Assim, dizer que n ∈ X significa afirmar
que n /∈ A e que todos os nu´meros naturais menores do que n
tambe´m na˜o pertencem a A.) Se tivermos 1 ∈ A, o teorema
estara´ demonstrado pois 1 sera´ o menor elemento de A. Se,
pore´m, for 1 /∈ A enta˜o 1 ∈ X. Por outro lado, temos X 6= N.
(Pois X ⊂ N − A e A 6= ∅.) Assim, X cumpre a primeira parte
40 [CAP. II: CONJUNTOS FINITOS, ENUMERA´VEIS E NA˜O-ENUMERA´VEIS
da hipo´tese de P3 (conte´m 1) mas na˜o satisfaz a` conclusa˜o de
P3 (na˜o e´ igual a N). Logo na˜o pode cumprir a segunda parte
da hipo´tese. Isto quer dizer: deve existir algum n ∈ X tal que
n + 1 /∈ X. Seja a = n + 1. Enta˜o todos os inteiros desde 1 ate´
n pertencem ao complementar de A mas a = n + 1 pertence a
A. Desta maneira, a e´ o menor elemento do conjunto A, o que
demonstra o teorema.
Do Princ´ıpio da Boa Ordenac¸a˜o decorre uma proposic¸a˜o co-
nhecida como o Segundo Princ´ıpio da Induc¸a˜o, que demonstra-
remos agora.
Teorema 2. (Segundo Princ´ıpio da Induc¸a˜o.) Seja X ⊂ N um
conjunto com a seguinte propriedade: dado n ∈ N, se X conte´m
todos os nu´meros naturais m tais que m < n, enta˜o n ∈ X.
Nestas condic¸o˜es, X = N.
Demonstrac¸a˜o. Seja Y = N − X. Afirmamos que Y = ∅. Com
efeito, se Y na˜o fosse vazio, existiria um elemento mı´nimo p ∈ Y.
Enta˜o, para todo nu´mero natural m < p, seria m ∈ X. Pela
hipo´tese feita sobre X, ter´ıamos p ∈ X, uma contradic¸a˜o.
O Segundo Princ´ıpio da Induc¸a˜o constitui um me´todo u´til
para demonstrac¸a˜o de proposic¸o˜es referentes a nu´meros naturais.
Ele tambe´m pode ser enunciado assim: Seja P uma propriedade
relativa a nu´meros naturais. Se, dado n ∈ N, do fato de todo
nu´mero naturalm < n gozar da propriedade P puder ser inferido
que n goza da propriedade P , enta˜o todo nu´mero natural goza
de P .
Exemplo 1. Um nu´mero natural p chama-se primo quando
p 6= 1 e na˜o se pode escrever p = m · n com m < p e n < p.
O chamado Teorema Fundamental da Aritme´tica diz que todo
nu´mero natural se decompo˜e, de modo u´nico, como produto de
fatores primos. A demonstrac¸a˜o utiliza o Segundo Princ´ıpio da
Induc¸a˜o. Com efeito, dado n ∈ N, suponhamos que todo nu´mero
natural menor do que n possa ser decomposto como produto
de fatores primos. Enta˜o, ou n e´ primo (e neste caso n e´, de
[SEC. 2: BOA ORDENAC¸A˜O E O SEGUNDO PRINC´IPIO DE INDUC¸A˜O 41
modo trivial, um produto de fatores primos) ou enta˜o n = m ·
k, com m < n e k < n. Pela hipo´tese de induc¸a˜o, m e k
sa˜o produtos de fatores primos. Segue-se que n tambe´m o e´.
Pelo Segundo Princ´ıpio da Induc¸a˜o, conclu´ımos que todo nu´mero
natural e´ produto de nu´meros primos. Omitimos a demonstrac¸a˜o
da unicidade.
Encerraremos este para´grafo falando do me´todo geral de de-
finic¸a˜o por induc¸a˜o.
Seja X um conjunto qualquer. Trata-se de definir uma func¸a˜o
f : N → X. Suponhamos que nos seja dado o valor f(1) e seja
dada tambe´m uma regra que nos permita obter f(n) desde que
conhec¸amos os valores f(m), para todo m < n. Enta˜o existe
uma, e uma so´, func¸a˜o f : N → X nessas condic¸o˜es. Este e´ o
me´todo geral de definic¸a˜o por induc¸a˜o (ou por recorreˆncia).
A afirmac¸a˜o acima constitui um teorema, cuja demonstrac¸a˜o
reduz-se a` iterac¸a˜o de uma func¸a˜o auxiliar. (Veja [Gleason], p.
145.) Daremos aqui apenas alguns exemplos. Outras definic¸o˜es
por induc¸a˜o sera˜o vistas no §3, logo a seguir.
Exemplo 2. Fixado a ∈ N, definamos uma func¸a˜o f : N → N,
indutivamente, pondo f(1) = a e f(n+ 1) = a · f(n). A func¸a˜o f
cumpre enta˜o f(2) = a ·a, f(3) = a ·a ·a, etc. Logo f(n) = an.
Acabamos de definir, por induc¸a˜o, a n-e´sima poteˆncia do nu´mero
natural a. Note-se que, neste caso, temos apenas a iterac¸a˜o da
multiplicac¸a˜o por a, isto e´, a forma mais simples de definic¸a˜o por
induc¸a˜o. Os exemplos seguintes requerem a forma geral, isto e´,
na˜o se reduzem imediatamente a` iterac¸a˜o de uma func¸a˜o dada.
Exemplo 3. Seja ϕ : N → N a func¸a˜o definida indutivamente
por ϕ(1) = 1 e ϕ(n + 1) = (n + 1) · ϕ(n). Enta˜o ϕ(1) = 1,
ϕ(2) = 2·1, ϕ(3) = 3·2·1, etc. Assim, ϕ(n) = n·(n−1) . . . 2·1,
ou seja, ϕ(n) = n! e´ o fatorial de n.
Exemplo 4. Definamos f : N → Q indutivamente pondo
f(1) = 1, f(2) = 1/2 e, em geral, f(n + 2) =
f(n) + f(n+ 1)
2
:
Enta˜o f(3) = 3/4, f(4) = 5/8, etc. Cada valor f(n), para
42 [CAP. II: CONJUNTOS FINITOS, ENUMERA´VEIS E NA˜O-ENUMERA´VEIS
n > 2, e´ a me´dia aritme´tica dos dois valores anteriores de f.
Exemplo 5. A soma a1 + · · · + an de uma n-upla de
nu´meros naturais a1, . . . , an e´ definida indutivamente
assim: a1 e a1 + a2 ja´ se conhecem. Supondo que ja´
se saiba somar n nu´meros quaisquer, po˜e-se, por definic¸a˜o,
a1+· · ·+an+1 = (a1+· · ·+an)+an+1 . A primeira vista, na˜o se veˆ
aqui a definic¸a˜o de uma func¸a˜o f : N → X, por
induc¸a˜o. Na realidade, pore´m, a soma de n nu´meros naturais
(n fixo) e´ uma func¸a˜o σn : N
n→ N. O que se acabou de definir
indutivamente foi a func¸a˜o f : n→ σn . (Qual e´ o contradomı´nio
X de f ?)
Exemplo 6. Tambe´m o produto a1 · a2 · · · · · an de uma
n-upla de nu´meros naturais e´ definido indutivamente: a1 ·a2 sa˜o
conhecidos. Po˜e-se a1 · a2 · · · · · an+1 = (a1 · a2 · · · · · an) · an+1 .
3 Conjuntos finitos e infinitos
Neste para´grafo, indicaremos pelo s´ımbolo In o conjunto
{1, . . . , n} dos nu´meros naturais desde 1 ate´ n. Mais precisa-
mente, dado n ∈ N,