Aula_conjuntos

Prévia do material em texto

MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Matemática Discreta
Conjuntos
Prof.ª Dr.ª Diane Castonguay
Prof. Me. Julliano R. Nascimento
{diane, julliano}@inf.ufg.br
Instituto de Informática
Universidade Federal de Goiás
1 / 157
MD
DC
Revisão
Conjuntos
Relações
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
O que é um conjunto?
Definção
Um conjunto é uma coleção de objetos, sem repetição e não
ordenada.
Observação
Um objeto pertence ou não a um conjunto.
Um objeto só pertence uma vez.
Não importa a ordem dos objetos.
Notação
♥ ∈ {♣,♦,♥,♠}
� 6∈ {♣,♦,♥,♠}
{pi, 2, 3, pi} = {2, 3, pi} = {3, 2, pi}
2 / 157
MD
DC
Revisão
Conjuntos
Relações
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Conjuntos Importantes
Definições
O conjunto vazio é o conjunto que não possui elementos.
É denotado por ∅.
N = {0, 1, 2, 3, . . .}, o conjunto dos números naturais.
N∗ = N− {0} = {1, 2, 3, . . .}, o conjunto dos números
naturais exceto o zero.
Z = {. . . ,−2,−1, 0, 1, 2, . . .}, o conjunto dos números
inteiros.
Z+ = {1, 2, 3, . . .}, o conjunto dos números inteiros
positivos.
Q = {pq | p ∈ Z, q ∈ Z e q 6= 0}, o conjunto dos números
racionais.
R, o conjunto dos números reais.
3 / 157
MD
DC
Revisão
Conjuntos
Relações
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Definição
Sejam A e B dois conjuntos. Dizemos que A é um subconjunto
de B (ou A está contido em B, ou B contém A) se todo
elemento de A é um elemento de B.
Notação
A ⊆ B
Observação
Seja A um conjunto. Então:
∅ ⊆ A.
A ⊆ A.
x ∈ A⇔ {x} ⊆ A.
4 / 157
MD
DC
Revisão
Conjuntos
Relações
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Criando conjuntos a partir de outros
Seja A um conjunto.
Definição: Potência
O conjunto potência de A, denotado por 2A, é o conjunto
formado de todos os subconjuntos de A.
Observação
Observamos que 2A = {X conjunto t. q. X ⊆ A}.
Exemplo
Consideramos A = {0, 1}. Então, 2A = {∅, {0}, {1}, A}.
Seja B = {♥, pi, c}. Então
2B = {∅, {♥}, {pi}, {c}, {♥, pi}, {♥, c}, {pi, c}, B}.
5 / 157
MD
DC
Revisão
Conjuntos
Relações
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Produto Cartesiano
Definição
Sejam A e B dois conjuntos.
O produto cartesiano de A por B é o conjunto de todos os
pares ordenados formados de um elemento de A e depois de um
elemento de B
Notação
A×B = {(a, b) t. q. a ∈ A, b ∈ B}
Exemplo
Consideramos os conjuntos A = {0, 1} e B = {?,�, pi}.
O produto cartesiano de A por B é o conjunto
A×B = {(0, ?), (0,�), (0, pi), (1, ?), (1,�), (1, pi)}
6 / 157
MD
DC
Revisão
Conjuntos
Relações
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Relações
Definição
Sejam A e B dois conjuntos.
Dizemos que R é uma relação de A para B se R ⊆ A×B.
Dizemos que R é uma relação sobre A se R ⊆ A×A.
Exemplos
∅ é uma relação de A para B.
A×B é uma relação de A para B.
Se X ⊆ A e Y ⊆ B
então X × Y é uma relação de A para B.
idA = {(a, b) ∈ A×A t. q. a = b} é uma relação sobre A.
Div = {(a, b) ∈ Z× Z t. q. a|b} é uma relação sobre Z.
≤ = {(a, b) ∈ Z× Z t. q. a ≤ b}.
7 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função
8 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
De onde vem, onde vai
Definições
Seja f uma relação.
O domínio de f é o conjunto
Domf = {a t. q. ∃b; (a, b) ∈ f}
A imagem de f é o conjunto
Imf = {b t. q. ∃a; (a, b) ∈ f}
Exemplos
f = {(1, 3); (2, 3); (3, 2); (3, 4)},
Domf = {1, 2, 3}, Imf = {2, 3, 4}.
g = {(1, 3), (2, 3), (3, 2), (4, 4)},
Domf = {1, 2, 3, 4}, Imf = {2, 3, 4}.
h = {(1, 3), (2, 1), (3, 2), (4, 4)},
Domf = {1, 2, 3, 4} = Imf .
9 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função
Definição
Seja f uma relação de A para B.
Dizemos que f é uma função de A para B quando satisfaz:
se (a, b), (a, c) ∈ f então b = c.
se a ∈ A, então ∃b ∈ B tal que (a, b) ∈ f , ou seja
Domf = A.
Notação
Denotamos por f : A→ B uma função de A para B.
Para cada a ∈ A, existe um único b ∈ B tal que (a, b) ∈ f .
Denotamos este elemento b por f(a) (f de a). Neste caso,
dizemos que f(a) é definido.
10 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função
Exemplos
idA é uma função sobre A definida por idA(x) = x.
Em geral, A×A não é uma função.
Div|N não é uma função.
f = {(1, 3), (2, 3), (3, 2), (3, 4)} não é uma função.
g = {(1, 3), (2, 3), (3, 2), (4, 4)} é uma função sobre
{1, 2, 3, 4}.
h = {(1, 3), (2, 1), (3, 2), (4, 4)} é uma função sobre
{1, 2, 3, 4}.
A relação f = {(x, y) ∈ R× R t. q. xy = 1} é uma
função de R∗ para R definida por f(x) = 1/x.
A relação g = {(x, y) ∈ R×R t. q. xy = 0} não é função.
A relação h = g ∩ (R∗ × R) é uma função de R∗ para R.
Observe que h é definida por h(x) = 0.
11 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função de Escolha
Definição
Seja B um conjunto, P ⊆ 2B e A ∈P. Dizemos que
f :P → B
é uma função de escolha quando:
f(A) ∈ A, ∀A ∈P
Observação
∅ /∈P
12 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função de Escolha
Definição
Seja B um conjunto, P ⊆ 2B e A ∈P. Dizemos que
f :P → B
é uma função de escolha quando:
f(A) ∈ A, ∀A ∈P
Exemplos (1/3)
A função f :P → B definida por
A1 7−→ 2
A2 7−→ 4
A3 7−→ 2
é uma função de escolha.
13 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função de Escolha
Definição
Seja B um conjunto, P ⊆ 2B e A ∈P. Dizemos que
f :P → B
é uma função de escolha quando:
f(A) ∈ A, ∀A ∈P
Exemplos (2/3)
A função g :P → B definida por
A1 7−→ 2
A2 7−→ 3
é uma função de escolha.
14 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função de Escolha
Definição
Seja B um conjunto, P ⊆ 2B e A ∈P. Dizemos que
f :P → B
é uma função de escolha quando:
f(A) ∈ A, ∀A ∈P
Exemplos (3/3)
A função h :P → B definida por
A1 7−→ 3
A2 7−→ 1
A3 7−→ 4
não é uma função de escolha.
15 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Injetora
Definição
Seja f uma função.
Dizemos que f é injetora quando
se (a, y) ∈ f e (b, y) ∈ f , (ou seja se f(a) = f(b)) então a = b.
Exemplos (1/2)
idA é uma função injetora.
g = {(1, 3), (2, 3), (3, 2), (4, 4)} não é uma função injetora.
h = {(1, 3), (2, 1), (3, 2), (4, 4)} é uma função injetora.
A relação f = {(x, y) ∈ R× R t. q. xy = 1} é uma
função injetora.
16 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Injetora
Definição
Sejaf uma função.
Dizemos que f é injetora quando
se (a, y) ∈ f e (b, y) ∈ f , (ou seja se f(a) = f(b)) então a = b.
Exemplos (2/2)
A função de escolha e :P → B
definida por
A1 7−→ 3
A2 7−→ 4
A3 7−→ 2
é uma função injetora.
17 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
18 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
19 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
20 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
21 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
22 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
23 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
24 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : R→ R definida por f(x) = x+ 1. Mostre que f é
injetora.
Solução
Sejam x, y ∈ R tais que f(x) = f(y).
Logo, x = x+ 0 (neutro)
= x+ (1− 1)
= (x+ 1)− 1 (associatividade)
= (y + 1)− 1 (hipótese)
= y + (1− 1) (associatividade)
= y + 0
= y (neutro)
Portanto, x = y.
25 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : Z→ Z definida por f(x) = 3x+ 4. Prove que f é
injetora.
Solução
Sejam x, y ∈ Z tais que f(x) = f(y).
Temos que 3x+ 4 = 3y + 4.
Subtraindo 4 de ambos os membros, então 3x = 3y.
Dividindo ambos os membros por 3, obtemos que x = y.
Portanto, x = y.
26 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : Z→ Z definida por f(x) = 3x+ 4. Prove que f é
injetora.
Solução
Sejam x, y ∈ Z tais que f(x) = f(y).
Temos que 3x+ 4 = 3y + 4.
Subtraindo 4 de ambos os membros, então 3x = 3y.
Dividindo ambos os membros por 3, obtemos que x = y.
Portanto, x = y.
27 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : Z→ Z definida por f(x) = 3x+ 4. Prove que f é
injetora.
Solução
Sejam x, y ∈ Z tais que f(x) = f(y).
Temos que 3x+ 4 = 3y + 4.
Subtraindo 4 de ambos os membros, então 3x = 3y.
Dividindo ambos os membros por 3, obtemos que x = y.
Portanto, x = y.
28 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Seja f : Z→ Z definida por f(x) = 3x+ 4. Prove que f é
injetora.
Solução
Sejam x, y ∈ Z tais que f(x) = f(y).
Temos que 3x+ 4 = 3y + 4.
Subtraindo 4 de ambos os membros, então 3x = 3y.
Dividindo ambos os membros por 3, obtemos que x = y.
Portanto, x = y.
29 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Determine se a função f : Z→ Z definida por f(x) = x2 é
injetora.
Solução
Não é injetora pois, f(1) = f(−1) = 1, mas 1 6= −1.
30 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função Injetora
Exemplo
Determine se a função f : Z→ Z definida por f(x) = x2 é
injetora.
Solução
Não é injetora pois, f(1) = f(−1) = 1, mas 1 6= −1.
31 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Sobrejetora
Definição
Seja f : A→ B uma função.
Dizemos que f é sobrejetora quando para cada b ∈ B, existe
a ∈ A tal que f(a) = b, ou seja Imf = B.
Exemplos (1/2)
idA é uma função sobrejetora.
g = {(1, 3), (2, 3), (3, 2), (4, 4)} não é uma função
sobrejetora.
h = {(1, 3), (2, 1), (3, 2), (4, 4)} é uma função sobrejetora.
A relação f = {(x, y) ∈ R× R t. q. xy = 1} não é uma
função sobrejetora.
32 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Sobrejetora
Definição
Seja f : A→ B uma função.
Dizemos que f é sobrejetora quando para cada b ∈ B, existe
a ∈ A tal que f(a) = b, ou seja Imf = B.
Exemplos (2/2)
A função de escolha e :P → B
definida por
e = {(A1, 3), (A2, 1), (A3, 2),
(A4, 4), (A5, 5)}
é uma função sobrejetora.
33 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto deCantor
Bibliografia
Função sobrejetora
Exemplo
Seja a função f : Z→ Z definida por f(x) = x+ 1. Mostre
que f é sobrejetora.
Solução
Seja b ∈ Z.
Consideramos ♥ = b− 1 ∈ Z.
Temos que
f(♥) =
♥+ 1 = (b− 1) + 1 = b
Portanto, f(♥) = b.
34 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja a função f : Z→ Z definida por f(x) = x+ 1. Mostre
que f é sobrejetora.
Solução
Seja b ∈ Z.
Consideramos ♥ = b− 1 ∈ Z.
Temos que
f(♥) =
♥+ 1 = (b− 1) + 1 = b
Portanto, f(♥) = b.
35 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja a função f : Z→ Z definida por f(x) = x+ 1. Mostre
que f é sobrejetora.
Solução
Seja b ∈ Z.
Consideramos ♥ = b− 1 ∈ Z.
Temos que
f(♥) =
♥+ 1 = (b− 1) + 1 = b
Portanto, f(♥) = b.
36 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja a função f : Z→ Z definida por f(x) = x+ 1. Mostre
que f é sobrejetora.
Solução
Seja b ∈ Z.
Consideramos ♥ = b− 1 ∈ Z.
Temos que
f(♥) = ♥+ 1 =
(b− 1) + 1 = b
Portanto, f(♥) = b.
37 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja a função f : Z→ Z definida por f(x) = x+ 1. Mostre
que f é sobrejetora.
Solução
Seja b ∈ Z.
Consideramos ♥ = b− 1 ∈ Z.
Temos que
f(♥) = ♥+ 1 = (b− 1) + 1 =
b
Portanto, f(♥) = b.
38 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja a função f : Z→ Z definida por f(x) = x+ 1. Mostre
que f é sobrejetora.
Solução
Seja b ∈ Z.
Consideramos ♥ = b− 1 ∈ Z.
Temos que
f(♥) = ♥+ 1 = (b− 1) + 1 = b
Portanto, f(♥) = b.
39 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja f : Q→ Q dada por f(x) = 3x+ 4. Prove que f é
sobrejetora.
Solução
Seja b ∈ Q.
Consideramos ♥ = 13(b− 4) ∈ Q.
Note que
f(♥) =
3(♥) + 4 = 3(1
3
(b− 4)) + 4 = b− 4 + 4 = b
Portanto, f(♥) = b.
40 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja f : Q→ Q dada por f(x) = 3x+ 4. Prove que f é
sobrejetora.
Solução
Seja b ∈ Q.
Consideramos ♥ = 13(b− 4) ∈ Q.
Note que
f(♥) =
3(♥) + 4 = 3(1
3
(b− 4)) + 4 = b− 4 + 4 = b
Portanto, f(♥) = b.
41 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja f : Q→ Q dada por f(x) = 3x+ 4. Prove que f é
sobrejetora.
Solução
Seja b ∈ Q.
Consideramos ♥ = 13(b− 4) ∈ Q.
Note que
f(♥) =
3(♥) + 4 = 3(1
3
(b− 4)) + 4 = b− 4 + 4 = b
Portanto, f(♥) = b.
42 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja f : Q→ Q dada por f(x) = 3x+ 4. Prove que f é
sobrejetora.
Solução
Seja b ∈ Q.
Consideramos ♥ = 13(b− 4) ∈ Q.
Note que
f(♥) = 3(♥) + 4 =
3(
1
3
(b− 4)) + 4 = b− 4 + 4 = b
Portanto, f(♥) = b.
43 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja f : Q→ Q dada por f(x) = 3x+ 4. Prove que f é
sobrejetora.
Solução
Seja b ∈ Q.
Consideramos ♥ = 13(b− 4) ∈ Q.
Note que
f(♥) = 3(♥) + 4 = 3(1
3
(b− 4)) + 4 =
b− 4 + 4 = b
Portanto, f(♥) = b.
44 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja f : Q→ Q dada por f(x) = 3x+ 4. Prove que f é
sobrejetora.
Solução
Seja b ∈ Q.
Consideramos ♥ = 13(b− 4) ∈ Q.
Note que
f(♥) = 3(♥) + 4 = 3(1
3
(b− 4)) + 4 = b− 4 + 4 =
b
Portanto, f(♥) = b.
45 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
Seja f : Q→ Q dada por f(x) = 3x+ 4. Prove que f é
sobrejetora.
Solução
Seja b ∈ Q.
Consideramos ♥ = 13(b− 4) ∈ Q.
Note que
f(♥) = 3(♥) + 4 = 3(1
3
(b− 4)) + 4 = b− 4 + 4 = b
Portanto, f(♥) = b.
46 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
A função f : Z→ Z definida por f(x) = x2 é sobrejetora?
Solução
Note que não há número inteiro x com x2 = −1. Logo, f não é
sobrejetora.
47 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Função sobrejetora
Exemplo
A função f : Z→ Z definida por f(x) = x2 é sobrejetora?
Solução
Note que não há número inteiro x com x2 = −1. Logo, f não é
sobrejetora.
48 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Bijetora
Definição
Seja f : A→ B uma função.
Dizemos que f é uma bijeção, ou é uma função bijetora se ela é
injetora e sobrejetora.
Exemplos
idA é uma função bijetora e id−1A = idA.
A função g : Q→ Q definida por f(x) = 3x+ 4 é uma
função bijetora.
h = {(1, 3), (2, 1), (3, 2), (4, 4)} é uma função bijetora.
Seja B um conjunto e P = {{x} | x ∈ B}.
A função de escolha
f :P → B dada por
{x} 7−→ x é bijetora.
49 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
50 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
51 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x= y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
52 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
53 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 =
|y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
54 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| =
y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
55 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
56 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
57 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) =
(♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
58 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) = (♥)2 =
(
√
b)2 = b
Portanto, f(♥) = b.
59 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) = (♥)2 = (
√
b)2 =
b
Portanto, f(♥) = b.
60 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : R+ → R+ dada por f(x) = x2. A função f é bijetora?
Solução
Sejam x, y ∈ R+ tais que f(x) = f(y).
Então x2 = y2.
Note que
x = |x| =
√
x2 =
√
y2 = |y| = y
Portanto, x = y.
Seja b ∈ R+.
Consideramos ♥ = √b ∈ R+.
Observe que
f(♥) = (♥)2 = (
√
b)2 = b
Portanto, f(♥) = b.
61 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : [0, 1]→ (0, 1) definida por
f(x) =

