Teoria dos Conjuntos

Prévia do material em texto

Teoria dos Conjuntos
Renato Martins Assunção
assuncao@dcc.ufmg.br
Antonio Alfredo Ferreira Loureiro
loureiro@dcc.ufmg.br
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 1
Introdução
• O que os seguintes objetos têm em comum?
– um grupo de pessoas
– um rebanho de animais
– um buquê de flores
– uma dúzia de ovos
• Conjunto: coleção de objetos bem definidos, denominados elementos ou
membros do conjunto.
– As palavras “conjunto” e “elementos” são termos indefinidos da teoria dos
conjuntos.
• Teoria dos conjuntos: base do pensamento matemático.
– Todos objetos matemáticos podem ser definidos em termos de conjuntos.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 2
Introdução
• Notação:
Seja S um conjunto e a um elemento de S.
– a ∈ S: a pertence a S
– a 6∈ S: a não pertence a S
• Axioma da extensão:
– Um conjunto é completamente determinado pelos seus elementos.
– A ordem na qual os elementos são listados é irrelevante.
– Elementos podem aparecer mais de uma vez no conjunto.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 3
Formas de definir um conjunto
• Listar seus elementos entre chaves:
– {Ana, Roberto, Carlos}
– {Roberto, Carlos, Ana}
– {Roberto, Roberto, Ana, Carlos, Ana}
• Especificar uma propriedade que define um conjunto, como S =
{x|P (x)}:
– {x ∈ Z| − 2 < x < 5}
– {x ∈ R| − 2 < x < 5}
Ü P (x) não pode ser uma propriedade qualquer.
Exemplo:
S = {A|A é um conjunto e A 6∈ A};S ∈ S? [Paradoxo de Russel]
• Usar uma definição recursiva:
–
{
1 ∈ A
se x ∈ A e x+2 < 10, então x+2 ∈ A
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 4
Formas de definir um conjunto
• Usar operações sobre conjuntos para criar novos conjuntos:
– S = {1,3,5,7,9} ∪ P
• Especificar uma função característica:
– µA(x) =
{
k para x = 1,3,5,7,9
0 caso contrário
Ü Nem sempre é possível utilizar todos os tipos de definição:
Exemplo: S = {x ∈ R|0 ≤ x ≤ 1}
Não é possível definir S listando os elementos.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 5
Relações entre conjuntos: Subconjuntos
• Definição: Se A e B são conjuntos, A é chamado subconjunto de B, escrito
A ⊆ B, sse cada elemento de A também é um elemento de B.
• Simbolicamente:
A ⊆ B ⇔ ∀x, se x ∈ A então x ∈ B.
• As frases “A está contido em B” e “B contém A” são formas alternativas de
dizer que A é um subconjunto de B.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 6
Relações entre conjuntos:
Subconjunto próprio
• Definição: Se A e B são conjuntos, A é subconjunto próprio de B sse cada
elemento de A está em B mas existe pelo menos um elemento de B que não
está em A.
• Simbolicamente:
A ⊂ B ⇔ A ⊆ B e A 6= B.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 7
Relações entre conjuntos:
Diagramas de Venn
• Se os conjuntos A e B forem representados por regiões no plano, relações
entre A e B podem ser representadas por desenhos chamados de Diagra-
mas de Venn.
• Exemplo 1: A ⊆ B.
A B A B
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 8
Relações entre conjuntos:
Diagramas de Venn
• Exemplo 2: A 6⊆ B.
A B A B BA
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 9
Relações entre conjuntos:
Igualdade
• Definição:
Dados os conjuntos A e B, A = B sse cada elemento de A está em B e
cada elemento de B está em A.
• Simbolicamente:
A = B ⇔ A ⊆ B e B ⊆ A.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 10
Operações sobre conjuntos
Sejam A e B subconjuntos do conjunto universal U .
• União: A ∪B = {x ∈ U |x ∈ A ou x ∈ B}
Notação: A1 ∪A2 ∪ . . . ∪An = ∪ni=1Ai
• Intersecção: A ∩B = {x ∈ U |x ∈ A e x ∈ B}
Notação: A1 ∩A2 ∩ . . . ∩An = ∩ni=1Ai
• Diferença: B −A = {x ∈ U |x ∈ B e x 6∈ A}
• Complemento: Ac = {x ∈ U |x 6∈ A}
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 11
Tuplas ordenadas
• Seja n um inteiro positivo e seja x1, x2, . . . , xn uma sequência de elementos
não necessariamente distintos.
• A n-tupla ordenada, (x1, x2, . . . , xn), consiste de:
– elementos da sequência, i.e., x1, x2, . . . , xn, e
– a ordem desses elementos na sequência, i.e., x1 é o primeiro elemento, x2
o segundo, etc.
• Exemplos:
– Uma 2-tupla ordenada é chamada de “par ordenado”.
– Uma 3-tupla ordenada é chamada de “tripla ordenada”.
• Duas n-tuplas ordenadas (x1, x2, . . ., xn) e (y1, y2, . . ., yn) são iguais sse
xi = yi, para i = 1 . . . n.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 12
Produto Cartesiano
• Dado dois conjuntosA eB, o produto cartesiano deA eB, denotadoA×B,
é o conjunto de todos os pares ordenados (a, b), onde a ∈ A e b ∈ B.
– Notação: A×B = {(a, b)|a ∈ A e b ∈ B}
• Dado os conjuntos A1, A2, . . . , An, o produto cartesiano de A1, A2, . . . , An,
denotado A1 × A2 × . . . × An, é o conjunto de todas n-tuplas ordenadas
(a1, a2, . . . , an), onde ai ∈ Ai para i = 1 . . . n.
– Notação:
A1 ×A2 × . . .×An =
{(a1, a2, . . . , an)|ai ∈ Ai para i = 1 . . . n}
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 13
Propriedades de subconjuntos
• Inclusão da intersecção: para todos conjuntos A e B.
– A ∩B ⊆ A
– A ∩B ⊆ B
• Inclusão na união: para todos conjuntos A e B.
– A ⊆ A ∪B
– B ⊆ A ∪B
• Propriedade transitiva dos subconjuntos: para todos conjuntos A, B e C.
– se A ⊆ B e B ⊆ C então A ⊆ C
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 14
Identidades de conjuntos
Sejam todos os conjuntos abaixo subconjuntos do conjunto universal U .
• Comutatividade:
A ∩B = B ∩A A ∪B = B ∪A
• Associatividade:
(A ∩B) ∩ C = A ∩ (B ∩ C) (A ∪B) ∪ C = A ∪ (B ∪ C)
• Distributividade:
A ∪ (B ∩ C) =
(A ∪B) ∩ (A ∪ C)
A ∩ (B ∪ C) =
(A ∩B) ∪ (A ∩ C)
• Intersecção com U:
A ∩ U = A
• União com U:
A ∪ U = U
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 15
Identidades de conjuntos
• Complemento duplo:
(Ac)c = A
• Idempotência:
A ∩A = A A ∪A = A
• De Morgan:
(A ∩B)c = Ac ∪Bc (A ∪B)c = Ac ∩Bc
A− (B ∩ C) =
(A−B) ∪ (A− C)
A− (B ∪ C) =
(A−B) ∩ (A− C)
• Absorção:
A ∩ (A ∪B) = A A ∪ (A ∩B) = A
• Representação alternativa para diferença de conjuntos:
A−B = A ∩Bc
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 16
Teorema sobre conjunto vazio
Teorema: Um conjunto com nenhum elemento é um subconjunto de cada con-
junto. Em outras palavras, se ∅ é um conjunto com nenhum elemento e A é um
conjunto qualquer, então ∅ ⊆ A.
Prova (por contradição):
• Suponha que não. Suponha que exista um conjunto ∅ com nenhum elemento
e um conjunto A tal que ∅ 6⊆ A. [Deve-se deduzir uma contradição.]
• Neste caso, deve haver um elemento de ∅ que não é um elemento de A [pela
definição de subconjunto]. Mas não pode haver tal elemento já que ∅ não tem
nenhum elemento. Isto é uma contradição.
.
.
. A suposição que existem conjuntos ∅ eA, onde ∅ não tem nenhum elemento
e ∅ 6⊆ A é F e o teorema é V.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 17
Teorema sobre conjunto vazio
• Corolário: Existe somente um conjunto com nenhum elemento.
Prova:
– Suponha que ∅1 e ∅2 são conjuntos com nenhum elemento. Pelo teorema
acima, ∅1 ⊆ ∅2 já que ∅1 não tem nenhum elemento. Da mesma forma,
∅2 ⊆ ∅1 já que ∅2 não tem nenhum elemento. Logo, ∅1 = ∅2 pela definição
de igualdade de conjuntos.
• Definição: o conjunto único com nenhum elemento é chamado de conjunto
vazio e é denotado pelo símbolo ∅.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 18
Propriedades de conjuntos que envolvem ∅
Sejam todos os conjuntos abaixo subconjuntos do conjunto universal U .
• União com ∅:
A ∪ ∅ = A
• Intersecção e união com o complemento:
A ∩Ac = ∅ A ∪Ac = U
• Intersecção com ∅:
A ∩ ∅ = ∅
• Complementos de U e ∅:
Uc = ∅ ∅ c = U
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 19
Partições de conjuntos
• Definição: Dois conjuntos são chamados disjuntos sse eles não têm nenhum
elemento em comum.
• Simbolicamente,
A e B são disjuntos ⇔ A ∩B = ∅
• Proposição: Dados dois conjuntos A e B, (A−B) e B são disjuntos.
Prova (por contradição):
– Suponha que não.Suponha que existam conjuntos A e B tais que (A −
B) e B não sejam disjuntos. [Deve-se deduzir uma contradição.]
– Neste caso, (A − B) ∩ B 6= ∅ e, desta forma, existe um elemento x em
(A−B)∩B. Pela definição de intersecção, x ∈ (A−B) e x ∈ B e já que
que x ∈ (A−B), pela definição de diferença, x ∈ A e x 6∈ B. Acabou-se
de mostrar que x ∈ B e x 6∈ B, o que é uma contradição.
.
.
. A suposição que existem conjuntos A e B tais que (A−B) e B não são
disjuntos é F e a proposição é V.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 20
Partições de conjuntos
• Definição (conjuntos mutuamente disjuntos): Conjuntos A1, A2, . . . , An são
mutuamente disjuntos (ou disjuntos par-a-par ou sem sobreposição) sse Ai∩
Aj para todos i, j = 1,2, . . . , n e i 6= j, i.e., Ai ∩Bi = ∅.
• Definição (partição): Uma coleção de conjuntos não vazios {A1, A2, . . ., An}
é uma partição do conjunto A sse
1. A = A1 ∪A2 ∪ . . . ∪An
2. A1, A2, . . . , An são mutuamente disjuntos
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 21
Conjunto potência
• Definição (conjunto potência): Dado um conjunto A, o conjunto potência de
A, denotado por P(A), é o conjunto de todos os subconjuntos de A.
• Ache o conjunto potência do conjunto {x, y}.
P({x, y}) = {∅, {x}, {y}, {x, y}}.
• Teorema: Para todos conjuntos A e B, se A ⊆ B então P(A) ⊆ P(B).
Prova:
– Suponha que A e B são conjuntos tais que A ⊆ B. [Deve-se mostrar que
P(A) ⊆ P(B)].
– Suponha que X ⊆ P(A). [Deve-se mostrar que X ⊆ P(B)]. Já que
X ⊆ P(A) então X ⊆ A pela definição de conjunto potência. Mas como
A ⊆ B, temos que X ⊆ B pela propriedade transitiva dos subconjuntos.
Conclui-se então que X ⊆ P(B) [o que devia ser mostrado].
.
.
. P(A) ⊆ P(B) pela definição de subconjunto.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 22
Conjunto potência
Teorema: Para todos inteiros n ≥ 0, se um conjunto X tem n elementos então
P(X) tem 2n elementos.
Prova (por indução matemática): Considere a propriedade “Qualquer conjunto
com n elementos tem 2n elementos.
Passo base: Para n = 0 tem-se 20 = 1 subconjunto. O único conjunto com
zero elementos é o conjunto vazio que só tem um subconjunto que é ele próprio.
Logo, a propriedade é verdadeira para n = 0.
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 23
Conjunto potência
Passo indutivo: se a fórmula é verdadeira para n = k então deve ser verdadeira para n = k+1.
(a) Seja k ≥ 0 e suponha que qualquer conjunto com k elementos tem 2k subconjuntos.
[hipótese indutiva]
(b) Deve-se mostrar que qualquer conjunto com k+1 elementos tem 2k+1 subconjuntos.
– Seja X um conjunto com k+1 elementos e escolha um elemento z em X.
– Observe que qualquer subconjunto de X ou contém z ou não contém.
– Além disso, qualquer subconjunto deX que não contém z é um subconjunto deX−{z}.
– E qualquer subconjunto A de X−{z} pode ser associado com um subconjunto B, igual
a A ∪ {z}, de X que contém z.
– Consequentemente, existem tantos subconjuntos de X que contém z como os que não
contém, e assim existem duas vezes tantos subconjuntos de X quanto existem subcon-
juntos de X − {z}.
– Mas como X − {z} tem k elementos e como o número de subconjuntos de X − {z} é
2k temos que o número de subconjuntos de X é duas vezes o número de subconjuntos
de X − {z}, ou seja, 2 · 2k = 2k+1. [O que devia ser provado]
UFMG/ICEx/DCC MD · Teoria dos Conjuntos 24