Md-Aula05 Conjuntos

Conjuntos
Área de Teoria DCC/UFMG
Matemática Discreta
2019/01
Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 1 / 31

Conjuntos: Introdução
Conjuntos são as estruturas discretas fundamentais sobre as quais todas as

demais estruturas discretas podem ser construı́das.
A Teoria dos Conjuntos é capaz de representar toda a Matemática.

Conceitos básicos como conjunto, pertinência de elementos a um conjunto, o
conjunto vazio, operações sobre conjuntos (união, interseção, complemento,
...) podem capturar conceitos como aritmética, lógica, etc.
Os conceitos que estudaremos aqui são essenciais para diversas áreas,

incluindo algumas que estudaremos neste curso:
funções, análise combinatória,

sequências, relações.
somatórios e produtórios, ...

Conjuntos

Conjuntos
Um conjunto é coleção não-ordenada de objetos bem definidos,

denominados elementos ou membros do conjunto.
Escrevemos
a∈A
para denotar que o elemento a pertence ao conjunto A.
Escrevemos
a 6∈ A
para denotar que o elemento a não pertence ao conjunto A.
Usamos normalmente letras maiúsculas para denotar conjuntos, e minúsculas

para denotar elementos destes conjuntos.

Formas de definir um conjunto
Listar seus elementos entre chaves:
1 {Ana, Bia, Carlos} 2 {Júpiter, 2, π, Ana} 3 {1, 2, 3, . . . , 100}
Especificar uma propriedade que define um conjunto, como em

S = {x | P(x)}:
1 {x ∈ R | −2 ≤ x ≤ 5} 2 {x ∈ N | x é primo e x > 431}
Usar uma definição recursiva:

