Notas de Álgebra 1

Sheila Campos Chagas

Departamento de Matemática
Universidade de Brası́lia - UNB

Copyright © 2024 by Sheila Campos Chagas

Todos os direitos reservados.

14 de maio de 2024
 Sumário

Introdução 1

1 Introdução à lógica matemática 1

1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Sentença, Conectivos e Modificador. . . . . . . . . . . . . . . . . . . . 1
1.2.1 Proposições Compostas Imediatas . . . . . . . . . . . . . . . . 3
1.2.2 Tabelas-Verdade . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Tautologia, implicação e equivalência . . . . . . . . . . . . . . . . . . 10
1.4 Raciocı́nio Dedutivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5 Contradição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.6 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.7 “De quem você está falando”? . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Argumentos lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.9 Indução Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Conjuntos 27
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Elementos da teoria dos conjuntos . . . . . . . . . . . . . . . . . . . . 27
2.3 Operações com Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Conjunto das Partes e Produto Cartesiano . . . . . . . . . . . . . . . 36
2.5 Famı́lias de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6 Para saber mais... . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3 Funções 43
3.1 Conceito e Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

i
SUMÁRIO ii

3.2 Composição de Funções . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.3 Imagens diretas e Inversas . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 Funções Bijetoras e Inversas . . . . . . . . . . . . . . . . . . . . . . . 47
3.5 Funções Inversas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.6 Relação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7 Relação de equivalência . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.8 Partição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.9 Ordem Parcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.9.1 Reticulado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.10 Cardinalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4 Os números inteiros 67
4.1 Axiomas para o conjunto dos números inteiros . . . . . . . . . . . . . 67
4.2 Princı́pio da Boa Ordenação . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Aritmética dos inteiros, divisibilidade e MDC . . . . . . . . . . . . . 76
4.4 O Teorema Fundamental da Aritmética . . . . . . . . . . . . . . . . . 90
4.5 Aritmética Modular . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.6 Princı́pio de Indução Finita . . . . . . . . . . . . . . . . . . . . . . . 108

Referências Bibliográficas 116

 CAPÍTULO 1

Introdução à lógica matemática

1.1 Introdução
A lógica desempenha um papel essencial no pensamento humano. Os cientistas
por exemplo usam a lógica para tirar conclusões de experiências, os juı́zes usam-na
para deduzir consequências da lei e os matemáticos usam-na para provar teoremas.
Neste capı́tulo desenvolveremos um pouco sobre lógica matemática de modo um
tanto rápido, estas noções contidas aqui serão utilizadas na construção dos capı́tulos
seguintes. O leitor interessado em aprofundar seus estudos lendo as referências
contidas no fim doi capı́tulo. Faremos como a maioria dos matemáticos, o ponto de
vista ingênuo em relação à teoria dos conjuntos. Assumiremos que o que se entende
por conjunto de objetos é intuitivamente claro e prosseguiremos com base nisso
sem analisar mais profundamente o conceito. Tal análise pertence propriamente aos
fundamentos da matemática e à lógica matemática, e este curso não tem o objetivo
de discutir estes assuntos.

1.2 Sentença, Conectivos e Modificador.

O estudo da lógica objetiva distinguir os argumentos válidos dos não válidos. Assim,
o próposito deste capı́tulo é fazer o leitor a entender os princı́pios e métodos
usados em cada passo de uma demonstração.
. A lógica surge na linguagem comum com afirmações como “se Masha estudar

1
Seção 1.2 • Sentença, Conectivos e Modificador. 2

muito‘Álgebra 1, ela passará no curso” ou “se um número inteiro n é divisı́vel por

15, então n é divisı́vel por 3. Em cada caso, o objetivo é afirmar que se uma
determinada afirmação é verdadeira, ou se então uma outra afirmação também deve
ser verdadeira.
No discurso diário encontramos com frequência sentenças declarativas (ou
afirmações como as dadas acima) as quais foram formadas conectando-se outras
sentenças com as palavras e, ou, se · · · então, e se, . . . e somente se, . . . , ou
então modificando-se uma dada afirmação com a palavra não. Os quatro primeiros
conjuntos de palavras são comumente chamados de conectivos, enquanto a palavra
não é chamada de modificador. Uma sentença que foi modificada pela palavra
“não” é dita a negação da sentença original. Assim, o ponto de partida é o termo
Proposição que é uma afirmação, declaração ou asserção lógica que pode assumir
os valores verdadeiro ou falso, não é necessário saber de antemão se a afirmação
é verdadeira ou falsa, o que uma proposição não pode ser é ambos, isto é não po-
demos ter ambiguidade. É claro, assumiremos que isto admite que uma definição é
ela própria uma declaração.
Por sentença primitiva ou proposição simples, entendemos uma proposição
constituida de um nome (sujeito) e um predicado, sem a presença de conectivos ou
do modificador. E o elemento fundamental de uma linguagem.
Algumas vezes a validade ou a falsidade de uma afirmação é chamada de o seu
valor boleano. Determinar se uma proposição é verdadeira ou falsa pode ser:
fácil, um tanto difı́cil e até mesmo impossı́vel chegar a uma conclusão. segue alguns
exemplos de declarações.
Exemplos de proposições simples são:

Exemplo 1.2.1. (1) Vou de Taxi.

(2) O número 927 é primo.
(3) Está nevando.
(4) Não existe vida inteligente em Marte.

A afimação 1 é verdadeira e a 2 é falsa, pois 927 é divesı́vel por 3 e por 103,

quanto a afimação 4 podemos ter dúvidas. E a veracidade ou falsidade da declaração
3, depende das condições meterológicas do momento e o lugar que esta declaração
for feita.
Cap. 1 • Introdução à lógica matemática 3

As seguintes frases não são proposições, pois não tem sentido questionar se elas
são verdadeiras ou falsas:

Exemplo 1.2.2. (1) Conheça a Chapada dos Viadeiros.

(2) Guilherme esta estudando.
(3) Bom fim, de semana.

O C álculo Proposicional consiste em analisar a estrutura de uma proposição

composta (isto é , uma proposi,cão na qual aparece um ou mais conectivos ou o
modificador) em termos das proposições simples. Esta análise é meramente formal
(simbólica), de modo que, por praticidade, podemos expressar nossas proposições
através de sı́mbolos. É comum o uso de letras latinas minúsculas p, q, r, etc, para
indicar proposições simples, enquanto as proposições compostas são designadas por
letras latinas maiúsculas P , Q, R, etc. Pode ser conveniente destacar as proposições
componentes de uma sentença a P ; neste caso escrevemos P (p1 , p2 , . . . , pn ).

1.2.1 Proposições Compostas Imediatas

Cada conectivo pode ser visto como um operador no conjunto das proposições ; eles
são operadores binárias, no sentido que, aplicando-se um conectivo a um par de
proposições p, q, produzimos uma terceira P (p, q) (o conceito preciso de operação
binária é introduzido nas seções). Destacamos a seguir cada um dos conectivos.

conjunção: A proposição obtida de duas outras pelo conectivo “e” é dita a

conjunção das duas proposições. A conjunção das proposições p e q é simbolizada
por p ∧ q.

disjunção : A disjunção das proposições p e q é a proposição obtida destas

através do conectivo “ou”; simbolizada por p ∨ q, a disjunção para nós é consirerada
não exclusiva, isto é, quando aplicada às proposições p, q, nenhuma das sentenças
componentes é excluida. Isto significa que vale p, ou q, ou ambas!

condicional: Aplicada às proposições p e q, nesta ordem, produz a proposição

(condicional) se p então q, simbolizada por p → q. Aqui p é chamada de antecedente
e q é a consequente. Outras sentenças com o mesmo significado da condicional “se
p então q” são, por exemplo, p é condição suficiente para q, ou q, d esde que p, ou
ainda q é condição necessária para p.
Seção 1.2 • Sentença, Conectivos e Modificador. 4

bicondicional: Como o termo sugere, a bicondicional é a sentença obtida de

duas outras com o conectivo “se, e somente se”; usamos o sı́mbolo p ↔ q para
indicar a bicondicional “p se, e somente se, q”. Esta é, de fato, uma condicional
de “mão-dupla”, significando se p, então q e se q, então p ou ainda, q é condição
necessária e suficiente para p.

negação : usamos o sı́mbolo ¬ para negar uma proposição . Assim, a negação

da proposição p é indicada por ¬p. Note que, ao contrário dos conectivos que são
operadores binários, o modificador ¬ é um operador unário.
Podemos combinar muitas declarações em uma única afirmação de diversas for-
mas, mas as cinco mais usuais são as seguintes:

• “e” , representado pelo sı́mbolo ∧;

• “ou” , representado pelo sı́mbolo ∨;

• “implica” , representado pelo sı́mbolo →;

• “se, e somente se”, representado pelo sı́mbolo ↔.

• “não ” , representado pelo sı́mbolo ¬;

Também usamos o “ou exclusivo” por ∨ (este está definido na tabela abaixo).
Mas podemos definir o “ou” exclusivo e o ↔ em termos da negação ¬ e dos outros
três conectivos ∨, ∧ e → como veremos adiante.
Resumindo tudo, podemos introduzir letras “p00 , “q 00 , “r00 , etc, para designar nos-
sas proposições simples e certos sı́mbolos especiais para indicar os conectivos e o
modificador. Juntando agora alguns parênteses “(· · · )00 para as necessárias pon-
tuações, temos todos os ingredientes para expressar uma proposição composta sim-
bolicamente. Por exemplo, a sentença

Se o Corinthians ou o Flamengo ganhar então o Atético será o campeão

se, e somente se o Guaranı́ perder e o Internacional não empatar,

pode muito bem ser simbolizada pela expressão

(c ∨ f ) → (a ↔ (g ∧ ¬i)),

onde os sı́mbolos utilizados indicam as seguintes proposições simples:

Cap. 1 • Introdução à lógica matemática 5

c: o Corinthians ganha;

f: o Flamengo ganha;

a: o Atlético será campeão;

g: o Guarani perde;

i: o Internacional empata.

Como em toda linguagem, existem também aqui certas regras para pontuação
que evitam o uso demasiado de parenteses. Convenciona-se que o ↔ é o conectivo
mais forte (isto é, que tem maior alcance), seguido depois pelo condicional →. Os
sı́mbolos ∨ e ∧ vêm a seguir, com igual alcance, e por útimo o modificador ¬, o qual
atinge apenas a proposição mais próxima. Assim,

p∧q →r significa (p ∧ q) → r;

p→q∨r significa p → (q ∨ r);

p↔q→r significa p ↔ (q → r);

¬p ∧ q significa (¬p) ∧ q,

de modo que nosso exemplo acima pode ser reescrito na forma

c ∨ f → (a ↔ g ∧ ¬i).

1.2.2 Tabelas-Verdade
Quando aplicamos os conectivos e o modificador a determinadas proposições ob-
temos novas proposiições, as quais no nosso entender são sentenças declarativas,
suscetı́ves portanto de atribuiição de um e apenas um valor-verdade V ( verda-
deira) ou F (falsa), de acordo com os correspondentes valores-verdade atribuı́dos
às sentenças componentes. Dada então a expressão simbólica de uma determinada
proposição composta P (p1 , . . . , pn ), podemos fazer uso de um dispositivo prático,
chamado tabela-verdade, para tabular os valores de P de acordo com os valores de
p1 , . . . , pn . A tabela-verdade de P (p1 , . . . , pn ) tem assim n+1 colunas, onde usamos
as n primeiras para atribuir os possı́veis valores das proposições p1 , . . . , pn e na última
calculamos os correspondentes valores de P . Quando a expressão da proposição P é
muito longa, pode ser conveniente calcular tabelas parciais, ”quebrando-se”P como
Seção 1.2 • Sentença, Conectivos e Modificador. 6

composta de outras que aparecem de acordo com a pontuação (parênteses) utilizada

na sua expressão. Os valores-verdade dessas compostas parciais podem ser compu-
tados na mesma tabela de P , bastando para isso acrescentar-se uma nova coluna
para cada tal proposição parcial.
Em vista disso, tudo o que precisamos para computar a tabela-verdade de uma
dada proposição é saber como atribuir os valores-verdade das compostas imediatas.
Isto é feito quase que ”por decreto”, se bem que para tanto levamos em conta o
significado dos conectivos e do modificador na linguagem cotidiana.
Assim, a negação de uma proposição verdadeira é uma proposição falsa, enquanto
a negação de uma falsa é verdadeira.
Por exemplo: seja p uma proposição. A negação da proposição p, é denotada
por ¬p, é lida como “não p”ou como “a negação de p”. A afirmação ¬p é verdadeira
quando a proposição p é falsa, e ela é falsa quando p é verdadeira. Por exemplo,
seja p a proposição “ Xadrez é um jogo fácil”. Então sua negação é ¬p representa
“Xadrez não é um jogo fácil”.
Com este exemplo em mente a tabela- verdade para o modificador ¬ fica.

p ¬p
V F
F V
Tabela 1.2.1

onde as letras V e F signficam “verdadeiro” e “falso”, respectivamente. Na primeira

coluna da tabela (4.6.1), listamos as duas possı́veis possibilidades para a proposição
p. Cada linha em uma tabela verdade representa um caso que deve ser considerado,
e claramente, nesta situação bastante simples, existem somente dois casos. A Tabela
(4.6.1) nos diz o valor verdade de ¬p em cada caso.

O sı́mbolo p ∧ q tem significado de “p e q”, ou conjução de “p e q”. Isto quer

dizer que se p é a proposição “o carro é azul”e q é a proposição “a casa é vermelha”.
Então a conjução “p ∧ q” significa “o carro é azul e a casa é vermelha”. Na conjução
cada proposição é dita uma componente. Assim, as possibilidades de “p ∧ q” são
4 (= 2 × 2 ) possibilidades e elas sãop chamadas de possibilidades lógicas, como
podemos ver na Tabela (1.2.2).
Pelo significado da conjunção ∧, convenciona-se que a proposição composta p ∧ q
é verdadeira quando, e somente quando, p e q são ambas verdadeiras. Por exemplo,
Cap. 1 • Introdução à lógica matemática 7

Se r é a proposição “o número 19 é primo” e s simboliza a sentença a “a lua é

um planeta” então, muito embora 19 seja de fato um número primo, a proposição
composta r ∧ s é falsa. Na conjução cada proposição é dita uma componente.
Assim, as possibilidades de “p ∧ q” são 4 (= 2 × 2 ) possibilidades e elas sãop
chamadas de possibilidades lógicas, como podemos ver na Tabela (1.2.2).
Na lı́ngua portuguesa existe uma ambiguidade com o uso do “ou” (∨), onde o
usamos com sentido inclusivo ou exclusivo. A proposição “Você quer beber água ou
café?” indica que você deve escolher água ou café, e não exclui a opossibilidade de
escolher ambos. Mas, a proposição “Jorge casará com Maria ou Cristina”, a palavra
“ou” significa que apenas uma das duas casará com Jorge. Na matemática e na
lógica não podemos permitir ambiguidades Portanto, devemos nos decidir sobre o
significado da palavra “ou” ∨.
O sı́mbolo p ∨ q tem significado de “p ou q”, ou disjunção de “p e q”. Assim, o
conectivo ∨ pode ser colocado entre duas proposições quaisquer p e q para formar a
proposição composta p ∨ q.. Os valores verdade de p ∨ q são dados na Tabela (1.2.3).
Portanto, ∨ é definido como sendo o “ou” inclusivo. Por outro lado, pelo caráter não
exclusivo da disjunção ∨, fica convencionado que a proposição p ∨ q é falsa quando
e apenas quando p e q forem ambas falsas. Logo as tabelas-verdade são:

p q p∧q
V V V
V F F
F V F
F F F
Tabela 1.2.2: Conjunção

p q p∨q
V V V
V F V
F V V
F F F
Tabela 1.2.3: Disjunção

Note que a conjunção de p e q é verdadeira apenas quando as duas componentes

são ambas verdadeiras ((veja Tabela (1.2.2)). Em contrate com a conjunção, a
disjunção é falsa quando e apenas quando as duas componentes são falsas, veja
Tabela (1.2.3).
Seção 1.2 • Sentença, Conectivos e Modificador. 8

O conectivo → é chamado condicional e podemos colocar entre duas proposições

p e q para formar a proposição composta p → q( lê-se: “se p então q). Por definição,
a proposição p → q é equivalente a proposição ¬(p ∧ ¬q) conforme podemos ver na
Tabela (1.2.2).

Vejamos o seguinte exemplo: que motiva esta definição. Seja p a delaração “ Eu

sou um milionário” e q a declaração “ Eu comparei um iate”. A afimação que
p → q é verdadeira, pois se eu fosse um milionário, eu realmente poderia comprar
um iate. Agora, quando podemos considerar tal proposição falsa? Claramente p → q
é falsa se eu sou um milionário, mas eu não compro o iate, e apenas neste caso. Mas
se eu não sou e não posso comprar o iate, então p e q são ambas falsas. Isto dar
suporte a ideia que F → F é verdade. Agora seja q a declaração “Eu comprarei um
sorvete. Eu afirmo que se p então q é verdade. O problema é, eu planejo comprar
sorvete de qualquer jeito, isto é, q é verdade e não importa o que p seja, e isto
apoia a idéia de que “’F → V é verdadeiro. Em particular, devemos ter cuidado
com a elaboração das conclusões a partir de suposições falsas, porque elas
implicam em afimações verdadeiras e falsas.
Conforme a definição de p → q, o significado da proposição condicional afasta-se
radicalmente do nosso uso ordinário de “Se p então q” Na nossa linguagem ordinária,
uma sentença da forma “Se p então q” é considerada como querendo dizer que q é
verdadeira sempre que p é verdadeira. Portanto os casos em que p é falsa não
precisam ser considerados.
Por exemplo, considere a proposição “Se os russos elegeram Trump, então chi-
neses elegeram Biden” é considerada sem sentido, pois ambas as componentes são
falsas. Consequêntemente, no uso ordinário não se questiona se uma proposição
componente é verdadeira. Ao criar a linguagem formal, o lógico deseja designar
um valor verdade a p → q para cada uma das quatro possibilidades lógicas, muito
embora dois dos casos pareçam ser sem sentido em nossa linguagem ordinária. Por
várias razões, que aparecerão no tempo devido, os lógicos decidiram-se pela definição
adotada aqui. Portanto, em nossa linguagem formal, p → q é verdadeira em todos os
casos exceto no caso em que q é faso (veja Tabela (1.2.2)). Como consequência desse
acerto, seremos capazes de demonstrar alguns teoremas utéis bastante simples, cujas
demonstrações, sem tal acerto, seriam desajeitadas ou muito difı́cies. Introduzimos
agora o último dos cinco conectivos mais comuns, um que aparece frequêntemente
nos enunciados de teoremas matemáticos.
Cap. 1 • Introdução à lógica matemática 9

p q p↔q p q p ∨q
V V V V V F p ¬p
V F F V F V V F
F V F F V V F V
F F V F F F
Introduzimos agora o último dos cinco conectivos mais comuns, um que aparece
frequentemente nos enunciados (proposições de teoremas matemáticos). O conectivo
↔ é chamado o bicondicional e pode ser colocado entre duas proposções p e q para
formar a proposição composta p ↔ q (lê-se: “p se e somente se q”).
A proposição p ↔ q é equivalente a proposição (p → q) ∧ (q → p), e os valores
verdade de p ↔ q são dados na Tabela (1.2.2). Da tabela verdade, observamos
que p ↔ q é verdadeira se ambas as componentes são verdadeiras ou ambas as
componentes são falsas. Em qualquer outro caso a proposição p ↔ q é falsa.
Note que ↔ é análogo para o sinal de igual =.

Exercı́cio 1.2.1. O que você, logicamente pode concluir a partir do seguinte

provérbio chinês?

Se há luz na alma,

Então, haverá beleza na pessoa,
Se houver beleza na pessoa,
Então, haverá harmonia no casa,
Se houver harmonia na casa,
Então, haverá ordem na nação,
Se houver ordem na nação,
Então, haverá paz no mundo.

Pelo que observamos, com as tabelas acima podemos construir a tabela-verdade

para qualquer proposição composta* . Por exemplo, consideremos dadas as pro-
posições simples

p: Hoje vou ao cinema;

q: Hoje faz calor;

r: Hoje tenho visita;

*
Obtida a partir de um dado conjunto inicial de proposições simples, pelo uso dos conectivos
e do modificador
Seção 1.3 • Tautologia, implicação e equivalência 10

que podem ser usadas para expressar a sentença a se hoje fizer calor e eu não tiver
visita então vou ao cinema ou, simbolicamente, (q ∧ ¬r) → p, cuja tabela-verdade
é:

p q r q ∧ ¬r (q ∧ ¬r) → p
V V V F V
V V F V V
V F V F V
V F F F V
F V V F V
F V F V F
F F V F V
F F F F V
Tabela 1.2.4

Observe que a tabela-verdade de uma proposição composta por n proposições

simples apresenta 2n linhas.

1.2.3 Exercı́cios
1. Construir a tabela-verdade para a proposição ¬(p ∧ q) ↔ ¬p ∨ ¬q.

2. Computar a parte da tabela-verdade para a proposição (c ∨ f ) → (a ↔ g ∧ ¬i)

na hipótese de f e g assumirem os valores-verade V e F respectivamente.

3. Verifique que a tabela-verdade da proposição (¬p ∨ q) ↔ (p → q) apresenta

apenas o valor-verdade V na úlltima coluna.
4. Encontre as proposições simples que compoem a sentença

S e os preços são altos então os salários são altos e há inflação se, e
somente se, não há controle de preços

e reescreva-a simbolicamente, utilizando a convenção adotada para adoção de

parênteses. Em seguida, compute a tabela-verdade.

1.3 Tautologia, implicação e equivalência

Na seguinte Tabela (1.3.1) apresentaremos proposições compostas pelo uso dos co-
nectivos.
Cap. 1 • Introdução à lógica matemática 11

declaração notação terminologia

negar p ¬p negação
peq p∧q conjunção
p ou q p∨q disjunção
p implica q p→q condicional
¬q implica ¬p ¬q → ¬p contra positiva de p → q
p se e somente se q p↔q bicondicional
ou p ou q (não ambos) p ∨q ou exclusivo
Tabela 1.3.1

A contrapositiva é a essência de qualquer argumento de demonstração por con-

tradição, ou redução ao absurdo.

Definição 1.3.1. Quando duas proposições P e Q, simples ou compostas, tem os

mes mos valores verdade em cada uma de todas as possibilidades lógicas, dizemos que
P é logicamente equivalente ou simplesmente equivalente a Q, e escrevemos P ≡ Q.

Assim, de modo breve duas proposições são logicamente equivalentes desde que
tenham a mesma tabela verdade. Verifique a seguinte equivalência lógica

Exercı́cio 1.3.1. p ∨ q ≡ ¬(¬p ∧ ¬q).

Mesmo que duas proposições equivalentes sejam consideradas como a mesma, do

ponto de vista da lógica matemática, prefirimos a proposição mais simples “p ou q”
em vez da proposição equivalente mais complicada “Não é verdade que vale nem p
e nem q”
Lembremos que declaração é chamada primitiva se não pode ser expressa em
termos de outrar mais simples. Vejamos uma vez mais a tabela verdade para a
proposição p ∨ ¬p:

p ¬p p ∨ ¬p
V F V
F V V
Vejamos que a proposição p ∨ ¬p é verdadeira em todos os casos, isto é, em todas
as possibilidades lógicas. Esse tipo de proposição receberá o seguinte nome especial.

Definição 1.3.2. Uma proposição é chamada uma tautologia quando é verdadeira

em cada uma das possibilidades lógicas, independentemete dos valores lógicos de suas
declarações primitivas.
Seção 1.3 • Tautologia, implicação e equivalência 12

O leitor que resolveu corretamente o exercı́cio (??), verificou que a tabela-verdade

da proposição (p → q) ↔ (¬p ∨ q) tem, de fato, apenas o valor V na última
coluna, isto é , a proposição é verdadeira independentemente dos valores-verdade
das proposições componentes. Assim, este exerçicio nos fornece mais um exemplo de
tautologia. Ao contrário, quando aparece apenas o valor F , dizemos que a proposição
é logicamente falsa ou uma contradição. Claramente, P é uma tautologia se, e
somente se, ¬P é uma contradição.
Sejam p e q proposições, compostas ou simples. Se a proposição condicional
p → q é uma tautologia, então a proposição é chamada uma implicação e é denotada
por p ⇒ q, e leremos p implica q.
Assim as seguintes proposições condicionais são tautologias:

(1) p → p.

(2) p → (p ∨ q).

(3) p ∧ q → q ∧ p.

(4) p → p ∧ p.

(5) p ∧ q → q.

Entretanto (p ∨ q) → (p ∧ q) não é uma tautologia.

Uma proposição pode ser testada mecanicamente para determinar se é ou não
uma tautologia por meio de uma tabela de verdade, onde todas as possibilidades
são consideradas.
Cada linha em uma tabela verdade corresponde a uma combinação de valores
verdade de seus componentes primitivos. Escrevemos as posssibilidades para os
valores verdade das declarações primitivos p e q sob esses sı́mbolos e os valores
verdadeiros para cada sub-proposição sob o sı́mbolo do operador relevante. A última
linha geralmente não é incluı́da. É fornecido aqui simplesmente para mostrar a
ordem em que as colunas foram preenchidas. Essa ordem pode ser um pouco variada.
Vamos escrever “P é V” para dizer que P é uma tautologia (a notação |= P é
também usada). Para indicar que P é F uma contradição escrevemos “P é F”.
No que segue vamos supor a existência de um dado conjunto inicial S de pro-
posições simples (as quais são também chamadas fórmulas simples), e considerar
a totalidade PS das proposições que obtemos a partir dessas através dos conecti-
vos e do modificador. Tais proposições são às vezes chamadas de fórmulas. Na
Cap. 1 • Introdução à lógica matemática 13

p q p→q p ∧ (p → q) p ∧ (p → q) → q
V V V V V
V F F F V
F V V F V
F F V F V
Tabela 1.3.2

q r s r∨s r∨s→q (r ∨ s) ∧ (r∨ → q) (r ∨ s) ∧ (r ∨ s → q) → q

V V V V V V V
V V F V V V V
V F V V V V V
V F F F V F V
F V V V F F V
F V F V F F V
F F V F V F V
F F F F V F V
Tabela 1.3.3

lógica ou na matemática os “teoremas” significam proposições verdadeiras, e uma

“demonstração” de um teorema justifica a sua validade.

Teorema 1.3.1 (Princı́pio da Substituição ). Se P = P (p1 , . . . , p, . . . , pn ) é V e se

P ∗ = P (p1 , . . . , Q, . . . , pn ) é a proposição obtida de P substituindo-se pela proposição
Q todas as ocorrências de p em P , entãoP ∗ é V.

Demonstração. A cada escolha de valores-verdade das componentes simples de P ∗ ,

obtemos um valor-verdade para Q (note que as componentes simples de Q estão entre
aquelas de P ∗ ) e um valor-verdade para P ∗ . Ora, com essa particular combinação
de valores atribuidos às componentes simples de P , vemos que os valores de P e P ∗
coincidem. Mas como P é V, segue-se que P ∗ é V.

Exemplo 1.3.1. Seja P (p, q) a proposição p∧(p → q) → q, a qual é uma tautologia.

Substituindo p pela proposição r ∨ s, o teorema 1.3.1 garante que (r ∨ s) ∧ (r ∨ s →
q) → q é uma tautologia. As tabelas 1.3.2 e 1.3.3 ilustram melhor a situação.

Definição 1.3.3. Dizemos que duas proposições P e Q são equivalentes quando

elas têm a mesma tabela-verdade* .

Por exemplo, as proposições ¬(p ∨ q) e ¬p ∧ ¬q são equivalentes. Usamos a

notação P ⇐⇒ Q para indicar o fato que P e Q são equivalentes.
*
Sem perda de generalidade podemos admitir que as proposições simples envolvidas em P e Q
são as mesmas.
Seção 1.3 • Tautologia, implicação e equivalência 14

É com base neste conceito de equivalência que freqüentemente nos expressamos

com uma frase do tipo: “dizer i sto equivale a dizer aquilo”.
Segue imediatamente da definição 1.3.3 o

Teorema 1.3.2. Duas proposições P e Q são equivalentes se, e somente se, a

bicondicional P ↔ Q é uma tautologia.

Note que a bicondicional P ↔ Q é uma proposição , enquanto a equivalência

P ⇐⇒ Q expressa uma relação entre duas proposições. Uma outra relação entre
duas proposições é obtida através do conceito de implicação lógica.

Definição 1.3.4. Dizemos que P implica logicamente Q, em sı́mbolos P =⇒

Q, se Q for verdadeira pelo menos para qualquer atribuição de valores-verdade às
componentes simples que tornam P verdadeira.

É também consequência direta da definição acima o

Teorema 1.3.3. Dadas as proposições P e Q, tem-se que P =⇒ Q se, e somente

se, a condicional P → Q é uma tautologia.

Teorema 1.3.4. Sejam p e q duas proposições quaisquer. Então

(1) Lei da Adição (Ad.): p ⇒ p ∨ q.

(2) Leis de Simplificação (Simp.): p ∧ q ⇒ p, p ∧ q ⇒ q.

(3) Silogismo Disjuntivo (S.D.): (p ∨ q) ∧ ¬p ⇒ q.

Demonstração. Faça os itens 1 e 2 como exercı́cios. Abaixo colocamos a uma tabela

verdade simplificada para (p ∨ q) ∧ ¬p → q.

p∨q ¬p (p ∨ q) ∧ ¬p (p ∨ q) ∧ ¬p → q q
V F F V V
V F F V F
V V V V V
F V F V F
A demonstração do item 4 é dado na quarta coluna, e como esta consiste só de
V ’s, então a proposição condicional é de fato uma implicação.

Se a proposição bicondicional p ↔ q for uma tautologia, ela é chamada uma

equivalência e é denotada por p ⇔ q e lemos p é equivalente a q. Observando as
Cap. 1 • Introdução à lógica matemática 15

tabelas verdades podemos ver que p ↔ q se p e q tem os mesmos valores em cada

uma das possibilidades lógicas (veja a tabela do se, e somente se). Reciprocamente,
p e q tem os mesmos valores verdade em cada uma das possibilidades lógicas se
p ↔ q. Logo, como foi dito antes p ↔ q e p ≡ q tem o mesmo significado, e portanto
podemos trocar ↔ por ≡.

Teorema 1.3.5. Sejam p e q proposições quaisquer. Então:

(1) Lei da Dupla negação (D.N.): ¬(¬p) ≡ p.

(2) Leis Comutativas (Com.): p ∧ q ≡ q ∧ p, p ∨ q ≡ q ∨ p.

(3) Leis de Idempotência (Idemp.): p ∧ p ≡ p, p ∨ q ≡ q ∨ p.

(4) Lei Contrapositiva (Contrap.): (p → q) ≡ (¬q → ¬p).

Demonstração. O leitor deve fazer os itens 1, 2, 3, faremos apenas o item 4, e neste

usaremos a notação simplificada.

(p → q) ↔ (¬q → ¬p)
V V V V F V F
V F F V V F F
F V V V F V V
F V F V V V V
1 2 1 4 2 3 2

Os números na última linha da tabela verdade indicam a ordem que tomamos os

valores lógicos. Logo, a tabela acima mostra que p → q é equivalente à ¬q → ¬p

Tendo estabelecido estes conceitos podemos começar a fazer alguma matemática.

Como o matemático o Matemático Bertrand Russeldisse:

“As regras da lógica estão para a matemática, assim como

as estruturas estão para a arquitetura.”
(Mysticism and logic and other essays, 1917, p61)

Podemos começar com as leis de Morgan,

que são umas das ferramentas mais convenientes da
lógica.
Seção 1.4 • Raciocı́nio Dedutivo 16

Leis de Morgan
(a) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r).
(b) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r).
e as leis de negação:
(c) ¬(p ∧ q) ⇔ (¬p) ∨ (¬q).
(d) ¬(p ∨ q) ⇔ (¬p) ∧ (¬q).