1/2, se x = 0,
1/(n+ 2), se x = 1/n, n ∈ N∗,
x, se x 6= 0, 1/n, n ∈ N∗.
Mostre que f é bijetora.
62 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : [0, 1]→ (0, 1) definida por
f(x) =

1/2, se x = 0,
1/(n+ 2), se x = 1/n, n ∈ N∗,
x, se x 6= 0, 1/n, n ∈ N∗.
Mostre que f é bijetora.
Esboço da Solução (1/3)
Primeiro mostramos que f([0, 1]) ⊆ (0, 1). Seja x ∈ [0, 1].
Caso 1: x = 0, f(0) = 1/2 ∈ (0, 1).
63 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : [0, 1]→ (0, 1) definida por
f(x) =

1/2, se x = 0,
1/(n+ 2), se x = 1/n, n ∈ N∗,
x, se x 6= 0, 1/n, n ∈ N∗.
Mostre que f é bijetora.
Esboço da Solução (1/3)
Primeiro mostramos que f([0, 1]) ⊆ (0, 1). Seja x ∈ [0, 1].
Caso 2: x = 1/n, n ∈ N∗, f(x) = 1/(n+ 2).
Como n > 0, temos que n+ 2 > 2 > 1.
Dividindo a desigualdade 0 < 1 < n+ 2 por n+ 2, temos
0 < 1/(n+ 2) < 1.
64 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : [0, 1]→ (0, 1) definida por
f(x) =

