Matemática Discreta IBCC101
Teoria de Conjuntos
2
Teoria de Conjuntos
Tudo em matemática pode ser escrito em termos de conjuntosA Teoria de Conjuntos é adequada para descrever e explicar todas as estruturas matemáticas.
3
O que é um conjunto?Um conjunto é uma coleção de objetosCada objeto da coleção é dito um elemento do conjunto. Exemplos: 𝐍 = {0,1,2,3,…} números naturais
𝐙 = {…,-3,-2,-1,0,1,2,3,…} números inteiros
𝐐 = {n/m | n,m ∈ , m≠0 } 𝐙 números racionais
𝐑 números reais
4
Mais exemplos de conjuntos
𝐁 = {T,F} conjunto Booleano
C = {a,e,I,o,u} conjunto das vogais
D = {(0,0),(1,5),(3,2)} conjunto de pares de números
E = {{1,2},{10},{3,3,3}} conjunto de conjuntos
F = {3,{2,5},{5,8,2}} - elementos não precisam ser do mesmo tipo
- 3 ∈ F
- {2,5} ∈ F
- 2 ∉ F
5
Cardinalidade
Se A é um conjunto finito, a cardinalidade de A é o número de elementos de A
Notação: |A|Exemplos:
- A = {a,b,c,d} |A| = 4- B = {{1,2}, {1,2,3}} |B| = 2
6
Conjunto Vazio
{ } conjunto vazio: não possui elementos– 3 { }– x { } — não importa o que seja x– = { } — a letra Grega phi denota o
conjunto vazio
Observação: ≠ {}- || = 0- |{}| = 1
7
Exercício
F = {,{},{{}}}
1.Qual é a cardinalidade de F? 2. ∈ F ?3. ∈ {{}} ?
8
Notação para conjuntos { x | x {2, 3, 5, 7, 11} , x 4}
– {5, 7, 11} { x + x | x {2, 3, 5, 7, 11} , x 3 , x 11}
– {6, 10, 14}
{f x | x A, p x}– Denota o conjunto cujos elementos têm a forma (f
x), onde x vem de A e é tal que (p x) é verdadeira (True)
Para evitar contradições:– O predicado deve especificar o universo de discurso– Examplos inválidos:
{X | X é um conjunto}{X | X X}Nestes exemplos, o universo de discurso não é
especificado
9
ExercíciosListar os elementos dos seguintes conjuntos:
1.{n ∈ | n é primo}𝐍2.{n2 | n ∈ }𝐙
3.{x ∈ | x𝐑 2 – 2 = 0}
4.{x ∈ | x𝐙 2 – 2 = 0}
5.{x ∈ | |x| < 4}𝐙6.{2x ∈ | |x| < 4}𝐙7.{x ∈ | |2x| < 4}𝐙8.{X | X ∈ {{1,2},{3,4,5,6},{7}}, |X|<3 }
Subconjuntos, IgualdadeA é um subconjunto de B– Definição: A B x. (x A x B)
– Exemplos• {2, 3, 5, 7} {2, 3, 5, 7, 11}• A — independentemente do que seja A
Igualdade entre conjuntos– Definição: A = B (A B) e (B A)
A é um subconjunto próprio de B– Definição: A B (A B) e (A B)
11
Exercícios
1. 1 ∈ {1,{1}}
2. 1 {1,{1}}
3. {1} ∈ {1,{1}}
4. {1} {1,{1}}
5. {{1}} ∈ {1,{1}}
6. {{1}} {1,{1}}
7. 𝐍 ∈ 𝐍8. 𝐍 𝐍9. ∈ 𝐍10. 𝐍
11. 𝐍 ∈ { }𝐍12. 𝐍 { }𝐍13. ∈ { }𝐍14. { }𝐍15. ∈ {, }𝐍16. {, }𝐍17.{ } 𝐍 {, }𝐍18.{ } 𝐍 {,{ }}𝐍19.{ } 𝐍 ∈ {,{ }}𝐍20. ∈
Quais afirmações são verdadeiras?
12
Operações Conjunto Potência
Cojunto Potência de A– Definição: P(A) = {S | S A}– Exemplos
• P({2, 3, 5}) = {, {2}, {3}, {5}, {2,3}, {2,5}, {3,5}, {2,3,5}}
• P() = {}
– |P(A)| = 2|A|
– Isso será provado mais tarde, usando indução • Quantos elementos tem P(P())?
– P(P()) = { , {} }• Quantos elementos tem P(P(P()))?
– P(P(P())) = { , {}, {{}}, {, {}} }• Quantos elementos tem P(P(P(P())))?
– 24 = 16• Quantos elementos tem P(P(P(P(P()))))?
– 216 — um bocado! em torno de 65.000
13
Exercícios
Liste todos elementos de cada conjunto:
1.P({0,1,3})
2.P({1})
3.P()
4.P({1,{1,2}})
5.P({ ,𝐙 𝐍})
14
Operações: Produto Cartesiano
Produto Cartesiano de A e B– Definição: A B = {(a, b) | a A e b B}
• |A x B| = |A| x |B|
– Exemplos• {2, 3} {3, 5, 7} = {(2,3), (2,5), (2,7), (3,3), (3,5),
(3,7)}• {0, 1, 2, …} {1, 2, 3, …} = conjunto de todos os pares
de números naturais em que o segundo componente ≠ 0
Exercício:- Quantos elementos tem A P(A)? (Suponha que A tem n elementos)
15
Operações: União e Interseção União de A e B
– Definição: A B = {x | x A ou x B}– Outra maneira: x. (x A B) (x A ∨ x B)– Exemplos
• {2, 3, 5} {5, 7, 11} = {2, 3, 5, 7, 11}• A = A — independentemente do que seja A• {, {}} { {{}}, {, {}} } = {, {}, {{}}, {,
{}} }
Interseção de A e B– Definição: A B = {x | x A e x B}– Exemplos
• {2, 3, 5, 7} {2, 7, 11} = {2, 7}• A = — independentemente do que seja A
Conjuntos disjuntos– Definição: A e B são disjuntos A B =
16
Operações: Diferença e Complemento Diferença A menos B
– Definição: A – B = {x | x A e x B}– Exemplos
• {2, 3, 5, 7} – {2, 7, 11} = {3, 5}• A – = A — independentemente do que seja A• – A = — independentemente do que seja A
• Complemento de A– Definição: A’ = U – A onde U é o universo de discurso– Exemplos - universo de discurso = {0, 1, 2, …}
• {2, 3, 4, 5}’ = {0, 1} {6, 7, 8, …}• {2x | x {0, 1, 2, …}} ’ = {2x+1 | x {0, 1, 2, …}}
Exercícios
1. A B 2. A B3. A – B4. B – A5. (A-B) (B-A)
6. A C7. A C8. A – C9. (A C) (A – C)
Sejam A = {a,b,c,d,e} B={d,e,f} C={1,2,3}
10.(A B) x B11.(AxC) (BxC)
18
Famílias de conjuntos
União de uma família de conjuntos S– Definição: S = {x | x A para algum AS. }– Outra maneira: x. (x S) (A. AS x A)– Exemplos
• { {2, 3, 5}, {5, 7, 11}, {2, 5, 13, 17} } = {2, 3, 5, 7, 11, 13, 17}
Interseção de uma família de conjuntos S– Definição: S = {x | x A, para todo AS}– Exemplos
• { {2, 3, 5, 11}, {5, 7, 11}, {2, 5, 7, 11, 13, 17} } = {5, 11}
• { {xn | x {1, 2, …}} | n {0, 1, 2, …} } = {1}
19
Famílias indexadas de conjuntos
Sejam A1, A2, … , An tais que Ai = {-i, …,0….,i}
União
Interseção
Exemplo: A1={-1,0,1} A2={-2,-1,0,1,2} An={-n,…,-1,0,1,…,n}
Exercícios
1.
1.
3.
6.
Determine os seguintes conjuntos
21
Princípio da Boa Ordenação
Todo subconjunto não vazio de números naturais tem um menor elemento:
A ⊆ e A≠𝐍 → existe x0∈A tal que
x0 ≤ x, para todo x∈A
É uma propriedade fundamental de 𝐍Não vale para números reais:
A = {1/n | n∈ } não tem um menor 𝐍elemento
22
Princípio da Boa Ordenação- consequência
Algoritmo de Divisão: Dados dois números naturais a e b, com b>0, existem números naturais q e r tais que a = qb + r e 0 ≤ r < b
Prova: Dados a e b, com b>0, construa o conjuntoA = {a – xb | x∈ , 0 ≤ a – xb} 𝐙
Por exemplo, se a=17 e b=3, A ={2,5,8,11,14,17,…}A é não vazio. Seja r o menor elemento de A.Então r=a–qb, p/ algum q∈ e, portanto, a=qb+r.𝐙Além disso, r<b: se r≥b, então um número não negativo r-b=(a-qb)-b=a-(q+1)b, da forma a–xb seria o menor elemento de A, ao invés de ser r.
23
Paradoxo de Russel Bertrand Russell (1872-1970)
Uma teoria ingênua de conjuntos pode levar a paradoxos. Considere:
A = {X | X é um conjunto e X ∉ X}
- {1,2} ∈ A
- ∈𝐍 A
- Seja X = {X}. X ∉ A
Paradoxo: A∈A ?
24
Teoria Axiomática de Conjuntos
Para evitar os paradoxos que podem ocorrer em uma teoria ingênua de conjuntos, foi proposta, por Zermelo e Frankel, uma teoria axiomática, que inclui como axiomas:
Princípio da Boa Ordem Nenhum conjunto não vazio C pode ter a
propriedade de que C ∩ x ≠ , para todos os elementos seus elementos x que sejam conjuntos. Isso exclui conjuntos tais como X = {X}.