“ Com isso podemos começar a fazer alguma matemática”. Poderiamos utilizar

tabelas verdades para contruir a prova destas leis, mas isso seria um tanto longo e
tediante. Uma vez na vida é bom fazer isto, portanto encorajamos o leitor a fazer
isso (faça por exemplo a, ced e use-os para deduzir b). É mais fácil provar a teoria
dos conjuntos análoga, e utilizando os diagramas de Venn e depois deduzir estas
regras acima usano a teoria dos conjuntos.
Observe que as leis de Morgan são análogos da lei distributiva

a.(b + c) = a.b + b.c

para os números reais. A. De Morgan (1806-1871) começou seu estudos para ser
matemático mas lhe foi recusada uma bolsa de estudos na Universidade de Cam-
bridge devido a sua objeções sobre o teste teológica obrigatório . Então ele começou
a estudar até a idade de 21 então aplicou para a cadeira de Matemática aplicada
para a Universidade College London. Ele foi nomeado e começou como professor
titular um ano mais tarde. Ele renunciou a sua cadeira várias vezes por questões de
princı́pios.

1.4 Raciocı́nio Dedutivo

As leis de adição, simplicaçao, silogismo dijuntivo, modus ponus e tolens e a redução
ao absurdo são muito úteis para justificar equivalências lógicas e implicações. Cha-
mamos estas leis de leis de inferência. Chamamos atenção para o fato que estas regras
foram selecionadas como referências convenientes e não precisam ser independentes
entre si. Por exemplo, a lei contrapositiva pode ser estabelecida “dedutivamente”
pelo uso de outras leis e definições relevantes, como podemos ver abaixo.

Exemplo 1.4.1.
(p ⇒ q) ≡ (¬q ⇒ ¬p).
Cap. 1 • Introdução à lógica matemática 17

Veja que,

(p ⇒ q) ¬(p ∧ ¬q) pela def. de implica

¬(¬qp ∧ p) pela lei de comutativa
(¬q ⇒ ¬p) pela def. de implica novamente.

Portanto, pela transitividade (p ⇒ q) ≡ (¬q ⇒ ¬p).

O método usado acima é chamado de raciocı́nio dedutivo. No raciocı́nio

dedtivo, quaisquer axiomas, definições, teoremas e regras de inferência, previamente
enunciados podem ser usados.

Exercı́cio 1.4.1. Prove o silogismo disjuntivo por raciocı́nio dedutivo. E prove

também que
(p ⇒ r) ∨ (q ⇒ s) ≡ p ∧ q ⇒ r ∨ s.

Agora vale ressaltar que é melhor usar o racicı́nio dedutivo do que tabelas ver-
dades, pois conseguimos provar muito mais brevemente a demonstração.

1.5 Contradição
Diferentemente das tautologias, existem proposições cujos os valores na tabela ver-
dade são todos falsos F , para cada uma das possibilidades lógicas. Tais proposições
são chamadas contradições. Por exemplo, p ∧ ¬p é uma contradição.
É fácil ver, que se t é uma tautologia, então ¬t é uma contradição. Reciproca-
mente, se c é uma contradição, então ¬c é uma tautologia.

Exercı́cio 1.5.1. Sejam t, c e p uma tautologia, uma contradição e uma proposição

qualquer. Então mostre que:

(1) p ∧ t ⇔ p,
p∨t⇔t

(2) p ∨ c ⇔ p,
p∧c⇔c

(3) c ⇒ p e p ⇒ t.
Seção 1.6 • Quantificadores 18

1.6 Quantificadores
Em qualquer discussão sempre devemos ter em mente o domı́nio ou o universo do
qual estamos falando, isto é, sobre que coleção de objetos estamos discutindo e que
propriedades são consideradas nestes objetos. Por exemplo, na afirmação: “ Todo
os humanos são mortais”, o universo é a coleção de todos os humanos. Com esta
consideração sobre o universo, a afimação “ Todo os humanos são mortais” pode ser
expressa como:

Para todo x no universo, x é mortal.

A frase “ Para todo x no universo” é chamada um quantificador universal, e é

simbolizada coma notação ∀. E a sentença x é mortal diz algo sobre o x, e podemos
simbolizar isso com p(x). Usando estes novos sı́mbolos, podemos escrever a afimação
geral “ Todo os humanos são mortais” como

(∀ x)(p(x)).

Considere agora a afirmação “ Alguns homens são mortais”, o universo em dis-

cusso é o mesmo. Agora, podemos refazer esta afirmação como:

Existe pelo menos um indivı́duo que é mortal.

Existe pelo menos um x tal que x é mortal.
ou ainda
Existe pelo menos um x tal que p(x).

A frase “Existe ao menos um x tal que” é chamada de um quantificador exis-

tencial e é simbolizado por (∃ x). Usando este novo sı́mbolo podemos podemos
reescrever a afirmação “ Alguns homens são mortais” como

(∃ x)(p(x)).

Assim, temos a seguinte definição.

Definição 1.6.1. “Para todo”, é escrito como ∀, é o quantificador universal.

“Existe”, é escrito como ∃, é o quantificador existencial.

Exercı́cio 1.6.1. Determine quais das seguintes afirmações é verdadeira:

1. Exatamente uma destas afimações é falsa;

Cap. 1 • Introdução à lógica matemática 19

2. Exatamente duas destas afirmações são falsas;

3. Exatamente três destas afirmações são falsas;

4. Exatamente quatro destas afirmações são falsas;

5. Exatamente cinco destas afirmações são falsas;

Apesar de ainda não termos definido conjunto, veremos agora o que podemos
fazer com um conjunto com somente dois elementos:

Definição 1.6.2. Seja B um conjunto contendo somente dois elementos 0 e 1, isto

é, B = {0, 1}, pense em zero como sendo “desligado” e 1 como sendo a palavra
“ligado”. Em aplicações, B modela as duas posibilidades de estado de um circuito
elétrico. Seja definidas sobre B duas operações a adição (+) e a multiplicação (∗)
definidas por:

x y x+y x y x∗y
1 1 0 1 1 1
1 0 1 1 0 0
0 1 1 0 1 0
0 0 0 0 0 0

Note que estas são idênticas as tabelas verdade de “ou exclusivo” ( ∨) e do “e”
∧ respectivamente. Chamamos B de Álgebra Booleana. (Em aplicações, + e ∗ são
os dois modelos de portas que comunmente ocorrem em um circuito elétrico).
Um predicado é uma declaração que envolve variáveis. Predicados se tornam
proposições quando objetos particulares (por exemplo, números) são substituı́dos
pelas variáveis. As proposições resultantes têm valores de verdade que dependem
desses elementos.
Temos os seguintes exemplos de predicados em matemática: x < y e m divide
n. Se substituirmos x = 2 e y = 3 no predicado x <, y, obteremos a afirmação
VERDADEIRA 2 < 3. Se substituirmos m = 2 e n = 3 no predicado m divide n,
obteremos a declaração FALSA 2 divide 3
Substituir uma das variável em um predicado reduz o número de variáveis em
1. Substituir todas as variáveis produz uma declaração. Agora, uxiste outraforma
de reduzir o número de variáveis em um predicado, que é quantificar uma ou mais
variáveis. Quantificadores serão familiares para você, mesmo que nunca tenha ouvido
Seção 1.6 • Quantificadores 20

essa palavra. Na verdade, a matemática não poderia existir sem eles. Existe o
quantificador universal, denotado por ∀ e o quantificador existencial ∴.
Suponhamos que temos um universo U e uma afirmação qualquer p(x), chamada
de predicado condicional, cuja variável x percorre, ou varia em U . Então (∀ x)(p(x))
afirma que para todo x em U , a proposição p(x), com respeito a x, é verdadeira, e
(∃ x)(p(x)) significa que pelo menos um x, em U , a afirmação p(x) é verdadeira.
Na lógica e na matemática, a negação de uma proposição “p(x) é verdadeira para
todo x (em U )”, [(∀ x)(p(x))], é considerada o mesmo que a asserção “∃ pelo menos
um x (em U ) para o qual p(x) é falsa”, (∃ x)(¬p(x)). Analogamente, ¬[(∃ x)(p(x))]
é considerada o mesmo que “não há nenhum x (em U ) tal que p(x) é verdadeira”
(na lı́ngua portuguesa, “não há nenhum” tem o significado de “∃ nenhum”); ou, em
outras palavras, p(x) é falsa para todo x (em U )”, ou (∀ x)(¬p(x)). Sumarizamos
tudo isto no seguinte axioma:

Axioma 1.6.1. [Regra da negação do quantificador] Seja p(x) um predicado pro-

posicional, isto é, uma proposiçao sobre um objeto não especificado de um dado
universo. Então
¬[(∀ x)(p(x))] ≡ [(∃ x)(¬p(x))],

¬[(∃ x)(p(x))] ≡ [(∀ x)(¬p(x))].

Exemplo 1.6.1. Quais das seguintes proposições é equivalente a negação da pro-

posição “Todas as cobras são venenosas”?

(a) Todas as cobras não são venenosas.

(b) Algumas cobras são venenosas.

(c) Algumas cobras não são venenosas.

Solução: O domı́nio de discurso U é a coleção de todas as cobras. Seja p(x) o

predicado proposicional que afirma que x é venenosa (onde a variável x varia sobre
U ). A afirmação “Todas as cobras são venenosas” é então traduzida em (∀x)(p(x)).
Conforme a regra de negação do quantificador, o Axioma (1.6.1), ¬[(∀x)(p(x))] é
equivalente à (∃x)(¬p(x)), que representa “Algumas cobras não são venenosas”.

Exercı́cio 1.6.2. . Traduza a proposição da álgebra elementar: “A equação x2 +

3x + 2 = 0 tem soluções” em linguagem lógica, usando um quantificador. Qual é o
domı́nio de discurso aqui?
Cap. 1 • Introdução à lógica matemática 21

Exercı́cio 1.6.3. Encontre a proposição equivalente à negação de cada uma das

seguintes proposições, usando N.Q.(a negação do quantificador).

(a) Todas as cobras são répteis.

(b) Alguns cavalos são mansos.

(c) Alguns matemáticos não são sociáveis.

(d) Não há bebê que não seja fofo.

1.7 “De quem você está falando”?

Em termos mais precisos podemos dizer

Definição 1.7.1. Uma variável é uma letra x denotando algum (possivelmente des-
conhecido) objeto. Uma constante é uma letra denotando algum objeto especı́fico
(um objeto bem definido). Um termo é uma variável ou constante.

Um predicado é uma regra que associamos a cada termo uma afirmação lógica.

Exemplo 1.7.1. “Mickey” é uma constante. A afirmação “x” é uma das favoritas
músicas de “Mickey” é um predicado envolvendo uma variável e uma constante.
Aqui x pode por exemplo ser uma música clássica de Wagner.

Voltemos ao tı́tulo da aula por um momento, a frase lunática no tı́tulo da aula

é : “você tem lógica em sua mente se...”. Vejamos os famosos ditados:
“O tempo não espera por nenhum homem”
e
“Nenhum homem é uma ilha!”.
Você pensa: portanto, “O tempo espera por uma ilha!”.
Se x denota denota a constante “nenhum homem” e y denota a con- stante
“uma ilha”, então esses dois ditos pode ser escritos “O Tempo espera por x” e
“x = y’. Substituindo, podemos portanto obter “O tempo espera por y”’, isso
pode parecer uma loucura, mas é lógica.

Exemplo 1.7.2. . (a) Considere a afirmação: “Cada um do meus amigos podem

correr 2 km na esteira em 12 minutos”. Então M (x) : “x pode correr 2 km na
Seção 1.8 • Argumentos lógicos 22

esteira em 12 minutos”, A(x) : “x é um amigo meu”. Então, em simbologia a frase

fica:
∀x, A(x) → M (x).

Faça a a negação da frase: “Alguns de meus amigos podem correr 2 km na esteira

em 12 minutos”, em forma simbólica.

Exercı́cio 1.7.1. (M. Gardner). O Professor White, Professor Brown e o Professor

Black foram lanchar juntos. Não é supreendente!, disse a moça da lanchonete, “Que
o nomes são White, Black, e Brown e um de nós tem cabelo Black, um tem cabelo
Brown e um tem cabelo White”. “Isto é verdade”, respondeu o de cabelos Black, já
que o Professor Black mordia o sanduı́che, “e observe que nenhum deles tem a cor
dos cabelos combinando com o nome? O cabelo da moça não é Brown. Qual é a cor
do cabelo do Professor Black?

White Brown Black Moça

White
Brown
Black
Moça X

1.8 Argumentos lógicos

Definição 1.8.1. Para pensar logicamente, precisamos produzir argumentos lógicos,
mas o que argumentos lógicos? Um argumento lógico é uma sequência de afirmações
chamadas de hipóteses p1 , p2 , . . . , pn que implicam em alguma afirmação q chamada
de conclusão. Tal argumento lógico é chamada de uma demonstração de q. Em
sı́mbolos:
(p1 ∧ p2 ∧ · · · ∧ pn ) ⇒ q.

Exercı́cio 1.8.1. Usando as tabelas verdade, verifique as argumentos lógicos:

 
(1) (p ⇒ q) ∧ (q ⇒ r) ⇒ (p ⇒ r). (Lei Transitiva)
(2) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r). (Leis Associativas)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r).

Uma demonstração formal de validade para um dado argumento é uma sequência

de proposições, cada uma das quais é ou uma premissa do argumento ou segue de
Cap. 1 • Introdução à lógica matemática 23

proposições precedentes por um argumento válido conhecido, terminando com a

conclusão do argumento. Algumas vezes indicamos a conclusão com o sı́mbolo ∴.

Existe um outro método de demonstração chamado demonstração indireta, ou

método de demonstração por redução ao absurdo. Uma demonstração indireta de
validade, para um dado argumento, é feita incluindo-se, como premissa adicional,
a negação de sua conclusão, e então derivando uma contradicão; assim que uma
contradição é obtida, e a demonstração fica completa.

Exemplo 1.8.1. Faça uma demonstração indireta para demonstrar a validade do

seguinte argumento.
p∨q →r

s→p∧u

q∨s

∴r

Demonstração:

1.9 Indução Matemática

Um outro método de demonstração, muito útil para demonstrar a validade de uma
proposição P (n), envolvendo o número natural n, é o seguinte princı́pio de indução
matemática.
Indução Matemática. Se P (n) é uma proposição envolvendo o número natural
n, tal que
Seção 1.9 • Indução Matemática 24

(1) P (1) é verdadeira, e

(2)P (k) ⇒ P (k + 1) para qualquer número natural arbitrário k, então P (n) é ver-
dadeira para todo número natural n.
O princı́pio acima é uma consequência de um dos Axiomas de Peano para os
números naturais. Quando aplicarmos o princı́pio de indução matemática para
demonstrarmos um teorema, o teorema tem que ser subdividido em casos, uma caso
para cada número natural. Assim, devemos verificar ambas as condições (1) e (2).
A verificação de (1), é geralmente fácil, nos garante que o teorema é verdadeiro pelo
menos no caso n = 1. Para verificar a condição (2), devemos provar um teorema
auxiliar cuja premissa (hipótese) é “P (k) é verdadeira”, e cuja conclusão (tese) é
“P (k + 1) é verdadeira”. A premissa “P (k) é verdadeira” é chamada a hipótese de
indução.

Exemplo 1.9.1. Demonstre por indução matemática que:

n(n + 1)
1 + 2 + 3 + ··· + n = .
2

Solução. A proposição P (n) em questão neste exemplo é:

n(n + 1)
P (n) : 1 + 2 + 3 + ··· + n = .
2

Obserque que P (1) é verdadeira, pois 1 = 1(1 + 1)/2. Portanto vale a condição
(1). Suponha agora que k ≥ 1, e que P (k) é verdadeira, isto é, temos que:

k(k + 1)
1 + 2 + 3 + ··· + k = .
2

é verdadeira. Então se somando a esta igualdade k + 1 em ambos os membros

obtemos:

k(k + 1) k(k + 1)
1 + 2 + 3 + ··· + k = + (k + 1) = + (k + 1)
2 2
k(k + 1) 2(k + 1)
= +
2 2
(k + 2)(k + 1)
=
2
(k + 1)(k + 2)
=
2

O que mostra que P (k + 1) é verdadeira. Como mostramos que as condições (1)e

(2) são satisfeitas. Portanto, pelo Princı́pio da Indução Matemática, temos que a
Cap. 1 • Introdução à lógica matemática 25

afirmação P (n) é verdadeira para cada número natural n.

A idéia de indução matemática pode ser usada para fazermos definições ma-
temáticas envolvendo números naturais. Por exemplo, a definição de potências de
um número real x podem ser definidas por:

x1 = x
n+1
x = xn .x para cada número natural n

As definições acima indicam que x1 = x, x2 = x.x, x3 = x.x.x, . . . e assim por

diante. A seguir daremos uma definição indutiva do sı́mbolo c(n, r).

Definição 1.9.1. Seja n um número natural e r um número inteiro. O sı́mbolo

C(n, r) é definido por

C(0, 0) = 1 C(0, r) = 0 para cada r 6= 0

C(n + 1, r) = C(n, r) + C(n, r − 1)

Teorema 1.9.1. Sejam n, r números inteiros, tais que 0 ≤ r ≤ n, então:

n!
C(n, r) = ,
r!(n − r)!

sendo n! o produto n(n − 1)(n − 2) . . . 3.2.1, dos primeiros n números naturais con-
secutivos, consideramos que n > 0 e 0! = 1 por convenção.

Demonstração. Exercı́cio.

Teorema 1.9.2. [Teorema Binomial] Se x e y são dois números reais e n é um

número natural, então

(x + y)n = C(n, 0)xn + C(n, 1)xn−1 y + · · · + C(n, r)xn−r y r + · · · + C(n, n)y n .

Demonstração. Usaremos indução matemática. Se n = 1, temos (x + y)1 = x + y.

Portanto a igualdade é verdadeira para n = 1. Suponha agora que k ≥ 1 e que a
igualdade é verdadeira para n = k, isto é:

(x + y)k = C(k, 0)xk + C(k, 1)xk−1 y + · · · + C(k, r)xk−r y r + · · · + C(k, k)y k .

Então, para termos a validade da igualdade com k +1 no lugar de k, multiplicaremos

ambos os lados da igualdade por (x + y), e já fica claro que o ado esquerdo terá a
Seção 1.9 • Indução Matemática 26

forma desejada com vemos abaixo:

(x + y)k+1 = (x + y)[xk + C(k, 1)xk−1 y + · · · + C(k, r)xk−r y r + · · · + y k ]

= xk+1 + [C(k, 0) + C(k, 1)]xk y + . . .
+[C(k, r − 1) + C(k, r)]x(k+1)−r y r + · · · + y k+1
= C(k + 1, 0)xk+1 + C(k + 1, 1)xk y + · · · + C(k + 1, r)x(k+1)−r y r
+ · · · + C(k + 1, k + 1)y k+1

Na primeira igualdade usamos a distributividade e na terceira usamos a definição

do sı́mbolo C(n, r) dado em (1.9.1). E assim mostramos a igualdade desejada, isto
é se a afirmação é verdadeira para n = k então ela também é válida para n = k + 1.
Logo, pelo princı́pio da indução matemática a afimação é veradeira para todos os
naturais n.
 CAPÍTULO 2

Conjuntos

2.1 Introdução
A teoria dos conjuntos é a base de toda a matemática moderna. Assim como a lógica
fornece uma estrutura rigorosa de como pensamos, a teoria dos conjuntos fornece
uma estrutura similarmente precisa para como reunimos mentalmente instâncias
de objetos em classes. Noções da teoria dos conjuntos, tais como: relações, equi-
valências, operações, funções, etc., fornecem uma maneira logicamente rigorosa de
atribuir propriedades a objetos ou de pensar em como as classes de objetos estão em
relação umas às outras ou de considerar como dois objetos podem ser combinados
para obtermos um outro objeto.
Conseqüentemente, a terminologia e a notação da teoria dos conjuntos fornecem
uma maneira concisa de dizer muitas coisas diferentes, matemáticas ou não, com
precisão exata.

2.2 Elementos da teoria dos conjuntos

O conceito de conjuntos na matemática torna preciso a noção coleção de objetos e
este conceito é fundamental para a matemática moderna.

Definição 2.2.1. Um conjunto é um coleção de objetos para o qual existe uma

regra clara para determinar se um objeto está ou não incluı́do. Um objeto em um
conjunto é chamado um elemento do conjunto. Escrevemos x ∈ A para significar

27
Seção 2.2 • Elementos da teoria dos conjuntos 28

que o elemento x pertence ao conjunto A e escrevemos x ∈

/ A para significar que o
elemento x não é um elemento do conjunto A.

Uma forma alternativa de expressar que x ∈ A é dizer “x está em A”ou A contém

x”.
Os conjuntos são usualmente designados por letras maiúsculas enquanto que os
elementos representados por letras minúsculas. A afirmação de que um elemento a
pertence ao conjunto A é simbolizada com a ∈ A, enquanto que a sua negação é
simbolizada por a ∈
/ A.
Conjunto de números padrões:

• N : é o conjunto dos números naturais incluindo o zero;

• Z : é o conjunto dos números inteiros;

• Q : é o conjunto dos números racionais:

• R : é o conjunto dos números reais;

• C : é o conjunto dos números complexos.

Algumas vezes fazemos uso de modificações dos conjutos acima. Por exemplo
denotaremos por R+ para denotar o conjunto de dos números reais não negativos e
R<0 denota o conjunto dos números reais estritamente negativos. Denotamos por N∗
, Z∗ , R∗ , etc para denota o respectivo conjunto de números sem o zero. Denotamos
por ∅ o conjuto vazio.
Apresentaremos duas formas comuns de denotar conjuntos. Uma delas fornece
regras claras de se um obeto está neste conjunto ou não, isto listando seus elementos.
No outro caso usamos chaves para demarcar o ı́nicio e o fim da regra definidora do
conjunto considerado.

Exemplo 2.2.1 (Listagem de elementos). Considere, por exemplo o conjunto A =

{5, 9, 11, 13}o conjunto formado por quatro números inteiros. Nesta notação a ordem
dos elementos não importa, tão puco escrevemos um mesmo elemento mais que uma
vez (não tomamos cuidado com ordem ou repetição de elementos). É importante
notar que o que escrevemos na lista é meramente um significante que aponta para
o objeto real. Portanto, o sı́mbolo 5 está representando o objeto matemático de
“cinco”. Da mesma forma, podemos escrever F = {A, S, P, V } como um conjunto
de quatro elementos que descreve por exemplo as iniciais dos membro da minha
Cap. 2 • Conjuntos 29

famı́lia, onde os sı́mbolos A, S, P, V são indicadores dos objetos reais no conjunto,

ou seja, meus filhos, meu marido e eu.

Exemplo 2.2.2 (Declaração definidora). Exibindo explicitamente uma propriedade

definidora. Por exemplo, considere A = {x | x é um número real tal que − 1 ≤ x ≤
1}. Isso define um rótulo que expressa de que números reais estamos falando, e
geralmente escrevemos de forma mais concisa A = {x ∈ R | − 1 ≤ x ≤ 1} e lemos
“o conjunto dos números reias miores do que −1 e menores que 1.”

Dizemos que os conjuntos A e B são considerados iguais quando x ∈ A ⇔ x ∈ B,

ou em outras palavras, cada elemento de A é um elemento de B e cada elemento
de B é um elemento de A, ou seja que eles têm exatamente os mesmos elementos.
Escrevemos A = B para indicar que os conjunto são iguais.
Ao trabalharmos com conjuntos, é comum trabalharmos dentro de ambiente
de contexto e considerar os conjuntos dentro deste contexto. Por exemplo, se um
determinado problema ou discussão envolve apenas o conjunto de carros novos,
então estaremos interessados apenas em considerar conjuntos que existem dentro
desse ambiente de contexto.

Definição 2.2.2 (Subconjunto). Um conjunto B é chamado de subconjunto de

um conjunto A, se x ∈ B implica que x ∈ A. Em outras palavras, cada elemento de
B é um elemento de A. E denotamos este fato com a simbologia B ⊆ A.

A condição de que todo elemento de um conjunto B pertence a um conjunto

