capitulo 1

Prévia do material em texto

1
Inteiros e Indu»c~ao Finita
Neste cap¶³tulo estudaremos uma estrutura alg¶ebrica que j¶a nos ¶e familiar: a estru-
tura alg¶ebrica do conjunto Z dos n¶umeros inteiros.
Por estrutura alg¶ebrica do conjunto Z entende-se o conjunto de propriedades
dos n¶umeros inteiros que dizem respeito µas suas duas opera»c~oes habituais, a adi»c~ao
e a multiplica»c~ao, bem como µa ordem de¯nida no conjunto Z pela rela»c~ao <, a
chamada rela»c~ao de ordem \menor".
Na parte ¯nal do cap¶³tulo, estabeleceremos os assim chamados princ¶³pios de
indu»c~ao ¯nita e mostraremos algumas de suas aplica»c~oes.
1.1 Axiom¶atica da estrutura de Z
Introduziremos as opera»c~oes de adi»c~ao e multiplica»c~ao em Z de forma axiom¶atica,
isto ¶e, a partir de um conjunto de axiomas ou postulados | propriedades b¶asicas,
admitidas a priori | que caracterizam essas opera»c~oes em Z. A partir desse
conjunto de propriedades axiom¶aticas, deduziremos algumas outras propriedades,
tamb¶em elementares e conhecidas por todos n¶os, por¶em \demonstr¶aveis", isto ¶e,
dedut¶³veis a partir dos axiomas b¶asicos.
Admitiremos axiomaticamente que existe um conjunto Z, cujos elementos
s~ao chamados n¶umeros inteiros, havendo em Z dois elementos destacados e dis-
tintos que s~ao, a saber, 0 (zero) e 1 (um).
Admitiremos tamb¶em que em Z, s~ao de¯nidas duas opera»c~oes, a adi»c~ao
(denotada por +) e a multiplica»c~ao (denotada por ¢). Dizendo que + e ¢ s~ao duas
opera»c~oes em Z, queremos dizer que + e ¢ s~ao duas fun»c~oes
+ : Z£ Z! Z e ¢ : Z£ Z! Z;
sendo que a primeira (+) associa cada par ordenado de inteiros (x; y) a um ¶unico
inteiro x+y, chamado soma de x e y, e a segunda (¢) associa cada par de inteiros
(x; y) a um ¶unico inteiro x ¢ y (denotado tamb¶em por xy, quando isto n~ao gerar
ambigÄuidade), chamado produto de x e y.
1
Inteiros e Induc»~ao Finita 2
Assumiremos que as opera»c~oes adi»c~ao e multiplica»c~ao em Z tem as seguintes
propriedades:
Para cada x, cada y, e cada z, todos em Z, tem-se:
(A1) x+ (y + z) = (x+ y) + x (isto ¶e, a adi»c~ao em Z ¶e associativa);
(A2) x+ y = y + x (a adi»c~ao em Z ¶e comutativa);
(A3) x+ 0 = 0 + x = x (isto ¶e, 0 ¶e elemento neutro da adi»c~ao em Z);
(A4) Existe um elemento ¡x em Z, chamado oposto de x ou inverso aditivo de
x, ou ainda sim¶etrico de x relativamente µa opera»c~ao adi»c~ao, satisfazendo
x+ (¡x) = (¡x) + x = 0.
(M1) x(yz) = (xy)z (a multiplica»c~ao em Z ¶e tamb¶em associativa);
(M2) xy = yx (a multiplica»c~ao em Z ¶e tamb¶em comutativa);
(M3) x ¢ 1 = 1 ¢ x = x (1 ¶e elemento neutro da multiplica»c~ao em Z);
(D) x(y + z) = xy + xz (a multiplica»c~ao ¶e distributiva em rela»c~ao µa adi»c~ao).
De¯ni»c~ao 1.1 (Subtra»c~ao em Z) Chama-se diferen»ca de dois inteiros x e y µa
soma x+(¡y). A subtra»c~ao em Z ¶e a opera»c~ao ¡:Z£Z! Z, que associa cada
par ordenado (x; y) µa diferen»ca x¡ y.
Teorema 1.1 Para cada x, cada y, e cada z, todos em Z, valem as propriedades:
1. x+ y = x) y = 0 (ou seja, 0 ¶e o ¶unico elemento neutro da adi»c~ao em Z)
2. x+ y = 0) y = ¡x (ou seja, o oposto de um inteiro x ¶e ¶unico);
3. x+ y = x+ z ) y = z ( lei do cancelamento da adi»c~ao);
4. ¡(¡x) = x;
5. ¡(x+ y) = ¡x¡ y (aten»c~ao!: ¡x¡ y signi¯ca (¡x)¡ y, ou seja, (¡x) +
(¡y));
6. x ¢ 0 = 0;
7. (¡x)y = ¡xy;
8. (¡x)(¡y) = xy;
9. (x¡ y)z = xz ¡ yz.
Inteiros e Induc»~ao Finita 3
Demonstra»c~ao.
1. x+y = x) (¡x)+(x+y) = (¡x)+x. Pelos axiomas (A1), (A3) e (A4),
temos conseqÄuentemente que
((¡x) + x) + y = 0) 0 + y = 0) y = 0
2. Se x+ y = 0 ent~ao (¡x) + (x+ y) = (¡x) + 0. Pelos axiomas (A1), (A3)
e (A4), temos conseqÄuentemente que
((¡x) + x) + y = ¡x) 0 + y = ¡x) y = ¡x
3. Se x + y = x + z, ent~ao (¡x) + (x + y) = (¡x) + (x + z). Pelo axioma
(A1), ((¡x) + x) + y = ((¡x) + x) + z ) 0 + y = 0 + z, e ent~ao, pelo
axioma (A3), y = z.
4. Pelo axioma (A4) ¡(¡x) + (¡x) = 0.
Logo, [¡(¡x)+(¡x)]+x = 0+x. Aplicando ent~ao os axiomas (A1) e (A3),
deduzimos: ¡(¡x) + [(¡x) + x] = x) ¡(¡x) + 0 = x) ¡(¡x) = x.
5. (Exerc¶³cio para o leitor. Sugest~ao: Calcule inicialmente a soma (x + y) +
[(¡x) + (¡y)], aplicando os axiomas da adi»c~ao.)
6. Seja x ¢ 0 = a. Ent~ao, pelos axiomas (A3) e (D), a = x ¢ 0 = x ¢ (0 + 0) =
x ¢ 0 + x ¢ 0 = a + a. Logo, a + a = a + 0, e ent~ao, pelo item 3 provado
acima, a = 0, ou seja x ¢ 0 = 0.
7. Por um lado, temos que [(¡x) + x]y = (¡x)y + xy. Por outro, temos que
[(¡x)+x]y = 0 ¢y = 0. Logo, aplicando o resultado do item 2 demonstrado
acima, (¡x)y + xy = 0) ¡(xy) = (¡x)y.
8. (Exerc¶³cio para o leitor. Sugest~ao: Aplique o resultado do item anterior)
9. (Exerc¶³cio para o leitor.)
Observa»c~ao 1.1 Os axiomas listados ainda n~ao s~ao su¯cientes para caracterizar
o conjunto Z de maneira ¶unica. Em outras palavras, existem outras estruturas
alg¶ebricas familiares que tamb¶em satisfazem µas propriedades acima.
O leitor certamente j¶a est¶a familiarizado com os conjuntos num¶ericos Q, dos
n¶umeros racionais, e R, dos n¶umeros reais. Sabe portanto, que em Q, bem como
em R, tamb¶em s~ao de¯nidas uma adi»c~ao e uma multiplica»c~ao, as quais, embora
tendo propriedades adicionais, satisfazem a todos os axiomas listados acima.
Isto indica claramente que esses axiomas s~ao satisfeitos por outras estruturas
alg¶ebricas familiares, tais como as de Q e R.
Existem tamb¶em estruturas alg¶ebricas \abstratas" satisfazendo os axiomas
(A1), (A2), (A3), (A4), (M1), (M2), (M3) e (D).
Inteiros e Induc»~ao Finita 4
Consideremos, por exemplo, o conjunto Z = f0; 1g, no qual de¯niremos
uma adi»c~ao e uma multiplica»c~ao conforme as tabelas abaixo (aten»c~ao! Aqui, os
n¶umeros 0 e 1 n~ao s~ao aqueles do conjunto Z dos n¶umeros inteiros.)
+ 0 1
0 0 1
1 1 0
¢ 0 1
0 0 0
1 0 1
Assim, as opera»c~oes + e ¢, de¯nidas em Z conforme suas t¶abuas dadas
acima, satisfazem os axiomas (A1), (A2), (A3), (A4), (M1), (M2), (M3) e (D).
Veri¯que. Note que este \Z" tem apenas dois elementos.
1.1.1 Problemas complementares
1. °^. . Usando somente os axiomas (A1) a (D) das opera»c~oes em Z, deduza
que (¡1)(¡1) = 1. (N~ao utilize o resultado do item 8 do teorema 1.1) Use
o menor n¶umero de axiomas poss¶³vel para essa dedu»c~ao. Quais axiomas s~ao
utilizados nela?
2. °^. . Existe um elemento neutro para a opera»c~ao de subtra»c~ao em Z? Ex-
plique.
1.2 Ordem em Z
J¶a temos um conhecimento intuitivo de que os inteiros s~ao ordenados, no sentido
de que ¡1 ¶e menor que 0, que por sua vez ¶e menor que 1, que ¶e menor que 2,
e assim por diante. Nesta se»c~ao trataremos de caracterizar a rela»c~ao de ordem
\menor" (<) no conjunto Z de maneira formal.
De¯ni»c~ao 1.2 (Rela»c~ao num conjunto) Sendo A um conjunto n~ao vazio, dize-
mos que R ¶e uma rela»c~ao em A, se R ¶e um subconjunto do produto cartesiano
A£A. (O produto cartesiano A£B de dois conjuntos A e B ¶e o conjunto cujos
elementos s~ao todos os pares ordenados (a; b), com a 2 A e b 2 B.)
Por exemplo, R = f(1; 2); (1; 4); (2; 3)g ¶e uma rela»c~ao em A = f1; 2; 3; 4g.
Tamb¶em s~ao rela»c~oes em A os conjuntos S = ¿ e T = A£A.
Se S ¶e uma rela»c~ao em A, e se o par (a; b) faz parte dessa rela»c~ao, escrevemos
(a; b) 2 S ou aSb, e dizemos que a est¶a relacionado com b pela rela»c~ao S. Se
(x; y)62 S, tamb¶em escrevemos x6Sy.
No exemplo acima, temos 1S2, 1S4 e 2S3 mas, por exemplo, 16S3.
Inteiros e Induc»~ao Finita 5
1.2.1 Axiomas para a rela»c~ao \menor" (<) em Z
Admitiremos que em Z est¶a de¯nida uma rela»c~ao <, chamada rela»c~ao menor. Se
(x; y) 2<, escrevemos x < y (ou y > x) e dizemos que x ¶e menor que y (ou,
respectivamente, que y ¶e maior que x),
Admitiremos que a rela»c~ao < em Z satisfaz os seguintes axiomas: Para cada
x, cada y, e cada z, todos em Z,
(O1) Lei da tricotomia. Vale uma e somente uma das a¯rma»c~oes:
x < y; x = y; y < x
(O2) Se x < y e y < z ent~ao x < z (a rela»c~ao < em Z ¶e transitiva);
(O3) Se x < y ent~ao x + z < y+ z (a rela»c~ao < em Z ¶e compat¶³vel com a
adi»c~ao);
(O4) Se x > 0 e y > 0 ent~ao xy > 0 (a rela»c~ao < em Z ¶e compat¶³vel com a
multiplica»c~ao).
Observa»c~ao 1.2 Escrevemos a · b quando a < b ou a = b. Analogamente,
escrevemos a ¸ b se a > b ou a = b. Assim, por exemplo, 2 · 4, bem como
3 · 3.
Teorema 1.2 (Propriedades adicionais da rela»c~ao <) Para cada x, cada y,
cada z e cada w, todos em Z, valem as seguintes propriedades:
1. x < y se e somente se x¡ y < 0;
2. x < 0 se e somente se ¡x > 0;
3. (Lei do Cancelamento para a adi»c~ao) Se x+ z < y + z ent~ao x < y;
4. Se x < y e z < w ent~ao x+ z < y + w;
5. (Regras de Sinais)
(a) Se x < 0 e y > 0 ent~ao xy < 0;
(b) Se x < 0 e y < 0 ent~ao xy > 0;
6. Se x6= 0 ent~ao x2 > 0;
7. 1 > 0;
8. (a) Se x < y e z > 0 ent~ao xz < yz;
(b) Se x < y e z < 0 ent~ao xz > yz;
9. Se x > y > 0 e z > w > 0 ent~ao xz > yw > 0;
Inteiros e Induc»~ao Finita 6
10. (Leis do Cancelamento para a multiplica»c~ao)
(a) Se xz < yz e z > 0 ent~ao x < y;
(b) Se xz < yz e z < 0 ent~ao x > y.
Demonstra»c~ao.
1. Se x < y ent~ao, pelo axioma (O3), x + (¡y) < y + (¡y), e portanto
x¡ y < 0.
2. (Exerc¶³cio para o leitor).
3. (Exerc¶³cio para o leitor).
4. Se x < y ent~ao, pelo item 1, x + z < y + z. Analogamente, z < w )
y + z < y +w. Logo, x+ z < y + z e y + z < y +w e ent~ao, pelo axioma
(O2), x+ z < y + w.
5. Provaremos a primeira das a¯rma»c~oes e deixaremos a segunda como exer-
c¶³cio. Se x < 0 e y > 0 ent~ao ¡x > 0 e y > 0. Pelo axioma (O4), temos
¡(xy) = (¡x)y > 0, e ent~ao, pelo item 2, xy < 0,
6. (Exerc¶³cio para o leitor).
7. Temos que 16= 0 e que 12 = 1 ¢ 1 = 1. Da¶³, pelo item 6, 1 > 0.
8. Provaremos a primeira das a¯rma»c~oes e deixaremos a segunda como exer-
c¶³cio. Se x < y e z > 0, ent~ao x ¡ y < 0, pelo item 1. Aplicando a
propriedade (a) do item 5, x ¡ y < 0 e z > 0 ) (x ¡ y)z < 0, de onde
xz ¡ yz < 0, e ent~ao xz < yz.
9. (Exerc¶³cio para o leitor).
10. Provaremos o item (a) e deixaremos o item (b) como exerc¶³cio. Ambos os
itens s~ao conseqÄue^ncia direta do item 8. Se xz < yz e z > 0 ent~ao neces-
sariamente x < y pois, caso contr¶ario, teremos x > y ou x = y. Pelo item
8, sub-item (a), como z > 0, temos que xz > yz ou xz = yz, contrariando
nosso dado inicial de que xz < yz. Portanto xz < yz e z > 0 ) x < y.
Proposi»c~ao 1.1 Se x e y s~ao inteiros, com x 6= 0 e y 6= 0, ent~ao xy 6= 0.
Equivalentemente, xy = 0) x = 0 ou y = 0.
Demonstra»c~ao. Se x 6= 0 e y 6= 0 ent~ao, pela lei da tricotomia (axioma (O1)),
temos x < 0 ou x > 0, bem como tamb¶em y < 0 ou y > 0. Da¶³, aplicando
o axioma (O4) ou o teorema 1.2, item 5, teremos xy > 0 ou xy < 0, portanto
xy6= 0.
Inteiros e Induc»~ao Finita 7
1.2.2 O conjunto N dos n¶umeros naturais e o Princ¶³pio da
Boa Ordem
Alguns textos introdut¶orios de estruturas alg¶ebricas, bem como outros tantos de
introdu»c~ao µa teoria dos n¶umeros apresentam uma teoria axiom¶atica dos n¶umeros
naturais e ent~ao, a partir dos n¶umeros naturais e suas propriedades, uma constru»c~ao
dos n¶umeros inteiros. Um desses conjuntos de axiomas ¶e conhecido como Axiomas
de Peano, levando o sobrenome de Giuseppe Peano, que em 1889 formulou uma
abordagem axiom¶atica dos n¶umeros naturais.
Em nossa introdu»c~ao µas estruturas alg¶ebricas, optamos por partir axiomati-
camente dos n¶umeros inteiros e ent~ao, a partir deles, de¯nir os n¶umeros naturais.
Uma das vantagens dessa estrat¶egia ¶e a economia de tempo na elabora»c~ao de con-
ceitos e resultados fundamentais, bem como o r¶apido atalho tomado em dire»c~ao a
resultados, sobre os inteiros, j¶a n~ao t~ao intuitivos, conforme veremos adiante.
De¯ni»c~ao 1.3 (O conjunto N dos n¶umeros naturais) Chamaremos de n¶ume
ros naturais aos elementos do conjunto
N = fx 2 Z j x ¸ 0g
Se x e y s~ao n¶umeros naturais ent~ao, por resultados acima estabelecidos
(quais?), x+y e xy tamb¶em s~ao n¶umeros naturais. Na linguagem dos algebristas,
o conjunto N ¶e fechado nas opera»c~oes de adi»c~ao e multiplica»c~ao de¯nidas em Z,
isto ¶e, somando-se ou multiplicando-se elementos de N, tem-se o resultado (soma
ou produto) sempre em N.
Tamb¶em s~ao utilizadas as nota»c~oes Z+=N e Z
¤
+=N
¤=fx 2 Z j x > 0g.
Os elementos de N¤ s~ao chamados inteiros positivos. Se n ¶e um inteiro e
n < 0, ent~ao n ¶e chamado um inteiro negativo. O conjunto dos inteiros negativos
ser¶a denotado por Z¤¡.
Pela lei da tricotomia, temos que Z decomp~oe-se como reuni~ao de tre^s partes
disjuntas, a saber
Z = Z¤¡ [ f0g [ Z¤+
Enunciaremos agora o
Axioma da Boa Ordem em N, ou Princ¶³pio do Menor N¶umero Natu-
ral. Cada subconjunto n~ao vazio do conjunto N possui um menor (ou primeiro)
elemento.
O axioma da boa ordem em N a¯rma que se A ¶e um subconjunto do conjunto
N e A 6= ¿ ent~ao existe um elemento n0 em A satisfazendo n0 · a para cada
inteiro a do conjunto A.
Observa»c~ao 1.3 Observe que as propriedades elementares das opera»c~oes em Z,
bem como as propriedades da rela»c~ao <, axiomatizadas ou deduzidas at¶e o presente
Inteiros e Induc»~ao Finita 8
momento, excetuando-se o Axioma da Boa Ordem em Z+, s~ao igualmente v¶alidas
para os n¶umeros racionais e para os n¶umeros reais. Do ponto de vista axiom¶atico,
o axioma da boa ordem ¶e o primeiro dos axiomas que ¶e satisfeito pelos inteiros
n~ao negativos mas n~ao ¶e satisfeito pelos racionais n~ao negativos, visto que nem
todo conjunto de n¶umeros racionais n~ao negativos possui um primeiro elemento.
Admitamos, por um momento, familiaridade com o conjunto Q dos n¶umeros
racionais. O conjunto dos n¶umeros racionais positivos da forma 1=n, com n inteiro
positivo, n~ao possui um menor elemento. Se n > 0 ent~ao n + 1 > n (visto que
1 > 0). No a^mbito dos n¶umeros racionais, ¶e sabido que ent~ao 0 < 1
n+1
< 1
n
, o
que demonstra ser imposs¶³vel encontrar um primeiro (o menor) racional da forma
1=n, com n inteiro positivo.
Observa»c~ao 1.4 (Diferentes leituras de uma mesma nota»c~ao) Quando es-
crevemos \se x 2 A ent~ao..." queremos dizer \se x ¶e elemento de A, ent~ao...",
mas na frase \para cada x 2 A, tem-se...", seremos for»cados a ler \para cada x
pertencente a A, tem-se...". De modo an¶alogo, as senten»cas \se x > 2 ent~ao..."
e \para cada x > 2, tem-se..." s~ao lidas de modos diferentes. Nas senten»cas do
primeiro tipo, os s¶³mbolos empregados ( 2, > etc.) tem um papel verbal (\¶e ele-
mento de", \¶e maior que"), enquanto que no segundo caso, o s¶³mbolo empregado
quali¯ca o objeto que o precede (\x pertencente a", \x maior que").
Estabeleceremos agora as primeiras conseqÄue^ncias do Princ¶³pio do Menor
N¶umero Natural.
Teorema 1.3
1. N~ao existe um inteiro n tal que 0 < n < 1;
2. Para cada inteiro m, n~ao existe um inteiro n tal que m < n < m+ 1;
3. Se m e n s~ao inteiros com m < n ent~ao m + 1 · n. Reciprocamente, se
m+ 1 · n ent~ao m < n.
Demonstra»c~ao.
1. Suponhamos que existe um inteiro n tal que 0 < n < 1. Tal n ¶e um n¶umero
natural, e portanto o conjunto A de n¶umeros naturais caracterizado por
A = fx 2 N j 0 < x < 1g
¶e um conjunto n~ao vazio (visto que n 2 A).
Pelo axioma da boa ordem, A tem um menor elemento n0. Por¶em
0 < n0 < 1) 0 ¢ n0 < n0 ¢ n0 < 1 ¢ n0;
ou seja, 0 < n20 < n0. Temos a¶³ uma contradi»c~ao, pois 0 < n
2
0 < 1 ) n20 2 A,
por¶em n0 ¶e o menor elemento de A e n
2
0 < n0.
Inteiros e Induc»~ao Finita 9
2. Sejam m e n dois inteiros e suponhamos que m < n < m + 1. Ent~ao
m ¡m < n ¡m < (m + 1) ¡m, ou seja, 0 < n ¡m < 1, o que ¶e imposs¶³vel,
segundo o item 1 acima.
3. (Exerc¶³cio para o leitor).
De¯ni»c~ao 1.4 Seja A um subconjunto n~ao vazio de Z.
1. Dizemos que A ¶e limitado inferiormente por um inteiro m se a ¸ m, para
cada a em A;
2. Dizemos que A ¶e limitado superiormente por um inteiro M se a ·M , para
cada a em A.
Uma conseqÄue^ncia imediata do princ¶³pio do menor n¶umero natural¶e a se-
guinte proposi»c~ao:
Proposi»c~ao 1.2 Seja A um subconjunto n~ao vazio de Z.
1. Se A ¶e limitado inferiormente por m 2 Z, ent~ao A possui um primeiro
(menor) elemento, isto ¶e, existe a0 em A tal que a ¸ a0 para cada a em A.
(Tal a0 ¶e chamado m¶³nimo de A).
2. Se A ¶e limitado superiormente por M 2 Z, ent~ao A possui um ¶ultimo
(maior) elemento, isto ¶e, existe b0 em A tal que a · b0 para cada a em A.
(Tal b0 ¶e chamado m¶aximo de A).
Demonstra»c~ao.
1. Considere o conjunto
A0 = fx 2 Z j x = a¡m; com a 2 Ag
Para cada a 2 A, temos a ¸ m, logo a¡m ¸ 0, o que implica que cada elemento
x de A0 ¶e um n¶umero natural. Como A0 ½ N e A0 6= ¿ (pois A6= ¿), pelo Axioma
da Boa Ordem, existe n0 2 A0 tal que x ¸ n0 para cada x 2 A0.
Sendo n0 um elemento de A
0, temos que n0 = a0 ¡m para algum inteiro
a0 2 A. Logo, para cada x 2 A0, x ¸ a0¡m. Isto signi¯ca que para cada a 2 A,
a¡m ¸ a0 ¡m, ou seja, a ¸ a0.
2. Considere o conjunto
A00 = fx 2 Z j x = ¡a; com a 2 Ag
Para cada a 2 A, temos a · M ou, equivalentemente, ¡a ¸ ¡M . Logo,
para cada x 2 A00, temos x ¸ ¡M . Pelo item 1 provado acima, A00 tem um
primeiro elemento, ou seja, existe c0 2 A00 tal que x ¸ c0 para cada x 2 A00. Pela
caracteriza»c~ao dos elementos de A00, c0 = ¡b0 para algum b0 2 A. Da¶³, ¡a ¸ ¡b0
para cada a 2 A, ou seja, a · b0 para cada a 2 A.
Inteiros e Induc»~ao Finita 10
1.2.3 Problemas complementares
1. °. . Para cada inteiro m, de¯ne-se o m¶odulo ou valor absoluto de m, como
sendo o inteiro
jmj =
½
m se m ¸ 0
¡m se m < 0
Mostre (prove) que se a e b s~ao inteiros, ent~ao
(a) °^. . j ¡mj = jmj;
(b) °^. . jmj ¸ 0; jmj = 0, m = 0;
(c) °^. . jmj ¢ jnj = jmnj;
(d) °. . jm+nj · jmj+jnj [Sugest~ao: mostre que jm+nj2 · (jmj+jnj)2];
(e) °. . jmj · n, ¡n · m · n.
2. °. . Demonstre que a e b s~ao inteiros com ab = 1 ent~ao a = b = §1.
[Sugest~ao: Pelas regras de sinais, temos que a e b s~ao simultaneamente
positivos ou negativos. Suponha primeiramente a > 0 e b > 0. Mostre que
ent~ao a ¢ (b¡ 1) · 0, de onde b · 1. Sendo 0 < b · 1, tem-se ent~ao b = 1
e ent~ao a = b = 1. Trabalhe ent~ao no caso a < 0 e b < 0.]
3. °^. . Prove que se a e b s~ao inteiros com a > b > 0 ent~ao a2 > b2.
4. °. . Agora prove que se a e b s~ao inteiros positivos com a2 > b2 ent~ao
a > b. Prove tamb¶em que se n ¸ 3 ¶e um inteiro positivo e an > bn ent~ao
a > b. [Sugest~ao: use os \produtos not¶aveis" a2 ¡ b2 = (a ¡ b)(a + b) e
an ¡ bn = (a¡ b)(an¡1 + an¡2b+ : : :+ abn¡2 + bn¡1), para n ¸ 2.]
5. °. . Mostre que se n ¶e um inteiro ent~ao n+1 ¶e o menor inteiro maior que n
(Todo mundo sabe disto. Compete a voce^, futuro matem¶atico, demonstr¶a-
lo!).
6. °^. . Admita familiaridade com o conjunto R dos n¶umeros reais, bem como
das propriedades da adi»c~ao e multiplica»c~ao em R. Em R tamb¶em de¯ne-
se uma rela»c~ao de ordem < satisfazendo os axiomas de ordem O1 a O4
descritos na p¶agina 5.
Sendo A um subconjunto n~ao vazio de R, dizemos que A ¶e bem-ordenado
ou que A satisfaz o axioma da boa ordem se todo subconjunto n~ao vazio de
A possui um menor elemento.
Quais dos seguintes conjuntos de n¶umeros reais ¶e bem-ordenado? Em caso
positivo, demonstre sua a¯rma»c~ao. Em caso negativo, exiba um subconjunto
n~ao vazio sem um menor elemento.
(a) R+ = fx 2 R j x ¸ 0g
(b) Z
(c) P = fx jx = 2n; n 2 Ng
Inteiros e Induc»~ao Finita 11
1.3 Indu»c~ao Finita
Os chamados princ¶³pios de indu»c~ao ¯nita nos prove^em um m¶etodo para demonstrar
propriedades dos n¶umeros inteiros que tem um formato do tipo \Para cada inteiro
n, a partir de um certo inteiro n0 dado, vale a propriedade..."
Como veremos ao ¯nal da se»c~ao, ambos os princ¶³pios s~ao conseqÄue^ncias da
proposi»c~ao 1.2, por conseguinte do Princ¶³pio do Menor Inteiro.
Teorema 1.4 (Primeiro Princ¶³pio de Indu»c~ao Finita) Seja n0 um n¶umero
inteiro e suponhamos que a cada inteiro n, n ¸ n0, est¶a associada uma a¯rma»c~ao
A(n), a qual possui, para cada n, um valor l¶ogico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condi»c~oes 1 e 2 abaixo sejam veri¯cadas:
1. A a¯rma»c~ao A(n) ¶e verdadeira para n = n0;
2. Para cada k ¸ n0, se A(k) ¶e verdadeira, ent~ao (¶e poss¶³vel demonstrar que)
A(k + 1) ¶e tamb¶em verdadeira.
Ent~ao a a¯rma»c~ao A(n) ¶e verdadeira para cada n ¸ n0.
Antes de passarmos µa demonstra»c~ao do Primeiro Princ¶³pio da Indu»c~ao Finita,
daremos exemplos de resultados (teoremas) que podem ser demonstrados mediante
sua aplica»c~ao.
Exemplo 1.1 (Teoreminha) Para cada inteiro n, n ¸ 0, o inteiro 9n ¡ 1 ¶e
divis¶³vel por 8.
Demonstra»c~ao. (habitualmente chamada \prova por indu»c~ao sobre n").
Aqui a a¯rma»c~ao A(n), que queremos provar ser verdadeira para cada inteiro
n ¸ 0, ¶e a seguinte:
A(n): \9n ¡ 1 ¶e divis¶³vel por 8".
A prova de que vale a propriedade A(n) para cada n ¸ 0, por indu»c~ao sobre
n, consiste em veri¯car a validade de A(n) em apenas duas insta^ncias, realizando
duas \veri¯ca»c~oes" (da¶³ o nome \indu»c~ao ¯nita"), a saber,
² veri¯camos a validade da a¯rma»c~ao A(n) para n = 0;
² considerando um inteiro k qualquer, k ¸ 0, supomos que a a¯rma»c~ao A(n)
j¶a esteja valendo para n = k (esta suposi»c~ao ¶e chamada hip¶otese de indu»c~ao)
e, a partir disto, deduzimos (demonstramos) que a¯rma»c~ao A(n) tamb¶em
vale para n = k + 1.
Se n = 0, A(n) = A(0) ¶e a a¯rma»c~ao \90 ¡ 1 ¶e divis¶³vel por 8", que ¶e
verdadeira.
Inteiros e Induc»~ao Finita 12
Seja ent~ao k um inteiro, k ¸ 0, e admitamos a hip¶otese de indu»c~ao, de que
A(k) ¶e verdadeira, ou seja, de que 9k ¡ 1 ¶e divis¶³vel por 8. Provaremos que ent~ao
9k+1 ¡ 1 tamb¶em ¶e divis¶³vel por 8.
Por hip¶otese de indu»c~ao, 9k¡1 = 8a para algum inteiro a. Da¶³ 9k = 8a+1.
Como conseqÄue^ncia temos ent~ao
9k+1 ¡ 1 = 9k ¢ 9¡ 1 = (8a+ 1) ¢ 9¡ 1 = 72a+ 9¡ 1 = 72a+ 8 = 8(9a+ 1),
e assim, acabamos deduzindo que 9k+1 ¡ 1 = 8(9a+ 1) ¶e um m¶ultiplo inteiro de
8, ou seja, tamb¶em ¶e divis¶³vel por 8.
Provamos portanto que a hip¶otese de indu»c~ao, isto ¶e, a validade da a¯rma»c~ao
A(k), implica na validade da a¯rma»c~ao A(k + 1).
Sendo assim, provamos, pelo Primeiro Princ¶³pio de Indu»c~ao Finita, que A(n)
¶e v¶alida para cada n ¸ 0, ou seja, que 9n ¡ 1 ¶e divis¶³vel por 8 para cada n ¸ 0.
Outro importante resultado da aritm¶etica dos inteiros, e que pode ser demon-
strado por indu»c~ao ¯nita, ¶e o seguinte teorema.
Teorema 1.5 (Algoritmo da Divis~ao Euclidiana em N) Para cada n¶umero
natural n, e cada inteiro positivo d, existem n¶umeros naturais q (quociente) e r
(resto) satisfazendo:
n = d ¢ q + r e 0 · r < d:
Al¶em disso, os naturais q e r, satisfazendo as condi»c~oes acima, s~ao ¶unicos.
Prova da existe^ncia dos naturais q e r, por indu»c~ao sobre n.
Mostraremos que, ¯xado um inteiro positivo d, para cada n¶umero natural n,
existem q e r nas condi»c~oes enunciadas.
Se n = 0, basta tomar q = r = 0.
Seja k um n¶umero natural e suponhamos que existem q e r satisfazendo
k = dq + r e 0 · r < d:
Ent~ao k + 1 = dq + (r + 1).
Como 0 · r < d, temos r + 1 < d + 1, ou seja, r + 1 · d. Se r + 1 < d,
tomamos q0 = q e r0 = r + 1 e teremos k + 1 = dq0 + r0, com 0 · r0 < d.
Se r+1 = d, ent~ao k+1 = dq+ d = d(q+1) = dq00+ r00, onde q00 = q+1
e r00 = 0.
Portanto, pelo Primeiro Princ¶³pio de Indu»c~ao Finita, para cada n 2 N ,
existem q e r satifazendo n = dq + r, com 0 · r < d.
Para a demonstra»c~ao da unicidade de q e r, veja problema 7, na se»c~ao 1.3.2.
Inteiros e Induc»~ao Finita 13
Observa»c~ao 1.5 (Uma nota»c~ao para o algoritmo da divis~ao.) Se n e d s~ao
n¶umeros naturais, com d6= 0, e se q e r s~ao n¶umeros naturais como no teorema
1.5, denotamos simbolicamente:
n d
r q
Neste caso, nessa divis~ao euclidiana de n por d, n ¶e o dividendo, d ¶e o
divisor, q ¶e o quociente e r ¶e o resto.
Observa»c~ao 1.6 O leitor poder¶a veri¯car facilmente, atrav¶es de alguns poucos
exemplos, queo teorema 1.5 n~ao ¶e v¶alido se d = 0.
Observa»c~ao 1.7 No pr¶oximo cap¶³tulo enunciaremos e provaremos um teorema do
algoritmo da divis~ao na sua vers~ao mais geral para inteiros, n~ao necessariamente
naturais.
Uma segunda forma de prova por indu»c~ao ¯nita, por vezes utilizada, ¶e esta-
belecida pelo seguinte teorema:
Teorema 1.6 (Segundo Princ¶³pio de Indu»c~ao Finita.) Seja n0 um n¶umero
inteiro e suponhamos que a cada inteiro n, n ¸ n0, est¶a associada uma a¯rma»c~ao
A(n), a qual possui, para cada n, um valor l¶ogico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condi»c~oes 1 e 2 abaixo sejam veri¯cadas:
1. A a¯rma»c~ao A(n) ¶e verdadeira para n = n0;
2. Para cada inteiro k ¸ n0, se A(n) ¶e verdadeira para n0 · n · k ent~ao
A(k + 1) ¶e tamb¶em verdadeira.
Ent~ao a a¯rma»c~ao A(n) ¶e verdadeira para cada n ¸ n0.
Observa»c~ao 1.8 O que difere o segundo princ¶³pio de indu»c~ao ¯nita do primei-
ro ¶e a forma como ¶e formulada a hip¶otese de indu»c~ao. No primeiro princ¶³pio,
supomos que a asser»c~ao A(n) ¶e verdadeira para n = k somente, enquanto que no
segundo, supomos A(n) v¶alida para cada n satisfazendo n0 · n · k. Em ambos
os princ¶³pios, devemos provar que a hip¶otese de indu»c~ao acarreta a validade de
A(n) para n = k + 1.
Antes de passarmos µa demonstra»c~ao dos dois princ¶³pios de indu»c~ao ¯nita, exibire-
mos um teorema cuja prova pode ser feita pelo segundo princ¶³pio.
Teorema 1.7 (Representa»c~ao decimal de n¶umeros naturais) Para cada in-
teiro n ¸ 1, existem n¶umeros naturais a0; : : : ; as, (s ¸ 0), com os \algarismos"
a0; : : : ; as, tomados no conjunto f0; 1; 2; : : : ; 9g, e as 6= 0, tais que
n =
sX
i=0
ai ¢ 10i = as10s + ¢ ¢ ¢+ a0100
Inteiros e Induc»~ao Finita 14
Observa»c~ao 1.9 Ilustrando o teorema acima com um exemplo, quando escreve-
mos, por exemplo, 50 237, queremos dizer 5 ¢ 104 + 2 ¢ 102 + 3 ¢ 101 + 7 ¢ 100.
Prova do teorema 1.7.
Se n = 1, podemos tomar n = a0 = 1.
Seja k ¸ 1 um inteiro e suponhamos que o resultado do teorema seja ver-
dadeiro para cada inteiro n, com 1 · n · k. Mostraremos que isto acarreta a
validade da mesma propriedade para n = k + 1.
Com efeito, realizando a divis~ao euclidiana de k + 1 por 10,
k + 1 10
r q
obtemos um quociente q 2 N e um resto r 2 N, satisfazendo k + 1 = 10q + r,
com 0 · r < 10, conforme o teorema 1.5.
Se q = 0, ent~ao k + 1 = r = a0, com a0 2 f0; 1; 2; : : : ; 9g.
Se q > 0, ent~ao q · k, pois se q > k, ent~ao k+1 = 10q+r > 10k+r ¸ 10k,
e assim k + 1 > 10k e ent~ao 1 > 9k ¸ 9, o que ¶e imposs¶³vel.
Sendo ent~ao 1 · q · k, pela hip¶otese de indu»c~ao,
q = bt ¢ 10t + ¢ ¢ ¢+ b0 ¢ 100
para certos algarismos bt; : : : ; b0, todos em f0; 1; 2; : : : ; 9g.
Ent~ao,
k + 1 = 10q + r
= 10(bt ¢ 10t + ¢ ¢ ¢+ b0 ¢ 100) + r
= bt ¢ 10t+1 + ¢ ¢ ¢+ b0 ¢ 101 + r
com bt; : : : ; b0 e r todos em f0; 1; 2; : : : ; 9g.
Logo, pelo segundo princ¶³pio de indu»c~ao ¯nita, a representa»c~ao decimal de
n ¶e poss¶³vel para cada inteiro n ¸ 1.
1.3.1 Demonstra»c~ao dos Princ¶³pios de Indu»c~ao Finita
Veremos agora que ambos os princ¶³pios de indu»c~ao ¯nita s~ao conseqÄue^ncias do
Princ¶³pio do Menor Inteiro (teorema 1.2, item 1).
Prova do Primeiro Princ¶³pio da Indu»c~ao Finita.
Suponhamos que estejam estabelecidas as hip¶oteses do teorema 1.4 e que
as condi»c~oes 1 e 2 l¶a enumeradas estejam ocorrendo.
Suponhamos que, al¶em disso, contrariamente µa tese do teorema, exista um
inteiro s ¸ n0 tal que a a¯rma»c~ao A(s) ¶e falsa.
Inteiros e Induc»~ao Finita 15
Seja S = fn 2 Z j n ¸ n0 e A(n) ¶e falsag.
S ¶e n~ao vazio, pois s 2 S.
Sendo S ½ Z, e limitado inferiormente por n0, pelo Princ¶³pio do Menor
Inteiro, proposi»c~ao 1.2, item 1, S possui um menor elemento s0.
Como n0 · s0 e A(n0) ¶e verdadeira, temos n0 < s0, e ent~ao n0 · s0 ¡ 1.
Seja k = s0¡1. Ent~ao A(k) ¶e verdadeira, pois k < s0 e s0 ¶e o menor inteiro
n com A(n) falsa.
Mas como k ¸ n0 e A(k) ¶e verdadeira temos ent~ao A(k + 1) verdadeira.
Por¶em k + 1 = s0 e A(s0) ¶e falsa.
Assim, temos uma contradi»c~ao decorrente do fato de existir um inteiro s ¸ n0
para o qual A(s) ¶e falsa.
Portanto A(n) ¶e verdadeira para cada inteiro n ¸ n0.
Prova do Segundo Princ¶³pio da Indu»c~ao Finita.
Salvo ligeiras modi¯ca»c~oes, a prova do Segundo Princ¶³pio da Indu»c~ao Finita,
teorema 1.6, ¶e ide^ntica µa prova apresentada acima.
A ¶unica diferen»ca se d¶a nas ¶ultimas linhas da demonstra»c~ao.
Considere S e s0 tal como na demonstra»c~ao do primeiro princ¶³pio de indu»c~ao.
Suponha agora que est~ao satisfeitas as condi»c~oes 1 e 2 da hip¶otese do teorema
1.6.
Tal como na demonstra»c~ao acima, teremos n0 · s0 ¡ 1. Como s0 ¶e o
menor inteiro n com A(n) falsa, temos ent~ao A(n) verdadeira para cada n tal
que n0 · n · s0 ¡ 1. Tomando k = s0 ¡ 1, temos ent~ao A(n) verdadeira para
cada n satisfazendo n0 · n · k. Pelo item 2 da hip¶otese, isto acarreta A(k + 1)
verdadeira. Mas k + 1 = s0 e novamente temos uma contradi»c~ao.
1.3.2 Problemas Complementares
1. °^. . Mostre, por indu»c~ao sobre n, que, se n ¸ 1 ent~ao:
(a) 1 + 2 + ¢ ¢ ¢+ n = n(n+1)
2
;
(b) 12 + 22 + ¢ ¢ ¢+ n2 = n(n+1)(2n+1)
6
;
(c) 13 + 23 + ¢ ¢ ¢+ n3 = [n(n+1)
2
]2;
2. Mostre tamb¶em que:
(a) °^. . Para cada inteiro n ¸ 0, n2 + n ¶e par. [Um inteiro ¶e par se ¶e da
forma 2m para algum inteiro m].
(b) °^. . (aqui admita familiaridade com os n¶umeros reais) Para cada n¶u-
mero real positivo a e cada inteiro n ¸ 0, tem-se (1 + a)n ¸ 1 + na.
Inteiros e Induc»~ao Finita 16
(c) °. . Para cada inteiro m, m3 ¡m ¶e divis¶³vel por 3.
(d) °. . 42n+1+3n+2 ¶e um m¶ultiplo de 13 (isto ¶e, ¶e da forma 13 ¢ a com a
inteiro), para cada n ¸ 0;
(e) °. . Todo conjunto de n elementos possui 2n subconjuntos.
3. °. . Aponte o erro na seguinte \demonstra»c~ao" de que 1 = : : : = n para
cada inteiro n ¸ 1:
A a¯rma»c~ao ¶e verdadeira se n = 1.
Supondo que ela ¶e v¶alida para n = k, com k ¸ 1, temos 1 = : : : = k, e
portanto 1 + 1 = : : : = k + 1.
Por hip¶otese de indu»c~ao, 1 = 2 = : : : = k. Como tamb¶em 2 = : : : = k + 1,
por transitividade teremos 1 = 2 = : : : = k + 1.
Assim, pelo primeiro princ¶³pio de indu»c~ao ¯nita, 1 = : : : = n, para cada
inteiro n ¸ 1.
4. °^. . Para cada a 2 Z e cada n 2 N, de¯ne-se a pote^ncia de base a e
expoente n (ou n-¶esima pote^ncia de a) como sendo o inteiro denotado por
an e de¯nido pelas leis:
(i) Se n = 0, ent~ao an = a0 = 1;
(ii) Para cada k ¸ 0, ak+1 = ak ¢ a.
A partir das duas leis de¯nidas acima, prove, por indu»c~ao sobre n, que se m
e n s~ao n¶umeros naturais e a ¶e um inteiro, ent~ao
(a) am+n = am ¢an [Sugest~ao: Assuma que m ¶e um n¶umero natural ¯xado
e fa»ca a prova por indu»c~ao sobre n];
(b) (am)n = amn;
(c) Se a6= 1 ent~ao 1 + a+ a2 + ¢ ¢ ¢+ an = an+1¡1
a¡1
5. Sendo n e p n¶umeros naturais, com n ¸ p, de¯ne-se o n¶umero binomial
Cn;p =
¡
n
p
¢
, µ
n
p
¶
=
n!
p!(n¡ p)!
sendo 0! = 1! = 1, 2! = 2 ¢ 1 = 2, 3! = 3 ¢ 2 ¢ 1 = 6, etc. De um modo
geral, se n ¸ 1, n! = n ¢ (n¡ 1)!
(a) °. . Prove a rela»c~ao de Stifel: sendo n e p n¶umeros naturais, se n ¸
p+ 1, µ
n
p
¶
+
µ
n
p+ 1
¶
=
µ
n+ 1
p+ 1
¶
(b) °. . Prove a f¶ormula chamada bino^mio de Newton: sendo a e b n¶umeros
reais e n um n¶umero natural, n ¸ 1,
(a+ b)n =
Pn
k=0
¡
n
k
¢
an¡kbk =
¡
n
0
¢
an +
¡
n
1
¢
an¡1b+ ¢ ¢ ¢+ ¡n
r
¢
an¡rbr +
¢ ¢ ¢+ ¡n
1
¢
abn¡1 +
¡
n
0
¢
bn
Inteiros e Induc»~ao Finita 17
(c) °. . Prove que, sendo n ¸ p ¸ 1, ¡n
p
¢
¶e o n¶umero de subconjuntos
(\combina»c~oes"), com p elementos, de um conjunto contendo n ele-
mentos. [Sugest~ao: Fa»ca a demonstra»c~ao por indu»c~ao sobre n, usando
o primeiro princ¶³pio de indu»c~ao ¯nita e a rela»c~ao de Stifel.]
6. °_. . A seqÄue^ncia de Fibonacci ¶e um exemplo de uma seqÄue^ncia de inteirosde¯nida indutivamente. Ela ¶e de¯nida como a0; a1; a2; : : :, sendo
a0 = 0; a1 = 1 e, an+1 = an + an¡1 para cada n ¸ 0
Assim, ela come»ca como 0; 1; 1; 2; 3; 5; 8; 13; : : :
(a) Prove por indu»c~ao sobre n que
an =
[(1 +
p
5)=2]n ¡ [(1¡p5)=2]np
5
[Sugest~ao: Use o segundo princ¶³pio da indu»c~ao. Provavelmente lhe ser¶a
¶util saber que (1+
p
5
2
)2 = 3+
p
5
2
]
(b) (para experts em C¶alculo I) Mostre que lim
n!1
(an+1
an
) = Á = 1+
p
5
2
. (J¶a
ouviu falar deste n¶umero, a \raz~ao ¶aurea"?)
7. °. . Mostre que os n¶umeros naturais q (quociente) e r (resto) no enunciado
do teorema do algoritmo da divis~ao em N (teorema 1.5, p¶agina 12), s~ao
¶unicos. [Sugest~ao: mostre que sendo n e d n¶umeros naturais, com d6= 0, se
n = dq1+r1 = dq2+r2 para certos naturais q1; q2; r1; r2, com 0 · r1; r2 < d,
ent~ao djq1 ¡ q2j = jr1 ¡ r2j < d e logo jq1 ¡ q2j = 0.]
8. °_. . (Para experts) Mostre que os algarismos a0; : : : ; as utilizados na repre-
senta»c~ao decimal de um n¶umero natural n s~ao determinados de maneira
¶unica. [Sugest~ao: Mostre que se a0 + a110 + : : : + an10
n = 0, sendo os
coe¯cientes a0, a1, : : :, an, todos tomados no conjunto de inteiros f¡9;¡8;
: : : ; ¡1; 0; 1; 2; : : : ; 9g, ent~ao an10n = ¡a0 ¡a110 ¡ : : : ¡an¡110n¡1 )
janj10n · ja0j+ ja1j10 + : : :+ jan¡1j10n¡1 · 9 + 9 ¢ 10 + : : :+ 9 ¢ 10n¡1 =
10n ¡ 1 < 10n ) janj10n < 10n ) an = 0. ConseqÄuentemente, se
a0 + a110 + : : :+ an10
n = 0, e a0, a1, : : :, an, est~ao todos no conjunto de
d¶³gitos f¡9;¡8; : : : ;¡1; 0; 1; 2; : : : ; 9g ent~ao an = an¡1 = : : : = a0 = 0].
9. °^. . Considere a igualdade
2 + 4 + 6 + ¢ ¢ ¢+ 2n = n2 + n+ 100
Mostre que tal igualdade ¶e falsa. Mostre por¶em que, sendo k um inteiro,
supondo-a verdadeira para n = k podemos demonstrar que tamb¶em ¶e ver-
dadeira para n = k + 1.
10. °^. . Considere a a¯rma»c~ao
n2 ¡ n+ 5 ¶e primo
Inteiros e Induc»~ao Finita 18
(Um inteiro p ¶e primo se p6= 0, p6= §1, e seus ¶unicos fatores inteiros s~ao
§1 e §p)
Mostre que essa a¯rma»c~ao ¶e verdadeira se n 2 f1; 2; 3; 4g, mas ¶e falsa se
n = 5.