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}.