A estabelece uma relação entre B e A chamada relação de inclusão. O sı́mbolo
⊆ lembra o sı́mbolo ≤ dos números reais. Esta similaridade de notação pode nos
inspirar a assumir que B ⊂ A, como o sı́mbolo de desigualdade estrita <, significaria
A ⊂ B e A 6= B. Infelizmente, por um acaso de inconsistência histórica na notação,
alguns autores usam o sı́mbolo ⊂ para significar um subconjunto estrito, enquanto
outros o usam como sinônimo de ⊆. Para não causar confusão, usamos o sı́mbolo
A ( B para significar B ⊂ A e B 6= A. O sı́mbolo B * A significa que B não é um
subconjunto de B.
A condição de que todo elemento de um conjunto A pertence a um conjunto B
estabelece uma relação entre A e B chamada relação de inclusão. Quando existir
uma tal relação entre A e B escreveremos
Seção 2.2 • Elementos da teoria dos conjuntos 30

A ⊂ B ou B ⊃ A,

e leremos A está contido em B, ou A é um subconjunto de B, ou ainda diremos B

contém A.
A negação e A ⊂ B é simbolizada por A 6⊂ B. Para mostrarmos que A 6⊂ B
deve-se exibir pelo menos um elemento de A que não pertence a B.

Exemplo 2.2.3 (Exemplo não trivial de subconjunto de um conjunto). Seja

C 0 ([0, 1]) o conjunto das funções de uma variável real sobre o intervalo [0, 1] e
seja C 1 ([0, 1]) o conjunto de todas as funções diferenciáveis cuja derivada é uma
função contı́nua no intervalo [0, 1]. Então, C 1 ([0, 1]) ⊆ C 0 ([0, 1]) segue do resulg-
tado não trivial que uma função diferenciável sobre um intervalo fechado é uma
função contı́nua sobre este intervalo.

A relação de inclusão possui claramente as seguintes propriedades:

(1) A ⊂ A, para todo conjunto A.

(2) A = B se, e somente se, A ⊂ B e B ⊂ A.

(3) Se A ⊂ B e B ⊂ C, então A ⊂ C.

Daremos mais exemplos de conjunto dados a partir de declarações definidoras

(veja Exemplo (2.2.2)), que comumente chamaremos setença aberta.
Dado um conjunto A (nosso conjunto contexto considertado) e uma sentença
aberta P (x) em A admitiremos a existência de um subconjunto de A formado pelos
elementos a ∈ A para os quais P (a) é verdadeira. Este conjunto será denotado da
seguinte forma
{x ∈ A | P (x)}.

E assim, estamos expressando um suconjuto de A caracterizado pela propriedade

P (x), esta será a maneira usual para representarmos conjunto de um modo geral.

Exemplo 2.2.4. 1. O conjunto {x ∈ Z | x ≥ 0} é o conjunto de todos os números

inteiros não negativos. Este conjunto será denotado por Z+ .
2. Temos que o conjunto {x ∈ Z | Existe n ∈ Z tal que x = 2.n} é o conjunto
dos números inteiros pares. Os conjuntos da forma {x ∈ Z | Existem n, m ∈
Z tal que x = m.4 + n.6}, serão vistos adiante no texto.
Cap. 2 • Conjuntos 31

3. Seja A = Z e seja a seguinte sentença aberta

P (x) = {x ∈ A | Existem inteiros m, n tais que x = m.4 + n.6}.

Então temos que P (2) é verdadeira, pois 2 = 2.4 + (−1).6, onde m = 2 e n = −1;
P (−6) é verdaddeira, pois −6 = 0.4 + (−1).6, onde m = n = 0. Agora, P (3) é falsa,
pois se tivessemos −3 = m.4 + n.6 = 2.(m.2 + n.3), e terı́amos que −3 seria um
número par, o que não é verdade.
4. Seja P (x) uma sentença aberta em um conjunto A. Considere os conjuntos
B = {x ∈ A | P (x)} e B 0 = {x ∈ A | (não P(x))}. É claro que B e B 0 não tem
elementos comuns, e um elemento qualquer de A ou pertence à B ou pertence à B 0 .
5. O conjunto {x ∈ A | x 6= x} não tem nenhum elemento.

O último exemplo em (2.2.4) admite a existência de um conjunto que não possui

elementos. Tal conjunto é chamado de conjunto vazio e é denotado com o sı́mbolo
∅. Afirmamos que ∅ ⊆ A para qualquer que seja o conjunto A. Podemos verificar
isso, verificando que a negação desta afirmação é falsa (confirmando assim que esta
é verdadeira). Vejamos negação da afirmação, isto é, ∅ * A. Para que isto seja
verdade devemos obter x ∈ ∅, mas como não existe uma tal elemento visto que o
conjunto vazio não possui elementos esta afirmação é falsa. E então afirmação ∅ ⊆ A
é verdadeira.
No que segue usaremos as seguintes notações e regra da lógica simbólica. Seja
P (x) uma sentença aberta em um conjunto A. Usaremos as notações

∀ x ∈ A, P (x),

para representar a sentença, para todo x em A a afirmação P (x) é verdadeira.

A negação da sentença, ∀ x ∈ A, P (x) é a sentença

∃ x ∈ A, P(x),

enquanto que a negação da sentença ∃ x| P (x) é a sentença

∀ x ∈ A, (não) P(x).

Usaremos os conectivos e (∧) e ou (∨), sendo que o conectivo ou terá sentido

inclusivo, isto é, significando uma coisa ou outra, ou ambas. Se P e Q são sentenças,
Seção 2.3 • Operações com Conjuntos 32

a negação (¬) de P ou Q é
(não) P e (não) Q,

enquanto que a negação de P e Q é

(não) P ou (não) Q.

2.3 Operações com Conjuntos

Existem algumas operações básicas sobre um conjunto U dado. Nesta lista, defini-
mos as operações sobre subconjuntos A e B de U e fornecemos os correspondentes
diagramas de Venn, sobre o qual a porção mas escura representa o resultado da
operação.

• A união de A e B é o conjunto A ∪ B = {x ∈ U | x ∈ A ou x ∈ B}.

• A Interseção de A e B é o conjunto A ∩ B = {x ∈ U | x ∈ A e x ∈ B}.

• O Complementar de A é o conjunto AC = {x ∈ U | x ∈
/ A}, isto é, o conjunto
dos elementos de U que não estão em A.

• A Diferença de A com relaçãlo à B é o conjunto A \ B = {x ∈ U | x ∈ A e x ∈

/
B}.

Figura 2.1: União de A e B Figura 2.2: Interseção de A e B

Figura 2.3: Complementar de A Figura 2.4: Diferença A \ B

Cap. 2 • Conjuntos 33

Exemplo 2.3.1. Seja U = {1, 2, . . . , 10} e considere os subconjuntos A = {1, 3, 6, 7}

e B = {1, 5, 6, 8, 9} e C = {2, 3, 4, 5, 6}. Calularemos os seguintes exemplos de
operações.
(1) A ∩ B = {1, 6}.
(2) B \ (A ∪ C) = B \ {1, 2, 3, 4, 5, 6, 7} = {8, 9}.
(3)(B ∪ C)C = {1, 2, 3, 4, 5, 6, 8, 9}C = {7, 10}.
(4)(A ∩ B) ∩ C = 1, 6 ∩ C = {6}.
(5) A ∩ (B ∩ C) = A ∩ {5, 6} = {6}.

As operações de conjunto oferecem maneiras concisas de descrever muitas pro-

priedades comuns de conjuntos. A seguinte definição ilustra isso.

Definição 2.3.1. Sejam A e B subconjuntos de U . Dizemos que A e B são disjuntos

se A ∩ B = ∅.

Proposição 2.3.1. Para conjuntos A e B, temos A = B se, e somente se, A ⊆ B

e B ⊆ A.

Demonstração. Se A = B, então temos que A ⊆ B e B ⊆ A. Reciprocamente,

se A ⊆ B e B ⊆ A, então x ∈ A ⇒ x ∈ B e x ∈ B ⇒ x ∈ A. Portanto,
x ∈ A ⇔ x ∈ B, o que significa que A e B tem exatamente os mesmos elementos.

Veremos agora muitas propriedades de como as operações de conjunto se relaci-

onam entre si.
Quando em uma discussão usarmos o termo sentença aberta P (x) sem especificar
sobre que conjunto ela é definida, subentende-se que ela é definida sobre a união de
todos os conjuntos que intervém na discussão.
A união tem as seguintes propriedades.
Para todos os conjuntos A, B e C valem:

(1) A ∪ ∅ = A e A ∪ A = A

(2) A ⊆ A ∪ B e B ⊆ A ∪ B

(3) A ∪ B = B ∪ A

(4) (A ∪ B) ∪ C = A ∪ (B ∪ C)

Proposição 2.3.2. Dodos conjuntos A, A0 , B e B 0 com A ⊆ B e A0 ⊆ B 0 , então

A ∪ A0 ⊆ B ∪ B 0 .
A ⊆ B
⇒ A ∪ A0 ⊆ B ∪ B 0
A0 ⊆ B 0
Seção 2.3 • Operações com Conjuntos 34

Demonstração. Se tivermos que A ∪ A0 = ∅, a afirmação é verdadeira, uma vez que

o conjunto vazio está contido em um conjunto qualquer.
Agora, suponha que A ∪ A0 6= ∅. Seja x ∈ A ∪ A0 qualquer, temos que x ∈ A ou
x ∈ A0 . Mas por hipótese temos que A ⊆ B e A0 ⊆ B 0 , segue então que x ∈ B ou
x ∈ B 0 . Logo, x ∈ B ∪ B 0 . Portanto, A ∪ A0 ⊆ B ∪ B 0 .

Corolário 2.3.1. Se A ∪ B = A se, e somente se, B ⊆ A.

Demonstração. (⇒) Seja x ∈ B um elemento qualquer, então temos que x ∈ B ∪ A.

Mas por hipótese A ∪ B = A, assim x ∈ A e então B ⊆ A.
(⇐) Suponhamos agora que B ⊆ A, e como A ⊆ A segue da Proposição (2.3.2) que
A ∪ B ⊆ A ∪ A = A, logo A ∪ B ⊆ A. Como claramente A ⊆ A ∪ B, segue que
A ∪ B = A.

A seguir listamos as propriedades da interseção.

Para todos os conjuntos A, B e C temos que

(1) A ∩ ∅ = ∅ e A ∩ A = A

(2) A ∩ B ⊆ A e A ∩ B ⊆ B

(3) A ∩ B = B ∩ A

(4) (A ∩ B) ∩ C = A ∩ (B ∩ C)

Proposição 2.3.3. Sejam A, B e C conjuntos quaisquer, então

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Demonstração. (⊆) Primeiro observe que se A ∩ (B ∪ C) = ∅ não temos nada para

provar. Suponha que A ∩ (B ∪ C) 6= ∅. Seja x ∈ A ∩ (B ∪ C) um elemento qualquer.
Logo, x ∈ A e x ∈ B ∪ C. Se x ∈ B, então x ∈ A ∩ B. Se x ∈ C, então x ∈ A ∩ C.
Em qualquer caso, x ∈ (A ∩ B) ∪ (A ∩ C).

(⊇) Se o conjunto (A ∩ B) ∪ (A ∩ C) = ∅ a inclusão é óbvia. Suponha que este

conjunto é não vazio e seja x ∈ (A ∩ B) ∪ (A ∩ C) um elemento qualquer. Logo,
x ∈ A ∩ B ou x ∈ A ∩ C. Em qualquer caso, x ∈ A e temos que x ∈ B ou x ∈ C.
Portanto, x ∈ A ∩ (B ∪ C).
Cap. 2 • Conjuntos 35

Proposição 2.3.4. Sejam A, B e C conjuntos quaisquer, então

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Demonstração. Faça este exercı́cio, o leitor pode fazer de modo bem parecido como
na Proposição (2.3.3).

A seguir listamos as propriedades da diferença, que seguem imediatamente das

definições.

(1) A \ ∅ = A e A \ A = ∅

(2) Se A ∩ B = ∅, então A \ B = A e B \ A = B

(3) CA (∅) = A e CA (A) = A

Proposição 2.3.5. Sejam B e B 0 subconjuntos de A. Se B ⊆ B 0 , então

CA (B 0 ) ⊆ CA (B)

Demonstração. Seja x ∈ CA (B 0 ) um elemento qualquer. Então temos que x ∈ A

/ B 0 . Mas por hipótese temos que B ⊆ B 0 , então segue que x ∈
ex ∈ / B, pois do
contrário se x ∈ B terámos que x ∈ B 0 . E desta fomra temos que x ∈ A e x ∈
/ B
então x ∈ CA (B).

Proposição 2.3.6. Sejam B e B 0 subconjuntos de A. Então

CA (B ∪ B 0 ) = CA (B) ∩ CA (B 0 ).

Demonstração. (⊆) Seja x ∈ CA (B ∪ B 0 ) um elemento qualquer. Então temos que

/ B ∪ B 0 . Assim, temos que x ∈
x∈Aex∈ / B ∪ B, desta forma x ∈ / B0 e
/B ex∈
portanto x ∈ CA (B) ∩ CA (B 0 ).
(⊇) Seja x ∈ CA (B) ∩ CA (B 0 ) um elemento qualquer, então temos que x ∈ CA (B) e
x ∈ CA (B 0 ). Assim, x ∈ A e x ∈ / B 0 . Logo, x ∈ A e x ∈
/ B ex∈ / B ∪ B 0 e desta
forma x ∈ CA (B ∪ B 0 ).

Proposição 2.3.7. Sejam B e B 0 subconjuntos de A. Então

CA (B ∩ B 0 ) = CA (B) ∪ CA (B 0 ).
Seção 2.4 • Conjunto das Partes e Produto Cartesiano 36

Demonstração. A demostração desta proposição é deixada como exercı́cio para o

leitor.

2.4 Conjunto das Partes e Produto Cartesiano

Dado um conjunto A qualquer. Seja P(A) o conjunto formado por todos os sub-
conjuntos de A. É claro que um elemento de P(A) é um subconjunto de A, isto é,
S ∈ P(A) é equivalente a escrever S ⊆ U . Além disso, o conjunto das partes de um
conjunto é uma maneira de obter um novo conjunto a partir de um conjunto.

Exemplo 2.4.1. Seja A = {1, 2, 3}. O conjunto das partes de A é P(A) =

{∅}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. Note que P(A) tem oito elementos.

Proposição 2.4.1. Seja n um inteiro não negativo. Se A é um conjunto com n

elementos, então P(A) tem 2n elementos.

Demonstração. Primeiro provaremos o caso n = 0. Isto significa que A = ∅. Então

P(A) = {∅} e portanto 1 = 20 elemento. Assim a proposição vale para n = 0. Es-
crevamos A = {a1 , a2 , . . . , an } para algum inteiro positivo n. Para todo subconjunto
B, podemos perguntar n questões independentes: se a1 ∈ B, sea2 ∈ B e assim por
diante para cada elemento de A. Cada questão tem duas possibilidades de respos-
tas, e cada uma delas é independente das outras. Assim, existem 2n = 2 × 2 × . . . 2
subconjuntos de A.

Proposição 2.4.2. Seja n um inteiro não negativo e seja A um conjunto com n

elementos. O número de subconjuntos com k elementos é:
!
n n!
=
k k!(n − k)!
!
n
Demonstração. Denotemos de o número de subonjuntos com k elementos em
k
um conjunto com n elementos. Agora, para contarmos o número de subconjunto
com k elementos, podemos contar de muitas maneiras, podemos selecionar k ele-
mentos (não ordenados) de A. Esta escolha não ordenada corresponde a um único
subconjunto. Se selecionamos k elementos em ordemsem repetições, temos

n!
n × (n − 1) × (n − 2) × · · · × (n − (k − 1)) =
(n − k)!
Cap. 2 • Conjuntos 37

escolhas para fazer isto. Por outro lado, com um dado conjunto de k elementos
existem k! possibilidades.
Portanto, !
n n!
k! =
k (n − k)!
e o resultado segue.

O produto cartesiano é outra maneira de criamos novos conjuntos a partir de

conjuntos conhecidos. E o que é mais importante, o produto cartesiano de dois
conjuntos fornece um modelo rigoroso para a noção mental de emparelhar ou ordenar
os elementos dos conjuntos.

Definição 2.4.1. [Produto Cartesiano] Sejam A e B conjuntos, o produto car-

tesiano de A e B, denotado por A × B é o conjunto consistindo de todos os pares
ordenados (a, b), onde a ∈ A e b ∈ B. Portanto:

A × B = {(a, b) | a ∈ A, b ∈ B}

De modo geral temos: se A1 , A2 , . . . , An são n conjuntos, definimos o produto car-

tesiano A1 × A2 × · · · × An como o conjunto das n-uplas ordenadas (a1 , a2 , . . . , an ),
com ai ∈ Ai , para i = 1, 2, . . . , n. Em sı́mbolos

A1 × A2 × · · · × An = {(a1 , a2 , . . . , an ) | ai ∈ Ai , para i = 1, 2, . . . , n}

Se consideramos o mesmo conjunto A, escrevemos:

An = A
| ×A×
{z· · · × A}
n

Por exemplo, se A = {a, b} e B = {c, d}, então temos que A × B =

{(a, c), (a, d), (b, c), (b, d)}, e B × A = {(c, a), (c, b), (d, a), (d, b)}.
Note que em geral temos que A × B 6= B × A. Além disso, temos também que
A × B = ∅ se, e somente se, A = ∅ ou B = ∅.

2.5 Famı́lias de Conjuntos

Seja I um conjunto não vazio qualquer. Uma famı́lia indexada por I é uma coleção
de conjuntos Ai com i ∈ I. Uma tal famı́lia será denotada por (Ai )i∈I .
Seção 2.6 • Para saber mais... 38

A união dos elementos da famı́lia é

[
Ai = {x | x ∈ Ai para algum i ∈ I}
i∈I

e sua interseção é
\
Ai = {x | x ∈ Ai para todo i ∈ I}.
i∈I

Como acontece com o caso da interseção de dois conjunto temos as própriedades

imediatas:
[ \
Aj ⊆ Ai e Ai ⊆ Aj .
i∈I i∈I

2.6 Para saber mais...

A teoria moderna dos conjuntos é considerada criada por Georg Cantor (1845-1918),
que observou a necessidade de uma tal teoria quando estudava séries trigonométricas.
Cantor escreveu: “Por um conjunto entendemos qualquer coleção dentro de
um todo de objetos distintos definidos, de noção intuição ou pensamento”
Isto não proibe ninguém de considerar “ o conjunto de todos os conjuntos”,
é foi isso que Russel pensou. O problema na definição de Cantor de conjunto é a
palavra coleção, bom o que é uma coleção? poderı́amos pensar por exemplo: é um
grupo de objetos coletados, mas isto não nos ajudaria em nada, Cantor não notou
que o termo conjunto era realmente indefinı́vel.
Para evitar dificuldade, como o paradoxo de Russel (2.6.1) na teoria dos conjun-
tos, devemos aceitar que os termos conjunto e elemento com termos indefinidos ou
primitivos, e guiar estes conceitos primitivos por um número de axiomas:

• Axioma da Especificação;

• Axioma do Conjunto das Partes;

• Axioma da Extensão: Como A = B se e somente se A e B contém os

mesmos elementos;

• Axioma do Conjunto Vazio: ∅ é um conjunto

• Axioma do Emparelhamento: Se A e B são conjuntos, então também o é

{A, B};
Cap. 2 • Conjuntos 39

• Axioma das Uniões: Se F é um conjunto de conjunto, então F é um con-

junto.

Estes axiomas são frequentemente dados em tratamentos axiomáticos da teoria

dos conjuntos.
O Paradoxo de Russel não foi o único a aparecer na teoria dos conjuntos.
Logo depois do seu aparecimento, muitos paradoxos foram construı́dos por vários
matemáticos e lógicos. Como uma consequência de todos esses paradoxos, muitos
matemáticos e lógicos contribuı́ram com várias formulações da teoria axiomática
dos conjuntos, cada uma projetada de modo a evitar esses paradoxos e, ao mesmo
tempo, a preservar o corpo principal da teoria dos conjuntos de Cantor. Entretanto,
ninguém apareceu com um sistema axiomático completamente satisfatório para a
teoria dos conjuntos.
Apesar das dificuldades supracitadas, a teoria dos conjuntos de Cantor já pe-
netrou em todos os ramos da matemática moderna, e provou ser de importância
particular nos fundamentos da análise moderna e da topologia. Na verdade, mesmo
os mais simples e bem construı́dos sistemas axiomáticos da teoria dos conjuntos
são inteiramente adequados para a construção de virtualmente toda a matemática
clássica (por exemplo, a teoria dos números reais e complexos, álgebra, topologia,
etc.)
Vejamos agora o seguinte paradoxo:

Observação 2.6.1. [Paradoxo de Russel] Devemos ter um pouco de cuidado

quando descrevemos conjunto usando propriedades pois algumas propriedade “auto-
referenciadas” podem levar a contradições: Seja

R = {x | x 6= x}

Em outras palavras, para todo x, x ∈ R ⇔ x 6= x. Em particular, se tomamos

x = R, então vem
R∈R⇔R∈
/ R,

um contradição óbvia. O problema aqui é que o conjunto R não está bem-definido

(no sentido que não satisfaz os axiomas da Teoria dos Conjuntos (veja [St]) por
exemplo).
[St] R. Stoll, Set theory and logic, Dover, 1963. para um aprofundamento maior no
assunto.
Seção 2.6 • Para saber mais... 40

Até este momento poderı́amos pensar que entendemos o significado de conjunto

pelo menos intuitivamente. Fazendo um curso de teoria de conjunto a primeira vez,
não perceberı́amos que não há nada de errado em considerar “ o conjunto de todos
os conjuntos” (conjunto universal). De 1895 (criação da teoria dos conjuntos por
Georg Cantor) até 1902 (quando o paradoxo de Russel apareceu) a existência de
um tal conjunto universal era considerada correta. Russel chocou a comunidade
matemática de sua época que a admissão de um conjunto de todos os conjuntos
levaria a uma contradição, este é o paradoxo de Russel.
Apresentaremos este paradoxo na forma de dois lemas aparentemente contra-
ditórios, e dos quais um teorema é consequência.

Lema 2.6.1. Suponhamos que existe um conjunto U de todos os conjuntos. Seja

R = {S ∈ U | S ∈
/ S}. Então R ∈
/ R.

Demonstração. Suponha o contrário, isto é , que R ∈ R. Então pela especificação do

conjunto R temos que R ∈
/ R, o que contraria a hipótese que R ∈ R. A contradição
prova que R ∈
/ R.

Lema 2.6.2. Suponhamos que existe um conjunto U de todos os conjuntos. Seja

R = {S ∈ U | S ∈
/ S}. Então R ∈ R.

Demonstração. Suponha o contrário, isto é , que R ∈

/ R. Então como R ∈ U e
pela especificação do conjunto R temos que R ∈ R, o que contraria a hipótese que
R∈
/ R. A contradição prova que R ∈ R.

Teorema 2.6.1. Não existe um conjunto de todos os conjuntos.

Demonstração. Dos Lemas (2.6.1) e (2.6.2), o conjunto de todos os conjunto não

pode existir. Pois, se este existisse, terı́amos a contradição qeu R ∈ R e R ∈
/ R.

Exemplo 2.6.1. Outra forma de pensar no paradoxo de Russel: Um certo mari-

nheiro barbeiro foi ordenado a somente barbear aqueles marinheiros que não podiam
barbear a si próprios. O Barbeiro pode barbear a si próprio? Bem, se ele pode,
então ele barbea a si mesmo o que é impossı́vel, porque ele foi ordenado a só barbear
quem não pode barbear a si próprio. Se não pode, isto é,se ele não pode barbea a si
próprio, então pela ordem ele teria que barbear a si próprio que é impossı́vel. Como
é que este pobre barbeiro poderia evitar a corte marcial por não seguir
as ordens!
Cap. 2 • Conjuntos 41

Veja também os filmes sobre lógica do “Isto é matemática” no youtube. link:

[Link]
[Link]
[Link]
Seção 2.6 • Para saber mais... 42
 CAPÍTULO 3

Funções

3.1 Conceito e Exemplos

As funções são onipresentes dentro e fora da matemática. As funções modelam o
hábito mental de associar de maneira única várias quantidades ou opções à objetos
em um conjunto. Por exemplo, se V é o conjunto de veı́culos motorizados registrados
no Distrito Federal, o conceito de quilometragem (em uma determinada data) é uma
função f : V → N. Em um determinado momento, um carro tem um único número
associado a ele que descreve a sua quilometragem. Como outro exemplo, se P é o
conjunto de pessoas (vivas ou que já faleceram), o conceito de mãe biológica pode ser
representado como uma função m : P → P tal que m(a) = b significa que a pessoa
b é mãe biológica de a. O conceito de irmão não é uma função porque algumas
pessoas podem ter mais de um irmão.

Definição 3.1.1. Sejam X e Y dois conjuntos. Uma função f : X → Y é uma

associação (lei) que para cada elemento do x ∈ X associa exatamente um elemento
y ∈ Y . Escrevemos y = f (x) se y é associado a x via f . O conjunto X é chamado
de domı́nio de f e o conjunto Y é chamado de contradomı́nio.

Uma função pode ser simbolizada por

f: X → Y
.
x 7→ f (x)

43
Seção 3.1 • Conceito e Exemplos 44

Para abreviar, quando não quisermos explicitar a lei f , usaremos a notação

f : X → Y e nos referimos a f , como sendo a função. O conjunto X é chamado
de domı́nio da função f e f (x) de imagem de x por f . Usaremos também os nomes
aplicação ou correspondência como sinônimos de função.
Quando é dada uma lei x 7→ f (x) que associa aos elementos de X elementos de
Y , para termos certeza que esta lei define uma função f : X → Y , devemos verificar
efetivamente se a cada elemento de X é associado um único elemento de Y . Deve-se
então mostrar que:

a = b, então f (a) = f (b).

Duas funções

f 1 : X1 → Y1 f 2 : X2 → Y1 2
,
x 7→ f1 (x) x 7→ f2 (x)

serão ditas iguais, e escreveremos neste caso f1 = f2 , se X1 = X2 , Y1 = Y2 e

f1 (x) = f2 (x) para todo x ∈ X1 = X2 .

Exemplo 3.1.1. (1) Seja a função

f: Z → Z
.
x 7→ x + 1

Esta função associa a cada número inteiro x o número inteiro f (x) = x + 1. Em

particular, temos que f (0) = 1, f (−1) = 0 e f (1) = 2.

(2) A função f : X → X, que oa elemento x associa o próprio x, é chamada de

função identidade e é denotada por Id, ou mais precisamente IdX , quando queremos
informar o seu domı́nio.

(3) Seja f : X → Y uma função tal que existe b ∈ Y com f (x) = b para todo x ∈ X.
Este tipo de aplicação é chamada de aplicação constante.

(4) Toda função S : N → Aé chamada de sequência em A. Costumamos escrever

sn em vez de s(n). E nos referimos a sequência (sn )n∈N = (s1 , s2 , . . . , sn , . . . )

(5) Seja f : X → Y uma função e A um subconunto de X. Podemos definir uma

Cap. 3 • Funções 45

nova função g : A → Y como a mesma lei de f , isto é, g(x) = f (x) para todo x ∈ A.
Esta função é chamada de restrição de f a Ae é denotada por f|A ou quando não
houver risco de confusão, simplesmente por f .

3.2 Composição de Funções

Definição 3.2.1. Sejam f : X → Y e g : Y → Z funções. A composição de g e f
é a função g ◦ f : X → Z definida para todo x ∈ X por (g ◦ f )(x) = g(f (x)).,

Exemplo 3.2.1. (1) Sejam as funções

f: Z → Z g: Z → Z
, .
x 7→ x + 1 x 7→ x2

Considere as funções f ◦ g e g ◦ f de Z em Z. Temos que

f ◦ g(x) = f (g(x)) = x2 + 1,

enquanto que
g ◦ f (x) = g(f (x)) = (x + 1)2 .

Este exemplo ilustra que em geral temos que f ◦ g 6= g ◦ f .

(2) Seja f : X → Y uma função. Temos que

f ◦ IdX (x) = f (IdX (x)) = f (x),

e que
IdY ◦ f (x) = IdY (f (x)) = f (x).

Logo, qualquer que seja a função f : X → Y , temos que

f ◦ IdX = f e IdY ◦ f = f.

(3) Sejam
f: Z → Z g: Z → Z
, .
x 7→ x + 1 x 7→ x − 1
Temos que g ◦ f = f ◦ g = IdZ .
(4) Seja f : Z → Z dada por f (x) = x3 . Considere a função f 2 = f ◦ f . Temos que
Seção 3.3 • Imagens diretas e Inversas 46

f 2 (x) = f ◦ f (x) = f (f (x)) = (x3 )3 = x9 . Observe que, f 2 (x) não é a mesma coisa
que (f (x))2 , e neste caso (f (x))2 = (x3 )2 = x6 .

O processo de composição pode ser iterado. Dada três funções, f : X → Y, g :

Y → Z e h : Z → W , podemos compor estas funções de dois modos aparentemente
distintos,
h ◦ (g ◦ f ) (h ◦ g) ◦ f.

A seguinte proposição estabelece uma identidade sobre a composição iterada de

funções. Embora simples, ele sustenta as propriedades algébricas desejadas para
muitas situações que veremos mais tarde.

Proposição 3.2.1. Sejam f : X → Y, g : Y → Z e h : Z → W . Então h ◦ (g ◦ f ) =

(h ◦ g) ◦ f .

Demonstração. Seja x ∈ X um elemento qualquer. Então

(h ◦ (g ◦ f ))(x) = h((g ◦ f )(x)) = h(g(f (x)))

= (h ◦ g(f (x))) = ((h ◦ g) ◦ f )(x)

como as funções são iguais para todo elemento de X, então as funções são iguais.

Assim, vemos que o que parecia ser quando considerarmos três funções, na ver-
dade não existe ambiguidade pois os dois modos de compor conduzem ao mesmo
resultado.

3.3 Imagens diretas e Inversas

Dada uma função f : X → Y e um subconjunto A de X, definimos a imagem direta
de A por f como sendo

f (A) = {y ∈ Y | y = f (x) para algum x em A}.

Em particular, f (X) é chamada simplesmente de imagem de f .

Se V é um subconjunt de Y , definimos a imagem inversa de V por f como sendo

f −1 (V ) = {x ∈ X | f (x) ∈ V }.

Segue imediatamente das definições que f (∅) = ∅, f −1 (∅) = ∅ e f −1 (Y ) = X.

Cap. 3 • Funções 47

3.4 Funções Bijetoras e Inversas

Uma função f : X → Y será dita injetora se satisfaz:

∀ x1 , x2 ∈ X, com x1 6= x2 ⇒ f (x1 ) 6= f (x2 ).

Uma forma equivalente de provar injetividade é:

∀ x1 , x2 ∈ X, f (x1 ) = f (x2 ) ⇒ x1 = x2 .

Uma função é dita sobrejetora se todo elemento de Y é imagem por f de algum

elemento de X. Em outras palavras, f é sobrejetora se

∀ y ∈ Y, ∃ x ∈ X tal que y = f (x).

ou equivalentemente, se f (X) = Y .

Uma função é chamada bijeora ou uma bijeção se ela é injetora e sobrejetora.

Exemplo 3.4.1. (1) A função

f: Z → Z
x 7→ x + 1

é injetora e sobrejetora, e portanto é uma bijeção.

(2) A função
f: N → N
n 7→ n2
é injetora e não é sobrejetora.

(3) A função
f: Z → Z
x 7→ 2
não é injetora e nem sobrejetora.
Seção 3.5 • Funções Inversas 48

3.5 Funções Inversas

Dada uma função f : X → Y , diremos que uma função g : Y → X é uma inversa à
esquerda de f , se
g ◦ f = IdX .

Dizemos que g é uma inversa à direita de f , se

f ◦ g = IdY .

Proposição 3.5.1. Uma função é sobrejetora se, e somente se, ela admite inversa
à direita.

Demonstração. Seja f : X → Y uma função sobrejetora. Então para cada y ∈ Y

´podemos escolher pelo menos um x ∈ X tal que y = f (x). Fixe uma tal x para
cada y. Defina g : Y → X talq eu g(y) = x (note que em geral tal função g não
é unicamente determinada, ela o será se f for injetora). Segue então, para todo
y ∈ Y , que
f ◦ g(y) = f (g(y)) = f (x) = y,

Logo, f ◦ g = IdY e portanto g é a inversa a direita de f .

Reciprocamente, suponha que f ◦ g = IdY para alguma função g : Y → X. Seja
y ∈ Y um elemento qualquer, então apliquemos g neste y, e assim temos g(y) = x ∈
X. Agora, apliquemos f neste x = g(y), e segue que f (x) = f (g(y)) = f (x), pois
sabemos que f ◦ g = IdY . E desta forma f é sobrejetora.

Proposição 3.5.2. Uma função é injetora se, e somente se, ela admite inversa à
esquerda.

Demonstração. Seja f : X → Y uma função injetora. Então, cada y ∈ f (X)

determina um único y = f (x) em Y . Defina, então
(
x, se y = f (x);
g(y) =
qualquer valor, se y ∈
/ f (X)

Note que em geral g não é unicamente determinada, ela o será se f for sobrejetora.
Segue, então que
g ◦ f (x) = g(f (x)) = g(y) = x,

para todo x ∈ X, logo g ◦ f = IdX , e portanto g é a inversa à esquerda de f .

Cap. 3 • Funções 49

Reciprocamente, suponha que exista g : Y → X tal que g◦f = IdX . Mostraremos

que f é injetora, então sejam x1 , x2 ∈ X tais que f (x1 ) = f (x2 ), então como
f (x1 ) ∈ Y segue que

g ◦ f (x1 ) = g(f (x1 )) = g(f (x2 )) = g ◦ f (x2 ),

e então x1 = x2 , pois g ◦ f = IdX . E assim f é injetora.

Proposição 3.5.3. Se uma função admite uma inversa à esquerda r uma inversa
à direita, então estas inversas são iguais.

Demonstração. Sejam g1 , g2 : Y → X respectivamente à inversa à direita e uma

inversa à esquerda de uma função f : X → Y . Então:

g1 = IdX ◦ g1 = (g2 ◦ f ) ◦ g1 = g2 ◦ (f ◦ g1 ) = g2 ◦ IdY = g2 .

Definição 3.5.1. Uma função g : Y → X é dita função inversa de f : X → Y

se ela for simultaneamente função inversa à direita e à esquerda de f . Segue ime-
diatamente da Proposição (3.5.3) que se f admite uma inversa, então esta inversa
é única.

A Proposição seguinte caracteriza funções que possuem inversas.

Proposição 3.5.4. Uma função admite função inversa se, e somente se, ela é
bijetora.

Demonstração. Seja f uma função bijetora. Pelas Proposições (3.5.1) e (3.5.2), a

função f admite inversa à direita e à esquerda, logo da Proposiçã (3.5.3) estas são
iguais e define a inversa de f . A reciproca segue segue das Proposições (3.5.1) e
(3.5.2).

3.6 Relação
A noção cotidiana de uma relação entre classes de objetos é muito geral e um tanto
vaga. A matemática requer um conceito tão amplo quanto o de relação, mas com
rigor. Os produtos cartesianos oferecem uma solução simples.
Seção 3.6 • Relação 50

Definição 3.6.1. Uma relação de um conjunto A para um conjunto B é um subcon-

junto R de A×B. Uma relação em um conjunto A é um subconjunto de A×A = A2
Se (a, b) ∈ R, frequentemente escrevemos uma aRb e dizemos que a está relacionado
com b via R.

À primeira vista, essa definição pode parecer estranha. Normalmente pensa-

mos em uma relação como alguma afirmação sobre pares de objetos que é verda-
deira ou falsa. Ao reunir todas as afirmações verdadeiras sobre uma relação em um
subconjunto do produto cartesiano, essa definição dá a noção de uma relação (em
matemática) com o mesmo rigor que as noções de conjuntos e a lógica booleana.

Exemplo 3.6.1. Seja W o conjunto de alunos da UNB matriculados agora seja C

o conjunto de disciplinas oferecidas agora. Seja T a relação de “ter aulas”. Vemos
que T é uma relação de W para C e escrevemos wT c se o aluno w estiver fazendo
a aula c. (A principal função de T é registrar ( observar) um dado ponto dado em
algum momento.)

Exemplo 3.6.2. Considere a relação ≤ em S = {1, 2, 3, 4, 5}. De acordo

com a Definição (3.6.1), a relação ≤ é o subconjunto de S × S, dado por
{(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5)}.

Quando consideramos as relações em conjuntos razoavelmente pequenos, pode-

mos retratá-los de várias maneiras. Ilustramos as quatro descrições a seguir com a
mesma relação R de A = {1, 2, 3, 4, 5} para B = {a, b, c}

Lista. Defina a relação R como um subconjunto de A × B:

R = {(1, b), (1, c), (2, a), (2, b), (4, a), (4, b), (4, c), (5, c)}

Tabela. Em uma tabela com as colunas rotuladas para os elementos de A e as

linhas rotuladas com os elementos de B, marque um X com indicado na tabela( isto
é na coluna x e linha y se xRy). A tabela do emplo acima é:

Matriz. Rotule os elementos de A e B por A = {a1 , a2 , . . . , am } e B =

{b1 , b2 , . . . , bn }. Defina a matriz m × n MR associada a R pela matriz com entradas
mij definidas por: (
1, se bi Raj
mij =
0, em outro caso
Cap. 3 • Funções 51

Para nosso exemplo anterior temos que;

 
0 1 0 1 0
m R = 1 1 0 1 0 
 

1 0 0 1 1

Observe que as descrições do tabela e da matriz são muito semelhantes.

Diagrama de setas. Use um diagrama de Venn com circulo para os elemento de

A e outro para os elementos de B, ilustrando os elementos por pontos. Desenhamos
uma seta de um ponto de um elemento a de A para um ponto b em B se (aRb). O
seguinte diagrama de seta ilusta o nosso exemplo anterior

Observamos que toda função é uma relação, mas nem toda relação é uma função.
A noção de relação engloba a noção de funções. Poderı́amos definir uma função da
seguinte maneira: ntroduzimos funções entre conjuntos antes das relações. Muitas

Uma função f de X para Y é uma relação que satisfaz:

∀x ∈ X, ∃ ! y ∈ Y, xf y
Na notação de função usamos f (x) em vez de xf y. Agora vemos as relações
como uma generalização de funções.
Seção 3.6 • Relação 52

Exemplo 3.6.3. Seja P o conjunto de pessoas vivas e seja E o conjunto de contas

de e-mail ativas. Seja R a relação de P para E, então pRe representa a pessoa p
possui o e-mail e. Algumas pessoas pessoas possuem várias contas de e-mail, então
R não poderia ser uma função. Mas também, R também deixa de ser uma função
porque algumas muitas pessoas não tem sua própria conta de e-mail. Por outro lado,
observe que algumas contas de e-mail são usadas por mais de uma pessoa, portanto,
não seria possı́vel criar uma função de E a P que descrevesse possuir um e-mail
próprio.

Definição 3.6.2. Sejam A, B, e C conjuntos. Sejam R1 uma relação de A para B

e R2 uma relação de B para C. A composição de R2 com R1 é uma relação de A
para C tal que:

aRb ⇐⇒ ∃ b ∈ B, aR1 b e bR2 c.

Definição 3.6.3. Se R é uma relação de A para B, então a relação inversa R−1 é

uma relação de B para A tal que:

aR−1 b ⇐⇒ aRb.

Certas classes de relações de conjunto A para ele mesmo desempenham papéis

importantes devido a uma combinação de propriedades especı́ficas. Uma relação
de um conjunto A sobre si mesmo é chamada de relação em A. Na próxima
seção, introduzimos relações de equivalência, que é essencial na álgebra abstrata.
No entanto, listamos aqui abaixo algumas das propriedades para relações em um
conjunto A que geralmente são de interesse particular.

Definição 3.6.4. Seja R uma relação sobre um conjunto A. A relação R é chamada

1. reflexiva se ∀ a ∈ A, aRa;

2. Simetrica se aRb ⇒ bRa;

3. Antisimetrica se aRb e bRa ⇒ a = b;

4. Transitiva se aRb e bRc ⇒ aRc.

Exemplo 3.6.4. Seja L o conjunto de retas em R2 . A noção de perpendiculari-

dade ⊥ é uma relação em L. Essa relação é simétrica, mas não satisfaz as outras
prpriedades descritas na Definição (3.6.4).
Cap. 3 • Funções 53

Exemplo 3.6.5. Seja B o conjunto de tipos de sangue. Codifique os tipos

sanguı́neos por B = {o, a, b, ab} e considere a relação doador →, de forma que
t1 → t2 significa (desconsiderando todos os outros fatores) que alguém com tipo
sanguı́neo t1 pode doar para alguém com tipo sanguı́neo t2 . Considere como um
subconjunto de B 2 , a relação doador é:

{(o, o), (o, a), (o, b), (o, ab), (a, a), (a, ab), (b, b), (b, ab), (ab, ab)}.

Não é difı́cil verificar exaustiva ou logicamente que → é reflexiva, antissimétrica e

transitiva mas não simétrica.

3.7 Relação de equivalência

Uma relação de equivalência é uma generalização do conceito de igualdade. Grossei-
ramente falando,uma relação de equivalênacia modela mentalmente uma noção de
semelhança ou similaridade, ou seja, dois elementos estão em relação um ao outro
se forem “iguais sob uma certa perspectiva”’. Este conceito é onipresente em toda
a matemática e ocorre com frequência na álgebra.

Definição 3.7.1. [Relação de equivalência] Uma relação de equivalência sobre um

conjunto A é uma relação denotada por ¬ que é reflexiva, simetriaca e transitiva

Exemplo 3.7.1. Seja A um conjunto qualquer. A relação de igualdade é uma

relação que é claramente, reflexiva, simetrica e transitiva. Em particular, a = é uma
relação de equivalência. Dois elementos são relacionados via = se les representm o
mesmo objeto.

Exemplo 3.7.2. Seja A o conjunto de todas as retas de R3 . Considere a relação

de paralelismo, denotada por k. Esta relação é reflexiva, simétrica e transitiva e
portanto é uma relação de equivalência sobre A. De uma pespectiva intuitiva que
todas as retas que são pararelas tem a mesma direcão.

Exemplo 3.7.3. Defina B como interseções em Brası́lia e defina a relação R em B

como sendo “distância curta”. Do jeito que colocamos , isto não fica bem definido,
então vamos dizer que duas interseções em Brası́lia estão em “distância curta” se
e somente se, se estiverema mesno de 2 kilometros ou menos uma da outra. Essa
relação é reflexiva e simétrica, mas não transitiva. Se três interseções a, b e c estão
Seção 3.7 • Relação de equivalência 54

sucessivamente em linha reta com a e b a dois kilometros de distância e b e c também

a dois kilometros de distância, então a e c estão a quatro kilometros de distância.
Esta relação não é uma relação de equivalência.

Exemplo 3.7.4. Seja X = {1, 2, 3, . . . , 10} e considere S = P (X). Para as duas

relações a seguir, discutimos se elas são relações de equivalência.

• A¬1 B se |A| = |B|. Esta é uma relação de equivalência. Dois conjuntos são
equivalentes entre si se tiverem a mesma cardinalidade.

• As ∈2 B se 1 ∈ A ∩ B. A relação ¬2 é simétrica e transitiva, mas não é

reflexiva. Um conjunto que não contém 1 não está em relação a si mesmo.
Conjuntos que estão em relação uns aos outros em ¬2 têm a propriedade se-
melhante de todos conterem o elemento 1, mas parece natural impor que em
qualquer noção de igualdade, um elemento deve ser “igual” a si mesmo.

Visto que uma relação de equivalência fornece em um certo sentido uma alguma
noção de semelhança entre os elementos de um conjunto, é natural reunir elementos
semelhantes em classes. Essas classes formalizam a propriedade de igualdade.
Agora definiremos o que é uma classe de equivalência

Definição 3.7.2. [Classe de equivalência] Seja ¬ uma relação de equivalência em

um conjunto A. Para a ∈ A, definimos a classe de equivalência de a por

a = {b ∈ A | b¬a}.

Um subconjunto B ⊆ A é chamado de classe de equivalência se B = a para algum

a ∈ A. Um elemento a de uma classe de equivalência B é chamado de representante
de B.
Chamamos um subconjunto T de A um conjunto completo de representantes
distintos da relação de equivalência ¬ se qualquer classe de equivalência U tem que
U = a, para algum a ∈ T e para quaisquer a1 , a2 ∈ T , a1 = a2 implica que a1 = a2 .

Definição 3.7.3. Seja A um conjunto e ¬ uma relação de equivalência em A. O

conjunto das classes de equivalência em A é chamado de conjunto quociente de
A pela relação de equivalência ¬ e é denotado por A/¬.

O conjunto quociente A/¬ é um primeiro exemplo do que do que chamaremos

de objeto quociente. Como veremos adiantre ao considerarmos uma dada estrutura
Cap. 3 • Funções 55

algébrica, se começarmos com um objeto O que também tem uma relação de equi-
valência ¬ tal que O/¬ é novamente um objeto com a mesma estrutura algébrica,
chamamos O/¬ um objeto quociente.
Com um conjunto A, qualquer relação de equivalência em A fornece um conjunto
quociente. No entanto, com outras estruturas algébricas, nem todas as relações de
equivalência são tais que o conjunto de classes de equivalência produz naturalmente
outro objeto com a mesma estrutura algébrica. Portanto, o estudo de objetos quo-
cientes exigirá alguns cuidados.
Observamos que existe uma bijeção entre A/¬ e o conjunto completo de repre-
sentantes T da relação de equivalência ¬ através da função

φ : T → A/¬
a 7→ a

No entanto, não consideramos esses conjuntos iguais, uma vez que seus objetos
são diferentes.

Observação 3.7.1. A noção de cardinalidade (quantidade) de subconjuntos de um

determinado conjunto pode agora ser descrita da seguinte maneira. Fixe um con-
junto A finito ou infinito e considere a relação de equivalência ¬ em P (A) por

X¬Y se, e somente se houver uma bijeção entre X e Y.

Não é difı́cil verificar que se trata de um relação de equivalência em P (A). Se

representamos a classe de X por |X| em vez de X. Agora a cardinalidade de X fica
bem definida , e nada mais é que um elemento de P (A)/¬, mesmo que X não seja
um conjunto finito.

Exemplo 3.7.5. [Espaço Projetivo] Seja R3 o conjunto de todas as retas e considere

sobre a relação de equivalência paralelismo k sobre R3 . Se L é uma reta em R3 , então
L é o conjunto de todas as retas paralelas à L. Existem outras maneiras de entender
o espaço projetivo. Por exemplo toda reta em R3 é paralela a uma única reta que
passa pela origem. Os vetores direções possı́veis para estas retas que passam na
origem consistem de vetores não nulos, então considere o conjunto R3 \ {(0, 0, 0)}.
Duas retas que passam pela origem são as mesmas se, e somente se, seus vetores
direções diferem por por um múltiplo não nulo. Portanto, definimos a relação de
equivalência ¬ sobre R3 \ {(0, 0, 0)} por:
Seção 3.7 • Relação de equivalência 56

→
− →
− →
−
a ¬ ab ⇔ →
−
a = λ b , para algum λ ∈ R \ {0}.

Usando está notação para vetores, temos que R3 \{(0, 0, 0)}/¬ = RP2 é chamado
espaço projetivo e é denotado por RP2 .

Exemplo 3.7.6. [Númerops racionais] Considere o conjunto dos pares ordenados

S = Z × Z∗ e a relação ¬ sobre S dada por:

(a, b)¬(c, d) ⇔ ad = bc.

Deixamos como exercı́cio a verificação que ¬ é uma relação de equivalência sobre

S. O espaço quciente S/¬ é uma definição rigorosa para o conjunto Q dos números
racionais. A relacão de equivalência é precisamente a condição que é dada quando
duas frações são consideradas iguais. Portanto, a notação de fração que estamos
a
acostumados b
para números racionais representa a classe de equivalência (a, b)
sobre a relação acima ¬.

Observação 3.7.2. Quando trabalhamos com funções cujo domı́nio são conjunto
quocientes, é natural desejar definir uma função sobre a classe de equivalência a
partir da escolha de um representante desta classe. Mais precisamente, Se S e T
sãop conjuntos e ¬ é uma relação de equivalência sobre S, e desejamos definir uma
função

f : S/¬ → T
a 7→ F (a),
onde f : S → T é uma função qualquer. A função dada em (3.7.2) nem sempre
produz uma função. Dizemos que (3.7.2) define uma função, isto é, é uma função
bem definida se:
a¬b, então f (a) = f (b).

Assim, usando qualquer representante de a terá o mesmo valor para F (a).

Agora, usaremos o exemplo (3.7.6) para ilustrar, considere a relação de equi-
a
valência sobre Z × Z∗ descrita no exemplo (3.7.6). Usaremos a notação tı́pica b
para denotar a classe de equivalência do elemento (a, b) ∈ Z × Z∗ ao invés de (a, b).
Suponha que f é a função dada por

f : Q/¬ → Z
a
b
7→ a + b,
Cap. 3 • Funções 57

Esta função não está bem definida, e portanto não é uma função, pois por exemplo
1
2
= 36 , entrentanto 1 + 2 = 3 e 3 + 6 = 9. Assim, dependendo do representante
a
escolhido para a frção b
, o valor a + b muda e sto significa que f não está bem
definida e portanto não é uma função.
Poderı́amos contornar este problema de definir corretamente as funções cujo
domı́nio é um conjunto quociente, simplesmente escolhendo um representante es-
pecı́fico de cada classe de equivalência. Por exemplo, considerando a mesma f (3.7.2)
a
e definimos f (q) = a + b, onde q = b
é expressa na forma reduzida onde b > 0.
Esta abordagem às vezes não é tratável nem desejável. Caso contrário, podemos
definir uma função f em termos de um representante de uma classe de equivalência
e provar que é bem definido, mostrando que sua imagem sob f é a mesma para todos
os elementos em qualquer classe de equivalência.
Por exemplo, considere agora a função

g : Q/¬ → Q
a 2 +b2
b
7→ a ab .

Mostraremos que g é bem definida, isto é, que ela não depende da escolha do repre-
a a
sentante do elemento b
considerado para representar a classe. Sejam então b
= dc ,
então temos que (a, b)¬(c, d) (veja Exemplo (3.7.6)) e isto siginifica que ad = bc.
Agora, calculemos o valor de f nestes representantes:

2 2
c2 +d2
cd
= b2 ( c b+d
2 cd
)
estas frações satisfazem ¬
a2 d2 +b2 d2
= bad2
já que bc = ad
a2 +b2
= ba
já que a última fração satisfaz ¬.
Portanto a fórmula para g independe da esolha do representante para a fração
a
b
.

A Observação (3.7.2) permite-nos fornecer uma outra propriedade bonito sobre

um conjunto quociente. Seja ¬ uma relação de equivalência sobre um conjunto A e
seja π : A → A/¬ a “projeção”definida por π(a) = a. PAra qualquer conjunto X e
para qualquer função f : S → X tal que a¬b implica f (a) = f (b), existe uma única
função f˜ : A/¬ → X tal que π ◦ f˜ = f . Essa função é simplemente definida por
f˜(a) = f (a) e é fácil ver que f˜ é bem definida, pois f (a) = f (b) sempre que a¬b.
Frequentemente expresamos a relação π ◦ f˜ = f dizendo que o seguinte diagrama de
conjuntos e funções é comutativo.
Seção 3.8 • Partição 58

A
π / A/¬

f˜
f


X

3.8 Partição
Seja ¬ uma relação de equivalência sobre um conjunto A. Para qualquer dois le-
mentos a, b ∈ S, por definição a ∈ b se, e somente se, a¬b. Portanto, como ¬ é
simétrica, isto implica que b¬a e portanto a = b. Pela transitividade, se a ∈ b, então
c¬a implica que c¬b, então a ∈ b. Logo, a ⊆ b. Assim, provamos que as seguintes
afirmações sao logicamente equivalentes:

a ∈ a ⇔ a ⊆ b ⇔ b ∈ a ⇔ b ⊆ a ⇔ a = b.

Esta ovbservação prova a seguinte proposição.

Proposição 3.8.1. Seja A um conjunto munido de uma relação de equivalência ¬.

Então:

1. Classes de equivalência distintas são disjuntas;

2. A união das classes de equivalências é igual ao conjunto A.

Demonstração. (1) Suponha que a ∩ b = ∅. Então existe c ∈ a ∩ b, assim c ∈ a e

c ∈ b. Portanto, a = c = b. Logo, se duas classes de equivalências se interceptam
então elas são iguas.

(2) Seja T um conjunto completo de representantes para as classes laterais de ¬

sobre A. Obviamente, como a ∈ a, todo elemento de A está em alguma classe de
equivalência. Assim, temos que

A = ∪ a = ∪ a.
a∈A a∈T

E o resultado segue.

A propriedade dada na Proposição (3.8.1) tem um nome na teoria dos conjuntos.

Cap. 3 • Funções 59

Definição 3.8.1. Seja A um conjunto. Uma coleção A = {Ai }i∈I de subconjuntos

de A é chamada uma partição de A se se:

1. Ai ∩ Aj 6= ∅ ⇒ i = j e;

2. ∪ Ai = A.
i∈I

Figura 3.1: Partição de um conjunto.

As partições do conjunto podem ser vistas através de um diagram semelhante

ao da Figura (??). Neste figura o conjunto A foi particionado nos seguintes sub-
conjuntos: {a1 }, {a2 , a3 , a4 }, {a7 , a8 , a9 } e {a5 , a6 , a10 , a11 }. Uma partição de A é
em particular suconjunto de p(A). Um subconjunto geral de P (A) pode conter su-
conjuntos de A que tenham e podem não cobrir todo o conjunto A. Portanto, um
diagrama como o da Figura (??) não seria suficiente para visualizar um subconjunto
geral de P (S).
O conceito de partição simplesmente modela a construção mental de subdividir
um conjunto em partes sem perder nenhum elemento do conjunto e sem sobreposição
das partes. As partições e as relações de equivalência estão intimamente relaciona-
das. A Proposição(3.8.1) estabelece que o conjunto de classes de equivalência dis-
tintas de uma relação de equivalência em A forma uma partição de A. A proposição
a seguir estabelece a recı́proca.

Proposição 3.8.2. Seja A = {Ai }i∈I uma partição de um conjunto A. Defina a

relação ¬ sobre A por:

a¬b ⇒ ∃ i ∈ I com a ∈ Ai e b ∈ Ai .

Então ¬ é uma relação de equivalência. Além disso, os conjuntos em A são classes

de equivalência distintas de ¬.
Seção 3.8 • Partição 60

Demonstração. Seja a ∈ A um elemento qualquer. Como A é uma partição, então

a ∈ Ai para algum i ∈ I. Portanto, a¬a e então ¬ é reflexiva.
Suponha que a¬b. Então para algum i ∈ I, temo que a ∈ Ai e b ∈ Ai . Clara-
mente, isto significa que b¬a, mostrando que ¬ é simétrica.
Suponha agora que a¬b e b¬c. Então temos que existe i ∈ I tal que a ∈ Ai
e b ∈ Ai . Da mesma forama temos que existe j ∈ I tal que b ∈ Aj e c ∈ Aj .
Entretanto, note que b ∈ Ai ∩ Aj , então temos que Ai ∩ Aj 6= ∅. Mas por definição
de partição, segue que i = j e então a ∈ Ai e c ∈ Ai e assim a¬c. E isto mostra que
¬ é transitiva. Portanto, provamos que ¬ é uma relação de equivalência sobre A.
Seja Ai um conjunto deA e seja a um elemento quelauqer em Ai . Pela construção,
a = Ai e então os elementos de A são precisamente as classes de equivalência de
¬.

Exemplo 3.8.1. Considere o conjunto A = {1, 2, 3, 4, 5, 6, 7, 8}. Os seguintes são

exemplos de partições sobre A:

{{1, 4, 5}, {2, 6, 7}, {3, 8}}, {{1, 3, 5, 7}, {2, 4, 6, 8}}, {{1, 2, 3, 4, 5, 6, 7, 8}}.

Entretanto, {{1, 3, 5}, {2, 8}, {4, 7}} não é uma partição poisa união deste sub-
conjuntos não contem o 6. Por outro lado, {{1, 2, 3, 5}, {3, 6, 8}, {4, 6, 7}} não é
uma partição pois alguns deste subconjuntos tem interseção não vazia, a saber
{1, 2, 3, } ∩ {3, 6, 8} = {3} e {3, 6, 8} ∩ {4, 6, 7} = {6}.

Exemplo 3.8.2 (partição na esfera em R3 ). Considere a esfera unitária em R3 , que

denotamos por S2 . Considere a partição A dada por :

A = {(p, −p) | p ∈ S2 }.

Esta partição consite dos pares de pontos que são diametricamente opostos um
do outro. Pela Proposição (3.8.2), existe uma única relaçào de equivalência ¬ so-
bre S2 que tem A como um conjunto de classes de equivalências distintas. Note
que, qualquer reta que passa pela origem intercepta S2 em dois pontos diametrical-
mente opostos. Portanto, o conjunto quociente S2 /¬ é igual ao plano projetivo RP2
construı́do no Exemplo (3.7.5).
Cap. 3 • Funções 61

3.9 Ordem Parcial

Como foi dito anteriormente as relações de equivalência como uma generalização da
noção de igualdade. As relações de equivalências fornecem um modelo mental para
chamar certos objetos em um conjunto de equivalente. Da mesma forma, o conceito
de uma ordem parcial generaliza a noção de desigualdade em R para um modelo
mental de ordenar objetos em um conjunto.

Definição 3.9.1. Uma ordem parcial em um conjunto S é uma relação 4 que é

reflexiva, antissimétrica e transitiva. Um par (S, 4), onde S é um conjunto e 4 é
uma ordem parcial em S, é freqüentemente chamado de forma sucinta de “poset”.

O nome poset, que abrevia conjunto parcialmente ordenado, ”enfatiza a perspec-

tiva de que posets formam uma estrutura algébrica. Como primeiro exemplo de uma
estrutura não trivial, destacamos que um poset consiste em um conjunto equipado
com uma relação com certas propriedades especificadas. Muitos outras estruturas
algébricas serão semelhantes à Definição .
Motivados pelas notações para desigualdades sobre R, usamos o sı́mbolo 4 para
significar

x 4 y =⇒ x 4 y e x 6= y

e o sı́mbolo 64 para significar que não é verdade que 4.

Exemplo 3.9.1. Considere a relação ≤ em R. Para todo x ∈ R, x ≤ x, então ela

é reflexiva. Para todos x, y ∈ R, se x ≤ y e y ≤ x, então x = y e, portanto, é
anti-simétrico. Também é verdade que x ≤ y e y ≤ z implica que x ≤ z e, portanto,
é transitivo. Assim, a desigualdade ≤ em R é uma ordem parcial.

Observe que ≥ também é uma ordem parcial em R, mas as desigualdades estritas

< e > não são. A desigualdade < não é reflexiva embora seja antissimétrico e
transitivo. (< é anti-simétrico porque não existe nenhum x, y ∈ R tal que x < y e
y < x então a declaração condicional “x < y e y < x implica x = y ”é trivialmente
satisfeito.)
As relações de equivalência generalizam a = e, portanto, afrouxam algumas pro-
priedades da =. De maneira semelhante, embora modelado após a relação ≤ de em
R, uma ordem parcial em um conjunto S tem um número de possibilidades. Por
Seção 3.9 • Ordem Parcial 62

exemplo, em um poset geral (S, 4), dados dois elementos arbitrários a, b ∈ S, é

possı́vel que nem a 4 b e nem b 4 a.

Definição 3.9.2. Seja (S, 4) um poset. Se por algum par {a, b} de elementos dis-
tintos, ou a 4 b ou b 4 a, então dizemos que a e b são comparáveis; caso contrário,
a e b são chamados de incomparáveis. Uma ordem parcial na qual cada par de
elementos é comparável é chamada de ordem total.

Os posets (N, ≤) e (R, ≤) são ordens totais. Muitos posets não são ordem totais
como os seguintes exemplos ilustram.

Exemplo 3.9.2. Considere a relação “doador” → denido sobre o conjunto dos tipos
sanguı́neos B = {o, a, b, ab} como vista no Exemplo (3.6.5). vimos que esta relação
é reflexiva, antissimétrica e transitiva. Isto mostra que (B, →) é um poset. Observe
que a e b não são comparáveis, o que significa que nenhum deles pode doar para o
outro.

Exemplo 3.9.3. Seja S qualquer conjunto. A relação subconjunto j em P (S)

é uma ordem parcial. Na ordem parcial, muitos pares de subconjuntos em S são
incomparáveis. De fato, dois subconjuntos A e B são incomparáveis se, e somente
se, A \ B e B \ A não forem ambos vazios.

Exemplo 3.9.4. Considere a relação 4 em R2 definida por

(x1 , y1 ) 4 (x2 , y2 ) ⇔ 2x1 − y1 < 2x2 − y2 ou (x1 , y1 ) = (x2 , y2 )

Que (x1 , y1 ) 4 (x2 , y2 ) está embutido na própria definição, então 4 é reflexiva. É

impossı́vel para 2x1 −y1 < 2x2 −y2 e 2x2 −y2 ≤ 2x1 −y1 , então o único jeito de ocorrer
(x1 , y1 ) 4 (x2 , y2 ) e (x2 , y2 ) 4 (x1 , y1 ) é quando (x1 , y1 ) = (x2 , y2 ). Finalmente, a
relação também é transitiva, de modo que 4 é uma ordem parcial em R2 .
Neste poset em R2 , dois elementos (x1 , y1 ) e (x2 , y2 ) são incomparáveis ??se, e
somente se, 2x2 −y2 < 2x1 −y1 e (x1 , y1 ) 6= (x2 , y2 ), a saber, eles são pontos distintos
na mesma reta com inclinação 2.
Além da dicotomia entre posets totalmente ordenados e ordens parciais com
elementos incomparáveis, há uma outra dicotomia que já aparece ao comparar as
propriedades dos posets (N, ≤) e (R, ≤). Em (R, ≤) dado qualquer x ≤ y com x 6= y,
sempre existe um elemento z tal que z 6= x e z 6= y com x ≤ z ≤ y. Em contraste,
em (N, ≤), por exemplo 2 ≤ 3, mas para todo z ∈ N, se 2 ≤ z ≤ 3, então z = 2 ou
z = 3.
Cap. 3 • Funções 63

3.9.1 Reticulado

Para conjuntos parcialmente ordenados com um número relativamente pequeno de

elementos, é possı́vel visualizar facilmente a relação por meio de um diagrama de
Hasse.
Seja (S, 4) um poset em que S é finito. Em um diagrama de Hasse, cada
elemento de S corresponde a um ponto no plano, com os pontos colocados sobre o
plano de modo que se a 4 b, então b aparece acima de a desenhado no plano. Os
pontos do diagrama de Hasse também são chamados de nós ou vértices. Finalmente,
desenhamos uma aresta entre dois pontos (correspondendo a) a e b com b acima de
a se b for um sucessor imediato de a. Uma cadeia de ordem parcial aparece no
diagrama de Hasse como um caminho ascendente.

Figura 3.2: Diagrama de Hasse para relação doador tipo sanguı́neo.

A Figura (3.2) fornece o diagrama de Hasse para a relação doadora descrita no

Exemplo (3.9.2). O diagrama de Hasse de um poset (S, 4) não tem uma aresta
entre cada par (p, q) onde p 4 q. O diagrama não precisa indicar que p 4 p para
todos os elementos em S desde reflexividade é parte da definição. Além disso, o
diagrama não mostra quaisquer arestas que existiriam em virtude de transitividade.
Por exemplo, na Figura (3.2), o diagrama não mostra uma aresta explı́cita entre o
e ab, mas lemos que o → ab porque há uma cadeia de o até ab.
Os diagramas de Hasse permitem uma fácil visualização das propriedades do
poset. Por exemplo, um poset irá ser um reticulado se, e somente se, tomando
quaisquer dois pontos p1 e p2 no diagrama, existe uma caminho ascendente de p1
que se cruza com um caminho ascendendo de p2 (existência do menor cota superior)
e uma cadeia descendente de p1 que se cruza com uma cadeia descendente de p2
(existência do maior cota superior). A Figura (3.3) ilustra três diferentes reticulados.
Seção 3.10 • Cardinalidade 64

Figura 3.3: Exemplos de Reticulados

3.10 Cardinalidade
Concluı́mos este capı́tulo com uma breve discussão sobre um conceito de tamanho
para conjuntos. Curiosamente, as propriedades das funções entre os conjuntos são
a chave tornar preciso este conceito.

Definição 3.10.1. Dizemos que dois conjuntos A e B têm a mesma cardinalidade

se existe uma bijeção f : A → B. Escrevemos |A| = |B|. Se não existe uma bijeção
entre A e B, então escrevemos |A| =
6 |B|. Se houver uma injetiva f : A → B, então
escrevemos |A| ≤ |B|. Se |A| ≤ |B| e |A| =
6 |B|, então escrevemos |A| < |B|.

Definição 3.10.2. Um conjunto A é denominado finito se existe uma bijeção de

A em {1, 2, . . . , n}, onde n é um número inteiro positivo. Neste caso, escrevemos
abreviadamente |A| = n. Se um conjunto A não é finito, é denominado infinito.

Definição 3.10.3. Um conjunto infinito A é chamado enumerável (contável) se

existe uma bijeção f : A → N∗ . Nesse caso, denotamos sua cardinalidade por ℵ0
e escrevemos |A| = ℵ0 . E em caso contrário dizemos que A é um conjunto não
enumerável ( isto é se não for contável).

A definição do termo “enumerável” modela o processo mental de listar todos

os elementos no conjunto A e rotulá-los como “primeiro”(1), “segundo” (2), “ter-
ceiro”(3) e assim por diante. A função f : N → N∗ definida por f (n) = n + 1 de-
ternima uma bijeção entre N e N∗ então N é enumerávell. Freqüentemente, mostrar
que alguns outros conjuntos são enumerável requer um pouco mais de criatividade.

Proposição 3.10.1. O conjunto dos números inteiros Z é enumerável.

Demonstração. Considere a função f : Z → N definida por


1  m , se n é par
f (n) = d|2n + |e = 2
2 − m+1 , se n é ı́mpar
2
Cap. 3 • Funções 65

Esta função é bem definida e é uma bijeção.

Nos sı́mbolos de =, ≤ e < são obviamente uma reminiscência de desigualdades

sobre os inteiros. No entanto, precisamos ter cuidado para não usar a analogia desses
sı́mbolos e assumir que algo é verdadeiro simplesmente por analogia.
Por exemplo, o fato de que |A| ≤ |B| e |B| ≤ |A| implica que |A| = |B| é o
Teorema de Schröder-Bernstein. Considere também a Lei da Tricotomia, que afirma
que para quaisquer dois conjuntos A e B, então exatamente uma das seguintes
afirmações é verdadeira:

|A| < |B|, |A| = |B|, |A| > |B|.

A Lei da Tricotomia é equivalente ao Axioma da Escolha.

Mencionamos sem prova alguns resultados interessantes sobre cardinalidades de
conjuntos. A Proposição (3.10.1) mostra que Z = N. Não é difı́cil mostrar que
|N>0 | = |Q>0 | e daı́ conclua que Q é enumerável. Por outro lado, |N| < |R|. Esta
prova segue mostrando que existe uma bijeção entre R e PN junto com o teorema
de Cantor.

Teorema 3.10.1 (Cantor). Se X é um conjunto, então |X| < |P(X)|

Enfatiza a noção de uma estrutura algébrica e salientamos que conjuntos, junta-

mente com funções entre conjuntos, fornecem um primeiro exemplo de uma estrutura
algébrica. Podemos considerar a estrutura dos conjuntos como a estrutura algébrica
mais simples possı́vel. As estruturas algébricas posteriores envolvem conjuntos com
propriedades, operações e relações adicionais sobre eles. Essas estruturas virão com
suas próprios aplicações e propriedades interessantes, bem como seu interesse abs-
trato.
Para saber mais sobre a Teoria axiomatica dos conjuntos, veja:

[1] Murray Eisenberg. Axiomatic Theory of Sets and Classes. Holt, Rinehart and
Winston, New York, 1971.
Seção 3.10 • Cardinalidade 66
 CAPÍTULO 4

Os números inteiros

Iniciaremos uma definição estrutural para o conjunto dos números inteiros, isto é
um conjunto de axiomas definido o conjuntos dos números inteiros. Exitem algumas
formulações diferentes, mas todas elas são equivalentes. Um desses conjuntos de
axiomas é conhecido como Axiomas de Peano, levando o sobrenome de Giuseppe
Peano, que em 1889 formulou uma abordagem axiomática dos números naturais.
Começamos falando dos números inteiros, com o intuito de ganhar tempo para a
construção de resultados fundamentais. Escolhemos a apresentação dos números
inteiros a seguir visto que quase todos os axiomas são bem conhecidos até por
crianças do ensino fundamental. E de fato, o único axioma que não é aparentemente
claro é o princı́pio da boa ordenação.

4.1 Axiomas para o conjunto dos números intei-

ros
Estudaremos agora um estrutura algébrica que já nos é familiar de longa data, a sa-
ber a estrutura algébrica do conjunto Z dos números inteiros. Por estrutura algébrica
do conjunto Z entedemos o conjunto de propriedades dos números inteiros que di-
zem respeito às duas operações usuais, a “adição” e a “multiplicação”, e também a
ordem definida no conjunto Z pela relação < (chamada de relação “menor”).
Introduziremos uma adição e uma multiplicação sobre o conjunto Z de modo
axiomático, isto é, a partir de um conjunto de axiomas e postulados (proprieda-

67
Seção 4.1 • Axiomas para o conjunto dos números inteiros 68

des básicas supostas a priori que caracterizam essas operações em Z). E a partir
deste conjunto de axiomas deduziremos outras propriedades, bastante elementares
e usadas a longo tempo por todos nós, mas é importante o leitor demonstrá-las pelo
menos uma vez na sua vida.
Adimitamos axiomaticamente a existência do conjunto Z dos números inteiros,
havendo em Z dois elementos destacados e distintos, a saber 0 zero e 1 um. Adi-
mitamos que sejam definidas em Z

+ : Z+Z → Z · : Z×Z → Z
e
(x, y) 7→ x + y (x, y) 7→ x · y
onde a adição associa a cada par (x, y) de inteiros um único inteiro x + y, chamado
de soma de x e y, e a multiplicação associa a cada par (x, y) de inteiros um único
inteiro x · y, chamado de produto de x e y (que podemos denotar por simplicidade
por xy).
Assumiremos que as operações de adição e de multiplicação satisfazem as segun-
tes propriedade:

(A1) x + (y + z) = (x + y) + z (Associatividade);

(A2) x + y = y + x (Comutatividade);

(A3) x + 0 = 0 + x = x ( 0 é o elemento neutro da adição);

(A4) Existe um elemento que denotaremos por −x em Z, chamado de oposto de x

ou inverso de x com respeito á adição, satisfazendo: x + (−x) = (−x) + x = 0;

(M1) x(yz) = (xy)z ( Associatividade);

(M2) xy = yx (Comutatividade);

(M3) x.1 = 1.x = x (1 é o elemento neutro da multiplicação em Z);

(D) x(y + z) = xy + xz ( distributividade da multiplicação relativamente a adição);

Podemos usar estes axiomas e as propriedades usuais da igualdade para obter

outras propriedades dos números inteiros.

Teorema 4.1.1. Para cada par x, y e z de inteiros, valem as seguintes propriedades:

1. x + y = x ⇒ y = 0 (O elemento neutro da adição é único);

Cap. 4 • Os números inteiros 69

2. x + y = 0 ⇒ y = −x ( O elemento oposto é único);

3. x + y = x + z ⇒ y = z (Lei do cancelamento da adição);

4. −(−x) = x;

5. −(x + y) = −x − y (Note que: −x − y significa (−x) − y, isto é, (−x) + (−y));

6. x.0 = 0;

7. (−x)y = −xy;

8. (−x)(−y) = xy;

9. (x − y)z = xz − yz

Demonstração. (1) Se tivemos um elemento y é elemento neutro da adição, então

pela proprieade (A3) temos que x + y = x, então pela pela condição (A4), existe
−x, e assim usando (A1), (A4) segue (−x) + (x + y) = (−x) + x, e então

(−x) + x + y = 0 ⇒ 0 + y = 0 ⇒ y = 0.

(2) Dado um elemento x qualquer, se tivemos que um outro elemnto y é elemento

oposto de x com respeito a adição, então pela proprieade (A4) temos que x + y = 0,
então temos (−x) + (x + y) = (−x) + 0. Pelos axiomas (A1), (A3) e (A4) segue que

(−x) + x + y = −x ⇒ 0 + y = −x ⇒ y = −x.

(3) Se tivermos a igualdade x + y = x + z, então do axioma (A3), existe o elemnto

simétrico de x, e então adicionando este elemento segue que (−x) + (x + y) =
(−x) + (x + z). Pelos axiomas (A1), temos que

((−x) + x) + y = ((−x) + x) + z ⇒ 0 + y = 0 + z ⇒ y = z.

(4) Usando o axioma (A3) o elemento (−x) tem oposto e este é denotado por −(−x) e
vale que −(−x)+(−x) = 0. Logo, somando-se x segue que [−(−x)+(−x)]+x = 0+x.
Pelos axiomas (A1) e (A3), temos que

−(−x) + [(−x) + x] = 0 + x ⇒ −(−x) + 0 = x ⇒ −(−x) = x.

Seção 4.1 • Axiomas para o conjunto dos números inteiros 70

(5) Queremos mostrar que −x − y é o oposto do elemento x + y, então se isto é

verdade pelo axioma (A3) a soma de (x + y) com −x − y deve ser zero. De fato,

(x+y)+[(−x)+(−y)] = (y+x)+[(−x)+(−y)] = y+[x+(−x)]+(−y) = y+(−y) = 0,

usamos na igualdade anterior (A2), (A1), (A4) e finalizamos com (A4) novamente e
obtemos o desejado.
(6) Queremos mostrar que x.0 = 0, suponhamos que seja um valor a inicialmente,
isto é a = x.0 = x.(0 + 0) = x.0 + x.0 = a + a, onde usamos sucessivamente nas
igualdades suposição, (A3), (D) e a suposição novamente. Logo, usando agora o
item (3) deste Teorema temos que a = 0, o que acarreta x.0 = 0.
(7) Observe que podemos escrever 0 = 0.y = ((−x) + x).y = (−x).y + xy, onde
usamos respectivamente nas igualdades o item (6) do Teorema, os axiomas (A4) e
(D), assim da última igualdade temos que 0 = (−x).y + xy, o que significa que pelo
item 1 do Teorema que (−x)y é o oposto de (xy), isto é, (−x)y = −(xy).
Os item (9) e (10) são deixados como exercı́cio para o leitor, e na verdade encoraja-
mos o leitor a refazer cada item sozinho.

Observação 4.1.1. Os axiomas listados acima não sao suficiente para caracterizar
o conjunto Z de modo único, isto é, existem outras estruturas algébricas famili-
ares que também satisfazem as propriedades acima. Por exemplo, o leitor muito
provavelmente está familiarizado com os conjuntos dos números racionais Q, dos
números reais R, e portanto pode notar que ambos conjuntos possem uma adição e
multiplicação, que embora tendo propriedades adicionais satisfazem cada uma dos
axiomas e dos item no Teorema (4.1.1). Isto indica que podemos ter outras estru-
turas não familiares “estruturas abstratas” que satisfazem os axiomas (A1), (A2),
(A3), (A4), (M1), (M2), (M3) e (D).
Consideremos, por exemplo, o conjunto Z = {0, 1}, sobre o definimos uma
adição e uma multiplicação como abaixo:

+ 0 1 · 0 1
0 0 1 0 0 0
1 1 0 1 0 1
Logo, as operações de + e de · conforme as tabelas acimas dadas, satisfazem
cada um dos axiomas (A1), (A2), (A3), (A4), (M1), (M2), (M3) e (D). ( O leitor
deve verificar isso!).
Cap. 4 • Os números inteiros 71

4.2 Princı́pio da Boa Ordenação

De uma forma pelo menos intuitiva entendemos que o conjunto dos números inteiros
são ordenados, no sentido que −1 é menor que 0, que é por sua vez menor que 1, que
é menor que 2, e assim por diante. Tratatemos agora de caracterizarmos a relação
de ordem “menor que” (<) sobre o conjunto dos números inteiros Z de maneira
formal.
A ordenação dos números inteiros é definida usando o conjunto de inteiros posi-
tivos {1, 2, 3, . . . }. Assim segue que

Definição 4.2.1. Se a e b são inteiros, então a < b se b − a é um inteiro positivo.

Se a < b, também escrevemos b > a.

Observe que a é um número inteiro positivo se, e somente se, a > 0.

Note que as propriedades fundamentais para a ordenação de inteiros sao o fecha-
mento para inteiros positivos (a + b e a.b são inteiros positivos sempre que a e b são
inteiros positivos) e a lei de tricotomia.
O conjunto de inteiros é considerado um conjunto ordenado porque tem um
subconjunto fechado sob adição e multiplicação e porque a lei da tricotomia vale
para todo inteiro. As propriedades básicas de ordenação de inteiros podem agora
ser provadas usando nossos axiomas a seguir.

(O1) Lei da tricotomia - Vale uma e somente uma das afirmações:

x < y; x = y; y<x

(O2) Se x < y e y < z então x < z (a relação < em Z é transitiva);

(O3) Se x < y então x + z < y + z (a relação < em Z é compatı́vel com adição);

(O4) Se x > 0 e y > 0 então xy > 0 (a relação < em Z é compatı́vel com a

multiplição).

Escrevemos a ≤ b para siginificar que 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 4.2.1. (Propriedades adicionais da relação <) Para todos x, y, z, e w em

Z, valem as seguintes propriedades:
Seção 4.2 • Princı́pio da Boa Ordenação 72

(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ção) Se x + z < y + z então x < y;

(4) Se x < y e z < w então x + z < y + w;

(5) (Regras de Sinais)

(a) Se x < 0 e y > 0, então xy < 0;
(b) Se x < 0 e y < 0 então xy > 0;

(6) Se x 6= 0 então x2 > 0;

(7) 1 > 0;

(8) (a) Se x < y e z > 0 então xz < yz; (b) Se x < y e z < 0 então xz > yz;

(9) Se x > y > 0 e z > w > 0 então xz > yw > 0;

(10) (Leis do Cancelamento para a multiplicação)

(a) Se xz < yz e z > 0 então x < y; (b) Se xz < yz e z < 0 então x > y.

Demonstração. (1) Se x < y então, pelo axioma (O3), x + (−y) < y + (−y), e
portanto x − y < 0.
(2) (Deixamos com exercı́cio para o leitor).
(3) (Deixamos com exercı́cio para o leitor).
(4) Se x < y entã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 então, pelo axioma (O2), x + z < y + w.
(5) Provaremos a primeira das afirmações e deixaremos a segunda como exercı́cio. Se
x < 0 e y > 0 então −x > 0 e y > 0. Pelo axioma (O4), temos −(xy) = (−x)y > 0,
e então, pelo item 2, xy < 0.
(6) Deixamos com 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 afirmações e deixaremos a segunda como exercı́cio.
Se x < y e z > 0, então x − y < 0, pelo item 1. Aplicando a propriedade (a) do item
5, x − y < 0 e z > 0, então (x − y)z < 0, de onde xz − yz < 0, e então xz < yz.
(9)(Deixamos com exercı́cio para o leitor).
(10) Provaremos o item (a) e deixaremos o item (b) como exercı́cio. Ambos os itens
são consequências direta do item 8. Se xz < yz e z > 0 então necessariamente x < y
Cap. 4 • Os números inteiros 73

pois, caso contrá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.

Proposição 4.2.1. Se x e y são inteiros, com x 6= 0 e y 6= 0, então xy 6= 0.

Equivalentemente, xy = 0 ⇒ x = 0 ou y = 0.

Demonstração. Se x 6= 0 e y 6= 0 então, pela lei da tricotomia (axioma (O1)), temos

x < 0 ou x > 0, bem como também y < 0 ou y > 0. Daı́, aplicando o axioma (O4)
ou o Teorema (4.2.1), item 5, teremos xy > 0 ou xy < 0. Portanto xy 6= 0.

Definição 4.2.2. Chamaremos de números naturais aos elementos do conjunto

N = {x ∈ Z | x ≥ 0}.

Se x e y são números naturais então, por resultados acima estabelecidos (Teorema

(4.2.1)), x+y e xy também são números naturais. Que na linguagem dos algebristas
significa que o conjunto dos números naturais N é fechado sob as operações de adição
e multiplicação definidas em Z, isto é, somando-se ou multiplicando-se elementos de
N, temos que o resultado (soma ou produto) é um elemento de N.
Também serão utilizadas as notações Z+ = N e Z∗+ = N∗ . Os elementos de N∗
são chamados inteiros positivos. Se n é um inteiro e n < 0, então n é chamado de
um inteiro negativo. O conjunto dos inteiros negativos será denotado por Z∗− .
Portanto, pela lei da tricotomia, temos que Z decompõem-se como união de três
partes disjuntas, a saber
Z = Z∗+ ∪ {0} ∪ Z∗−

Precisamos de mais uma propriedade para completar nosso conjunto de axiomas.

Axioma da Boa Ordem em N . Cada subconjunto não vazio do conjunto N
possui um menor (ou primeiro) elemento.

Exemplo 4.2.1. Seja A = {n ∈ N | n2 > 139}. O conjunto A é não vazio, pois por
exemplo (20)2 = 400 > 139, e assim 20 ∈ A. O axioma da boa ordenação permitenos
concluir que A tem um menor elemento. Assim, por tentativa e erro obtemos que
12 é o menor elemento de A.

Dizemos que o conjunto de inteiros positivos está bem ordenado. Por outro lado,
o conjunto de todos inteiros não estão bem ordenados, porque existem conjuntos
Seção 4.2 • Princı́pio da Boa Ordenação 74

de inteiros que não possuem o menor elemento (como o leitor deve verificar). Ob-
serve que o princı́pio da indução matemática é uma consequência do conjunto de
axiomas listados aqui. Às vezes, o princı́pio da indução matemática é tomado como
um axioma que substitui a propriedade da boa ordenação. Quando isso é feito, a
propriedade de boa ordem segue como uma consequencia.
Alguns textos introdutórios de estruturas algébricas, apresentam uma teoria
axiomática dos números naturais e então, a partir dos números naturais e suas
propriedades, uma construção dos números inteiros.

Observação 4.2.1. Observe que as propriedades elementares das operações em Z,

bem como as propriedades da relação <, axiomatizadas ou deduzidas até o momento
momento, excetuando-se o Axioma da Boa Ordem em Z+ , são igualmente válidas
para os números racionais e para os números reais. Do ponto de vista axiomático,
o axioma da boa ordem é o primeiro dos axiomas que é satisfeito pelos inteiros não
negativos mas não é satisfeito pelos racionais não negativos, visto que nem todo
conjunto de números racionais não negativos possui um primeiro elemento. Admi-
tamos, por um momento, familiaridade com o conjunto Q dos números racionais.
O conjunto dos números racionais positivos da forma 1/n, com n inteiro positivo,
não possui um menor elemento. Se n > 0 então n + 1 > n (visto que 1 > 0). No
âmbito dos números, é sabido que entã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. resumidamente o conjunto dos número racionais positivo não satisfazThe
rational numbers, equipped with a ordem ≤ não satizfaz o PBO. Seja A o conjunto
dos racionais positivos. O conjunto A não contem um menor elemento. Não importa
p p
qual número racional q
consideremos, temos que 2q
é menor que pq .

Exemplo 4.2.2. Seja A o conjunto de inteiros que podem ser escritos como a
soma de dois cubos positivos de três maneiras diferentes. Como A consiste em
números positivos, o PBO nos permite concluir que A é vazio ou tem um elemento
mı́nimo. Neste exemplo, se existe um método teórico numerico para encontrar o
elemento mı́nimo de A (além de executar um algoritmo de computador que faria
uma busca exaustiva), o PBO não oferece nenhuma maneira de determinar esse
elemento mı́nimo.

O Exemplo (4.2.2) mostra que o PBO é um resultado não construtivo, pois

afirma a existência de um elemento com uma determinada propriedade sem oferecer
um método para “construir’ ou encontrar esse elemento.
Cap. 4 • Os números inteiros 75

Estabeleceremos agora as primeiras consequências do Princı́pio da Boa Or-

denação.

Teorema 4.2.2. (1) Não existe um inteiro n tal que 0 < n < 1;

(2) Para cada inteiro m, não existe um inteiro n tal que m < n < m + 1;

(3) Se m e n são inteiros com m < n então m + 1 ≤ n. Reciprocamente, se

m + 1 ≤ n então m < n.

Demonstração. (1) Suponhamos que existe um inteiro n tal que 0 < n < 1. Tal n
é um número natural, e portanto o conjunto A de números naturais caracterizado
por
A = {x ∈ N | 0 < x < 1}

é um conjunto não vazio (visto que n ∈ A). Pelo axioma da boa ordem, A tem um
menor elemento n0 . Porém,

0 < n0 < 1 ⇒ 0 < n0 < n0 .n0 < 1.n0 ,

ou seja, 0 < n20 < n0 . Temos então uma contradição, pois 0 < n20 < 1 ⇒ n20 ∈ A,
mas n0 é o menor elemento de A e n20 < n0 .
(2) Sejam m e n dois inteiros e suponhamos que m < n < m + 1. Então m − m <
n − m < (m + 1) − m, ou seja, 0 < n − m < 1, o que é impossı́vel, pelosegundo o
item 1.
(3) (Este item é deixado como exercı́cio para o leitor).

Definição 4.2.3. Seja A um subconjunto não vazio de Z.

(1) Dizemos que A é limitado inferiormente por um inteiro m se a ≥ m, para

cada a em A;

(2) Dizemos que A é limitado superiormente por um inteiro M se a ≤ M , para

cada a em A.

Uma consequência imediata do princı́pio do menor número natural é a seguinte

proposição:

Proposição 4.2.2. Seja A um subconjunto não vazio de Z.

(1) Se A é limitado inferiormente por m ∈ Z, então A possui um primeiro (menor)
Seção 4.3 • Aritmética dos inteiros, divisibilidade e MDC 76

elemento, isto é, existe a0 em A tal que a ≥ a0 para cada a em A. (Tal a0 é chamado
mı́nimo de A). (2) Se A é limitado superiormente por M ∈ Z, então A possui um
último (maior) elemento, isto é, existe b0 em A tal que a ≤ b0 para cada a em A.
(Tal b0 é chamado máximo de A).

Demonstração. (1) Considere o conjunto

A0 = {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 A0 é um numero natural. Como A0 ⊂ N e A0 6= 0 (pois A 6= ∅), pelo Axioma da
Boa Ordem, existe n0 ∈ A0 tal que x ≥ n0 para cada x ∈ A.
Sendo n0 um elemento de A0 , temos que n0 = a0 − m para algum inteiro a0 ∈ A.
Logo, para cada x ∈ A0 , x ≥ a0 − m. Isto significa que para cada a ∈ A, a − m ≥
a0 − m, ou seja, a ≥ a0 .

(2) Considere o conjunto

A00 = {x ∈ Z | x = −a, com a ∈ A}.

Para cada a ∈ A, temos a ≤ M ou, equivalentemente, −a ≥ −M . Logo, para cada

x ∈ A00 , temos −x ≥ −M . Pelo item 1 provado acima, A00 tem um primeiro elemento,
ou seja, existe c0 ∈ A00 tal que x ≥ c0 para cada x ∈ A00 . Pela caracterização dos
elementos de A00 , c0 = −b0 para algum b0 ∈ A. Daı́, −a ≤ −b0 para cada a ∈ A, ou
seja, a ≤ b0 para cada a ∈ A.

4.3 Aritmética dos inteiros, divisibilidade e MDC

Definição 4.3.1. Para cada inteiro x, define-se o inteiro valor absoluto de x ou
módulo de x, denotado por |x|, pela igualdade:

(
x, x ≥ 0;
|x| =
−x, x < 0.
A proposição a seguir estabele as propriedades do módulo de um inteiro.

Proposição 4.3.1. Para cada x, y ∈ Z, tem-se

(1) |x| ≥ 0, e |x| = 0 ⇔ x = 0;

Cap. 4 • Os números inteiros 77

(2) | − x| = |x|;

(3) |xy| = |x|.|y|;

(4) |x ± y| ≤ |x| + |y|;

(5) |x| ≤ y ⇔ −y ≤ x ≤ y.

Demonstração. Deixamos a demonstração destas propriedades como exercı́cio para

o leitor.

A noção de divisibilidade de inteiros é frequentemente introduzida na escola

primária. No entanto, a fim de provar teoremas sobre divisibilidade, precisamos de
uma definição rigorosa.

Definição 4.3.2. Dados dois inteiros a e b, a 6= o denotaremos por

a | b,

para siginificar que existe algum k ∈ Z tal que b = a.k e dizemos que a divide b,
ou que a é divisor de b, ou que a é um fator de b, ou ainda que b é múltiplo de a.

Escrevemos Z para o conjunto de todos os múltiplos do inteiro a.

Observação 4.3.1. se a e b são inteiros, escrevemos a - b para denotar que a não

divide divide b. Ao denotar que a divide b, não escreva a / b e nem tampouco a\b.
Lembre-se que a / b denota a fração de inteiros a sobre b no conjunto dos números
racionais. E a / b, com a e b inteiros, é uma notação que necessita de darmos algum
significado.

Exemplo 4.3.1. 2 | (−6), pois −6 = 2.(−3).

Para cada inteiro a, a | a, 1 | a e a | 0, pois, respectivamente, a = a.1 e 0 = a.0
0 | 0 (zero divide zero !), pois 0 = 0.k, para qualquer inteiro k.
0 | a ⇔ a = 0. De fato, 0 | a ⇔ a = 0.k = 0, para algum inteiro k.

Podemos provar muitas propriedades básicas sobre a divisibilidade diretamente

da definição. Mencionamos apenas alguns na proposição a seguir.

Proposição 4.3.2. Para cada a, b e c inteiros, temos:

(1) a | a;
(2) a | b e b | a ⇔ a = ±b
Seção 4.3 • Aritmética dos inteiros, divisibilidade e MDC 78

(3) a | b e b | c ⇒ a | c;
(4) a | b e a | c ⇒ a | (mb ± nc), ∀ m, n ∈ Z;
(5) a | b e a | (b ± c) ⇒ a | c.

Demonstração. Sejam a, b e c números inteiros. Então

(1) Podemos escrever a = a.1, então a | a.
(2) Se a | b e b | a, então b = ax e a = by, para certos inteiros x e y. Assim,
a = by = (ax)y = a(xy). Se a = 0, então b = ax = 0 e logo a = b. Se a 6= 0, então
a = a(xy) ⇒ xy = 1 e desta forma x = y = ±1. Logo, a = by = b(±1) = ±b.
Reciprocamente, se a = ±b, então a = b(±1) e b = a(±1) e desta forma a | b e b | a
(3) Se a | b e b | c, então existem x, y ∈ Z, tais que b = ax e c = by. Portnato,
c = by = (ax)y = a(xy) e assim a | c.
(4) Se a | b e aj | c, então existem inteiros x e y, tais que b = ax e c = ay. Logo, dados
m, n ∈ Z, temos mb + nc = m(ax) + n(ay) = a(mx + ny) implica que a | (mb + nc).
(5) Se a | b e a | (b ± c) ⇒ a | [b − (b ± c)], então a | (±c) ⇒ a | c.

Suponha que restringimos a relação de divisibilidade a inteiros positivos N. Como

cada inteiro positivo se divide, divide ele mesmo a divisibilidade em N é reflexiva,
antissimétrica e pela Proposição (4.3.2) (3) é transitiva. Assim, N é um conjunto
parcialmente ordenado e tem um elemento mı́nimo 1, porque 1|n para todos os
inteiros positivos n, mas não tem elemento máximo.
Para discutir como a divisibilidade interage com o sinal dos inteiros, observe que,
como dk = a implica d(−k) = −a, então d é um divisor de a se, e somente se, d
é um divisor de −a. Portanto, ao discutir o conjunto de divisores de um número
a 6= 0, podemos assumir sem perda de generalidade que a > 0. Seja d um número
inteiro diferente de zero. Para obter um múltiplo positivo dk de d, precisamos de
k 6= 0 com o mesmo sinal de d. Então

dk = |d|.|k| ≥ |d| (4.1)

pois |k| ≥ 1. Assim, qualquer múltiplo diferente de zero a de d satisfaz |a| ≥ |d|.
Com o mesmo sı́mbolo (notação) Equação (4.1), qualquer divisor d de a satisfaz
|d| ≤ |a|.

Teorema 4.3.1. (Algoritmo da Divisão em Z) Para cada inteiro n, e cada inteiro

Cap. 4 • Os números inteiros 79

d, com d 6= 0, existem inteiros q (quociente) e r (resto) satisfazendo:

n = d.q + r e 0 ≤ r < |d|.

Além disso, os inteiros q e r, nas condições acima, são únicos. Chamamos q quoci-
ente e r de resto.

Antes de passarmos a demosntração deste resultado, vejamos alguns exemplos

que ilustram o emprego deste teorema de forma simples.
Na divisão euclidiana de 23 por 10, temos o seguinte esquema:

23 | 10

3 2

na divisão de 23 por 10 temos quociente 3 e resto 2 (23 = 10.2 + 3). Na divisão de

−23 por 10 serı́amos tentados a fazer

−23 | 10

−3 −2

claro que −23 = 10.(−2) + (−3), mas se quisermos o resto r nas condições do
Teorema (4.3.1) (r não negativo e menor que o valor absoluto do divisor),
Variando os sinais do dividendo e do divisor, temos os seguintes exemplos:
23 | 10 −23 | 10 23 | − 10 −23 | − 10
3 2 7 −3 3 −2 7 3

Demonstração do Algoritmo da divisão. Sejam n ∈ Z. Defina o conjunto

S = {n − kd ∈ N | k ∈ Z}.

Sejam n − k1 d e n − k2 d dois elementos de S. Temos

(n − k1 d)(n − k2 d) = (k2 − k1 )d,

portanto, a diferença de quaisquer dois elementos em S é um múltiplo de d. Além

disso, a cada elemento n−kd em S corresponde a apenas um inteiro k. Pelo princı́pio
da boa ordenação (PBO), S tem um elemento mı́nimo r = n−qd, para algum inteiro
q.
Seção 4.3 • Aritmética dos inteiros, divisibilidade e MDC 80

Agora, se r ≥ d, então n − d(q + 1) = n − dq − d = r − d ≥ 0 e assim r − d

contradiz a minimalidade de r como um elemento mı́nimo de S.
Como quaisquer dois elementos de S diferem por um múltiplo de d, então r é
o único elemento de S com 0 ≤ r < d. Portanto, os inteiros q e r satisfazem a
conclusão do teorema.

Técnicas de divisões de inteiros são ensinadas na escola prmária. É óbvio que

d|n se, e somente se, o resto da divisão inteira de n por d é 0. Tomando emprestada
a notação de algumas linguagens de programação, é comum escrever b mod a para
representar o resto da divisão de b por a.

Observação 4.3.2. Se x e a são inteiros, com a 6= 0, e x | a então |x| ≤ |a|. De

fato, como x | a temos que a = x.c, para algum inteiro c e c 6= 0 (pois a 6= 0), temos
|c| ≥ 1, e logo |x| = |x|.1 ≤ |x|.|c| = |x.c| = |a| ⇒ |x| ≤ |a|.

Assim sendo, se a 6= 0, o conjunto D(a) dos inteiros divisores de a é limitado

superiormente por |a| (note porém que se a = 0, então D(a) = D(0) = Z, pois cada
inteiro é divisor de zero).
Agora, dados dois inteiros a e b, com a 6= 0 ou b 6= 0, existe pelo menos um
divisor comum de a e b, a saber, 1, já que 1 | a e 1 | b.
Além disso, se x ∈ Z é um divisor comum de ambos a e b então, temos que
|x| ≤ |a| (se a 6= 0) ou |x| ≤ |b| (se b 6= 0).
Assim sendo, o conjunto dos divisores comuns de a e b é limitado superiormente
(pelo menor dos inteiros |a| e |b|), e portanto possui um máximo d ( pela Proposição
(4.2.2)) e temo que d ≥ 1, já que 1 | a e 1 | b. A este inteiro d chamamos máximo
divisor comum de a e b.
Os conceitos de maior divisor comum (ou fator) e o mı́nimo múltiplo comum
surgem cedo na educação matemática. No entanto, introduzimos esses conceitos
de uma maneira que pode parecer nova, mas é equivalente à formulação do ensino
fundamental, mas tem o benefı́cio de permitir generalizá-lo em outros contextos
algébricos.

Definição 4.3.3. [MDC] Dados dois inteiros a e b, chama-se máximo divisor co-
mum de a e b ao inteiro d que satisfaz as condições:
(1) d = 0, se a = 0 = b.
(2) Se a 6= 0 ou b 6= 0, d é caracterizado pelas propriedades:
Cap. 4 • Os números inteiros 81

(i) d | a e d | b (“d é divisor comum”);

(ii) Para todo x ∈ Z, tal que x | a e x | b ⇒ x | d (“d é o maior dos divisores

comuns”).

Usaremos a notação d = mdc(a, b), para denotar o máximo divisor comum de a

e b.
Pela definição temos que mdc(0, 0) = 0. E que se a 6= 0 ou b 6= 0, então

mdc(a, b) = max {x ∈ Z | x | a e x | b}.

Proposição 4.3.3. Para todos interios a, b temos:

(1) mdc(a, 0) = |a|;
(2) Se a 6= 0 ou b 6= 0, então mdc(a, b) = mdc(|a|, |b|);
(3) mdc(a, b) = mdc(b, a);

Demonstração. A prova dos itens (2) e (3) é imediata, já que para todo x ∈ Z,

x | a e x | b ⇔ x | b e x | a ⇔ x | |a| e x | |b|.

(1)Se a = 0, então mdc(a, 0) = mdc(0, 0) = 0 = |a|. Se a 6= 0, seja d = |a|. Como

a = ±d = d(±1), temos que d | a. Também, d | 0. Agora, para cada x ∈ Z, x | a
e x | 0 ⇒ x | a ⇒ x ≤ |a| ⇒ x ≤ d. Logo, pela definição de mdc, |a| = d =
mdc(a, 0).

O próximo teorema dá uma caracterização do mdc entre dois inteiros não nulos
como sendo o menor elemento dentro do conjunto das combinações lineares inteiras
de a e b.

Teorema 4.3.2. [Caracterização do MDC] Sejam a, b ∈ Z com a 6= 0 ou b 6= 0,

então o máximo divisor comum de a e b é a menor das combinações lineares positivas
ma + nb, com m e n inteiros. Em outras palavras, se a 6= 0 ou b 6= 0, então
mdc(a, b) = min{x ∈ Z | x > 0 e x = ma + nb, com m, n ∈ Z}.

Demonstração. Seja

L = {x ∈ Z | x > 0 e x = ma + nb, com m, n ∈ Z}.

Temos que L 6= 0, pois, sendo a 6= 0 ou b 6= 0, o inteiro |a| + |b| é elemento de L,

pois |a| + |b| > 0 e |a| + |b| = (±a) + (±b) = ma + nb, sendo m = ±1 e n = ±1.
Seção 4.3 • Aritmética dos inteiros, divisibilidade e MDC 82

Além disso, L é um subconjunto de Z limitado inferiormente por 0. Pelo Princı́pio

do Boa Ordenção, existe um inteiro d, tal que d = min L, isto é, d ∈ L e d ≤ x, ∀ x ∈
L.
Veremos agora que d | a e d | b:
Sendo d > 0, pelo algoritmo da divisão em Z, Teorema (4.3.1), existem inteiros
q e r tais que
a = dq + r e 0 ≤ r < d(= |d|)

Como d ∈ L, d pode ser escrito na forma

d = m0 a + n0 b, para certos m0 , n0 ∈ Z.

Então teremos
r = a − dq
= a − (m0 a + n0 b)q
.
= (1 − m0 q)a + (−n0 q)b
= m0 a + n0 b
Desta forma temos que r ∈ L, pois tem a forma dos eslementos deste conjunto.
Agora, note que 0 ≤ r = m0 a + n0 b < d, isto é, r é menor que d que por sua vez
é o menor elemento do conjunto d, se tivessemos r < d e sendo r ∈ L temos um
absurdo, pois r é um elemento de L, menor que o menor elemento de L. Assim,
temos que r = 0, e desta forma a = dq e logo d | a. Analogamente, mostra-se que
d | b.
Para mostrar a segunda condição do mdc, considere x um inteiro qualquer tal
que x | a e x | b. Então da Proposição (4.3.3) item (4) temos que x | (m0 a + n0 b), e
então x | d.
Logo, temos que d = mdc(a, b) e então min L = mdc(a, b).

A conclusão imediata é que o do teorema fornece o mdc como combinação linear

inteira de a e b.

Corolário 4.3.1. Sejam a e b inteiros e d = mdc(a, b), então existem inteiros r e

s tais que d = ra + sb.

O Corolário (4.3.1) não oferece uma maneira de encontrar os inteiros r e s tais

que o mdc (a, b) = ra + sb. Se a e b são valores pequenos, então é possı́vel encontrar
r es por inspeção. Por exemplo, inspecionando os divisores de 22, é fácil ver que
mdc (22, 14) = 2. Uma combinação linear que ilustra o Corolário (4.3.1) para 22 e
Cap. 4 • Os números inteiros 83

14 é 2 × 22 − 3 × 14 = 44 − 42 = 2. No entanto, é possı́vel retroceder as etapas do

Algoritmo Euclidiano e encontrar r e s de forma que ra + sb = mdc (a, b).

Corolário 4.3.2. Sejam a, b ∈ Z e d = mdc(a, b). Sejam

A = {x ∈ Z | x = ma + nb, com m, n ∈ Z} e

M = {y ∈ Z | y = λd, com λ ∈ Z}.

Então, A = M , isto é, as combinações lineares ma + nb, com m e n inteiros, são,

na verdade, os inteiros múltiplos de d.

Demonstração. Se a = b = 0, temos d = 0 e A = M = {0}. Suponhamos então que

a 6= 0 ou b 6= 0. Para provar que A = M , provaremos que A ⊆ M e M ⊆ A.
(⊆) Seja x um elemento de A, então x = ma + nb, para certos inteiros m e n. Sendo
d = mdc(a, b), temos que d | a e d | b ⇒ d | (ma + nb) ⇒ d | x ⇒ x = λd, para algum
inteiro λ então, x ∈ M .
(⊇) Seja y um elemento de M , então y = λd, para algum inteiro λ. Pelo Teorema
(4.3.2) temos que d = ra + sb, para certos inteiros r, s. Logo, y = λd = λ(ra + sb) =
(λr)a + (λs)b ⇒)y ∈ A. Portanto, temos que A = M .

Estabeleceremos agora um algoritmo para o cálculo do mdc(a, b), no caso em

que a e b são inteiros ambos não nulos, realizado através de uma sequência finita
de divisões sucessivas. Antes de enunciá-lo ilustrémos o processo por meio de um
exemplo.

Exemplo 4.3.2. Considere o problema de calcular mdc(91, 35). Começamos fa-

zendo a divisão de 91 por 35.

91 | 35

21 −2
Consideramos então o divisor 35 e o resto 21 e apliquemos o algoritmo da divisão
para estes valores.
35 | 21

14 1
Agora repetimos o processo iniciado acima, isto é, tomamos, na próxima divisão,
21 como dividendo e 14 como divisor:
Seção 4.3 • Aritmética dos inteiros, divisibilidade e MDC 84

21 | 14

7 1
Finalmente, chegamos à divisão exata.

14 |7

0 2
Tendo chegado a um resto igual a zero, o algoritmo termina. O último resto não
nulo, das divisões sucessivas realizadas, é o mdc procurado, ou seja, mdc(91, 35) = 7.

Antes de formalizarmos este procedimento, note que por causa da condição (ii)
na Definição (4.3.3) não é óbvio que dois inteiros dados ambos não tenham o
maior divisor comum. (Se tivéssemos dito d0 ≤ d na definição, a prova de que dois
inteiros, não ambos nulos, têm um maior divisor comum é uma aplicação simples
do Princı́pio de Boa Ordem em Z). A chave para mostrar que os inteiros possuem
um maior comum divisor depende do algoritmo euclidiano, que descrevemos aqui
abaixo.
Sejam a e b dois inteiros positivos com a ≥ b. O Algoritmo Euclidiano começa
definindo r0 = a e r1 = b, em seguida, realiza repetidamente as seguintes divisões
inteiras.

r0 = r1 q1 + r2 , onde 0 ≤ r2 < b
r1 = r2 q2 + r3 , onde 0 ≤ r3 < r2
.. ..
. .
rn−2 = rn−1 qn−1 + rn , onde 0 ≤ rn < rn−1
rn−1 = rn qn + 0, onde rn > 0
Este procedimento termina pois a sequência r1 , r2 , r3 , . . . é uma sequência estri-
tamente crescente de inteiros positivos e portanto tem no máximo r1 = b termos
nela. Note que b|a, então n = 1 e o algoritmo tem um passo somente.
Para ver o que o algoritmo no diz, considere o inteiro positivo rn . Pelo último
passo do algoritmo euclidiano vemos que rn |rn−1 . Da segunda para a último passo li-
nha, do algoritmo euclidiano, rn |rn−1 qn−1 e pela Proposição (4.3.2) item (4), rn |rn−2 .
Repetidas aplicações deste processo (,isto é, na verdade aplicando n − 1 vezes este
procedimento e portanto um número finito), temos que rn |r1 e rn |r0 , então rn é um
divisor comum de a e b.
Agora, se d0 é um outro divisor comum de a e b. Então tomando, d0 k0 = a = r0
Cap. 4 • Os números inteiros 85

e d0 k1 = b = r1 , temos que

r2 = r0 − r1 q1 = d0 k0 − d0 k1 q1 = d0 (k0 − k1 q1 ).

Portanto, d0 divide r2 com d0 k2 = r2 . Repetindo o processo (n − 1) vezes temos que

d0 |rn . Assim, rn é o máximo divisor comum de a e b, pois as condições da Definição
(4.3.3) são satisfeitas. Vejamos este procedimento de modo mais formal, onde o
primeiro passo e o seguinte lema.

Lema 4.3.1. Sejam a e b dois inteiros, com b 6= 0, e seja r o resto da divisão de a

por b. Então mdc(a, b) = mdc(b, r).

Demonstração. Para demonstrar o resultado enunciado no lema, basta provarmos

que que todo divisor de a e b é também divisor de b e r, e reciprocamente. Assim
sendo, o maior divisor de a e b coincidirá com o maior divisor de b e r. Note que
esse “maior divisor” existe, já que b 6= 0.
Sabemos que por hipótese, a = bq + r, logo r = a − bq. Seja x um inteiro divisor
de a e b.
Então, x | a e x | b ⇒ x (a − qb) ⇒ x | r.
Logo, x | b e x | r.
Agora, seja x um inteiro divisor de b e r. Então, x | b e x | r ⇒ x | (qb + r) ⇒ x | a.
Logo, x | b e x | a.

Sabendo pelo Lema (4.3.1) o mdc de a e b e o mesmo que o mdc entre b e o resto
r, onde r é o resto da divisão de a por b. O próximo lema mostrar como realizar
divisões sucessivas a fim de obter o mdc entre a e b.

Lema 4.3.2. Sejam a e b inteiros ambos positivos com a ≥ b e definamos uma

sequência de inteiros não negativos da seguinte forma:
(i) r1 = a;
(ii) r2 = b;
Para cada ı́ndice k, com k ≥ 2, se rk 6= 0, rk+1 é o resto da divisão Euclidiana de
rk−1 por rk :
rk−1 | rk

rk+1 ∗
e se rk = 0, a sequência termina em rk . Então, a sequência r1 , r2 , . . . , é uma
sequência finita que termina em zero, em outras palavras, existe um ı́ndice n tal que
r1 ≥ r2 > · · · > rn > 0 e rn+1 = 0.
Seção 4.3 • Aritmética dos inteiros, divisibilidade e MDC 86

Demonstração. Por hipótese, r1 ≥ r2 e então pela definição de rk+1 , para k ≥ 2

temos rk+1 < rk .
Considere o conjunto de números naturais S = {r1 , r2 , . . . }. Como S ⊆ N e
S 6= ∅, então pelo princı́pio da boa ordenação, S possui um menor elemento, o qual
denotaremos por rn+1 . Pelo que foi observado acima, teremos rn+1 < rn < · · · <
r2 ≤ r1 . Afirmamos que rn+1 = 0. De fato, basta observar que se rn+1 6= 0 então
podemos definir rn+2 ∈ S como sendo o resto da divisão de rn por rn+1 . Teremos
então 0 ≤ rn+2 < rn+1 , contrariando o fato de rn+1 é o menor elemento do conjunto
S.

Usando os Lemas (4.3.1) e (4.3.2) obtemos o seguinte teorema.

Teorema 4.3.3. (Algoritmo Euclidiano para o cálculo do mdc) Sejam a e b inteiros

ambos positivos com a ≥ b e seja r1 , r2 , . . . , rn , rn+1 a sequência definida pelo Lema
(4.3.2), sendo r1 ≥ r2 > · · · > rn > rn+1 = 0. Então rn = mdc(a, b).

Demonstração. Para cada k ≥ 3, rk é o resto da divisão de rk−2 por rk−1 . Pelo

Lema (4.3.1):
mdc(rk , rk−1 ) = mdc(rk−1 , rk−2 ).

Logo,
rn = mdc(0, rn )
= mdc(rn+1 , rn ) (pois rn+1 = 0)
= mdc(rn+1 , rn ) (pelo Lema (4.3.1))
...
= mdc(r3 , r2 )
= mdc(r2 , r1 )
= mdc(a, b)

A próxima proposição mostrar que o mdc de dois inteiros não nulos é único.

Proposição 4.3.4. Existe um único máximo divisor comum para qualquer dois
inteiros não nulos

Demonstração. Suponha primeiro que a ou b seja zero. Sem perda de generalidade

podemos supor que a 6= 0 e que b = 0. Como qualquer inteiro divide zero, então
os divivores comuns de a e b neste caso consiste dos divisores de a. Então, o maior
divisor comum de a e 0 consistem em a e −a e |a| é o maior divisor comum positivo
de a e 0 e é único.
Cap. 4 • Os números inteiros 87

Agora suponha que nem e nem b seja zero. Visto que o conjunto de divisores de
um inteiro c é o mesmo conjunto que os divisores de −c, então podemos assumir,
sem perda de generalidade, que a e b são ambos positivos. Aplicando o Algoritmo
Euclidiano para a e b mostramos que o par (a, b) tem o maior divisor comum. Agora
suponha que d1 e d2 sejam os dois maiores divisores comuns positivos de a e b.
Então d1 |d2 e d2 |d1 e de acordo com a Proposição (4.3.2) item (2) d1 = d2 , visto
que ambos são positivos. Portanto, a e b possuem um único máximo divisor comum
positivo.

Pela Proposição (4.3.4), normalmente nos referimos ao maior divisor comum de

dois inteiros como este único inteiro positivo e o denotamos por mdc (a, b). A prova
da Proposição (4.3.4) nos diz como calcular o maior divisor comum: (1) se a 6= 0,
então mdc (a, 0) = |a|; (2) se a, b 6= 0, então mdc (a, b) é o resultado do Algoritmo
Euclidiano aplicado para |a|e |b|.

Exemplo 4.3.3. Calcularemos agora o mdc entre 522 e 408. Usaremos o algoritmo
euclidiano para este fim. Observe as divisões:

552 = 408 × 1 + 114

408 = 144 × 3 + 66
114 = 66 × 1 + 48
66 = 48 × 1 + 18
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6×2+0

Assim, de acordo com o algoritmo euclidiano, mdc (522, 408) = 6.

Escreveremos agora atráves de um exemplo como obter o mdc(a, b) na forma

ra + sb, com r e s inteiros, usando o algoritmo Euclidiano.

Exemplo 4.3.4. ( Escrevendo o mdc d como combinação de a e b) No Exemplo

(4.3.2) vimos que mdc(91, 35) = 7 e ele foi obtido mediante quatro divisões sucessi-
vas:
91 | 35 35 | 21 21 | 14 14 |7

21 2 14 1 7 1 0 2
Seção 4.3 • Aritmética dos inteiros, divisibilidade e MDC 88

As três primeiras divisões dão que

91 = 35.2 + 21
35 = 21 + 14
21 = 14.1 + 7

E então, isolando os restos em cada igualdade temos:

21 = 91 − 35.2
14 = 35 − 21.1 ,
7 = 21 − 14.1

de onde então obtemos, passo a passo, cada um dos três restos como combinação
linear de 91 e 35:

21 = 91 − 35.2, conforme já estabelecido.

Agora, na segunda iguladade 14 = 35 − 21.1 substituı́mos 21 como a combinação

acima e então obtemos:

14 = 35 − 21.1
= 35 − (91 − 35.2) ,
= (−1)91 + 3.35
e finalmente,
7 = 21 − 14.1
= (91 − 35.2) − [(−1).91 + 3.35].1 ,
= 2.91 + (−5).35
ou seja, 7 = 2.91 + (−5).35. Obtemos assim, 7 = mdc(91, 35) como combinação
linear r.91 + s.35, com r e s inteiros.

Dois inteiros sempre têm 1 e −1 como divisores comuns. No entanto,

se mdc (a, b) = 1, então dizemos que a e b são relativamente primos.

Lema 4.3.3. Sejam a e b inteiros positivos. Então, se k e l são inteiros tais que
a = kmdc (a, b) e b = lmdc (a, b), então k e l são relativamente primos.

Demonstração. Considere c = mdc (k, l) e escreva k = ck 0 e l = cl0 para alguns

inteiros k 0 e l0 . Então,

a = k 0 cmdc (a, b) e b = l0 cmdc (a, b).

Cap. 4 • Os números inteiros 89

Portanto, cmdc (a, b) seria um divisor do mdc (a, b), então para algum inteiro h,
temos cmdc (a, b)h = mdc (a, b). Portanto, ch = 1. Como c é um número inteiro
positivo, e isso só é possı́vel se c = 1.

A caracterização do máximo divisor comum dada na na Proposição (4.3.2) per-

mite obtermos muitas consequências sobre o máximo divisor comum, a próxima
proposição é uma amostra disso.

Proposição 4.3.5. Sejam a e b inteiros não nulos relativamente primos. Para

qualquer interiro c, se a|bc, então a|c.

Demonstração. Como a e b são relativamente primos temos que mdc (a, b) = 1. Pela
Proposição (4.3.2) existem inteiros r e s tais que 1 = ra + sa. Como por hipótese
a|bc temos que bc = ka, para algum k ∈ Z.
Assim, c = rac + sbc = rac + ska = a(rc + sk) que diz que c é um mútiplo de a
e então a|c.

Definição 4.3.4. [Mı́nimo múltiplo comum] Se a, b ∈ Z∗ , um mı́nimo múltiplo

comum é um elemento m ∈ Z tal que:
(i) a|m e b|m (significando que m é múltiplo comum);
(ii) Se a|m0 e b|m0 , então m|m0 (significando que m é o menor múltiplo comum).

De modo análogo à apresentação do máximo divisor comum, devemos notar que,

a partir dessa definição, não é óbvio que sempre exista um mı́nimo múltiplo comum.
Novamente, devemos mostrar que ele existe.

Proposição 4.3.6. Existe um único mı́nimo múltiplo comum m de qualquer par de

inteiros a e b não nulos.

Demonstração. Sejam m1 e m2 mı́nimos múltiplos comuns de a e b, então m1 |m2 e

m2 |m1 pela Proposição (4.3.2) item (2), se a e b têm pelo menos um múltiplo comum
m, então o inteiro −m é um outro múltiplo comum. Sem perda de generalidade,
assuma que a e b são positivos no resto da demonstração.
Como omdc (a, b) divide a e divide b, então mdc (a, b)|ab. Além disso, podemos
escrever a = kmdc (a, b) e b = lmdc (a, b).
Seja M o número inteiro positivo tal que M mdc (a, b) = ab. De M mdc (a, b) =
mdc (a, b)kb, obtemos M = bk e da mesma forma M = al e, portanto, M é um
múltiplo comum de a e b.
Seção 4.4 • O Teorema Fundamental da Aritmética 90

Seja m0 um outro múltiplo comum de a e b com m0 = pa e m0 qb. Como pa = qb

então
pkmdc (a, b) = qlmdc (a, b)

e, portanto, pk = ql. Como mdc (k, l) = 1, pela Proposição (4.3.5) k|q com q = kc,
para algum c inteiro.
Portanto, m0 = (kc)b = c(bk) = cM e assim deduzimos que m0 |M . Isso mostra
que M = ab/mdc (a, b) satisfaz a Definição (4.3.4) e a proposição segue.

Geralmente chamamos esse único múltiplo mı́nimo comum positivo de a e b como

“o” mı́nimo múltiplo comum. Denotamos esse número inteiro positivo por

mmc(a, b).

A Proposição (4.3.6) estabelece o seguinte resultado importante

mdc(a, b) mmc(a, b) = ab

para todo a, b inteiros não nulos.

4.4 O Teorema Fundamental da Aritmética

Costumamos dizer “p é primo” em vez de dizermos “p é um número primo”. Por
mais simples que seja o conceito de primalidade, as propriedades sobre os números
primos intrigam os matemáticos desde Euclides e antes. A distribuição de números
primos em N ou em sequências de inteiros, propriedades aditivas de números primos,
algoritmos rápidos para checar se um número é primo e muitas outras questões ainda
oferecem áreas ativas de pesquisa na teoria dos números. Por definição, todo número
inteiro positivo ou é 1, ou é um número primo ou é um número composto. Seja S
o conjunto de inteiros compostos que não são divisı́veis por um número primo.
Suponha que S não é um conjunto vazio. Pela princı́pio da boa ordenação dos
inteiros, S tem pelo menos o elemento m. Como m é composto, podemos escrever
m = ab, onde nem a nem b são 1. Então, a é primo ou a é composto. Agora, a
não pode ser primo porque m não é divisı́vel por um número primo. Portanto, a é
composto. Como a < m, então a ∈
/ S, então a é divisı́vel por um número primo.
Pela Proposição, m também deve ser divisı́vel por um número primo. Isso contradiz
Cap. 4 • Os números inteiros 91

a suposição de que S 6= ∅. Esse raciocı́nio estabelece o resultado fundamental de

que todo número inteiro positivo maior que 1 é divisı́vel por um número primo.
Um dos primeiros resultados sobre os números primos que vem de Euclides,
que habilmente aplicou um argumento por contradição para provar que existe um
número infinito de números primos.

Definição 4.4.1. Dados a e b inteiros, dizemos que a e b são relativamente primos

ou primos entre si se mdc(a, b) = 1, ou seja, se a e b não tem fatores positivos
comuns além da unidade.

Proposição 4.4.1. Dados dois inteiros a e b, a e b são primos entre si se, e somente
se, existem inteiros r e s satisfazendo r.a + s.b = 1.

Demonstração. A prova é uma aplicação imediata do Teorema (4.3.3). Se vale uma

uma igualdade do tipo ra + sb = 1, com r e s inteiros, se e somente se, a 6= 0 ou
b 6= 0 e, além disso, 1 é a menor combinação linear positiva de a e b, com coeficientes
inteiros, ou seja, se e somente se mdc(a, b) = 1 (Proposição (4.3.2)).

Proposição 4.4.2. Dados inteiros a, b e c, se a e b são primos entre si e a | bc,

então a | c.

Demonstração. Como a e b são primos entre si, pela Proposição (4.4.1), temos que
r.a + s.b = 1 para certos inteiros r e s. Logo, multiplicando esta igualdade por c
temos rac + sbc = c. Agora, como a | rac e a | bc, segue que a | c.

Proposição 4.4.3. Dados inteiros a, b e c, com a e b primos entre si, se a | c e b | c,

então ab | c.

Demonstração. Por hipótese, a | c e b | c. Isto quer dizer que para certos inteiros x e
y, temos c = ax e c = by.
Como a e b são primos entre si, pelo Teorema(4.3.3), existem inteiros r e s
tais que ra + sb = 1. Portanto, rac + sbc = c. Logo, ra(by) + sb(ax) = c, onde
substituimos na igualdade anterior no primeiro c por by e o segundo c por ax. Daı́,
ab(ry + sx) = c, e então ab | c.

Definição 4.4.2. Dizemos que um inteiro p é um número primo se p 6= 0, p 6= ±1

os únicos inteiros divisores de p são 1, p, −1, −p.

Proposição 4.4.4. Sendo a e p inteiros, se p é primo e p não divide a então a e p

são relativamente primos.
Seção 4.4 • O Teorema Fundamental da Aritmética 92

Demonstração. Sejam a e p tal que p é primo, com p - a. Seja d = mdc(a, p). Então
d > 0, e temos por definição que d | a e d | p. Como p é primo, temos que d = 1 ou
d = p. Mas, p - a e d | a, logo d = 1 e assim a e p são primos entre si.

Teorema 4.4.1. Sejam a, b e p inteiros, com p primo. Se p | ab, então p | a ou p | b

(podendo o p ser fator de ambos, a e b).

Demonstração. Temos que p | a ou p | a. Se p - a, então da Proposição (4.4.4), p e

a são relativamente primos. Como p | ab, então pela Proposição (4.4.2) temos que
p | b.

Corolário 4.4.1. Sejam p, a1 , . . . , an números inteiros com n ≥ 2 e p primo. Se

p | (a1 a2 . . . an ), então p | ai para algum ı́ndice i, 1 ≤ i ≤ n.

Demonstração. A demosntração pode serfeita por indução sobre n. Para n = 2, o

corolário é exatamente o conteúdo da Proposição (4.4.1). Seja k um inteiro com
k ≥ 2 e suponhamos que a afirmação do corolário seja verdadeira para n = k,
isto é, suponhamos que se p é primo e p divide um produto de k números in-
teiros então p divide ao menos um dos fatores. Consideremos então um pro-
duto de k + 1 inteiros a1 a2 . . . ak ak+1 e suponhamos que p | a1 a2 . . . ak ak+1 . Então,
p | (a1 a2 . . . ak )ak+1 . Pela Proposição (4.4.1), p | (a1 a2 . . . ak ) ou p | ak+1 . Logo, p | aj
para algum j ∈ {1, 2, . . . , k} (pela hipótese de indução) ou p | ak+1 , e assim a pro-
priedade enunciada também se aplica ao produto de k + 1 inteiros.
Pelo primeiro principio de indução finita, o corolário está demonstrado.

Teorema 4.4.2. (Teorema Fundamental da Aritmética) Para cada inteiro m, com

m ≥ 2, existe um conjunto de inteiros positivos e primos p1 , . . . , pn , com n ≥ 1
e p1 ≤ p2 ≤ · · · ≤ pn , tal que m = p1 p2 . . . pn . Além disso, os fatores primos
p1 , p2 , . . . , pn , satisfazendo as condições acima, são únicos, isto é, se q1 , q2 , . . . , qs
são também primos positivos com q1 ≤ q2 ≤ · · · ≤ qs e m = q1 q2 . . . qs , então n = s
e além disso, p1 = q1 , p2 = q2 , . . . , pn = qn .

Demonstração. Existência da decomposição de m em fatores primos.

Provaremos, por indução sobre m (pelo segundo princı́pio de indução finita), a
existência da decomposição de m em fatores primos.
Se m = 2, então m é primo (prove isto!). Temos então m = p1 , com p1 primo
positivo. Seja k ≥ 2 e suponhamos que se m é um inteiro, com 2 ≤ m ≤ k, então
m é primo ou se decompõe como produto de fatores primos. Trataremos de provar
Cap. 4 • Os números inteiros 93

que então que k + 1 também é primo ou se escreve como produto de fatores primos.
Se k + 1 é primo, então nada mais temos a provar. Se k + 1 não é primo (isto é,
se k + 1 é composto), então existem inteiros positivos a e b, com 1 < a < k + 1 e
1 < b < k + 1, tais que k + 1 se fatora na forma k + 1 = a.b.
Agora, como 1 < a ≤ k e 1 < b ≤ k, pela hipótese de indução, cada um dos
inteiros a e b se decompõe como produto de fatores primos positivos.
Logo, como k + 1 = ab, k + 1 se decompõe como um produto de fatores primos.
Assim sendo, cada inteiro m ≥ 2 é primo ou se escreve como um produto de pri-
mos. Arranjando-se convenientemente a ordem dos fatores, teremos m = p1 p2 . . . pn ,
com p1 , p2 , . . . , pn primos e p1 ≤ p2 ≤ . . . , ≤ pn .

Unicidade da decomposição de m em fatores primos.

Para a prova da unicidade dos fatores primos de m, utilizaremos novamente o

segundo princı́pio de indução finita. Se m = 2, obviamente não será possı́vel termos
m = q1 . . . qs , com q1 , q2 , . . . , qs primos positivos e s ≥ 2, já que 2 é primo. Só nos
resta a possibilidade s = 1, tendo então 2 = q1 . Assim, só existe uma maneira de
escrever 2 como produto de fatores primos positivos.
Seja k ≥ 2 e suponhamos que para cada inteiro m, com 2 ≤ m ≤ k, só há
uma fatoração possı́vel de m como produto de primos positivos, se considerados
ordenadamente, como no enunciado do teorema. Mostraremos que o mesmo se dá
com relação ao inteiro k + 1.
Suponhamos que k + 1 = p1 p2 . . . pn = q1 q2 . . . qs , com n, s ≥ 1, p1 ≤ p2 ≤ · · · ≤
pn e q1 ≤ q2 ≤ · · · ≤ qs .
Se n = 1, então k + 1 = p1 é primo e, neste caso também teremos s = 1, já que
um primo não pode ser um produto de dois ou mais primos. Então n = s = 1 e
k + 1 = p1 = q 1 .
Se, por outro lado, s = 1, então analogamente, teremos n = 1 e k + 1 = p1 = q1 .
Suponhamos então n ≥ 2 e s ≥ 2. Como p1 p2 . . . pn−1 pn = q1 q2 . . . qs−1 qs , temos
que pn | (q1 q2 . . . qs ) e qs | (p1 p2 . . . pn ).
Pelo Corolário (4.4.1), temos que pn | qi e qs | pj para certos ı́ndices i, j, com
1 ≤ i ≤ s e 1 ≤ j ≤ n. Logo, pn ≤ qi ≤ qs ≤ pj ≤ pn , o que então implica pn = qs .
Logo, p1 . . . pn−1 pn = q1 . . . qs−1 qs e pn = qs , e então

p1 . . . pn−1 = q1 . . . qs−1 .
Seção 4.4 • O Teorema Fundamental da Aritmética 94

Agora, 2 ≤ p1 . . . pn−1 = q1 . . . qs−1 < k+1, ou seja, 2 ≤ p1 . . . pn−1 = q1 . . . qs−1 ≤

k Aplicando a hipótese de ind ução, temos então que n − 1 = s − 1 e além disso,
p1 = q1 , . . . ,pn−1 = qn−1 .
Logo, n = s e p1 = q1 , . . . , pn−1 = qn−1 , pn = qn . Assim sendo, a unicidade dos
fatores primos de m é válida para cada m ≥ 2.

Corolário 4.4.2. Para cada inteiro m, com m ≥ 2, existem primos positivos

p1 , . . . , ps , com s ≥ 1 e p1 < · · · < ps se s ≥ 2, e inteiros positivos α1 , α2 , . . . , αs tal
que m = pα1 1 pα2 2 . . . pαs s . Tal representação de m é única.

Demonstração. Pelo teorema fundamental da aritmética, m é um produto de fa-

tores primos q1 , q2 , . . . , qn , com q1 ≤ q2 ≤ · · · ≤ qn , (n ≥ 1). Agrupando-se os
fatores primos repetidos na forma de potências de primos, temos a representação
enunciada neste corolário. Além disso, pelo Teorema Fundamental da Aritmética,
tal representação é única.

Corolário 4.4.3. Seja m um inteiro, m = pα1 1 pα2 2 . . . pαnn , com n ≥ 1 e p1 , p2 , . . . , pn

primos positivos com p1 < p2 < · · · < pn se n ≥ 2 e α1 , α2 , . . . , αn inteiros positivos.
Sendo a um inteiro, temos que a divide m se, e somente se, a = pβ1 1 pβ2 2 . . . pβnn , para
certos inteiros não negativos β1 , β2 , . . . , βn , satisfazendo β1 ≤ α1 , β2 ≤ α2 , . . . , βn ≤
αn .

Demonstração. Se a | m, então m = a.c para um certo inteiro positivo c. Assim, os

eventuais fatores primos de a (eventuais, pois podemos ter a = 1) são fatores primos
de m. Ou seja, o conjunto de fatores primos de a é um subconjunto dos fatores
primos de m.
Logo, a = pβ1 1 pβ2 2 . . . pβnn para certos inteiros não negativos β1 , β2 , . . . , βn (onde
teremos β= 0 se pj não for um fator de a). Claramente, para cada ı́ndice j, teremos
βj ≤ αj , pois como pα1 1 pα2 2 . . . pαnn = pβ1 1 pβ2 2 . . . pβnn .c, se αj < βj para algum ı́ndice j,
teremos uma contradição ao Teorema Fundamental da Aritmética.

Corolário 4.4.4. Sejam a e b dois inteiros positivos. Então, existem primos positi-
vos p1 , p2 , . . . , pn , com n ≥ 1 e p1 < p2 < · · · < pn se n ≥ 2, e inteiros não negativos
α1 , α2 , . . . , αn , β1 , β2 , . . . , βn , tais que a = pα1 1 pα2 2 . . . pαnn e b = pβ1 1 pβ2 2 . . . pβnn . E a
partir destas representações de a e b, teremos

mdc(a, b) = pγ11 pγ22 . . . pγnn ,

Cap. 4 • Os números inteiros 95

onde para cada ı́ndice i, γi = min {αi , βi }.

Teorema 4.4.3. (Teorema do Número Primo de Euclides) O conjunto de números

primos é infinito.

Demonstração. Suponha que o conjunto de números primos seja finito. Escreva

o conjunto como {p1 , p2 , . . . , pn }. Considere o inteiro Q = (p1 p2 . . . pn ) + 1. O
inteiro Q é obviamente maior do que 1, portanto, é divisı́vel por um número primo,
digamos pk . Então desde que 1 = Q − (p1 p2 . . . pn ) concluı́mos pela Proposição que
1 é divisı́vel por pk . Isso é uma contradição, pois 1 é apenas divisı́vel por 1 e −1.
Portanto, o conjunto de números primos não é finito.

O problema de encontrar um algoritmo mais rápido para determinar se um dado

inteiro n é primo é um problema difı́cil. Este problema não é apenas de simples
curiosidade, mas tem aplicações na segurança da informação industrial. É possı́vel
simplesmente tomar uma sequência todos os inteiros 1 < d ≤ n e realizar uma
divisão inteira de n por d. O menor inteiro d que divide n é um número primo. Este
d satisfaz d = n se e somente se n for primo. Este método oferece um algoritmo
exaustivo para determinar se n é primo, mas muitas melhorias podem ser feitas.
Podemos encurtar o algoritmo exaustivo com o seguinte resultado.
√
Proposição 4.4.5. Se n é composto, então n tem um divisor d tal que 1 < d ≤ n.
√
Demonstração. Suponha que todos os divisores de n sejam maiores que n. Como
n é composto, existem inteiros positivos a e b maiores que 1 com n = ab. A suposição
√ √
de que a > n e b > n implica que ab = n > n, uma contradição.

Na fatorização de n no Corolário (4.4.2) temos m = pα1 1 pα2 2 . . . pαs s , com pi primos

distintos e αi são inteiros não nulos. A fotorização em números primos permite
definirmos a função ordem prima

ordp : N∗ → N

definida por
ordp (m) = k ⇔ pk | m e pk+1 - m

Exemplo 4.4.1. Seja n = 2016 dividindo por números primos apropriados, encon-
tramos que a fatorização de 2016 é 2016 = 25 × 32 × 7.
Assim, ord2 (2016) = 5, ord3 (2016) = 2, ord7 (2016) = 1, e a ordp (2016) = 0
para todo p ∈
/ {2, 3, 7}.
Seção 4.4 • O Teorema Fundamental da Aritmética 96

Podemos definir a função ordem prima para o conjunto Q da seguinte forma

m
ordp : Q>0 → Z. Seja n
uma fração escrita na forma irredutı́vel. Então: Let mn be
a
m
ordp ( ) = ordp (m) − ordp (n)
n
m 48
Exemplo 4.4.2. Seja n
= 55
. Temos que ord2 ( 48
55
48
) = 4, ord3 ( 55 ) = 1, ord5 ( 48
55
)=
−1, ord11 ( 48
55
) = −1 e a 48
ordp ( 55 ) = 0 para todo p ∈ {2, 3, 5, 11}.

Veremos em breve que dado um inteiro positivo n, contando o número de inteiros

menores que n e que são coprimos com n aparecem em inúmeros contextos. A seguir
definimos a função de Euler que faz esta associação.

Definição 4.4.3. [Função de Euler] A função de Euler é a função ϕ : N∗ → N∗ tal

que ϕ(n) é o número de inteiros positivos menores que n e que são coprimos com
n. em outras palavras,

ϕ(n) = |{a ∈ N | 1 ≤ a ≤ n e mdc(a, n) = 1}|.

Exemplo 4.4.3. Aqui exibimos algiuns cálculos de valores para função de Euler:
(1) ϕ(8) = 4, pois no conjuntos dos números inteiros menores que 8
{1, 2, 3, 4, 5, 6, 7, 8} somente 1, 3, 5, e 7 are relatively prime to 8.
(2) ϕ(20) = 48, pois para 1 ≤ a ≤ n, os únicos inteiros relativamente primos com
20 são aqueles que não são divisı́veis por 2 ou por 5. Assim, {a ∈ Z | 1 ≤ a ≤
n e mdc(a, n) = 1} = {1, 3, 7, 9, 11, 13, 17, 19}.
(3) ϕ(243) = ϕ(35 ) = 35 − 34 = 243 − 81 = 162, pois os inteiros que são coprimos
com 243 são aqueles que não não divisı́veis por 3.

Proposição 4.4.6. Se um inteiro n positivo tem decomposição em fatores primos

dada por
n = pα1 1 pα2 2 . . . pαk k .

Então,
ϕ(n) = (pα1 1 − pα1 1 −1 )(pα2 2 − pα2 2 −2 ) . . . (pαk k − pαk k −1 )

A prova deste fato é deixada para o leitor.

Cap. 4 • Os números inteiros 97

4.5 Aritmética Modular

Nesta seção, assumimos que n representa um número inteiro maior ou igual a 2.
Um dos teoremas frequentemente apresentados como destaque em uma introdução
à aritmética modular, o Pequeno Teorema de Fermat, data de 1640. No entanto,
muitas propriedades das congruências, uma noção fundamental na aritmética mo-
dular, aparecem nos primeiros trabalhos de Leonhard Euler sobre os teoria dos
números, por volta de 1736. A formulação moderna de congruências apareceu pela
primeira vez em Gauss “Disquisitiones Arithmeticae” em 1801. Ele aplicou a te-
oria das congruências ao estudo das equações diofantinas, equações algébricas em
que procuramos apenas soluções inteiras. Apresentamos a aritmética modular aqui
por seu valor fundamental na teoria dos números e porque a aritmética modular
fornecerá exemplos relativamente fáceis de grupos mais adiante.
Em matemática, coisas que são consideradas diferentes em algum contexto po-
dem ser vistas como equivalentes em outro contexto. Por exemplo, a soma 2 + 1 e
4 + 4 são diferentes na aritmética ordinária, mas veremos que na aritmética módulo
5 são iguais.
Triângulos congruentes são posicionados diferentemente no plano não são o
mesmo, mas eles podem ser considerados como o mesmo no plano geométrico. Em
fı́sica, vetores que possuem a mesma magnitude e direção podem produzir dferentes
efeitos um peso de 10 quilos colocado 2 metros de uma fulcro (sustentáculo) pro-
duz um efeito diferente de um peso de 10 quilos colocado um pé a partir de um
ponto de apoio. Mas, em álgebra linear, vetores de mesma magnitude e direção são
considerados como o mesmo.
O que precisamos é fazer estas distinções precisas em uma adequada genera-
lização da noção de igualdade, ou seja, precisamos de um mecanismo formal para
especificar se ou não duas quantidades são as mesmas em um dado contexto. Este
mecanismo é uma relação de equivalência que lembramos agora Definição (3.7.1).
Uma relação de equivalência sobre um conjunto S é um subconjunto R de
S × S satifaz as seguintes propriedades:

(1) (a, a) ∈ R para todo a ∈ S (Propriedade Reflexiva).

(2) (a, b) ∈ R ⇒ (b, a) ∈ R (Propriedade Simétrica).

(3) (a, b) ∈ R e (b, c) ∈ R ⇒ (a, c) ∈ R (Propriedade Transitiva).

Seção 4.5 • Aritmética Modular 98

Quando R é uma relação de equivalência sobre um conjunto S, escrevemos aRb

ao invés de (a, b) ∈ R. Também, como a noção de relação de equivalência é apenas
uma generalização da noção de igualdade, podemos usar os seguintes sı́mbolos ≈,
≡ ou ∼ são geralmente usados para denotar a relação. Se ∼ é uma relação de
equivalência sobre S e a ∈ S, então o conjunto {x ∈ | x ∼ a} é chamada a classe de
equivalência de S que contém o elemento a.

Exemplo 4.5.1. Seja S o conjunto de todos os triângulos de um plano. Se a, b ∈ S,

defina:
a ∼ b, se a e b são congruntes, isto é, se os correspondentes ângulos são os mesmos.

Exemplo 4.5.2. Seja S o conjunto de todos os polinômios com coeficientes reais.

Se f, g ∈ S definamos f ∼ g se, e somente se, f 0 = g 0 , onde f 0 é a derivada de f .
Então, ∼ é uma realção de equivalência sobre S. Como duas funções com derivadas
iguais diferem por uma constante, vemos que para qualquer f em S. A classe de
equivalência que contém f é dada pelo conjunto

{f + c | c é real }.

Uma importante aplicação do Algoritmo da divisão que será importante para

nós é a aritmética modular.
Seja n um inteiro positivo fixo. Defina a relação sobre Z com:

a ∼ b (mod n), se n | a − b.

Claramante a ∼ a, e a ∼ b impica que b ∼ a para quaisquer a, b inteiros, e então

esta relação é reflexiva e simétrica. Se a ∼ b e b ∼ c, então n | a − b e n | b − c, então
n divide a soma destes inteiros, isto é, n | (a − b) + (b − c) = a − c, isto significa que
a ∼ c, e desta forma esta relação é transitiva.
Portanto, ∼ é uma relação de equivalência. Definimos

Definição 4.5.1. Sejam a, b ∈ Z. Dizemos que a é congruente à b módulo a se

n| b − a e escrevemos
a ≡ b (mod n).

Se n é claro no contexto escrevemos simplesmente a ≡ b. O inteiro n é chamado o

módulo.
Cap. 4 • Os números inteiros 99

Na Seção (3.7) introduzimos a noção de classe de equivalência e conjunto quo-

ciente no contexto de relações de equivalência arbitrárias. Entretanto, a relação de
congruência tem uma longa história que carrega suas próprias notações.
Qunado o módulo é claro no contexto, denotamos a classe de equivalência de
a(modn) e chamamos ela de classe de congruência de a ou classe de resı́duo
de a mod n e a denotamos por a.
Se consideramos a divisão inteira de a por n com a = nq + r, temos que n | a − r.
Portanto, r ∈ a. De fato, caracterizamos a classe de equivalência de a de duas
formas:

a = {b ∈ Z | b ≡ a(modn)}
= {b ∈ Z | b − a = kn, para algum k ∈ Z}
= {b ∈ Z | b = a + kn, para algum k ∈ Z} = a + nZ

É importante para aplicações de congruências notar que

a ≡ 0 (mod n) ⇔ a | n

Existem precisamente, n classes distintas modn, à saber, 0, 1, 2, . . . , n − 1 de-

terminadas pelos possı́veis restos após a divisão por n e estas classes de resı́duos
particionam o conjunto Z dos números inteiros. Ao invés de escrevermos Z/ ≡ para
o conjunto quociente para a relação de equivalência congruência, escremos
Z/nZ = {0, 1, 2, . . . , n − 1} para o conjunto das classes de equivalências módulo
n. E lemos este conjunto como “Z módulo nZ”.

Exemplo 4.5.3. Suponha que n = 15, então temos as igualdades 2 = 17 = −13

e muitos outras igualdades deste tipo por que todos estes números são congruentes
um a cada outro. Também dizemos que 2, 17, −13 são representantes da classe de
congruência do 2.

O conjunto {0, 1, 2, . . . , n − 1} é um conjunto completo de resentantes dis-

tintos para a congruência módulo n. I Se n é ı́mpar, o conjunto Z/nZ =
{− n−1
2
, . . . , −2, −1, 0, 1, 2, . . . , n−1
2
}
É útil lembrar que no contexto de funções f : Z/n Z → X, onde X é um conjunto
qualquer. Se definimos f (a) = F (a) para alguma função F : Z/n Z → X, devemos
checar que realmente f é uma função. Por exemplo, digamos que f : Z/5 Z → Z
definida por f (a) = a2 . Esta função não está bem definida por que por exemplo
Seção 4.5 • Aritmética Modular 100

1 = 6, mas 1 = 12 6= 36 = 62 . Por outro lado, se dizemos f (a) é igual a k 2 , onde k

é o resto da divisão de a por 5, então está função é bem definida.
Note que para distintos n’s as relações de equivalência e classes de equivalências
são diferentes então sempre devemos ser cuidadosos em fixar o n primeiro antes de
usar a notação barra.
Podemos definir uma adição e uma multiplicação para os elementos de Z/n Z,
definindo a aritmética modular como segue.

Para a, b ∈ Z/n Z, defina sua soma e produto por:

a+b = a+b
a.b = a.b

Isto significa o seguinte: dado qualquer dois elementos a, b em Z/n Z, para cal-
cular sua soma (respectivamente o seu produto) tome qualquer representante inteiro
a na sua classe a e qualquer representante b na sua classe b e some (repectivamente,
multiplique ) os inteiros a e b como usualmente fazemos em Z e tome a classe de
equivalência contendo o resultado. O teorema seguinte diz que esta operação está
bem definida, isto é, que ela não depende da escolha dos representantes escolhidos
para os elementos a e b de Z/n Z.

Exemplo 4.5.4. Seja n = 10 e considere Z/10 Z, que consiste das classes de

resı́duos:
0, 1, 2, . . . , 9

determinada pelos possı́veis 10 restos de um inteiro após sua divisão por 10. Os
elementos da classe de resı́duos 5, por exemplo, são os inteiros que deixam resto 5
quando divididos por 10 (inteiros congruentes à 5 mod 10). qualquer inteiro con-
gruente à 5 mod 10 (tal como: 5, 15, 18, 27, . . . ou 8, −10, −13, −21, . . . ) servem
como representantes para a classe de resı́duos 5. Note que, Z/10 Z consiste de 10
emenentos e cada um destes elementos consiste de um número infinito de inteiros
usuais.
Suponha que a = 4 e b = 9. O mais óbvio representnate de a é 5 e similarmente
9 é omais óbvio representante de b. Usando estes representantes para as classes de
resı́duos obtemos:
Cap. 4 • Os números inteiros 101

4 + 9 = 13 = 3,

pois 13 e 3 estão na mesma classe módulo 10. Se tivessemos usado ao invés 4,

para a, e o representante −23, digamos, para 9, obtemos:

−23 + 9 = 13 = 4,

e como foi mensionado o resultado não depende sobre a escolha dos representan-
tes. O produto de duas destas classes é

b.b = 5.9 = 45 = 5,

e também não depende da escoha dos representantes.

Proposição 4.5.1. Seja n um inteiro fixado. Dados a, b, c, d ∈ Z e m um número

natural temos:

(1) a ≡ b (mod n) ⇔ a + c ≡ b + c (mod n);

(2) a ≡ b (mod n) e c ≡ d (mod n) ⇔ a + c ≡ b + d (mod n);

(3) a ≡ b (mod n) ⇔ ac ≡ bc (mod n);

(4) a ≡ b (mod n) e c ≡ d (mod n) ⇔ ac ≡ bd (mod n);

(5) a ≡ b (mod n) ⇔ am ≡ bm (mod n);

Demonstração. (1) a ≡ b (mod n) ⇔ n | (a − b) ⇔ n | [(a + c) − (b + c)] ⇔ a + c ≡

b + c (mod n).

(2) Sendo a ≡ b (mod n) e c ≡ d (mod n) então n | (a − b) e n | (c − d). Daı́ temos que

n | [(a − b) + (c − d)], e então n | [(a + c) − (b + d)], e assim a + c ≡ b + d (mod n).

(3) Se a ≡ b (mod n), então n | (a−b) e daı́ n | (a−b)c, isto é, n | (ac−bc). E portanto,
ac ≡ bc (mod n).
(4) Como a ≡ b (mod n) e c ≡ d (mod n), então do item (3) segue que ac ≡ bc (mod n)
e bc ≡ bd (mod n). E da transitividade vem que ac ≡ bd (mod n).
(5) Este item é deixado como exerfcı́cio.
Seção 4.5 • Aritmética Modular 102

Observação 4.5.1. (Congruências Irrelevantes) 1. Se n = 0, dados dois inteiros a

e b,

a ≡ b (mod n) ⇔ a ≡ b (mod 0) ⇔ a − b = 0 ⇔ a = b

Assim, a relação de congruência módulo 0 coincide com a relação de igualdade

em Z.
2. Se n = 1, dados dois inteiros a e b,

a ≡ b (mod n) ⇔ 1 | (a − b)

Como 1 divide qualquer inteiro, quaisquer dois inteiros a e b são congruentes módulo
1. Em vista dos itens 1 e 2 acima, as congruências módulo 0 e módulo 1 são casos
desinteressantes de congruência.

3. Dado n ∈ Z e inteiros a e b,

a ≡ b (mod n) ⇔ n | (a − b) ⇔ (−n) | (a − b) ⇔ a ≡ b (mod − n)

Assim, as congruências módulo n e módulo −n são a mesma relação de con-

gruência. Em vista das três observações trataremos de estudar a relação de con-
gruência módulo n ≥ 2 em Z.

Proposição 4.5.2. (Congruência módulo n e resto da divisão por n) Sejam a, b e

n inteiros com n ≥ 2. Então,
1. Se r é o resto da divisão de a por n, então a ≡ r (mod n).
2. Se a ≡ s (mod n) (s ∈ Z) e 0 ≤ s < m, então s é o resto da divisão de a por m.
3. a ≡ b (mod n) se, e somente se, os restos das divisões de a e b por n são iguais.

Demonstração. 1. Se a = nq +r, com q ∈ Z, então a−r = nq implica que n | (a−r),

e daı́ temos que a ≡ r (mod n).

2. Sendo a ≡ s (mod n), temos que a−s = nq, para algum inteiro q. Daı́, a = nq +s,
com q e s inteiros e 0 ≤ s < |n| = n. Pelo Teorema do Algoritmo da Divisão em Z,
s é o resto da divisão de a por n, já que o resto e o quociente dessa divisão são únicos.

3. Seja r o resto da divisão de a por n. Pelo item 1, a ≡ b (mod n), pelas propriedades
Cap. 4 • Os números inteiros 103

da relação de congruência módulo n, Proposição (4.5.2) teremos b ≡ r (mod n).

Como 0 ≤ r < m, pelo item 2, r é o resto da divisão de b por n.

Intuitivamente falando, a Proposição (4.5.1) itens (2) e (4) mostra que a relação
de congruência se comporta bem com respeito a classes de congruência módulo n.
Mais precisamente, a função adição

A : Z/nZ × Z/nZ → Z/nZ

(a, b) 7→ a + b

é bem definida, bem como a função multiplicação.

A aritmética modular módulo n é a aritmética que se origina das operações de
adição e de multiplicação sobre o conjunto Z/nZ.

Exemplo 4.5.5. Para ilustrar exemplos de aritmética modular, mostramos as tabe-

las de adição e multiplicação para Z/5Z e para Z/6ZTo Em Z/5Z = {0, 1, 2, 3, 4},
as tabelas são:

Em Z/6Z = {0, 1, 2, 3, 4, 5}, as tabelas são:

As tabelas de adição e de multiplicação para Z/5Z e Z/6Z apresentam algumas

semlhança e também diferenças.
Os padrões nas tabelas de adição são similares. Em Z/5Z todo lemento diferente
de zero tem um inverso multiplicativo, isto é, algum b 6= 0 tal que ab = 1. entretanto,
em Z/6Z os elementos 2, 3, e 4 não tem inverso. Além disso, em Z/6Z, existem
elementos não nulos a, b tais que ab = 0
Daremos exemplos do emprego de congruências módulo n no cálculo de restos
de divisões euclidianas. Note que no primeiro exemplo o dividendo considerado é
Seção 4.5 • Aritmética Modular 104

tão grande que nos impede de computar o quociente da divisão.

Exemplo 4.5.6. Determinar o resto da divisão de 2364638564 por 7. Em virtude

da Proposição (4.5.2), basta determinar um inteiro r, com 0 ≤ r < 7 satisfazendo
2364638564 ≡ r(mod 7). Temos inicialmente

2364 ≡ 5(mod 7).

Pois, 2364 deixa resto 5 quando dividido por 7. Daı́, 2364 ≡ 5(mod 7), implica que
23642 ≡ 52 (mod 7) e 252 ≡ 4(mod 7). Então, 23642 ≡ 4(mod 7). Agora,

n 2364 ≡ 5 (mod 7)
⇒ 23643 ≡ 5.4 = 20 ≡ 6(mod 7)
23642 ≡ 4 (mod 7)

n 2364 ≡ 5 (mod 7)
2
⇒ 23643 ≡ 5.4 = 20 ≡ 6(mod 7)
2364 ≡ 4 (mod 7)
E finamente,

23644 .23641 ≡ 5.2 = 10(mod 7) ⇒ 23645 ≡ 3(mod 7)

E como 23646 ≡ 1 (mod 7) , escrevendo 638564 = 6m + s, temos

236463856 ≡ 23646m+s (mod 7) = 23646m .2364s

= (23646 )m .2364s (mod 7) .
= 1.2364s ≡ 2364s (mod 7)

Portanto, dividindo 638564 por 6, obtemos 638564 = 6m + 2, logos = 2 e então

236463856 ≡ 23642 ≡ 4(mod 7) .

Logo o restoda divisão é 4.

Introduzimos a aritmética modular aqui porque ela oferecerá exemplos de grupos

e anéis quando introduzirmos essas estruturas algébricas. Mais importante para a
teoria dos números, entretanto, a aritmética modular oferece técnicas para provar
propriedades de divisibilidade que seriam mais difı́ceis de provar de outra forma.

Exemplo 4.5.7. Neste exemplo, consideramos a divisibilidade de inteiros por 3.

Portanto, trabalhamos o módulo 3. Seja n um inteiro positivo escrito na base 10
como n = bk bk−1 . . . b1 b0 , com o que queremos dizer que n = bk 10k + bk−1 10k−1 +
Cap. 4 • Os números inteiros 105

· · · + b1 10 + b0 100 , onde 0 ≤ bi < 10 para todos bi . Notamos que 10 ≡ 1mod3. Então

102 ≡ 12 ≡ 1, 103 ≡ 13 , . . . , 10k ≡ 1, para todo k ∈ N. Então,

n ≡ bk 10k + bk−1 10k−1 + · · · + b1 10 + b0 100 ≡ bk + bk−1 + · · · + b1 + b0 (mod3).

Portanto, um inteiro n tem o mesmo resto quando dividido por 3 que o resto da
soma de seus dı́gitos (algorismos) quando dividido por 3. Em particular, um inteiro
n é divisı́vel por 3 se e somente se a soma de seus dı́gitos for divisı́vel por 3 .

Usar o termo “aritmética” significa a habilidade de fazer adição, multiplicação,

subtração e divisão; resolver equações; e estudar várias propriedades entre essas
operações. A subtração de dois elementos é definida

a − b = a + −b,

onde −b, é o inverso aditivo de b. O inverso aditivo de b é um elemento c tal que

b + c = b + c = 0. Podemos tomar −b = −b. Se usarmos {0, 1, 2, . . . , n − 1}
como o conjunto completo de representantes distintos, escreverı́amos −b = n − b.
No entanto, como a tabela de multiplicação para Z/6Z no Exemplo (4.5.5) ilustra,
existem elementos diferentes de zero que não têm inversos multiplicativos. Esta é
apenas uma das diferenças entre a aritmética em Z e Q e a aritmética modular.

Definição 4.5.2 (Unidade de Z/nZ). Se a tiver um inverso multiplicativo, este será

chamado de unidade. Denotamos o conjunto de unidades em Z/nZ como U (n) =
{a ∈ Z/nZ | ∃ c ∈ Z/nZ, ac = 1}. Denotamos o inverso de a por a−1 .

Proposição 4.5.3. O conjunto das unidade de Z/nZ é U (n) = {a ∈

Z/nZ | mdc(a, n) = 1}.

Demonstração. Suponha que ac = 1. Então, ac = 1(mod n) e assim existe k ∈ Z tal

que ac = 1+kn. Portando, existe uma combinação linear de a e n que é 1. O número
1 é o menor inteiro positivo então pela Proposição (4.3.1) segue que mdc(a, n) = 1.
Isto mostra que se a é um elemento inversı́vel módulo n, então a é relativamente
primo com n. Reciprocamente, suponha que mdc(a, n) = 1, novamente usando a
Proposição (4.3.1) existem s, t ∈ Z tal que sa + rt = 1. Assim, sa = 1 − tn, e desta
forma sa ≡ 1(mod n). E a proposição fica provada.

Corolário 4.5.1. O número de unidades de Z/nZ é |U (n)| = φ(n) (a função de

Euler).
Seção 4.5 • Aritmética Modular 106

Demonstração. Usaremos o conjunto {0, 1, 2, . . . , n − 1} A função de Euler φ(n)

fornece o número de inteiros a ∈ {0, 1, 2, . . . , n − 1} tal que mdc(a, n) = 1, pela
Proposição (4.5.3) temo que |U (n)| = φ(n).

Note que não faz sentido dizer, que por exemplo, o inverso de 2 módulo 5 é
1 1
2
. A fração 2
é um elemento especı́fico em Q. As seguintes sentenças em Q são
−1 −1 −1
adequadas 2 = 12 . Em Z/5Z, 2 = 3. E em Z/5Z, 2 não existe (veja tabela de
multiplicação).
Encontrar o inverso de a em Z/nZ não é fácil, especialmente para valores grandes
de n. Se n for pequeno, então podemos encontrar o inverso por inspeção (observando
a tabela de multiplicação). A prova da Proposição (4.5.3) mostra que s = a−1 na
com combinação linear sa + tn = 1, que é verdadeira para alguns inteiros s e t se a
tiver um inverso módulo n. O Algoritmo Euclidiano extendido descrito no Exemplo
(4.3.3) fornece um método para encontrar tais s e t.

Exemplo 4.5.8. Procuremos o inverso de 79 em Z/123Z. Escreveremos o Algo-

ritmo de euclides, e na direita o Algoritmode Euclides extendido aplicado para 123
e 79. (O procedimento deve ser lido de cima para baixo na metade esquerda e de
baixo para cima na metade direita.)

123 = 79 × 1 + 44 1 = (123 − 79) × 9 − 79 × 5 = 123 × 9 − 79 × 14

79 = 44 × 1 + 35 1 = 44 × 4 − (79 − 44) × 5 = 44 × 9 − 79 × 5
44 = 35 × 1 + 9 1 = (44 − 35) × 4 − 35 × 1 = 44 × 4 − 35 × 5
35 = 9 × 3 + 8 1 = 9 − (35 − 9 × 3) × 1 = 9 × 4 − 35 × 1
9 = 8×1+1 1 = 9−8×1
De acordo com a Proposição (4.3.1), o Algoritmo de Euclides diz que
mdc(123, 79) = 1 e estabelece que 79 tem inverso em Z/123Z. A igualdade
1 = 123 × 9 − 79 × 14 fornece que 1 ≡ −14 × 79 ≡ 109 × 79(mod 123). Assim, em
−1
Z/123Z, temos que 79 = 109.

−1
Exemplo 4.5.9. Seja n = 13. Calculemos 3 (6 − 11). Primeiro observe que
−1
3 = 9, já que 3 × 9 = 27 ≡ 1(mod 13). Assim,

−1
3 (6 − 11) = 9 × (6 − 11) = 9(−5) = −45 = −6 = 7.

Exemplo 4.5.10. Considere a equaçào 3x + 7 ≡ 5(mod 11). Podemos resolvê-la

pesquisando exaustivamente o conjunto {0, 1, . . . , 10} para descobrir os valores de x
Cap. 4 • Os números inteiros 107

que a satisfazem. Outra maneira para resolvê-la é usar métodos padrões da álgebra
do modo que segue

3x + 7 ≡ 5 ⇔ 3x ≡ 5 − 7 ≡ 9
⇔ 4 × 3x ≡ 4 × 9 é o inverso de 3 módulo 11
⇔ x≡3
Assim, todos os inteiros que resolvem a equação de congruência são os x tais que
x ≡ 3(mod11).

Exemplo 4.5.11. Suponha que estamos considerando o conjunto quociente Z/15Z.

Mostramos como resolver a equação 7x + 10 = y. Observe primeiro que 27 = 14 =
−1. Portanto, −2 = 13 é o inverso multiplicativo de 7 módulo 15. Agora temos

7x + 10 = y ⇒ 7x = y − 10 ⇒ −27x = −2(y − 10) ⇒ x = −2y + 20 = 13y + 5.

Se um inteiro a for maior que 2 em valor absoluto, então em Z o valor absoluto

das potências ak aumentarão sem limite. No entanto, uma vez que Z/nZ é um
conjunto finito, as potências de a em Z/nZ possuem padrões interessantes.

Exemplo 4.5.12. Calcularemos as potências de 2 e 3 em Z/7Z.

Note que as potências seguem um padrão. Isto por causa que se a ∈ Z/nZ e
ak = ak+l , então
ak+2l = ak+l al = ak al = ak+l = ak .

e, por indução, provamos que ak+ml = ak, para todos m ∈ N. Observando o

padrão para 3, vemos que por exemplo que, em congruências,

33201 ≡ 36×533+3 ≡ (36 )533 33 ≡ 33 ≡ 33 ≡ 6(mod 7.)

Portanto, usando congruências, calculamos facilmente o restante de 33201 quando

dividido por 7, sem nunca calcular 33201 , que tem |log10 (33210)| + 1 = |3201log10 3| =
1, 528 dı́gitos.

Alguns dos padrões da potências de um número em um determinado módulo

nem sempre são fáceis de detectar. O seguinte teorema fornece um resultado geral.
Seção 4.6 • Princı́pio de Indução Finita 108

Teorema 4.5.1. Seja p um número primo e a um inteiro com p - a. Então ap−1 ≡

1(mod p).

Demonstração. Pela Proposição (4.5.3) e como um primo p é relativamente primo

com inteiro positivo a menor que ele mesmo, então p - a se, e somente se, a é uma
unidade módulo p. Observe que |U (p)| = p − 1. Considere a sequência de classes
de congruência a, a2 , a3 , . . . Isso significa que esta sequência para em Z/pZ, muitos
termois se repetem, então existem i, j ∈ N tais que aj = ai . Assim, multiplicando
j
ambos os lador por a−1 obtemos:

i
aj a−1 = 1 ⇔ aj−i = 1.

Seja k o menor inteiro positivo tal que ak = 1. Observe que os

elementos{1, a, a2 , . . . , ak−1 } são todos distintos. Defina a relação de equivalência
em U (p) por:

b ≡ c para significar b = caj para algum j ∈ Z.

Cada classe de equivalência tem a forma {c, ca, ca2 , . . . , cak−1 } para algum c, em
particular tem k elementos. Como as classes de equivalência formam uma partição
de U (p), desta forma a fração (p − 1)/k conta o número de classes de equivalência
e, portanto, é um inteiro. Portanto, k|(p − 1) e, assim

ap−1 = 1.

Observamos que a notação Z/nZ vem de conjuntos de quocientes e é consis-

tente com grupos quocientes que discutiremos posteriormente. Entretanto, se p é
um número primo, então Z/nZ tem a estrutura especial de corpo. Por causa da
importância particular da aritmética modular sobre um primo, também denotamos
Z/pZ por Fp .

4.6 Princı́pio de Indução Finita

A lógica, um predicado P (x) é uma afirmação verdadeira ou falsa, dependendo
do que valor especı́ficado para a variável x. Por exemplo, a expressão algébrica
Cap. 4 • Os números inteiros 109

“x ≥ 1” é um predicado porque não é verdadeira nem falsa por si só, mas tem um
valor verdade que depende do valor numérico de x. Dizemos que um predicado P (x)
é um instanciado quando x recebe um valor.
Os chamados princı́pios de indução finita nos provêem um método para demons-
trar propriedades dos nú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 na demosntração os princı́pios de indução finita primeira forma e segunda
forma são consequências da Proposição (4.2.2) e portanto é uma consequência do
Princı́pio da Boa Ordenação.
Lembremos uma vez mais o Princı́pio da Boa Ordenação (PBO) que afirma que
cada conjunto não vazio de números naturais possui um menor elemento.

Teorema 4.6.1. [Princı́pio da Indução Finita Primeira Forma] Seja n0 um número

inteiro e suponhamos que a cada inteiro n, com n ≥ n0 , está associada uma
afirmação P (n), a qual possui, para cada n, um valor lógico V (quando verdadeira)
ou F (quando falsa). Suponhamos que as condições 1 e 2 abaixo sejam válidass:
(1) A afirmação P (n) é verdadeira para n = n0 ;
(2) Para cada k ≥ n0 , se P (k) é verdadeira, então (é possı́vel demonstrar que)
P (k + 1) é também verdadeira. Então a afirmação P (n) é verdadeira para cada
n ≥ n0 .

Antes de passarmos para a demonstração do Primeiro Princı́pio da Indução Fi-

nita,vejamos o seguinte exemplo.

Exemplo 4.6.1. Para cada inteiro n, n ≥ 0, o inteiro 9n − 1 é divisı́vel por 8.

De fato, a afirmação P (n) que vamos provar ser verdadeira para cada inteiro n ≥ 0,
é a seguinte:
P (n) : 9n − 1 é divisı́vel por 8.

A prova consiste em verificar a validade de P (n) em apenas duas instâncias, reali-

zando duas verificações (daı́ o nome indução finita), a saber, verificamos a validade
da afirmação (i) P (n) para n = 0, considerando um inteiro k qualquer, k ≥ 0, supo-
mos que a afirmação P (n) já esteja valendo para n = k (esta suposição é chamada
hipótese de indução) e, a partir disto, deduzimos que afirmação P (n) também vale
para n = k + 1.
Se n = 0, P (n) = P (0) é a afirmação é 90 − 1 = 0, que é divisı́vel por 8, portanto
A(0) éverdadeira.
Seção 4.6 • Princı́pio de Indução Finita 110

Seja então k um inteiro, k ≥ 0, e admitamos a hipótese de indução, isto é, que

P (k) é verdadeira, e então 9k −1 é divisı́vel por 8. Provaremos que então que 9k+1 −1
também é divisı́vel por 8. Por hipótese de indução 9k − 1 = 8m para algum inteiro
m. Logo, 9k = 8m + 1. Como consequência temos então 9k+1 − 1 = 9k .9 − 1 =
(8m + 1)9 − 1 = 72m + 9 − 1 = 72m + 8 = 8(9m + 1), e assim, acabamos deduzindo
que 9k+1 − 1 = 8(9m + 1) é um múltiplo inteiro de 8, ou seja, também é divisı́vel
por 8.
Portanto temos que se P (k) é verdadeira, então P (k + 1) é verdadeira.
Logo, pelo Primeiro Princı́pio de Indução Finita, que P (n) é verdadeira para
cada n ≥ 0, ou seja, que 9n − 1 é divisı́vel por 8 para cada n ≥ 0.

Uma imagem mental comum para indução é uma cadeia de dominós que começa
em um determinado ponto, mas continua infinitamente. Suponha que o n-ésimo
dominó caia e suponha também que se um dominó cair, então o subsequente cai
também. Então, o n-ésimo dominó e todos os dominós depois dele cairão.

Figura 4.1: Dominó

Na Figura 4.1, o primeiro dominó a cai, e depois o segundo, e sucessivamen-

tes todos os dominós também cairão. O Princı́pio de Indução, conforme afirmado
acima, também é chamado de indução primeira forma em contraste com a indução
segunda forma, discutido anteriormente. Em uma prova de indução onde n0 é dado,
chamamos a etapa de provar P (n0 ) de etapa básica. A etapa básica geralmente é
fácil, especialmente quando requer apenas uma verificação de cálculo. A parte de
uma prova de indução que envolve provar P (n) → P (n + 1) para todo n ≥ n0 é
chamada de passo de indução. Durante a etapa de indução, comumente se refere a
P (n) como a hipótese de indução.
Passaremos agora a prova do princı́pio de indução primeira forma:
Cap. 4 • Os números inteiros 111

Demonstração do Princı́pio de Indução Primeira Forma. Veremos agora que am-

bos os princı́pios de indução finita são consequências do Pricı́pio do Menor Elemento
(PBO). Para provar o Primeiro Princı́pio de Indução suponhamos que estejam es-
tabelecidas as hipóteses (1) e (2) do Teorema (4.6.1). Suponhamos que a tese do
teorema não seja verdadeira, isto significa que exista um inteiro s ≥ n0 tal que a
afirmação P (s) é falsa.
Seja S = {n ∈ Z | n ≥ n0 e P (n) é falsa}. Temos que o conjunto S é não vazio,
pois s ∈ S.
Sendo S ⊆ Z, e limitado inferiormente por n0 , pelo Princı́pio do Menor Elemento,
Proposição (4.2.2), item 1, S possui um menor elemento s0 .
Como n0 ≤ s0 e P (n0 ) é verdadeira, temos n0 < s0 , e então n0 ≤ s0 − 1.
Seja k = s0 − 1. Então, P (k) é verdadeira, pois k < s0 e s0 é o menor inteiro
n com P (n) falsa. Mas como k ≥ n0 e P (k) é verdadeira temos então P (k + 1)
verdadeira. Poré, k + 1 = s0 e P (s0 ) é falsa.
Assim, temos uma contradição decorrente do fato de existir um inteiro s ≥ n0
para o qual P (s) é falsa.
Portanto P (n) é verdadeira para cada inteiro n ≥ n0 .

Exemplo 4.6.2 (Números de Fibonacci). Considere a sequência de números de

Fibonacci definidas por f0 = 0, f1 = 1 e satisfazendo

fn+2 = fn+1 + fn , ∀ n ≥ 0.

Os primeiros termos desta sequência são como segue:

n 0 1 2 3 4 5 6 7 8 9 10 11
fn 0 1 1 2 3 5 8 13 21 34 55 89
Tabela 4.6.1

A sequência tem muitas propriedades interessantes. Neste exemplo, provaremos

que se 5|n então 5|fn . Precisamos expressar este problema para na forma de indução.
Propomos provar que 5|f5k , para todo inteiro não negativo k. Assim o passo base
da indução é k = 0, que é verdade, posto que 5|f5.0 = f0 = 0. Agora, supomos que
5|f5k , para algum inteiro não neativo k. Então, temos que f5k = 5m, para algum
inteiro m. Além disso,
Seção 4.6 • Princı́pio de Indução Finita 112

f5(k+1) = f5k+5 = f5k+4 + f5k+3

= (f5k+3 + f5k+2 ) + (f5k+3 = 2f5k+3 + f5k+2
= 2(f5k+2 + f5k+1 ) + f5k+2 = 3f5k+2 + 2f5k+1
= 3(f5k+1 + f5k ) + 2f5k+1 = 5f5k+1 + f5k
= 5f5k+1 + 5m = 5(f5k+1 + m).
Portanto, 5|f5(k+1) . Por indução sobre k, os números de Fibonacci f5k é divisı́vel
por 5 para todos k, que afirma que podemos afirmar que se 5|n ⇒ 5|fn

Uma segunda forma de prova por indução finita, que também pode ser utilizada,
é estabelecida pelo seguinte teorema:

Teorema 4.6.2. [Segundo Princı́pio de Indução Finita.] Seja n0 um número inteiro

e suponhamos que a cada inteiro n, n ≥ n0 , esteja associada uma afirmação P (n),
a qual possui, para cada n, um valor lógico V (quando verdadeira) ou F (quando
falsa). Suponhamos que as seguintes condições são válidas:

(1) A afirmação P (n) é verdadeira para n = n0 ;

(2) Para cada inteiro k ≥ n0 , se P (n) é verdadeira para n0 ≤ n ≤ k então P (k+1)

é também verdadeira. Então a afirmação P (n) é verdadeira para cada n ≥ n0 .

À primeira vista, o princı́pio da indução fsegunda forma parece mais poderoso do

que o primeiro princı́pio de indução. A declaração conjuntiva P (n0 ) e P (n0 +1) e . . .
e P (n) é falso não apenas quando P (n) é falso, mas quando qualquer um dos outros
predicados instanciados é falso. Uma declaração condicional p → q, significando
“se p então q” ou p implica q, é falsa quando p é verdadeiro, mas q é falso e é
verdadeiro caso contrário. Portanto, a declaração condicional P (n0 ) e P (n0 + 1)
e . . . e P (n)implica P (n + 1) será falso se todos os P (k) com n0 ≤ k ≤ n forem
verdadeiros e P (n + 1) for falso, enquanto P (n) implica P (n + 1) é falso apenas
quando P (n) é verdadeiro e P (n + 1) é falso. Assim, a etapa de indução de indução
segunda forma é menos provável de ocorrer do que a etapa de indução de indução
primeira forma. No entanto, podemos ver que a indução segunda forma e a indução
primeira forma são de fato iguais. Se a hipótese da indução for válida na indução
primeira forma, então a hipótese da indução segunda forma será válida. Por outro
lado, definindo o predicado Q(n) como “P (k) é verdadeiro para todos os inteiros k
com n0 ≤ k ≤ n, vemos que o princı́pio da indução segunda forma é simplesmente
um problema na indução primeira forma.
Cap. 4 • Os números inteiros 113

Observamos que o Princı́pio de indução finita Segunda forma difere do primeiro

na forma como é formulada a hipótese de indução. No primeiro princı́pio, supomos
que a asserção P (n) é verdadeira para n = k somente, enquanto que no segundo,
supomos P (n) é verdadeira para cada n satisfazendo n0 ≤ n ≤ k. Em ambos os
princı́pios, devemos provar que a hipótese de indução possibilita obtermos a validade
de P (n) para n = k + 1.
Antes de passarmos a demonstração do princı́pios de indução finita segunda
forma, exibiremos um teorema cuja prova pode ser feita pelo segundo princı́pio.

Teorema 4.6.3. (Representação decimal de números naturais) Para cada inteiro

n ≥ 1, existem números naturais a0 , a1 , . . . , as , (s ≥ 0), com os “algarismos”
a0 , a1 , . . . , as , tomados no conjunto {0, 1, 2, 3, . . . , 9}, e as 6= 0, tais que
s
X
n= ai 10i = as 10s + · · · + a0 100
i=0

Ilustrando o teorema acima com um exemplo, quando escrevemos, por exemplo,

50237, queremos dizer 5.104 + 2.102 + 3.101 + 7.100 .

Demonstração. Se n = 1, podemos tomar n = a0 = 1. Seja k ≥ 1 um inteiro e

suponhamos que o resultado do teorema seja verdadeiro para cada inteiro n, com
1 ≤ n ≤ k. Mostraremos que isto acarreta a validade da mesma propriedade para
n = k + 1. Com efeito, aplicando o algoritmo da divisão euclidiana de k + 1 por 10,
temos k + 1 = 10.q + r, onde 0 ≤ r < 10 (Teorema (4.3.1)).
Se q = 0, então k + 1 = r = a0 , com a0 ∈ {0, 1, 2, 3, . . . , 9}. Se q > 0, então
q ≤ k, pois se q > k, então k + 1 = 10q + r > 10k + r ≥ 10k, e assim k + 1 > 10k e
então 1 > 9k ≥ 9, o que é impossı́vel.
Sendo então 1 ≤ q ≤ k, pela hipótese de indução,

q = bt .10t + · · · + b0 .100 ,

para certos algarismos bt , . . . , b0 , todos em {0, 1, 2, 3, . . . , 9}. Entã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, 3, . . . , 9}. Logo, pelo segundo princı́pio de

indução finita, a representação decimal de n é possı́vel para cada inteiro n ≥ 1.
Seção 4.6 • Princı́pio de Indução Finita 114

Demonstraremos agora o o princı́pio de indução segunda forma

Demonstração do Princı́pio de Indução Segunda Forma. Salvo algumas modificações,

a prova é basicamente idêntica a prova apresentada acima. A única diferença se dá
nas últimas linhas da demonstração. Considere S e s0 tal como na demonstração
do primeiro princı́pio de indução. Suponha agora que estão satisfeitas as condições
(1) e (2) da hipótese do teorema.
Tal como na demonstração do princı́pio de indução primeira forma, teremos
n0 ≤ s0 − 1. Como s0 é o menor inteiro n com P (n) falsa, temos então P (n)
verdadeira para cada n tal que n0 ≤ n ≤ s0 − 1. Tomando k = s0 − 1, temos
então P (n) verdadeira para cada n satisfazendo n0 ≤ n ≤ k. Pelo item (2) da
hipótese, isto acarreta P (k + 1) verdadeira. Mas k + 1 = s0 e novamente temos uma
contradição.

A proposição a seguir é importante por si só para seções futuras. Fornecemos

aqui porque sua prova depende do princı́pio de indução segunda forma.

Proposição 4.6.1. [Operação binária] Seja S um conjunto e seja ? uma operação

binária em um conjunto S que é associativa. Em uma expressão de operação com
um número finito de termos,

a1 ? a2 ? · · · ? an , com n ≥ 3, (4.2)

todas as ordens possı́veis nas quais emparelhamos as operações (ou seja, ordens entre
parênteses) são iguais.

Demonstração. Antes de iniciar a prova, definimos uma notação temporária, mas

útil. Dada uma sequência a1 , a2 , . . . , an de elementos em S, por analogia com a
P
notação , definimos

?ki=1 ai = (. . . ((a1 ? a2 ) ? a3 . . . ak−1 ? ak )) (4.3)

Nesta notação, executamos as operações em (4.2) da esquerda para a direita.

Observe que se k = 1, a expressão é igual ao elemento a1 . Provaremos pelo Princı́pio
da indução segunda forma sobre n, que toda expressão de operação em (4.2) é igual
a ?ki=1 ai = (. . . ((a1 ? a2 ) ? a3 . . . ak−1 ? ak )). O passo básico com n ≥ 3 é precisamente
a suposição de associatividade. Agora assumimos que a proposição é verdadeira
para todos os inteiros k com 3 ≤ k ≤ n. Considere uma expressão de operação
Cap. 4 • Os números inteiros 115

(4.2) envolvendo n + 1 termos. Suponha, sem perda de generalidade, que a última

operação realizada ocorre entre o j-ésimo e o j + 1-ésimo termos, isto é,

j termos n−j termos

z }| { z }| {
q = (expressão da operação1 ) ? (expressão da operação2 )

Como ambas expressões da operação envolvem n termos ou menos, pela hipótese de

indução

q = (?ji=1 ai ) ? (?ni=j+1 ai ).

Além disso,

q = (?ji=1 ai ) ? (aj+1 ? (?ni=j+2 ai )) pela hipótese de indução

= ((?ji=1 ai ) ? aj+1 ) ? (?ni=j+2 ai ) pela associatividade
= (?j+1 n
i=1 ai ) ? (?i=j+2 ai )

Repetindo n − j − 2 vezeso argumento, concluı́mos que q = ?n+1

i=1 ai

Concluı́mos esta seção falando sobre como definir recusivamente subconjuntos

de um conjunto dado. Este método aparece nos capı́tulos seguintes. Portanto,
apresentamos a ideia aqui não como uma curiosidade, mas como um precursor de
uma prática comum. Apresentamos o conceito de definição de conjunto recursivo
com um exemplo.

Exemplo 4.6.3. Sejam a, b ∈ Z e definamos o conjunto S ⊆ Z da seguinte forma:

0 ∈ S e se x ∈ S, então x − a, x + a, x − b, x + b também estão em S. Provaremos
que S = mdc(a, b).Z, ou seja, todos os múltiplos do mdc(a, b). Primeiro mostramos
(por indução) que todo múltiplo sa ∈ S para todo s ∈ Z. Obviamente, isso é verdade
quando s = 0. Suponha que sa e −sa estão em S para algum s ∈ N. Então
sa + a = (s + 1)a ∈ S e −sa − a = (−s − 1)a ∈ S. Portanto, por indução em N,
todos os inteiros da forma sa com s ∈ Z estão em S.
Agora mostramos que todos os inteiros da forma sa + tb, para s, t ∈ Z estão em
S. Dado qualquer s, sabemos que sa ∈ S. Agora suponha que sa + tb e sa − tb estão
em S para algum t ∈ N. Então pela definição recursiva de S,

(sa + tb) + b = sa + (t + 1)b ∈ S e (sa − tb) − b = sa − (t + 1)b ∈ S.

 116

Portanto, por indução em t em N, todos os inteiros da forma sa+tb com s, t ∈ Z

estão em S. Pela Proposta (4.3.1), o conjunto de inteiros da forma sa + tb com
s, t ∈ Z é precisamente mdc(a, b)Z. Mostramos que mdc(a, b)Z ⊆ S.
Mostramos a inclusão reversa S ⊆ mdc(a, b)Z como segue. Observe que
0 ∈ mdc(a, b)Z. Além disso, se x ∈ mdc(a, b)Z, então pelas propriedades de di-
visibilidade, todos os quatro inteiros x + a, x − a, x + b, x − b serão divisı́veis pelo
mdc(a, b). Portanto, todo inteiro em S satisfaz a propriedade de ser divisı́vel pelo
mdc(a, b) e, portanto, S ⊆ mdc(a, b)Z.
Podemos agora concluimos que S = mdc(a, b)Z.

Devemos notar que a definição de S no Exemplo (4.6.3) difere das maneiras

usuais que definimos conjunto . Uma definição recursiva de um subconjunto S em
um conjunto de contexto U não lista explicitamente todos os elementos de S nem
fornece uma propriedade que pode ser testada imediatamente em cada elemento
de U . Em vez disso, uma definição recursiva contém um passo básico e um passo
recursivo dado da seguinte forma.
Etapa de base.a1 , a2 , . . . , ak ∈ S (para alguns elementos especı́ficos em U );
Etapa de recursiva. se x1 , x2 , . . . , xm ∈ S, então

f1 (x1 , x2 , . . . , xm ), f2 (x1 , x2 , . . . , xm ), . . . , fn (x1 , x2 , . . . , xm )

também estão em S, onde fi são funções U m → U .

A partir de uma definição recursiva de um conjunto, às vezes é difı́cil fornecer
uma definição não recursiva do conjunto e, portanto, decidir se um elemento está ou
não no conjunto. Na verdade, o leitor cuidadoso pode se perguntar se uma definição
recursiva de um subconjunto S de um conjunto U é bem definida, ou seja, sempre
determina um subconjunto especı́fico de U . Definições recursivas de subconjuntos
são de fato bem definidas no seguinte sentido. Seja

C = {A ∈ P(U ) | a1 , a2 , . . . , ak ∈ A e A satisfaz o passo recursivo }.

Então, o conjunto S definido recursivamente é

S = ∩ A,
A∈C

que também podemos pensar como o menor conjunto (com respeito a inclusão) que
satisfaz tanto a etapa base quanto a etapa de recursão da definição recursiva.