Complementos de Matemática_Mauro_2

Prévia do material em texto

2012
ME-100
Fundamentos de Matemática
Mauro S. de F. Marques
– p. 1/63
CAPÍTULO 2
Elementos de teoria de conjuntos
msdfm
– p. 2/63
2.1 Introdução
A Teoria de conjuntos é a base de quase toda a
matemática moderna.
Essa teoria foi iniciada Gerg Cantor (1845-1918) por
volta de 1870.
As idéias de Cantor sofreram muitas críticas dos
matemáticos de então. Hoje, esta teoria é aceita
plenamente e vista como uma mudança de para-
digma da maior importância.
Um referência interessante sobre a história da Teoria
de Conjuntos é:
Johnson, P.E (1972). A History of Set Theory. Prindle,Weber & Smith. Boston
msdfm
– p. 3/63
Aqui daremos um enfoque mais informal à Teoria dos
Conjunto suficiente para os nossos objetivos.
Um estudo mais rigoroso (“axiomático”) pode ser
encontrado em
Halmos,P.R (1972). Naive Set Theory. Springer-Verlag.
“Definic¸a˜o”:
Entendemos por conjunto uma coleção de objetos
distinguíveis, chamados de elementos, pensada como
um todo.
O que ha´ de errado com essa definic¸a˜o?
msdfm
– p. 4/63
Não podemos usar a frase anterior como definição
pois palavra colec¸a˜o não foi previamente definida!
Poderiamos então definir:
Uma colec¸a˜o é um conjunto de objetos distinguíveis,
chamados de elementos, pensado como um todo.
?!?1?!?!?!?!?!?
msdfm
– p. 5/63
Assumiremos como um conceito primitivo as
noc¸o˜es de conjunto e elementos.
Um conjunto deve sempre ser bem definido no sentido que dado
um objeto, somos capazes de dizer (concluir) se este objeto é ou
não um elemento do conjunto.
Para evitar discussões pertinentes a teoria geral de conjuntos, em
uma dada situação, os conjuntos aqui considerados serão
formados por elementos de um conjunto fixo, digamos Ω,
chamado de conjunto universal (ou universo), conjunto
ba´sico, ou espac¸o.
msdfm
– p. 6/63
Assim quando dizemos “todo elemento de A e´ um elemento de
B” estamos dizendo
(∀a em Ω,∀a em A)⇒ (a em B),
para algum conjunto universal Ω.
• Letras maiúsculas (Ω,X,Y, ..., A,B,C, . . .) serão usadas
para denotar conjuntos.
• Letras minúsculas (ω, x, y, . . . , a, b, c, . . .) denotarão
elementos do conjunto.
• Os elementos de um conjunto também são chamados de
membros ou pontos
msdfm
– p. 7/63
Pertineˆncia:
• “a e´ um elemento de A”, ou “a pertence a A”,
ou “a e´ um membro de A”, ou “a e´ um ponto de
A”, ou “a em A” será denotado por
a ∈ A
• A negação, “a não é um elemento de A”, será
expressa por
a 6∈ A.
msdfm
– p. 8/63
Se um conjunto tem “poucos” elementos, por exemplo, quando
A é o conjunto formado pelos elementos ♣,♦,♥ e ♠, então A é
representado na forma {
♣,♦,♥,♠
}
Uma outra maneira de descrever um conjunto é usando alguma
função proposicional p com domínio Ω;
“A é o conjunto dos elementos ω em Ω tal que p(ω) é verdade”
ou
(∀ω ∈ Ω ∋ p(a))⇒ (ω ∈ A).
Notação
A = {ω ∈ Ω : p(ω)} ou A = {ω : p(ω)}.
Exemplos: Seja R o conjunto dos “números reais”.
• A = {x ∈ R : (x− 1)(x+ 1)(x− 2) = 0}.
• A = {x ∈ R : x e´ um nu´mero par}.
• A = {x ∈ R : 0 ≤ x < 1}.
msdfm
– p. 9/63
Um conjunto que merece destaque é aquele que não
possue elementos. Ele é usualmente denotado por
∅ ou { }
e chamado de conjunto vazio.
Por exemplo, o conjunto definido da forma:
{n : n e´ par e n e´ impar}
é vazio.
Note que:
{ } e {{ }}
são conjuntos distintos!?!?!?!?!?
msdfm
– p. 10/63
Dizemos que A é um subconjunto de B ou que
A esta´ contido em B, escreve-se
A ⊂ B,
se todo elemento de A é também um elemento de B,
isto é,
(A ⊂ B)⇔ ((∀ω ∈ Ω) ∧ (ω ∈ A)⇒ ω ∈ B)
A negação de A ⊂ B, é dada por
(A 6⊂ B) = ¬(A ⊂ B)⇔
(
∃ω ∈ Ω,∋ (ω ∈ A)∧(ω 6∈ B)
)
.
msdfm
– p. 11/63
Já usamos de forma empírica o símbolo de igualdade de
conjuntos; para fazermos esta idéia precisa basta observar que
como conjuntos são determinados pelos seus elementos, então
A = B ⇔
(
A ⊂ B e B ⊂ A
)
,
ou seja,
(A = B)⇔
(
(∀ω ∈ Ω, ω ∈ A⇒ ω ∈ B)∧(∀ω ∈ Ω, ω ∈ B ⇒ ω ∈ A)
(∀ω, ω ∈ A⇔ ω ∈ B).
A negação da igualdade é dada por:
(A 6= B) = ¬(A = B)⇔
(
(∃ω ∈ A ∋ ω 6∈ B)∨(∃ω ∈ B ∋ ω 6∈ A)
)
.
msdfm
– p. 12/63
Exercı´cio:
1. Demonstre os seguintes teoremas e em cada caso indique
quais são as premissas e qual é a conclusão:
(i) “O conjunto vazio e´ u´nico”.
(ii) ∀Ω, ∀A,A ⊂ Ω, ∅ ⊂ A.
(iii) ∀A,∀B, ∀C, (A ⊂ B) ∧ (B ⊂ C)⇒ A ⊂ C.
(iv) (A ⊂ ∅)⇔ (A = ∅)
(v) ∅ = {ω ∈ Ω : p(ω) ∧ ¬p(ω)}.
(vi) ({ω ∈ Ω : p(ω)} ⊂ {ω ∈ Ω : q(ω)}) ⇔ (p(ω)⇒ q(ω))
(vii) ({ω ∈ Ω : p(ω)} = {ω ∈ Ω : q(ω)}) ⇔ (p(ω)⇔ q(ω))
Acima p e q são funções proposicionais quaisquer.
msdfm
– p. 13/63
2.2 Operações de conjuntos
Os três operadores (conectivos) básicos são o complementar, a
unia˜o e a intersecc¸a˜o. Sejam A e B subconjuntos de um
universo Ω (A,B ⊂ Ω).
1. O complemento de A (com relação a Ω) é o conjunto
Ac = {ω ∈ Ω : ω /∈ A};
2. A unia˜o de A e B é dada por
A ∪B = {ω ∈ Ω : (ω ∈ A) ∨ (ω ∈ B)} e
3. A intersecc¸a˜o de A e B é
A ∩B = {ω ∈ Ω : (ω ∈ A) ∧ (ω ∈ B)}.
msdfm
– p. 14/63
Em outras palavras;
1. Um elemento de Ω que não é elemento de A é um elemento
do complemento de A.
2. Um elemento da união de A e B é elemento de pelo menos
um dos conjuntos
3. Um elemento da intersecção de A e B é elemento de
ambos.
Dizemos que A e B são disjuntos se
A ∩B = φ,
isto é, A e B na˜o teˆm elementos comuns.
msdfm
– p. 15/63
Sejam A, B e C subconjuntos de um conjunto universo Ω. As
seguintes propriedades são facilmente verificadas:
(i) Lei comutativa:
A ∪B = B ∪ A; A ∩B = B ∩ A.
(ii) Lei associativa:
(A ∪B) ∪ C = A ∪ (B ∪ C);
(A ∩B) ∩ C = A ∩ (B ∩ C).
(iii) Lei distributiva:
(A ∪B) ∩ C = (A ∩ C) ∪ (B ∩ C);
(A ∩B) ∪ C = (A ∪ C) ∩ (B ∪ C).
(iv) Lei de De Morgan:
(A ∪B)c = Ac ∩Bc; (A ∩B)c = Ac ∪Bc. msdfm
– p. 16/63
Exercı´cios:
2. Verifique as propriedades no “slide” anterior.
3. Sejam A e B subconjuntos de um conjunto universo Ω. Demonstre:
(i) ∀A,∀B, (A ⊂ B)⇔ (A ∩B = A).
(ii) ∀A,∀B, (A ⊂ B)⇔ (A ∪B = B).
(iii) ∀A,A ∪Ac = Ω.
(iv) ∀A,A ∩Ac = ∅.
(v) ∀A,∀B, (A ⊂ B)⇔ (Bc ⊂ Ac).
(vi) ∀A,A ∩ ∅ = ∅.
(vii) ∀A,A ∪ Ω = Ω.
(viii) ∀A,∀B,A ∩B ⊂ A.
(ix) ∀A,∀B,A ⊂ A ∪B.
(x) ∀A,∀B,A ∩B ⊂ A ∪B.
(xi) ∀A, (Ac)c = A.
Em cada caso acima identifique claramente premissa(s) e conclusão.
msdfm
– p. 17/63
Já vimos que um conjunto pode ser definido via uma
função proposicional p;
P = {ω ∈ Ω : p(ω)}.
O conjunto P é algumas vezes referido com o
conjunto verdade de p.
De fato,
(ω ∈ P )⇔ p(ω) e´ verdade.
msdfm
– p. 18/63
Exercício:
4. Sejam p e p funções proposicionais com domínio em Ω. Para
P = {ω ∈ Ω : p(ω)} e Q = {ω ∈ Ω : q(ω)},
demonstre que:
(i) P ∪Q = {ω ∈ Ω : p(ω) ∨ q(ω)}.
(ii) P ∩Q = {ω ∈ Ω : p(ω) ∧ q(ω)}.
(iii) P c = {ω ∈ Ω : ¬p(ω)}.
(iv) (P = Q)⇔ (p⇔ q).
(v) (∀ω ∈ A ⊂ Ω, p(ω))⇔ A = P .
(vi) (∃ω ∈ Ω ∋ p(ω))⇔ P 6= ∅.
msdfm
– p. 19/63
Outros operadores: Sejam A e B subconjuntos de
um conjunto universo Ω.
1 O conjunto dos elementos de A que não são
elementos de B, chamado diferenc¸a entre A e B, é
dado por
A \B = A ∩Bc (= A−B).
2 O conjunto dos elementos que pertencem somente a
um deles, chamado de diferenc¸a sime´trica, é dado
por
A△B = (A \B)∪ (B \A) = (A∩Bc)∪ (Ac∩B).
msdfm
– p. 20/63
2.3 Conjunto Potência
Definic¸a˜o: Seja A um subconjunto qualquer de um espaço Ω. O
conjunto cujos elementos são todos os subconjuntos de A,
denotado por P(A) (ou 2A), é chamado conjunto poteˆncia ou
conjunto das partes de A:
P(A) = 2A = {B : B ⊂ A).
Exemplo: Seja A = {a1, a2, a3}.
P(A) = 2A =
{
∅, {a1}, {a2}, {a3}, {a1, a2}, {a1, a3}, {a2, a3}, {a1, a2, a3}
}
.
msdfm
– p. 21/63
Exercı´cios:
5. ∅ ∈ P(A) ou ∅ ⊂ P(A)?
Abaixo, Sejam A e B subconjuntos de um universo Ω.
6. Demonstre de modo direto os teoremas abaixo.(i) (A ⊂ B)⇒ (P(A) ⊂ P(B)).
(ii) (P(A) ⊂ P(B)) ⇒ (A = B).
(iii) Ω ∈ P (A)⇔ A = Ω.
7. Verifique, demonstrando ou dando um contra-exemplo, se as conjecturas abaixo são
verdadeiras ou falsas.
(i) (P(A) ∪ P(B)) ⊂ P(A ∪B).
(ii) (P(A) ∩ P(B)) ⊂ P(A ∩B).
(iii) P(A ∪B) ⊂ (P(A) ∪ P(B)).
(iv) P(A ∩B) ⊂ (P(A) ∩ P(B)).
(v) P(A ∩B) ⊂ P(A ∪B).
msdfm
– p. 22/63
2.4 Cardinalidade
Um conjunto pode ter um número finito ou infinito de elementos.
Definic¸a˜o: Se A é um conjunto com um número finito de
elementos, o número de elementos de A é chamado de
cardinalidade de A e denotado por
♯(A) ou card(A) ou |A|.
A “cardinalidade” de um conjunto com infinitos elementos é um
problema mais delicado e sua discussão será adiada. Para se ter
um noção do problema, imagine o “número” de elementos dos
conjuntos
N = {1, 2, 3, . . .}, Z = {. . . ,−2,−1, 0, 1, 2, . . . },
[0, 1) = {x : 0 ≤ x < 1} e R = {x : −∞ < x < +∞}.
msdfm
– p. 23/63
Exercı´cio:
Sejam A e B subconjuntos de um universo Ω, com número finito de elementos.
8. Demonstre que:
(i) Se A ∩B = ∅, então ♯(A ∪B) = ♯(A) + ♯(B).
(ii) Se A ⊂ B, então ♯(B\A) = ♯(B)− ♯(A).
(iii) Se A ⊂ B, então ♯(A) ≤ ♯(B).
(iv) Se ♯(Ω) = n, então ♯(Ac) = n− ♯(A).
(v) Para todo A e para todo B, ♯(A ∪B) = ♯(A) + ♯(B)− ♯(A ∩B).
9. Verifique que:
(i) Se ♯(A) = 2, então ♯(P(A)) = 4.
(ii) Se ♯(A) = 3, então ♯(P(A)) = 8.
(iii) Se ♯(A) = n, então ♯(P(A)) = 2n.
msdfm
– p. 24/63
Operações envolvendo um número infinito de subcon-
juntos
Considere An, n = 1, 2, . . . , subconjuntos de um universo Ω.
1 A união dos conjuntos An, n ≥ 1, é definida por
A = ∪∞n=1An = ∪n≥1An = {ω ∈ Ω : ∃n ∈ N,∋ ω ∈ An} =
{ω ∈ Ω : (ω ∈ A1) ∨ (ω ∈ A2) ∨ · · · } = {ω ∈ Ω : ω ∈ An para algum n ∈ N}.
2 A intersecção dos conjuntos An, n ≥ 1 é definida por
B = ∩∞n=1An = ∩n≥1An = {ω ∈ Ω : ∀n ∈ N, ω ∈ An} =
{ω ∈ Ω : (ω ∈ A1) ∧ (ω ∈ A2) ∧ · · · } = {ω ∈ Ω : ω ∈ An para todo n ∈ N}.
3 Analogamente
Cn = ∪
∞
k=n
Ak = ∪k≥nAk = {ω ∈ Ω : ∃k ≥ n,∋ ω ∈ Ak}.
Dn = ∩
∞
k=n
Ak = ∩k≥nAk = {ω ∈ Ω : ∀k ≥ n, ω ∈ Ak}.
msdfm
– p. 25/63
2.5 Relações
Conjuntos são determinados por seus elementos, logo
{♣,♦} = {♦,♣}
Em muitas situações é importante distinguir os
mesmos elementos listados em ordens diferentes.
Nestes casos denotamos o par ordenado onde o
primeiro elemento é ♣ e o segundo elemento é ♦ por
(♣,♦).
Assim, o par ordenado (♣,♦) é diferente do par
ordenado (♦,♣):
(♣,♦) 6= (♦,♣).
msdfm– p. 26/63
Para mostrar a importância de considerarmos pares
ordenados, considere a função proposicional
p(n,m) = “n < m”.
Enquanto p(1, 2) é verdadeira, p(2, 1) é falsa!
Definic¸a˜o: Considere os pares ordenados (r, s) e
(u, v);
(r, s) = (u, v) ⇔ (r = u) ∧ (s = v).
Em particular (r, s) 6= (s, r), a menos que r = s.
msdfm
– p. 27/63
Com base na noção de par ordenado podemos definir
uma nova operação entre conjuntos.
Definic¸a˜o: Sejam A e B dois conjuntos. O produto
cartesiano de A com B , denotado por A×B, é o
conjunto de todas os pares ordenados (a, b), onde a é
elemento de A e b é elemento de B;
A×B =
{
(a, b) : a ∈ A ∧ b ∈ B
}
.
msdfm
– p. 28/63
Exemplo: Para A = {♣,♦,♥,♠}, e B = {0, 1}.
• A×B ={
(♣, 0), (♦, 0), (♥, 0), (♠, 0), (♣, 1), (♦, 1), (♥, 1), (♠, 1)
}
• B × A ={
(0,♣), (0,♦), (0,♥), (0,♠), (1,♣), (1,♦), (1,♥), (1,♠)
}
• Em particular, A× ∅ = ∅ e ∅ × A = ∅, ∀A.
• Note que A×B 6= B × A.
• Qual é o conjunto universo para o subconjunto A×B?
msdfm
– p. 29/63
Definic¸a˜o: Sejam A e B dois conjuntos. Uma relac¸a˜o de A
para B é um subconjunto R de A×B definido por uma função
proposicional p(a, b) com domínio A×B.
R = {(a, b) ∈ A×B : p(a, b)}.
Se R é uma relação de A para B e (a, b) ∈ R denotamos
aRb
(lê-se a se relaciona com b).
O domı´nio de R é definido como sendo o conjunto
Dom(R) = {a ∈ A : ∃b ∈ B ∋ (a, b) ∈ R} = {a : ∃b ∋ aRb}.
e a imagem de R o conjunto
Im(R) = {b ∈ A : ∃a ∈ A ∋ (a, b) ∈ R} = {b : ∃a ∋ aRb}.
msdfm
– p. 30/63
Exemplos:
• Se A = {0, 1, 2, 3}, B = {−1, 1, 2, 3} e p(a, b) = “a < b”, então
R = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}, Dom(R) = {0, 1, 2} e
Im(R) = {1, 2, 3}
• Se A é o conjunto de todas as mulheres, B é o conjunto de todos os homens e
p(a, b) = “a e b sa˜o casados”.
R = conjuntos de todos os casais casados,
Dom(R) = conjuntos de todas as mulheres casadas, e
Im(R) = conjuntos de todos os homens casados
• Se A = B = R = {x : x e´ um nu´mero real} e p(x, y) = “y = x2”, então
R = {(x, x2) : x ∈ R}, Dom(R) = R e Im(R) = {(y : y ≥ 0}.
msdfm
– p. 31/63
Seja R uma relação em A, isto é, uma relação de A em A.
Dizemos que:
(i) R é reflexiva se e somente se
∀a ∈ A, aRa.
(ii) R é sime´trica se e somente se
∀a, b ∈ A, aRb⇒ bRa.
(iii) R é transitiva se e somente se
∀a, b, c ∈ A, (aRb ∧ bRc)⇒ aRc.
(iv) R é uma relac¸a˜o de equivaleˆncia se e somente se
R é reflexiva, simétrica e transitiva.
msdfm
– p. 32/63
Exercı´cios:
10. Verifique se as proposições abaixo são verdadeiras ou falsas. Justifique as respostas!
(i) Considere R o conjunto dos números reais e R definida por
xRy ⇔ (x ≤ y).
Então R é uma relação de equivalência.
(ii) Considere P(Ω) o conjunto potência de um universo Ω eR definida por
ARB ⇔ (A ⊂ B).
EntãoR é simétrica e transitiva mas não é reflexiva.
(iii) Seja A um conjunto, não vazio, qualquer e considere a relação dada pelo conjunto
R = A×A.
Então R não é uma relação de equivalência.
(iv) Seja N = {1, 2, . . .} o conjunto dos números naturais e defina a relação
nRm⇔
(
5 divide (n−m)
)
.
Então R é uma relação de equivalência.
msdfm
– p. 33/63
Relac¸o˜es de equivaleˆncia e partic¸o˜es
Definic¸a˜o:
Dado um conjunto não vazio A, uma partic¸a˜o de A é
um conjunto ΠA cujos elementos são subconjuntos de
A e cada elemento de A é elemento de exatamente
um desses subconjuntos.
Note que se P e S são elementos de ΠA, então
P = S ou P ∩ S = ∅.
Além disto, a união de todos os elementos de ΠA é
igual a A.
msdfm
– p. 34/63
Exemplos:
• Se A = {a, b, c, d}, então
{
{a}, {b}, {c}, {d}
}
,
{
{a}, {b, c}, {d}
}
,
{
{a, d}, {b, c}
}
,
entre outras, são partições de A.
• Se A = N = {1, 2, . . .}, então
{
{1, 2, . . . , 10}, {11, 12, . . . , 20}, . . .
}
,
{
{n : n = 2k, k ∈ N}, {n : n = 2k − 1, k ∈ N}
}
,
entre outras, são partições de N.
msdfm
– p. 35/63
Dizemos que uma partição Π′A é um refinamento da partição
ΠA se
∀P ′ ∈ Π′A ⇒ ∃P ∈ ΠA,∋ P
′ ⊂ P.
Exemplos: A = {a, b, c, d}:
•
{
{a}, {b}, {c}, {d}
}
é um refinamento de
{
{a}, {b, c}, {d}
}
.
•
{
{a}, {b, c}, {d}
}
na˜o e´ um refinamento de
{
{a, b}, {c, d}
}
.
msdfm
– p. 36/63
Definic¸a˜o:
Seja R uma relação de equivalência em um conjunto
não vazio A.
A classe de equivaleˆncia de um elemento x de A,
denotada por
[x]R (ou resumidamente por [x]),
é o subconjunto de A formado por todos os elementos
de A que se relacionam com x;
[x]R =
{
y ∈ A : xRy
}
msdfm
– p. 37/63
Exemplo: Em N = {1, 2, . . .} seja a relação de
equivalência
nRm⇔
(
5 divide (n−m)
)
.
Então:
[1]R = {1, 6, 11, 16, . . .}, [2]R = {2, 7, 12, 17, . . .},
[3]R = {3, 8, 13, 18, . . .}, [4]R = {4, 9, 14, 19, . . .},
[5]R = {5, 10, 15, 20, . . .},
[6]R = {1, 6, 11, 16, . . .} = [1]R, [7]R = [2]R,
[8]R = [3]R, [9]R = [4]R, [10]R = [5]R, . . .
msdfm
– p. 38/63
Teorema 1. Seja R uma relac¸a˜o de equivaleˆncia
(reflexiva, sime´trica e transitiva) em um conjunto na˜o
vazio A. Enta˜o
(i) ∀x ∈ A, [x]R 6= ∅.
(ii) ∀x, y ∈ A, [x]R ∩ [y]R 6= ∅ ⇔ xRy.
(iii) ∀x, y ∈ A, [x]R = [y]R ⇔ xRy.
(iv) ∀x, y ∈ A, [x]R 6= [y]R ⇔ [x]R ∩ [y]R = ∅.
msdfm
– p. 39/63
Demonstrac¸a˜o: (i) Como R é reflexiva,xRx⇔ x ∈ [x]R ⇒ [x]R 6= ∅.
(ii) (→) ∀x, y ∈ A, [x]R ∩ [y]R 6= ∅ ⇔ ∃z ∈, [x]R ∩ [y]R ⇔ xRz ∧ yRz.
Como R é simétrica,
yRz ⇔ zRy.
Temos então
xRz ∧ zRy
Segue pela transitividade de R que
xRy.
(←) Agora
xRy ⇒ y ∈ [x]R
Mas
y ∈ [y]R,
portanto
[x]R ∩ [y]R 6= ∅.
msdfm
– p. 40/63
(iii) (→) Segue de (i) e (ii).
(←) Vamos assumir xRy,
∀z ∈ [x]R ⇔ xRz.
Por outro lado, pela simetria de R,
xRy ⇔ yRx.
Agora, pela transitividade
yRx ∧ xRz ⇒ yRz.
Logo,
z ∈ [y]R
e portanto
[x]R ⊂ [y]R.
Similarmente, trocando x por y, obtemos
[y]R ⊂ [x]R,
demonstrando que
[x]R = [y]R.
(iv) É uma consequência direta de (ii) e (iii).
c.q.d
msdfm
– p. 41/63
Teorema 2. Seja R uma relac¸a˜o de equivaleˆncia (reflexiva, sime´trica e transitiva) em um
conjunto na˜o vazio A. Defina
[A]R =
{
[x]R : x ∈ A
}
.
Enta˜o [A]R e´ uma partic¸a˜o de A.
Demonstrac¸a˜o:
∀ ∈ A, x ∈ [x]r ∈ [A]R.
Isto mostra que todo elemento de A pertence a pelo menos um elemento de [A]R
Para demonstrar que [A]R é uma partição temos que verificar que cada elemento de A pertence a
um e somente um elemento de [A]R.
Vamos usar o método de demonstração por contradição. Suponhamos que
∃y ∈ A ∋ y ∈ [z]r ∩ [u]R, [z]r 6= [u]R.
Pelo teorema anterior (iv),
[z]r 6= [u]R ⇒ [z]r ∩ [u]R = ∅,
o que contradiz a existência de y.
c.q.d
msdfm
– p. 42/63
Teorema 3. Seja Π uma partic¸a˜o de A. Enta˜o Π define um relac¸a˜o de equivaleˆncia em A.
Demonstrac¸a˜o: Consider a relação:
xRy ⇔ ∃P ∈ Π ∋ {x, y} ⊂ P.
Claro, com Π é uma partição,
∀x ∈ A,∃P ∈ Π,∋ {x} ∈ P.
Logo xRx, o que mostra que r é reflexiva.
A relação é claramente simétrica.
xRy ⇔ P ∈ Π ∋ {x, y} ⊂ P ⇔ yRx.
Para mostrar a transitividade considere
(xRy ∧ yRz)⇔ (∃P ∈ Π,∋ {x, y} ⊂ P ) ∧ (∃S ∈ Π,∋ {y, z} ⊂ S).
Logo
y ∈ P ∩ S ⇒ P ∩ S 6= ∅ ⇒ P = S.
Portanto
{x, z} ⊂ P ⇒ xRz.
Como R é reflexiva, simétria e transitiva, ela é uma relação de equivalência.
c.q.d
.
A relação acima é usualmente denotada por A/Π (lê-se Amodulo Π).
msdfm
– p. 43/63
Exercı´cios:
11. Demonstre o Teorema:
Teorema 4. Seja R uma relac¸a˜o de equivaleˆncia em um
conjunto A e Π uma partic¸a˜o de A. Enta˜o AR = Π se e somente
se R = A/Π.
12. Considere
A = {∗, ⋆, ◦, •, ⋄, ⊳} e Π =
{
{⋆, •, ⊳}, {∗, ⋄}, {◦}
}
.
Liste os elementos de A/Π.Encontre [⋄]A/Π.
13. No intervalo [0, 2π) defina a seguinte relação:
xRy ⇔ sen(x) = sen(y).
(i) Mostre que R é uma relação de equivalência.
(ii) Encontre [0, π)R.
msdfm– p. 44/63
14. Seja A um conjunto não vazio. Considere as seguintes
partições de A:
Π1 =
{
{x} : x ∈ A
}
e Π2 =
{
A
}
.
Determine as correspondentes relações de equivalência.
msdfm
– p. 45/63
2.6 Funções
O conceito de função é usualmente introduzido nos cursos de
matemática do segundo grau. Nesta secção daremos uma
definição rigorosa desse conceiro.
Definic¸a˜o: Uma func¸a˜o f é uma relação de um conjunto A em
um conjunto B, denotada por
f : A 7→ B
(lê-se “f e´ uma func¸a˜o de A em B), que satisfaz:
(i) Dom(f) = A.
(ii) ∀x ∈ A,∀y, z ∈ B, (((x, y) ∈ f) ∧ (x, z) ∈ f)⇒ y = z).
msdfm
– p. 46/63
Em outras palavras,
se f e´ uma relac¸a˜o de A em B tal que para cada x em A existe
exatamente um y em B tal que (x, y) pertence a f , enta˜o f e´ dita
ser uma func¸a˜o de A em B.
Se f é uma função de A em B então a “propriedade funcional”
que a cada x em A está relacionada com exatamente um y em B
permite que usemos a notação usual
y = f(x).
Note que se f é uma relação mas não uma função, um dado x em
A pode estar relacionado com vários (ou nenhum) elemento de
B.
msdfm
– p. 47/63
Exemplos:
• Considere A =
{
♣,♦,♥,♠
}
e B =
{
1, 2, 3, 4, 5}. Defina
(i) f = {(♣, 2), (♦, 3), (♥, 4), (♠, 5)}.
(ii) g = {(♣, 2), (♣, 3), (♦, 4), (♥, 5), (♠, 5)}.
(iii) h = {(♣, 1), (♦, 2), (♥, 3)}.
Então f , g e h são relações de A em B mas somente f é uma função.
• Considere A =
{
1, 2, 3, 4, 5
}
e B =
{
a, b, c, d
}
.
f =
{
(1, b), (2, b), (3, a), (4, d), (5, a)
}
Claramente f e´ uma func¸a˜o! Observe que
f(1) = f(2) = b, f(3) = f(5) = a
e
6 ∃x ∈ A ∋ f(x) = c.
( 6 ∃ significa na˜o existe!)
msdfm
– p. 48/63
Um pouco de linguagem: Seja f : A 7→ B.
• O nome da função é f , f(x) é um elemento de B.
• Se y = f(x) dizemos que y é a imagem de x e x uma pre´-imagem de y.
• A = Dom(f) e Im(f) ⊂ B. B é chamado contradomı´nio de f .
• f é chamada injetora (ou uma injec¸a˜o) se e somente se
∀u, v ∈ A, f(u) = f(v)⇒ u = v.
• f é chamada sobrejetora se e somente se Im(f) = B, isto é,
∀y ∈ B, ∃x ∈ A,∋ y = f(x).
• f é chamada bijetora (ou biunı´voca, ou uma bijec¸a˜o) se e somente se ela é injetora e
sobrejetora.
msdfm
– p. 49/63
Exemplos:
• A =
{
♣,♦,♥,♠
}
e B =
{
∗, ⋆, ◦
}
f =
{
(♣, ∗), (♦, ◦), (♥, ◦), (♠, ⋆)
}
é sobrejetora mas não é injetora.
• A =
{
∗, ⋆, ◦
}
e B =
{
♣,♦,♥,♠
}
f =
{
(∗,♦), (⋆,♣), (◦,♥)
}
é injetora mas não é sobrejetora.
• A =
{
∗, ⋆, ◦
}
e B =
{
∗, ⋆, ◦
}
f =
{
(∗, ∗), (⋆, ◦), (◦, ◦)
}
não é injetora nem é sobrejetora.
• A =
{
♣,♦,♥,♠
}
e B =
{
♣,♦,♥,♠
}
f =
{
(♣,♦), (♦,♥)(♥,♠), (♠,♣)
}
é bijetora.
msdfm
– p. 50/63
Teorema 5. Considere f : A 7→ B e g : A 7→ B. Enta˜o
f = g ⇔ ∀x ∈ A, f(x) = g(x).
Demonstrac¸a˜o: Suponhamos f = g.
∀x ∈ A⇒ ∃y ∈ B,∋ (x, y) ∈ f.
Agora,
(x, y) ∈ f ∧ (f = g)⇒ (x, y) ∈ g.
Logo
y = f(x) ∧ y = g(x)⇒ f(x) = g(x).
Suponhamos agora que
∀x ∈ A, f(x) = g(x).
Como f e g são relações, para mostrar que f = g temos que verificar que (f ⊂ g) ∧ (g ⊂ f ).
Para tanto,
∀(x, y) ∈ f, y = f(x) = g(x)⇒ (x, y) ∈ g,
mostrando que
f ⊂ g.
Analogamente, intercambiando f e g, temos g ⊂ f e consequentemente
f = g.
c.q.d
msdfm
– p. 51/63
Definic¸a˜o: Seja f : A 7→ B uma função (relação) bijetora. A função inversa de f , denotada por
f−1, é uma função de B em A, f−1 : B 7→ A definida por;
f−1 =
{
(b, a) : (a, b) ∈ f
}
.
Teorema 6. f−1 esta´ bem definida como func¸a˜o, isto e´,
(i) Dom(f−1) = B
(ii) ∀y ∈ B, ∀x, z ∈ A, (((y, x) ∈ f−1) ∧ (y, z) ∈ f−1)⇒ x = z).
Demonstrac¸a˜o: Inicialmente como f é sobrejetora,
∀y ∈ B,∃x ∈ A,∋ (f(x) = y) ∧
(
(x, y) ∈ f
)
⇒ (y, x) ∈ f−1
Logo,
Dom(f−1) = B.
Por outro lado,
(y, x) ∈ f−1 ∧ (y, z) ∈ f−1 ⇒ (x, y) ∈ f ∧ (z, y) ∈ f
Portanto, como f é injetora
x = z.
c.q.d
msdfm
– p. 52/63
Definic¸a˜o: Se f : A 7→ B e g : B 7→ C definimos a composição
de g com f , denotada por (g ◦ f) (lê-se g composta com f ) por
(g ◦ f) : A 7→ C, ∋ (g ◦ f)(x) = g
(
f(x)
)
.
Note que que:
(g◦f)(x) = z ⇒ (x, z) ∈ (g◦f)⇒ ∃y ∈ B,∋ (x, y) ∈ f∧(y, z) ∈ g.
Ou seja,
y = f(x) ∧ g(y) = z
Portanto,
z = g(y) = g(f(x)) = (g ◦ f)(x).
msdfm
– p. 53/63
Definic¸a˜o: A função IA : A 7→ A definida como
∀x ∈ A, IA(x) = x.
é chamada func¸a˜o identidade em A.
Exercı´cios:
15. Demonstre o teorema:
Teorema 7. Se f−1 existe, enta˜o ela e´ bijetora e (f−1)−1 = f .
16. Demonstre o teorema:
Teorema 8. Se f : A 7→ B e´ uma func¸a˜o bijetora, enta˜o
(i) f−1 ◦ f = IA ∧ f ◦ f−1 = IB .
(ii) f ◦ IA = f ∧ IB ◦ f = f.
17. Demonstre o teorema:
Teorema 9. Se f : A 7→ B e g : B 7→ C sa˜o uma func¸o˜es bijetoras, enta˜o
(i) (g ◦ f) e´ bijetora.
(ii) (g ◦ f)−1 = (f−1 ◦ g−1)
msdfm
– p. 54/63
Imagens e imagens inversas
Seja f : A 7→ B.
Definic¸a˜o: Se C ⊂ A, a imagem de C é o subconjunto de B
definido por
f [C] = {y ∈ B : ∃x ∈ A,∋ y = f(x)}.
Definic¸a˜o: Se D ⊂ B, a imagem inversa (ou pre´-imagem) de
D é o subconjunto de A definido por
f−1[D] = {x ∈ A : f(x) ∈ D}.
Observe que a definição e imagem inversa na˜o assume a
existência da função inversa. msdfm
– p. 55/63
Exemplo: Considere
A = {♣,♦,♥,♠}, B= {∗, ⋆, ◦} e f : A 7→ B,
onde
f(♣) = ∗, f(♦) = ∗, f(♥) = ◦ e f(♠) = ◦.
Então,
f [{♣,♥}] = {∗, ◦}, f [{♣,♦}] = {∗}, f [A] = {∗, ◦}, f [∅] = ∅;
f−1[{∗, ⋆}] = {♣,♦}, f−1[{⋆}] = ∅ f−1[B] = A f−1[∅] = ∅.
msdfm
– p. 56/63
Teorema 10. Seja f : A 7→ B e considereD e F subconjuntos de B. Enta˜o
(i) f−1[D ∪ F ] = f−1[D] ∪ f−1[F ]
(ii) f−1[D ∩ F ] = f−1[D] ∩ f−1[F ]
(iii) f−1[Dc] = (f−1[D])c.
Demonstrac¸a˜o:
(i) x ∈ f−1[D ∪ F ]⇔ f(x) ∈ (D ∪ F )⇔ (f(x) ∈ D) ∨ (f(x) ∈ F )⇔
(x ∈ f−1[D]) ∨ (x ∈ f−1[F ])⇔ x ∈ (f−1[D] ∪ f−1[F ]).
(ii) x ∈ f−1[D ∩ F ]⇔ f(x) ∈ (D ∩ F )⇔ (f(x) ∈ D) ∧ (f(x) ∈ F )⇔
(x ∈ f−1[D]) ∧ (x ∈ f−1[F ])⇔ x ∈ (f−1[D] ∩ f−1[F ]).
(iii) x ∈ f−1[Dc]⇔ f(x) ∈ Dc ⇔ f(x) 6∈ D ⇔ x 6∈ f−1[D]⇔ x ∈ (f−1[D])c.
c.q.d
msdfm
– p. 57/63
Exercı´cios:
16. Mostre que
f [·] : P(A) 7→ P(B) e f−1[·] : P(B) 7→ P(A)
definem funções.
17. Demonstre o teorema:
Teorema 11. Seja f : A 7→ B. SeD ⊂ F ⊂ B, enta˜o
f−1[D] ⊂ f−1[F ].
18. Seja f : A 7→ B. Demonstrando ou dando um contraexemplo, indique se as proposições
abaixo são verdadeiras ou falsas.
(i) C ⊂ D ⊂ A⇒ f [C] ⊂ f [D] ⊂ f [A].
(ii) (C ⊂ A) ∧ (D ⊂ A)⇒ f [C ∪D] = f [C] ∪ f [D].
(iii) (C ⊂ A) ∧ (D ⊂ A)⇒ f [C ∩D] = f [C] ∩ f [D].
(iv) (C ⊂ A)⇒ f [Cc] = (f [C])c.
(v) (C ⊂ A)⇒ f−1[f [C]] = C.
(vi) (D ⊂ B)⇒ f [f−1[D]] = D.
msdfm
– p. 58/63
19. Demonstre o seguinte teorema:
Teorema 12. Considere uma func¸a˜o f : A 7→ B. Seja a relac¸a˜o
em A definida por
xRy ⇔ f(x) = f(y).
Enta˜o R e´ uma relac¸a˜o de equivaleˆncia em A. Ale´m disto, se
[A]R e´ a correspondente partic¸a˜o de A, defina duas novas
func¸o˜es:
α : A 7→ [A]R
x α(x) = [x]R
e
f∗ : [A]R 7→ B
[x]R f
∗
(
[x]R
)
= f(x).
Enta˜o f ∗ e´ bijetora e
f = f∗ ◦ α.
msdfm
– p. 59/63
Relações binárias
As operações aritiméticas usuais (+,−,×,÷), assim como os conectivos lógicos (∨,∧,→,⇔)
e as operações de conjuntos (∪,∩, \) podem ser vistas como funções (relações). Para tanto
considere a seguinte definição:
Definic¸a˜o: Seja A um conjunto. Uma função
• : A×A 7→ A
é chamada uma operac¸a˜o bina´ria em A. Em outras palavras, uma operação binária em A associa
a cada par ordenado de elementos de A um elemento de A.
No caso onde a função de interesse é uma operação binária • a notação usual,
•
(
(a, b)
)
= c
será substituida por
a • b = c.
Por exemplo no caso de soma de números naturais, + : N 7→ N, no lugar de
+
(
(2, 10)
)
= 12
escrevemos
2 + 10 = 12.
msdfm
– p. 60/63
Definic¸a˜o: Seja • uma operação binária em um conjunto A. Então:
(i) • é comutativa se e somente se
∀a, b ∈ A, a • b = b • a.
(ii) • é associativa se e somente se
∀a, b, c ∈ A, a • (b • c) = (a • b) • c.
(iii) Uma elemento e de A é uma identidade para • se e somente se
∀a ∈ A, a • e = e • a = a.
(iv) Se e é uma identidade para •, dizemos que um elemento a de A é invertı´vel se e somente
se
∃b ∈ A,∋ a • b = b • a = e.
Neste caso, um tal b é chamado inverso de a.
(v) Uma elemento a de A é idempotente para • se e somente se
a • a = a. msdfm
– p. 61/63
Teorema 13. Seja • uma operac¸a˜o bina´ria em um conjunto A. Enta˜o existe no ma´ximo um
elemento identidade para •.
Demonstrac¸a˜o: Suponhamos que e e e′ são identidades para •. Então
e = e • e′ = e′.
c.q.d
Teorema 14. Seja • uma operac¸a˜o bina´ria associativa com elemento identidade e em um
conjunto A . Enta˜o cada elemento invertı´vel de A, tem no ma´ximo um elemento inverso.
Demonstrac¸a˜o: Suponhamos que b e b′ são inversos de um elemento a de A. Então
a • b = b • a = e ∧ a • b′ = b′ • a = e.
Logo,
b = b • e = b • (a • b′) = (b • a) • b′ = e • b′ = b′.
c.q.d
msdfm
– p. 62/63
Exercı´cios:
20. Seja Ω um conjunto não vazio. O que voce pode dizer das operações binárias ∪, ∩ e \
definidas em P(Ω), o conjuntos das partes de Ω?
21. Seja Ω um conjunto não vazio. Defina em P(Ω) a seguinte operação binária:
A •B = (A ∩Bc) ∪ (Ac ∩B), ∀A,B ∈ P(Ω).
(i) Mostre que • é comutativa.
(ii) Mostre que • é associativa.
(iii) Qual é a identidade para •?
(iv) Mostre que todo elemento em P(Ω) é invertível.
(v) Se A ⊂ Ω, qual é o inverso de A?
msdfm
– p. 63/63
	small 2.1 Introduc c~ao
	small 2.2 Operac c~oes de conjuntos
	small 2.3 Conjunto Pot^encia
	small 2.4 Cardinalidade
	small Operac c~oes envolvendo um n'umero infinito de subconjuntos
	small 2.5 Relac c~oes
	small 2.6 Func c~oes
	small Imagens e imagens inversas
	small Relac c~oes bin'arias