Logic2015

e �xo. É necessário (e su�ci-
ente) demonstrar que existe único z ∈ C tal que
(x, z) ∈ g ◦ f.
Notemos que tal z existe: z = g(f(x)). De fato, se
y = f(x), então
(x, y) ∈ f ∧ (y, z) ∈ g.
Daqui (x, z) ∈ g ◦ f .
Suponhamos que existe mais um z1 ∈ C tal que
(x, z1) ∈ g ◦ f . Para esse z1 existe um y1:
(x, y1) ∈ f ∧ (y1, z1) ∈ g.
Daqui y1 = f(x), z1 = g(y1) = g(f(x)) = z.
Exemplo 11.3. Sejam f, g : R→ R,
f(x) = x2, g(x) =
x
x2 + 1
.
Achar g ◦ f e f ◦ g.
Temos
g ◦ f(x) = g(x2) = x
2
x4 + 1
,
f ◦ g(x) =
(
x
x2 + 1
)2
.
11.2.2 Funções injectivas, sobrejecti-
vas, bijectivas
De�nição 11.2 (Injecção). Uma função f : A→ B
é chamada injectiva (ou injecção) se
¬∃x1∃x2(f(x1) = f(x2) ∧ x1 6= x2)
68
ou, o que é o mesmo,
∀x1∀x2(f(x1) = f(x2)→ x1 = x2)
ou
∀x1∀x2(x1 6= x2 → f(x1) 6= f(x2)).
Se existem dois argumentos x1 6= x2 com valores
iguais a função não é injectiva.
De�nição 11.3 (Sobrejecção). Uma função
f : A→ B é chamada sobrejectiva (ou sobrejecção)
se
Im(f) = B
ou, o que é o mesmo,
∀y ∈ B∃x ∈ A(y = f(x)).
De�nição 11.4 (Bijecção). Uma função f : A →
B é chamada bijectiva (ou bijecção, ou correspon-
dência biunívoca) se é injectiva e sobrejectiva.
As propriedades de injectividade, sobrejectivi-
dade e bijectividade de uma função admitem des-
crição equivalente nos termos das equações.
Teorema 11.2. Seja f : A → B. Consideremos a
equação
f(x) = y (11.3)
em relação ao incógnito x ∈ A.
1. A função f é injectiva se e somente se a equa-
ção (11.3) admite no máximo uma única so-
lução qualquer que seja parte direita y ∈ B
(a equação tem a propriedade de unicidade de
solução).
2. A função f é sobrejectiva se e somente se a
equação (11.3) é compatível qualquer que seja
parte direita y ∈ B (a equação tem a proprie-
dade de existência de solução).
3. A função f é bijectiva sé e somente se a equa-
ção (11.3) tem uma única solução qualquer que
seja parte direita y ∈ B (existência e unicidade
da solução).
As propriedades de injectividade, sobrejectivi-
dade e bijectividade de uma função f : A → B
no caso particular, quando A,B ⊂ R também ad-
mitem uma interpretação geométrica.
Teorema 11.3. Seja A,B ⊂ R e f : A→ B.
1. A função f é injectiva se e somente se qualquer
que seja b ∈ B a recta horizontal y = b tem
nó máximo um ponto comum com o grá�co da
função y = f(x).
2. A função f é sobrejectiva se e somente se qual-
quer que seja b ∈ B a recta horizontal y = b e o
grá�co da função y = f(x) têm ponto comum.
3. A função f é bijectiva se e somente se qual-
quer que seja b ∈ B a recta horizontal y = b
intersecta o grá�co da função y = f(x) exac-
tamente num ponto.
Exemplo 11.4. Seja
f(x) = x2 (11.4)
1. A função f : [0,∞[→ [0,∞[ de�nida pela fór-
mula (11.4) é bijectiva.
2. A função f : [0,∞[→ R de�nida pela fórmula
(11.4) é injectiva mas não é sobrejectiva.
3. A função f : R→ [0,∞[ de�nida pela fórmula
(11.4) é sobrejectiva mas não é injectiva.
4. A função f : R → R de�nida pela fórmula
(11.4) não é injectiva nem sobrejectiva.
11.2.3 Funções inversas
Seja f : A → B. A relação inversa f−1 sempre
existe:
f−1 = {(y, x) : (x, y) ∈ f} = {(y, x) : y = f(x)}.
Teorema 11.4. Seja f : A→ B. A relação inversa
f−1 é uma função de B em A se e somente se f é
uma função bijectiva.
Seja iA = {(x, x) : x ∈ A} relação identidade.
Veri�que que no caso de existência da função in-
versa
f−1 ◦ f = iA, f ◦ f−1 = iB . (11.5)
11.2.4 Exercícios
1. Seja
a mod b
o resto de divisão de a por b. Seja f : A→ A,
onde A = {0, 1, 2, 3, 4, 5},
f(x) = x2 mod 6.
Achar f ◦ f .
69
2. Veri�que as proposições do Exemplo 11.4 na
base do Teorema 11.2, analisando a equação
x2 = y de dois métodos: analiticamente e gra-
�camente, isto é, usando o Teorema 11.3.
3. Seja f : A→ A, A = Rr {1},
f(x) = (x+ 1)/(x− 1).
(a) Mostre que f é bijectiva.
(b) Mostre que f ◦ f = iA.
4. Seja f : R→ R de�nida pela
f(x) =
2x+ 5
3
.
Mostrar que f é bijectiva e achar f−1.
5. Sejam f : R→ R, f(x) = ax+ b
(a) f é injectiva?
(b) f é sobrejectiva?
6. Seja A = Rr {2},
f(x) =
3x
x− 2
.
Mostrar que f : A → Im(f) é bijectiva. Achar
f−1.
7. Sejam c 6= 0, f : R r {−d/c} → R, f(x) =
(ax+ b)/(cx+ d)
(a) f é injectiva?
(b) f é sobrejectiva?
8. Sejam f : R→ R, g : R→ R,
f(x) =
1
x2 + 1
, g(x) = 2x− 1.
Achar as fórmulas para f ◦ g e g ◦ f
9. Sejam f : A → B e g : B → A. Suponhamos
que g◦f = iA. É possível a�rmar que g = f−1?
11.3 Imagem e pré-imagem
Da de�nição de imagem de relação vamos ter a se-
guinte forma de imagem de função:
Im(f) = {y : ∃x(y = f(x))}
= {f(x) : x ∈ A}. (11.6)
Introduz-se também a imagem de um conjunto.
De�nição 11.5 (Imagem). Seja f : A → B uma
função e X ⊂ A. O conjunto
f(X) = {f(x) : x ∈ X} ≡ {y : ∃x ∈ X(y = f(x))}.
diz-se imagem do conjunto X.
No exemplo 11.1 f(A) = {2, 4}.
Notemos que a imagem do conjunto A sob a f
coincide com Im(f):
Teorema 11.5.
Im(f) = f(A).
De�nição 11.6 (Pré-imagem). Seja f : A → B
uma função e Y ⊂ B. O conjunto
f−1(Y ) = {x ∈ A : f(x) ∈ Y }.
chama-se pré-imagem (ou imagem inversa, ou ima-
gem recíproca) do conjunto Y .
No exemplo 11.1 f−1({1, 2}) = {a, c}.
11.3.1 Exercícios
1. Sobre o conjunto U = {0, 1, 2, 3, 4, 5} é de�-
nida a função f : U → U segundo a formula
f(x) = x2 mod 6. Encontrar as imagens e pré-
imagens f(U), f−1(U), f(B), f−1B) onde
B = {2, 3, 5}. Resolver a equação f(x) = x.
2. Sejam A = {0, 1, 2, 3, 4, 5, 6, 7} e f : A → A a
função de�nida pela fórmula f(x) = x2 mod
8. Achar um elemento x ∈ f(A) tal que x /∈
f−1({x}).
3. Seja f : A → R onde A = R r {0} a função
de�nida por f(x) = x + 1/x. Achar f([2, 3]),
f(A), f−1([0,+∞)).
4. Demonstrar que se X1 ⊂ X2 então
f(X1) ⊂ f(X2).
A proposição reciproca é verdadeira?
5. Seja f : A→ B. Demonstrar que ∀X ⊂ A
X ⊂ f−1(f(X)).
Construir um exemplo com X 6= f−1(f(X))
Indicação. Sejam
A = {a, b, c, d}, B = {1, 2, 3, 4}.
70
Pode ser considerada a função f : A→ B,
x a b c d
f(x) 2 4 2 1
6. Seja f : A → B, Y1, Y2 ⊂ B, Y1 ⊂ Y2. De-
monstrar que se f−1(Y1) = f−1(Y2) então
(Y2 r Y1) ∩ f(A) = ∅.
7. Demonstrar as seguintes propriedades da ope-
ração pré-imagem
(a) f−1(X ∪ Y ) = f−1(X) ∪ f−1(Y )
(b) f−1(X ∩ Y ) = f−1(X) ∩ f−1(Y )
(c) f−1(Xc) =
(
f−1(X)
)c
8. Sejam f : A → B, X ⊂ A, Y ⊂ B. Demons-
trar que
X ⊂ f−1(Y )⇔ f(X) ⊂ Y.
9. Sejam f : A → B, X ⊂ A, Y ⊂ B. Mostrar
que as implicações
(a) X ⊃ f−1(Y )→ f(X) ⊃ Y
(b) f(X) ⊃ Y → X ⊃ f−1(Y )
são falsas.
10. Sejam A = {1, 2, 3}, B = P(A), f : B → B,
f(X) = ArX.
Achar f({1, 3}).
71
Tema IV
Conjuntos enumeráveis e não
enumeráveis
72
Capítulo 12
Conjuntos enumeráveis e não
enumeráveis
12.1 Conjuntos �nitos e in�ni-
tos
73
74
75
12.2 Equipotência de conjun-
tos
76
77
12.3 Propriedades de conjun-
tos enumeráveis
78
79
12.4 Conjuntos não enumerá-
veis
80