1/2, se x = 0,
1/(n+ 2), se x = 1/n, n ∈ N∗,
x, se x 6= 0, 1/n, n ∈ N∗.
Mostre que f é bijetora.
Esboço da Solução (2/3)
Agora mostramos que f é injetora.
Observe que
f(0) = 1/2 6= 1/(n+ 2) = f(1/n), ∀n ∈ N∗ e
f(1/n) = 1/(n+ 2) 6= 1/(m+ 2) = f(1/m), ∀m,n ∈ N∗,
m 6= n.
Seja x 6= 0, 1/n, ∀n ∈ N∗. Temos que
f(x) = x 6= 1/m, ∀m ∈ N∗.
65 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : [0, 1]→ (0, 1) definida por
f(x) =

1/2, se x = 0,
1/(n+ 2), se x = 1/n, n ∈ N∗,
x, se x 6= 0, 1/n, n ∈ N∗.
Mostre que f é bijetora.
Esboço da Solução (3/3)
Agora mostramos que f é sobrejetora. Seja x ∈ (0, 1).
Logo, x 6= 0, e temos dois casos: x = 1/n, para algum n ∈ N∗
ou não.
Caso 1: x = 1/n. Como x 6= 1, n ≥ 2.
Se n = 2, f(0) = 1/2 = 1/n.
Senão f(1/(n− 2)) = 1/(n− 2 + 2) = 1/n.
66 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Funções
Exemplo
Seja f : [0, 1]→ (0, 1) definida por
f(x) =

