Estruturas Algébricas Inteiros e Indução Finita

Prévia do material em texto

Cap´ıtulo 1
Inteiros e Induc¸a˜o Finita
Neste cap´ıtulo estudaremos uma estrutura alge´brica que ja´ nos e´ familiar: a estru-
tura alge´brica do conjunto Z dos nu´meros inteiros.
Por estrutura alge´brica do conjunto Z entende-se o conjunto de propriedades
dos nu´meros inteiros que dizem respeito a`s suas duas operac¸o˜es habituais, a adic¸a˜o
e a multiplicac¸a˜o, bem como a` ordem definida no conjunto Z pela relac¸a˜o <, a
chamada relac¸a˜o de ordem “menor”.
Na parte final do cap´ıtulo, estabeleceremos os assim chamados princ´ıpios de
induc¸a˜o finita e mostraremos algumas de suas aplicac¸o˜es.
1.1 Axioma´tica da estrutura de Z
Introduziremos as operac¸o˜es de adic¸a˜o e multiplicac¸a˜o em Z de forma axioma´tica,
isto e´, a partir de um conjunto de axiomas ou postulados — propriedades ba´sicas,
admitidas a priori — que caracterizam essas operac¸o˜es em Z. A partir desse
conjunto de propriedades axioma´ticas, deduziremos algumas outras propriedades,
tambe´m elementares e conhecidas por todos no´s, pore´m “demonstra´veis”, isto e´,
dedut´ıveis a partir dos axiomas ba´sicos.
Admitiremos axiomaticamente que existe um conjunto Z, cujos elementos
sa˜o chamados nu´meros inteiros, havendo em Z dois elementos destacados e dis-
tintos que sa˜o, a saber, 0 (zero) e 1 (um).
Admitiremos tambe´m que em Z, sa˜o definidas duas operac¸o˜es, a adic¸a˜o
(denotada por +) e a multiplicac¸a˜o (denotada por ·). Dizendo que + e · sa˜o duas
operac¸o˜es em Z, queremos dizer que + e · sa˜o duas func¸o˜es
+ : Z× Z→ Z e · : Z× Z→ Z,
sendo que a primeira (+) associa cada par ordenado de inteiros (x, y) a um u´nico
inteiro x+y, chamado soma de x e y, e a segunda (·) associa cada par de inteiros
(x, y) a um u´nico inteiro x · y (denotado tambe´m por xy, quando isto na˜o gerar
ambigu¨idade), chamado produto de x e y.
1
2 Estruturas Alge´bricas
Assumiremos que as operac¸o˜es adic¸a˜o e multiplicac¸a˜o 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 adic¸a˜o em Z e´ associativa);
(A2) x+ y = y + x (a adic¸a˜o em Z e´ comutativa);
(A3) x+ 0 = 0 + x = x (isto e´, 0 e´ elemento neutro da adic¸a˜o em Z);
(A4) Existe um elemento −x em Z, chamado oposto de x ou inverso aditivo de
x, ou ainda sime´trico de x relativamente a` operac¸a˜o adic¸a˜o, satisfazendo
x+ (−x) = (−x) + x = 0.
(M1) x(yz) = (xy)z (a multiplicac¸a˜o em Z e´ tambe´m associativa);
(M2) xy = yx (a multiplicac¸a˜o em Z e´ tambe´m comutativa);
(M3) x · 1 = 1 · x = x (1 e´ elemento neutro da multiplicac¸a˜o em Z);
(D) x(y + z) = xy + xz (a multiplicac¸a˜o e´ distributiva em relac¸a˜o a` adic¸a˜o).
Definic¸a˜o 1.1 (Subtrac¸a˜o em Z) Chama-se diferenc¸a de dois inteiros x e y a`
soma x+ (−y). A subtrac¸a˜o em Z e´ a operac¸a˜o −:Z×Z→ Z, que associa cada
par ordenado (x, y) a` diferenc¸a 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 u´nico elemento neutro da adic¸a˜o em Z)
2. x+ y = 0⇒ y = −x (ou seja, o oposto de um inteiro x e´ u´nico);
3. x+ y = x+ z ⇒ y = z ( lei do cancelamento da adic¸a˜o);
4. −(−x) = x;
5. −(x+ y) = −x− y (atenc¸a˜o!: −x− y significa (−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¸a˜o Finita 3
Demonstrac¸a˜o.
1. x+y = x⇒ (−x) + (x+y) = (−x) +x. Pelos axiomas (A1), (A3) e (A4),
temos consequ¨entemente que
((−x) + x) + y = 0⇒ 0 + y = 0⇒ y = 0
2. Se x+ y = 0 enta˜o (−x) + (x+ y) = (−x) + 0. Pelos axiomas (A1), (A3)
e (A4), temos consequ¨entemente que
((−x) + x) + y = −x⇒ 0 + y = −x⇒ y = −x
3. Se x + y = x + z, enta˜o (−x) + (x + y) = (−x) + (x + z). Pelo axioma
(A1), ((−x) + x) + y = ((−x) + x) + z ⇒ 0 + y = 0 + z, e enta˜o, pelo
axioma (A3), y = z.
4. Pelo axioma (A4) −(−x) + (−x) = 0.
Logo, [−(−x)+(−x)]+x = 0+x. Aplicando enta˜o os axiomas (A1) e (A3),
deduzimos: −(−x) + [(−x) + x] = x⇒ −(−x) + 0 = x⇒ −(−x) = x.
5. (Exerc´ıcio para o leitor. Sugesta˜o: Calcule inicialmente a soma (x + y) +
[(−x) + (−y)], aplicando os axiomas da adic¸a˜o.)
6. Seja x · 0 = a. Enta˜o, pelos axiomas (A3) e (D), a = x · 0 = x · (0 + 0) =
x · 0 + x · 0 = a + a. Logo, a + a = a + 0, e enta˜o, 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. Sugesta˜o: Aplique o resultado do item anterior)
9. (Exerc´ıcio para o leitor.)
Observac¸a˜o 1.1 Os axiomas listados ainda na˜o sa˜o suficientes para caracterizar
o conjunto Z de maneira u´nica. Em outras palavras, existem outras estruturas
alge´bricas familiares que tambe´m satisfazem a`s propriedades acima.
O leitor certamente ja´ esta´ familiarizado com os conjuntos nume´ricos Q, dos
nu´meros racionais, e R, dos nu´meros reais. Sabe portanto, que em Q, bem como
em R, tambe´m sa˜o definidas uma adic¸a˜o e uma multiplicac¸a˜o, as quais, embora
tendo propriedades adicionais, satisfazem a todos os axiomas listados acima.
Isto indica claramente que esses axiomas sa˜o satisfeitos por outras estruturas
alge´bricas familiares, tais como as de Q e R.
Existem tambe´m estruturas alge´bricas “abstratas” satisfazendo os axiomas
(A1), (A2), (A3), (A4), (M1), (M2), (M3) e (D).
4 Estruturas Alge´bricas
Consideremos, por exemplo, o conjunto Z = {0, 1}, no qual definiremos
uma adic¸a˜o e uma multiplicac¸a˜o conforme as tabelas abaixo (atenc¸a˜o! Aqui, os
nu´meros 0 e 1 na˜o sa˜o aqueles do conjunto Z dos nu´meros inteiros.)
+ 0 1
0 0 1
1 1 0
· 0 1
0 0 0
1 0 1
Assim, as operac¸o˜es + e ·, definidas em Z conforme suas ta´buas dadas
acima, satisfazem os axiomas (A1), (A2), (A3), (A4), (M1), (M2), (M3) e (D).
Verifique. Note que este “Z” tem apenas dois elementos.
1.1.1 Problemas complementares
1. ©^. . Usando somente os axiomas (A1) a (D) das operac¸o˜es em Z, deduza
que (−1)(−1) = 1. (Na˜o utilize o resultado do item 8 do teorema 1.1) Use
o menor nu´mero de axiomas poss´ıvel para essa deduc¸a˜o. Quais axiomas sa˜o
utilizados nela?
2. ©^. . Existe um elemento neutro para a operac¸a˜o de subtrac¸a˜o em Z? Ex-
plique.
1.2 Ordem em Z
Ja´ temos um conhecimento intuitivo de que os inteiros sa˜o 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 sec¸a˜o trataremos de caracterizar a relac¸a˜o de ordem
“menor” (<) no conjunto Z de maneira formal.
Definic¸a˜o 1.2 (Relac¸a˜o num conjunto) Sendo A um conjunto na˜o vazio, dize-
mos que R e´ uma relac¸a˜o 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 sa˜o todos os pares ordenados (a, b), com a ∈ A e b ∈ B.)
Por exemplo, R = {(1, 2), (1, 4), (2, 3)} e´ uma relac¸a˜o em A = {1, 2, 3, 4}.
Tambe´m sa˜o relac¸o˜es em A os conjuntos S = ø e T = A× A.
Se S e´ uma relac¸a˜o em A, e se o par (a, b) faz parte dessa relac¸a˜o, escrevemos
(a, b) ∈ S ou aSb, e dizemos que a esta´ relacionado com b pela relac¸a˜o S. Se
(x, y) 6∈ S, tambe´m escrevemos x 6 Sy.
No exemplo acima, temos 1S2, 1S4 e 2S3 mas, por exemplo, 16 S3.
Inteiros e Induc¸a˜o Finita 5
1.2.1 Axiomas para a relac¸a˜o “menor” (<) em Z
Admitiremos que em Z esta´ definida uma relac¸a˜o <, chamada relac¸a˜o menor. Se
(x, y) ∈<, 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 relac¸a˜o < 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 afirmac¸o˜es:
x < y; x = y; y < x
(O2) Se x < y e y < z enta˜o x < z (a relac¸a˜o < em Z e´ transitiva);
(O3) Sex < y enta˜o x + z < y + z (a relac¸a˜o < em Z e´ compat´ıvel com a
adic¸a˜o);
(O4) Se x > 0 e y > 0 enta˜o xy > 0 (a relac¸a˜o < em Z e´ compat´ıvel com a
multiplicac¸a˜o).
Observac¸a˜o 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 relac¸a˜o <) 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 adic¸a˜o) Se x+ z < y + z enta˜o x < y;
4. Se x < y e z < w enta˜o x+ z < y + w;
5. (Regras de Sinais)
(a) Se x < 0 e y > 0 enta˜o xy < 0;
(b) Se x < 0 e y < 0 enta˜o xy > 0;
6. Se x 6= 0 enta˜o x2 > 0;
7. 1 > 0;
8. (a) Se x < y e z > 0 enta˜o xz < yz;
(b) Se x < y e z < 0 enta˜o xz > yz;
9. Se x > y > 0 e z > w > 0 enta˜o xz > yw > 0;
6 Estruturas Alge´bricas
10. (Leis do Cancelamento para a multiplicac¸a˜o)
(a) Se xz < yz e z > 0 enta˜o x < y;
(b) Se xz < yz e z < 0 enta˜o x > y.
Demonstrac¸a˜o.
1. Se x < y enta˜o, 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 enta˜o, 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 enta˜o, pelo axioma
(O2), x+ z < y + w.
5. Provaremos a primeira das afirmac¸o˜es e deixaremos a segunda como exer-
c´ıcio. Se x < 0 e y > 0 enta˜o −x > 0 e y > 0. Pelo axioma (O4), temos
−(xy) = (−x)y > 0, e enta˜o, pelo item 2, xy < 0,
6. (Exerc´ıcio para o leitor).
7. Temos que 1 6= 0 e que 12 = 1 · 1 = 1. Da´ı, pelo item 6, 1 > 0.
8. Provaremos a primeira das afirmac¸o˜es e deixaremos a segunda como exer-
c´ıcio. Se x < y e z > 0, enta˜o 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 enta˜o xz < yz.
9. (Exerc´ıcio para o leitor).
10. Provaremos o item (a) e deixaremos o item (b) como exerc´ıcio. Ambos os
itens sa˜o consequ¨eˆncia direta do item 8. Se xz < yz e z > 0 enta˜o neces-
sariamente x < y pois, caso contra´rio, 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.
Proposic¸a˜o 1.1 Se x e y sa˜o inteiros, com x 6= 0 e y 6= 0, enta˜o xy 6= 0.
Equivalentemente, xy = 0⇒ x = 0 ou y = 0.
Demonstrac¸a˜o. Se x 6= 0 e y 6= 0 enta˜o, pela lei da tricotomia (axioma (O1)),
temos x < 0 ou x > 0, bem como tambe´m y < 0 ou y > 0. Da´ı, aplicando
o axioma (O4) ou o teorema 1.2, item 5, teremos xy > 0 ou xy < 0, portanto
xy 6= 0.
Inteiros e Induc¸a˜o Finita 7
1.2.2 O conjunto N dos nu´meros naturais e o Princ´ıpio da
Boa Ordem
Alguns textos introduto´rios de estruturas alge´bricas, bem como outros tantos de
introduc¸a˜o a` teoria dos nu´meros apresentam uma teoria axioma´tica dos nu´meros
naturais e enta˜o, a partir dos nu´meros naturais e suas propriedades, uma construc¸a˜o
dos nu´meros inteiros. Um desses conjuntos de axiomas e´ conhecido como Axiomas
de Peano, levando o sobrenome de Giuseppe Peano, que em 1889 formulou uma
abordagem axioma´tica dos nu´meros naturais.
Em nossa introduc¸a˜o a`s estruturas alge´bricas, optamos por partir axiomati-
camente dos nu´meros inteiros e enta˜o, a partir deles, definir os nu´meros naturais.
Uma das vantagens dessa estrate´gia e´ a economia de tempo na elaborac¸a˜o de con-
ceitos e resultados fundamentais, bem como o ra´pido atalho tomado em direc¸a˜o a
resultados, sobre os inteiros, ja´ na˜o ta˜o intuitivos, conforme veremos adiante.
Definic¸a˜o 1.3 (O conjunto N dos nu´meros naturais) Chamaremos de nu´me
ros naturais aos elementos do conjunto
N = {x ∈ Z | x ≥ 0}
Se x e y sa˜o nu´meros naturais enta˜o, por resultados acima estabelecidos
(quais?), x+y e xy tambe´m sa˜o nu´meros naturais. Na linguagem dos algebristas,
o conjunto N e´ fechado nas operac¸o˜es de adic¸a˜o e multiplicac¸a˜o definidas em Z,
isto e´, somando-se ou multiplicando-se elementos de N, tem-se o resultado (soma
ou produto) sempre em N.
Tambe´m sa˜o utilizadas as notac¸o˜es Z+=N e Z∗+=N∗={x ∈ Z | x > 0}.
Os elementos de N∗ sa˜o chamados inteiros positivos. Se n e´ um inteiro e
n < 0, enta˜o n e´ chamado um inteiro negativo. O conjunto dos inteiros negativos
sera´ denotado por Z∗−.
Pela lei da tricotomia, temos que Z decompo˜e-se como reunia˜o de treˆs partes
disjuntas, a saber
Z = Z∗− ∪ {0} ∪ Z∗+
Enunciaremos agora o
Axioma da Boa Ordem em N, ou Princ´ıpio do Menor Nu´mero Natu-
ral. Cada subconjunto na˜o vazio do conjunto N possui um menor (ou primeiro)
elemento.
O axioma da boa ordem em N afirma que se A e´ um subconjunto do conjunto
N e A 6= ø enta˜o existe um elemento n0 em A satisfazendo n0 ≤ a para cada
inteiro a do conjunto A.
Observac¸a˜o 1.3 Observe que as propriedades elementares das operac¸o˜es em Z,
bem como as propriedades da relac¸a˜o <, axiomatizadas ou deduzidas ate´ o presente
8 Estruturas Alge´bricas
momento, excetuando-se o Axioma da Boa Ordem em Z+, sa˜o igualmente va´lidas
para os nu´meros racionais e para os nu´meros reais. Do ponto de vista axioma´tico,
o axioma da boa ordem e´ o primeiro dos axiomas que e´ satisfeito pelos inteiros
na˜o negativos mas na˜o e´ satisfeito pelos racionais na˜o negativos, visto que nem
todo conjunto de nu´meros racionais na˜o negativos possui um primeiro elemento.
Admitamos, por um momento, familiaridade com o conjunto Q dos nu´meros
racionais. O conjunto dos nu´meros racionais positivos da forma 1/n, com n inteiro
positivo, na˜o possui um menor elemento. Se n > 0 enta˜o n + 1 > n (visto que
1 > 0). No aˆmbito dos nu´meros racionais, e´ sabido que enta˜o 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.
Observac¸a˜o 1.4 (Diferentes leituras de uma mesma notac¸a˜o) Quando es-
crevemos “se x ∈ A enta˜o...” queremos dizer “se x e´ elemento de A, enta˜o...”,
mas na frase “para cada x ∈ A, tem-se...”, seremos forc¸ados a ler “para cada x
pertencente a A, tem-se...”. De modo ana´logo, as sentenc¸as “se x > 2 enta˜o...”
e “para cada x > 2, tem-se...” sa˜o lidas de modos diferentes. Nas sentenc¸as do
primeiro tipo, os s´ımbolos empregados ( ∈, > etc.) tem um papel verbal ( “e´ ele-
mento de”, “e´ maior que”), enquanto que no segundo caso, o s´ımbolo empregado
qualifica o objeto que o precede ( “x pertencente a”, “x maior que”).
Estabeleceremos agora as primeiras consequ¨eˆncias do Princ´ıpio do Menor
Nu´mero Natural.
Teorema 1.3
1. Na˜o existe um inteiro n tal que 0 < n < 1;
2. Para cada inteiro m, na˜o existe um inteiro n tal que m < n < m+ 1;
3. Se m e n sa˜o inteiros com m < n enta˜o m + 1 ≤ n. Reciprocamente, se
m+ 1 ≤ n enta˜o m < n.
Demonstrac¸a˜o.
1. Suponhamos que existe um inteiro n tal que 0 < n < 1. Tal n e´ um nu´mero
natural, e portanto o conjunto A de nu´meros naturais caracterizado por
A = {x ∈ N | 0 < x < 1}
e´ um conjunto na˜o vazio (visto que n ∈ A).
Pelo axioma da boa ordem, A tem um menor elemento n0. Pore´m
0 < n0 < 1⇒ 0 · n0 < n0 · n0 < 1 · n0,
ou seja, 0 < n20 < n0. Temos a´ı uma contradic¸a˜o, pois 0 < n
2
0 < 1 ⇒ n20 ∈ A,
pore´m n0 e´ o menor elemento de A e n
2
0 < n0.
Inteiros e Induc¸a˜o Finita 9
2. Sejam m e n dois inteiros e suponhamos que m < n < m + 1. Enta˜o
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).
Definic¸a˜o 1.4 Seja A um subconjunto na˜o 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 consequ¨eˆncia imediata do princ´ıpio do menornu´mero natural e´ a se-
guinte proposic¸a˜o:
Proposic¸a˜o 1.2 Seja A um subconjunto na˜o vazio de Z.
1. Se A e´ limitado inferiormente por m ∈ Z, enta˜o 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 ∈ Z, enta˜o A possui um u´ltimo
(maior) elemento, isto e´, existe b0 em A tal que a ≤ b0 para cada a em A.
(Tal b0 e´ chamado ma´ximo de A).
Demonstrac¸a˜o.
1. Considere o conjunto
A′ = {x ∈ Z | x = a−m, com a ∈ A}
Para cada a ∈ A, temos a ≥ m, logo a−m ≥ 0, o que implica que cada elemento
x de A′ e´ um nu´mero natural. Como A′ ⊂ N e A′ 6= ø (pois A 6= ø), pelo Axioma
da Boa Ordem, existe n0 ∈ A′ tal que x ≥ n0 para cada x ∈ A′.
Sendo n0 um elemento de A
′, temos que n0 = a0 −m para algum inteiro
a0 ∈ A. Logo, para cada x ∈ A′, x ≥ a0−m. Isto significa que para cada a ∈ A,
a−m ≥ a0 −m, ou seja, a ≥ a0.
2. Considere o conjunto
A′′ = {x ∈ Z | x = −a, com a ∈ A}
Para cada a ∈ A, temos a ≤ M ou, equivalentemente, −a ≥ −M . Logo,
para cada x ∈ A′′, temos x ≥ −M . Pelo item 1 provado acima, A′′ tem um
primeiro elemento, ou seja, existe c0 ∈ A′′ tal que x ≥ c0 para cada x ∈ A′′. Pela
caracterizac¸a˜o dos elementos de A′′, c0 = −b0 para algum b0 ∈ A. Da´ı, −a ≥ −b0
para cada a ∈ A, ou seja, a ≤ b0 para cada a ∈ A.
10 Estruturas Alge´bricas
1.2.3 Problemas complementares
1. ©. . Para cada inteiro m, define-se o mo´dulo ou valor absoluto de m, como
sendo o inteiro
|m| =
{
m se m ≥ 0
−m se m < 0
Mostre (prove) que se a e b sa˜o inteiros, enta˜o
(a) ©^. . | −m| = |m|;
(b) ©^. . |m| ≥ 0; |m| = 0⇔ m = 0;
(c) ©^. . |m| · |n| = |mn|;
(d) ©. . |m+n| ≤ |m|+|n| [Sugesta˜o: mostre que |m+n|2 ≤ (|m|+|n|)2];
(e) ©. . |m| ≤ n⇔ −n ≤ m ≤ n.
2. ©. . Demonstre que a e b sa˜o inteiros com ab = 1 enta˜o a = b = ±1.
[Sugesta˜o: Pelas regras de sinais, temos que a e b sa˜o simultaneamente
positivos ou negativos. Suponha primeiramente a > 0 e b > 0. Mostre que
enta˜o a · (b− 1) ≤ 0, de onde b ≤ 1. Sendo 0 < b ≤ 1, tem-se enta˜o b = 1
e enta˜o a = b = 1. Trabalhe enta˜o no caso a < 0 e b < 0.]
3. ©^. . Prove que se a e b sa˜o inteiros com a > b > 0 enta˜o a2 > b2.
4. ©. . Agora prove que se a e b sa˜o inteiros positivos com a2 > b2 enta˜o
a > b. Prove tambe´m que se n ≥ 3 e´ um inteiro positivo e an > bn enta˜o
a > b. [Sugesta˜o: use os “produtos nota´veis” 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 enta˜o n+ 1 e´ o menor inteiro maior que n
(Todo mundo sabe disto. Compete a voceˆ, futuro matema´tico, demonstra´-
lo!).
6. ©^. . Admita familiaridade com o conjunto R dos nu´meros reais, bem como
das propriedades da adic¸a˜o e multiplicac¸a˜o em R. Em R tambe´m define-
se uma relac¸a˜o de ordem < satisfazendo os axiomas de ordem O1 a O4
descritos na pa´gina 5.
Sendo A um subconjunto na˜o vazio de R, dizemos que A e´ bem-ordenado
ou que A satisfaz o axioma da boa ordem se todo subconjunto na˜o vazio de
A possui um menor elemento.
Quais dos seguintes conjuntos de nu´meros reais e´ bem-ordenado? Em caso
positivo, demonstre sua afirmac¸a˜o. Em caso negativo, exiba um subconjunto
na˜o vazio sem um menor elemento.
(a) R+ = {x ∈ R |x ≥ 0}
(b) Z
(c) P = {x |x = 2n, n ∈ N}
Inteiros e Induc¸a˜o Finita 11
1.3 Induc¸a˜o Finita
Os chamados princ´ıpios de induc¸a˜o finita nos proveˆem um me´todo para demonstrar
propriedades dos nu´meros 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 final da sec¸a˜o, ambos os princ´ıpios sa˜o consequ¨eˆncias da
proposic¸a˜o 1.2, por conseguinte do Princ´ıpio do Menor Inteiro.
Teorema 1.4 (Primeiro Princ´ıpio de Induc¸a˜o Finita) Seja n0 um nu´mero
inteiro e suponhamos que a cada inteiro n, n ≥ n0, esta´ associada uma afirmac¸a˜o
A(n), a qual possui, para cada n, um valor lo´gico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condic¸o˜es 1 e 2 abaixo sejam verificadas:
1. A afirmac¸a˜o A(n) e´ verdadeira para n = n0;
2. Para cada k ≥ n0, se A(k) e´ verdadeira, enta˜o (e´ poss´ıvel demonstrar que)
A(k + 1) e´ tambe´m verdadeira.
Enta˜o a afirmac¸a˜o A(n) e´ verdadeira para cada n ≥ n0.
Antes de passarmos a` demonstrac¸a˜o do Primeiro Princ´ıpio da Induc¸a˜o Finita,
daremos exemplos de resultados (teoremas) que podem ser demonstrados mediante
sua aplicac¸a˜o.
Exemplo 1.1 (Teoreminha) Para cada inteiro n, n ≥ 0, o inteiro 9n − 1 e´
divis´ıvel por 8.
Demonstrac¸a˜o. (habitualmente chamada “prova por induc¸a˜o sobre n”).
Aqui a afirmac¸a˜o 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 induc¸a˜o sobre
n, consiste em verificar a validade de A(n) em apenas duas instaˆncias, realizando
duas “verificac¸o˜es” (da´ı o nome “induc¸a˜o finita”), a saber,
• verificamos a validade da afirmac¸a˜o A(n) para n = 0;
• considerando um inteiro k qualquer, k ≥ 0, supomos que a afirmac¸a˜o A(n)
ja´ esteja valendo para n = k (esta suposic¸a˜o e´ chamada hipo´tese de induc¸a˜o)
e, a partir disto, deduzimos (demonstramos) que afirmac¸a˜o A(n) tambe´m
vale para n = k + 1.
Se n = 0, A(n) = A(0) e´ a afirmac¸a˜o “90 − 1 e´ divis´ıvel por 8”, que e´
verdadeira.
12 Estruturas Alge´bricas
Seja enta˜o k um inteiro, k ≥ 0, e admitamos a hipo´tese de induc¸a˜o, de que
A(k) e´ verdadeira, ou seja, de que 9k − 1 e´ divis´ıvel por 8. Provaremos que enta˜o
9k+1 − 1 tambe´m e´ divis´ıvel por 8.
Por hipo´tese de induc¸a˜o, 9k−1 = 8a para algum inteiro a. Da´ı 9k = 8a+1.
Como consequ¨eˆncia temos enta˜o
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 mu´ltiplo inteiro de
8, ou seja, tambe´m e´ divis´ıvel por 8.
Provamos portanto que a hipo´tese de induc¸a˜o, isto e´, a validade da afirmac¸a˜o
A(k), implica na validade da afirmac¸a˜o A(k + 1).
Sendo assim, provamos, pelo Primeiro Princ´ıpio de Induc¸a˜o Finita, que A(n)
e´ va´lida para cada n ≥ 0, ou seja, que 9n − 1 e´ divis´ıvel por 8 para cada n ≥ 0.
Outro importante resultado da aritme´tica dos inteiros, e que pode ser demon-
strado por induc¸a˜o finita, e´ o seguinte teorema.
Teorema 1.5 (Algoritmo da Divisa˜o Euclidiana em N) Para cada nu´mero
natural n, e cada inteiro positivo d, existem nu´meros naturais q (quociente) e r
(resto) satisfazendo:
n = d · q + r e 0 ≤ r < d.
Ale´m disso, os naturais q e r, satisfazendo as condic¸o˜es acima, sa˜o u´nicos.
Prova da existeˆncia dos naturais q e r, por induc¸a˜o sobre n.
Mostraremos que, fixado um inteiro positivo d, para cada nu´mero natural n,
existem q e r nas condic¸o˜es enunciadas.
Se n = 0, basta tomar q = r = 0.
Seja k um nu´mero natural e suponhamos que existem q e r satisfazendo
k = dq + r e 0 ≤ r < d.
Enta˜o k + 1 = dq + (r + 1).
Como 0 ≤ r < d, temos r + 1 < d + 1, ou seja, r + 1 ≤ d. Se r + 1 < d,
tomamos q′ = q e r′ = r + 1 e teremos k + 1 = dq′ + r′, com 0 ≤ r′ < d.
Se r+ 1 = d, enta˜o k+ 1 = dq+ d = d(q+ 1) = dq′′+ r′′, onde q′′ = q+ 1
e r′′ = 0.
Portanto, pelo Primeiro Princ´ıpio de Induc¸a˜o Finita, para cada n ∈ N ,
existem q e r satifazendo n = dq + r, com 0 ≤ r < d.
Para a demonstrac¸a˜o da unicidade de q e r, veja problema 7, na sec¸a˜o 1.3.2.
Inteiros e Induc¸a˜o Finita 13
Observac¸a˜o 1.5 (Uma notac¸a˜o para o algoritmo da divisa˜o.) Se n e d sa˜o
nu´meros naturais, com d 6= 0, e se q e r sa˜o nu´meros naturais como no teorema
1.5, denotamos simbolicamente:
n d
r q
Neste caso, nessa divisa˜o euclidiana de n por d, n e´ o dividendo, d e´ o
divisor, q e´ o quociente e r e´ o resto.
Observac¸a˜o 1.6 O leitor podera´ verificar facilmente, atrave´sde alguns poucos
exemplos, que o teorema 1.5 na˜o e´ va´lido se d = 0.
Observac¸a˜o 1.7 No pro´ximo cap´ıtulo enunciaremos e provaremos um teorema do
algoritmo da divisa˜o na sua versa˜o mais geral para inteiros, na˜o necessariamente
naturais.
Uma segunda forma de prova por induc¸a˜o finita, por vezes utilizada, e´ esta-
belecida pelo seguinte teorema:
Teorema 1.6 (Segundo Princ´ıpio de Induc¸a˜o Finita.) Seja n0 um nu´mero
inteiro e suponhamos que a cada inteiro n, n ≥ n0, esta´ associada uma afirmac¸a˜o
A(n), a qual possui, para cada n, um valor lo´gico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condic¸o˜es 1 e 2 abaixo sejam verificadas:
1. A afirmac¸a˜o A(n) e´ verdadeira para n = n0;
2. Para cada inteiro k ≥ n0, se A(n) e´ verdadeira para n0 ≤ n ≤ k enta˜o
A(k + 1) e´ tambe´m verdadeira.
Enta˜o a afirmac¸a˜o A(n) e´ verdadeira para cada n ≥ n0.
Observac¸a˜o 1.8 O que difere o segundo princ´ıpio de induc¸a˜o finita do primei-
ro e´ a forma como e´ formulada a hipo´tese de induc¸a˜o. No primeiro princ´ıpio,
supomos que a asserc¸a˜o A(n) e´ verdadeira para n = k somente, enquanto que no
segundo, supomos A(n) va´lida para cada n satisfazendo n0 ≤ n ≤ k. Em ambos
os princ´ıpios, devemos provar que a hipo´tese de induc¸a˜o acarreta a validade de
A(n) para n = k + 1.
Antes de passarmos a` demonstrac¸a˜o dos dois princ´ıpios de induc¸a˜o finita, exibire-
mos um teorema cuja prova pode ser feita pelo segundo princ´ıpio.
Teorema 1.7 (Representac¸a˜o decimal de nu´meros naturais) Para cada in-
teiro n ≥ 1, existem nu´meros naturais a0, . . . , as, (s ≥ 0), com os “algarismos”
a0, . . . , as, tomados no conjunto {0, 1, 2, . . . , 9}, e as 6= 0, tais que
n =
s∑
i=0
ai · 10i = as10s + · · ·+ a0100
14 Estruturas Alge´bricas
Observac¸a˜o 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 divisa˜o euclidiana de k + 1 por 10,
k + 1 10
r q
obtemos um quociente q ∈ N e um resto r ∈ N, satisfazendo k + 1 = 10q + r,
com 0 ≤ r < 10, conforme o teorema 1.5.
Se q = 0, enta˜o k + 1 = r = a0, com a0 ∈ {0, 1, 2, . . . , 9}.
Se q > 0, enta˜o q ≤ k, pois se q > k, enta˜o k+1 = 10q+r > 10k+r ≥ 10k,
e assim k + 1 > 10k e enta˜o 1 > 9k ≥ 9, o que e´ imposs´ıvel.
Sendo enta˜o 1 ≤ q ≤ k, pela hipo´tese de induc¸a˜o,
q = bt · 10t + · · ·+ b0 · 100
para certos algarismos bt, . . . , b0, todos em {0, 1, 2, . . . , 9}.
Enta˜o,
k + 1 = 10q + r
= 10(bt · 10t + · · ·+ b0 · 100) + r
= bt · 10t+1 + · · ·+ b0 · 101 + r
com bt, . . . , b0 e r todos em {0, 1, 2, . . . , 9}.
Logo, pelo segundo princ´ıpio de induc¸a˜o finita, a representac¸a˜o decimal de
n e´ poss´ıvel para cada inteiro n ≥ 1.
1.3.1 Demonstrac¸a˜o dos Princ´ıpios de Induc¸a˜o Finita
Veremos agora que ambos os princ´ıpios de induc¸a˜o finita sa˜o consequ¨eˆncias do
Princ´ıpio do Menor Inteiro (teorema 1.2, item 1).
Prova do Primeiro Princ´ıpio da Induc¸a˜o Finita.
Suponhamos que estejam estabelecidas as hipo´teses do teorema 1.4 e que
as condic¸o˜es 1 e 2 la´ enumeradas estejam ocorrendo.
Suponhamos que, ale´m disso, contrariamente a` tese do teorema, exista um
inteiro s ≥ n0 tal que a afirmac¸a˜o A(s) e´ falsa.
Inteiros e Induc¸a˜o Finita 15
Seja S = {n ∈ Z | n ≥ n0 e A(n) e´ falsa}.
S e´ na˜o vazio, pois s ∈ S.
Sendo S ⊂ Z, e limitado inferiormente por n0, pelo Princ´ıpio do Menor
Inteiro, proposic¸a˜o 1.2, item 1, S possui um menor elemento s0.
Como n0 ≤ s0 e A(n0) e´ verdadeira, temos n0 < s0, e enta˜o n0 ≤ s0 − 1.
Seja k = s0−1. Enta˜o 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 enta˜o A(k + 1) verdadeira.
Pore´m k + 1 = s0 e A(s0) e´ falsa.
Assim, temos uma contradic¸a˜o 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 Induc¸a˜o Finita.
Salvo ligeiras modificac¸o˜es, a prova do Segundo Princ´ıpio da Induc¸a˜o Finita,
teorema 1.6, e´ ideˆntica a` prova apresentada acima.
A u´nica diferenc¸a se da´ nas u´ltimas linhas da demonstrac¸a˜o.
Considere S e s0 tal como na demonstrac¸a˜o do primeiro princ´ıpio de induc¸a˜o.
Suponha agora que esta˜o satisfeitas as condic¸o˜es 1 e 2 da hipo´tese do teorema
1.6.
Tal como na demonstrac¸a˜o acima, teremos n0 ≤ s0 − 1. Como s0 e´ o
menor inteiro n com A(n) falsa, temos enta˜o A(n) verdadeira para cada n tal
que n0 ≤ n ≤ s0 − 1. Tomando k = s0 − 1, temos enta˜o A(n) verdadeira para
cada n satisfazendo n0 ≤ n ≤ k. Pelo item 2 da hipo´tese, isto acarreta A(k + 1)
verdadeira. Mas k + 1 = s0 e novamente temos uma contradic¸a˜o.
1.3.2 Problemas Complementares
1. ©^. . Mostre, por induc¸a˜o sobre n, que, se n ≥ 1 enta˜o:
(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 tambe´m 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 nu´meros reais) Para cada nu´-
mero real positivo a e cada inteiro n ≥ 0, tem-se (1 + a)n ≥ 1 + na.
16 Estruturas Alge´bricas
(c) ©. . Para cada inteiro m, m3 −m e´ divis´ıvel por 3.
(d) ©. . 42n+1 + 3n+2 e´ um mu´ltiplo 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 “demonstrac¸a˜o” de que 1 = . . . = n para
cada inteiro n ≥ 1:
A afirmac¸a˜o e´ verdadeira se n = 1.
Supondo que ela e´ va´lida para n = k, com k ≥ 1, temos 1 = . . . = k, e
portanto 1 + 1 = . . . = k + 1.
Por hipo´tese de induc¸a˜o, 1 = 2 = . . . = k. Como tambe´m 2 = . . . = k + 1,
por transitividade teremos 1 = 2 = . . . = k + 1.
Assim, pelo primeiro princ´ıpio de induc¸a˜o finita, 1 = . . . = n, para cada
inteiro n ≥ 1.
4. ©^. . Para cada a ∈ Z e cada n ∈ N, define-se a poteˆncia de base a e
expoente n (ou n-e´sima poteˆncia de a) como sendo o inteiro denotado por
an e definido pelas leis:
(i) Se n = 0, enta˜o an = a0 = 1;
(ii) Para cada k ≥ 0, ak+1 = ak · a.
A partir das duas leis definidas acima, prove, por induc¸a˜o sobre n, que se m
e n sa˜o nu´meros naturais e a e´ um inteiro, enta˜o
(a) am+n = am ·an [Sugesta˜o: Assuma que m e´ um nu´mero natural fixado
e fac¸a a prova por induc¸a˜o sobre n];
(b) (am)n = amn;
(c) Se a 6= 1 enta˜o 1 + a+ a2 + · · ·+ an = an+1−1
a−1
5. Sendo n e p nu´meros naturais, com n ≥ p, define-se o nu´mero 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 relac¸a˜o de Stifel: sendo n e p nu´meros naturais, se n ≥
p+ 1, (
n
p
)
+
(
n
p+ 1
)
=
(
n+ 1
p+ 1
)
(b) ©. . Prove a fo´rmula chamada binoˆmio de Newton: sendo a e b nu´meros
reais e n um nu´mero natural, n ≥ 1,
(a + b)n =
∑n
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¸a˜o Finita 17
(c) ©. . Prove que, sendo n ≥ p ≥ 1, (n
p
)
e´ o nu´mero de subconjuntos
(“combinac¸o˜es”), com p elementos, de um conjunto contendo n ele-
mentos. [Sugesta˜o: Fac¸a a demonstrac¸a˜o por induc¸a˜o sobre n, usando
o primeiro princ´ıpio de induc¸a˜o finita e a relac¸a˜o de Stifel.]
6. ©_. . A sequ¨eˆncia de Fibonacci e´ umexemplo de uma sequ¨eˆncia de inteiros
definida indutivamente. Ela e´ definida como a0, a1, a2, . . ., sendo
a0 = 0, a1 = 1 e, an+1 = an + an−1 para cada n ≥ 0
Assim, ela comec¸a como 0, 1, 1, 2, 3, 5, 8, 13, . . .
(a) Prove por induc¸a˜o sobre n que
an =
[(1 +
√
5)/2]n − [(1−√5)/2]n√
5
[Sugesta˜o: Use o segundo princ´ıpio da induc¸a˜o. Provavelmente lhe sera´
u´til saber que (1+
√
5
2
)2 = 3+
√
5
2
]
(b) (para experts em Ca´lculo I) Mostre que lim
n→∞
(an+1
an
) = φ = 1+
√
5
2
. (Ja´
ouviu falar deste nu´mero, a “raza˜o a´urea”?)
7. ©. . Mostre que os nu´meros naturais q (quociente) e r (resto) no enunciado
do teorema do algoritmo da divisa˜o em N (teorema 1.5, pa´gina 12), sa˜o
u´nicos. [Sugesta˜o: mostre que sendo n e d nu´meros naturais, com d 6= 0, se
n = dq1+r1 = dq2+r2 para certos naturais q1, q2, r1, r2, com 0 ≤ r1, r2 < d,
enta˜o d|q1 − q2| = |r1 − r2| < d e logo |q1 − q2| = 0.]
8. ©_. . (Para experts) Mostre que os algarismos a0, . . . , as utilizados na repre-
sentac¸a˜o decimal de um nu´mero natural n sa˜o determinados de maneira
u´nica. [Sugesta˜o: Mostre que se a0 + a110 + . . . + an10
n = 0, sendo os
coeficientes a0, a1, . . ., an, todos tomados no conjunto de inteiros {−9,−8,
. . . , −1, 0, 1, 2, . . . , 9}, enta˜o an10n = −a0 −a110 − . . . −an−110n−1 ⇒
|an|10n ≤ |a0|+ |a1|10 + . . .+ |an−1|10n−1 ≤ 9 + 9 · 10 + . . .+ 9 · 10n−1 =
10n − 1 < 10n ⇒ |an|10n < 10n ⇒ an = 0. Consequ¨entemente, se
a0 + a110 + . . .+ an10
n = 0, e a0, a1, . . ., an, esta˜o todos no conjunto de
d´ıgitos {−9,−8, . . . ,−1, 0, 1, 2, . . . , 9} enta˜o an = an−1 = . . . = a0 = 0].
9. ©^. . Considere a igualdade
2 + 4 + 6 + · · ·+ 2n = n2 + n+ 100
Mostre que tal igualdade e´ falsa. Mostre pore´m que, sendo k um inteiro,
supondo-a verdadeira para n = k podemos demonstrar que tambe´m e´ ver-
dadeira para n = k + 1.
10. ©^. . Considere a afirmac¸a˜o
n2 − n+ 5 e´ primo
18 Estruturas Alge´bricas
(Um inteiro p e´ primo se p 6= 0, p 6= ±1, e seus u´nicos fatores inteiros sa˜o
±1 e ±p)
Mostre que essa afirmac¸a˜o e´ verdadeira se n ∈ {1, 2, 3, 4}, mas e´ falsa se
n = 5.