(
1 ∈ A,
1
se x ∈ A e x + 2 < 10, então x + 2 ∈ A.

Formas de definir um conjunto
Especificar uma função caracterı́stica:

( (
1, se x = 1, 3, 5, 7, 9, 1, se x ∈ N é primo,
1 µA (x) = 2 µA (x) =
0, caso contrário. 0, caso contrário.
Nem sempre é possı́vel utilizar todos os tipos de definição:

1 Não é possı́vel definir o conjunto S = {x ∈ R | 0 ≤ x ≤ 1} listando todos os
seus elementos.

Alguns conjuntos importantes
Alguns conjuntos importantes são:

1 N = {0, 1, 2, 3, 4, 5, . . .} é o conjunto dos números naturais.
2 Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .} é o conjunto dos números inteiros.
3 Z+ = {1, 2, 3, 4, 5 . . .} é o conjunto dos números inteiros positivos.
4 Q = {p/q | p ∈ Z, q ∈ Z, e q 6= 0} é o conjunto dos números racionais.
5 R é o conjunto dos números reais.
6 R+ é o conjunto dos números reais positivos.
7 C é o conjunto dos números complexos.

Igualdade de conjuntos
Dois conjuntos são iguais sse eles possuem os mesmos elementos.

Formalmente, para todos conjuntos A e B,
A=B ↔ ∀x : (x ∈ A ↔ x ∈ B).
A definição de igualdade de conjuntos implica que:
A ordem na qual os elementos são listados é irrelevante:
1 {a, b, c, d} = {d, c, b, a} = {c, a, d, b}
Elementos podem aparecer mais de uma vez no conjunto:
1 {a, a, a, a, b, b, b, c, c, d} = {a, b, c, d}

Subconjuntos
Um conjunto A é chamado subconjunto de um conjunto B sse cada

elemento de A também é um elemento de B.
Usamos A ⊆ B para denotar que A é subconjunto de B.
Formalmente:
A⊆B ↔ ∀x : (x ∈ A → x ∈ B).
As frases “A está contido em B” e “B contém A” são formas alternativas

de dizer que A é um subconjunto de B.
1 O conjunto dos naturais é um subconjunto dos inteiros.
2 O conjunto de brasileiros é um subconjunto do conjunto de brasileiros. (Nada

impede que um conjunto seja um subconjunto de si próprio!)
3 O conjunto dos números complexos não é um subconjunto dos números reais.

Subconjuntos próprios
Um conjunto A é subconjunto próprio de um conjunto B sse cada elemento

de A está em B e existe pelo menos um elemento de B que não está em A.
Formalmente:
A⊂B ↔ ∀x : (x ∈ A → x ∈ B) ∧ ∃x : (x ∈ B ∧ x 6∈ A)
↔ A⊆B ∧ A 6= B.
1 O conjunto dos naturais é um subconjunto próprio do conjunto dos inteiros.
2 O conjunto dos brasileiros não é um subconjunto próprio dos brasileiros.

Diagramas de Venn
Se os conjuntos A e B forem representados por regiões no plano, relações
entre A e B podem ser representadas por desenhos chamados de Diagramas
de Venn.
Exemplo 1: A ⊆ B.
Exemplo 2: A 6⊆ B.

Diagramas de Venn não podem ser usados como demonstração!
O conjunto vazio
O conjunto vazio ou conjunto nulo não contém elementos.

Denotamos o conjunto vazio por {} ou ∅.
Note que {∅} não denota o conjunto vazio, mas o conjunto cujo único
elemento é o conjunto vazio.
Teorema: O conjunto vazio é subconjunto de qualquer conjunto.
Prova. Seja A um conjunto qualquer. Então
∀x : (x ∈ ∅ → x ∈ A)
é verdade por vacuidade, já que a premissa da implicação é sempre falsa.

Logo ∅ ⊆ A.

Conjunto potência
Dado um conjunto A, o conjunto potência de A é o conjunto de todos os

subconjuntos de A.
Denotamos por P(A) o conjunto potência de A.
Exemplos:
1 Dado o conjunto S = {x, y , z}, seu conjunto potência é
P(S) = {∅, {x}, {y }, {z}, {x, y }, {x, z}, {y , z}, {x, y , z}}.
2 Dado o conjunto vazio ∅, seu conjunto potência é
P(∅) = {∅}.

Conjunto potência
Teorema: Se um conjunto finito A tem n elementos, então P(A) tem 2n

elementos.
Prova. Para formar um subconjunto S qualquer de A, podemos percorrer

cada elemento ai ∈ A (1 ≤ i ≤ n), decidindo se ai ∈ S ou se ai 6∈ S.
Como para cada elemento há duas opções (pertence ou não pertence), e há
um total de n elementos em A, há 2n maneiras de se formar um subconjunto
S de A.
Logo, |P(A)| = 2n .

Tuplas ordenadas
Uma n-tupla ordenada (a1 , a2 , . . . , an ) é uma coleção ordenada de n

elementos, em que a1 é o primeiro elemento, a2 é o segundo elemento, . . ., e
an é o n-ésimo elemento.
Algumas n-tuplas ordenadas recebem nomes especiais:
Uma 2-tupla ordenada é chamada de par ordenado.

Uma 3-tupla ordenada é chamada de tripla ordenada.
Uma 4-tupla ordenada é chamada de quádrupla ordenada.
...
Duas n-tuplas ordenadas (x1 , x2 , . . ., xn ) e (y1 , y2 , . . ., yn ) são iguais sse
xi = yi , para i = 1, . . . n.

Produto Cartesiano
Sejam A e B conjuntos. O produto cartesiano de A e B, denotado A × B, é

o conjunto de todos os pares ordenados (a, b), onde a ∈ A e b ∈ B.
Formalmente:
A × B = {(a, b) | a ∈ A e b ∈ B}.
Exemplo 3: Sejam A = {1, 2} e B = {a, b, c}.
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}
A × A = A2 = {(1, 1), (1, 2), (2, 1), (2, 2)}
Note, em geral, que A × B 6= B × A.

Produto Cartesiano
Produtos cartesianos podem ser generalizados para mais de dois conjuntos.
Sejam A1 , A2 , . . . , An conjuntos.
O produto cartesiano de A1 , A2 , . . . , An , denotado
A1 × A2 × . . . × An ,
é o conjunto de todas n-tuplas ordenadas (a1 , a2 , . . . , an ), onde ai ∈ Ai para
i = 1 . . . n.
Formalmente:
A1 × A2 × . . . × An = {(a1 , a2 , . . . , an ) | ai ∈ Ai para i = 1 . . . n}
Exemplo 4: Sejam A = {0, 1}, B = {a, b}, C = {γ, δ}.
A × B × C = {(0, a, γ), (0, a, δ), (0, b, γ), (0, b, δ),

(1, a, γ), (1, a, δ), (1, b, γ), (1, b, δ)}

O tamanho de conjuntos finitos
Seja A um conjunto finito contendo exatamente n elementos distintos.

Dizemos que a cardinalidade (ou tamanho) de A é n.
A notação |A| = n indica que o tamanho de A é n elementos.
Estudaremos a cardinalidade de conjuntos infinitos mais adiante.

Operações em conjuntos

Operações em conjuntos: Introdução
Dois ou mais conjuntos podem ser combinados de diferentes maneiras.

Por exemplo, dados o conjunto de estudantes de Matemática Discreta e o
conjunto de pessoas nascidas em Minas Gerais, podemos definir:
1 o conjunto de mineiros que estudam Matemática Discreta,
2 o conjunto de pessoas que são mineiras ou estudam Matemática Discreta,
3 o conjunto de estudantes de Matemática Discreta que não são mineiros,
4 ...
Aqui estudaremos operações em conjuntos que permitem a criação de

conjuntos mais complexos a partir de conjuntos mais simples.

Sejam A e B subconjuntos do conjunto universal U:
União: A∪B = {x ∈ U | x ∈ A ∨ x ∈ B}
Alternativamente: x ∈A∪B ↔ x ∈A ∨ x ∈B
Sn
Notação: i=1 Ai = A1 ∪ A2 ∪ . . . ∪ An
Interseção: A∩B = {x ∈ U | x ∈ A ∧ x ∈ B}
Alternativamente: x ∈A∩B ↔ x ∈A ∧ x ∈B
Tn
Notação: i=1 Ai = A1 ∩ A2 ∩ . . . ∩ An
Diferença: A−B = {x ∈ U | x ∈ A ∧ x 6∈ B}
Alternativamente: x ∈A−B ↔ x ∈ A ∧ x 6∈ B
Complemento: A = {x ∈ U | x 6∈ A}
Alternativamente: x ∈A ↔ x 6∈ A

Exemplo 5: Sejam os conjuntos A = {1, 3, 4, 5} e B = {1, 2, 5, 6}.

Considere como conjunto universo U = {0, 1, 2, 3, 4, 5, 6, 7}.
A ∪ B = {1, 2, 3, 4, 5, 6} B − A = {2, 6}
A ∩ B = {1, 5} A = {0, 2, 6, 7}
A − B = {3, 4} B = {0, 3, 4, 7}

Dois conjuntos A e B são iguais se, e somente se, cada elemento de A está
em B, e cada elemento de B está em A.
Uma maneira conveniente de se mostrar que dois conjuntos são iguais é

mostrando que cada conjunto é subconjunto do outro.
Formalmente:
A=B sse ∀x : (x ∈ A ↔ x ∈ B).
Teorema: A = B sse A ⊆ B e B ⊆ A.
Prova. Escrevendo A ⊆ B e B ⊆ A formalmente:

A=B
≡ ∀x : (x ∈ A ↔ x ∈ B) (definição de igualdade)
≡ ∀x : ((x ∈ A → x ∈ B) ∧ (x ∈ B → x ∈ A)) (definição de ↔)
≡ (∀x : (x ∈ A → x ∈ B)) ∧ (∀x : (x ∈ B → x ∈ A)) (distributividade de ∀ sobre ∧)
≡ A⊆B ∧B ⊆A (definição de ⊆)

Exemplo 6: Mostre que (A ∩ B) = A ∪ B.
Solução.
Médodo 1: Manipulando a definição dos operadores em conjuntos.

Vamos mostrar que x ∈ (A ∩ B) sse x ∈ (A ∪ B):
x ∈ (A ∩ B) ↔ x 6∈ (A ∩ B) (definição de complemento)
↔ ¬(x ∈ (A ∩ B)) (definição de 6∈)
↔ ¬((x ∈ A) ∧ (x ∈ ∩B)) (definição de interseção)
↔ ¬(x ∈ A) ∨ ¬(x ∈ B) (de Morgan)
↔ (x 6∈ A) ∨ (x 6∈ B) (definição de 6∈)
↔ (x ∈ A) ∨ (x ∈ B) (definição de complemento)
↔ x ∈ (A ∪ B) (definição de união)

Exemplo 6: (Continuação)
Médodo 2: Usando uma tabela de pertinência, em que usamos o sı́mbolo 1

para indicar que um elemento pertence a um conjunto, e o sı́mbolo 0 para
indicar que ele não pertence.
A tabela abaixo demonstra que um elemento pertence a (A ∩ B) (quarta
coluna) sse ele pertence a A ∪ B (sexta coluna):
A B A∩B (A ∩ B) A B A∪B
1 1 1 0 0 0 0
1 0 0 1 0 1 1
0 1 0 1 1 0 1
0 0 0 1 1 1 1

Sejam todos os conjuntos abaixo subconjuntos do conjunto universal U.
Comutatividade A∩B = B ∩A A∪B = B ∪A

(A ∩ B) ∩ C = (A ∪ B) ∪ C =
Associatividade
A ∩ (B ∩ C ) A ∪ (B ∪ C )
A ∪ (B ∩ C ) = A ∩ (B ∪ C ) =
Distributividade
(A ∪ B) ∩ (A ∪ C ) (A ∩ B) ∪ (A ∩ C )
União e interseção com U A∩U = A A∪U = U
Complemento duplo A = A
Idempotência A∩A = A A∪A = A
De Morgan (A ∩ B) = A ∪ B (A ∪ B) = A ∩ B
Absorção A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A
Diferença de conjuntos A−B = A∩B
União e interseção com ∅ A∪∅ = A A∩∅ = ∅
União e interseção com o
A∪A = U A∩A = ∅
complemento
Complementos de U e ∅ U = ∅ ∅ = U
Conjuntos disjuntos
Dois conjuntos são chamados disjuntos sse eles não têm nenhum elemento
em comum.
Formalmente:
A e B são disjuntos ↔ A ∩ B = ∅.
Proposição: Dados dois conjuntos A e B, (A − B) e B são disjuntos.
Prova. Por contradição. Suponha que a afirmação seja falsa, ou seja, que
existem conjuntos A e B tais que (A − B) ∩ B 6= ∅. Neste caso existe um
elemento x tal que x ∈ (A − B) ∧ x ∈ B. Note que, em particular, isso
significa que x ∈ B.
Por outro lado, também teremos x ∈ (A − B), o que, pela definição de
diferença, significa que x ∈ A ∧ x 6∈ B. Em particular, isso implica que x 6∈ B.
Logo chegamos a uma contradição, uma vez que x ∈ B e x 6∈ B. Portanto, a
proposição deve ser verdadeira.

Partições de um conjunto
Os conjuntos A1 , A2 , . . . , An são chamados mutuamente disjuntos (ou

disjuntos par-a-par, ou sem sobreposição) sse Ai ∩ Aj = ∅ para todos
i, j = 1, 2, . . . , n e i 6= j.
Uma coleção de conjuntos não vazios {A1 , A2 , . . ., An } é uma partição do

conjunto A sse
(i) A = A1 ∪ A2 ∪ . . . ∪ An , e
(ii) A1 , A2 , . . . , An são mutuamente disjuntos.
Exemplo 7: {{1, 2, 5}, {3}, {4}} é uma partição de {1, 2, 3, 4, 5}.

Exemplo 8: N pode ser particionado entre o conjunto dos números pares e

o conjunto dos números ı́mpares.


O Paradoxo de Russell e a
Teoria de Conjuntos
“Ingênua”

O Paradoxo do Barbeiro
Vimos que um conjunto pode ser especificado através de uma propriedade

que define um conjunto, como em S = {x | P(x)}:
1 {x ∈ R | −2 ≤ x ≤ 5} 2 {x ∈ N | x é primo e x > 431}
Entretanto, a propriedade P(x) não pode ser uma propriedade qualquer.
Paradoxo do Barbeiro: “O barbeiro é alguém que barbeia todos aqueles, e

apenas aqueles, homens que não se barbeiam sozinhos.”
A pergunta é: o barbeiro barbeia a si mesmo?
Equivalentemente, seja b o barbeiro e seja B o conjunto de todas as pessoas
que o barbeiro b barbeia. Então:
b ∈ B?
Paradoxo: b ∈ B ↔ b 6∈ B!

O Paradoxo de Russell e a Teoria de Conjuntos “Ingênua”
O Paradoxo do Barbeiro é um caso especial do problema identificado por

Bertrand Russell:
Paradoxo de Russell: Se definirmos S como “o conjunto de todos os
conjuntos que não têm a si mesmo como elemento”, ou seja,
S = {A | A é um conjunto e A 6∈ A},
como decidir se S ∈ S?
Paradoxo: S ∈ S ↔ S 6∈ S!
Lições:
Teoria de Conjuntos “Ingênua” (“Naı̈ve set theory”) não pode ser usada sem
cuidado.
Para isso existem abordagens axiomáticas, como a de Zermelo-Fraenkel (“ZF
Set Theory”).

Md-Aula05 Conjuntos

Enviado por

Direitos autorais:

Formatos disponíveis

Md-Aula05 Conjuntos

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Md-Aula05 Conjuntos

Enviado por

Direitos autorais:

Formatos disponíveis

Conjuntos

Área de Teoria DCC/UFMG

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 1 / 31

Conjuntos são as estruturas discretas fundamentais sobre as quais todas as

A Teoria dos Conjuntos é capaz de representar toda a Matemática.

Os conceitos que estudaremos aqui são essenciais para diversas áreas,

funções, análise combinatória,

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 2 / 31

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 3 / 31

Um conjunto é coleção não-ordenada de objetos bem definidos,

Usamos normalmente letras maiúsculas para denotar conjuntos, e minúsculas

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 4 / 31

Listar seus elementos entre chaves:

1 {Ana, Bia, Carlos} 2 {Júpiter, 2, π, Ana} 3 {1, 2, 3, . . . , 100}

Especificar uma propriedade que define um conjunto, como em

1 {x ∈ R | −2 ≤ x ≤ 5} 2 {x ∈ N | x é primo e x > 431}

Usar uma definição recursiva:

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 5 / 31

Especificar uma função caracterı́stica:

Nem sempre é possı́vel utilizar todos os tipos de definição:

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 6 / 31

Alguns conjuntos importantes são:

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 7 / 31

Dois conjuntos são iguais sse eles possuem os mesmos elementos.

A definição de igualdade de conjuntos implica que:

A ordem na qual os elementos são listados é irrelevante:

1 {a, b, c, d} = {d, c, b, a} = {c, a, d, b}

Elementos podem aparecer mais de uma vez no conjunto:

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 8 / 31

Um conjunto A é chamado subconjunto de um conjunto B sse cada

As frases “A está contido em B” e “B contém A” são formas alternativas

1 O conjunto dos naturais é um subconjunto dos inteiros.

2 O conjunto de brasileiros é um subconjunto do conjunto de brasileiros. (Nada

3 O conjunto dos números complexos não é um subconjunto dos números reais.

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 9 / 31

Um conjunto A é subconjunto próprio de um conjunto B sse cada elemento

1 O conjunto dos naturais é um subconjunto próprio do conjunto dos inteiros.

2 O conjunto dos brasileiros não é um subconjunto próprio dos brasileiros.

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 10 / 31

O conjunto vazio ou conjunto nulo não contém elementos.

Teorema: O conjunto vazio é subconjunto de qualquer conjunto.

Prova. Seja A um conjunto qualquer. Então

é verdade por vacuidade, já que a premissa da implicação é sempre falsa.

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 12 / 31

Dado um conjunto A, o conjunto potência de A é o conjunto de todos os

2 Dado o conjunto vazio ∅, seu conjunto potência é

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 13 / 31

Teorema: Se um conjunto finito A tem n elementos, então P(A) tem 2n

Prova. Para formar um subconjunto S qualquer de A, podemos percorrer

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 14 / 31

Uma n-tupla ordenada (a1 , a2 , . . . , an ) é uma coleção ordenada de n

Algumas n-tuplas ordenadas recebem nomes especiais:

Uma 2-tupla ordenada é chamada de par ordenado.

Duas n-tuplas ordenadas (x1 , x2 , . . ., xn ) e (y1 , y2 , . . ., yn ) são iguais sse

Matemática Discreta Conjuntos Área de Teoria DCC/UFMG - 2019/01 15 / 31

Sejam A e B conjuntos. O produto cartesiano de A e B, denotado A × B, é

Exemplo 3: Sejam A = {1, 2} e B = {a, b, c}.

A × A = A2 = {(1, 1), (1, 2), (2, 1), (2, 2)}

Note, em geral, que A × B 6= B × A.