1/2, se x = 0,
1/(n+ 2), se x = 1/n, n ∈ N∗,
x, se x 6= 0, 1/n, n ∈ N∗.
Mostre que f é bijetora.
Esboço da Solução (3/3)
Agora mostramos que f é sobrejetora. Seja x ∈ (0, 1).
Logo, x 6= 0, e temos dois casos: x = 1/n, para algum n ∈ N∗
ou não.
Caso 2: x 6= 1/n.
f(x) = x.
67 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
CardinalidadeEnumerabilidade
Conjunto de
Cantor
Bibliografia
Função inversa
Pergunta
Seja f : A→ B uma função.
Quando a relação f−1 é uma função de B para A?
Observação
Seja f uma relação.
Domf−1 = Imf
e
Imf−1 = Domf
68 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Para a inversa ser uma função de B para A
Teorema
Seja f : A→ B uma função.
A relação inversa f−1 é uma função de B para A.
(f−1 : B → A) se e somente se f é bijetora.
Exemplos
idA é uma função bijetora e id−1A = idA.
A função f : Q→ Q definida por f(x) = 3x+ 4 é uma
função bijetora e f−1 é definida por f−1(x) = (x− 4)/3.
h = {(1, 3), (2, 1), (3, 2), (4, 4)} é uma função bijetora.
69 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Composição de função
Definição e resultado
Sejam f : A→ B e g : B → C funções. Então, a relação g ◦ f
é uma função de A para C definida por (g ◦ f)(x) = g(f(x)).
Exemplos
Consideramos f : Q→ Q e g : Q→ Q definidas por
f(x) = x2 e g(x) = x+ 1. Então, temos que
(f ◦ g)(x) = (x+ 1)2 = x2 + 2x+ 1 e
(g ◦ f)(x) = x2 + 1.
Consideramos f : Q→ Q e g : Q→ Q definidas por
f(x) = x2 + x e g(x) = 3x+ 1. Então, temos que
(f ◦ g)(x) = (3x+ 1)2 + 3x+ 1 = 9x2 + 9x+ 2 e
(g ◦ f)(x) = 3(x2 + x) + 1 = 3x2 + 3x+ 1
70 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Alguns resultados
Proposição
Seja f : A→ B uma função.
1 se f é bijetora então f ◦ f−1 = idB e f−1 ◦ f = idA
2 se existe g : B → A uma função tal que f ◦ g = idB e
g ◦ f = idA então f é bijetora e f−1 = g.
3 f ◦ idA = f = idB ◦ f .
71 / 157
MD
DC
Revisão
Funções
Injetora
Sobrejetora
Bijetora
Inversa
Composição
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Alguns resultados
Proposição
Sejam f : A→ B e g : B → C funções.
Se g ◦ f é injetora então f é injetora.
Se g ◦ f é sobrejetora então g é sobrejetora.
Se g ◦ f é bijetora então f é injetora e g é sobrejetora.
Se f e g são injetoras então g ◦ f é injetora.
Se f e g são sobrejetoras então g ◦ f é sobrejetora.
Se f e g são bijetoras então g ◦ f é bijetora.
72 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Definição
Um conjunto finito é um conjunto que possui uma
quantidade finita de elementos.
A cardinalidade de um conjunto finito é o valor desta
quantidade. Denotamos por |A| a cardinalidade de A.
Um conjunto é dito infinito se não for finito.
Exemplo
Consideramos D = {x ∈ Z t. q. x | 10}. Então, D é um
conjunto finito e |D| = 8
Consideramos C = {♣,♦,♥,♠}. Então, C é um conjunto
finito e |C| = 4.
O conjunto N é infinito.
|∅| = 0.
73 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Definição
Um conjunto finito é um conjunto que possui uma
quantidade finita de elementos.
A cardinalidade de um conjunto finito é o valor desta
quantidade. Denotamos por |A| a cardinalidade de A.
Um conjunto é dito infinito se não for finito.
Observações
Cardinalidade de conjuntos finitos define uma relação de
equivalência.
Reflexiva: |A| = |A| para qualquer conjunto A.
Simétrica: Se |A| = |B|, então |B| = |A|.
Transitiva: Se |A| = |B| e |B| = |C|, então |A| = |C|.
74 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Finito vs. Infinito
Um conjunto é infinito se ele tem a cardinalidade de algum
subconjunto próprio dele mesmo.
Caso contrário o conjunto é finito.
75 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
E a cardinalidade dos conjuntos infinitos?
Como saber se dois conjuntos têm a mesma cardinalidade?
Se os dois conjuntos forem finitos, basta contar a
quantidade de elementos de cada um e comparar se as
quantidades são iguais.
Mas, como comparar a cardinalidade de dois conjuntos
infinitos?
76 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Mais sobre Cardinalidade
Cardinalidade de conjuntos finitos e infinitos é definida
utilizando funções bijetoras.
A cardinalidade de um conjunto A é:
Finita: se A = ∅: |A| = 0, ou existe uma bijeção entre A
e o conjunto {1, 2, 3, . . . , n} para algum n ∈ N∗: |A| = n.
Infinita: se existe uma bijeção entre A e um subconjunto
próprio de A.
Portanto, um conjunto A é um:
Conjunto finito se for possível representá-lo por extensão
(listar exaustivamente todos os seus elementos).
Conjunto infinito se for possível retirar alguns elementos
de A e, mesmo assim, estabelecer uma bijeção com A.
77 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Mais sobre Cardinalidade
Cardinalidade de conjuntos finitos e infinitos é definida
utilizando funções bijetoras.
A cardinalidade de um conjunto A é:
Finita: se A = ∅: |A| = 0, ou existe uma bijeção entre A
e o conjunto {1, 2, 3, . . . , n} para algum n ∈ N∗: |A| = n.
Infinita: se existe uma bijeção entre A e um subconjunto
próprio de A.
Portanto, um conjunto A é um:
Conjunto finito se for possível representá-lo por extensão
(listar exaustivamente todos os seus elementos).
Conjunto infinito se for possível retirar alguns elementos
de A e, mesmo assim, estabelecer uma bijeção com A.
78 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Mais sobre Cardinalidade
Cardinalidade de conjuntos finitos e infinitos é definida
utilizando funções bijetoras.
A cardinalidade de um conjunto A é:
Finita: se A = ∅: |A| = 0, ou existe uma bijeção entre A
e o conjunto {1, 2, 3, . . . , n} para algum n ∈ N∗: |A| = n.
Infinita: se existe uma bijeção entre A e um subconjunto
próprio de A.
Portanto, um conjunto A é um:
Conjunto finito se for possível representá-lo por extensão
(listar exaustivamente todos os seus elementos).
Conjunto infinito se for possível retirar alguns elementos
de A e, mesmo assim, estabelecer uma bijeção com A.
79 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Definição
Dois conjuntos A e B têm a mesma cardinalidade se existe
uma função bijetora f : A→ B.
Notação: |A| = |B|.
Observações
Esta definição é válida para conjuntos finitos e infinitos.
Cardinalidade é uma relação de equivalência também para
conjuntos infinitos.
80 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Definição
Dois conjuntos A e B têm a mesma cardinalidade se existe
uma função bijetora f : A→ B.
Notação: |A| = |B|.
Exemplos
Sejam A = {0, 1, 2} e B = {−2,−1, 0}. |A| = |B|.
Sejam C = {♣,♦,♥,♠} e D = {1, 2, 3, 4}. |C| = |D|.
|N| = |N∗|.
|N∗| = |Z|.
|[0, 1]| = |R|.
81 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Proposição 1
Sejam A e B dois conjuntos finitos e f : A→ B uma função.
Se f é injetora então |A| ≤ |B|.
Se f é sobrejetora então |A| ≥ |B|.
Proposição 2
Sejam A e B dois conjuntos finitos tais que |A| = |B| e
f : A→ B uma função.
As seguintes condições são equivalentes:
f é injetora.
f é sobrejetora.
f é bijetora.
82 / 157
MD
DC
RevisãoFunções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Teorema de Cantor-Bernstein-Schröeder
Sejam A e B dois conjuntos.
Se existem funções injetoras f : A→ B e g : B → A, então
existe uma bijeção h : A→ B.
Veja mais
A prova deste teorema pode ser encontrada em Hammack [2].
83 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Teorema de Cantor-Bernstein-Schröeder
Sejam A e B dois conjuntos.
Se existem funções injetoras f : A→ B e g : B → A, então
existe uma bijeção h : A→ B.
Observação (1/2)
A partir do Teorema de Cantor-Bernstein-Schröeder, a
Proposição 1 pode ser extendida também para conjuntos
infinitos.
Assim, para dois conjuntos A e B, se |A| ≤ |B| e |B| ≤ |A|,
então |A| = |B|.
84 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Teorema de Cantor-Bernstein-Schröeder
Sejam A e B dois conjuntos.
Se existem funções injetoras f : A→ B e g : B → A, então
existe uma bijeção h : A→ B.
Observação (2/2)
A Proposição 2 não pode ser extendida para conjuntos infinitos.
Seja f : N→ N definida por
f(x) = x+ 1
Note que f é injetora, mas f não é sobrejetora.
85 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exemplo
Mostre que N = {0, 1, 2, 3, . . . } e N∗ = {1, 2, 3, . . . } têm a
mesma cardinalidade.
Demonstração
Considere a função f : N→ N∗ definida por f(x) = x+ 1.
Note que f é bijetora. Portanto |N| = |N∗|.
Observação
A partir deste exemplo fica clara a definição de conjunto
infinito através de subconjunto próprio.
O conjunto N é infinito, pois existe uma bijeção
f : N→ N∗ ⊂ N.
86 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exemplo
Mostre que N = {0, 1, 2, 3, . . . } e N∗ = {1, 2, 3, . . . } têm a
mesma cardinalidade.
Demonstração
Considere a função f : N→ N∗ definida por f(x) = x+ 1.
Note que f é bijetora. Portanto |N| = |N∗|.
Observação
A partir deste exemplo fica clara a definição de conjunto
infinito através de subconjunto próprio.
O conjunto N é infinito, pois existe uma bijeção
f : N→ N∗ ⊂ N.
87 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exemplo
Mostre que N = {0, 1, 2, 3, . . . } e N∗ = {1, 2, 3, . . . } têm a
mesma cardinalidade.
Demonstração
Considere a função f : N→ N∗ definida por f(x) = x+ 1.
Note que f é bijetora. Portanto |N| = |N∗|.
Observação
A partir deste exemplo fica clara a definição de conjunto
infinito através de subconjunto próprio.
O conjunto N é infinito, pois existe uma bijeção
f : N→ N∗ ⊂ N.
88 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exemplo
Mostre que N∗ = {1, 2, 3, . . . } e P = {2, 4, 6, . . . } têm a
mesma cardinalidade.
Demonstração
Considere a função f : N∗ → P definida por f(x) = 2x.
Note que f é bijetora. Portanto |N∗| = |P |.
89 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exemplo
Mostre que N∗ = {1, 2, 3, . . . } e P = {2, 4, 6, . . . } têm a
mesma cardinalidade.
Demonstração
Considere a função f : N∗ → P definida por f(x) = 2x.
Note que f é bijetora. Portanto |N∗| = |P |.
90 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exemplo
Mostre que G = [0, 1] e H = [4, 7] têm a mesma cardinalidade.
Demonstração
Considere a função f : G→ H definida por f(x) = 3x+ 4.
Como f é bijetora, |G| = |H|.
91 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exemplo
Mostre que G = [0, 1] e H = [4, 7] têm a mesma cardinalidade.
Demonstração
Considere a função f : G→ H definida por f(x) = 3x+ 4.
Como f é bijetora, |G| = |H|.
92 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exercício
Mostre que |N| = |Z|.
Dica
Considere a função bijetora f : N→ Z definida por
f(n) =
{
−n/2 se n é par,
(n+ 1)/2 se n é ímpar.
93 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Exercício
Mostre que |N| = |Z|.
Dica
Considere a função bijetora f : N→ Z definida por
f(n) =
{
−n/2 se n é par,
(n+ 1)/2 se n é ímpar.
94 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Cardinalidade
Georg Cantor (1845-1918)
A teoria de conjuntos moderna se deve ao matemático
alemão Georg Cantor.
Antes de Cantor, dois conjuntos infinitos eram
considerados com a mesma cardinalidade.
Com as ideias revolucionárias de Cantor e seu famoso
Método da Diagonal pode-se demonstrar um fato até então
impensável: que existem infinitos maiores do que outros!
95 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Definições
Um conjunto A é enumerável, se |A| = |N|.
Um conjunto A é contável, se A é finito ou enumerável, e
não enumerável se A é infinito e |A| 6= |N|.
Um conjunto A é contínuo, se |A| = |R|.
Exemplos de Conjuntos Enumeráveis
A = {1, 1/2, 1/3, . . . , 1/n, . . . }
P = {2, 4, 6, . . . }
N∗ = {1, 2, 3, . . . }
N∗ × N∗ = {(1, 1), (2, 1), (1, 2), (1, 3), (2, 2), (3, 1), . . . }
S = {a, aa, aaa, . . . }
96 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Observações
Um conjunto enumerável é um conjunto contável infinito.
A cardinalidade dos números naturais é denotada por ℵ0
(aleph zero), isto é, |N| = ℵ0.
Qualquer conjunto contável infinito tem cardinalidade ℵ0.
Um conjunto enumerável pode ser escrito numa lista
infinita x1, x2, x3, x4 . . .
A cardinalidade dos números reais é denotada por c
(contínuo), assim, |R| = c.
97 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que o conjunto dos inteiros positivos pares é enumerável.
Demonstração
Seja P = {2, 4, 6, . . . } o conjunto dos inteiros positivos pares.
Para provar que P é enumerável, mostramos que |N| = |P |.
Considere a função f : N∗ → P definida por f(x) = 2x.
Note que f é bijetora, assim |N∗| = |N| = |P |.
Portanto P é enumerável.
98 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que o conjunto dos inteiros positivos pares é enumerável.
Demonstração
Seja P = {2, 4, 6, . . . } o conjunto dos inteiros positivos pares.
Para provar que P é enumerável, mostramos que |N| = |P |.
Considere a função f : N∗ → P definida por f(x) = 2x.
Note que f é bijetora, assim |N∗| = |N| = |P |.
Portanto P é enumerável.
99 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que o conjunto dos inteiros positivos pares é enumerável.
Demonstração
Seja P = {2, 4, 6, . . . } o conjunto dos inteiros positivos pares.
Para provar que P é enumerável, mostramos que |N| = |P |.
Considere a função f : N∗ → P definida por f(x) = 2x.
Note que f é bijetora, assim |N∗| = |N| = |P |.
Portanto P é enumerável.
100 / 157
MD
DC
Revisão
Funções
CardinalidadeEnumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo: Hotel de Hilbert
O Hotel de Hilbert possui infinitos quartos e cada quarto
está ocupado por um hóspede. E se chegar um novo
hóspede?
O hotel está lotado, no sentido de que todos os quartos
estão ocupados, mas não no sentido de que não caiba mais
hóspedes.
101 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo: Hotel de Hilbert
Se o hotel tivesse uma quantidade finita de quartos não
seria mais possível acomodar um novo hóspede.
Como o hotel possui um número infinito de quartos então
se movermos o hóspede do quarto 1 para o quarto 2, o
hóspede do quarto 2 para o quarto 3 e assim por diante,
movendo o hóspede do quarto n para o quarto n+ 1,
podemos acomodar o novo hóspede no quarto 1.
102 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Primeiro Desafio: Alocar um número infinito de novos
clientes
Por um argumento análogo é possível alocar um número
infinito (enumerável) de novos clientes (um ônibus com
infinitos passageiros).
Apenas mova o hóspede do quarto 1 para o quarto 2, o
hóspede do quarto 2 para o quarto 4, e em geral do quarto
n para o quarto 2n, assim todos os quartos de número
ímpar estarão livres para os novos hóspedes.
103 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Segundo Desafio: Alocar os passageiros de uma excursão
com infinitos ônibus cada um com infinitos passageiros
O gerente resolve este problema realocando seus hóspedes:
desta vez, um hóspede que esteja no quarto n deverá se
mudar para o quarto 2n.
O gerente dispõe de infinitas vagas novamente.
Depois, o gerente associa a cada ônibus um número primo
diferente de dois. Então, ele acomoda os passageiros
segundo a seguinte regra: o passageiro que está na cadeira
n do ônibus p ocupará o quarto de número pn.
104 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Hotel de Hilbert
Observe que em todas as situações anteriores sempre
conseguimos enumerar a quantidade de hóspedes e os
quartos do Hotel, ou seja, é possível construir uma bijeção
entre N e a quantidade de hóspedes.
105 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto Q+ dos números racionais positivos é enumerável.
...
5
1
4
1
3
1
2
1
1
1
...
5
2
4
2
3
2
2
2
1
2
...
5
3
4
3
3
3
2
3
1
3
...
5
4
4
4
3
4
2
4
1
4
...
5
5
4
5
3
5
2
5
1
5
...
5
6
4
6
3
6
2
6
1
6
· · ·
· · ·
· · ·
· · ·
· · ·
106 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Cardinalidade de Conjuntos Infinitos
Vimos que a cardinalidade de conjuntos está associada à
existência de uma bijeção entre eles.
Através das ideias de Cantor, é possível demonstrar que
existem conjuntos infinitos maiores que outros.
Mas, afinal, quais conjuntos infinitos têm cardinalidade
diferente?
A técnica que veremos a seguir é chamada “método da
diagonalização”.
107 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (1/6)
Por contradição, suponha que A é enumerável.
Assim podemos listar, em sequência, os elementos de A.
A = {x1, x2, x3, . . . }
108 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (2/6)
Cada elemento em A pode ser escrito na sua forma decimal.
Para os números que podem ser escritos de duas formas, por
exemplo 1.0 e 0.9, para evitar escrever o mesmo elemento duas
vezes, optamos (arbitrariamente) pela segunda representação.
Mas 1.0 = 0.9 mesmo?
Note que
1
3
= 0.3
1 = 0.9 (multiplicando por 3)
109 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (3/6)
Listamos cada elemento de A na sua forma decimal:
x1 = 0.d11d12d13 . . .
x2 = 0.d21d22d23 . . .
x3 = 0.d31d32d33 . . .
... =
...
...
...
. . .
onde dij ∈ {0, 1, . . . , 9}.
110 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (4/6)
Agora construímos um número real
y = 0.p1p2p3 . . .
da seguinte maneira:
pi =
{
6 se dii = 5,
5 caso contrário.
111 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (5/6)
Por exemplo, se a enumeração começar com
x1 = 0.342134 . . .
x2 = 0.257001 . . .
x3 = 0.546122 . . .
x4 = 0.716525 . . .
y seria 0.5656 . . . .
Note que y ∈ A, já que y é um número real entre 0 e 1.
112 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (6/6)
Se compararmos y com a enumeração do conjunto, y é
diferente do primeiro número na primeira casa decimal, do
segundo número na segunda casa decimal, e assim por diante.
Como y não contém zeros à direita do ponto decimal, ele não é
a representação alternativa de qualquer número da enumeração.
Portanto, y não é igual a qualquer elemento na enumeração.
Mas a enumeração é suposta a incluir todos os elementos do
conjunto, uma contradição.
113 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (6/6)
Se compararmos y com a enumeração do conjunto, y é
diferente do primeiro número na primeira casa decimal, do
segundo número na segunda casa decimal, e assim por diante.
Como y não contém zeros à direita do ponto decimal, ele não é
a representação alternativa de qualquer número da enumeração.
Portanto, y não é igual a qualquer elemento na enumeração.
Mas a enumeração é suposta a incluir todos os elementos do
conjunto, uma contradição.
114 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (6/6)
Se compararmos y com a enumeração do conjunto, y é
diferente do primeiro número na primeira casa decimal, do
segundo número na segunda casa decimal, e assim por diante.
Como y não contém zeros à direita do ponto decimal, ele não é
a representação alternativa de qualquer número da enumeração.
Portanto, y não é igual a qualquer elemento na enumeração.
Mas a enumeração é suposta a incluir todos os elementos do
conjunto, uma contradição.
115 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Demonstração (6/6)
Se compararmos y com a enumeração do conjunto, y é
diferente do primeiro número na primeira casa decimal, do
segundo número na segunda casa decimal, e assim por diante.
Comoy não contém zeros à direita do ponto decimal, ele não é
a representação alternativa de qualquer número da enumeração.
Portanto, y não é igual a qualquer elemento na enumeração.
Mas a enumeração é suposta a incluir todos os elementos do
conjunto, uma contradição.
116 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
O conjunto A = [0, 1] não é enumerável.
Observação
Lembrando que |[0, 1]| = |R|, o teorema acima indica a
existência de pelo menos dois conjuntos infinitos com
tamanhos diferentes: N e R.
117 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Voltando ao Exemplo do Hotel de Hilbert
Se chegasse um grupo infinito de hóspedes ao Hotel de
Hilbert, contendo um novo hóspede para cada numero real,
o gerente poderia hospedá-los?
Não! Não é possível enumerar um número natural para
cada número real.
118 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Voltando ao Exemplo do Hotel de Hilbert
De fato, o conjunto dos números reais possui uma
cardinalidade maior do que a dos números naturais e,
portanto é “maior” do que ℵ0.
Quando se tinha conjuntos infinitos enumeráveis de
hóspedes para se acomodar no Hotel, sempre se conseguia
reorganizar os hóspedes, mas no momento que você tem
uma quantidade infinita não enumerável (números Reais)
surge um problema, afinal existem infinitos “maiores” que
outros.
119 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Devemos mostrar uma função bijetora f : R→ (0, 1).
Considere a função f : R→ (0, 1) definida por
f(x) =
1
1 + ex
120 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é injetora.
Sejam x, y ∈ R tais que f(x) = f(y).
Logo,
1
1 + ex
=
1
1 + ey
1 + ey = 1 + ex
ey = ex
y = x
x = y
Portanto, x = y.
121 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é injetora.
Sejam x, y ∈ R tais que f(x) = f(y).
Logo,
1
1 + ex
=
1
1 + ey
1 + ey = 1 + ex
ey = ex
y = x
x = y
Portanto, x = y.
122 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é injetora.
Sejam x, y ∈ R tais que f(x) = f(y).
Logo,
1
1 + ex
=
1
1 + ey
1 + ey = 1 + ex
ey = ex
y = x
x = y
Portanto, x = y.
123 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é injetora.
Sejam x, y ∈ R tais que f(x) = f(y).
Logo,
1
1 + ex
=
1
1 + ey
1 + ey = 1 + ex
ey = ex
y = x
x = y
Portanto, x = y.
124 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é injetora.
Sejam x, y ∈ R tais que f(x) = f(y).
Logo,
1
1 + ex
=
1
1 + ey
1 + ey = 1 + ex
ey = ex
y = x
x = y
Portanto, x = y.
125 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é injetora.
Sejam x, y ∈ R tais que f(x) = f(y).
Logo,
1
1 + ex
=
1
1 + ey
1 + ey = 1 + ex
ey = ex
y = x
x = y
Portanto, x = y.
126 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é sobrejetora.
Seja b ∈ (0, 1).
Consideramos ♥ = ln(1b − 1) ∈ R.
Temos que
f(♥) =
1
1 + e♥
=
1
1 + eln(
1
b
−1) =
1
1 + 1b − 1
=
1
1
b
= b
Portanto, f(♥) = b.
127 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é sobrejetora.
Seja b ∈ (0, 1).
Consideramos ♥ = ln(1b − 1) ∈ R.
Temos que
f(♥) =
1
1 + e♥
=
1
1 + eln(
1
b
−1) =
1
1 + 1b − 1
=
1
1
b
= b
Portanto, f(♥) = b.
128 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é sobrejetora.
Seja b ∈ (0, 1).
Consideramos ♥ = ln(1b − 1) ∈ R.
Temos que
f(♥) =
1
1 + e♥
=
1
1 + eln(
1
b
−1) =
1
1 + 1b − 1
=
1
1
b
= b
Portanto, f(♥) = b.
129 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é sobrejetora.
Seja b ∈ (0, 1).
Consideramos ♥ = ln(1b − 1) ∈ R.
Temos que
f(♥) = 1
1 + e♥
=
1
1 + eln(
1
b
−1) =
1
1 + 1b − 1
=
1
1
b
= b
Portanto, f(♥) = b.
130 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é sobrejetora.
Seja b ∈ (0, 1).
Consideramos ♥ = ln(1b − 1) ∈ R.
Temos que
f(♥) = 1
1 + e♥
=
1
1 + eln(
1
b
−1) =
1
1 + 1b − 1
=
1
1
b
= b
Portanto, f(♥) = b.
131 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é sobrejetora.
Seja b ∈ (0, 1).
Consideramos ♥ = ln(1b − 1) ∈ R.
Temos que
f(♥) = 1
1 + e♥
=
1
1 + eln(
1
b
−1) =
1
1 + 1b − 1
=
1
1
b
= b
Portanto, f(♥) = b.
132 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exemplo
Mostre que |R| = |(0, 1)|.
Demonstração
Mostraremos que f é sobrejetora.
Seja b ∈ (0, 1).
Consideramos ♥ = ln(1b − 1) ∈ R.
Temos que
f(♥) = 1
1 + e♥
=
1
1 + eln(
1
b
−1) =
1
1 + 1b − 1
=
1
1
b
= b
Portanto, f(♥) = b.
133 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Exercício
1 Mostre que |[0, 1]| = |(0, 1)|.
Dica
Utilize a função do slide 23:
Seja f : [0, 1]→ (0, 1) definida por
f(x) =

1/2, se x = 0,
1/(n+ 2), se x = 1/n, n ∈ N∗,
x, se x 6= 0, 1/n, n ∈ N∗.
134 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (1/2)
Por contradição, suponha que |A| = |2A|.
Considere uma função bijetora f : A→ 2A.
Para qualquer elemento a ∈ A, f(a) é um elemento de 2A, de
forma que f(a) é um conjunto que contém alguns elementos de
A e possivelmente contém o próprio a.
135 / 157
MD
DC
Revisão
FunçõesCardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (1/2)
Por contradição, suponha que |A| = |2A|.
Considere uma função bijetora f : A→ 2A.
Para qualquer elemento a ∈ A, f(a) é um elemento de 2A, de
forma que f(a) é um conjunto que contém alguns elementos de
A e possivelmente contém o próprio a.
136 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (1/2)
Por contradição, suponha que |A| = |2A|.
Considere uma função bijetora f : A→ 2A.
Para qualquer elemento a ∈ A, f(a) é um elemento de 2A, de
forma que f(a) é um conjunto que contém alguns elementos de
A e possivelmente contém o próprio a.
137 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (2/2)
Definimos agora um conjunto S = {x ∈ A | x /∈ f(x)}.
Como S ⊆ A, S ∈ 2A então ∃y ∈ A tal que f(y) = S. Assim y
pode ser ou não um elemento de S.
Se y ∈ S, então, pela definição de S, y /∈ f(y), mas como
f(y) = S, y /∈ S.
Por outro lado, se y /∈ S, então, uma vez que S = f(y),
y /∈ f(y) e, pela definição de S, y ∈ S.
Em ambos os casos, chegamos a uma contradição.
138 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (2/2)
Definimos agora um conjunto S = {x ∈ A | x /∈ f(x)}.
Como S ⊆ A, S ∈ 2A então ∃y ∈ A tal que f(y) = S. Assim y
pode ser ou não um elemento de S.
Se y ∈ S, então, pela definição de S, y /∈ f(y), mas como
f(y) = S, y /∈ S.
Por outro lado, se y /∈ S, então, uma vez que S = f(y),
y /∈ f(y) e, pela definição de S, y ∈ S.
Em ambos os casos, chegamos a uma contradição.
139 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (2/2)
Definimos agora um conjunto S = {x ∈ A | x /∈ f(x)}.
Como S ⊆ A, S ∈ 2A então ∃y ∈ A tal que f(y) = S. Assim y
pode ser ou não um elemento de S.
Se y ∈ S, então, pela definição de S, y /∈ f(y), mas como
f(y) = S, y /∈ S.
Por outro lado, se y /∈ S, então, uma vez que S = f(y),
y /∈ f(y) e, pela definição de S, y ∈ S.
Em ambos os casos, chegamos a uma contradição.
140 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (2/2)
Definimos agora um conjunto S = {x ∈ A | x /∈ f(x)}.
Como S ⊆ A, S ∈ 2A então ∃y ∈ A tal que f(y) = S. Assim y
pode ser ou não um elemento de S.
Se y ∈ S, então, pela definição de S, y /∈ f(y), mas como
f(y) = S, y /∈ S.
Por outro lado, se y /∈ S, então, uma vez que S = f(y),
y /∈ f(y) e, pela definição de S, y ∈ S.
Em ambos os casos, chegamos a uma contradição.
141 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema de Cantor
Para qualquer conjunto A, os dois conjuntos A e 2A não têm a
mesma cardinalidade.
Demonstração (2/2)
Definimos agora um conjunto S = {x ∈ A | x /∈ f(x)}.
Como S ⊆ A, S ∈ 2A então ∃y ∈ A tal que f(y) = S. Assim y
pode ser ou não um elemento de S.
Se y ∈ S, então, pela definição de S, y /∈ f(y), mas como
f(y) = S, y /∈ S.
Por outro lado, se y /∈ S, então, uma vez que S = f(y),
y /∈ f(y) e, pela definição de S, y ∈ S.
Em ambos os casos, chegamos a uma contradição.
142 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
Os conjuntos [0, 1) e (0, 1) têm a mesma cardinalidade.
Demonstração
Sejam as duas funções f : [0, 1)→ (0, 1) e g : (0, 1)→ [0, 1)
definidas por
f(x) =
1
4
+
1
2
x
g(x) = x.
Como f e g são injetoras, o Teorema de
Cantor-Bernstein-Schröeder implica que existe uma bijeção
h : [0, 1)→ (0, 1).
Portanto |[0, 1)| = |(0, 1)|.
143 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
Os conjuntos R e 2N têm a mesma cardinalidade.
Demonstração (1/4)
Como |R| = |(0, 1)| = |[0, 1)|, mostraremos que |[0, 1)| = |2N|.
Pelo Teorema de Cantor-Bernstein-Schröeder é suficiente
mostrar funções injetoras f : [0, 1)→ 2N e g : 2N → [0, 1).
Para a definição de f , utilizamos o fato de que qualquer
número em [0, 1) tem uma única representação decimal.
Lembre-se que, por exemplo, que 0.359 = 0.36.
144 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
Os conjuntos R e 2N têm a mesma cardinalidade.
Demonstração (2/4)
Seja f : [0, 1)→ 2N definida por
f(0.b1b2 . . . ) = {10b1, 102b2, . . . }
Por exemplo, f(0.05) = {0, 500} e
f(0.12) = {10, 200, 1000, 20000, . . . }.
Mostraremos que f é injetora.
Sejam dois números diferentes 0.b1b2 . . . e 0.d1d2 . . . em [0, 1).
Então, bi 6= di, para algum i.
Logo, bi10i ∈ f(0.b1b2 . . . ), mas bi10i /∈ f(0.d1d2 . . . ).
Portanto f(0.b1b2 . . . ) 6= f(0.d1d2 . . . ).
145 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
Os conjuntos R e 2N têm a mesma cardinalidade.
Demonstração (3/4)
Agora, seja g : 2N → [0, 1) definida por
g(X) = 0.b1b2 . . .
onde
bi =
{
1 se i ∈ X,
0 caso contrário.
Por exemplo, g({1, 3}) = 0.101, g({2, 4, 6, . . . }) = 0.01,
g(∅) = 0 e g(N) = 0.1.
Mostraremos que g é injetora.
146 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Teorema
Os conjuntos R e 2N têm a mesma cardinalidade.
Demonstração (4/4)
Sejam dois conjuntos X e Y tais que X 6= Y .
Então, existe ao menos um inteiro i que pertence ou a X ou Y .
Logo, g(X) 6= g(Y ), porque eles diferem no i-ésimo dígito
decimal.
A partir das funções injetoras f : [0, 1)→ 2N e g : 2N → [0, 1),
o Teorema de Cantor-Bernstein-Schröeder implica que existe
uma bijeção h : [0, 1)→ 2N.
Portanto, |[0, 1)| = |2N| e concluímos |R| = |2N|.
147 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Relação entre |N| e |R|
Vimos que |N| = ℵ0 e |R| = c.
Pelo Teorema de Cantor |N| < |R|.
Por quase um século depois que Cantor formulou suas teorias
sobre conjuntos infinitos, vários matemáticos trabalharam com
a questão de se existe ou não um conjunto A para o qual
ℵ0 < |A| < c
A suspeita comum era que nenhum desses conjuntos existe, mas
ninguém foi capaz para provar ou refutar isso. A proposição
dessa não existência foi chamada de Hipótese do Contínuo.
148 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Hipótese do Contínuo
Não existe número cardinal β tal que ℵ0 < β < c.
Observações (1/3)
Em 1931, o lógico Kurt Gödel provou que para qualquer
sistema axiomático existem proposições que não podem ser
comprovadas nem refutadas dentro do sistema.
Mais tarde, eleprovou que a negação da Hipótese do
Contínuo não pode ser provada dentro dos axiomas padrão
da teoria dos conjuntos.
Isso significa que ou a Hipótese do Contínuo é falsa e não
pode ser provada falsa, ou é verdadeira.
149 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Hipótese do Contínuo
Não existe número cardinal β tal que ℵ0 < β < c.
Observações (2/3)
Em 1964, Paul Cohen mostrou que dadas as leis da lógica
e dos axiomas da teoria dos conjuntos, nenhuma prova
pode deduzir a Hipótese do Contínuo.
Em essência, ele provou que a Hipótese do Contínuo não
pode ser provada.
150 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Enumerabilidade
Hipótese do Contínuo
Não existe número cardinal β tal que ℵ0 < β < c.
Observações (3/3)
Em conjunto, os resultados de Gödel e Cohen significam
que os axiomas padrão da matemática não podem “decidir”
se a Hipótese do Contínuo é verdadeira ou falsa e que
nenhum conflito lógico pode surgir de afirmar ou negar a
Hipótese.
Somos livres de aceitá-la como verdadeira ou falsa, e as
duas escolhas levam a diferentes, mas igualmente versões
consistentes da teoria dos conjuntos.
151 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Conjunto de Cantor
História
Foi descoberto em 1874 por Henry John Stephen Smith e
introduzido por Georg Cantor em 1883.
Propriedades
Possui aplicações em Topologia, Geometria e Teoria dos
Conjuntos.
Tem a mesma cardinalidade do conjunto dos números reais.
Possui medida nula.
Pode ser visto como um fractal (autossimilaridade).
152 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Conjunto de Cantor
Figura: Exemplo de um fractal.
153 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Conjunto de Cantor
Construção do Conjunto de Cantor
Parte-se do intervalo A0 = [0, 1],
No passo 1, retira-se o terço do meio do intervalo:
A1 =
[
0,
1
3
]
∪
[
2
3
, 1
]
154 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Conjunto de Cantor
Construção do Conjunto de Cantor
No passo 2, retira-se o terço do meio de cada um dos dois
intervalos criados pelo passo 1:
A2 =
[
0,
1
9
]
∪
[
2
9
,
3
9
]
∪
[
6
9
,
7
9
]
∪
[
8
9
, 1
]
Recursivamente, no passo n, retira-se o terço do meio de
cada um dos intervalos criados pelo passo n− 1.
155 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Conjunto de Cantor
Construção do Conjunto de Cantor
O Conjunto de Cantor é a intersecção dos conjuntos An
produzidos:
C =
∞⋂
n=1
An
156 / 157
MD
DC
Revisão
Funções
Cardinalidade
Enumerabilidade
Conjunto de
Cantor
Bibliografia
Referências Bibliográficas I
[1] Gersting, J. L.
Fundamentos Matemáticos para a Ciência da Computação.
5a. edição, Editora LTC, 2004.
[2] Hammack, R. H.
Book of Proof.
Richard Hammack, 2013.
Disponível em: https://www.people.vcu.edu/~rhammack/BookOfProof/.
Acesso em janeiro de 2018.
[3] Lipschutz, S.
Theory and problems of set theory and related topics.
New York, Schaum, 1964.
[4] Rosen, K. H.
Matemática Discreta e suas aplicações.
6a. edição, Editora McGraw Hill, 2009.
[5] Scheinerman, E. R.
Matemática Discreta, Uma introdução.
Thomson Pioneira, 2003.
157 / 157
	Revisão
	Conjuntos
	Relações
	Funções
	Injetora
	Sobrejetora
	Bijetora
	Inversa
	Composição
	Cardinalidade
	Enumerabilidade
	Conjunto de Cantor
	Bibliografia