Fund A Mentos
Fund A Mentos
Fund A Mentos
aç
or
Fundamentos da Matemática
ab
Notas de Aula
Atualizado 11/10/2022
Em
ão
aç
or
ab
el
Em
The structure of the book is a modification of the "Legrange Orange Book"wich is a Latex template model
obtained at LaTeXTemplates.com as and licensed under the Creative Commons Attribution-NonCommercial 3.0
Unported License ( http://creativecommons.org/licenses/by-nc/3.0).
ão
Conteúdo
aç
1
or
Apresentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
ab
I Lógica e Conjuntos
2 Proposições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
el
3 Tabelas da Verdade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Cálculo Proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Em
5 Argumentação Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
7 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8 Produto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
9 Familia de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10 Relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
11 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
II Conjuntos Numéricos
12 Números Naturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
13 Cardinalidade de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
15 Divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
ão
18 Representação decimal dos números reais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
aç
20 Números Complexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
21
or
Introdução à Análise combinatória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
ab
el
Em
ão
1. Apresentação
aç
or
Este texto está composto por minhas notas de aula para o ministério da disciplina Fundamentos da Matemática.
O conteúdo do texto está baseado em material dos seguintes livros
ab
• Iezzi, G., Murakami, C., Fundamentos de Matemática Elementar, Atual Editora, 2013
• Aguilar, I.; Dias, M. Sequeiros. A Construção dos Números Reais e Suas Extensões. Rio de Janeiro:UFF,
2015.
• Roitman, J. Introduction to modern set theory. Wiley (1990).
• Saenz, J. Fundamentos de la Matemática. Hipotenusa (2005).
el
• Seymour Lipschutz - Schaum’s outline of theory and problems of set theory and related topics. McGraw-
Hill (1998)
e foi modificado e adapatado da forma que achei conveniente para o ministério das aulas.
O texto é de ajuda e guia sobre os tópicos que irei abordando ao longo do semestre com a maior quatidade
de detalhes que consegui. No entanto, recomendo fortemente que seja feita sempre uma conferência com as
Em
ão
aç
or
ab
el
2 Proposições . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Em
3 Tabelas da Verdade . . . . . . . . . . . . . . . . . 13
4 Cálculo Proposicional . . . . . . . . . . . . . . . 15
5 Argumentação Lógica . . . . . . . . . . . . . . . 23
6 Quantificadores . . . . . . . . . . . . . . . . . . . . . 33
7 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8 Produto Cartesiano . . . . . . . . . . . . . . . . . . 53
9 Familia de conjuntos . . . . . . . . . . . . . . . . 57
10 Relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
11 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Em
el
ab
or
aç
ão
ão
2. Proposições
aç
or
Em matemática utilizamos uma linguagem com termos e expressões específicas e com significados precisos.
Começamos a estudar estes termos e expressões
ab
Definição 2.1 Uma proposição é uma sentença declarativa, por meio de palavras ou termos, e cujo conteúdo
é submetido a juízo no qual poderá ser considerado Verdadeiro (V) ou Falso (F). Estes verdadeiros ou falsos
correspondem ao valor lógico da proposição.
• Princípio da Exclusão: uma proposição só pode ser verdadeira ou falsa, não existindo possibilidade de
uma terceira opção.
• Princípio da Identidade: uma proposição verdadeira é verdadeira e uma falsa é falsa.
• Princípio da não contradição: nenhuma proposição é verdadeira e falsa simultâneamente.
Em
Definição 2.2 Um Paradoxo ou Absurdo é uma sentença declarativa que não possue valor de verdade
verdadeiro nem falso e, portanto, não é proposição.
Algumas proposições tem seu valor de verdade fixo e não pode ser provado ou demonstrado.
Definição 2.3 Um axioma é uma proposição que aceitamos como verdadeira e que não admite demonstração.
dos catetos"(Falso)
• P="a soma dos ângulos internos de um triângulo retângulo no plano é menor do que π"(Falso)
• P="Brasilia é a capital do Brasil"(Verdadeiro)
• P="52 = 25"(Verdadeiro).
• P="7 > 5"(verdadeiro)
• P="2 < π"(verdadeiro)
O que não é proposição:
• "O número π tem propriedades tão interessantes!"(sentença exclamativa)
• "Tomara seja um número par"(sentença optativa)
ão
• "Será que a2 + b2 < a + b?"(sentença interrogativa)
• "Faça a conta para mostrar que (−2)2 = 4” (sentença imperativa )
• Opiniões não são proposições.
• Sentenças abertas também não são proposições: "quanto devo adicionar a 2 para obter 5?
aç
Dadas certas proposições P e Q podemos criar novas proposições fazendo operações sobre elas. Passamos a
descrever estas operações:
• Negação: Dada uma proposição P formamos uma nova proposição "não P" que é a negação de P e é
denotada por ¬P.
por P ∧ Q.
or
• Conjunção: Dadas duas proposições P e Q formamos uma nova proposição "P e Q" e que é denotada
• Disjunção Dadas duas proposições P e Q formamos uma nova proposição "P ou Q" e que é denotada por
P ∨ Q.
ab
• Condicional: Dadas duas proposições P e Q formamos uma nova proposição "se P então Q" e que é
denotada por P ⇒ Q. Neste caso P é denominada "condição suficiente ou hipótese" e Q é chamada de
"condição necessária ou conclusão".
• Bicondicional: Dadas duas proposições P e Q formamos uma nova proposição "P se, e somente se, Q"e
que é denotada por P ⇔ Q .
el
Observamos que com estas operações lógicas podemos formar novas proposições a partir de proposições simples.
Chamamos estas proposições de proposições compostas.
Exemplo 2.3 Sejam P, Q, R, S proposições, então
P ∨ [(Q ∧ ¬R) ⇒ S] ⇔ (Q ∧ P)
Em
ão
Obs.
O sistema lógico que estamos trabalhando só temos, como vimos, dois valores de verdade (V ou F) no
aç
entanto há outros sistemas lógicos em que o número de valores de verdade pode ser maior. Existe, por
exemplo, a lógica de n ∈ N valores de verdade para a lógica de E. Post ou a lógica difusa ou Fuzzy em que
há tantos valores de verdade como pontos no intervalo real [0, 1].
or
ab
el
Em
Em
el
ab
or
aç
ão
ão
3. Tabelas da Verdade
aç
or
Como dizemos anteriormente, uma proposição tem um valor de verdade (Verdadeira ou Falsa). Vamos ver
agora qual é o valor de verdade das proposições compostas obtidas a partir das operações negação, conjunção,
ab
disjunção, condicional e bicondicional.
Junto a isto vamos construir um dispositivo muito útil no estudo da lógica matemática que são as tabelas
da verdade. Com elas poderemos definir valor lógico de uma proposição composta em função dos valores de
verdade das proposições que a compõem.
• Negação: Para a negação temos a seguinte regra,
el
V F
F V
• Conjunção: Para a conjunção temos a seguinte regra: Sejam P e Q duas proposições, então a proposição
P ∧ Q é verdadeira se, e somente se, P e Q são verdadeiras.
Podemos resumir isto na seguinte tabela.
P Q P∧Q
V V V
V F F
F V F
F F F
• Disjunção: Para a disjunção temos a seguinte regra: Sejam P e Q duas proposições, então a proposição
P ∨ Q é falsa se, e somente se, P e Q são falsas.
Podemos resumir isto na seguinte tabela.
P Q P∨Q
V V V
V F V
F V V
F F F
14 Capítulo 3. Tabelas da Verdade
• Condicional: Para o condicional temos a seguinte regra: Sejam P e Q duas proposições, então a proposição
P ⇒ Q é falsa se, somente se, P e verdadeiro e Q é falso.
Podemos resumir isto na seguinte tabela.
P Q P⇒Q
V V V
V F F
F V V
F F V
ão
• Bicondicional: Para a proposição bicondicional temos então a seguinte regra: P ⇔ Q é verdadeira se os
valores de verdade de P e Q coincidem e falsa no caso contrário
Podemos resumir isto na seguinte tabela.
P Q P⇔Q
aç
V V V
V F F
F V F
F F V
or
Com estas tabelas básicas podemos formar as tabelas das proposições compostas (uma proposição formada a
partir de outras proposições utilizando conectivos lógicos, veremos isto depois) seguindo o seguinte roteiro:
Dada uma uma formula proposicional construímos uma tabela-verdade da seguinte forma
• Na linha superior colocamos as subfórmulas da fórmula proposicional. Dispondo de menor a maior na
ab
formação da proposição.
• Para cada subformula teremos uma coluna.
• As proposições básicas sobre as quais esta construida a proposição por meio das operações lógicas são
colocadas nas primeiras colunas.
• Completamos as linhas em função dos valores de verdade das proposições básicas. Observar que se temos
el
P Q R (P ∨ Q) (P ∨ Q) ∧ R
V V V V V
Em
V V F V F
V F V V V
V F F V F
F V V V V
F V F V F
F F V F F
F F F F F
ão
4. Cálculo Proposicional
aç
or
Como vimos anteriormente a partir de proposições simples podemos formar, utilizando operadores lógicos,
proposições compostas.
ab
O conjunto das proposições munido das operações negação, conjunção, disjunção formam uma álgebra que
é a chamada álgebra proposicional. Com ela podemos fazer "contas". Passamos agora estudar essa álgebra.
Uma fórmula proposicional é uma regra, construída a partir de um número finito de conectivos lógicos,
que pode ser aplicada a um conjunto de proposições,
el
P(Q1 , . . . , Qk ).
Nesse caso a regra P é a fórmula e as entradas Q1 , . . . , Qk são as variáveis. Ao aplicar uma fórmula proposicional
P(Q1 , . . . , Qk )
Em
P(R1 , . . . , Rk ).
A proposição assim obtida é chamada de proposição composta, isto é, uma proposição composta é uma
proposição P que é obtida ao aplicar uma fórmula proposicional a um conjunto de proposições.
Dada uma fórmula proposicional P(Q1 , . . . , Qk ) e um conjunto de proposições R1 , . . . , Rk produzimos uma
proposição composta
P = P(R1 , . . . , Rk ),
o valor lógico de P é obtido em função dos valores lógicos das proposições R1 , . . . , Rk e das tabelas da verdade
para os conectivos lógicos utilizando para definir P.
Exemplo 4.1 Por exemplo
• Considere a fórmula
P1 (P) = ¬(¬(P).
P = ”5 < 6”,
16 Capítulo 4. Cálculo Proposicional
teremos
P1 (P, Q) = P ∧ (P ⇒ Q).
ão
P = ”O número π é irracional” Q = ”π < 5”
teremos
aç
P1 (P, Q) = ”O número π é irracional e se número π é irracional então π < 5 .”
Em particular se P é falsa, para qualquer valor lógico que assuma Q a proposição P1 (P, Q) será falsa.
• Considere a fórmula
P1 (P, Q, R) = R ∨ (P ∧ Q).
P = ”5 < π”
or
Q = ”5 é número impar” R = ”2 divide a 3”
ab
teremos,
Se R é verdadeira então para qualquer valor lógico que assuumam P e Q a proposição P1 (P, Q, R) será
verdadeira.
lentes se elas assumem valores lógicos iguais para quaisquer escolha dos valores lógicos que podem assumir
as variáveis Q1 , . . . , Qk .
Para provar que duas fórmulas proposicionais são equivalentes podem ser utilizadas tabelas da verdade. A
seguir vemos alguns exemplos que mostrar algumas equivalência básicas de fórmulas proposicionais.
- Dupla Negação: "¬(¬P) = P"
De fato
P ¬P ¬(¬P)
V F V
F V F
- Idempotência:
”P ∨ P = P” e ”P ∧ P = P”.
De fato
P P∨P P∧P
V V V
F F F
17
- Comutatividade:
”P ∨ Q = Q ∨ P” e ”P ∧ Q = Q ∧ P”.
ão
P Q O (P ∨ Q) (Q ∨ O) P ∨ (Q ∨ O) (P ∨ Q) ∨ O
V V V V V V V
V V F V V V V
V F V V V V V
aç
V F F V F V V
F V V V V V V
F V F V V V V
F F V F V V V
- Distributividade:
F F F
”P ∨ (Q ∧ O) = (P ∨ Q) ∧ (P ∨ O)”
F
or
e
F F F
”P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∨ O)”.
ab
Novamente mostramos um pois o outro é análogo
P Q O (P ∨ Q) (P ∨ O) (Q ∧ O) P ∨ (Q ∧ O) (P ∨ Q) ∧ (P ∨ O)
V V V V V V V V
V V F V V F V V
el
V F V V V V V V
V F F V V F V V
F V V V V V V V
F V F V F F F F
F F V F V F F F
Em
F F F F F F F F
- Leis de De Morgan:
P ¬P (P ∨ ¬P) Q (P ∨ ¬P) ∧ Q
V F V V V
V F V F F
F V V V V
F V V F F
18 Capítulo 4. Cálculo Proposicional
”P ∨ Q = Q” e ”P ∧ Q = P”.
De fato
P Q (P ∨ Q)
V V V
F V V
ão
e
Q P (P ∧ Q)
V V V
V F F
aç
Obs. Da mesma forma que provamos as equivalências acima, podemos mostrar as seguintes:
• P ⇒ Q = (¬P ∨ Q). De fato
P ¬P Q P⇒Q ¬P ∨ Q
V
V
F
F
V
V
F
F
or V
F
V
F
V
F
V
V
V
F
V
V
ab
Trataremos, daqui para frente, a identidade
P ⇒ Q = ¬P ∨ Q
P ⇔ Q = (P ⇒ Q) ∧ (Q ⇒ P)
é equivalente a
P⇒Q = ¬P ∨ Q
= ¬[P ∧ (¬Q)].
ão
Lema 4.1 Se R é uma proposição falsa então P ∧ R é falsa e P ∨ R = P.
aç
= ¬R → De onde R falsa garante P ∧ R é falsa.
Para a segunda, vemos que
¬(P ∨ R) = ¬P ∧ ¬R
= ¬P → De onde R é falsa garante (P ∨ R) = P.
é sempre verdadeira para qualquer valor que possa assumir P, e a fórmula proposicional
R2 (P) = P ∧ ¬P
el
V F V
F V V
Da mesma forma, P ∧ ¬P é sempre falsa. De fato,
P ¬P P ∧ ¬P
V F F
F V F
ão
F V F V F V V
F F V V V V V
• Dadas P e Q proposições, vamos mostrar que a fórmula
R(P, Q) = P ∧ ¬(Q ∨ P)
aç
é uma contradição.
De fato, construindo a tablea de verdade vemos que:
P Q Q∨P ¬(Q ∨ P) P ∧ ¬(Q ∨ P)
V V V F F
V
F
F
F
V
F
V
V
F
or F
F
V
F
F
F
ab
Com as leis e resultados acima podemos fazer contas com as proposições. Vejamos a seguir alguns exemplos.
Exemplo 4.3 Vamos mostrar que as seguintes equivalências entre fórmulas proposicionais
P ∨ (P ∧ Q) = P e P ∧ (P ∨ Q) = P,
Demonstração. Observamos que se R é uma proposição que sempre é verdadeira, temos que
P ∨ (P ∧ Q) = (P ∧ R) ∨ (P ∧ Q) (R é verdadeira)
= P ∧ (R ∨ Q) (distributividade)
ão
= P ∧ R (R é verdadeira)
= P (R é verdadeira).
Também
P ∧ (P ∨ Q) = ¬[¬P ∨ ¬(P ∨ Q)] (dupla negação)
aç
= ¬[¬P ∨ (¬P ∧ ¬Q)] (De Morgan)
= ¬[¬P] (resultado anterior)
= P (dupla negação).
or
ab
el
Em
Em
el
ab
or
aç
ão
ão
5. Argumentação Lógica
aç
or
A argumentação lógica é uma organização ou estruturação de proposições pela qual, junto com as regras da
lógica, chegamos a uma conclusão ou solução. Ela é importante pois nos permite, principalmente, encontrar o
ab
caminho correto para a resolução de um problema. No entanto, claramente, ajuda na resolução de problemas
práticos do dia a dia.
Definição 5.1 Sejam P e Q duas proposições. Dizemos que P implica logicamente Q (ou P implica Q) e o
denotamos por
el
P ` Q.
se a proposição composta
P1 (P, Q) = [P ⇒ Q]
Em
é verdadeira.
Obs. Lembramos que se P e Q são duas proposições temos que a tabela da verdade do condicional é
P Q P⇒Q
V V V
V F F
F V V
F F V
Portanto, para que o condicional seja verdadeira temos que pedir que se P é verdadeira, então Q é verdadeira.
Veremos isso com mais detalhes depois.
Definição 5.2 • Um raciocínio ou argumento lógico é a afirmação de que uma proposição C, cha-
mada conclusão, é consequência de outras proposições, P1 , . . . , Pn , chamadas premisas. Neste caso,
denotamos
{P1 , · · · , Pn } ` C
24 Capítulo 5. Argumentação Lógica
• Um argumento é válido ou correto se a conjunção das premisas implica lógicamente a conclusão, isto
é, se a fórmula
P1 ∧ · · · ∧ Pn ` C.
ão
• Uma falácia e um raciocínio que não é válido.
Vamos mostrar agora, utilizando o que foi visto acima, duas regras canônicas da argumentação lógica: As
regras de Modus Ponens e Modus Tollens.
Observamos que estas regras são na verdade fórmulas que valem sempre que as componentes forem
aç
substituidas por proposições com seus respectivos valores de verdade.
• A regra Modus Ponendo Ponens (do Latim "maneira que afirma afirmando") ou afirmação do antecedente.
Chamamos esta regra de modus ponens por simplicidade. Esta regra pode ser escrita da seguinte forma:
sejam P e Q duas proposições então
{P ⇒ Q, P} ` Q.
R(P, Q) = P ∧ (P ⇒ Q)
or
ab
e vamos mostrar que R implica lógicamente Q, isto é, R ` Q. Construímos a tabela
P Q P⇒Q R R⇒Q
V V V V V
el
V F F F V
F V V F V
F F V F V
Portanto a fórmula S(P, Q) = [R(P, Q) ⇒ Q] é uma tautologia, de onde segue que R(P, Q) implica lógica-
mente Q para quaisquer valores de P e Q.
Em
"Se hoje é domingo então não trabalho. Hoje é domingo. Logo, não trabalho."
Podemos também mostrar este argumento utilizando as regras de cálculo proposicional, para isto observa-
mos que
{P ⇒ Q, ¬Q} ` ¬P
25
R(P, Q) = ¬Q ∧ (P ⇒ Q)
ão
F F V V V V V
Portanto a fórmula S(P, Q) = [R(P, Q) ⇒ ¬P] é uma tautologia, de onde segue que R(P, Q) implica
lógicamente ¬P para quaisquer valores de P e Q.
Um exemplo da regra de Modus Tollens é a seguinte
aç
"Se hoje é domingo então não trabalho. Trabalho. Logo, hoje não é domingo."
Podemos também mostrar este argumento utilizando as regras de cálculo proposicional, para isto observa-
mos que
or
[(P ⇒ Q) ∧ ¬Q] ⇒ ¬P = [(¬P ∨ Q) ∧ ¬Q] ⇒ ¬P (definição ⇒)
= [(¬P ∧ ¬Q) ∨ (Q ∧ ¬Q)] ⇒ ¬P (distributividade)
= [(¬P ∧ ¬Q)] ⇒ ¬P (pois (Q ∧ ¬Q) é Falsa e dominação)
= ¬(¬P ∧ ¬Q) ∨ ¬P (definição ⇒)
ab
= (P ∨ Q) ∨ ¬P (De Morgan)
= Q ∨ (P ∨ ¬P) (asociatividade)
que é uma tautologia pois ¬P ∨ P = ¬(P ∧ ¬P) é verdadeira.
Associadas a estas regras temos duas falácias ou argumentos inválidos que são de uso cotidiano na forma de
el
raciocinar:
• Falácia da afirmação do consequênte: É muito similar a Modus Ponens. A fórmula proposicional da
mesma é
{P ⇒ Q, Q} ` P
Em
Para ver que o argumento é inválido temos que mostrar que a fórmula do argumento não é uma tautologia.
De fato, se
R(P, Q) = (P ⇒ Q) ∧ Q
temos
P Q P⇒Q R R⇒P
V V V V V
V F F F V
F V V V F
F F V F V
Um exemplo desta falácia é o seguinte argumento
"Se hoje é domingo então não trabalho. Não trabalho. Logo, hoje é domingo."
Veja que, neste caso,
e argumento não se sustenta precisamente quando P é falso e Q verdadeiro, pois pode ser segunda-feira e,
no caso, também não trabalhar.
26 Capítulo 5. Argumentação Lógica
{P ⇒ Q, ¬P} ` ¬Q
Para ver que o argumento é inválido temos que mostrar que a fórmula do argumento não é uma tautologia.
De fato, se
R(P, Q) = (P ⇒ Q) ∧ (¬P)
ão
temos
P Q P⇒Q ¬P R ¬Q R ⇒ ¬Q
V V V F F F V
V F F F F V V
aç
F V V V V F F
F F V V V V V
Um exemplo da falácia é o seguinte argumento
Obs. Estas duas falácias vistas acima são a mais comuns em argumentação de prova. Principalmente nos
el
resultados em que temos que provar que uma propriedade vale para todo elemento de um conjunto. A falácia
surge ao argumentar que como "vale para um caso particular vale para todo". Isto é uma falácia do tipo
afirmação do consequente, pois a argumentação correta é que se "vale para todo elemento do conjunto, vale
para o caso particular". Isto ficará mais claro quando sejam vistos os quatificadores.
A seguir estudamos alguns exemplos de regras de argumentos lógicos com as mesmas técnicas que estudamos
Em
acima.
Exemplo 5.1 • Considere as seguintes fórmulas proposicionais
P1 = (P ⇒ Q) P2 = (R ⇒ ¬Q) P3 = R C = (¬P)
e o argumento
{P1 , P2 , P3 } ` C.
ão
e o argumento seria:
"Se hoje é dia 15 então amanhã é dia 16. Se hoje é dia 13 amanhã não é dia 16. Hoje é dia 13. Logo, hoje
não é dia 15."
aç
Podemos também mostrar que este argumento é valido utilizando as regras de cálculo proposicional, para
isto observamos que
P1 ∧ P2 ∧ P3 ⇒ ¬P = (P ⇒ Q) ∧ (R ⇒ ¬Q) ∧ R ⇒ ¬P
= (¬P ∨ Q) ∧ (¬R ∨ Q) ∧ R ⇒ ¬P (definição ⇒)
or
= (¬P ∨ Q) ∧ [(¬R ∨ Q) ∧ R)] ⇒ ¬P (associatividade)
= (¬P ∨ Q) ∧ [(¬R ∧ R) ∨ (Q ∧ R)] ⇒ ¬P
= (¬P ∨ Q) ∧ (Q ∧ R) ⇒ ¬P (dominação)
(distributividade)
ab
= (¬P ∧ Q ∧ R) ∨ (Q ∧ Q ∧ R) ⇒ ¬P (distributividade)
= (¬P ∧ Q ∧ R) ∨ (Q ∧ R) ⇒ ¬P (idempotência)
= [¬P ∧ (Q ∧ R)] ∨ (Q ∧ R) ⇒ ¬P (associatividade)
= ¬P ⇒ ¬P (absorção)
el
= (P ∨ ¬P) (definição ⇒)
que é claramente uma tautologia.
• Considere as seguintes fórmulas proposicionais
P1 = (P ⇒ Q) P2 = (Q ⇒ R) C = (P ⇒ R)
Em
e o argumento
{P1 , P2 } ` C.
Éste argumento é conhecido como Silogismo Hipotético. A tabela de verdade associada a este argumento
é
P Q R P1 P2 P1 ∧ P2 C P1 ∧ P2 ⇒ C
V V V V V V V V
V V F V F F F V
V F V F V F V V
V F F F V F F V
F V V V V V V V
F V F V F F V V
F F V V V V V V
F F F V V V V V
"Se ontem foi dia 14 então hoje é dia 15. Se hoje é dia 15 então amanhã é dia 16. Logo, se ontem foi dia
14 então amanhã é dia 16."
ão
Podemos também mostrar que este argumento é valido utilizando as regras de cálculo proposicional, para
isto observamos que
P1 ∧ P2 ⇒ C = [(P ⇒ Q) ∧ (Q ⇒ R)] ⇒ (P ⇒ R)
aç
= [(P ⇒ Q) ∧ (¬Q ∨ R)] ⇒ (¬P ∨ R) (definição ⇒)
= [(P ⇒ Q) ∧ ¬Q] ∨ [(P ⇒ Q) ∧ R)] ⇒ (¬P ∨ R) (Distributividade)
= [¬P] ∨ [(P ⇒ Q) ∧ R)] ⇒ (¬P ∨ R) (Modus Tollens)
= [¬P] ∨ [(¬P ∨ Q) ∧ R)] ⇒ (¬P ∨ R) (definição ⇒)
or
= [¬P ∨ (¬P ∨ Q)] ∧ [¬P ∨ R] ⇒ (¬P ∨ R) (Distributividade)
= ¬[ [¬P ∨ (¬P ∨ Q)] ∧ [¬P ∨ R] ] ∨ (¬P ∨ R) (definição ⇒)
= ¬[¬P ∨ (¬P ∨ Q)] ∨ [¬(¬P ∨ R)] ∨ (¬P ∨ R) (De Morgan)
ab
Que é uma tautologia pois [¬(¬P ∨ R)] ∨ (¬P ∨ R) é sempre Verdadeira.
Nos detemos um pouco na questão de como utilizamos, em matemática, a argumentação lógica para provar
que um determinado argumento
el
{P1 , . . . , Pn } ` C,
é válido. Neste caso sabemos que o que temos que provar é que a proposição
Em
onde P1 , . . . , Pn são as premisas e C é a conclusão, é verdadeira. A proposição Q(P1 , . . . , Pn ,C) tem a seguinte
tabela da verdade
P1 ∧ · · · ∧ Pn C P1 ∧ · · · ∧ Pn ⇒ C
V V V
V F F
F V V
F F V
Portanto, para mostrar que o argumento é válido, temos que ver que NUNCA OCORRE o caso em que
P1 ∧ · · · ∧ Pn : Verdadeira e C : Falsa
ão
V F V F F
F V F V V
F F V V V
Desta forma, para mostrar que o argumento é válido devemos mostrar que se assumimos a C como sendo
aç
falsa chegamos, utilizando as ferramentas matemáticas que dispomos, o cálculo proposicional e/ou tabelas
da verdade, a que a única posibilidade para ¬(P1 ∧ · · · ∧ Pn ) seja ser uma proposição verdadeira e portanto,
o que está grifado em verde não acontece.
• Redução ao Absurdo: O método consiste em mostrar a partir de supostos que alguma das proposições
que constituem o argumento não pode ser uma proposição, o que é um absurdo ou paradoxo. Ele se baseia
or
em que a negação de uma tautologia é uma contradição. Como
¬(P1 ∧ · · · ∧ Pn ⇒ C) = ¬(¬(P1 ∧ · · · ∧ Pn ) ∨C) = P1 ∧ · · · ∧ Pn ∧ ¬C
a ideia é provar que
ab
P1 ∧ · · · ∧ Pn ∧ (¬C)
é um contradição lógica. Fazendo a tabela da verdade vemos que,
P1 ∧ · · · ∧ Pn C ¬C P1 ∧ · · · ∧ Pn ∧ ¬C
el
V V F F
V F V V
F V F F
F F V F
e portanto, deve-se mostrar que o que está grifado em verde não acontece.
Em
Assim, este caso consiste em mostrar utilizando as ferramentas matemáticas que dispomos, o cálculo
proposicional e/ou tabelas da verdade, que se assumimos que as Pi são verdadeiras e C falsa chegamos a
que uma das proposições que compõem o argumento (geralmente C, mas pode ser alguma das Pi também)
tem dois valores de verdade (Verdadeiro e Falso) simultáneamente violando o princípio de exclusão.
De onde segue que esta não pode ser uma proposição, o que é um absurdo que provém dos supostos.
Consequêntemente o grifado em verde não pode acontecer.
Dado um determinado argumento que devemos provar escolheremos a forma em que vamos mostrá-lo. A
forma que será empregada na demonstração depende do contexto. Muitas vezes uma é mais conveniente respeito
das outras por ser mais simples de ser aplicada.
De forma geral,
• Se vamos mostrar que P ` Q mostramos P ⇒ Q é verdadeira e, portanto, que nunca ocorre o caso em que
P é verdadeira e Q é falsa.
• Se vamos mostrar que P = Q então devemos mostrar que P ` Q e que Q ` P, isto é, que o bicondicional
P ⇔ Q é uma verdadeira e, portanto, nunca ocorre o caso em que as proposições tem valores lógicos
diferentes.
Exemplo 5.2 • A gente aplica algum dos três métodos no dia a dia: Suponha, por exemplo, que você
mora numa kitnet (casas maiores requerem mais pasos porém o raciocínio é similar) e você tem que sair e
precisa das chaves porque está trancado do lado de dentro. Então, para buscar a chave, o raciocínio que
você aplica é
30 Capítulo 5. Argumentação Lógica
Vamos mostrar que este raciocínio é válido das três formas vistas acima.
Primeiramente, denotamos por
ão
{P1 , P2 } ` C,
aç
Q(P1 , P2 ,C) = [P1 ∧ P2 ⇒ C]
é verdadeira.
Assumimos que P1 é sempre verdadeira pois sabemos que há uma chave.
or
ab
– Direta: Assumimos P1 ∧ P2 como verdadeira. Então, como a casa tem 2 cómodos, se a chave não
está na sala (P1 é verdadeira) tem que estár no outro cómodo. Como este cómodo é o banheiro ela
el
que também não está no banheiro. Portanto, como a casa tem dois cómodos, não pode estar na casa.
Mas a gente estava dentro da casa e teve que abrir a porta. De onde segue que a casa não tem chave.
Isto é um absurdo (pois sabemos que há uma chave) que provém de supor que a chave não está no
banheiro.
• Considere as proposições
P1 = "o número natural N é divisível por 2"
P2 = "o número natural N é divisível por 3"
C = "o número natural N é divisível por 6"
Queremos mostrar que {P1 , P2 } ` C é um argumento válido. Ou, dito de outra forma, que
"Se o número natural N é divisível por 2 e o número natural N é divisível por 3 então o número natural N
é divisível por 6"
N = 3 · k = 3 · 2 · t = 6 · t.
de onde C é verdadeira.
31
– Indireta. Assuma que C é falsa, e ¬C verdadeira, isto é , que N = 6 · k + r com 0 < r < 6.
Modo 1: Se 2|r (P1 verdadeira) então 3 6 |r pois, se dividisse teríamos que 6|r, o que não acontece.
Portanto P2 é falsa e, consequêntemente P1 ∧ P2 é falsa, de onde ¬(P1 ∧ P2 ) é verdadeira.
Modo 2: Se 3|r (P2 verdadeira) então 2 6 |r pois, se dividisse teríamos que 6|r, o que não acontece.
Portanto P1 é falsa e, consequêntemente P1 ∧ P2 é falsa, de onde ¬(P1 ∧ P2 ) é verdadeira.
– Absurdo: Assuma que P1 e P2 são verdadeiras e C é falsa, isto é que 2|N, 3|N e N = 6k + r com
0 < r < 6. Então, como 2|N temos que N = 2m pois e, como 3|n e (2, 3) = 1 temos que m = 3m0 de
onde N = 6m0 . De onde obtemos que C é verdadeira e falsa ao mesmo tempo, e portanto não pode
ser uma proposição, o que é um absurdo que provém do fato de supor que C é falsa.
ão
• Considere as proposições
P1 = "N 2 um inteiro múltiplo divisível por 3"
C = "N é um número inteiro divisível por 3"
Queremos mostrar que P1 ` C é um argumento válido. Ou, dito de outra forma, que
aç
"Se N 2 um inteiro múltiplo divisível por 3 então N é um número inteiro divisível por 3"
Vamos mostrar isto das três formas deferentes vistas acima, mas antes de começar observamos que se N é
um número inteiro então, do algoritmo da divisão,
N = 3·k+r
portanto
k ∈ Z, 0≤r<3
N 2 = 3 · (3 · k2 + 2 · k) + r2
or
ab
onde
0 se r = 0
r2 = 1 se r = 1
el
4 se r = 2
aç
or
Existem frases declarativas que não há como dizer se são verdadeiras ou falsas pois dependem do valor que
assume uma variável para que possam ser consideradas como proposição. Estas são chamadas de funções
ab
proposicionais. Para definir corretamente o conceito de função proposicional precisamos da noção de conjunto.
A noção de conjunto, elemento e pertinência, são conceito básicos da matemática e aceitos sem definição.
Algo similar ao que acontece com pontos, retas, etc., na geometria. No entanto, podemos dizer que
• Um agrupamento, classe, coleção ou sistema é, em geral, um conjunto.
• Cada membro ou objeto que entra na formação do conjunto é chamado de elemento do conjunto.
el
pertenência.
Vamos denotar por letras maiúsculas A, B, C . . . aos conjuntos e por minúsculas a, b, c . . . aos elementos
dos conjuntos.
Obs. Se definirmos os elementos de um conjunto a partir de uma propriedade de seus elementos de forma
descuidada, podemos ter problemas. Por exemplo, considere
O = {X conjunto, X 6∈ X}
Observamos que dizer que X conjunto tal que X 6∈ X ou X ∈ X não é absurdo. De fato
• Seja A o conjunto de todos os carros, como A não é um carro temos que A 6∈ A.
• Seja A o conjunto das ideias abstratas é um conjunto que, por ser uma ideia abstrata, é um conjunto
satisfaz A ∈ A.
No entanto, O não é um conjunto. De fato, se assumimos que é conjunto, observamos que:
• Se O ∈ O então, da definição, O 6∈ O.
• Por outro lado O 6∈ O então O ∈ O. O que é uma contradição.
O problema parte de admitir que O é conjunto. Este problema é conhecido como Paradoxo de Russel. Em
particular, decorre disto que a coleção de todos os conjuntos não é um conjunto.
Para representar gráficamente conjuntos,utilizamos os diagramas de Venn (em honor a John Venn, matemático
inglés). Para isso começamos desenhando um quadrado que é o conjunto universal U e dentro dele utilizamos
34 Capítulo 6. Quantificadores
uma linha fechada que não possui auto-intersecção para representar o conjunto A. Dentro dela, utilizando pontos,
representamos os elementos do conjunto A.
Exemplo 6.1 Se A = {a, b, c} então
ão
aç
Outra forma de representar os conjuntos é por listando todos seus elementos entre chaves. Por exemplo,
A = {a, b, c, d, . . .}.
Denotamos a função proposicional por (A, P(x)) ou simplesmente P(x) quando damos por subentendido o
conjunto A.
el
Se temos uma função proposicional (A, P(x)) podemos nos perguntar para quantos elementos de A a
proposição é verdadeira?. As respostas podem ser: todos, alguns, um e nenhum. Passamos agora a ver estes
quantificadores.
Formalmente, se P é um proposição, existem dois quantificadores
• Quantificador universal (ou para todo): que é simbolizado por
∀x, P
∃ x, P = ¬[∀ x, ¬P]
e se lê, "existe x tal que P" ou "não é verdade que para todo x temos que P é falsa".
A proposição assim construída será verdadeira se existe um valor que pode assumir x tal que P é verdadeira.
Com estes quantificadores construimos os chamados de quantificadores delimitados como segue: Seja
(A, P(x)) uma função proposicional
35
ão
Neste caso a proposição é verdadeira se P(x) é verdadeira para, pelo menos, um x ∈ A.
• Quantificador Existencial de unicidade delimitado: "Existe um único x em A tal que P(x) é verdadeira."
A notação para esta expressão é
∃! x ∈ A, P(x) ≡ ∃ x ∈ A, ∀ y ∈ A, [(P(x) ∧ P(y)) ⇔ (x = y)].
aç
Neste caso a proposição é verdadeira se P(x) é verdadeira para um único x ∈ A.
Exemplo 6.3
¬P = ∀x, x ∈ N ⇒ (x ≤ 5).
• A proposição:
P = ∀ x, x ∈ N ⇒ ( 2|x ⇒ x é par.)
¬P = ∃ x, x ∈ N ∧ ¬( 2|x ⇒ x é par.)
ão
Para negar as proposições construidas com quantificadores temos a seguinte regra de De Morgan que segue
da definição: Dada P uma proposição temos
aç
Da regra acima, decorre a seguinte regra:
e que
= ∃ x, (x ∈ A) ∧ (¬P(x))
= ∃ x ∈ A, ¬P(x).
Escrevemos
∃x ∈ R, x2 + 1 = 16
e sua negação
¬[∃x ∈ R, x2 + 1 = 16] = ∀x ∈ R, ¬(x2 + 1 = 16)
= ∀x ∈ R, x2 + 1 6= 16.
• b)
37
ão
= ∃ x ∈ R, (x2 + 1 = 16) ∧ (x + 1 < 6).
A demonstração das proposições com quantificadores pode ser feita de forma direta ou provando que sua
negação é falsa.
aç
Exemplo 6.5 • ∀ x ∈ (1, +∞), x < x2 .
Seja x > 1 então
x2 = x · x > x · 1 = x
• ∃x ∈ N tal que 2x > 201.
Seja x = 101 então 2(101) = 202 > 201.
or
No caso de querermos demonstrar a falsidade das proposições
ab
• com quantificador universal: se utiliza o método de contraexemplo. Ou seja, para mostrar que
∀x ∈ A, P(x)
é falsa se procura um elemento a ∈ A tal que ¬P(a) é verdadeira. Tal elemento, se existir, recebe o nome
de contraexemplo.
el
• com quantificador existêncial: se prova diretamente a não existência do elemento ou se prova que a
negação dela é verdadeira.
Exemplo 6.6 • ∀ x ∈ (0, +∞), x < x2 .
Seja x = 1/2 então
Em
1 1
x2 = < =x
4 2
portanto a proposição é falsa.
• ∃x ∈ (0, 100) tal que 2x > 201.
– Direto: Se 0 < x < 100 então 0 < 2x < 200 portanto 2x < 200 < 201. de onde a proposição é falsa.
– Negação: provamos que
¬[∃x ∈ (0, 100), 2x > 201] = ∀x ∈ (0, 100), ¬[2x > 201]
= ∀x ∈ (0, 100), 2x ≤ 201.
De fato, se 0 < x < 100 então 0 < 2x < 200 ≤ 201. Portanto a negação da proposição é verdadeira e,
consequêntemente, a proposição é falsa.
Com isto podemos construir a seguinte tabela que relaciona como mostrar que a veracidade ou falsidade das
proposições com um quatificador.
Proposição Quando é Verdadeira Quando é Falsa
∀ a ∈ A, P(a) Para todo a ∈ A Existe a ∈ A para
P(a) é verdadeira o qual P(a) é falsa.
∃ a ∈ A, P(a) Existe a ∈ A para o Para todo a ∈ A
qual P(a) é verdadeira P(a) é falsa.
38 Capítulo 6. Quantificadores
Observamos que nada temos falado das proposições com o quantificador ∃!. Isto porque ele é construido a
partir da conjunção de duas proposições com quantificadores.
Passamos a estudar proposições com dois quantificadores. De modo geral, estas proposições podem-se
resumir a quatro casos. Dada P(a, b) uma função proposicional em um universo U e A, B conjuntos em U,
temos as seguintes proposições
• ∀ a ∈ A, ∀ b ∈ B, P(a, b).
• ∀ a ∈ A, ∃ b ∈ B, P(a, b).
• ∃ a ∈ A, ∀ b ∈ B, P(a, b).
• ∃ a ∈ A, ∃ b ∈ B, P(a, b).
ão
Obs. É fácil ver que
∀ a ∈ A, ∀ b ∈ B, P(x, y) = ∀ b ∈ B, ∀ a ∈ A, P(a, b).
De fato se para todo a ∈ A temos ∀ b ∈ B, P(a, b) então P(a, b) é verdadeira para todo a ∈ A e b ∈ B. De
aç
onde segue que para todo b ∈ B temos que ∀ a ∈ A, P(a, b) é veraddeira. De forma similar, temos que
∃ a ∈ A, ∃ b ∈ B, P(a, b) = ∃ b ∈ B, ∃ a ∈ A, P(a, b).
Pois se existe a ∈ A tal que ∃ b ∈ B, P(a, b) é verdadeira, então existem a ∈ A e b ∈ B tal que P(a, b) é
verdadeira. De onde segue que é equivalente a dizer que existe b ∈ B tal que ∃ A ∈ A, P(a, b) é verdadeira.
or
No entanto, observamos que, de forma geral, temos
∀ a ∈ A, ∃ b ∈ B, P(a, b) 6= ∃ b ∈ B, ∀ a ∈ A, P(a, b).
Sabemos que
ab
{∃ b ∈ B, ∀ a ∈ A, P(a, b)} ` ∀ a ∈ A, ∃ b ∈ B, P(a, b).
De fato, se existe b tal que para todo a ∈ A temos que P(a, b) é verdadeira então para todo a ∈ A existe
b ∈ B tal que P(a, b) é verdadeira.
Para ver que o argumento
el
Como no caso de um quantificador, indicamos como negar proposições com mais de um quantificador.
Assim, utilizamos o visto acima junto as Leis de De Morgan para obter
•
¬[∀ x ∈ A, ∀ y ∈ B, P(x, y)] = ∃ x ∈ A, ¬[∀ y ∈ B, P(x, y)]
= ∃ x ∈ A, ∃ y ∈ B, ¬P(x, y)
•
¬[∀ x ∈ A, ∃ y ∈ B, P(x, y)] = ∃ x ∈ A, ¬[∃ y ∈ B, P(x, y)]
= ∃ x ∈ A, ∀ y ∈ B, ¬P(x, y)
ão
•
¬[∃ x ∈ A, ∀ y ∈ B, P(x, y)] = ∀ x ∈ A, ¬[∀ y ∈ B, P(x, y)]
= ∀ x ∈ A, ∃ y ∈ B, ¬P(x, y)
•
¬[∃ x ∈ A, ∃ y ∈ B, P(x, y)] = ∀ x ∈ A, ¬[∃ y ∈ B, P(x, y)]
aç
= ∀ x ∈ A, ∀ y ∈ B, ¬P(x, y)
Com isto podemos construir a seguinte tabela que relaciona como mostrar que a veracidade ou falsidade das
proposições com dois quatificadores.
Proposição Quando é Verdadeira Quando é Falsa
∀ a ∈ A, ∀ b ∈ B, P(a, b)
∀ a ∈ A, ∃ b ∈ B, P(a, b)
or
Para todo a ∈ A e b ∈ B
tal que P(a, b) é verdadeira
Para todo a ∈ A existe um b ∈ B
tal que P(a, b)é verdadeira
Existe um a ∈ A e um b ∈ B
tal que P(a, b) é falsa.
Existe um a ∈ A tal que para todo
b ∈ B temos P(a, b) é falsa .
ab
∃ a ∈ A, ∀ b ∈ B, P(a, b) Existe um a ∈ A, para todo b ∈ B, Para todo a ∈ A existe b ∈ B
tal que P(a, b) é verdadeira tal que P(a, b) é falsa.
∃ a ∈ A, ∃ b ∈ B, P(a, b) Existe um a ∈ A e existe um b ∈ B Para todo a ∈ A e para todo b ∈ B
tal que P(a, b) é verdadeira temos P(a, b) é falsa.
el
e as funções proposicionais
A negação é
¬[∀ x ∈ A, ∀ y ∈ A, (M(x) ∧ N(y)) ⇒ P(x, y)]
= ∃ x ∈ A, ¬[ ∀ y ∈ A, (M(x) ∧ N(y)) ⇒ P(x, y)]
= ∃ x ∈ A, ∃ y ∈ A, ¬[(M(x) ∧ N(y)) ⇒ P(x, y)]
= ∃ x ∈ A, ∃ y ∈ A, [(M(x) ∧ N(y)) ∧ ¬P(x, y)],
¬P ="Há uma necessidade de muitos que se não se sobrepõe a uma necessidade de poucos."
40 Capítulo 6. Quantificadores
Observamos que há uma forma melhor de descrever esta proposição definindo o que significa ser maioria
e minoria, em função da cardinalidade do conjunto de pessoas.
• Considere a proposição
"Existe um barbeiro que barbeia a todos aqueles, e somente aqueles que não se barbeiam."
Se consideramos o conjunto dos homens como sendo A e as funções proposicionais
P(x) = ”x é barbeiro”, B(x, y) = ”x barbeia y”
Destacamos que
ão
– "existe um barbeiro": ∃ x ∈ A, P(x)
– "que barbeia a todos aqueles, e somente aqueles, que não se barbeiam": pode ser traduzida como
∀ y ∈ A, ¬B(y, y) ⇔ B(x, y).
A frase então, pode ser escrita
aç
Q = ∃ x ∈ A, {P(x) ∧ [∀ y ∈ A, ¬B(y, y) ⇔ B(x, y)]}”
Veremos abaixo que isto pode ser escrito como
Q = ∃ x ∈ A, ∀ y ∈ A, [P(x) ∧ (¬B(y, y) ⇔ B(x, y)))]”
A negação de P é or
¬Q = ∀ x ∈ A, ∃ y ∈ A, {¬P(x) ∨ ¬[¬B(y, y) ⇔ B(x, y)]}”
que é igual a
ab
¬Q = ∀ x ∈ A, ∃ y ∈ A, {¬P(x) ∨ [B(y, y) ⇔ B(x, y)]}”.
• Consideramos o universo como sendo os números reais
"Para todo ε > 0 existe um δ > 0 para todo x ∈ R tal que se |x − 2| < δ então |2 · x − 4| < ε."
el
Escrevemos
∀ ε > 0, ∃ δ > 0, ∀ x ∈ R |x − 2| < δ ⇒ |2 · x − 4| < ε
Observamos que
Em
• Para mostrar a falsidade de uma proposição com mais de um quantificador se procede de forma similar ao
caso de um, isto é, se mostra um contraexemplo ou se prova que a negação dela é verdadeira.
Vamos mostrar que a proposição
∀ε > 0, ∃ δ > 0, ∀ x ∈ R, 0 < |x| < δ ⇒ | sin(1/x) − 1| < ε
é falsa. Novamente observamos que
ε > 0 = ε ∈ (0, ∞), e que δ > 0 = δ ∈ (0, ∞).
Para mostrar a falsidade de P provamos que a negação dela é verdadeira, isto é
ão
¬[∀ε > 0, ∃δ > 0, ∀ x ∈ R, 0 < |x| < δ ⇒ | sin(1/x) − 1| < ε]
= ∃ ε > 0 ¬[∃δ > 0, ∀ x ∈ R, 0 < |x| < δ ⇒ | sin(1/x) − 1| < ε]
= ∃ ε > 0, ∀ δ > 0, ¬[ ∀ x ∈ R, 0 < |x| < δ ⇒ | sin(1/x) − 1| < ε]
= ∃ ε > 0 ∀ δ > 0, ∃x ∈ R, ¬[0 < |x| < δ ⇒ | sin(1/x) − 1| < ε]
aç
= ∃ ε > 0 ∀ δ > 0, ∃x ∈ R, (0 < |x| < δ ) ∧ | sin(1/x) − 1| ≥ ε
Provamos então que
¬P = ∃ ε > 0 ∀ δ > 0, ∃x ∈ R, (0 < |x| < δ ) ∧ | sin(1/x) − 1| ≥ ε
De fato, considere ε = 1
2
1
| sin(1/x0 ) − 1| = 1 > .
2
or
e δ > 0 qualquer. Seja k ∈ N tal que δ > 1
k e, portanto, 0 < |x0 | =
1 1
1
kπ <δ e
ab
Portanto, temos mostrado que existe ε = 1/2 tal que para todo δ existe x0 = kπ ∈ R com kπ < δ tal que
0 < |x0 | < δ e
1
| sin(1/x0 ) − 1| = 1 > .
2
Portanto ¬P é verdadeira e P é falsa.
el
A seguir vamos estudar em detalhe como se comportam os quantificadores com respeito a conjunção e
disjunção de proposições. Isto pode ser omitido em uma primeira leitura.
Proposição 6.1 Sejam (U, P(x)) e (U, Q(x)) duas funções proposicionais. Então
Em
Demonstração. Mostramos cada uma delas por separado. Para a primeira observamos que se P(a) ∧ Q(a) é
verdadeira para todo a ∈ A se, e somente se temos que P(a) é verdadeira e Q(a) é verdadeira (da tabela de
verdade da conjunção) e isto ocorre se, e somente se, P(a) é verdadeira para todo a ∈ A e Q(a) é verdadeira para
todo a ∈ A. Isto prova a primeira identidade.
Para provar a segunda, utilizamos a que acabamos de provar junto com a dupla negação.
42 Capítulo 6. Quantificadores
Corolário 6.1 Seja P uma proposição e (U, Q(x)) uma função proposicional. Então
• ∀ x ∈ A, (P ∧ Q(x)) = P ∧ (∀x ∈ A, Q(x)),
• ∃x ∈ A, (P ∨ Q(x)) = P ∨ (∃ x ∈ A, Q(x)).
ão
Obs. A proposição ∃! a ∈ A, P(a) pode ser escrita
∃! a ∈ A, P(a) = ∃ a ∈ A, [P(a) ∧ ( ∀ b ∈ A, (P(b) ⇔ (b = a) )]
= ∃ a ∈ A, ∀ b ∈ B, [P(a) ∧ (P(b) ⇔ (b = a) )]
e sua negação é
aç
¬[∃! a ∈ A, P(a)] = ¬{∃ a ∈ A, ∀ b ∈ B, [P(a) ∧ (P(b) ⇔ (b = a) )]}
= ∀ a ∈ A, ∃ b ∈ A, ¬[P(a) ∧ (P(b) ⇔ (b = a) )]
= ∀ a ∈ A, ∃ b ∈ A, (¬P(a)) ∨ ¬[(P(b) ⇔ (b = a) )]
= ∀ a ∈ A, ∃ b ∈ A, (¬P(a)) ∨ ¬[ [(¬P(b)) ∨ (b = a)] ∧ [¬(b = a) ∨ P(b)] ]
=
=
or
∀ a ∈ A, ∃ b ∈ A, (¬P(a)) ∨ [P(b) ∧ (b 6= a)] ∨ [(b = a) ∧ ¬P(b)]
∀ a ∈ A, ∃ b ∈ A, ¬P(a) ∨ [P(b) ∧ (b 6= a)]
onde, na última linha, temos utilizado que
[(b = a) ∧ ¬P(b)] = ¬P(a).
ab
Proposição 6.2 Sejam (U, P(x)) e (U, Q(x)) duas funções proposicionais. Então
• [(∀ x ∈ A, P(x)) ∨ (∀ x ∈ A, Q(x))] ⇒ ∀ x ∈ A, (P(x) ∨ Q(x))
• ∃ x ∈ A, (P(x) ∧ Q(x)) ⇒ [(∃ x ∈ A, P(x)) ∧ (∃ x ∈ A, Q(x))]
As recíprocas, em geral, são falsas.
el
Corolário 6.2 Seja P uma proposição e (U, Q(x)) uma função proposicional. Então
• ∀ x ∈ A, (P ∨ Q(x)) = P ∨ (∀x ∈ A, Q(x)),
• ∃x ∈ A, (P ∧ Q(x)) = P ∧ (∃ x ∈ A, Q(x)).
Demonstração. Para o primeiro item observamos que somente devemos mostrar que
Mas isto é imediato pois se ∀ x ∈ A, (P ∨ Q(x))] é verdadeira então pode acontecer que P é verdadeira, em
ão
cujo caso P ∨ (∀x ∈ A, Q(x)) ou P é falsa, em cujo caso Q(x) é verdadeira, e portanto, P ∨ (∀x ∈ A, Q(x)) é
verdadeira.
Para o segundo item, utilizamos qua regra que acabamos de provar vale junto com a dupla negação. Vemos
então que
∃x ∈ A, (P ∧ Q(x)) = ¬[¬(∃x ∈ A, (P ∧ Q(x)))]
aç
= ¬[∀x ∈ A, ¬(P ∧ Q(x))]
= ¬[∀x ∈ A, (¬P) ∨ (¬Q(x))]
= ¬[ (¬P) ∨ (∀x ∈ A, ¬Q(x))]
= P ∧ (∃ x ∈ A, Q(x)). or
Corolário 6.3 Sejam (U, P(x)) e (U, Q(x)) funções proposicionais. Então
ab
• [(∀ x ∈ A, P(x)) ∨ (∀ x ∈ A, Q(x))] = ∀ x ∈ A, ∀y ∈ A (P(x) ∨ Q(y))
• ∃ x ∈ A, ∃ y ∈ A (P(x) ∧ Q(y)) = [(∃ x ∈ A, P(x)) ∧ (∃ x ∈ A, Q(x))]
aç
or
Vimos, na seção anterior, uma breve introdução à teoria de conjuntos. Em particular, observamos que a teoria
chega rápidamente em paradoxos se for feita de forma descuidada. Para evitar esta problemática, no século
ab
XX foram propostos varios sistemas axiomáticos com o intuito de promover uma teoria dos conjuntos sem os
paradoxos da teoria ingênua dos conjuntos (como o paradoxo de Russell). Um destes sistemas, são os axiomas
de Zermelo-Fraenkel (em homenagem aos matemáticos Ernst Zermelo e Abraham Fraenkel).
Sabemos, no entanto, por um resultado de K. Gödel (ver, para um leitura compreensível, o trabalho Godel’s
Proof de E. Nagel e J. Newman) que estes axiomas não podem ser provados dentro da teoria e, mais ainda,
el
se queremos uma teoria livre de paradoxos (isto é, consistente) então teremos uma teoria incompleta (isto é,
incapaz de provar todas suas afirmações), pois teremos que postular um número infinito de axiomas para evitar
paradoxos visto que a aparição deles é inevitável. O postulado de axiomas se traduz, na prática, em um humilde
reconhecimento da nossa limitação na capacidade de determinar se as afirmações dos paradoxos são verdadeiras
ou falsas.
Em
Nessa linha, enunciamos os axiomas de Zermelo-Fraenkel que formam a base da teoria de conjuntos, embora
não nos deteremos muito sobre eles. O objetivo de fazer isto é que o estudante tome ciência da existência de
uma teoria mais profunda sobre conjuntos e que deve ser levada em consideração ao se fazer um estudo sério e
cuidadoso.
Nos axiomas de Zermelo-Fraenkel todo elemento é visto como sendo também um conjunto. Os axiomas são:
• Axioma da existência: Existe o conjunto vazio, que é conjunto que não possui elementos.
• Axioma da extensão: Dois conjuntos são iguais se eles têm os mesmos elementos.
• Axioma da regularidade: Todo conjunto não-vazio A contém algúm elemento x tal que A e x são
disjuntos, isto é {A} e {x} são disjuntos.
• Axioma de especificação: Se U é um conjunto e P(x) é uma função proposicional com domínio em A,
então existe um subconjunto A de U que contém os elementos a de U para o qual P(a) é verdadeira.
• Axioma do par: Se A e B são conjuntos (não necessariamente distintos) então existe um conjunto no qual
A e B são elementos.
• Axioma da união: Para todo conjunto A existe um conjunto U tal que todo elemento que pertence a um
elemento de A é um elemento de U.
• Axioma da substituição: Seja P(a, b) uma propriedade do tipo: para todo a existe um b para o qual
P(a, b) é verdadeira, então: Para todo conjunto A existe um conjunto B tal que para todo a ∈ A existe
b ∈ B para o qual P(a, b) é verdadeira.
• Axioma do infinito: Existe um conjunto U que tem o conjunto vazio como elemento, e que, para todo
46 Capítulo 7. Conjuntos
ão
Demonstração. Se A ∈ A então {A} não contém um elemento disjunto de {A} pois o único elemento é o
próprio A, contradizendo o axioma da regularidade.
• No axioma de especificação, a restrição a U é necessária para evitar o paradoxo de Russell e suas variantes.
Em outras palavras, a função proposicional precisa, primeiramente, do contexto no qual vai ser formulada.
aç
• Do axioma do par decorre que se temos dois elementos então existe um conjunto que os contém.
• O axioma da substituição garante a existência do conjunto imagem para uma função (veremos isto depois).
• O axioma do infinito garante a existência de um conjunto infinito. Como sabemos que existe um conjunto
então temos a existência dos sucessores.
or
• O axioma da potência garante a existência do conjunto de partes.
A = {1, 2, 3, 4, 5, · · · }
B = {2, 4, 6, 8, 10, · · · }
el
• Por compreensão (ou axioma de especificação): Definindo uma propriedade de seus elementos. Como
o conjunto de verdade Dom(P) de uma função proposicional P(x) que tem como domínio um conjunto
universal. Assim se (U, P(x)) temos que o conjunto Dom(P) é
Por exemplo
0/ = {x ∈ U, x 6= x}
como não existe nenhum objeto diferente de si mesmo, o conjunto não tem elementos.
A ⊂ B ⇔ (∀x ∈ A, x ∈ B)
Gráficamente:
47
ão
próprio de B, se
[(A ⊂ B) ∧ (A 6= B)],
aç
Exemplo 7.1 Sejam
A = {x ∈ R, |x + 3| < 5}
B = {x ∈ R, x ≥ −8}
vamos mostrar que A ⊂ B. Temos que mostrar que
∀x ∈ A ⇒ x ∈ B
or
ab
é verdadeira. Se x ∈ A temos que
|x + 3| < 5 ⇔ −5 < x + 3 < 5
⇔ −8 < x < 2 ⇒ x ≥ −8
e, portanto, x ∈ B. Como o x escolhido pode ser qualquer elemento de A temos que vale para todo x ∈ A. O que
el
prova o resultado.
P(x) = ”x ∈ 0/ ⇒ x ∈ A”.
P(a) = (a ∈ 0/ ⇒ a ∈ A)
ão
⇔ B = A.
• Transitiva: [(A = B) ∧ (B = C)] ⇒ (A = C).
Definição 7.3 Seja A um conjunto. O conjunto de partes de A, que denotamos por P(A), é aquele cujos
aç
elementos são os subconjuntos de A, isto é,
Obs.
/ observamos que B = A ∪ P(A) é um conjunto não vazio com a seguinte propriedade: todo
• Se A 6= 0,
subconjunto A0 ⊂ A é um elemento e subconjunto de B.
ab
De fato como A0 é subconjunto de A temos que A0 ∈ P(A) de onde A0 ∈ B. Por outro lado, como A0 é
subconjunto de A temos que A0 ⊂ A de onde A0 ⊂ B.
Obs. Dado A ⊂ U, o conjunto universal Ũ onde o conjunto de partes está não é o conjunto universal U onde A
está. De fato, o conjunto Ũ não é conhecido e deve ser assumido pelo axioma da potência.
A ⊂ B ⇔ P(A) ⊂ P(B).
Vamos agora a estudar as operações básicas da teoria de conjuntos. Para não entrar com axiomas que
permitam fazer as operações, vamos admitir que conhecemos o conjunto universal que contém como subconjuntos
a todos os subconjuntos dos quais trataremos.
49
Definição 7.4 Sejam A e B dois conjuntos em um universo U.
ão
• A união de A e B é o conjunto
A ∪ B = {x ∈ U, x ∈ A ∨ x ∈ B}
aç
Gráficamente:
or
ab
• A interseção de A e B é o conjunto
A ∩ B = {x ∈ U, x ∈ A ∧ x ∈ B}
Gráficamente:
Em
A\B = {x ∈ A, x 6∈ B}
Gráficamente:
50 Capítulo 7. Conjuntos
• O complemento de B em U é o conjunto
BC = U\B.
Gráficamente:
ão
• A diferença simétrica entre A e B é o conjunto
aç
A∆B = (A\B) ∪ (B\A)
Gráficamente:
or
ab
Teorema 7.5 A união e interseção de conjuntos satisfazem as seguintes propriedades
• Idempotente: A ∪ A = A e A ∩ A = A para todo conjunto A.
el
A ∪ (B ∪C) = (A ∪ B) ∪C,
Em
A ∩ (B ∩C) = (A ∩ B) ∩C.
• Distributividade: Para quaisquer conjuntos A, B e C valem as seguintes identidades
A ∩ (B ∪C) = (A ∩ B) ∪ (A ∩C),
A ∪ (B ∩C) = (A ∪ B) ∩ (A ∪C).
ão
⇔ x ∈ (A ∪ B) ∪C.
• Distributividade: Novamente provamos uma pois a outra é análoga.
x ∈ A ∩ (B ∪C) ⇔ (x ∈ A) ∧ (x ∈ B ∪C)
aç
⇔ (x ∈ A) ∧ [(x ∈ B) ∨ (x ∈ C)]
⇔ [(x ∈ A) ∧ (x ∈ B)] ∨ [(x ∈ A) ∧ (x ∈ C)]
⇔ (x ∈ A ∩ B) ∨ (x ∈ A ∩C)
⇔ x ∈ (A ∩ B) ∪ (A ∩C)
or
Teorema 7.6 Sejam A e B dois conjuntos no universo U. Então
• U C = 0/ e 0/ C = U.
ab
• A ∪ AC = U, A ∩ AC = 0.
/
C
• AC ) = A.
• A ⊂ B ⇒ BC ⊂ AC .
• (A ∪ B)C = AC ∩ BC
• (A ∩ B)C = AC ∪ BC .
el
• A∆B = B∆A .
Demonstração. • U C = 0:
/ Claramente 0/ ⊂ U C . Assuma que U C 6= 0. / Seja x ∈ U C então x 6∈ U o que é uma
C
contradição. Portanto U = 0. /
Em
C C
0/ = U: Claramente 0/ ⊂ U. Por outro lado, se x ∈ U então x ∈ / 0/ de onde x ∈ 0/ C , de onde segue que
C
U ⊂ 0/ . Logo U = 0/ .C
• (A ∪ B)C = AC ∩ BC :
x ∈ (A ∪ B)C ⇔ ¬(x ∈ A ∪ B)
⇔ ¬[(x ∈ A) ∨ (x ∈ B)]
⇔ ¬(x ∈ A) ∧ ¬(x ∈ B)] (Lei de De Morgan)
⇔ (x ∈ AC ) ∧ (x ∈ BC )
⇔ x ∈ AC ∩ BC
52 Capítulo 7. Conjuntos
• (A ∩ B)C = AC ∪ BC :
x ∈ (A ∩ B)C ⇔ ¬(x ∈ A ∩ B)
⇔ ¬[(x ∈ A) ∧ (x ∈ B)]
⇔ ¬(x ∈ A) ∨ ¬(x ∈ B)] (Lei de De Morgan)
⇔ (x ∈ AC ) ∨ (x ∈ BC )
⇔ x ∈ AC ∪ BC
• A comutatividade segue da comutatividade da união: de fato
A∆B = (A\B) ∪ (B\A)
ão
= (B\A) ∪ (A\B)
= B∆A.
aç
Obs. Sejam (P(x),U) e (Q(x),U) duas funções proposicionais e considere os domínios de verdade
Dom(P) = {x ∈ U, P(x) é verdadeira} e Dom(Q) = {x ∈ U, Q(x) é verdadeira}
Então
• Dom(P ∨ Q) = Dom(P) ∪ Dom(Q),
• Dom(P ∧ Q) = Dom(P) ∩ Dom(Q),
• Dom(¬P) = Dom(P)C ,
or
• Dom(P ∧ ¬Q) = Dom(P) ∩ Dom(Q)C = Dom(P)\Dom(Q),
• Dom(P ⇒ Q) = Dom(¬P ∨ Q) = Dom(P)C ∪ Dom(Q),
ab
•
Dom(P ⇔ Q) = Dom([P ⇒ Q] ∧ [Q ⇒ P])
= [Dom(P)C ∪ Dom(Q)] ∩ [Dom(P) ∪ Dom(Q)C ]
= [Dom(P)C ∩ (Ker(P) ∪ Dom(Q)C )] ∪ [Dom(Q) ∩ (Dom(P) ∪ Dom(Q)C )]
= [Dom(P)C ∩ Dom(Q)C ] ∪ [Dom(Q) ∩ Dom(P)]
el
aç
or
Sejam A e B dois conjuntos e considere a ∈ A e b ∈ B definimos o par ordenado (a, b) como sendo o conjunto
formado por
ab
(a, b) = {{a}, {a, b}} .
Neste par ordenado o elementos a e b recebem o nome de primeira e segunda coordenadas, respectivamente.
el
Obs.
• O par ordenado (a, b) pode ser visto como um subconjunto de P(A ∪ B) e é, portanto, um elemento
do conjunto P(P(A ∪ B)).
• A relação de ordem fica clara pois
{a} ⊂ {a, b}.
Em
Teorema 8.1
ou
ão
Exemplo 8.1 • Seja A = {a, b, c} e B = {1, 2} então
A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c) (c, a), (c, b), (c, c)}.
A × B = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.
aç
B × A = {(1, a), (2, a), (1, b), (2, b), (1, c), (2, c)}.
• Seja A = R e B = N então
ão
Demonstração. • Mostramos a proposição equivalente: A × B 6= 0/ ⇔ A 6= 0/ ∧ B 6= 0./
Primeiramente observamos que se A 6= 0/ e B 6= 0/ então A ∪ B 6= 0/ e existem a ∈ A e b ∈ B. Do axioma do
par e da união {a} e {a, b} são subconjuntos de A ∪ B de onde
aç
(a, b) = {{a}, {a, b}} ∈ P(P(A ∪ B)).
Portanto A × B 6= 0.
/ Agora,
A × B 6= 0/ ⇔ ∃ (a, b) ∈ A × B
⇔ ∃ a ∈ A∧∃ b ∈ B
⇔ A 6= 0/ ∧ B 6= 0.
• A × (B ∪C) = (A × B) ∪ (B ×C):
/
or
ab
(a, b) ∈ A × (B ∪C) ⇔ (a ∈ A) ∧ (b ∈ B ∪C)
⇔ (a ∈ A) ∧ [(b ∈ B) ∨ (b ∈ C)]
⇔ [(a ∈ A) ∧ (b ∈ B)] ∨ [(a ∈ A) ∧ (b ∈ C)]
⇔ [(a, b) ∈ A × B] ∨ [(a, b) ∈ A ×C]
el
⇔ (a, b) ∈ (A × B) ∪ (A ×C).
• A × (B ∩C) = (A × B) ∩ (B ×C):
(a, b) ∈ A × (B ∩C) ⇔ (a ∈ A) ∧ (b ∈ B ∩C)
⇔ (a ∈ A) ∧ [(b ∈ B) ∧ (b ∈ C)]
⇔ (a ∈ A) ∧ (a ∈ A) ∧ [(b ∈ B) ∧ (b ∈ C)]
Em
Corolário 8.2 Sejam (U, P(x)) e (U, Q(x)) funções proposicionais. Então
• ∀ x ∈ A, ∀ y ∈ B, P(x, y) = ∀(x, y) ∈ A × B, P(x, y).
• ∃ x ∈ A, ∃ y ∈ B, P(x, y) = ∃ (x, y) ∈ A × B, P(x, y).
56 Capítulo 8. Produto Cartesiano
Demonstração. Se, para todo (a, b) ∈ A × B temos que P(a, b) é verdadeira então seja a ∈ A e b ∈ B temos que
(a, b) ∈ A × B e, portanto, P(a, b) é verdadeira. De onde para todo a ∈ A e para todo b ∈ B temos que P(a, b) é
verdadeira.
Por outro lado, para todo a ∈ A e para todo b ∈ B temos que P(a, b) é verdadeira então dado (a, b) ∈ A × B
temos que, como a ∈ A e b ∈ B, P(a, b) é verdadeira, de onde para todo (a, b) ∈ A × B temos que P(a, b) é
verdadeira.
Para provar a segunda identidade utilizamos que a primeira junto com a negação de quantificadores.
∃ x ∈ A, ∃ y ∈ B, P(x, y) = ¬[¬(∃ x ∈ A, ∃ y ∈ B, P(x, y))]
ão
= ¬[ ∀ x ∈ A, ¬( ∃ y ∈ B, P(x, y))]
= ¬[ ∀ x ∈ A, ∀ y ∈ B, ¬(P(x, y))]
= ¬[ ∀ (x, y) ∈ A × B, ¬(P(x, y))]
= ∃ (x, y) ∈ A × B, ¬[¬(P(x, y))]
aç
= ∃ (x, y) ∈ A × B, P(x, y).
or
ab
el
Em
ão
9. Familia de conjuntos
aç
or
Considere uma familia de conjuntos em um universo U dada por
ab
F = {Ai , i ∈ I} ⊂ P(U),
F = {A1 , . . . , An0 }.
Em
∪i∈I Ai = {x ∈ U, ∃ i ∈ I, x ∈ Ai }
∩i∈I Ai = {x ∈ U, x ∈ Ai ∀ i ∈ I}
Teorema 9.1 Seja F = {Ai , i ∈ I} uma familia de conjuntos de um universo U. Uma familia de conjuntos.
Então
• Ak ⊂ ∪i∈I Ai , ∀k ∈ I
• ∩i∈I Ai ⊂ Ak , ∀k ∈ I
• (∪i∈I Ai )C = ∩i∈I ACi
• (∩i∈I Ai )C = ∪i∈I ACi
• Observamos que
x ∈ (∪i∈I Ai )C ⇔ ¬ (x ∈ ∪i∈I Ai , )
⇔ ¬ (∃i ∈ I, x ∈ Ai , )
⇔ ∀i ∈ I, ¬ (x ∈ Ai )
⇔ ∀i ∈ I, x ∈ ACi
⇔ ∀i ∈ ∩i∈I ACi .
Logo
ão
• Observamos que
x ∈ (∩i∈I Ai )C ⇔ ¬ (x ∈ ∩i∈I Ai , )
⇔ ¬ (∀i ∈ I, x ∈ Ai , )
aç
⇔ ∃i ∈ I, ¬ (x ∈ Ai )
⇔ ∃i ∈ I, x ∈ ACi
⇔ ∀i ∈ ∪i∈I ACi .
Logo
Definição 9.2 Seja X um conjunto e F = {Ai , i ∈ I} uma familia de subconjuntos de X. Dizemos que F é
ab
uma partição de X se
• Ai 6= 0/ para todo i ∈ I
• Ai ∩ A j = 0/ para todo i, j tais que i 6= j.
• X = ∪i∈I Ai .
el
Se temos uma familia de conjuntos não vazios F = {Ai , i ∈ I} tais que Ai ∩ A j = 0/ para i 6= j então podemos
formar o conjunto
[
A= Ai .
i∈I
A1 = {n ∈ N, n é par} A2 = {n ∈ N, n é ímpar},
é uma partição.
• Se X = {a, b, c, d, e, g, f , h} então a familia F = {A1 , A2 , A3 , A4 } em que
ão
é uma partição.
Se X = R então a familia F = {Cn , n ∈ N} em que
aç
é uma partição.
Seja F = {Ai , i ∈ I} uma familia finita para I = {1, · · · , n}. Definimos o produto cartesiano
X = A1 × · · · × An
O processo acima conclui em k = n. Como notação, temos que os elementos do produto A1 × · · · × Ak × Ak+1
são escritos
el
No caso em que todos os conjuntos que são membros da familia F sejam iguais, isto é,
denotamos
n vezes
z }| {
n
A = A×···×A.
Obs. Se a familia de conjuntos for finita, isto é for da forma F = {A1 , . . . , An } então se todos os Ai 6= 0/ então
podemos aplicar o axioma da união e do par n vezes e assim provar a existência das n−uplas (a1 , . . . , an ).
De onde A1 × · · · × An 6= 0.
/ Isto pode ser feito para todo n ∈ N aplicando o proceso de indução.
Obs. De modo geral, para uma familia arbitrária de conjuntos F = {Ai , i ∈ I} o produto cartesiano pode ser
definido como sendo uma familia de funções
∏ Ai = { f : I ⇒ ∪i∈I Ai , f (i) ∈ Ai }.
i∈I
Se a familia for finita isto é I = {1, . . . , n} para n ∈ N veremos (quando vejamos funções bijetoras) que o
produto cartesiano assim definido é de certa igual ao conjunto definido acima.
60 Capítulo 9. Familia de conjuntos
A1 = A2 = A3 = {a, b} = A
Então
ão
A3 = A1 × A2 × A3
= {((a, a), a), ((a, b), a), ((b, a), a), ((b, b), a), ((a, a), b), ((a, b), b), ((b, a), b), ((b, b), b)}
= {(a, a, a), (a, b, a), (b, a, a), (b, b, a), (a, a, b), (a, b, b), (b, a, b), (b, b, b)}.
aç
or
ab
el
Em
ão
10. Relações
aç
or
Dados A e B dois conjuntos quaisquer, estudamos formas de corresponder elementos de A com elementos de B.
Tais correspondências deve conter a informação dos dois elementos então o lugar mais natural para começar
ab
esse estudo é no produto cartesiano A × B.
Definição 10.1 Sejam A e B dois conjuntos.
• Uma relação de A em B é um subconjunto R do produto cartesiano A × B, isto é R ⊂ A × B.
• Neste caso, o conjunto A é dito conjunto de partida da relação e o conjunto B é dito conjunto de chegada
el
da relação.
• Dizemos que a ∈ A está relacionado com b ∈ B, e o denotamos por aRb ou a ∼ b, se (a, b) ∈ R.
• No caso em que A = B dizemos que R é uma relação em A.
Em
Obs.
• Como vimos na definição, uma relação de A em B é um subconjunto R do produto cartesiano A × B,
portanto uma relação pode ser visto como um elemento do conjunto de partes P(A × B).
• Em particular a relação correspondente a 0/ ⊂ A × B é conhecida como relação nula.
Exemplo 10.1 • Seja A é o conjunto formado por um proposições {P1 , . . . , Pn } e de todas aquelas forma-
das a partir de conjunções, negações e disjunções de um número finito delas. Definimos a relação
R = {(P, Q) ∈ A2 , P ⇒ Q é verdadeira}.
R = {(U,V ) ∈ A2 , U ×V ⊂ W }.
ão
• Sejam A = R e B = R. Definimos a relação
R = {(x, y) ∈ R × R, x2 + 2 · y2 = 1} ⊂ R × R.
aç
Gráficamente, a relação é o conjunto de pontos que está em vermelho.
or
ab
el
Img(R) = {b ∈ B, ∃ a ∈ A, (a, b) ∈ R}
Exemplo 10.2 • Seja A é o conjunto formado por um proposições {P1 , . . . , Pn } e de todas aquelas forma-
das a partir de conjunções, negações e disjunções de um número finito delas. Considere a relação
R = {(P, Q) ∈ A2 , P ⇒ Q é verdadeira}.
Então
Dom(R) = A Img(R) = A
R = {(U,V ) ∈ A2 , U ×V ⊂ W }.
Então
• Sejam A = Z, B = R e a relação
Então
ão
• Sejam A = R, B = R e a relação
R = {(x, y) ∈ R × R, x2 + 2 · y2 = 1} ⊂ R × R.
aç
Então
Dom(R) = {x ∈ R, −1 ≤ x ≤ 1}
√ √
Img(R) = {y ∈ R, −1/ 2 ≤ y ≤ 1/ 2}
or
Uma forma de representar gráficamente as relações são os chamados diagramas sagitais. Nesta representação
os conjuntos A e B se representam como no diagrama de Venn e se utilizam setas para indicar a relação. Por
ab
exemplo, se
e R é a relação
el
tem
Em
Podemos construir relações a partir de relações já conhecidas. Para isto assuma que temos
• uma familia de conjuntos não vazios F = {Ai , i ∈ I} tais que Ai ∩ A j 6= 0/
• mm conjunto não vazio B
• relações Ri ⊂ Ai × B.
64 Capítulo 10. Relações
como sendo
Gráficamente
ão
aç
or
ab
Obs. Observamos que algo similar pode ser feito no caso em que F é uma partição de um conjunto A.
el
Exemplo 10.3 Considere F = {(−∞, 0), [0, 1], (1, 2), {2}, (2, +∞)} e as relações
R1 = {(x, y) ∈ (−∞, 0) × R, y = 2 · x}
R2 = {(x, y) ∈ [0, 1] × R, y = x2 }
Em
Definição 10.3 Seja R ⊂ A × B uma relação de A em B. A relação inversa, que denotamos por R−1 , é a
relação de B em A definida por
e R é a relação
ão
R = {(a, 1), (a, 3), (d, 2), (e, 5), ( f , 5)}
então
aç
R−1 = {(1, a), (3, a), (2, d), (5, e), (5, f )}
or
ab
Exemplo 10.4 • Seja A é o conjunto formado por um proposições {P1 , . . . , Pn } e de todas aquelas forma-
el
R = {(P, Q) ∈ A2 , P ⇒ Q é verdadeira}.
Então
Em
R = {(U,V ) ∈ A2 , U ×V ⊂ W }.
Então
R−1 = {(V,U) ∈ A2 , U ×V ⊂ W }.
• Sejam A = Z, B = R e a relação
Então
ão
• Sejam A = R, B = R e a relação
R = {(x, y) ∈ R × R, x2 + 2 · y2 = 1} ⊂ R × R.
aç
Então
R−1 = {(y, x) ∈ R × R, x2 + 2 · y2 = 1} ⊂ R × R.
Gráficamente podemos representar a relação inversa como os pontos em vermelho
or
ab
el
ão
aç
que nos dá uma relação
or
ab
el
onde
Em
• Seja A = B = C = R e as relações
ão
R = {(x, y) ∈ N × R, y = sin(x)} ⊂ A × B S = {(x, y), y = 2 · x} ⊂ B ×C.
aç
⇔ y = 2 · sin(x).
De onde segue que
el
então
T ◦ (S ◦ R) = (T ◦ S) ◦ R,
ão
Exemplo 10.7 • Sejam A = Z, B = N e C = R
aç
(x, z) ∈ S−1 ∧ (z, y) ∈ R−1 ⇔ (z, x) ∈ S ∧ (y, z) ∈ R
⇔ (x = ez ) ∧ (z = y2 )
√
⇔ (z = ln(x)) ∧ ( z = y)
p
⇔ y = ln(x).
De onde segue que
(S ◦ R)−1 = {(x, y) ∈ R × Z, y =
p
or
ln(x)}
• Seja A = B = C = R e as relações
ab
R = {(x, y) ∈ R × R, y = sin(x)} ⊂ A × B
e
el
S = {(x, y) ∈ R × R, y = 2 · x} ⊂ B ×C.
⇔ x = 2 sin(y).
De onde segue que
Observamos que
70 Capítulo 10. Relações
ão
(1, 2) ∈ R3 ∧ (2, 1) ∈ R3 ,
no entanto, 2 6= 1.
– Não é possível encontrar ternas de (a, b) ∈ Ri ∧ (b, c) ∈ Ri ∧ (a, c) 6∈ Ri para todo i = 1, 2, 3 então as
três relações são transitivas.
• Considere em A = {a, b, c} a relação
aç
R = {(1, 2), (2, 1), (2, 3)}
– R não é reflexiva, pois 2 ∈ A mas (2, 2) 6∈ R,
– R não é simétrica pois (2, 3) ∈ R mas (3, 2) 6∈ R,
or
– R não é antisimétrica pois (1, 2) ∈ R e (2, 1) ∈ R mas 1 6= 2.
– R não é transitiva pois (1, 2) ∈ R e (2, 3) ∈ R mas (1, 3) 6∈ R.
• Seja U = {(a, b) ⊂ R, a < b} e defina
R = {(A, B) ∈ U 2 , A ⊂ B}
ab
– a relação R é reflexiva pois, para todo A ∈ U temos A ⊂ A de onde (A, A) ∈ R.
– a relação R é antisimétrica pois, ∀A ∈ U, ∀B ∈ U, (A, B) ∈ R e (B, A) ∈ R então A = B
– a relação R é transitiva pois se ∀A ∈ U, ∀B ∈ U, (A, B) ∈ R e (B,C) ∈ R implica A ⊂ B ⊂ C de onde
A ⊂ C e (A,C) ∈ R.
• Seja p ∈ N um número diferente de 0. Defina
el
que b, isto é (a, b) ∈ R, então b tem o mesmo resto na divisão por p que a, de onde (b, a) ∈ R.
– a relação R é transitiva pois se para a, b, c ∈ Z temos que a tem o mesmo resto na divisão por p que
b, isto é (a, b) ∈ R, e b tem o mesmo resto na divisão por p que c, isto é (b, c) ∈ R, então a tem o
mesmo resto na divisão por p que c de onde (a, c) ∈ R.
Definição 10.6 Seja R uma relação em A. A relação R é dita de equivalência se ela for reflexiva, simétrica e
transitiva.
Se a ∈ A definimos a clase de equivalência do elemento a como sendo o conjunto
Exemplo 10.9 •
• Seja A um conjunto e considere uma partição de A dada por
P = {Ai , i ∈ I}
Definimos a relação R por
a ∼ b ⇔ ∃ i ∈ I, (a ∈ Ai ) ∧ (b ∈ Ai ).
vamos ver que esta relação é de equivalência. De fato:
71
a ∈ Ai ∧ b ∈ Ai e (b ∈ A j ) ∧ (c ∈ A j )
ão
aç
d) A = ∪a∈A [a].
Em particular, a familia formada por todas as classes de equivalência formam uma partição de A. Denotamos,
por abuso de notação, esta familia por
U = {[a], a ∈ A}.
Demonstração.
or
a) Como a relação é simétrica a ∼ a para todo a ∈ A. De onde a ∈ [a] para todo a ∈ A.
b) Dados a, b ∈ A, se a ∼ b então para todo a0 ∈ [a] temos que a0 ∼ a e a ∼ b. Pela transitividade da relação
temos que a0 ∼ b e, portanto a0 ∈ [b]. Temos assim que [a] ⊂ [b]. De forma similar se prova que [b] ⊂ [a]
ab
e portanto [a] = [b].
Por outro lado se [a] = [b] então a ∈ [b] e, portanto, a ∼ b.
c) Seja c ∈ [a] ∩ [b] então c ∼ a e c ∼ b. Por transitividade temos então que a ∼ b. O resultado decorre agora
do item anterior .
d) Claramente ∪a∈A [a] ⊂ A. Se a ∈ A então, pelo item a) vemos que a ∈ [a] e portanto a ∈ ∪a∈A [a]. Da
el
Definição 10.7 Considere uma relação de equivalência R sobre um conjunto A. Seja F a partição de A dada
pela relação de equivalência R e, na qual, cada conjunto corresponde a uma classe de equivalência. Definimos
o conjunto quociente A/ ∼ como o conjunto que tem por elementos as classes de equivalências. Por abuso de
notação,
A/ ∼= {[a], a ∈ A} ⊂ P(A).
Z p = Z/ ∼ .
72 Capítulo 10. Relações
ão
R = {(A, B) ∈ U 2 , A tem a mesma área que B}
Claramente
– ∀ A ∈ U, (A, A) ∈ R
– (A, B) ∈ R ⇒ (B, A) ∈ R
aç
– [(A, B) ∈ R ∧ (B,C) ∈ R] ⇒ (A,C) ∈ R.
o quociente é T / ∼ está formado pelas classes
em que or
Ar = triângulo com vértices em V1 = (0, 0), V2 = (0, 2), V3 = (r, 0).
ab
Definição 10.8 Seja R uma relação em A. Dizemos que R é uma relação de ordem (ou de ordem parcial), e
a denotamos por a ≺ b quando (a, b) ∈ R, se ela for reflexiva, antisimétrica e transitiva.
Neste caso dizemos que o par (A, ≺) é um conjunto ordenado. Mais ainda se a e b são dois elementos
distintos de A e são tais que a ≺ b então dizemos que b é consecutivo de a.
el
Obs. As relações de ordem parcial é uma generalização da "inclusão"para conjuntos e do "menor ou igual"para
números.
Em
R = {(p, q) ∈ Z2 , p divide a q} ⊂ Z2 ,
a1 . . . am ∼ b1 . . . bm ⇔ a1 = b1
Então dividimos as palavras em classes. Cada classe contem as palavras que começam com a mesma letra,
ão
isto é, por exemplo
[a] = {palavras que começam com a}
[b] = {palavras que começam com b}
.. ..
. .
aç
[z] = {palavras que começam com z}
Então, por exemplo para o idioma português.
Também em U podemos definir a ordem dada pela ordem lexicográfica, esta relação é uma relação de
or
ordem. Esta ordem precisa primeiro de um ordenamento das letras do alfabeto para depois induzir a ordem
nas palavras. Neste caso temos a ordem em que está o diccionário.
ab
Definição 10.9 Seja (A, ≺) um conjunto ordenado.
• Dois elementos a, b de A são comparáveis se
P = (a ≺ b) ∨ (b ≺ a)
∀ a ∈ A ∀ b ∈ A, [a 6= b ⇒ (a ≺ b) ∨ (b ≺ a)]
R = {(a, b) ∈ N2 , a ≤ b}
é uma relação de ordem parcial que não é total pois há conjuntos que não são comparáveis, por exemplo
A = {a} e B = {b} .
Definição 10.10 • Um conjunto (A, ≺) é dito bem ordenado se (A, ≺) é um conjunto totalmente orde-
nado para o qual todo subconjunto não vazio tem elemento mínimo, isto é, para todo B ⊂ X existe
b ∈ B tal que b ≤ c para todo c ∈ B.
• Um conjunto que admite uma relação de ordem para a qual é bem ordenado é dito um conjunto que
admite uma boa ordenação.
Obs. Como consequência disto é que: Existe uma boa ordem para os números reais. O problema é que não se
sabe qual é essa ordem.
ão
aç
or
ab
el
Em
ão
11. Funções
aç
or
Passamos a estudar o conceito de função. Éste é um dos conceitos fundamentais da matemática e que aparece
em cada uma de suas áreas. Começamos com a sua definição.
ab
Definição 11.1 Sejam A e B dois conjuntos. Uma função f de A em B, que denotamos por f : A → B é uma
relação f ⊂ A × B que satisfaz
• Dom( f ) = A
• ∀ x ∈ A, ∀ y, ∀ z ∈ B, [(x, y) ∈ f ∧ (x, z) ∈ f ] ⇒ (y = z).
el
f (x) = y
• A relação nula associada a 0/ é uma função pois podemos ver 0/ = A × 0. / Portanto o domínio é A e a
segunda condição é satisfeita naturalmente pois, por equivalência da contrapositiva ∀ x ∈ A, ∀ y, ∀ z ∈
B,
y 6= z ⇒ [(x, y) 6∈ f ∨ (x, z) 6∈ f ].
• Há relaçoes que não são funções. Por exemplo, a relação dada pelo círculo S1 ⊂ R2 .
não é função. De fato, para x1 temos que há dois pontos y1 e y2 tais que (x1 , y1 ) e (x2 , y2 ) estão na
relação.
76 Capítulo 11. Funções
ão
Observamos que de cada elemento do domínio sai uma única seta.
Estabelecemos a seguinte equivalência entre funções.
aç
Definição 11.2 Duas funções f , g : A → B são iguais se f (a) = g(a) para todo a ∈ A.
Exemplo 11.1 • Seja f : A → B e b0 ∈ B. A função tal que f (a) = b0 para todo a ∈ A é chamada de
função constante.
• Seja f : A → A dada por f (a) = a para todo a ∈ A. Esta função é conhecida como função identidade e a
denotamos por IA : A → A.
χA0 (a) =
1 se a ∈ A0
0 se a 6∈ A0
.
or
• Seja A0 ⊂ A. Definimos a função característica χA0 : A → N por
ab
Vamos a mostrar agora duas formas diferentes de contruir funções a partir de funções conhecidas.
• Restrição de uma função: Dada f : A → B uma função e A0 ⊂ A definimos a função f |A0 : A0 → B por
f |A0 (a) = f (a).
el
Exemplo 11.2 • Seja A = (−∞, −1] ∪ (−1, 2) ∪ {2} ∪ (2, +∞). Definimos então as funções f1 , f2 , f3 e
f4 como sendo
f1 : (−∞, −1] → R, x → ex
f2 : (−1, 2) → R, f2 (x) = x2
f3 : {2} → R, f3 (2) = 5
f4 : (2, +∞) → R, f4 (x) = cos(x)
ão
Então
x se x ∈ (−∞, −1]
e
x2
se x ∈ (−1, 2)
f (x) =
aç
5 se x = 2
cos(x) se x ∈ (2, +∞)
f (x) =
x + 2 se x > 0
x2 + 1 se x ≤ 0
Definição 11.3 Seja A0 ⊂ A e seja f : A0 → B uma função. Uma extensão de f é uma função F : A → B tal
que F|A0 = f .
Exemplo 11.3 A extensão de uma função não é necessáriamente única. por exemplo f : {0, 1, 2, 3} → N
el
F : N → N, F(a) = a
e
Em
a se a ≤ 4
G : N → N, G(a) =
a2 se a > 4
∀ x ∈ X, (g ◦ f )(x) = g( f (x))
Assim como acontece com as relações, temos que vale a associatividade na composição de funções.
Proposição 11.1 Sejam f : W → X, g : X → Y, h : Y → Z, então
f ◦ (g ◦ h) = ( f ◦ g) ◦ h
ão
Demonstração. Decorre do resultado visto para relações.
Obs. A composição de funções, assim como para acontece para as relações em geral, não é comutativa
aç
Exemplo 11.4 • Considere f (x) = 2x + 1 e g(x) = x2 + 1. Descreva a composta. Da definição segue que
f (x) = cos(x) : R → R,
or
• Vamos aqui exemplificar a definição 8. Considere as seguintes funções
g(x) = x2 + 1 : R → R e h(x) = ex : R → R.
ab
Segue então que
• Considere
x − 1 se x ∈ (−∞, 0]
(
x2
se x ∈ (−∞, 1]
f (x) = x e g(x) = 2 se x ∈ [0, 2]
e se x ∈ (1, ∞)
2
x +1 se x ∈ (2, ∞)
Em
Observamos que
– Se x ∈ (−∞, 1] então x2 ∈ [0, ∞) = [0, 2] ∪ (2, ∞) de onde
Obs. Se f : A → B é uma função bijetora então, pelo fato de ser função, para cada elemento de a ∈ A existe um
unico b ∈ B tal que f (a) = b. Agora, pelo fato de ser bijetora, para cada elemento de b ∈ B existe um único
elemento de a ∈ A tal que f (a) = b. Isto é, os elementos de A e B estão em correspondência biunívoca.
79
Claramente f é sobrejetora, mas não necessáriamente injetora. De fato, por exemplo, se U = N e A = {1}
então
ão
f : P(A) → P(A ∪ B), f (D) = D
então f é injetora mas não sobrejetora pois para B ∈ P(A ∪ B) não há nenhum conjunto D ∈ P(A) tal
que f (D) = B.
aç
• f : R → R dada por f (x) = x3 é bijetora.
√
De fato, dado y ∈ R então, x = 3 y satisfaz f (x) = y portanto é sobrejetora.
Se f (x1 ) = f (x2 ) então x13 = x23 de onde
Portanto g ◦ f é sobrejetora.
• Assuma que f ◦ g é bijetora. Dado c ∈ C existe a ∈ A tal que c = g ◦ f (a) = g( f (a)). Como f (a) ∈ B
temos que existe b ∈ B tal que g(b) = c de onde segue que g é sobrejetora.
Se f (a1 ) = f (a2 ) temos que
Exemplo 11.6 Seja f : [0, ∞) → R dada por f (x) = x2 e g : R → [0, ∞) dada por g(x) = |x|. Claramente f não
é sobrejetora nem g é injetora, no entanto, g ◦ f : [0, +∞) → [0, +∞) é dada por f (x) = x e, portanto, é bijetora.
80 Capítulo 11. Funções
Corolário 11.1 Seja f : A → B é invertível então para todo a ∈ A e para todo b ∈ B temos
f (a) = b ⇔ f −1 (b) = a.
f (a) = b ⇔ (a, b) ∈ f
ão
⇔ (b, a) ∈ f −1
⇔ f −1 (b) = a.
aç
Teorema 11.2 Uma função f : A → B é invertível se, e somente se, f é bijetora. Mais ainda, f −1 é também
bijetora.
⇔ f (x) = y.
de onde segue que ( f −1 )−1 = f e, portanto f −1 é invertível e, pelo visto acima, bijetora.
f −1 ◦ g−1
Demonstração. Como f e g são bijetoras, por um resultado acima, temos que g ◦ f é sobrejetora e injetora, de
onde segue que é bijetora. O restante segue de observar que
f (A1 ) = { f (x) ∈ B, x ∈ A1 } ⊂ B,
f −1 (B1 ) = {x ∈ A, f (x) ∈ B1 } ⊂ A.
Demonstração. Se y ∈ f (A1 \A2 ) então existe x ∈ A1 \A2 tal que f (x) = y. Como f é injetora e x 6∈ A2 , y 6∈ f (A2 )
de onde y ∈ f (A1 )\ f (A2 ). Por outro lado, se y ∈ f (A1 )\ f (A2 ) então existe x ∈ A1 tal que f (x) = y, como
y 6∈ f (A2 ) e f é injetora, temos que x 6∈ A2 .
Exemplo 11.7 Se f não é injetora não podemos garantir que o resultado acima vale. De fato seja f : R → R
dada por f (x) = x2 . Considere A1 = R e A2 = [0, ∞), então
ão
f (A1 )\ f (A2 ) = 0.
/
aç
• f −1 (∩i∈I Bi ) = ∩i∈I f −1 (Bi ).
• f −1 (Bi \B j ) = f −1 (Bi )\ f −1 (B j )
Demonstração. •
x ∈ f −1 (∪i∈I Bi ) ⇔ f (x) ∈ ∪i∈I Bi
⇔ ∃ i ∈ I, f (x) ∈ Bi
⇔ ∃ i ∈ I, x ∈ f −1 (Bi )
⇔ x ∈ ∪i∈I f −1 (Bi ).
or
ab
•
x ∈ f −1 (∩i∈∈I Bi ) ⇔ f (x) ∈ ∩i∈I Bi
⇔ ∀ i ∈ I, f (x) ∈ Bi
⇔ ∀ i ∈ I, x ∈ f −1 (Bi )
el
⇔ x ∈ ∩i∈I f −1 (Bi ).
•
x ∈ f −1 (Bi \B j ) ⇔ f (x) ∈ (Bi \B j )
⇔ ( f (x) ∈ Bi ) ∧ ( f (x) 6∈ B j )
⇔ [x ∈ f −1 (Bi )] ∧ [x 6∈ f −1 (B j )]
Em
⇔ x ∈ f −1 (Bi )\ f −1 (B j )
Se f : A → B é injetora podemos pensar que, de alguma forma, A ⊂ B. Nesse sentido, o seguinte resultado é
uma generalização do critério de igualdade entre conjuntos.
Demonstração. Seguimos o trabalho de "D. Tonien, A simple visual proof of the Schröder-Bernstein theorem.
Elemente der Mathematik 62 (2007)".
Definimos as familias de conjuntos F1 = {Ai , i ∈ N} e F1 = {Bi , i ∈ N} em que
• A0 = A e B0 = B
• se i > 0 então
Ai = g(Bi−1 ) e Bi = f (Ai−1 )
Graficamente
82 Capítulo 11. Funções
ão
aç
Observamos que, da injetividade de f e g, temos que existem bijeções
A ↔ B1 ↔ A2 ↔ B3 ↔ A4 ↔ · · ·
B ↔ A1 ↔ B2 ↔ A3 ↔ B4 ↔ · · ·
e que
Por contrução
f (An ) ⊂ Bn
or
ab
Ai+1 ⊂ Ai e Bi+1 ⊂ Bi ∀ i ∈ N,
A1 = g(B) ⊂ A e B1 = f (A) ⊂ B.
el
e
Em
C j = A j \A j+1 D j = B j \B j+1 .
são bijetores para todo i ∈ N, pois por um lado são injetores, e por outro lado são injetores e
f (Ci ) = f (Ai \Ai+1 )
= f (Ai )\ f (Ai+1 ) (pois f é injetor)
= Bi+1 \Bi = Di+1
Sejam
à = ∩i∈N Ai e B̃ = ∩i∈N Bi
Como B̃ ⊂ f (A) e
temos que f é uma bijeção entre à e B̃. De forma similar g é uma bijeção entre B̃ e Ã.
Construimos então h : A → B como
ão
f (x) se x ∈ C2i
h(x) = −1
g (x) se x ∈ C2i+1
f (x) = g−1 (x) se x ∈ Ã.
aç
or
ab
el
As consequências deste resultado, para o caso dos conjuntos numéricos, é bem pouco intuitiva.
Exemplo 11.8 Considere os conjuntos A = (1, 3) e B = (1, 3) ∪ (4, 5). Considere
f : A → B, f (x) = x,
Em
e
3
+ 14 x se x ∈ (1, 3)
g : B → A, g(x) = 4 .
x − 2 se x ∈ (4, 5)
Observamos as duas funções são injetoras. Para a primeira isto decorre trivialmente da definição pois
f (x1 ) = f (x2 ) ⇒ x1 = x2 .
g(x1 ) = g(x2 ) ⇒ [x1 ∈ (1, 3) ∧ x2 ∈ (1, 3)] ∨ [x1 ∈ (4, 5) ∧ x2 ∈ (4, 5)]
3 + x1 3 + x2
= ⇒ x1 = x2 ,
4 4
• se x1 ∈ (4, 5) ∧ x2 ∈ (4, 5) então
x1 − 2 = x2 − 2 ⇒ x1 = x2 .
ão
Agora, o teorema de Cantor-Bernstein-Schröder garante que existe uma função bijetora
Veremos depois que isto implica que os dois conjuntos tem a mesma quantidade de elementos.
aç
Um tipo particular de funções são as conhecidas como operações unárias e binárias.
Definição 11.7 • Dados dois conjuntos A e B uma operação unária é uma função f : A → B.
• Dados três conjuntos A, B e C, uma operação binária é uma função f : A × B → C.
Obs.
or
• As operações unárias e binárias geralmente não são escritas na forma f (a) = b (para a unária) ou
f (a, b) = c (para a binária) mas na forma
ab
– f a ou a f para a unária, em que f é o símbolo da operação.
– a f b em que f é o símbolo utilizado para a operação binária.
• As operações binárias são a base do estudo de estruturas algébricas. Algumas delas veremos mais
adiante no texto.
n2 = n · n.
∧ : P × P → P, (p, q) → p ∧ q,
Dada uma familia de conjuntos F = {Ai , i ∈ I} indexadas por um conjunto I, consideramos o conjunto das
funções
U = { f : I → ∪i∈I Ai , f (i) ∈ Ai }
85
No caso em que I = {1, . . . , n} este conjunto pode ser naturalmente identificado de forma bijetora com A1 × · · · An
por meio da função
F : U → A1 × · · · × An , F( f ) = ( f (1), . . . , f (n))
Sua inversa é
F −1 : A1 × · · · × An → U ,
ão
F −1 ( f )(i) = ai ∀i = 1 . . . n.
aç
∏ Ai = { f : I → ∪i∈I Ai , f (i) ∈ Ai }.
i∈I
produto cartesiano é não vazio. No entanto, isto é assumido como um axioma, que é o Axioma da escoha:
Para toda familia de conjuntos não vacios F , seu produto cartesiano é não vacío.
Uma boa referência sobre o axioma da escolha e suas equivalências é: Jech T. J. - The axiom of choice - North
Em
Holland (1973).
É relevante também observar que o axioma da escolha é independente dos axiomas de Zermelo-Fraenkel. De
fato, Godel mostrou que os axiomas de Zermelo-Fraenkel+(Axioma da escolha) são consistentes se os axiomas
de Zermelo-Fraenkel são consistentes. Cohen mostrou que Zermelo-Fraenkel+ ¬(Axioma da escolha) são
consistentes se os axiomas de Zermelo-Fraenkel são consistentes.
Nestas notas vamos assumir o axioma da escolha.
Em
el
ab
or
aç
ão
II
Conjuntos Numéricos
ão
aç
or
ab
el
Em
12 Números Naturais . . . . . . . . . . . . . . . . . . . 89
13 Cardinalidade de conjuntos . . . . . . . . . 99
15 Divisibilidade . . . . . . . . . . . . . . . . . . . . . . . 121
aç
or
Começamos agora a estudar a construção dos conjuntos numéricos. Para responder à pergunta "o que é um
número?" vamos mergulhar a resposta na teoria de conjuntos. Seguiremos assim a construção dos números
ab
naturais feita por von-Neuman (John von Neumann, matemático húngaro).
Vimos que,
• o axioma da existência garante a existência do conjunto vazio. Mais ainda, temos provado que o conjunto
vazio é subconjunto de qualquer conjunto.
• o axioma do infinito, garante que para todo conjunto A existe o seu conjunto sucessor s(A) = A ∪ {A} que,
el
Obs. Observar que não fazemos distinção entre elemento e conjunto assim como foi dito nos axiomas de
Zermelo-Fraenkel.
Obs.
• Na verdade o conjunto N pode ser definido de forma mais precisa do que listando simplesmente os
seus elementos. O mais correto seria dizer que N é o conjunto de elementos que satisfaz
– para cada a ∈ N e b, c ∈ a tais que b 6= c temos que b ∈ c ou c ∈ b. Mais ainda, se c ∈ b ∈ a
então c ∈ a.
90 Capítulo 12. Números Naturais
ão
Demonstração. Provamos isto provanto a contrapositiva. Se n 6= m então, por exemplo, existe k tal que k ∈ n e
k 6∈ m. Tal k 6= 0 pois 0 ∈ m e 0 ∈ n. Temos então que s(k) ∈ n mas s(k) 6∈ m. Portanto s(n) 6= s(m).
A seguinte é a definição que caracteriza o conjunto dos números naturais. Veremos que esta caracterização
vai ser utilizada para definir a soma, o produto e suas respectivas propriedades.
aç
Definição 12.2 Um número natural é um conjunto que pertence a todo conjunto indutivo. O conjunto de
todos estes elementos é chamado conjunto dos números naturais e o denotamos por N.
Obs. Pedir que os números naturais estejam em todo conjunto indutivo é uma condição de minimalidade. De fato
podemos pensar num conjunto M que esteja construído a partir dos conjunto 0/ e A e todos seus sucessores.
ab
Claramente M é indutivo, no entanto seus elementos não vão estar em todos os conjuntos indutivos. Por
exemplo A não está em N .
Teorema 12.1 Existe um conjunto cujos elementos são exatamente os números naturais
el
é não vazio, portanto tem ao menos um elemento n∗ . Claramente n∗ 6= 0 pois 0 ∈ U. Então n∗ = k + 1 para
algum k ∈ U. Mas como U é indutivo n∗ = k + 1, contradizendo a definição de n∗ .
Pelo axioma da especificação a função proposicional
x ∈ U ⇔ [x ∈ N ∧ (∀ B conjunto indutivo, x ∈ B)]
tem um domínio que, por definição, deve ser N.
Temos assim que o conjunto N é indutivo e é um subconjunto de todo conjunto indutivo.
Teorema 12.2 O conjunto N construído acima coincide com N. Mais ainda, todo número natural diferente
de 0 é sucessor de algúm número natural.
Demonstração. Sabemos que como N é indutivo N ⊂ N e como N é indutivo e está contido em todo conjunto
inductivo temos que N ⊂ N . De onde segue que N = N.
Para o restante do resultado observamos que a proposição
∃ a ∈ N, 0 = s(a)
é falsa pois não existe conjunto cujo sucessor seja 0.
/ Portanto, a negação da proposição é verdadeira de onde
segue o resultado.
91
Teorema 12.3 — Princípio de indução ou Axioma indução. Todo subconjunto indutivo de N coincide
com N.
Demonstração. Assuma que B ⊂ N. Como B é indutivo temos que N ⊂ B pelo teorema anterior. Portanto
B = N.
Portanto, para mostrar que um conjunto M ⊂ N é o conjunto dos número naturais mostramos o resultado do
teorema, isto é:
ão
i- 0 ∈ M
ii- k ∈ M ⇒ s(k) ∈ M, ∀ k ∈ M
então M = N.
aç
• m+0 = m
• m + s(n) = s(m + n)
• m + (n + p) = (m + n) + p (associatividade)
• m + n = n + m (comutatividade)
• m + p = n + p ⇒ m = n (cancelamento).
• m + n = 0 então m = 0 e n = 0.
Mm = {n ∈ N, n + m está definido}.
m + s(k) = s(m + k)
temos que s(k) ∈ Mm . Pelo princípio de indução temos que N ⊂ Mm , de onde segue o pedido.
• Da definição m + 0 = m. Seja
M = {m ∈ N, 0 + m = m}
0 = 0 + n = n + 0 = n.
Portanto o 0 é único.
• Primeiramente observamos que m + 1 = 1 + m. Para isto, defina
M = {n ∈ N, 1 + m = m + 1}.
ão
Claramente 0 ∈ M pois 1 + 0 = 1 e 0 + 1 = s(0 + 0) = s(0) = 1. Por outro lado se k ∈ M então
aç
de onde M = N.
Seja m ∈ N e defina
Mm = {n ∈ N, n + m = m + n}.
m + (k + 1) = m + s(k)
= s(m + k)
or
Claramente 0 ∈ Mn pelo item anterior. Se k ∈ M então n + k = k + m, como
= s(k + m)
ab
= k+m+1
= (k + 1) + m
de onde s(k) ∈ Mn e portanto Mn = N.
• Dados m, n ∈ N considere
el
Mm,n = {p ∈ N, m + p = n + p ⇒ m = n}.
⇒ m + k = n + k,
de onde m = n. Portanto s(k) ∈ Mm,n e Mm,n = N.
• Assuma que m + n = 0 então, se n 6= 0
m + n = m + s(n1 ) = s(m + n1 ) 6= 0.
Obs.
• Da definição, que
m · 1 = m · (0 + 1) = m · 0 + m = 0 + m = m
93
• a partir do produto definimos a potenciação como segue, para a, n ∈ N, definimos an como sendo
n vezes
an = a · a · · · a
z }| {
se n > 0 e
a0 = 1.
ão
Utilizando a definição dos números naturais junto com as propriedades da soma é possível mostrar que
Proposição 12.2 Para quaisquer m, n, p ∈ N temos
• 0 · m = 0.
• m · n está definida.
aç
• O número 1 é o único natural tal que m · 1 = m (existência de elemento neutro)..
• m · (n + p) = m · n + m · p, e (n + p) · m = n · m + p · m (distributividade).
• m · n = n · m (comutatividade).
• m · (n · p) = (m · n) · p (associatividade)
• se p 6= 0 então m · p = n · p ⇒ m = n (cancelamento).
• m · n = 0 então m = 0 ou n = 0.
Demonstração. • Seja
or
M = {m ∈ M, 0 · m = 0}.
ab
Claramente 0 ∈ M. Se k ∈ M então
0 · s(k) = 0 · k + 0 · 1 = 0 + 0 = 0.
el
M = {n ∈ N, m · n está definida.}
Em
m · s(k) = m · (k + 1) = m · k + m.
Como ambos termos estão definidos e a soma está definida, temos s(k) ∈ M de onde M = N.
• Seja
M = {m ∈ N, 1 · m = m}.
Claramente 0 ∈ M. Se k ∈ M então
1 · s(k) = 1 · k + 1 · 1 = k + 1 = s(k).
Portanto s(k) ∈ M e M = N. Para ver a unicidade observamos que se n é tal que m · n = m = n · m para
todo m ∈ N então
1 = 1 · n = n · 1 = n.
• Sejam m, n ∈ N e considere
Mm,n = {p ∈ N, m · (n + p) = m · n + m · p}.
94 Capítulo 12. Números Naturais
ão
• Seja m ∈ N e defina o conjunto
Mm = {n ∈ N, m · n = n · m}.
aç
N = {m ∈ N, 0 · n = 0 = n · 0}
0 · s(k) = 0 · (k + 1) = 0 · k + 0 = 0 = s(k) · 0
Se p ∈ Mm então m · p = p · m. Como
or
temos que s(k) ∈ N e, portanto, N = N. De onde 0 ∈ Mm .
m · s(p) = m · p + m = p · m + m = (p + 1) · m
ab
temos que s(p) ∈ Mm de onde Mm = N.
• Sejam m, n ∈ N e considere
Mm,n = {p ∈ N, m · (n · p) = (m · n) · p}.
el
= (m · n) · (k + 1)
= (m · n) · s(k).
Portanto s(k) ∈ Mm,n e N = Mm,n .
• Se m = n = 0 não ha nada que provar. Claramente se m = 0 então n = 0 pois caso contrário a identidade
não vale. Assuma m 6= 0, n 6= 0, que m = n + k com k 6= 0, isto é k = s(k1 ). Se
m · p = n · p,
temos
m· p = n· p+n·k
= n · p + n · s(k1 )
= n · p + n · k1 + n
então 0 = n · k1 + n de onde n = 0 o que é uma contradição. Portanto k = 0 e m = n.
• Assuma que m · n = 0 e assuma que n 6= 0 então n = s(n1 ) de onde
0 = m · n = m · s(n1 ) = m · n1 + m
então m · n1 = 0 e m = 0.
95
Definição 12.5 Sejam k, m ∈ N números naturais. Dizemos que m > k (ou k < m) se existem um número
l ∈ N tal que l 6= 0 e
m = k + l.
Dizemos que uma função proposicional P(n) vale para todo n ≥ k se ela for verdadeira para n = k e para
todo m tal que m > k.
ão
Obs.
• Dados m, n ∈ N, denotamos
– m ≥ n se, e somente se, n ≤ m.
– m > n se, e somente se, n < m.
• Não é necessário definir a soma para definir a < b. De fato, utilizando a construção dos naturais feita
acima podemos dizer que dados a, b ∈ N dizemos que
aç
a<b ⇔ a ∈ b.
• Voltaremos mais tarde sobre isto e veremos que ">"induz o que chamamos uma "relação de ordem
total"
or
O princípio de indução fornece uma técnica muito útil para provar que uma proposição é verdadeira a partir
de um certo número natural. Éste é o conteúdo do seguinte teorema.
Teorema 12.4 — Princípio de Indução generalizada. Seja k ∈ N um número natural fixo e P(n) uma
função propocicional com domínio em N. Se
ab
• P(k) é verdadeira e
• se, para todo r > k, P(r) verdadeira garante que P(r + 1) é verdadeira,
então, P(n) é verdadeira para todo n ≥ k.
Demonstração. Para demonstrar o teorema utilizamos o princípio de indução. Definimos a função proposicional
el
Observamos que
• Q(0) = P(k) é verdadeira, então 0 ∈ M
Em
101 − 1 = 9 = 3 · 3
• Assuma que k ∈ M então existe K ∈ N tal que 3 · K = 10k − 1. Vemos que k + 1 ∈ M, de fato
10k+1 − 1 = 10 · 10k − 1
= 9 · 10k + 10k − 1
= 9 · 10k + 3 · K
= 3 · (3 · 10k + K)
96 Capítulo 12. Números Naturais
Agora, pelo princício de indução, M = N e temos que P(n) vale para todo n ≥ 1.
2. Provar que, para todo n ≥ 1, temos
n
n2 (n + 1)2
∑ i3 = 13 + 23 + · · · + n3 = 4
.
i=1
ão
e seja M o seu domínio de verdade. Observamos que
• observamos que 1 ∈ M pois
1 · (1 + 1)
1=
2
aç
• Assuma que k ∈ M então
k2 (k + 1)2
13 + 23 + · · · + k3 = .
4
Vemos que k + 1 ∈ M, de fato
13 + 23 + · · · + k3 + (k + 1)3 =
=
or
k2 (k + 1)2
4
(k + 1)2 2
+ (k + 1)3
(k + 4k + 4)
ab
4
(k + 1)2
= (k + 2)2
4
(k + 1)2 (k + 2)2
=
4
Agora, pelo princício de indução, M = N e temos que P(n) vale para todo n ≥ 1.
el
41 − 1 = 9 = 3.
Q ∧ (P1 ∨ P2 ∨ · · · ∨ Pn ) = (Q ∧ P1 ) ∨ (Q ∧ P2 ) ∨ · · · ∧ (Q ∧ Pn )
para todo n ∈ N.
Para isto construímos a função proposicional
R(n) = Q ∧ (P1 ∨ P2 ∨ · · · ∨ Pn ) = (Q ∧ P1 ) ∨ (Q ∧ P2 ) ∨ · · · ∧ (Q ∧ Pn )
Q ∧ (P1 ) = (Q ∧ P1 ).
Q ∧ (P1 ∨ P2 ∨ · · · ∨ Pk ) = (Q ∧ P1 ) ∨ (Q ∧ P2 ) ∨ · · · ∧ (Q ∧ Pk ).
ão
= Q ∧ (P1 ∨ P2 ∨ · · · ∨ Pk ) ∨ (Q ∧ Pk+1 )
= (Q ∧ P1 ) ∨ (Q ∧ P2 ) ∨ · · · ∧ (Q ∧ Pk ) ∨ (Q ∧ Pk+1 )
Agora, pelo princício de indução, M = N e temos que R(n) vale para todo n ≥ 1.
5. Para mostrar que uma proposição P(n) com nomínio nos naturais é válida para todos os naturais n ≥ k
aç
temos que ver sempre que P(k) é verdadeira não bastando mostrar que P(n) verdadeira implica P(n + 1)
verdadeira. De fato, observe que se
de onde P(n + 1) é verdadeira. No entanto sabemos que P(0) é falsa e, portanto, o axioma de indução não
ab
nos permite concluir nada.
el
Em
Em
el
ab
or
aç
ão
ão
13. Cardinalidade de conjuntos
aç
or
Procuramos mensurar de alguma forma o tamanho dos conjuntos. Quando o conjunto tem um número natural de
elementos isso pode ser feito simplesmente ao contar seus elementos. No entanto, se esse não for o caso, como
ab
mensuramos o conjunto? o que significa neste caso que dois conjuntos tem a mesma quantidade de elementos?
É sobre isso que trata o conteúdo deste capítulo.
Começamos com algumas definições.
Definição 13.1 • A cardinalidade de um conjunto A é quantidade elementos de um conjunto. Denota-
el
Obs. Dados dois conjuntos A, B tais que ]A ≤ ]B e assuma que não existe uma função bijetora f : A → B então
dizemos que ]A 6= ]B e, neste caso, denotamos
]A < ]B.
Demonstração. Dado A conjunto defina f : A → P(A) como f (a) = {a}. Então f é injetora e ]A ≤ ]P(A).
Seja g : A → P(A) e considere o conjunto
B = {a ∈ A, a 6∈ g(a)}
a ∈ B se, e somente se a 6∈ B,
100 Capítulo 13. Cardinalidade de conjuntos
Corolário 13.2 Não existe um conjunto com cardinalidade maior do que todos os outros conjuntos.
Lema 13.1 Sejam A e B dois conjuntos. Assuma que existe uma função sobrejetora f : A → B. Então ]B ≤ ]A.
ão
Demonstração. Para a prova utilizamos o axioma da escolha. Dado b ∈ B escolhemos ab ∈ A tal que f (ab ) = b.
Observamos que para cada b temos um único ab . Seja à = ∪b∈B ab ⊂ A e defina
h : Ã → B, h(ab ) = b
aç
Claramente, h é bijetora por construção. Então temos
]B = ]Ã ≤ ]A.
or
Lema 13.2 Sejam A e B dois conjuntos. Assuma que ]A ≤ ]B e que a ∈ A e b ∈ B são dois elementos. Então
](A\{a}) ≤ ](B\b)
ab
Demonstração. Seja f : A → B injetora. Seja à = A\{a}, B̃ = B\{b} e a0 ∈ A tal que f (a0 ) = b. Definimos
h : Ã → B̃ por
f (x) se x 6= a0
h(x) =
f (a) se x = a0
el
n + 1 = {0, 1, 2, . . . , n}.
Definição 13.2 Um conjunto A é dito finito se ele tem a mesma cardinalidade que o conjunto correspondente
um n ∈ N. Neste caso, o cardinal de A será repressentado pelo número natural que tem a mesma cardinalidade
que A.
Caso o conjunto não seja finito, ele será dito infinito.
Com a definição acima, se A um conjunto finito, o cardinal de A, que denotamos por ]A, é
• ]A = 0 se A = 0.
/
• ]A = n se A tem a mesma cardinalidade que {0, 1, 2, . . . , n − 1} ou {1, 2, . . . , n}.
101
Exemplo 13.1 • Da definição, todo conjunto A que tem a mesma cardinalidade com algúm conjunto da
forma
{0, 1, 2, 3, . . . , n}
P = {3 · k, k ∈ N}
ão
Claramente a função f : P → N dada por f (x) = x é injetora. Por outro lado a função g : N → P é também
injetora. Agora o Teorema de Cantor-Bernestein Schröder garante a existência de uma bijeção. De onde
segue que N não é finito.
aç
Teorema 13.2 Seja A um conjunto. Então A é um conjunto finito se, e somente se, para todo subconjunto
próprio B ⊂ A temos ]B 6= ]A.
Claramente g é injetora e sobrejetora. De onde ]A = ]A\{ f (0)}. Então A é infinito e existe um subconjunto
próprio de A com a mesma cardinalidade que A. De onde provamos que A finito implica que todo subconjunto
el
Exemplo 13.2 • A = {a, b, c, d, e} e B = {1, 2, 3, 4, 5} são finitos e tem a mesma cardinalidade. Mais
ainda A ∼ B pela correspondência
• A = N e B = {2n, n ∈ N} tem a mesma cardinalidade e não são finitos. Mais ainda A ' B pela correspon-
dência
n ↔ 2n.
Assim como no conjunto dos números naturais é possível definir um operação soma e produto entre números
cardinais, básicamente, a ideia é que se α = ]A e β = ]B são dois números cardinais com A ∩ B = 0,
/ então
β α = ]{ f : A → B, função}.
No caso, 00 = 1 para números cardinais pois a única função que satisfaz é a que corresponde a relação nula
0/ = 0/ × 0.
/
Com isto temos os seguintes resultados para conjuntos finitos.
102 Capítulo 13. Cardinalidade de conjuntos
Então
ão
A ∪ B = {a1 , . . . , an , b1 , . . . , bm } A ∩ B = {a1 , . . . , ak }.
aç
B ↔ B̃ = {n + 1, n + 2, . . . , n + m + k}
A ∪ B ↔ C̃ = {1, 2, . . . , n + m}
A ∩ B ↔ D̃ = {n + m + 1, . . . , n + m + k}
Corolário 13.3 Sejam α e β números cardinais finitos, então a soma entre eles tem como resultado o valor
da soma como números naturais α · β .
Em
Teorema 13.3 Para todo n ∈ N temos que se A é um conjunto tal que ]A = n então ]P(A) = 2n .
Demonstração. Vamos a mostrar o resultado pelo princípio de indução e assumindo a bijeção com conjuntos
disjuntos para poder fazer a soma. Para isto construimos a função proposicional,
A = {a1 , . . . , ak , ak+1 }
escrevemos A = A1 ∪ Ak em que
A1 = {a1 , . . . , ak }, A2 = {ak+1 }
Então um elemento B do conjunto de partes de A satisfaz somente uma das seguintes afirmações
• B ∈ P(A1 ) (temos ]P(A1 ) elementos deste tipo)
• B = C ∪ A2 com C ∈ P(A1 ) (temos ]P(A1 ) elementos deste tipo).
103
portanto
Obs. Quando A é não finito temos também que P(A) = 2 . Mas esse número cardinal tem a seguinte descrição:
]A
Dado A um conjunto, considere o conjunto F de todas as funções f : A → {0, 1}, então definimos
ão
χ : P(A) → F,
como sendo
1 se a ∈ B
aç
χ(B)(x) =
0 se a ∈
6 B
Clamente, toda função f assume valor 1 em B = f −1 (1), então f = χ f −1 (1) . Portanto χ é sobrejetora e
naturalmente injetora. De onde se define
]P(A) := 2]A .
or
Teorema 13.4 Se ]A = m e ]B = n então existem 2n·m relações de A em B.
ab
Demonstração. O resultado segue de observar que cada relação se corresponde biunívocamente com um
elemento do conjunto de partes e, neste caso, o conjunto de partes tem 2nm elementos.
2
Corolário 13.4 Se ]A = m então existem 2m relações em A.
el
Demonstração. Aplicando o teorema anterior para B = A temos que n = m de onde existem 2m×m relações, isto
2
é 2m relações em A.
Teorema 13.5 Sejam n, m ∈ N. Se A é um conjunto tal que ]A = n e B é um conjunto tal que ]B = m então
](A × B) = n · m.
Demonstração. Seja B um conjunto com m elementos. Vamos mostrar que para todo conjunto A tal que ]A = n
temos que ](A × B) = n · m. Para isto construimos a função proposicional
0/ × B = 0/ e ]0/ × B = 0 · m = 0.
A = {a1 , . . . , ak , ak+1 }
escrevemos A = A1 ∪ Ak em que
A1 = {a1 , . . . , ak }, A2 = {ak+1 }
• u = (al , b) com l ≤ k e b ∈ B . Denotamos por à aao conjuntos constituído por estes elementos. Temos
](A1 × B) = k · m por hipótese indutiva.
• u = (ak+1 , b) com b ∈ B . Denotamos por B̃ ao conjuntos constituído por estes elementos. Temos
]B̃ = ]B = m, por construção.
Observamos que à ∩ B̃ = 0,portanto
/
](A × B) = ]Ã + ]B̃
= ](A1 × B) + ]B
= k·m+m
ão
= (k + 1) · m.
de onde k + 1 ∈ M e, pelo princípio de indução, M = N.
Corolário 13.5 Sejam α e β números cardinais finitos, então o produto entre eles tem como resultado o
aç
valor do produto como números naturais α · β .
De maneira análoga a demonstração para o caso de dois conjuntos, podemos mostrar o seguinte resul-
tado
](A1 × · · · × Ak ) = n1 · n2 · · · · nk .
or
Teorema 13.6 Sejam {A1 , . . . , Ak } uma familia de conjuntos tais que ]Ai = ni para todo i = 1 . . . k então
Demonstração. Provamos o resultado por indução em k. Primeiramente lembramos que se A é um conjunto tal
ab
que ]A = n e B é um conjunto tal que ]B = m então ](A × B) = n · m.
Considere agora a função proposicional
temos
](A1 × · · · × Ak × Ak+1 ) = ]((A1 × · · · × Ak ) × Ak+1 )
= ](A1 × · · · × Ak ) × ](Ak+1 )
= (n1 · n2 · · · · nk ) · nk+1
= n1 · n2 · · · · nk · nk+1 .
Pelo princípio de indução temos que P(k) vale para todo k ∈ N.
Teorema 13.7 Sejam n, m ∈ N. Se A é um conjunto tal que ]A = n e B é um conjunto tal que ]B = m então
](B)](A) = mn .
A = {a1 , . . . , an } e B = {b1 , b2 , . . . , bn }.
Denotamos por
F(A, B) = { f : A → B, função}.
105
Observamos que uma função f : A → B é construída associar por uma única seta um elemento de A com um
elemento de B, portanto para cada ai ∈ A temos m possibilidades para f (ai ). Assim temos mn possibilidades
diferentes de escolher a função f .
Corolário 13.6 Sejam α e β números cardinais finitos, então o número cardinal β α é o mesmo número que
o número natural que é resultado de fazer β α .
Temos dividido os conjuntos em finitos e infinitos. No entanto, para distinguir um pouco melhor entre a
ão
cardinalidade dos conjuntos que são infinitos introduzimos o conceito de enumerabilidade.
Definição 13.3 Um conjunto A é dito enumerável se existe uma função injetora f : A → N. Em particular
• se a função for sobrejetora sobre um conjunto finito de N então A é dito enumerável finito.
• se a função for sobrejetora sobre um subconjunto de N com a mesma cardinalidade que N então A é
dito enumerável infinito.
aç
Os conjuntos que não admitem uma tal função são chamados de não enumeráveis.
..
.
f (A) = a0
f (A\{a0 }) = a1
..
.
or
ab
f (A\{a0 , . . . , an }) = an+1
.. ..
. .
Como A é infinito temos que cada
el
A\{a0 , . . . , an } 6= 0/
e como f é uma função escolha an 6∈ {a0 , . . . , an−1 }. O conjunto B = {ai , i ∈ N} é então enumerável. Agora seja
g : N → B definida por g(n) = an .
Em
Teorema 13.8 — Princípio da Partição. Sejam A e B dois conjuntos. Se existe f : A → B sobrejetora então
existe g : B → A injetora.
Demonstração. Utilizamos o axioma da escolha. Construimos uma partição de A dada pelos conjuntos
f −1 (b) ∀ b ∈ B.
g(b) = ab ∈ f −1 (b).
Exemplo 13.3 • O conjunto dos números naturais é enumerável infinito de forma natural.
106 Capítulo 13. Cardinalidade de conjuntos
ão
Proposição 13.3 O conjunto Z dos números inteiros é enumerável.
aç
3−n se n < 0
Como 2 e 3 são coprimos temos que
2a 6= 3b ∀ a, b ∈ N\{0}.
é injetora.
or
Da mesma forma, se prova que 2a = 2b se, e somente se, a = b e que 3a = 3b se, e somente se a = b. Portanto f
Demonstração. • Seja C ⊂ A subconjunto. Como A é enumerável temos que existe uma função injetora
f : A → N. Em particular, f |A : A → N é injetora. De onde segue que C é enumerável.
• Como A é enumerável existe g : A → N tal que g é injetora. Então g ◦ f : U → N é injetora. Portanto U é
enumerável.
• Seja f : A → V é sobrejetora e considere a função injetora g : A → N dada pela enumerabilidade de A.
Em
é enumerável.
ão
[
F : N×N → Ai ,
i∈N
definida por
F(n, m) = fn (m),
aç
S
é claramente sobrejetora. De onde segue que i∈N Ai é enumerável.
Q∗+ =
é enumerável
na
b
or
, (a, b) ∈ (Z\{0}) × (Z\{0}), a > 0, b > 0
o
p
f = 2 p 3q .
q
Observamos que se
Em
p p1
f =f
q q1
então 2 p 3q = 2 p1 3q1 e, pelo teorema fundamental da aritmética, temos que p1 = p e q1 = q e, portanto
p p1
= .
q q1
Logo, f é injetora e, portanto Q∗+ é enumerável.
Exemplo 13.4 Para ilustrar um pouco o contra-intuitivo dos conjuntos infinitos temos o experimento mental
chamado de "Hotel de Hilbert". Neste experimento considera-se um hotel com infinitos quartos (tantos quartos
como números naturais), no qual todos os quartos contêm um hóspede. Desta forma o hotel está lotado. Ao
chegar um novo hóspede que deseja se hospedar no hotel, o recepcionista consegue acomoda-lo pedindo a cada
hospede do quarto n ir para o quarto n + 1, ficando assim o quarto 1 livre. Mais ainda, se cada hóspede ir do
quarto n ao quarto 2n podemos deixar livre um número infinito de hóspedes.
Claramente isto só pode acontecer pois o conjunto de quartos é infinito, pois se fosse finito a pessoa que
ocupa o último quarto não teria como se movimentar.
Pelo que vimos acima, para conjuntos infinitos, a noção de cardinalidade é um pouco delicada e pode ser
ão
pouco intuitiva. A definição diz que para mostrar que dois conjuntos tem a mesma cardinalidade devemos
construir uma função bijetora. No entanto, construir a tal função bijetora pode ser una tarefa um tanto complicada.
Nesse sentido o teorema de Cantor-Bernstein-Schröder simplifica o problema.
Exemplo 13.5 Considere os conjuntos A = (0, 1] e B = (1, 2) ∪ (3, 4]. Considere
aç
f :A→B f (x) = x + 3
x−1
2 se x ∈ (1, 2)
g:B→A g(x) = x−2
2 se x ∈ (3, 4)
ab
Como vimos os conjuntos finitos tem associado um número cardinal que é igual ao número n ∈ N com a
mesma cardinalidade embora "número cardinal" e "número natural" sejam dois conceitos diferentes, não ha
problema em denotar os dois números da mesma forma. Neste caso o número cardinal é chamado de número
cardinal finito. Os números cardinais dos conjuntos infinitos são camados de infinitos ou números cardinais
el
transfinitos. Como vimos o conjunto dos números cardinais formam um conjunto ordenado (utilizando funções
injetoras e bijetoras) e, mais ainda há um resultado de tricotomia, isto é, dados dois números cardinais a e b se
cumple uma das seguintes
a < b, a = b, a > b.
Em
A cardinalidade dos naturais é denotada por ℵ0 (Aleph 0). Os conjuntos enumeráveis infinitos tem
cardinalidade ℵ0 pelo teorema de Cantor-Bernstein-Schröder. De fato, por um lado sabemos que f : A → N é
injetora. Como A é infinito, então a função é sobrejetora sobre um conjunto com a mesma cardinalidade de N,
de onde construímos uma função injetora g : N → A.
Vimos que tanto os números inteiros como os racionais tem a mesma cardinalidade e igual a ℵ0 e, portanto,
são enumeráveis. Sempre é possível construir conjuntos de cardinalidade maior. Desta forma temos os sucessores
de ℵ0 são denotados por ℵ1 = s(ℵ0 ), ℵ2 = s(ℵ1 ) . . ..
Por outro lado, veremos depois que os reais terão cardinalidade c, que é chamada de cardinalidade do
contínuo, e que satisfaz ℵ0 < c = 2ℵ0 .
Existe uma hipótese, chamada de Hipótese do contínuo que diz que não há número cardinal, isto é número
que indique a quantidade de elementos do conjunto, entre as cardinalidades ℵ0 e 2ℵ0 , isto é ℵ1 = c. Observamos
também que foi mostrado que essa hipótese não pode ser demonstrada nem refutada dentro da teoria de conjuntos
de Zermelo-Fraenkel.
Também é sabido que há conjuntos com cardinalidade maior que o contínuo, por exemplo, o conjunto P(R)
tem cardinalidade 2c > c.
De modo geral temos as seguintes relações entre as cardinalidades
• ℵℵ 0
0 =c
n
• cn = 2ℵ0 = 2n×ℵ0 = 2ℵ0
ℵ0 ℵ = 2ℵ0 ×ℵ0 = 2ℵ0
• cℵ0 = 2 0
109
c
• cc = 2ℵ0 = 2ℵ0 ×c = 2c .
Para mais detalhes sobre número cardinais, sua aritmética e demais pode ser conjultado o trabalho W.
Sierpinski, Cardinal and ordinal numbers-PWN, Warsaw (1965).
Exemplo 13.6 • O conjunto P dos números naturais pares com o 0 e o conjunto I dos naturais ímpares
tem a mesma cardinalidade. De fato f : P → I dada por f (p) = p + 1 é injetora e g : I → P dada por
g(p) = p + 1 também é injetora, agora pelo teorema de Cantor-Bernstein-Schröder existe um bijeção entre
I e P.
• O intervalo A = (−1, 1) e o conjunto dos números reais tem a mesma cardinalidade. Podemos argumentar
pelo teorema de Cantor-Bernstein-Schröder. No entanto vamos construir a bijeção. De fato, considere
ão
f : A → R dada por
x
f (x) =
1 − x2
Observamos que
aç
(
0 se a = 0
f −1 (a) = √
−1+ 1+4·a2
2·a se a 6= 0.
pois, se a = 0 então f ◦ f −1
√(0) = f (0) = 0 e se a 6= 0 então
f ◦ f −1 (a) =
De forma similar,
−1 + 1 + 4 · a2
2·a
−1 +
q
·
1− 1+
1
√
1− 1+4·a2
a
1 + 4 · (1−a
2
or
= a.
2·a2
ab
2 )2
f −1 ◦ f (a) = a = a.
2 · 1−a 2
temos o resultado.
• Podemos mostrar que (0, 1) × (0, 1) tem a mesma cardinalidade de R2 . Utilizando o teorema de Cantor-
Bernstein-Schröder e as funções injetoras f : (0, 1) × (0, 1) → R2 e g : R2 → (0, 1) × (0, 1) dadas por
√ p !
2 · x − 1 + 1 + 4 · x 2 2 · y − 1 + 1 + 4 · y2
f (x, y) = (x, y) e g(x, y) = ,
4·x 4·y
• O conjunto (0, 1) × (0, 1) tem a mesma cardinalidade que (0, 1). Por um lado temos função injetora
f : (0, 1) → (0, 1) × (0, 1) dada por
f (0, a1 a2 a3 a4 . . .) = (0, a1 a3 a5 . . . , 0, a2 a4 a6 . . .),
e por outro lado g : (0, 1) × (0, 1) → (0, 1) definida por
g(0, a1 a2 a3 . . . , 0, b1 b2 b3 . . .) = 0, a1 b1 a2 b2 a3 b3 . . . ,
é também injetora.
• Da mesma forma podemos mostrar que para Rn a cardinalidade é c.
Fechamos o capítulo com uuma consequência do axioma daregularidade. Para isto precisamos de uma
definição prévia.
110 Capítulo 13. Cardinalidade de conjuntos
Definição 13.4 Considere uma familia de conjuntos {Ai , i ∈ I} com I ⊂ N. Dizemos que Ai é uma cadeia
descendente se
Ai ⊂ A j ∀ j<i
para todo i ∈ I.
ão
Demonstração. Se existe uma tal cadeia. Então defina f : N → A = ∪Ai dada por f (i) = Ai . Considere Img( f )
e F = { f (n), n ∈ N}.
Pelo axioma da regularidade existe B ∈ F tal que B ∩ F = 0.
/ No entanto B = f (k) pois é um elemento de B
e B ⊂ f (k − 1) de onde B = f (k) ∩ F, de onde B não pode ser disjunto de F, o que é uma contradição. Portanto
aç
não existe tal cadeia.
or
ab
el
Em
ão
14. Números Inteiros
aç
or
Temos construído até agora os número naturais. No entanto o conjunto dos naturais, como conjunto numérico,
não é completo o suficiente no seguinte sentido: De forma geral, procuramos um conjunto de números A munido
ab
de operações soma (+) e produto ( · ) tal que se a0 , a1 , . . . an , b ∈ A então a função proposicional do tipo
polinomial, isto é, da forma
P(x) = ”x ∈ A, a0 + a1 · x + · · · + an · xn = b.”
el
(a, b) ∼ (c, d) ⇔ a + d = b + c
ão
Z = N × N/ ∼
aç
b > a ⇒ b = a+n ∈ N ⇒ (a, b) ∈ [(a, b)] = [(0, n)].
Passamos agora a definir as operações de soma e produto entre números inteiros. A soma de números inteiros
é a operação + : Z × Z → Z definida por
Em
Obs. A operação soma nos números inteiros não é igual a operação soma nos números naturais. A notação correta
teria um simbolo para cada operação, então seria +Z : Z × Z → Z definida por
Como a notação fica muito sobrecarregada, deixamos a interpretação a cargo do leitor e subentendida ao
contexto.
É fácil ver que a soma, está bem definida, isto é não depende da escolha dos representantes. De fato se
então,
(a + c) + (b0 + d 0 ) = (b + d) + (a0 + c0 )
e portanto,
Mais ainda, temos que a soma nos Inteiros generaliza a soma nos naturais. De fato, observamos que se m ≤ n
são números naturais, e a = n + m e b + m = n então
ão
Proposição 14.1 Sejam a, b, c números em Z. Então
• a + b = b + a (comutatividade).
• a + (b + c) = (a + b) + c (associatividade).
• Existe um único elemento 0 = [(0, 0)] ∈ Z tal que a + 0 = a para todo a ∈ Z (existência de elemento
aç
neutro).
• Para todo a ∈ Z existe −a ∈ Z tal que a + (−a) = 0 (existência de elemento inverso).
• Se a + b = a + c Então b = c. (cancelamento na adição).
Demonstração. Sejam
•
a + b = [(a1 , a2 )] + [(b1 , b2 )]
or
a = [(a1 , a2 )] b = [(b1 , b2 )] e c = [(c1 , c2 )]
ab
= [(a1 + b1 , a2 + b2 )]
= [(b1 + a1 , b2 + a2 )]
= b + a.
•
el
0 = 0+k = k
a − b = a + (−b)
Os inteiros munidos da operação soma formam uma estrutura algébrica particular que passamos a descrever.
Definição 14.2 Seja G um conjunto e ? : G × G → G uma operação binária definida sobre G. O par ordenado
(G, ? ) é um grupo se são satisfeitas os seguintes axiomas:
• Associatividade: Quaisquer elementos a, b, c ∈ G temos (a ? b) ? c = a ? (b ? c)
• Existência do elemento neutro: Existe um elemento e ∈ G tal que e ? a = a ? e = a
• Existência do elemento simétrico: Para qualquer elemento a ∈ G, existe outro elemento a0 ∈ G, tal que,
ão
a ? a0 = a0 ? a = e, onde e é o elemento neutro previamente mencionado.
Mais ainda, se para todos a, b ∈ G temos a comutatividade, isto é, que a ? b = b ? a o grupo é dito abeliano.
Corolário 14.1 O conjunto dos números inteiros munidos da operação soma, isto é (Z, +), é um grupo
aç
abeliano.
Assim como acontece com a soma, podemos fazer com o produto. O produto de números inteiros · : Z × Z →
então
n = [(a, b)] e m = [(c, d)]
or
Z está definida em função da soma e da multiplicação nos números naturais da seguinte forma: se
ab
n · m = [(a · c + b · d, a · d + b · c)].
Obs. Novamente, aqui a operação produto nos números inteiros não é igual a operação produto nos números
el
naturais. A notação correta teria um simbolo para cada operação, então seria seria ·Z : Z × Z → Z definida
por
n ·Z m = [(a ·N c +N b ·N d, a ·N d +N b ·N c)].
Como a notação fica muito sobrecarregada, deixamos a interpretação a cargo do leitor e subentendida ao
Em
contexto.
então
a + b0 = b + a0 ⇒ ca + cb0 = cb + ca0
a + b0 = b + a0 ⇒ db + da0 = da + db0 .
ão
n · (-m) = [(n, 0)] + [(0, m)] = [(0, n · m)] = [(0, a)] = -a
(-n) · m = [(0, n)] · [(m, 0)] = [(0, n · m)] = [(0, a)] = -a
(-n) · (-m) = [(0, n)] · [(0, m)] = [(n + m, 0)] = a.
aç
n · (-m) = (-n) · m = -a.
Demonstração. Sejam
el
•
a · b = [(a1 · b1 + a2 · b2 , a1 · b2 + b1 · a2 )]
= [(b1 · a1 + b2 · a2 , b1 · a2 + a1 · b2 )]
Em
= b · a.
•
a · (b · c) = [(a1 , a2 )] · [(b1 · c1 + b2 · c2 , b1 · c2 + b2 · c1 )]
= [(a1 · (b1 · c1 + b2 · c2 ) + a2 · (b1 · c2 + b2 · c1 ), a1 · (b1 · c2 + b2 · c1 ) + a2 · (b1 · c1 + b2 · c2 ))]
= [(a1 · b1 + a2 · b2 , a1 · b2 + b1 · a2 )] · [(c1 , c2 )]
= (a · b) · c.
• Existe 1 = [(1, 0)] ∈ Z tal que
a · 1 = [(a · 1 + 0 · b, a · 0 + 1 · b)]
= [(a, b)]
= a.
•
a · (b + c) = [(a1 , a2 )] · [(b1 + c1 , b2 + c2 )]
= [(a1 · (b1 + c1 ) + a2 · (b2 + c2 ), a2 · (b1 + c1 ) + a1 · (b2 + c2 ))]
= [(a1 · b1 + a1 · c1 + a2 · b2 + a2 · c2 , a2 · b1 + a2 · c1 + a1 · b2 + a1 · c2 )]
= [(a1 · b1 + a2 · b2 , a1 · b2 + a2 · b1 )]
+[(a1 · c1 + a2 · c2 , a2 · c1 + a1 · c2 )]
= (a · b) + (a · c).
116 Capítulo 14. Números Inteiros
•
a · b = a · c ⇒ [(a1 · b1 + a2 · b2 , a1 · b2 + b1 · a2 )]
= [(a1 · c1 + a2 · c2 , a1 · c2 + c1 · a2 )]
⇒ ((a1 · b1 + a2 · b2 ) · (a1 · c1 + a2 · c2 )
+(a1 · b2 + b1 · a2 ) · (a1 · c2 + c1 · a2 )
= (a1 · b1 + a2 · b2 ) · (a1 · c2 + c1 · a2 )
+(a1 · b2 + b1 · a2 ) · (a1 · c1 + a2 · c2 )
⇒ (b1 · c1 + b2 · c2 ) = (b2 · c1 + b1 · c2 ) (cancelamento nos naturais)
ão
⇒ b = c.
O conjunto dos números inteiros munidos com a soma e o produto tem uma estrutura algébrica que passamos
a descrever de forma geral.
aç
Definição 14.3 Considere um conjunto A com um elemento 0 ∈ A e duas operações binárias
+ : A×A → A · : A×A → A
Corolário 14.2 O conjunto dos números inteiros munidos das operações soma e produto, isto é (Z, +, · ), é
um Anel.
el
P(x) = ”x ∈ Z, x + a = b”,
Em
• ≤ é reflexiva: seja [(a, b)] ∈ Z então a + b ≤ a + b de onde [(a, b)] ≤ [(a, b)]
• ≤ é antisimétrica: sejam [(a, b)], [(c, d)] ∈ Z tais que [(a, b)] ≤ [(c, d)] e [(c, d)] ≤ [(a, b)], então
ão
(a + f + p + q) + d + c = (a + d + p) + ( f + c + q)
= b+c+e+d
= (b + e) + (c + d) → a + f ≤ b + e.
e, portanto [(a, b)] ≤ [(e, f )].
aç
Vejamos que esta relação é compatível com a que conhecemos usualmente para Z. Sejam m, n ∈ N. Então
-n ≤ m pois [(0, n)] ≤ [(m, 0)],
se m ≤ n ⇒ m ≤ n pois [(n, 0)] ≤ [(m, 0)],
se m ≤ n ⇒ or
-n ≤ -m pois [(0, n)] ≤ [(0, m)].
Mais ainda podemos mostrar que
a ≤ b ⇒ a+c ≤ b+c
ab
a≤b e 0 ≤ c ⇒ a · c ≤ b · c.
Em particular dizemos que
a<b ⇔ (a ≤ b) ∧ (a 6= b).
el
Teorema 14.2 — Tricotomia dos Inteiros. Sejam a, b números em Z então ocorre uma das seguintes
situações a = b ou a < b ou b < a.
Demonstração. Provamos por contradição. Para isto assuma que a 6= b e que a < b e b < a simultáneamente.
Em
Demonstração. Utilizamos o fato de que, para todo a ∈ Z sempre existe n ∈ N tal que se
ão
a) Se a > 0 e b > 0 então
a · b = [(n, 0)] · [(m, 0)]
= [(n · m, 0)] > 0
b) Se a < 0 e b < 0
aç
a · b = [(0, n)] · [(0, m)]
= [(n · m, 0)] > 0
c) Se a > 0 e b < 0
a · b = [(n, 0)] · [(0, m)]
= [(0, n · m)] > 0 or
Idetificamos naturalmente os Naturais como um subconjunto dos inteiros pela seguinte função injetora
ab
f : N → Z, f (n) = [(n, 0)] ∈ Z
Embora os Naturais admitam cota inferior, eles não admitem cota superior em Z como mostra o seguinte
resultado.
Teorema 14.4 O conjunto N não admite cota superior em Z.
∃ z ∈ Z, ∀ n ∈ N, n ≤ z
119
∀ z ∈ Z, ∃ n ∈ N, z < n.
Portanto, mostramos que para todo z ∈ Z temos que existe um natural n tal que z < n de onde segue que N não
pode admitir cota superior.
Claramente, se z ≤ 0 então existe 1 ∈ N tal que z < 1. Se z > 0 então z ∈ N e, portanto o seu sucessor,
s(z) ∈ N de onde segue que existe o natural s(z) tal que z < s(z).
ão
Teorema 14.5 — Princípio da boa ordem. • Seja A ⊂ N um conjunto não vazio então A possui ele-
mento mínimo.
• Seja A ⊂ Z um conjunto não vazio e limitado inferiormente, então A possui elemento mínimo.
aç
• Para os Naturais considere o conjunto
B = {n ∈ N, n ≤ a, ∀ a ∈ A}.
B = N.
or
B 6= N portanto existe um k ∈ B tal que k + 1 6∈ B pois, caso contrário, o princípio de indução garante que
A0 = {a − α, a ∈ A} ⊂ N.
el
Pelo princípio da boa ordem de N (item anterior) temos que A0 possui elemento mínimo α 0 ∈ A0 . Então
existe a0 ∈ A tal que α 0 = a0 − α de onde m = α 0 + α ∈ A e, mais ainda, é um mínimo de A. De fato se
a ∈ A então α ≤< a − α e α + α 0 ∈ A, de onde α + α 0 ≤ a.
Em
e, portanto m2 ∈ A e é menor do que m portanto m não pode ser mínimo. Então m = 1 e é o mínimo e
máximo elemento de A, portanto A = {1}.
• Seja A = {x ∈ Z, a < x ≤ a + 1/}. Aqui a + 1 ∈ A de onde segue que A 6= 0./ Também temos que A está
limitado inferiormente por a. Pelo princípio da boa ordem, A possui elemento mínimo m ∈ A e, portanto,
0 < m − a ≤ 1.
aç
or
O objetivo desta seção é dar uma ideia rápida sobre o algoritmo da divisão nos números inteiros e suas aplicações.
Começamos com a definição.
ab
Definição 15.1 Dados a, b ∈ Z com a 6= 0. Dizemos que a|b (a divide a b) se existe c ∈ Z tal que b = a · c.
Mais ainda, neste caso, dizemos que b é um múltiplo de a.
a = 1 · a, a = 1·a e 0 = a · 0.
a = p·b e b = q·c
então
a = p · b = p · q · c = (p · q) · c.
Portanto c|a.
• Sabemos que existem inteiros p, q tais que
c = p·a e d = q·b
então
c · d = (p · a) · (q · b) = (a · b) · (q · p)
portanto a · b|c · d.
122 Capítulo 15. Divisibilidade
• Provamos uma implicação pois a outra é similar. Da hipótese temos que existem inteiros p, q tais que
c+d = a· p e c = a·q
então
d = a · p − a · q = a · (p − q).
de onde segue que a|d.
• Sejam a, b ∈ N. Se b 6= 0 e a|b então existe p ∈ Z tal que a = p · b. Como a, b > 0 temos que p > 0
portanto, p ≥ 1 de onde
ão
a = a · 1 ≤ p · a = b.
Exemplo 15.1 Sejam a, b ∈ Z e n ∈ N então
aç
• (a − b)|(an − bn ).
Provamos o resultado por indução. Seja
P(n) = ”(a − b)|(an − bn )”
e M o domínio de verdade de P. Observamos que 0 ∈ M pois a0 − b0 = 0 e (a − b)|0.
Assuma que k ∈ M, isto é
. Como
ak − bk = p · (a − b)
or
ab
ak+1 − bk+1 = (a − b) · ak + b · (ak − bk )
= (ak + p · b) · (a − b).
Portanto k + 1 ∈ M e, pelo princípio de indução, M = N.
• (a + b)|(a2·n+1 + b2·n+1 ).
Provamos o resultado por indução. Seja
el
. Como
a2·k+3 − b2·k+3 = (a2 − b2 )a2·k+1 + b2 · (a2·k+1 + b2·k+1 )
= (a2·k + p · b2 ) · (a + b).
Portanto k + 1 ∈ M e, pelo princípio de indução, M = N.
• a + b|a2·n − b2·n .
Provamos o resultado por indução. Seja
P(n) = ”(a + b)|(a2·n − b2·n )”
e M o domínio de verdade de P. Observamos que 0 ∈ M pois a0 − b0 = 0 e a + b|0.
Assuma que k ∈ M, isto é
a2·k + b2·k = p · (a − b)
. Como
a2·k+2 − b2·k+2 = (a2 − b2 )a2·k + b2 · (a2·k − b2·k+1 )
= [(a2·k · (a − b)) + p · b2 ] · (a + b).
Portanto k + 1 ∈ M e, pelo princípio de indução, M = N.
123
Definição 15.2 Um número p ∈ N\{0, 1} é dito primo se sus únicos divisores são 1 e ele mesmo.
Teorema 15.1 — Fudamental da Aritmética. Todo número natural maior do que 1 é primo ou se escreve
de modo único, a menos de uma ordem nos seus fatores, como um produto de primos.
Demonstração. Utilizamos o princípio de indução. Seja P(n) a função proposicional sobre N definida por
P(n) = ”n + 2 é primo ou se escreve de modo único, a menos de uma ordem nos seus fatores,
ão
como um produto de primos”
Seja M o seu domínio de verdade, então 0 ∈ M pois 2 é primo.
Assuma que k ∈ M e vejamos o que acontece com k + 1. Se k + 1 for primo, não temos nada a provar. Se
k + 1 não for primo então existem p, q ∈ N tais que 1 < p, q < k + 1 satisfazendo k + 1 = p · q. Como sabemos
que q, p ∈ M podemos escrever, de forma única,
aç
p = p1 · · · pr q = q1 · · · ql .
Então k + 1 = p1 · · · pr · q1 · · · ql . Vejamos agora que a escrita é única. Para assuma que existem duas escritas de
primos
Teorema 15.2 — Euclides. O conjunto formado pelos números primos não é finito.
Demonstração. Mostramos pelo método do absurdo ou contradição. Assuma que se A é o conjunto formado por
todos os números primos, então ]A = k ∈ N, denotamos por
Em
A = {p1 , . . . , pk }
aos elementos de A de forma tal que pi < pi+1 para todo i. Considere o número
a = (p1 · p2 · · · pk ) + 1
Claramente a > pk e pi 6 |a para todo i ≤ k pois pi 6 |1 então a so tem como divisor a 1 e a, portanto é primo o que
é uma contradição.
Teorema 15.3 Sejam a, b dois números naturais com 0 < a < b. Existem dois únicos naturais q, r tais que
b = a·q+r e 0 ≤ r < a.
A = {b − a · k, k ∈ N} ∩ N
Se a|b então r = 0 não temos nada a provar. Se a 6 |b então r 6= a. Assuma que r > a então existe c ∈ N tal
que c + a = r e, consequêntemente,
c = b − (q + 1) · a
a · q + r = b = a · q0 + r0
ão
para naturais q, q0 , r, r0 tais que 0 ≤ r ≤ r0 < a Então
a · (q − q0 ) = r0 − r.
aç
Corolário 15.1 Dados dois números naturais a, b com 1 < a < b, existe um natural n tal que
n · a ≤ b ≤ (n + 1) · b
or
Demonstração. Do algoritmo da divisão, temos que existe n ∈ N tal que
b = n·a+r
ab
com 0 ≤ r < a. Portanto
n · a ≤ b ≤ n · a + r ≤ n · a + a = (n + 1) · a.
el
• (0, a) = a
• (1, a) = 1
• (a, a) = a
• a|b se, e somente se, a = (a, b).
De fato se d = (a, b) então d|a, de onde a = (a, b). A outra implicação é imediata da definição.
Definição 15.4 Dois números a, b ∈ N\{0} são ditos primos entre si se (a, b) = 1.
A = {s = d · n, n ∈ Z} e B = {s = m · a + n · b, m, n ∈ Z},
são iguais.
Demonstração. Observamos que todo elemento de x ∈ B é divisível por d, portanto x = d · p para algum p ∈ Z.
Então B ⊂ A.
Por outro lado seja
c = min(B ∩ N),
125
então
c = n · a + m · b.
Portanto d|c.
Por outro lado, se c|z para todo z ∈ B. De fato, se
z = n1 · a + m1 · b,
ão
z = p·c+r com 0 ≤ r < c,
temos que
aç
0 ≤ r = (n1 − n) · a + (m1 − m) · b < c.
De onde segue que r = 0 pela minimalidade de c. Então c|a e c|b de onde c|d. Portanto c = d e d ∈ B e
A ⊂ B.
(a, b) = d = m · a + n · b
x = p·m e y = p · n.
Estas equações são conhecidas como equações diofantinas, pode ser mostrado que todo par da forma
também é solução de
a · x + b · y = k.
a·x+b·y = k
Lema 15.1 Sejam a, b, n ∈ N com a < n · a < b. Se existe (a, b − n · a) então (a, b) existe e
Demonstração. Seja d = (a, b − n · a), como d|a e d|b − n · a e b = b − n · a + n · a segue que d é dividor comum
de a e b então c|(a, b). Se c = (a, b) então c|b − n · a portanto c|d. Decorre disto que c = d.
126 Capítulo 15. Divisibilidade
A seguir apresentamos uma técnica para determinar o máximo divisor comúm de dois números naturais a e
b. Assuma, sem perder generalidade que a < b.
Se a|b então (a, b) = a. Caso a 6 |b então existe q1 , r1 ∈ N tais que
b = a · q1 + r1 .
Então
• se r1 |a então
ão
• se r1 6 |a então existem q2 , r2 ∈ N
a = r1 · q2 + r2 r2 < r1 .
aç
Novamente temos duas posibilidades
– se r2 |r1 então
r1 = r2 · q3 + r3 r3 < r2 .
or
Novamente temos duas posibilidades e o procedimento pode continuar um número finito de vezes
ab
pois o conjunto dos = {r1 , r2 , r3 , · · · } ⊂ N com ri < ri+1 e portanto possui um mínimo, pelo princípio
da boa ordem. Logo, existe um k tal que rk ∈ R e rk |rk−1 . De onde segue que
(a, b) = rk .
• (a + 1, a2·n+1 − 1) = (a + 1, a − 1).
De fato, utilizando que (a + 1)|(a2·n − 1) temos
(a + 1, a2·n+1 − 1) = (a + 1, a · (a2·n − 1) + (a − 1)
= (a + 1, a − 1).
• (a + 1, a2·n + 1)= (a + 1, 2).
De fato, utilizando que (a + 1)|(a2·n + 1) temos
(a + 1, a2·n + 1) = (a + 1, (a2·n − 1) + 2)
= (a + 1, 2).
a2·n −1
• a + 1, a+1 = (a + 1, 2 · n).
Escrevemos
a2·n − 1
= a2·n−1 − a2·n−2 + a2·n−3 + · · · − a2 + a − 1
a+1
= (a2·n−1 + 1) − (a2·n−2 − 1) + (a2·n−3 + 1) + · · · − (a2 − 1) + (a + 1) − 2 · n
e utilizamos que
e utilizamos que
a + 1|(a2·k − 1) e a + 1|(a2·k+1 + 1),
ão
para obter o resultado.
aç
de fato, como (a, b) = 1 temos que existe s, t ∈ R tal que
s · (a − b) + (t + s) · b = 1
s·a+t ·b = 1 ⇒
s · (a + b) + (t − s) · b = 1
−b
• a − b, aa−b
n n
= (a − b, n).
or
de onde (a − b, b) = 1 e (a + b, b) = 1 de onde segue o resultado.
ab
De fato, observamos que
an − bn
= an−1 + an−2 · b + · · · + a · bn−2 + bn−1
a−b
el
E utilizamos que
a − b|(ak − bk ),
Em
a2·n+1 + b2·n+1
= a2·n − a2·n−1 · b + · · · − a · b2·n−1 + b2·n
a+b
= (a2·n − b2·n ) − (a2·n−1 · b + b2·n ) + · · · − (a · b2·n−1 + b2·n−1 ) + (2 · n + 1) · b2·n .
E utilizamos que
a + b|(a2·k − b2·k ) e a + b|(a2·k+1 + b2·k+1 ),
junto a (a + b, bk ) = 1 para obter
a2·n+1 + b2·n+1
a + b, = (a + b, (2 · n + 1) · b2·n ) = (a + b, 2 · n + 1).
a+b
Em
el
ab
or
aç
ão
ão
16. Números Racionais
aç
or
Com o conjunto dos números inteiros, garantimos que todas as funções proposicionais da forma
ab
P(x) = ”x ∈ Z, x + a = b.”
para a, b ∈ Z, tem domínio de verdade não vazio. No entanto, por exemplo, a função proposicional
P(x) = ”x ∈ N, 2 · x = 7.”
el
é de equivalênca.
a·d · f = b·c· f e b · c · f = b · d · e.
ão
Este conjunto recebe o nome de conjunto dos números racionais.
Assim como fizemos com os naturais e inteiros, definimos as operações soma e produto.
Definição 16.3 Sejam ab e dc dois números racionais. Definimos a soma + : Q × Q → Q por
aç
a c a·d +b·c
+ = .
b d b·d
e o produto · : Q × Q → Q por
a c a·c
· =
c d b·d or
Obs. As operações soma e produto nos números racionais não são as mesmas que as operações soma e produto
ab
nos números inteiros. A notação correta teria um simbolo para cada operação, então seria algo da forma
+Q : Q × Q → Q dada por
a c a ·Z d +Z b ·Z c
+Q = .
b d b ·Z d
e ·Q : Q × Q → Q
el
a c a ·Z c
·Q =
c d b ·Z d
Como a notação fica muito sobrecarregada, deixamos a interpretação a cargo do leitor e subentendida ao
contexto.
Em
Mostramos agora que as definições de soma e produto são boas e não dependem do representante da classe
escolhido para computá-las. De fato, assuma que
a a0
= isto é a · c0 = c · a0 ,
c c0
e
b b0
= isto é b · d 0 = d · b0 .
d d0
Calculamos
a0 c0 a0 · d 0 + b0 · c0 a0 c0 a0 · c0
+ = · = .
b0 d 0 b0 · d 0 c0 d 0 b0 · d 0
Como
(a · d + b · c) · b0 · d 0 = a · d · b0 · d 0 + b · c · b0 · d 0
= a0 · b · d · d 0 + c0 · d · b · b0
= (a0 · d 0 + c0 · b0 ) · b · d.
131
Temos
a0 · d 0 + b0 · c0 a · d + b · c
= .
b0 · d 0 b·d
De forma similar, como
a0 · c0 · b · d = a0 · b · c0 · d
= a · b0 · c · d 0
= a · c · b0 · d 0 .
ão
Temos
a·c a0 · c0
= 0 0.
b·d b ·d
aç
O fato de ter mostrado que o resultado é independente do representante da classe escolhido para fazer a conta nos
permite fazer qualquer operação utilizando convenientemente qualquer representante da classe de equivalência
que define o número.
Obs.
• A classe 0
1
0 a a
+ =
1 b b
satisfaz
e
0 a 0 0
· = = .
1 b b 1
or
ab
1
• a classe 1 satisfaz
1 a a
· = .
1 b b
a −a
• Se ∈ Q então ∈ Q satisfaz
el
b b
a −a 0 0
+ = = .
b b b 1
a a 0 b
• Se b ∈ Q tal que b 6= 1 então a 6= 0 e, portanto, está definido a ∈ Q. Observamos que
Em
a b 1
· = .
b a 1
dizemos neste caso que
a −1 b
= .
b a
a 0 p
Mais ainda definimos, para b 6= 1 e q ∈Q
p a p a −1 p b
÷ = · = · .
q b q b q a
Demonstração. Sejam
a1 b1 c1
a= , b= e c= .
a2 b2 c2
•
a1 · b2 + b1 · a2
ão
a+b =
a2 · b2
b1 · a2 + a1 · b2
=
b2 · a2
= b + a.
•
aç
a1 b1 · c2 + c1 · b2
a + (b + c) = +
a2 b2 · c2
a1 · (b2 · c2 ) + (b1 · c2 + c1 · b2 ) · a2
=
a2 · c2 · b2
(a1 · b2 + b1 · a2 ) · c2 + (b2 · a2 ) · c1
• Seja 0 = 0
∈ Q, então
=
=
a2 · b2
or
a2 · c2 · b2
a1 · b2 + b1 · a2 c1
+ = (a + b) + c.
c2
ab
1
0 a1
0+a = +
1 a2
0 · a2 + a1 · 1
=
1 · a2
a1
el
= .
a2
Assuma que existe outro elemento d com a mesma propriedade, então
d = d + 0 = 0.
Portanto 0 é o único elemento com esta propriedade.
Em
• Considere a ∈ Q e defina
−a1
−a = ,
a2
então
a1 · a2 + (−a1 ) · a2 0
a + (−a) = = = 0.
a2 · a2 a2 · a2
•
a1 · b2 + b1 · a2 a1 · c2 + c1 · a2
a+b = a+c ⇒ =
a2 · b2 a2 · c2
⇒ (a1 · b2 + b1 · a2 ) · (a2 · c2 ) = (a2 · b2 ) · (a1 · c2 + c1 · a2 )
⇒ (b1 · a2 ) · (a2 · c2 ) = (a2 · b2 ) · (c1 · a2 ) (Cancelamento em Z)
⇒ b1 · c2 = b2 · c1 (Cancelamento em Z)
⇒ b = c.
•
a1 · b1
a·b =
a2 · b2
b1 · a1
=
b2 · a2
= b·a
133
•
a1 b1 · c1
a · (b · c) = ·
a2 b2 · c2
a1 · b1 · c1
=
a2 · b2 · c2
a1 · b1 c1
= ·
a2 · b2 c2
= (a · b) · c
• Seja a ∈ Q tal que a 6= 0 então a1 6= 0 portanto defina
ão
a2
a−1 =
a1
então
a1 · a2
a · a−1 =
aç
= 1.
a2 · a1
1
• Claramente se 1 = 1 então, para todo a ∈ Q temos
1 · a1 a1
1·a = = = a.
1 · a2 a2 or
Se d é outro elemento de Q com a propriedade d · a = a para todo a ∈ Q temos
d = d · 1 = 1.
ab
Portanto o 1 é único.
•
a1 b1 · c2 + c1 · b2
a · (b + c) = ·
a2 b2 · c2
a1 · (b1 · c2 + c1 · b2 )
el
= ·
a2 · b2 · c2
a1 · b1 · c2 + a1 · c1 · b2 )
= ·
a2 · b2 · c2
a1 · b1 a1 · c1
= · +
a2 · b2 a2 · c2
Em
= (a · b) + (a · c)
• Se a 6= 0 então
a1 · b1 a1 · c1
a·b = a·c ⇒ =
a2 · b2 a2 · c2
⇒ (a1 · b1 ) · (a2 · c2 ) = (a1 · c1 ) · (a2 · c2 )
⇒ (b1 · c2 ) = (c1 · b2 ) (cancelamento em Z)
⇒ b = c.
Os números racionais munidos com a soma e o produto tem uma estrutura algébrica que passamos a descrever
de forma geral.
Definição 16.4 Considere um conjunto A com elementos 0 e 1 em A e duas operações binárias
+ : A×A → A · : A×A → A
0 = 0 · b0 · a0 = a · b · b0 · a0 = 1.
ão
o que é uma contradição. Portanto a · b 6= 0.
aç
Corolário 16.2 O conjunto dos números racionais munidos das operações soma e produto, isto é (Q, +, · ),
é um Corpo.
a −1 b
= .
or
Obs. Se a, b ∈ Z tal que a 6= 0 e b 6= 0 temos definido
ab
b a
Observamos que, para r ∈ N\{0} temos
r r
a −1 b
=
b a
el
br
=
ar
h a r i−1
= .
b
Definimos então
Em
a −r r
a −1
= .
b b
Definição 16.5 Sejam ab e dc dois números racionais. Dizemos que ba é menor e igual a dc e denotamos por
a c
≤ se a · d ≤ b · c.
b d
Mais ainda, dizemos que
a c a c a c
< ⇔ ≤ ∧ 6= .
b d b d b d
Vejamos que, de fato, a relação definida acima é uma relação de ordem.
• Refexividade: Seja ab ∈ Q então a · b ≤ a · b temos que ab ≤ ba .
135
ão
b d
• Sejam ba , dc , ef ∈ Q e assuma que
a c c e
≤ ∧ ≤ .
b d d f
aç
Então
(a · d ≤ b · c) ∧ (c · f ≤ e · d),
para d, c, f inteiros positivos. Portanto,
a· f ·d ≤ b·c· f
≤ b·e·d
De onde segue que
a
≤ .
e
⇒
or
a · f ≤ b · e.
ab
b f
Obs.
Dados a, b ∈ Q, denotamos
• a ≥ b se, e somente se, b ≤ a.
el
Definição 16.6 Seja (A, ≤) um conjunto munido de uma ordem total. Se a ≤ b e a 6= b então dizemos que a
é menor que b e denotamos por a < b.
Em
Definição 16.7 Um corpo ordenado é um corpo A munido de uma relação de ordem total ≤ que satisfaz
• Para todo a, b, c ∈ A se a < b então a + c < b + c.
• Para todo a, b ∈ A se 0 < a e 0 < b então 0 < a · b.
Corolário 16.3 Seja (A, +, ·, 0, 1, <) um corpo ordenado e a ∈ A tal que a 6= 0 então 0 < a2 .
Demonstração. Sejam
ão
p1 p2 p3
a= b= e c=
q1 q2 q3
aç
a ≤ b ⇔ p1 · q2 ≤ p2 · q1
⇔ p1 · q2 · q3 ≤ p2 · q1 · q3
⇔ p1 · q2 · q3 + q1 · q2 · p3 ≤ p2 · q1 · q3 + q1 · q2 · p3 (propieddade dos inteiros)
⇔ (p1 · q3 + q1 · p3 ) · q2 ≤ (p2 · q3 + q2 · p3 ) · q1
⇔
p1 · q3 + q1 · p3
p1 p3
q1 · q3
≤
p2 p3
or
⇔ (p1 · q3 + q1 · p3 ) · q2 · q3 ≤ (p2 · q3 + q2 · p3 ) · q1 · q3
p2 · q3 + q2 · p3
q2 · q3
ab
⇔ + ≤ + .
q1 q3 q2 q3
• Como c ≥ 0 temos que p3 ≥ 0. Então
a ≤ b ⇒ p1 · q2 ≤ p2 · q1
⇒ p1 · q2 · p3 · q3 ≤ p2 · q1 · p3 · q3 (pois p3 ≥ 0 e q3 ≥ 0)
p1 · p3 p2 · p3
el
⇒ ≤
q1 · q3 q2 · q3
p1 p3 p2 p3
⇒ · ≤ · .
q1 q3 q2 q3
• Como c ≤ 0 temos que p3 ≤ 0. Então
a ≤ b ⇒ p1 · q2 ≤ p2 · q1
Em
⇒ p2 · q1 · p3 · q3 ≤ p1 · q2 · p3 · q3 (pois p3 ≤ 0 e q3 ≥ 0)
p2 · p3 p1 · p3
⇒ ≤
q2 · q3 q1 · q3
p2 p3 p1 p3
⇒ · ≤ · .
q2 q3 q1 q3
Demonstração. Sejam
p1 p2
a= e b= ,
q1 q2
P(x) = ”x ∈ Q, a · x + b = c”.
ão
tem por domínio de verdade M = {[c + (-b)] · a−1 .}.
aç
Obs. Os números inteiros podem ser vistos como um subconjunto dos números racionais da seguinte forma:
defina f : Z → Q por
a
f (a) = .
1
é fácil ver que
f (a + b) = f (a) + f (b) e
or
f (a · b) = f (a) · f (b).
desta forma dizemos que Z ⊂ Q. Mais ainda, temos que se a ≤ b em Z então f (a) ≤ f (b).
ab
Lema 16.1 Todo número racional positivo pode ser escrito, de forma única, como a = mn com (m, n) = 1.
p p1
a= =
q q1
com (p1 , q1 ) = 1. Se
p1 p2
Em
= ⇒ p1 · q2 = p2 · q1 .
q1 q2
com (p1 , q1 ) = 1 e (p2 , q2 ) = 1 Como (p1 , q1 ) = 1 temos que p1 |p2 e p2 = c1 · p1 . Da misma forma q2 = c2 · q1 .
Mas então cc12 = 1 de onde segue que c1 = c2 = 1.
p
Obs. Vamos dizer que um número racional 0 ≤ a está escrito na forma irredutível quando escrito na forma q em
que (p, q) = 1.
Lema 16.2 — densidade dos racionais. Sejam a e b dois números racionais tais que a < b, então existe um
número racional c tal que a < c < b.
Demonstração. Escrevemos
p1 p2
a= e b= .
q1 q2
p1 · q2 < p2 · q1 .
138 Capítulo 16. Números Racionais
Definimos
p2 · q1 + p1 · q2
c= .
2 · q1 · q2
claramente c ∈ Q. Observamos que
2 · q1 · q2 · p1 = q1 · q2 · p1 + q1 · q2 · p1
< q1 · p2 · q1 + q1 · q2 · p1
= (p2 · q1 + p1 · q2 ) · q1 ⇒ a < c,
ão
e
(p2 · q1 + p1 · q2 ) · q2 = p2 · q1 · q2 + p1 · q2 · q2
< p2 · q1 · q2 + q1 · p2 · q2
= (2 · q1 · q2 ) ⇒ c < b,
aç
obtendo assim o pedido.
Teorema 16.4 O conjunto dos números racionais, com a ordem definida acima, não é um conjunto bem
ordenado. or
Demonstração. Vamos mostrar que existem subconjuntos não vazios de Q, limitados inferiormente e sem
elemento mínimo. Para isto considere
ab
A = {a ∈ Q, 1 < 2 · a}
Claramente
• A 6= 0/ pois, por exemplo, a = 1 ∈ A.
• para todo a ∈ A temos que 0 < a.
el
• a = 12 é limite inferior de A.
Assuma A admite elemento mínimo m ∈ A e assuma que
p
m= (p, q) = 1.
q
Em
1
Então, como é limite inferior, temos que temos que
2
1 p 1 1 1 p p
< ⇒ < + < .
2 q 2 2 2 q q
Portanto
1 1 p 1 1 p p
+ ∈A e + < ,
2 2 q 2 2 q q
o que é uma contradição.
Teorema 16.5 O conjunto Q, com a ordem acima, não possui elemento máximo nem mínimo.
p
Demonstração. Assuma que existe um elemento mínimo m em Q. Então m = q com p < 0 e q > 0. Como
0 < 12 temos que 21 · qp ∈ Q e
2 p p
· <
1 q q
o que é uma contradição. De forma similar se mostra que não tem máximo.
ão
17. Números Reais
aç
or
Temos visto na seção anterior a construção dos número racionais. Com os números racionais temos que o
domínio de verdade as proposições da forma
ab
P(x) = ”x ∈ N, a · x + b = c.”
para a, b, c ∈ Q tem domínio de verdade vazio em Q. No entanto, sobre os racionais ainda temos funções
proposicionais do tipo polinomial com domínio de verdade vazio como mostra o seguinte exemplo.
el
P(x) = ”x ∈ R, x2 = 2.”
a
tem domínio de verdade vazio. De fato, se b ∈ Q está no domínio, então temos que
Em
a2 = 2 · b2 .
Do lado esquerdo o 2 deve aparecer um numero par de vezes e, no entanto, do lado direito deve aparecer um
número impar de vezes. O que é uma contradição pois teríamos duas decomposições diferentes em primos de a2 .
Mais ainda, o conjunto A = {x ∈ Q, x2 < 2} é um conjunto limitado, pois é fácil ver que −2 < x < 2 para
todo x ∈ A e não admite supremo. De fato se existir um supremo m ∈ Q então m > 1, pois por exemplo
Portanto
2 < m2 + 2 · m + 1.
Também m2 < 2. De fato, se m2 ≥ 2 temos que, como m ∈ Q sabemos, pelo visto acima, que m2 6= 2. Se m2 > 2
temos que m 6∈ A. Defina
δ = (2 − m2 ) · 2−1 · m−1
140 Capítulo 17. Números Reais
n = m+δ,
então n < m e
n2 = m2 + 2 · δ · m + δ 2
= m2 + (2 − m2 ) + δ 2
= 2+δ2
ão
> 2
ε = (2 − m2 ) · (2 · m + 1)−1
aç
⇒ 0 < ε < 1.
Defina
r = m+ε
satisfaz m < r e
r2 = m2 + 2 · ε · m + ε 2
= m2 + (ε + 2 · m) · ε
or
ab
< m2 + (1 + 2 · m) · ε
= m2 + (2 − m2 ) = 2.
Então, r ∈ A e r ≤ m o que√é também uma contradição. De onde seque que A não admite supremo. Observe que
o supremo, no caso, seria 2 que não pertence a Q.
el
É por este tipo de situações que continuamos ampliar nosso conjunto numérico de forma tal que, neste novo
conjunto numérico, as funções proposicionais sobre os racionais estejam contempladas e o seu domínio de
verdade seja não vazio.
Para definir os números reais vamos a proceder de uma forma diferente ao que foi feito anteriormente. Tanto
Em
para definir os números inteiros quanto os racionais considerávamos subconjuntos de um produto cartesiano de
dois conjuntos. Para a construção dos números reais vamos a considerar classes de equivalência de funções.
Começamos com a função valor absoluto | |Q : Q → Q que é definida por
a se 0 ≤ a
|a|Q =
−a se a < 0.
Obs. Tiramos o subíndice | |Q da função para não carregar a notação e a passamos a denotar por | |.
ão
Definição 17.1 Uma sequência de números racionais é uma função x : N → Q. Denotamos à sequência por
(xn )n∈N e por xn = x(n).
Definição 17.2 Seja (xn )n∈N uma sequência de números racionais. Dizemos que:
aç
• A sequência (xn )n∈N é de Cauchy se: para todo ε ∈ Q com ε > 0 existe um n0 ∈ N tal que se n0 < n, m
então |xm − xn | ≤ ε.
Denotamos por CQ ao conjunto das sequências de números racionais que são de Cauchy.
• A sequência (xn )n∈N converge a um número a ∈ Q se: para todo ε ∈ Q com 0 < ε existe um n0 ∈ N tal
que se n0 < n então |a − xn | ≤ ε.
or
Obs. Seja (xn )n∈N uma sequência então, como vimos antes é uma função x : N → Q. Assim uma sequência pode
ser vista como um processo que vai assumindo valores a medida que aumenta n.
ab
• Se a sequência é de Cauchy significa que seus termos ficam arbitráriamente próximos uns dos outros
a medida que n é maior. Isto, em matemática, é descrito dizendo que para qualquer ε > 0, podendo
ser arbitráriamente pequeno, temos que a distância entre os seus elementos x(n) e x(m) para n, m
suficientemente grandes, será menor que ε. Mais ainda, para cada ε > 0 podemos achar um n0 tal que
|xn0 − xm | < ε
el
para todo m > n0 . Ou seja, todos os termos sucessivos estão, no máximo a uma distância menor que
ε < 0.
Se um processo físico é descrito por uma sequência (por exemplo a variação de temperatura T (n) no
instante t = n), o fato que a sequência de eventos seja de Cauchy permite ver que o processo tem uma certa
previsibilidade pois a partir do valor que assume em um ponto, os outros vão estar perto deste. O fato da
sequência ser convergente, permite dizer que os valores vão estar muito perto do valor ao qual converge
(por exemplo T0 ).
Teorema 17.1 Seja (xn )n∈N uma sequência convergente a um número a ∈ Q. Então ela é de Cauchy.
Demonstração. Seja 0 < ε um número racional. Como a sequência (xn )n∈N converge a a temos que, para 12 · ε
existe um n0 tal que se n0 < n então |a − xn | ≤ 21 · ε. Sejam n0 < m, n então observamos que
|xn − xm | = |xn − a + a − xm |
≤ |xn − a| + |xm − a| ≤
1 1
≤ · ε + · ε = ε.
2 2
Portanto para todo ε ∈ Q tal que ε > 0 existe um n0 ∈ N tal que se n0 < n, m então |xm − xn | ≤ ε.
142 Capítulo 17. Números Reais
xn = (−1)n
ão
|xn − xn+(2m+1) | ≥ 1.
Como não é uma sequência de Cauchy, ela não pode ser convergente.
• Dado q ∈ Q, considere a sequência (xn )n∈N em que
aç
xn = q ∀ n ∈ N,
Ou seja x é a função constante. Claramente para todo ε > 0 existe n0 = 1 tal que m, n > 1 temos
|xn − xm | = 0 < ε,
or
portanto, é uma sequência de Cauchy e, mais ainda convergente pois para todo ε > 0 existe n0 = 1 tal que
se n > n0 então
ab
|xn − q| = 0 < ε.
• Uma sequência de Cauchy que não é convergente em Q pode ser construída como segue: Seja a ∈ (0, 1)
um número irracional, então
a = 0, a1 a2 . . . an an+1 . . .
el
Então
xn = 0, a1 . . . an .
Em
1
|xn − xm | < < ε.
10min{n,m}
Observamos que a sequência não converge em Q. De fato, se o limite for q ∈ Q tem um número máximo
n de cassas decimais ou é uma dízima periódica. Em qualquer dos dois casos haverá sempre um m
suficientemente grande em que xm − q 6= 0 pela construção do xn é pelo fato de a ser irracional. Portanto
chegamos a uma contradição. De onde segue que a sequência não é convergente.
• Considere a sequência (xn )n∈N em que
2 2
xn = 1 +
n
Observamos que ela é de Cauchy e é convergente. Mostramos cara uma por separado embora, por causa
do teorema acima, seja suficiente mostrar que é convergente para termos que é de Cauchy.
143
ão
e
2 2
2 2+ + < 12
n m
Portanto
aç
12
|xm − xn | <
m
Seja ε > 0, então sempre existe um número natural n0 tal que
n0 > 12 · ε −1 . or
Assim, dado ε > 0 existe um numero natural n0 > 10 · ε −1 tal que se n, m > n0 temos
12 12
ab
|xn − xm | ≤ < < ε.
min{n, m} n0
De onde a sequência é de Cauchy.
Vamos mostrar que a sequência é convergente. Observamos que, da forma de xn quanto maior for n o
termo 2n está mais perto de 0, desta forma, quando n for a infinito este irá para 0 e xn ficará mais perto de 1.
el
Como A = {|x0 |, . . . , |xn0 |, |xn0 +1 − 1|, |xn0 +1 + 1|} é um conjunto finito temos que existe N = max A. De
onde segue o resultado.
144 Capítulo 17. Números Reais
ão
1 1
|xn − xm | < · M −1 · ε |yn − ym | < My−1 · ε
2 x 2
para todo n0 < n, m e Mx e My como no primeiro item. Considere a sequência (zn )n∈N definida por
zn = xn · yn então
|zn − zm | = |xn · yn − xm · yn + xm · yn − xm · ym |
aç
= |xn − xm | · |yn | + |xm | · |yn − ym |
≤ |xn − xm | · My + Mx · |yn − ym | < ε.
para todo n, m ∈ N e portanto, é de Cauchy.
R = CQ / ∼ .
Denotamos à clase de (xn )n∈N por [xn ]n∈N . Então um número real a é uma classe de equivalência
a = [xn ]n∈N
a2 = p · b2 .
145
ão
t + s = [xn + yn ]n∈N .
e o produto · : R × R → R por
t · s = [xn · yn ]n∈N
aç
Obs. As operações soma e produto nos números reais não são as mesmas que as operações soma e produto
nos números racionais. A notação correta teria um simbolo para cada operação, então seria algo da forma
+R : R × R → R por
t +R s = [xn +Q yn ]n∈N .
e ·R : R × R → R por
t ·R s = [xn ·Q yn ]n∈N
or
ab
Como a notação fica muito sobrecarregada, deixamos a interpretação a cargo do leitor e subentendida ao
contexto.
Outra observação é que, a diferença dos número inteiros e racionais, a fórmula para computar as operações
não é feito por uma equação simples envolvendo um número finito de elementos. Elas requerem um número
infinito de passos e elementos.
el
Mostramos agora que as definições de soma e produto são boas e não dependem do representante da classe
escolhido para computá-las. De fato, assuma que
[xn ]n∈N = [xn0 ]n∈N e [yn ]n∈N = [y0n ]n∈N
isto é,
Em
De forma similar, temos que dado ε > 0 existe um n0 tal que se n0 < n então
1 1
|xn − xn0 | < · M −1
0 ·ε e |yn − y0n | < · M −1 · ε
2 y 2 x
Portanto
|xn · yn − xn0 · y0n | ≤ |xn · yn − xn · y0n | + |xn · y0n − xn0 · y0n |
= |xn | · |yn − y0n | + |xn − xn0 | · |y0n |
= Mx · |yn − y0n | + |xn − xn0 | · My .
De onde segue que [xn · yn ]n∈N = [xn0 · y0n ]n∈N .
146 Capítulo 17. Números Reais
definidas por
1 2
xn = yn = 1 +
n n+2
Observamos que as duas sequências são de Cauchy. De fato, dado ε > 0 existe n0 ∈ N, n0 · ε > 4 tal que se
ão
m, n > n0 temos
2
|xn − xm | < <ε
min{n, m}
e
aç
4
|yn − ym | < < ε.
min{n + 2, m + 2}
Então, pelo resultado anterior, as sequências (un )n∈N e (vn )n∈N definidas por
e
1
un = xn + yn = 1 + +
2
n n+2
or
1 2
ab
vn = xn · yn = + ,
n n · (n + 2)
são de Cauchy.
el
Obs.
• A classe 0 = [xn ]n∈N tal que xn = 0 para todo n ∈ N satisfaz
0+t = 0 e 0·t = 0 ∀t ∈ R.
Em
1·t = t ∀t ∈ R.
t + (−t) = 0.
• Se t = [xn ]n∈N tal que t 6= 0 temos que existe N ∈ N tal que xn 6= 0 para todo n ∈ N tal que n > N.
De fato, como a sequência é de Cauchy temos que para cada k ∈ N existe nk tal que |xn − xm | < 1k e
xnk > 1k . Como a sequência não converge para 0 existe um K ∈ N tal que |xn | > K1 para todo n > nK
pois, caso contrário, teríamos que sempre existe xm < 1k para todo k de onde segue que a sequência
converge para 0 o que é uma contradição.
Mais ainda temos que xm > 0 ou xm < 0 para todo m > nK . De fato, se xnK > 0 então, como a
1
sequência é de Cauchy temos que existe ε = 2·K tal que
1 1 1 1
xm = xm − xn + xn > + xm − xn > − = .
K K 2·K 2·K
De forma similar se mostra se xm < 0.
• Se t = [xn ]n∈N tal que t 6= 0, definimos t −1 = [y−1 −1
n ]n∈N onde yn = 0 para n ≤ n0 e yn = xn para todo
n > n0 satisfaz
t · t −1 = 1.
147
Podemos mostrar que R munido da soma e o produto definido acima satisfaz o seguinte resultado.
Proposição 17.2 Sejam a, b, c números em R. Então
• a + b = b + a (comutatividade).
• a + (b + c) = (a + b) + c (associatividade).
• Existe 0 ∈ R tal que a + 0 = a para todo a ∈ R (existência de elemento neutro).
• Para todo a ∈ R existe −a ∈ R tal que a + (−a) = 0 (existência de elemento inverso).
• Se a + b = a + c Então b = c. (cancelamento na adição).
• a · b = b · a (comutatividade).
ão
• a · (b · c) = (a · b) · c (associatividade).
• Existe 1 tal que a · 1 = a (existência de elemento neutro).
• Para todo a ∈ R tal que a 6= 0 existe a−1 ∈ R tal que a · a−1 = 1.
• a · (b + c) = (a · b) + (a · c) (distributividade).
• Se a 6= 0 e a · b = a · c. Então b = c (cancelamento no produto).
aç
Portanto os número reais formam um corpo.
Demonstração. Sejam
números em R. Então
•
a + b = [an + bn ]n∈N
or
ab
= [bn + an ]n∈N
= b+a
•
a + (b + c) = [an ]n∈N + [bn + cn ]n∈N
el
• Seja
−a = [−an ]n∈N
| − an − (−am )| = |an − am |
portanto, se (an )n∈N é de Cauchy, então (−an )n∈N também é de Cauchy. Agora
a + (−a) = [an + (−an )]n∈N
= [0]n∈N = 0.
148 Capítulo 17. Números Reais
• Como
isto é
ão
(bn − cn )n∈N converge a 0.
Portanto b = c. Então b = c.
•
a · b = [an · bn ]n∈N
aç
= [bn · an ]n∈N
= b·a
•
a · (b · c) = [an ]n∈N · [bn · cn ]n∈N
= [an · (bn · cn )]n∈N
= [(an · bn ) · cn ]n∈N
= [(an · bn )]n∈N · [cn ]n∈N
or
ab
= (a · b) + c.
• Seja
a · 1 = [an · 1]n∈N
= [an ]n∈N
= a.
• Se a 6= 0 então existe ε0 para todo n0 ∈ N tal que n0 < n e |an | ≥ ε0 . Portanto existe a−1
n para todo n > n0 .
Em
Se n, m > n0 então
|an − am | 1
|αn − αm | = < 2 |an − am |,
|an · am | ε0
portanto (αn )n∈N é de Cauchy. Mais ainda, para todo n > n0 temos
an · αn = 1
portanto
a · a−1 = 1.
149
•
a · (b + c) = [an · (bn + cn )]n∈N
= [(an · bn ) + (an · cn )]n∈N
= [(an · bn )]n∈N + [(an · cn )]n∈N
= (a · b) + (a · c).
• Se a · b = a · c então
ão
de onde
Assuma que a 6= 0 isto é (an ) não converge a 0. Então existe ε0 para todo n ∈ N tal que n0 < n e |an | ≥ ε0 .
aç
Portanto, para todo n > n0 temos
el
Obs. Os números racionais podem ser vistos como um subconjunto dos números reais da seguinte forma: defina
f : Q → R por
desta forma dizemos que Q ⊂ R. Mais ainda, temos que se a ≤ b em Q então f (a) ≤ f (b).
Obs. Assim como foi feito para os números racionais definimos para a ∈ R e n ∈ N
n termos
n z }| {
a = a · a · · · a,
ar · as = ar+s ,
para todo r, s ∈ Z.
150 Capítulo 17. Números Reais
Definição 17.5 Dado s ∈ R dizemos que 0 ≤ s se s = [xn ]n∈N existe um n0 ∈ N tal que se n0 < n então
0 ≤ xn .
Dados dois números reais s e t dizemos que s ≤ t se
0 ≤ t + (−s).
s<t ⇔ (s ≤ t) ∧ (s 6= t).
ão
Obs. Dados t, s ∈ R, denotamos
• t ≥ s se, e somente se, s ≤ t.
• t > s se, e somente se, st.
aç
Proposição 17.3 Sejam a, b, e c números reais
• a ≤ b se, e somente se, a + c ≤ b + c para todo c ∈ R
• Se a ≤ b e 0 ≤ c então a · c ≤ b · c
• Se a ≤ b e c ≤ 0 então b · c ≤ a · c.
0 ≤ (yn − xn ) e 0 ≤ zn .
portanto
0 ≤ (yn − xn ) e 0 ≤ −zn .
portanto
Demonstração. Somente resta mostrar que se a = [xn ]n∈N e b = [yn ]n∈N são números reais, então a ≤ b ou b ≤ a.
Para isto observamos que se a 6= b então a sequência (zn )n∈N definida por
zn = (xn − yn )
não converge para 0. Vamos mostrar que existe n0 ∈ N tal que para todo n > n0 temos
0 < xn − yn ou 0 < yn − xn .
ão
Caso isto acontece, temos de forma natural, que a < b ou b < c.
Como (zn )n∈N é de Cauchy e não converge para 0 temos que existe ε0 ∈ Q tal que para todo n0 ∈ N temos
que n > n0 e |zn | ≥ ε0 .
Seja ε1 < ε0 então existe um n1 ∈ N tal que se n, m são maiores que n1 temos |zn − zm | < ε1 . Assuma que
n2 > n1 e que zn1 > 0 então zn1 > ε0 > ε1 . Portanto
aç
−ε1 < zm − zn < ε1 ⇒ −ε1 + zn < zm < ε1 + zn
⇒ 0 < zm .
de onde b ≤ a. Caso zn1 < 0 então, por um argumento similar chegamos a
zm < 0 ⇒ a ≤ b,
Demonstração. Segue do fato de R ser um corpo bem ordenado. De fato se a = [xn ]n∈N e b = [yn ]n∈N tais que
a 6= b então (xn − yn )n∈N não converge para 0. Portanto existe um n0 ∈ N tal que
el
0 < xn − yn ou 0 < yn − xn ,
Obs. Os números racionais podem ser vistos como um subconjunto dos números reais da seguinte forma: defina
f : Q → R por
desta forma dizemos que Q ⊂ R. Mais ainda, temos que se a ≤ b em Q então f (a) ≤ f (b).
Temos assim as seguintes cadeias de inclussões
N ⊂ Z ⊂ Q ⊂ R.
Obs. Daremos aqui uma demonstração eurística do resultado de Cantor. Para mais detalhes consultar o livro:
Robert Roth Stoll - Set theory and logic. Dover. ( 1979)
152 Capítulo 17. Números Reais
Demonstração. Vamos mostrar qua a cardinalidade de P(N) é igual a cardinalidade de R e portanto R não
pode ser enumerável pois isso garante a existência de uma função sobrejetora de N → P(N) o que, pelo que
vimos no teorema 13.1, não pode acontecer.
Primeiramente considere f : R → P(Q) a função definida por
f (x) = {q ∈ Q, q ≤ x}
Observamos que se x 6= y então, por exemplo x < y. Da densidade dos racionais, temos que existe um racional
q1 tal que
ão
x < q1 < y ⇒ f (x) 6= f (y).
Portanto f é injetora. De onde segue que a cardinalidade de ]R é menor ou igual que a cardinalidade de ]P(Q)
Como os racionais são enumeráveis, temos que ]P(Q) é menor ou igual que ]P(N).
Definimos a função injetora g : P(N) → R da seguinte forma: Para A ⊂ N definimos χA : N → {0, 1} por
aç
1 se n ∈ A
χA (n) =
0 se n 6∈ A
e definimos
g(A) =
χA (0)
10
+···+
χA (n)
10n
+···
or
Claramente se A 6= B então g(A) 6= g(B) e portanto a função é injetora. De onde segue que ]P(N) é menor
igual que ]R. De onde segue que todas as cardinalidades são iguais.
ab
Vamos a provar agora uma propriedade dos números reais que, basicamente, diz que um número real não
pode ser infinitamente grande ou infinitamente pequeno.
Teorema 17.3 — Propriedade arquimediana. Dados a e b número positivos em R existe n ∈ N tal que
el
b < n·a
Demonstração. Sejam a = [xn ]n∈N e b = [yn ]n∈N números positivos. Então existe n0 ∈ N tal que
0 < xn e 0 < yn ,
Em
para todo n > n0 . Observamos que o que temos que mostrar é o seguinte:
Existem m, n ∈ N tal que se k > n então yk < m · xk .
Assuma que isto não acontece, então para todo m, n temos k > n e yk ≥ m · xk .
Seja ε ∈ Q tal que ε > 0.
• Como (yn )n∈N é de Cauchy, temos que existe R ∈ Q, R = qp com (p, q) = 1, tal que
0 < yn < R
• Como (xn )n∈N é de Cauchy, existe n1 > n0 tal que se n, m > 0 então
1
|xn − xm | < ε
2
q1
Como ε = q2 , o algoritmo da divisão garante a existência de um l ∈ N tal que
1 1
2 · p · q2 < l · q · q1 ⇒ · R < · ε.
l 2
Agora, dado m = l e n ∈ N com n > n1 temos que k > n1 e
1 1
0 < l · xk < yk < R ⇒ 0 < xk < ·R < ·ε
l 2
153
Estendemos a função valor absoluto aos número reais, isto é definimos | |R : R → R por
ão
a se 0 ≤ a
|a|R =
−a se a < 0.
É fácil verificar que possui as mesmas propriedades que para o caso dos racionais e que |a| < b se, e somente se
aç
−b < a < b. Mais ainda, se q1 , q2 são números racionais, então
|q1 − q2 |R = |q1 − q2 |Q ,
É por isto que tiramos o subíndice | |R da notação e denotamos a função valor absoluto por | | indistintamente se
ab
for sobre os reais ou racionais, deixando ao leitor a interpretação do contexto.
Com esta definição e o resultado anterior podemos mostrar que os numeros racionais são densos no conjunto
dos números reais.
Teorema 17.4 Dados um número real a e um número racional q, 0 < q, existe um número racional r tal que
el
|a − r| < q.
Demonstração. Seja a = [xn ]n∈N . Como (xn )n∈N é de Cauchy, dado q ∈ Q, 0 < q, existe n0 ∈ N tal que se n > n0
então |xn − xn0 | < q. Defina agora r = (yn )n∈N tal que
Em
yn = xn0 ∀ n ∈ N.
Então r ∈ Q. Como
temos
O seguinte resultado é a propriedade geométrica masi importante dos números reais e que é de grande
utilidade na análise matemática. Básicamente, o resultado garante que os números reais, como conjunto, não
tem "furos".
Teorema 17.5 Todo conjunto não vazio de R que é limitado superiormente admite elemento supremo.
Demonstração. Seja A ⊂ R um conjunto não vazio e seja M uma cota superior de A. Seja a ∈ A definimos as
sequências (un )n∈N e (vn )n∈N pelo seguinte processo recursivo ou jogo (veremos recorrências mais adiante no
texto):
154 Capítulo 17. Números Reais
• u0 = M e v0 = a
• Assuma conhecido un e vn , calculamos
1
Mn = · (un + vn )
2
então
– se Mn é conta superior, então un+1 = Mn e vn+1 = vn .
– se Mn não é cota superior, então un+1 = un e vn+1 = Mn .
Observamos que
ão
a) para cada n vn não é cota superior.
b)
un+1 − vn+1 = Mn − vn
1
= = · (un + vn ) − vn
aç
2
1
= · (un − vn )
2
1
≤ |M − a|.
2n
c) por definição,
1
|un − un+1 | ≤ |un−1 − un |
2
or
d)
ab
|un − un+k | ≤ (|un − un+1 | + |un+1 − un+2 | + · · · + |un+k−1 − un+k |)
1 1
= |un − un+1 | + · |un − un+1 | + · · · + k−1 |un − un+1 |
2 2
< 2|un − un+1 |
el
2
≤ |M − a|.
2n
Para cada n consideramos qn ∈ Q tal que |un − qn | < 1n e consideramos a sequência (qn )n∈N . Seja ε > 0 e
m ∈ N tal que 1 < m3 ε e 22m |M − a| < 31 · ε ( tal m existe pela propiedade arquimediana) então
Em
portanto (qn )n∈N é de Cauchy e representa um real que chamamos de b. Mais ainda, da construção, temos
que (un )n∈N converge para b. Por outro lado
1 1
|vn − qn | ≤ |vn − un | + |qn − un | ≤ n
|M − a| +
2 n
de onde segue que (vn )n∈N converge para b.
Assuma que existe a0 ∈ A tal que b < a0 , escolhemos ε = a0 − b, e como (un )n∈N converge para b existe
um n tal que un − b < ε, portanto
un < b + ε = b + (a0 − b) = a0 ,
o que é uma contradição pois un é uma cota superior de A. Portanto b é a cota superior.
Assuma agora que b0 < b é cota superior de A, então seja ε = b − b0 . Como (vn )n∈N converge para b temos
que existe um n0 ∈ N tal que para todo n0 < n vale b0 < vn mas vn não é cota superior o que contradiz o
fato de b0 ser cota superior.
155
Obs. Com este resultado podemos ver que se b ∈ R e b > 0 então a função proposicional
P(x) = ”x ∈ R, x2 = b.”
ão
é tal que s > s̃m e s̃2m > b2 contradizendo novamente o fato de s se supremo.
aç
para k ∈ N e a2k+1 6= 0, tem domínio de verdade não vazio em R. Para demonstrar isto se utiliza a continuidade
do a função polinomial junto ao Teorema do valor intermediário (Cálculo I). Para esses dois conceitos é utilizado
fortemente a propriedade da existência de supremo.
É fácil ver que, no entanto, ainda há funções proposicionais polinomiais sobre os números reais com comínio
Q(x) = ”x ∈ R, x2 + 1 = 0”
or
de verdade vazio. De fato, por exemplo, a função proposicional
Tem domínio de verdade vazio em R. Para resolver finalmente o problema do domínio de verdade não vazio
ab
para funções proposicionais do tipo polinomial, é construído um outro conjunto numérico que é o conjunto dos
números complexos.
el
Em
Em
el
ab
or
aç
ão
ão
18. Representação decimal dos números reais
aç
or
Vimos, na seção anterior, que um número real pode ser representado por uma sequência (xn )n∈N de números
racionais. No entanto, esta representação é pouco conveniente para efeitos práticos, visto que temos que
ab
temos que especificar um conjunto enumerável de números. Para simplificar a notação surge a bem conhecida
representação decimal dos números reais.
Vamos a estudar a representação decimal dos reais não negativos, pois para os negativos basta considerar a
representação decimal do valor absoluto do número e acrecentar um sinal − na frente.
Números inteiros: Primeiramente representamos o 0 e depois o restante dos números.
el
• No caso dos inteiros positivos observamos que, o algoritmo da divisão, nos permite escrever todo número
Em
a = a0 + a1 · 10 + a2 · 102 + · · · + an · 10n
para p, q ∈ N tais que (p, q) = 1. Primeiramente vamos representar cada número da forma
a0 a1 a2 an
+ + 2 +···+ n ,
1 10 10 10
158 Capítulo 18. Representação decimal dos números reais
com
a0 ∈ N e ai ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
a0 = ”a0m . . . a00 ”
ão
a = ”a0m . . . a00 , a1 a2 . . . an ”
10k · p = b · q
aç
onde
b = b0 + b1 · 10 + · · · + br · 10r .
Então
p
q
=
=
1
10k
1
10k
·
·
10k · p
b
1
q
or
ab
a
=
10k
1 1 1 1
= br · k−r + br−1 · k−r+1 + · · · + b1 · k−1 + b0 · k .
10 10 10 10
e representamos como acima.
el
• Não existe k ∈ N tal que q divide a 10k · p. Claramente, neste caso, q 6= 10l para todo l ∈ N. Do algoritmo
da divisão temos que
p = q · a0 + r,
10m+k · r = dk · q + rk k≥0
como temos no máximo q restos possíveis. Escolhemos os menores k1 < k2 tais que rk1 = rk2 . Temos
então que
10m · r · (10k2 − 10k1 ) = q · b ⇒ 10k1 · (10k2 −k1 − 1) < b < 10m+k1 · (10k2 −k1 − 1).
Novamente, pelo algoritmo da divisão, temos que
Portanto, escrevemos
c = c0 + c1 · 10 + . . . + ck2 · 10k2 −1
159
d = d0 + d1 · 10 + · · · + dm+k1 −1 · 10m+k1 −1
Então
10m · r b d c
= = + .
q (10 2 − 10 1 ) 1 (10 2 − 10k1 )
k k k
Observamos que
c 1 c
= k · k −k .
(10k2 k
− 10 ) 10 10 1 −1
ão
1 1 2
aç
que será mostrada quando estudemos recorrências. Com esta identidade, vemos que se
e = e0 + e1 · 10 + · · · + en−1 · 10n−1
e e e e
= + 2·n + · · · + n·k + · · ·
10n − 1 10 n 10
que é escrita como dízima periódica
e
10n − 1
10
se escreve
r
= ”0, dm+k1 −1 . . . d1 d0 ck2 −1 ck2 −2 . . . c1 c0 ”.
q
Portanto
Em
p
= ”a0 , dm+k1 −1 . . . d1 d0 ck2 −1 ck2 −2 . . . c1 c0 ”.
q
Da notação acima, temos
Obs.
r b c + d · (10k2 − 10k1 ) (c + d · 10k2 ) − d · 10k1
= m k k
= =
q 10 · (10 2 − 10 1 ) 10m · (10k2 − 10k1 ) 10m · (10k2 − 10k1 )
0, dm · · · d0 ck · · · c0
d = d0 + · · · + dm · 10m e c = c0 + · · · + ck · 10k
e fazendo
(c + 10k+1 · d) − d
.
10m (10k+1 − 1)
160 Capítulo 18. Representação decimal dos números reais
19
Exemplo 18.2 Considere o número 99 : observamos que
19 < 99 < 10 · 19
Então
10 · 19 · (102 − 1) = 99 · 190
ão
190 = 99 · 1 + 91
aç
Observamos que, pelo formato do número e a notação, também poderiamos ter escrito
0, 191 = 0, 19.
Por outro lado, transformando de dízimas periódicas a número racional temos duas expressões equivalentes:
• Para o caso: 0, 191 temos
d = 1 c = 91
or
ab
de onde o número fica
(91 + 102 · 1) − 1 190
= .
10 · (102 − 1) 990
d = 0 c = 19
= .
(102 − 1) 99
Números Irracionais: Tamos visto como escrever os números inteiros e racionais na forma decimal. Já com
os irracionais isto nunca poderá ser concluido. O número irracional não, por definição é um número que não é
racional, então sua representação decimal nunca poderá ser feita pois é o trabalho de escrever um número com
infinitas casas decimais depois do 0, o máximo que podemos fazer é uma aproximação racional e escrevé-los
como
a = ”a0 , a1 . . . an . . . ”
onde cada
a j ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ∀ j ∈ N\{0}
Observamos, pelo fato de não ser racional, nunca vamos ter um a n−upla da forma
ak+1 . . . ak+n
que se repete na forma de dízimas periódicas depois da vírgula. Então não temos como simplificar de alguma
forma a notação. Em geral, a menos dos casos de raizes quadradas de números primos, ou otros racionais
161
similares) os números irracionais são nomeados por alguma letra como é o caso do número π, número e etc.
Tambem observamos que há constantes que se conhecem com um número grande de casas decimais e das quais
não se sabe se são racionais ou irracionais, por exemplo π + e ou π · e.
Se a é um irracional, com
a = ”a0 , a1 . . . an . . . ”,
ão
a0 a1 aj
a = [q j ] j∈N onde q j = + +···+ j .
1 10 10
aç
π = 3, 14159265358979323846264338327950288419716939937510
5820974944592307816406286208998628034825342117067982148
0865132823066470938446095505822317253594081284811174502
or
8410270193852110555964462294895493038196442881097566593
3446128475648233786783165271201909145648566923460348610
454326648213393607260249141273 · · ·
ab
Consulte em htt p : //www.geom.uiuc.edu/ huberty/math5337/groupe/digits.html para mais detalhes.
Para representar gráficamente os números reais vamos a utilizar uma reta, que será chamada de reta real,
sobre a qual vamos distinguir um ponto 0, que corresponde ao número 0.
el
Em
Com uma unidade de comprimento marcamos os inteiros do lado esquerdo os negativos e do lado direito os
positivos. As marcas são a múltiplos de este comprimento.
Para representar os racionais primeiramente observamos que para representar um racional qp < 1 particionamos
o segmento da reta entre 0 e 1 em q partes iguais e marcamos a prosição p. Por exemplo, representamos os
racionais 16 , 62 , 36 , 64 e 56 como segue:
162 Capítulo 18. Representação decimal dos números reais
ão
p
Agora, todo racional da forma q pode ser escrito como
p a p0
= +
aç
q 1 q
com p0 > 0. Então para representar qp particionamos o segmento da reta entre a e a + 1 em q partes e marcamos
o correspondente a marca p0 . Por exemplo os racionais 6·a+1
6 ,
6·a+2 6·a+3 6·a+4
6 , 6 , 6 e 6·a+5
6 como segue:
or
ab
el
Os números reais que não são racionais podem ser também representados exatamente por um ponto na reta.
Porém pode ser um trabalho delicado, dada a definição dos irracionais. Embora alguns casos particulares possam
ser representados utilizando argumentos de trigonometria e demais, podemos fazer uma repressentação informal
da seguinte forma: sabemos que o número irracional vai estar entre dois racionais. Então, por abuso gráfico
Em
escolhemos dois racionais que estejam arbitráriamente próximos (tanto quanto a definição do nosso gráfico
permitir) e marcamos o ponto do meio.
Por exemplo o número π: pelo visto acima ele satisfaz 314 315
100 < π < 100 e o representamos marcando um ponto
neste intervalo, por exemplo:
ão
19. Sequências e Recorrências
aç
or
Neste capítulo estudaremos com um pouco mais de detalhes as sequências de números e sua definição por meio
de recursões ou processos recursivos do tipo que utilizamos nas demonstrações de alguns dos tópicos já vistos.
ab
Começamos o capítulo generalizando as definições sobre sequências para o caso em que os números da
sequência são números reais.
Definição 19.1 • Uma sequência de números reais é uma função x : N → R. Denotamos à sequência
por (xn )n∈N e por xn = x(n).
el
• Seja (xn )n∈N uma sequência de números reais, uma subsequência é uma aplicação y : N → R obtida de
compor x com uma função m : N → N em que m(i) ≤ mi+1 , isto é y = x ◦ m. Denotamos a subsequência
por (xmk )k∈N em que mnk = (x ◦ m)(k).
• Seja (xn )n∈N uma sequência de números reais. Dizemos que:
– A sequência (xn )n∈N é de Cauchy se para todo ε ∈ R tal que ε > 0 existe um n0 ∈ N tal que se
Em
lim xn = a.
n→∞
Corolário 19.1 Seja x um número real, x = [xn ]n para (xn )n∈N uma sequência de Cauchy de números
racionais. Então, como xn ∈ Q ⊂ R pela identificação vista, temos que (xn )n∈N é uma sequência de Cauchy
de números reais que converge a x.
Demonstração. O baso de ser sequência de Cauchy segue da densidade dos racionais nos reais. De fato, para
todo ε > 0 existe um número racional ε̃ > 0 tal que ε > ε̃ > 0. Portanto, há um n0 tal que se n, m > n0 então
|xn − xm | < ε. Agora da inclusão canônica de Q ⊂ R temos que a sequência é de Cauchy.
Para cada n seja, pela densidade de Q em R o número racional yn tal que
1
|x − yn | < ,
2n
164 Capítulo 19. Sequências e Recorrências
ão
|ym − yn | < ε.
Observamos que
aç
de onde segue que
zn = |xn − yn | ∀ n ∈ N,
or
é de Cauchy e converge para 0 pois, caso contrário, existe em δ > 0 tal que para todo n ∈ N temos m > n
ab
δ < |xm − ym |
Se (xn )n∈N é uma sequência convergente de números reais, então utilizando o mesmo argumento que para
el
sequências convergentes de números racionais, podemos mostrar que ela é de Cauchy. No conjunto dos números
reais podemos ver que a volta deste resultado, isto é, se é de Cacuhcy então é convergente, também vale. Esse é
o conteúdo do proximo resultado.
Teorema 19.1 Seja (xn )n∈N uma sequência reais então ela é de Cauchy se, e somente se, é convergente .
Em
xn = [ynk ]k∈N
zn = ynk , ∀ n ∈ N.
Observamos que (zn )n∈N é uma sequência de Cauchy. De fato, se ε > 0 existe um n0 ∈ N tal que se n, m > n0
temos
1
|xn − ynk | < · ε
3
1
|xm − ym k | < ·ε
3
1
|xn − xm | < · ε
3
165
Portanto, (zn )n∈N é de Cauchy. Seja x = [zn ]n∈N . Observamos que dado ε > 0 existe um n0 ∈ N tal que se
n, m > n0 temos
1
|x − zm | < ·ε
3
1
ão
|ym
k − xm | < ·ε
3
1
|xn − xm | < ·ε
3
aç
e, portanto
|x − xn | = |x − zm | + |zm − xn |
= |x − zm | + |ym
k − xm | + |xn − xm | < ε.
Exemplo 19.1
xn =
2·n
n+1
∀ n ∈ N.
or
• Seja (xn )n∈N uma sequência reais em que
ab
Dado ε > 0 existe n0 satisfazendo n0 > 2 · ε −1 tal que se n > n0 temos
2·n
|xn − 2| =
n+1
2
=
n+1
el
2
< <ε
n0 + 1
Portanto a sequência (xn )n∈N converge a 2, de onde
lim xn = 2.
n→∞
Em
Como a sequência é convergente é de Cauchy. Seja m : N → N definida por m(n) = 3 · n + 1 então (xmn )n∈N
e uma subsequência de (xn )n∈N e está definida por
2 · m(n)
xmn =
m(n) + 1
2 · (3 · n + 1)
=
(3 · n + 1) + 1
6·n+2
= , ∀ n ∈ N.
3·m+2
• Seja (xn )n∈N uma sequência reais em que
2 n
xn = · cos · π , ∀ n ∈ N.
n+3 2
Dado ε > 0 existe n0 satisfazendo n0 > 2 · ε −1 tal que se n > n0 temos
2 n
|xn − 0| = · cos ·π
n+3 2
2
≤
n+3
2
< <ε
n0
166 Capítulo 19. Sequências e Recorrências
lim xn = 0.
n→∞
Como a sequência é convergente é de Cauchy. Seja m : N → N definida por m(n) = 4 · n então (xmn )n∈N e
uma subsequência de (xn )n∈N eestá definida por
2 m(n)
xmn = · cos ·π
m(n) + 3 2
2
= · cos (2 · π)
ão
4·n+3
2
= ∀ n ∈ N.
4·n+3
Por outro lado se k : N → N definida por k(n) = 2 · n + 1 então (xkn )n∈N e uma subsequência de (xn )n∈N e
está definida por
aç
2 k(n)
x kn = · cos ·π
k(n) + 3 2
2 2·n+1
= cos · π = 0, ∀ n ∈ N.
n+3 2
Portanto a subsequência (xkn )n∈N tem todos seus termos iguais a 0.
or
A existência de uma ordem e a tricotomia nos números reais nos permite dar a seguinte definição.
Definição 19.2 Seja (xn )n∈N uma sequência reais. Dizemos que ela é
ab
• crecente: se para todo n ∈ N temos xn < xn+1 .
• não decrecente:se para todo n ∈ N temos xn ≤ xn+1 .
• decrecente:se para todo n ∈ N temos xn+1 < xn .
• não crecente:se para todo n ∈ N temos xn+1 ≤ xn .
• monótona se ela for não crescente ou não decrescente.
el
ou, pelo menos de uma subsequência da própria sequência. Isso é o que veremos nos resultados a seguir.
Demonstração. Seja (xn )n∈N uma sequência monótona limitada. Assuma que é não decrescente (o caso não
crescente é similar)
Considere o conjunto A = {xi , i ∈ N}. Como a sequência é limitada temos que A é limitado. Portanto, pela
existência de supremo em subconjuntos limitados de R temos que existe
s = sup A.
de onde
xn = (−1)n ∀ n ∈ N.
Claramente é uma sequência que é limitada. Não é crescente nem decrescente pois
ão
y( j) = x ◦ m1 ( j) = 1 e z( j) = x ◦ m2 ( j) = −1 ∀ j∈N
aç
p
xn = 1 + n2 ∀ n ∈ N.
xn ≥ 1 e xn < xn+1 .
xn ≥ 1 e xn < xn+1 ∀n ∈ N.
el
p xn é crescente, limitada inferiormente. Mais ainda, para todo M ∈ R existe um número natural
Portanto
n0 > |M 2 − 1| tal que se m > n0 então
2
xm = 1 + m2 > 1 + n20 > M 2 ⇒ xn > M.
xn j > xn j+1 ∀ j ∈ N.
168 Capítulo 19. Sequências e Recorrências
Veremos que esta subsequência é convergente, mais ainda, veremos que a sequência original é convergente
a 0. De fato, dado ε > 0 existe um número natural n0 > ε1 tal que se n > n0 então
n
|xn − 0| =
1 + n2
1
≤
n
1
< < ε.
n0
De onde
ão
lim xn = 0.
n→∞
aç
Observamos que, como 0 ≤ n ≤ 1 + n para todo n ∈ Ntemos que 0 ≤ xn ≤ 1. De onde segue que a
sequência é limitada superiormente e inferiormente, portanto é limitada. Mais ainda, como
n2 + 2 · n < n2 + 2 · n + 1
temos que
xn < xn+1
de onde seque que a sequência é crescente.
or 1
ab
A sequência converge a 1. De fato, dado ε > 0 existe um número natural n0 satisfazendo n0 + 1 > ε tal
que se n > n0 então
1
|xn − 1| =
1+n
1
< < ε.
el
1 + n0
De onde
lim xn = 1.
n→∞
Em
Lema 19.1 Toda sequência (xn )n∈N admite uma subsequência que pode ser não decrescente ou não crescente.
Teorema 19.3 — Bolzano-Weierstrass. Toda sequência limitada tem uma subsequência convergente.
Demonstração. Seja (xn )n∈N uma sequência limitada. Pelo lema anterior existe uma subsequência monótona
que é limitada. O teorema da convergencia monótona garante que esta subsequência deve converger.
Seja (xn )n∈N uma sequência. Sabemos que xn é o valor de uma função x : N → R. No entanto existem
diferentes formas de definir os valores x(n) = xn da função. Listamos aqui alguns.
• Direta: a partir do valor de x(n) = xn .
Por exemplos a sequência (xn )n∈N dada por
ão
1
x(n) = .
n+1
• por recursão: A partir dos valores de x em {0, 1, . . . , n} obtemos o valor de x(n + 1) por uma fórmula
aç
sobre os valores conhecidos {x(0), x(1), . . . , x(n)}.
Por exemplos a sequência (xn )n∈N dada por
em construir uma sequência (xn )n∈N por meio de uma recorrência. O algoritmo é o seguinte
1- Escolha x0 ∈ Q tal que
2- Para n ≥ 1 calcule
1 −1
xn = · xn−1 + p · xn−1 .
2
Observamos que
xn2 − p = xn · xn − p
= xn (xn − p · xn−1 )
1 −1
= 2 · xn · xn − (xn + p · xn )
2
= 2 · xn · (xn − xn+1 )
ão
1 −1 2
|xn − xn+1 | = x · (xn − p)
2 n
1
= · (xn − p · xn−1 )
2
1
aç
−1
≤ · (xn − p · xn−1 )
2
1
= · (xn + xn−1 − 2xn )
2
1
≤ · |xn−1 − xn |.
xm = xm+1
2
Como consequência disto temos que se para algum m temos que
⇒ xn = xm ∀ n ≥ m.
or
Agora, utilizando indução é fácil mostrar que
ab
1 1
|xn+1 − xn | < n
|x1 − x0 | = n+1 · x0−1 (p − x02 )
2 2
e que
1
el
x0 = 1 x1 = 2, 5 x2 = 2, 05 x3 = 2, 00060975609756
x4 = 2, 00000009292229 x5 = 2 x6 = 2.
√
Então
√ 4=2
• 3
ão
x0 = 1, x1 = 2, x3 = 1, 75 x3 = 1, 73214285714286
aç
Um caso particular, sobre definição de sequências por recursão está no seguinte resultado.
Teorema 19.4 — Princípio de Recursão. Seja A um conjunto não vazio e f : An × N → A uma função.
Então existe uma única sequência x : N → A tal que
• x0 = a0 , . . . , xn−1 = an−1
• xm = f (m, xm−1 , . . . , xm−n ) para m ≥ n
or
ab
Demonstração. Para fazer a demonstração utilizamos o princício de indução. Considere a função proposicional
Seja M o domínio de verdade de P. Observamos que {0, . . . , n − 1} ⊂ M pois x0 = a0 , . . . , xn−1 = an−1 estão
el
xm+1 = f (m + 1, xm , . . . , xm−n+1 )
está definida. Portanto m + 1 ∈ M e, pelo princípio de indução xn está definida para todo n ∈ N.
Para mostrar a unicidade onsidere a função proposicional
Em
Q(n) = ”Se y(n) está definida pela recursão do enunciado então y(n) = x(n)”
Se ym = xm então
Exemplo 19.4 A sequência de Fibonacci (xn )n∈N é definida como a única sequência de números naturais tal
que
• x0 = 1 e x1 = 1.
• xn+2 = xn+1 + xn para n ≥ 3..
• Progressão aritmética. É a sequência (xn )n∈N de números reais definida pela seguinte recorrência: Dados
a, r ∈ R temos
x0 = a xn = xn−1 + r ∀n ≥ 1.
xn = a + n · r.
ão
• Progressão geométrica. É a sequência (xn )n∈N de números reais definida pela seguinte recorrência:
Dados a, r ∈ R temos
x0 = a xn = r · xn−1 ∀n ≥ 1.
aç
De forma geral, podemos ver que
xn = a · rn .
• Seja (xn )n∈N de números reais. Construimos de forma recursiva duas recorrências que são importantes de
forma geral.
– O somatório: É a sequência de números reais
!
an = ∑ xi
n
or
ab
i=0 n∈N
0 n
el
a0 = ∑ xi = x0 an = ∑ xi = an−1 + xn .
i=0 i=0
i=0
De fato, seja
n
P(n) = ” ∑ xi = x0 + x1 + · · · + xn ”,
i=0
0
∑ xi = x0 .
i=0
i-
n n
∑ c · xi = c · ∑ xi .
i=0 i=0
De fato seja
n n
P(n) = ” ∑ c · xi = c · ∑ xi ”
i=0 i=k
ão
e considere M o seu domínio de verdade. Então 0 ∈ M, pois
0 0
∑ c · xi = c · x0 = · ∑ xi .
i=0 i=0
Se n ∈ M então como
aç
n+1 n
∑ c · xi = c · xn+1 + ∑ c · xi
i=0 i=0
n
= c · xn+1 + c · ∑ xi
i=k
= c · xn+1 + ∑ xi
n
i=k
Portanto n + 1 ∈ M e, pelo princípio de indução N = N.
or
!
n+1
= c · ∑ xi .
i=0
ii-
ab
n n n
∑ (xi + yi ) = ∑ xi + ∑ yi .
i=0 i=0 i=0
De fato seja
el
n n n
P(n) = ” ∑ (xi + yi ) = ∑ xi + ∑ yi ”
i=0 i=0 i=0
0 0 0
∑ (xi + yi ) = x0 + y0 = ∑ xi + ∑ yi .
i=0 i=0 i=0
Se n ∈ M então como
n+1 n
∑ (xi + yi ) = xn+1 + yn+1 + ∑ (xi + yi )
i=0 i=0
n n
= xn+1 + yn+1 + ∑ xi + ∑ yi
i=0 i=0
n+1 n+1
= ∑ xi + ∑ yi .
i=0 i=0
Portanto n + 1 ∈ M e, pelo princípio de indução N = N.
iii-
n
∑ c = (n + 1) · c.
i=0
De fato seja
n
P(n) = ” ∑ c = (n + 1) · c”
i=0
174 Capítulo 19. Sequências e Recorrências
Se n ∈ M então como
n+1 n
∑ c = c+ ∑c
i=0 i=0
= c + (n + 1) · c = (n + 2) · c.
ão
Portanto n + 1 ∈ M e, pelo princípio de indução N = N.
iv- Propiedad Telescópica
n
∑ (xi+1 − xi ) = xn+1 − x0 .
i=0
aç
De fato seja
n
P(n) = ” ∑ (xi+1 − xi ) = xn+1 − x0 ”
i=0
0
∑ (xi+1 − xi ) = x1 + x0 .
i=0
or
e considere M o seu domínio de verdade. Então 0 ∈ M, pois
ab
Se n ∈ M então como
n+1 n
∑ (xi+1 − xi ) = xn+2 − xn+1 + ∑ (xi+1 − xi )
i=0 i=0
= xn+2 − xn+1 + (xn+1 − x0 ) = xn+2 − x0 .
el
i=k n∈N
De fato, seja
n
P(n) = ” ∏ xi = x0 · x1 · · · xn ”,
i=0
ão
Assuma que n ∈ M então
n+1 n
∏ xi = xn+1 · ∏ xi
i=0 i=0
= xn+1 · (x0 · x1 · · · xn )
aç
= x0 · x1 · · · xn · xn+1 .
De onde n + 1 ∈ M e, pelo princípio de indução, M = N.
Sejam (xn )n∈N e (yn )n∈N duas sequências. Então
i-
n
∏ c · xi = cn · ∏ xi .
i=0
De fato seja
i=0
n
or
ab
n n
P(n) = ” ∏ c · xi = cn · ∏ xi ”
i=0 i=k
0 0
∏ c · xi = c · x0 = c · ∏ xi .
i=0 i=0
Se n ∈ M então como
n+1 n
∏ c · xi = c · xn+1 · ∏ c · xi
Em
i=0 i=0
n
= c · xn+1 · c · ∏ xi
i=k
!
n n+1
n+1
= c · xn+1 · ∏ xi = cn+1 · ∏ xi .
i=k i=0
Portanto n + 1 ∈ M e, pelo princípio de indução N = N.
ii-
n n n
∏(xi · yi ) = ∏ xi · ∏ yi .
i=0 i=0 i=0
De fato seja
n n n
P(n) = ” ∏(xi · yi ) = ∏ xi · ∏ yi ”
i=0 i=0 i=0
Se n ∈ M então como
n+1 n
∏ (xi · yi ) = xn+1 · yn+1 + ∏(xi · yi )
i=0 i=0
n n
= xn+1 · yn+1 · ∏ xi · ∏ yi
i=0 i=0
n+1 n+1
= ∏ xi · ∏ yi .
i=0 i=0
Portanto n + 1 ∈ M e, pelo princípio de indução N = N.
ão
iii-
n
∏ c = cn+1 .
i=0
De fato seja
aç
n
P(n) = ” ∏ c = cn+1 ”
i=0
Se n ∈ M então como
or
ab
n+1 n
∏ c = c·∏c
i=0 i=0
n+1
= c·c = cn+2 .
Portanto n + 1 ∈ M e, pelo princípio de indução N = N.
– A Produtória generalizada: É a sequência de números reais
el
!
n+k
an = ∏ xi
i=k n∈N
! !−1
n+k k−1
an = ∏ xi · ∑ xi .
i=0 i=0
Exemplo 19.5 Para alguns casos particulares, podemos calcular os termos genéricos do somatorio e a
produtoria dos termos de uma sequência.
• Se sequência (xn )n∈N definida pela progressão aritmética para a, r ∈ R temos
xn = a + n · r.
Portanto se
n
Sn = ∑ xn
i=0
temos que
xn = a · nr
Portanto se
n
Sn = ∑ xn
i=0
temos que
ão
Sn − qSn = x0 − xn+1 = a(1 − qn+1 )
1 − qn+1
aç
Sn = a · .
1−q
Achar o termo genérico da recorrência em função dos dados iniciais pode ser uma tarefa difícil, no entanto
existem alguns casos em que isto é possível.
Exemplo 19.6
x0 = a xn = n · xn−1 ∀n≥1
or
• Considere a sequência (xn )n∈N de números reais definida por uma expressão da forma
ab
Observamos que
x2 = 2 · a, x3 = 3 · 2 · a, . . . , xn = n · · · 3 · 2 · a = n! · a.
• Considere a sequência (xn )n∈N de números reais definida por uma expressão da forma
el
x0 = a xn = xn−1 + f (n) ∀ n ≥ 1
para f : N → R.
Observamos que
Em
n
xn = a + ∑ f (n)
j=1
Definição 19.4 Uma sequência (xn )n∈N de números reais definida por uma expressão da forma
xn+2 = 2 · xn+1 + xn ∀ n ∈ N.
178 Capítulo 19. Sequências e Recorrências
Teorema 19.5 Considere uma sequência (xn )n∈N de números reais definida por uma expressão da forma
x0 = a
xn+1 = r · xn ∀ n ≥ 1,
xn = rn · a
Demonstração. Foi feita acima quando vimos o termo genérigo da progressão geométrica.
ão
Teorema 19.6 Considere uma sequência (xn )n∈N de números reais definida por uma expressão da forma
x0 = a
aç
xn+1 = g(n) · xn + f (n) ∀ n ≥ 1,
para f , g : N → R duas funções. Então, o termo genérico da recorrência pode ser escrito como produto
xn = zn · yn
em que
zn = g(n − 1) · zn−1
or
ab
yn = yn−1 + f (n − 1)[g(n − 1) · zn−1 ]−1
x0 = a
xn+1 = r · xn + rn ∀ n ≥ 1,
Então resolvemos
zn = r · zn−1 ⇒ zn = rn · z0
e
1
yn = yn−1 + rn−1 [r · rn−1 · z0 ]−1 = yn−1 + + y0 .
z0 · r
que tem por solução
n+1
yn = + y0
z0 · r
portanto a solução de xn é
n n+1
xn = z0 · r · + y0 = z0 · y0 · rn + (n + 1)rn−1
z0 · r
179
A seguir mostramos um reultado geral para resolução de recorrências lineares de segunda ordem.
Teorema 19.7 Considere uma sequência (xn )n∈N de números reais definida por uma expressão da forma
x0 = a
ão
x1 = b
xn+1 = c1 · xn + c2 · xn−1 ∀ n ≥ 1,
aç
xn = α · r n + n · β · r n
xn = α · r1n + β · r2n
or
para α e β números reais que são determinados em função de a e b.
ab
Demonstração. Primeiramnte observamos que c1 6= 0 pois a recorrência é de segunda ordem.
• Se r é a única raiz de r temos
1
r2 = c1 · r + c2 r = − · c1 e c21 = 4 · c2
2
el
de onde
1
c1 · r − 2 · c2 = − · (c21 − 4 · c2 ) = 0.
2
Em
α =a e β = b · r−1 + (−a).
r12 = c1 · r1 + c2 e r12 = c1 · r1 + c2 .
180 Capítulo 19. Sequências e Recorrências
ão
α +β = a
α · r1 + β · r2 = b
aç
x0
• A sequência de Fibonacci é dada por
= 1
or
Obs. A resolução de recorrências de segunda ordem cuja equação característica não tem raizes no conjunto dos
números reais será vista quando estudemos números complexos.
Exemplo 19.9
ab
x1 = 1
xn+1 = xn + xn−1 ∀ n ≥ 1,
então a equação
x2 − x − 1 = 0
el
portanto
√ !n √ !n
1− 5 1+ 5
xn = α +β
2 2
Portanto
" √ !n √ !n #
1 1+ 5 1+ 5
xn = √ − .
5 2 2
então a equação
x2 − 4 · x + 4 = 0
r1 = r2 = 2.
ão
xn = α · 2n + β · n · 2n
α =1 e 2·α +2·β = 1
aç
de onde
1
β =−
2
e
xn = (2 − n) · 2n−1 ∀n ∈ N.
or
ab
Teorema 19.8 Considere uma sequência (xn )n∈N de números reais definida por uma expressão da forma
x0 = a
x1 = b
el
yn+1 = c1 · yn + c2 · yn−1
Em
Exemplo 19.10 Considere uma sequência (xn )n∈N de números reais definida por uma expressão da forma
x0 = 1
x1 = 1
xn+1 = −xn + 2 · xn−1 + 12 · n − 2 ∀ n ≥ 1,
Para achar a solução desta recorrência vamos primeiramente estudar a solução da recorrência homogênea
Logo, a xn terá por expressão xn = zn + yn . Finalmente estudamos o caso x0 e x1 para determinar a forma precisa
de xn .
• Estudamos a recorrência
ão
A equação característica é
x2 + x − 2 = 0
aç
r1 = 1 e r2 = −2.
é da forma
yn = α · (1)n + β (−2)n = α + β · 2n .
or
ab
• Para zn temos que propor uma solução. Aqui o estudo é intuitivo. Propomos uma solução da forma
zn = a · n2 .
Então
el
a · (n + 1)2 = −a · n2 + 2 · a · (n − 1)2 + 12 · n − 2.
Simplificando temos
12 · n − 2 = 6 · a · n − a
Em
portanto a = 2. De onde
zn = 2 · n2
xn = α + β · 2n + 2 · n2 .
Como x0 = 1 = x1 temos
α +β = 1 e 1 = α − 2 · β + 2.
1 (−2)n+1
xn = + + 2 · n2 .
3 3
ão
20. Números Complexos
aç
or
Vimos que com os números reais, toda função proposicional em R da forma
ab
P(x) = ”x ∈ R, a2k+1 · x2k+1 + · · · + a1 · x + a0 = 0”,
para k ∈ N e a2k+1 6= 0, tem domínio de verdade não vazio. Também vimos que a função proposicional
Q(x) = ”x ∈ R, x2 + 1 = 0”.
el
Tem domínio de verdade vazio em R. Novamente procuramos ampliar o conjunto numérico de forma tal que as
funções proposicionais sobre os números reais estejam contempladas no novo conjunto numérico e de forma
tal que, no novo conjunto numérico, seu domínio de verdade seja não vazio. Nesse sentido introduzimos os
números complexos.
Para construir o conjunto dos números complexos vamos primeiramente construir seus elementos. Para isto
Em
a + bi,
Obs. Aqui o sinal + é uma notação e, em princípio, nada tem a ver com a notação. Mais adiante, no texto,
veremos que podemos relacionar esse + com a operação soma entre números complexos.
Definição 20.1 O conjunto dos números complexos, que denotamos por C,é o conjunto
C = {z = a + bi, a, b ∈ R}.
Em particular se z = a + bi então
• a é chamada de parte real de z e a denotamos por Re(z)
• b é chamada de parte real de z e a denotamos por Im(z)
Obs. Na definição de soma acima utilizamos indistintamente a soma de números reais e de complexos, junto com
a simbologia de ” + ” utilizada na construção do número complexo. Algo similar ocorre com o produto, a
notação correta seria utilizar as operações +R e ·R para as operações sobre os números reais e +C e R e
definir:
• Soma: +C : C × C → C dada por
ão
(a + bi) +C (c + di) = (a +R c) + (b +R d)i.
• Produto: ·C : C × C → C dada por
(a + bi) ·C (c + di) = [a ·R c +R (−(b ·R d)] + (a ·R d +R b ·R c)i.
aç
Claramente, a definição fica sobrecarregada, portanto a omitiremos e deixamos a interpretação ao contexto.
e
(a + bi) + (0 + 0i) = a + bi,
• O elemento 1 = 1 + 0i satisfaz
(0 + ai)2 = (0 − a2 ) + 0i = −a2 + 0i
• O produto
z1 = a + bi, z2 = c + di e z3 = e + f i.
•
z1 + z2 = (a + c) + (b + d)i
= (c + a) + (d + b)i
= z2 + z1 .
185
•
z1 + (z2 + z3 ) = (a + bi) + (c + e) + (d + f )i
= (a + c + e) + (b + d + f )i
= (a + c) + (b + d)i + (e + f i)
= (z1 + z2 ) + z3 .
• Existe o elemento 0 = 0 + 0i
0 + z1 = (a + 0) + (b + 0)i = z1 .
ão
Observamos que é únito. De fato se w possui a mesma propriedade, temos
0 = w + 0 = w.
aç
z1 + (−z1 ) = (a + (−a)) + (b + (−b))i = 0 + 0i = 0.
•
z1 + z2 = z1 + z3 ⇔ (a + c) + (b + d)i = (a + e) + (b + f )i
•
⇔ c + di = e + f i
or
⇔ [(a + c) = (a + e)] ∧ [(b + d) = (b + f )]
⇔ (c = e) ∧ (d = f ) (cancelamente em R)
⇒ z2 = z3 .
ab
z1 · z2 = (a · c − b · d) + (a · b + b · c)i
= (c · a − d · b) + (b · a + c · b)i
= z1 + z2 .
• Provamos o cancelamento da soma por completitude.
el
• Para todo z1 ∈ C tal que z1 6= 0 vimos acima que existe um único z−1
1 ∈ C definido por
a b
z−1
1 = + i,
a2 + b2 a2 + b2
tal que
z−1
1 · z1 = 1.
•
z3 · (z1 + z2 ) = (e + f i)[(a + c) + (b + d)i]
= [e · (a + c) − f · (b + d)] + [e · (b + d) + (a + c) · f ]i
= [e · a + e · c − f · b + f · d] + [e · b + e · d + a · f + c · f ]i
= z3 · z1 + z3 · z2 .
• Provamos o cancelamento do produto por completitude.
z1 · z2 = z1 · z3 ⇒ z−1 −1
1 · z1 · z2 = z1 · z1 · z3
⇒ z2 = z3 .
186 Capítulo 20. Números Complexos
j(a) = a + 0i,
então
• j é injetora,
• j(a + b) = j(a) + j(b)
• j(a · b) = j(a) · j(b).
ão
Demonstração. • Assuma que j(a) = j(b) então a + 0i = b + 0i de onde a = b e portanto j é injetora.
• da definição
j(a + b) = (a + b) + 0i
= (a + 0i) + (b + 0i)
= j(a) + j(b).
aç
• da definição
j(a · b) = (a · b) + 0i
= (a + 0i) · (b + 0i)
= j(a) · j(b).
or
Obs. É por meio desta função injetora que identificamos R como um subconjunto de C. Temos assim uma torre
ab
de inclussões:
N ⊂ Z ⊂ Q ⊂ R ⊂ C.
a ∈ R ≡ a + 0i
el
e da regra
que escrevemos
Em
a · (b + ci) = (a · b) + (a · c)i.
Demonstração. Como R ⊂ C, se C for enumerável então R também deveria ser, o que é uma contradição.
z̄ = a + (−b)i := a − bi.
O produto
z · z̄ = a2 + b2 + 0i
pode ser identificado com o número real a2 + b2 . Definimos o módulo do número complexo z = a + bi por
√ p
|z| = z · z̄ = a2 + b2 .
187
ão
e
z1 · z2 = (a · c − b · d) + (ad + bc)i
= (a − bi) · (c − di)
aç
= z1 · z2 .
0 + 0i < (0 + i)2 = −1 + 0i
or
Demonstração. Assuma que C é um corpo ordenado. Então, como 0 + i 6= 0 + 0i temos duas posibilidades:
ab
de onde
portanto
1 + 0i = (1 + 0i) + (0 + 0i) < (1 + 0i) + (−1 + 0i) = 0 + 0i < (−1 + 0i)2 = 1 + 0i.
Por fim observamos que nos complexos toda função proposicional da forma
P(x) = ”x ∈ R, ak · xk + · · · + a1 · x + a0 = 0”,
como a0 , . . . , ak ∈ C e ak 6= 0 tem domínio de verdade não vazio. Mais ainda, pode ser mostrado que o domínio de
verdade contém, no máximo, k elementos. A prova deste resultado é conhecido como o Teorema fundamental
da Álgebra.
Para representar gráficamente os número complexos consideramos a função φ : C → R2 dada por
ão
(a, b) ≡ a + bi.
como segue:
aç
or
ab
el
θ = Arg(z).
ρi = |zi | e θi = Arg(zi ),
z = ρ cos(φ ) + ρ sin(φ )i
189
em que
ρ = ρ1 · ρ2 · · · ρn
φ + 2 · k · π = θ1 + θ2 + · · · + θn .
ão
z1 = ρ1 (cos(θ1 ) + sin(θ1 )i) e z2 = ρ2 cos(θ2 ) + sin(θ2 )i)
então
z1 · z2 = ρ1 ρ2 [(cos(θ1 ) · cos(θ2 ) − sin(θ1 ) · sin(θ2 )) + (cos(θ1 ) · sin(θ1 ) + cos(θ2 ) · sin(θ2 ))i]
aç
= ρ1 ρ2 [cos(θ1 + θ2 ) + sin(θ1 + θ2 )i]
Então
z = ρ cos(φ ) + ρ sin(φ )i
el
em que
ρ = ρ1 · ρ2 · · · ρn
φ + 2 · k · π = θ1 + θ2 + · · · + θn .
Calculamos
z1 · · · zn · zn+1 = (ρ · cos(θ ) + ρ · sin(θ )i) · (ρn+1 · cos(θn+1 ) + ρn+1 · sin(θn+1 )i
= [(ρ · ρn+1 ) · cos(θ + θn+1 )] + [(ρ · ρn+1 ) · sin(θ + θn+1 )]i
em que
ρ̃ = ρ1 · ρ2 · · · ρn · ρn+1
φ + 2 · k · π = θ1 + θ2 + · · · + θn + θn+1 .
Portanto, a identidade também vale para n + 1 números. O axioma de indução garante que vale para um número
n ≥ 2 de elementos.
190 Capítulo 20. Números Complexos
ão
com θ̃k ∈ [0, 2π) congruente com
1
· (θ + 2 · k · π) 0 ≤ k < m,
m
satisfaz
aç
zm
k = a + bi.
Corolário 20.3 Para todo z ∈ C existem duas soluçções da equação x2 = z que denotamos por z1 e z2 e que
ab
são tais que z1 = −z2 .
Demonstração. A existência de duas soluções é resultados da discussão acima. O fato de que as soluções
z1 = −z2 satisfazem essa relação é consequência do fato
Arg(z2 ) = Arg(z1 ) + π.
el
z5 = 1 + 1i.
Em
Observamos que
√ √
1 1
1 + 1i = 2 cos · π + 2 sin ·π ,
4 4
de onde seguem que os argumentos possíveis para z são
1
θ0 = · π,
20
1 1 9
θ1 = ·π + ·π = · π,
20 5 20
1 2 17
θ2 = ·π + ·π = · π,
20 5 20
1 3 27
θ3 = ·π + ·π = · π,
20 5 20
1 4 33
θ4 = ·π + ·π = · π,
20 5 20
portanto, as soluções são
√
10
√
10
zi = 2 cos(θi ) + 2 sin(θi )i, i = 0, 1, 2, 3, 4.
No plano complexo, estas soluções estão nos pontos indicados.
191
ão
x2 + z1 · x + z2 = 0.
aç
Para achar a solução vamos a derivar a bem conhecida fórmula de Bhaskara.
Teorema 20.5 — Fórmula de Bhaskara. Considere a função proposicional sobre C dada por
Se
1 1
x1 = [−z1 + w] e x2 = [−z1 + (−w)],
2 2
para
el
√ 1 √ 1
w = ρ · cos · θ + ρ · sin · θ i.
2 2
Demonstração. Comenzamos observando que, pelo corolário 20.3 existe um w ∈ C tal que w e −w são solução
Em
de
y2 = z21 − 4 · z2 .
2 · x + z1 = w ou 2 · x + z1 = −w
192 Capítulo 20. Números Complexos
x2 + z1 · x + z2 = 0.
são
1 1
x1 = [−z1 + w] e x2 = [−z1 + (−w)].
2 2
ão
Exemplo 20.2 Considere a equação
x2 + x + 1 = 0
calculamos a solução de
aç
y2 = 1 − 4 · 1 = −3
que são
√ √
w = 0 + 3i − w = 0 + (− 3)i
Então,
x1 =
1 1 √
+ · 3i
2 2
e x2 =
1 1 √
+ · (− 3)i
2 2
or
ab
são as soluções procuradas.
Já vimos como resolver recorrências lineares de ordem 2 no caso em que a equação característica tem raizes
reais. Agora, para completar o estudo vemos o caso de recorrências sobre os números reais no caso em que as
raizes da equação característica são complexas.
el
Teorema 20.6 Considere uma sequência (xn )n∈N de números reais definida por uma expressão da forma
x0 = a
x1 = b
xn+1 = c1 · xn + c2 · xn−1 ∀ n ≥ 1,
Em
xn = α · r1n + β · r2n
Demonstração. A demonstração é idéntica ao caso real. Primeiramente observamos que se r1 e r2 são raizes de
R temos que
r12 = c1 · r1 + c2 e r12 = c1 · r1 + c2 .
a = x0 = α + β e b = x1 = α · r1 + β · r2
Considere uma sequência (xn )n∈N de números reais definida por uma expressão da forma
x0 = a
ão
x1 = b
xn+1 = c1 · xn + c2 · xn−1 ∀ n ≥ 1,
aç
xn = α · r1n + β · r2n .
de onde
1 1
q q
2
r1 = · c1 + 4 · c2 − c1 i e 2
· c1 − 4 · c2 − c1 i
2 2
Em
r1 = ρ · cos(θ ) + ρ · sin(θ )i
r2 = ρ · cos(θ ) − ρ · sin(θ )i
e
xn = α · r1n + β · r2n
= (α + β ) · ρ n · cos(n · θ ) + (α − β ) · ρ n · sin(n · θ )i.
x0 = 1
x1 = 2
xn+1 = xn − xn−1 ∀ n ≥ 1,
xn = α · r1n + β · r2n
Como
1 = x0 = α + β e 2 = x1 = α · r1 + β · r2
ão
temos
α = r2 e β = r1 .
Utilizando que
aç
1 3
r1 · r2 = + + 0i = 1 + 0i,
4 4
e que
r1 = cos
r2 = cos
1
3
1
· π + sin
· π − sin
1
3
1
· π i,
· π i,
or
ab
3 3
temos
xn = r1n−1 + r2n−1
n−1 n−1 n−1 n−1
el
n−1
xn = 2 · cos ·π ∀ n ∈ N.
3
III
Introdução à Análise
combinatória
ão
aç
or
ab
el
Em
aç
or
Neste capítulo vamos estudar a contagem de elementos de um conjuntos sob alguma hipótese ou condição.
Em particular, daremos atenção ao problema do número de formas de alocar objetos em compartimentos sob
ab
hipóteses nos mesmos.
O primeiro resultado que estudamos e como contar o número de elementos que pertencem a união de vários
conjuntos que não são necessariamente disjuntos. Esse é o conteúdo do seguinte teorema.
Teorema 21.1 — Princípio de inclusão-exclusão. Seja {A1 , . . . , An } uma familia de conjuntos finitos.
el
Então
n
] (∪ni=1 Ai )) = ∑ ]Ai − ∑ ](Ai ∩ A j ) + ∑ ](Ai ∩ A j ∩ Ak ) − · · · + (−1)n ] (∩ni=1 Ai ) .
i=1 1≤i< j≤n 1≤i< j<k≤n
Em
n
] (∪ni=1 Ai )) = ∑ ]Ai − ∑ ](Ai ∩ A j ) + ∑ ](Ai ∩ A j ∩ Ak ) − · · · + (−1)n ] (∩ni=1 Ai ) .”
i=1 1≤i< j≤n 1≤i< j<k≤n
à = ∪ki=1 Ai e B̃ = Ak+1 .
Então, como
à ∩ B̃ = ∪ki=1 (Ai ∩ Ak )
198 Capítulo 21. Introdução à Análise combinatória
Temos
k
]Ã = ∑ ]Ai − ∑ ](Ai ∩ A j ) + ∑ ](Ai ∩ A j ∩ Al ) − · · · + (−1)k ] ∩ki=1 Ai
i=1 1≤i< j≤k 1≤i< j<l≤k
]B̃ = ]Ak+1
k
](Ã ∩ B̃) = ∑ ](Ai ∩ Ak+1 ) − ∑ ](Ai ∩ A j ∩ Ak+1 )
i=1 1≤i< j≤k
+ ∑ ](Ai ∩ A j ∩ Al ∩ Ak+1 ) − · · · + (−1)k ] ∩i=1
k+1
Ai
ão
1≤i< j<l≤k
aç
Portanto k + 1 ∈ M. De onde M = {n ∈ N, n ≥ 2}.
]F = 40 ]T = 35 ](F ∩ T ) = 15
el
](F\(F ∩ T )) = 40 − 15 = 25
](T \(F ∩ T )) = 35 − 15 = 20
Em
](F ∪ T ) = ]F + ]T − ](F ∩ T ) = 40 + 35 − 15 = 60
](U\(F ∪ T )) = 70 − 60 = 10.
](A1 × · · · × Ak ) = n1 · · · nk .
3 números?
Se A = {a, b, . . . , z} e N = {0, 1, . . . , 9} temos que uma placa de carro será um elemento de
N 3 ×A 4
199
então, como
Exemplo 21.3 Se queremos acomodar n pessoas ao redor de uma mesa redonda, temos que:
• Como a mesa é redonda então não há uma ordem linear, escolhida uma ordem temos n rotações da mesma
que também são possíveis e se identificam com a original. Uma vez escolhida onde se senta a primeira
pessoa, temos
ão
(n − 1)!
aç
lugar da primeira pessoa, uma mulher, automáticamente temos 2! lugares para as outras mulheres e 3!
possibilidades para os homens. Então temos
3! · 2!
possibilidades diferentes. or
Lembramos que o fatorial é a operação unária que associa a cada número natural n ∈ N o número n! da
seguinte forma
ab
se n = 0 então 0! = 1
se n > 0 então n! = n · (n − 1) · (n − 2) · · · 2 · 1.
A = {a1 , . . . , an }.
(a1 , . . . , ar ) ∈ Ar
Em
Teorema 21.2 Seja A um conjunto de n elementos. O número de arranjos de r elementos de A é dado por
n!
= n · (n − 1) · · · (n − r + 1)
(n − r)!
(a1 , . . . , ar )
200 Capítulo 21. Introdução à Análise combinatória
](A1 × · · · × Ar ) = n · (n − 1) · · · (n − r + 1)
Definição 21.2 Seja A um conjunto com n elementos. Uma permutação é um arranjo de n elementos de A.
ão
Com isto, podemos interpretar o fatorial da seguinte forma.
Corolário 21.1 Seja A um conjunto com n elementos. O número de permutações dos elementos de n é n!.
Demonstração. Imediato de
aç
n! n!
= = n!.
(n − n)! 1
Exemplo 21.5 or
• De quantas formas diferentes podemos escolher um presidente, um secretário e um
funcionario de um grupo de 9 pessoas? Devemos escolher, sem repetição. Então temos
9!
= 9 · 8 · 7,
6!
ab
arranjos diferentes.
• De quantas formas diferentes por três bolinhas diferentes entre si em três caixas diferentes?
Temos 3! permutações diferentes entre as caixas. Portanto o resultado é 6.
el
Seja s = (b1 , . . . , br ) ∈ Ar um elemento em que cada elemento ai ∈ A aparece ri vezes em s (sendo permitido
o caso ri = 0), isto é
r1 + . . . + rn = r.
Em
Queremos saber quantos elementos diferentes podemos construir desta forma ou, dito de outra forma, o número
de permutações distinguíveis de dos elementos de s.
Exemplo 21.6 Considere s = (A, B,C, B,C, B) queremos ver as possíveis permutações distinguíveis deste
objeto.
Como são 6 elementos temos 6! = 720 permutações. No entanto se trocarmos, por exemplo o elemento da
posição 2 com o da posição 4 temos o mesmo objeto, portanto a permutação não é distinguível.
Começamos com a letra A. Ela só aparece 1 vez e portanto temos que qualquer permutação que troque A de
lugar será distinguíveis. Portanto há
720
1!
permutações em que as letras B,C podem aparecer em locais diferentes.
A letra B se repite 3 vezes. Então cada palavra conta 3! permutações que não producem nenhum efeito pois
só alteram a posição da letra B. Dividimos então as 720 permutações em 3! permutações que não alteram o lugar
onde aparece a letra B e temos
720
= 120
3!
grupos de permutações na qual C pode aparecer em lugares diferentes .
201
A letra C aparece 2 vezes, portanto dividimos estes 120 grupos pelas 2! permutações não váo alterar a
posição da letra C e obtemos o conjunto de todas permutações diferentes entre si. Obtemos assim que, das 720
permutações originais, somente
120
= 60,
2!
vão ser distinguíveis entre si.
ão
Teorema 21.3 Seja s = (b1 , . . . , br ) ∈ Ar um elemento em que cada elemento ai ∈ A aparece ri vezes em s
(sendo permitido o caso ri = 0), isto é
r1 + · · · + rn = r.
aç
o número de permutações distinguíveis de s é
r!
r1 ! · · · rn !
or
Demonstração. Observamos que se s possui r elementos então temos r! permutações possíveis. O elemento a1
vai se repetir r1 vezes, portanto podemos organizar as permutações em
r!
r1 !
ab
conjuntos diferentes, que são todas as permutações obtidas de permutar todas as outras entradas diferentes de a1 .
Da mesma forma procedemos com a2 , ele vai aparecer m2 vezes. Então organizamos rr!1 ! permutações em
r!
el
r1 ! · r2 !
conjuntos diferentes, que são todas as permutações obtidas de permutar todas as outras entradas diferentes de a1
e a2 . Continuando o processo desta forma temos o resultado depois de n passos.
subconjunto de m elementos de A
Observamos que dois arranjos diferentes, e que sejam um permutação da posição dos elementos do outro, dão
lugar ao mesmo subconjunto. Por exemplo, os arranjos
{ai1 , . . . , aim }.
De fato temos como cada arranjo tem m elementos todos distintos entre si, temos
ão
m!
= m!
1! · 1! · · · 1!
arranjos dos mesmos elementos que dão origem ao mesmo conjunto.
Portanto, temos que dividir a quantidade de arranjos pelas m! permutações dos seus elementos de onde segue
aç
que há
n!
(n − m)! · m!
combinações possíveis.
or
Exemplo 21.7 Vamos contar o número de contrasenhas possíveis de 8 entradas das quais uma deve ser uma
letra maiúscula, uma deve ser um número e o restante são letras minúsculas.
Temos 26 · 10 (26 letras e 10 números) formas de escolher a letra maiúscula e o número.
ab
Devemos escolher 6 lugares de 8 que devemos preencher com as 26 letras do alfabeto. Temos assim
8
(26 · 10) · · 266 = 4, 497813699 · 1012 .
6
el
possibilidades de contrasenhas. Se conseguirmos testar 100 contrasenhas por segundo, para testar todas as
possibilidades vamos a demorar
4, 497813699 · 1012
' 1426 anos.
(365 · 24 · 60 · 60) · 100
Em
Sejam 0 ≤ m ≤ n números
Lema 21.1
n n
naturais.
Então
• m = e em particular n1 = n−1n
=n
n−mn
n−k+1
k−1 se k > 1
n
n−1 nk
• k = k n−k se k < n .
n−1 n
k−1 k se n, k > 1
• Da definição temos
Demonstração.
n n!
=
m (n − m)! · m!
n!
=
(n − m)! · (n − (n − m))!
n
=
n−m
Em particular
n n n!
= = = n.
1 n−1 (n − 1)! · 1!
203
• Mostramos
caso por separado. Se k > 1 temos
cada
n n−k+1 n! n−k+1
= ·
k−1 k (k − 1)! · (n − k + 1))! k
n! n
= = .
k! · (n − k))! k
Se k <n
n−1 n (n − 1)! n
= ·
k n−k k! · (n − k − 1)! n − k
n! n
ão
= = .
k! · (n − k))! k
E por último,
se n, k > 1 temos
n−1 n (n − 1)! n
= ·
k−1 k k − 1! · (n − k)! k
n! n
aç
= = .
k! · (n − k))! k
8
4
=
8!
=
8·7·6·5
4! · 4! 4 · 3 · 2 · 1
= 70
or
de 4 elementos de um conjunto de 8 elementos. Temos assim
ab
formas diferentes.
• De um grupo de 11 pessoas, das quais são 6 mulheres e 5 homens. De quantas formas podemos formar
uma comissão 6 pessoas de forma tal que 4 sejam mulheres e 2 homens. Observamos que as mulheres
podem ser seleccionadas de
el
6 6!
= = 15
4 2! · 4!
= = 10
2 2! · 3!
escolhas diferentes.
Observe que se você pegar 962766 baralhos de poker. Cada baralho tem aproximadamente 2, 5cm de
altura, portanto isso dá uma torre de pouco mais de 24 km de altura. Agora, se juntamos todos eles e
marcamos uma carta com seu nome. Observe que estaria marcando uma carta em
Ou seja, você tem mais chance de escolher uma dessas cartas e pegar aquela que foi marcada do que
acertar em um bilhete da Mega-Sena (o exemplo foi adaptado de um trecho pego do livro “Five-Minute
Mathematics, Ehrhard Behrends).
204 Capítulo 21. Introdução à Análise combinatória
Exemplo 21.9 Considere um baralho de 52 cartas estândar para o jogo de poker. Em cada mão recebe 5
cartas.
• Na primeira mão recebemos um subconjunto de 5 cartas de um total de 52 distintas, portanto temos
52
T= = 2.598.960
5
ão
5 cartas de um conjunto 52 − 13 = 39 cartas (que são o conjunto total menos as cartas que são ouro) no
total, portanto há
39
= = 575.757
5
aç
possibilidades diferentes de receber 5 cartas e que nenhuma delas seja ouro.
Observamos que o número de possiblidades de receber 5 cartas é a soma das possibilidades em que nenhuma
seja ouro, nenhuma seja espada, nenhuma seja copas e nenhuma bastos.
Portanto, a quantidade de possibilidades de que, pelo menos uma, das cartas da mão seja de ouro é subtrair
or
ao número total as possibilidades de que nenhuma seja ouro, isto é
Exemplo 21.10 Se temos uma turma de 20 alunos dos quais 11 são mulheres e 9 homens. Podemos:
escolher 3 estudantes de 20
• 2 formas diferentes.
escolher 3 estudantes mulheres de 11
• 3 formas diferentes.
escolher 3 estudantes dos quais 1 é um homem, de 11
9
2 · 1 formas diferentes.
el
•
• escolher 3 estudantes dos quais ao menos 1 é um homem de
total só mulheres
z }| {
z }| {
20 11
−
Em
3 3
formas diferentes.
A = {a1 , . . . , an } e B = {b1 , . . . , bm }
• O número de funções bijetoras de A em A é n!. De fato cada função bijetora associa biunívocamente os
elementos de A. Assim se f : A → A é bijetora, temos
f (a1 ) = ai1 (n possibilidades)
f (a2 ) = ai2 ∈ A\{ai1 } (n − 1 possibilidades)
f (a3 ) = ai3 ∈ A\{ai1 , ai2 } (n − 2 possibilidades)
.. ..
. .
f (an ) = ain ∈ A\{ai1 , ai2 , . . . , an−1 } (1 possibilidade)
ão
. .
f (an ) = bin ∈ A\{bi1 , bi2 , . . . , bn−1 } (m − (n − 1)) possibilidades)
de onde temos
m!
aç
m · (m − 1) · · · (m − n + 1) =
(m − n)!
possibilidades de escolhas para a função f .
• Se n ≥ m podemos ver que o número de funções sobrejetoras f : A → B é
m−1
m
∑ (−1) · k · (m − k)n .
k=0
k or
Podemos chegar a este resultado utilizando o princípio de inclussão-exclussão. A ideia é fazer o número
total de funções menos o número de funções que não são sobrejetoras, isto é
ab
mn − ](∪mj=1 A j )
em que
A j = { f : A → B, b j 6∈ f (A)}.
el
Como
m
∑ ](A j1 ∩ · · · ∩ A jk ) = k · (m − k)n ,
1≤ j1 ≤···≤ jk ≤m
pois estamos contanto as diferentes escolhas de k elementos de B que não vaõ ser atingidos pelo número
Em
funções sobrejetoras.
Cada função sobrejetora f : A → B vai produzir uma partição
A1 = f −1 (b1 ), . . . , Am = f −1 (bm )
de A. Assim, contar o número de funções sobrejetoras está relacionado a contar número de partições de A
com m conjuntos. Para cada partição deste tipo, haverá m! funções sobrejetoras que a geram obtidas de
permitar os valores bi que estão na imagem do conjunto A j . Assim, o número de partições é
1 m−1
k m
S(n, m) = ∑ (−1) · · (m − k)n .
m! k=0 k
chamado de Número de Stirling de segundo tipo e é denotado por S(n, m).
O leitor pode consultar ou trabalho de Fahd and Gulf, Classroom note: An inductive derivation of Stirling
numbers of the second kind and their applications in statistics, Journal of Applied Mathematics and
Decision Sciences (1997) para mais detalhes sobre o assunto.
206 Capítulo 21. Introdução à Análise combinatória
ão
m m!
= .
n n!(m − n)!
aç
n+m−1
.
n
• O número de maneiras de distribuirmos n objetos distintos em m < n compartimentos distintos sem que
nenhum fique vazio é
m−1
k=0
km
∑ (−1) · k · (m − k)n .
or
ab
• O número de maneiras de distribuirmos n objetos iguais em m < n compartimentos distintos sem que
nenhum fique vazio é
n−1
.
m−1
el
• O número de maneiras de distribuirmos n objetos distintos em m < n compartimentos iguais sem que
nenhum fique vazio é
1 m−1
k m
S(n, m) = ∑ (−1) · · (m − k)n .
Em
m! k=0 k
m!
n!
207
possibilidades.
• O número de maneiras de distribuirmos n objetos distintos em m ≥ n compartimentos iguais de forma
que tenhamos em cada um, no máximo, um objeto é o mesmo que contar o número de subconjuntos de m
elementos de um conjunto com n elementos. Isto é contar o número de arranjos de m objetos e fazer o
quociente pelas permutações dos seus elementos, ou seja, o número de combinações. De onde segue que
temos
m
n
ão
• Para achar o número de maneiras de distribuirmos n objetos iguais em m < n compartimentos distintos
com, no máximo o objeto por compartimento observamos que existem distribuições indistingíveis por
causa dos objetos serem iguais. Assim temos que se xi é o número de objetos no compartimento i temos
x1 + · · · + xm = n.
aç
Então procuramos o número de soluções não negativas desta equação. Isto é equivalente a escolher n
objetos entre m + n − 1 símbolos formados por n estrelas e m − 1 barras. Aqui as estrelas são os objetos e
as barras o que delimitam os compartimentos. Por exemplo para n = 8 e m = 4 um caso seria.
? ? ?| ? ?| ? | ? ?.
m + (n − m) − 1 n−1 n−1
= = .
n−m n−m m−1
• O número de maneiras de distribuirmos n objetos distintos em m < n compartimentos iguais sem que
nenhum fique vazio é igual ao número obtido ao contar o número obtido para compartimentos distintos e
Em
dividir pelas m! possibilidades de escolhas de ordem das caixas (visto que são todas iguais).
• O número de maneiras de distribuirmos n objetos distintos em m compartimentos iguais de forma que
tenhamos em cada um, no máximo, um objeto é 0 se n > m pois, necessárimante uma vez preenchidos os
m sobram objetos que devem ser colocados em algum dos compartimentos já preenchidos.
No caso em que n ≤ m colocamos um objeto em cada compartimento, podendo sobrar compartimentos.
Como os compartimentos são iguais, qualquer outra distribuição é equivalente a primeira (pios é uma
permutação da mesma), então existe uma única forma neste caso.
• Aqui, novamente utilizamos o princípio de inclussão-exclussão para
Ak = {maneiras de distribuirmos n objetos distintos em
k ≤ m compartimentos iguais sem que nenhum fique vazio}
e observandos que, neste caso as interseções Ai ∩ A j = 0/ para i 6= j pois se, por exemplo, i < j temos que
uma maneira de distribuir n objetos em j compartimentos sem que nenhum fique vazio nunca pode ser uma
maneira de distribuir n objetos em i compartimentos sem que nenhum fique vazio, pois necessáriamente
teremos um número menor que n bolas nos i compartimentos.
O número de maneiras de distribuirmos n objetos distintos em m < n compartimentos iguais é então igual
à soma é a soma
m
∑ ]Ak
k=1
208 Capítulo 21. Introdução à Análise combinatória
isto é, ao número obtido de somar número de maneiras de distribuirmos n objetos distintos em k ≤ m < n
compartimentos iguais sem que nenhum fique vazio de k = 1 até m. Obtendo assim o resultado.
Só resta, na análise do resultado acima, o caso de distribuir objetos iguais em compartimentos iguais.
Começamos por estudar o caso de distribuir n objetos iguais em m compartimentos iguais sem que nehum
fique vazio. Em geral esse número é denotado por
P(n, m),
ão
e satisfaz uma relação de recorrência que passamos a descrever.
O número P(n, m) é a soma das distribuições a seguir
• o caso em que existe um compartimento com um objeto só, e distribuimos os objetos restantes nos m − 1
compartimentos restantes, que dá P(n − 1, m − 1) possibilidades.
• o caso em que todas os compartimentos tem mais do que um objeto (pois como cada compartimento tem
aç
como mínimo um objeto, contamos o objeto a mais como sendo já distruibuído) . Neste caso, temos n − m
objetos a serem distribuídos em m compartimentos. Temos assim P(n − m, m)possibilidades.
Temos assim que
todos os compartimentos são iguais, estas n distribuições são indistinguíveis entre si e, portanto, são todas
equivalentes. De onde segue que temos uma distribuição só.
Com isto, junto a relação de recorrência
podemos achar todos os valores P(n, m). Escrevemos alguns dos valores na tabela abaixo.
m 1 2 3 4 5 6 7 8 9 10
n=1 1 0 0 0 0 0 0 0 0 0
n=2 1 1 0 0 0 0 0 0 0 0
n=3 1 1 1 0 0 0 0 0 0 0
n=4 1 2 1 1 0 0 0 0 0 0
n=5 1 2 2 1 1 0 0 0 0 0
n=6 1 3 3 2 1 1 0 0 0 0
n=7 1 3 4 3 2 1 1 0 0 0
n=8 1 4 5 5 3 2 1 1 0 0
n=9 1 4 7 6 5 3 2 1 1 0
n = 10 1 5 8 9 7 5 3 2 1 1
Por último, para obter a forma de distribuir n objetos iguais em m compartimentos iguais utilizamos o
princípio de inclussão-exclussão para
e observandos que, neste caso as interseções Ai ∩ A j = 0/ para i 6= j pois se, por exemplo, i < j temos que uma
maneira de distribuir n objetos em j compartimentos sem que nenhum fique vazio nunca pode ser uma maneira
de distribuir n objetos em i compartimentos sem que nenhum fique vazio, pois necessáriamente teremos um
número menor que n bolas nos i compartimentos.
Portanto, forma de distribuir n objetos iguais em m compartimentos iguais é a soma
m
∑ ]Ak
k=1
ão
isto é, a soma da possibilidade de distribuir em todos sem que nenhum fique vazio, com a de distribuir m − 1
compartimentos sem que nenhum fique vazio, e assim seguindo. Chegamos então a
m
∑ P(n, k) possibilidades.
k=1
aç
or
ab
el
Em