Teoria dos Conjuntos e Partições

Prévia do material em texto

Partic¸o˜es
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Novembro de 2013
Suma´rio
• Intersec¸a˜o e unia˜o generalizadas.
• Partic¸a˜o.
Halmos
• Escreveu um dos livros
mais “lidos” sobre Teoria
dos Conjuntos.
Paul Richard Halmos (1916 – 2006)
Conjunto quociente
Dado n ∈ N∗, temos que Nn = {[0]n, [1]n, [2]n, . . . , [n − 1]n} e´ um
conjunto finito e
N = [0]n ∪ [1]n ∪ [2]n ∪ . . . ∪ [n − 1]n.
Por exemplo, N4 = {[0]4, [1]4, [2]4, [3]4} e´ um conjunto com 4
elementos e
N = [0]4 ∪ [1]4 ∪ [2]4 ∪ [3]4.
Mu´ltiplos
Definic¸a˜o Sejam n ∈ N. O conjunto dos mu´ltiplos de n e´ definido
por
M(n) = {m ∈ N : existe q ∈ N tal que m = nq}.
M(0) = {0}
M(1) = {0, 1, 2, . . . , n, . . .} = N
M(2) = {0, 2, 4, . . .} = [0]2
M(3) = {0, 3, 6, . . .} = [0]3
...
M(n) = {0, n, 2n, . . .} = [0]n
...
Considere o conjunto cujos elementos sa˜o os conjuntos de
mu´ltiplos de cada natural:
M = {M(n) : n ∈ N}.
Temos um conjunto infinito cujos elementos sa˜o conjuntos
(infinitos ou na˜o).
E temos que
N = M(0) ∪M(1) ∪M(2) ∪M(3) ∪ · · · ∪M(n) ∪ · · ·
Unia˜o generalizada
Definic¸a˜o Seja F um conjunto. Dizemos que F e´ uma fam´ılia se
todos os elementos de F sa˜o conjuntos.
Definic¸a˜o Seja U um universo e F uma fam´ılia de subconjuntos
de U . A unia˜o de F e´ o conjunto definido por⋃
F = {a ∈ U : existe X ∈ F tal que a ∈ X}.
Unia˜o generalizada
Notac¸a˜o
A`s vezes, F e´ definida por interme´dio de um conjunto de ı´ndices I ,
cujos elementos correspondem aos conjuntos em F .
Neste caso, temos que
F = {Xi : i ∈ I}
e podemos usar as seguintes notac¸o˜es para
⋃F :
⋃
{Xi : i ∈ I},
⋃
i∈I
Xi ou
⋃
Xi .
As notac¸o˜es acima sa˜o usadas, principalmente, quando a fam´ılia e´
infinita, ou finita, mas muito grande.
Por exemplo,
⋃
M =
⋃
{M(n) : n ∈ N} =
⋃
n∈N
M(n) =
⋃
M(n) =
{a ∈ N : existe X ∈ M tal que a ∈ X} =
{a ∈ N : existe M(n) tal que a ∈ M(n)} =
{a ∈ N : existe n ∈ N tal que a ∈ M(n)}.
Intersec¸a˜o generalizada
Definic¸a˜o Seja U um universo e F uma fam´ılia de subconjuntos
de U tal que F 6= ∅. A intersec¸a˜o de F e´ o conjunto definido por⋂
F = {a ∈ U : para todo X ∈ F temos que a ∈ X}.
Intersec¸a˜o generalizada
Notac¸a˜o
Quando F e´ definida por interme´dio de um conjunto na˜o vazio de
ı´ndices I , ou seja, quando
F = {Xi : i ∈ I},
podemos usar as seguintes notac¸o˜es para
⋂F :
⋂
{Xi : i ∈ I},
⋂
i∈I
Xi ou
⋂
Xi .
Problema
(1) Determine
⋂
N4.
(2) Determine
⋂
M.
Propriedades ba´sicas
Sejam F , F1 e F2 fam´ılias de conjuntos, F ′, F ′1 e F ′2 fam´ılias
na˜o vazias de conjuntos e A um conjunto. Temos que:
(1) Se F1 ⊆ F2, enta˜o
⋃F1 ⊆ ⋃F2.
(2) Se F ′1 ⊆ F ′2, enta˜o
⋂F ′2 ⊆ ⋂F ′1.
(3) Se A ∈ F , enta˜o A ⊆ ⋃F .
(4) Se A ∈ F ′, enta˜o ⋂F ′ ⊆ A.
Propriedades ba´sicas
(5)
⋃ ∅ = ∅.
(6) A ∩⋃F = ⋃{A ∩ X : X ∈ F}.
(7) A ∪⋂F ′ = ⋂{A ∪ X : X ∈ F ′}.
(8)
⋃F ′ = ⋂{X : X ∈ F ′}.
(9)
⋂F ′ = ⋃{X : X ∈ F ′}.
Partic¸a˜o
Definic¸a˜o Seja A um conjunto e F ⊆ P(A).
Dizemos que F e´ uma partic¸a˜o de A se:
(1) Para todo X ∈ F , temos que X 6= ∅.
(2) Para todos X ,Y ∈ F , se X 6= Y , enta˜o X ∩ Y = ∅.
(3)
⋃F = A.
Partic¸a˜o e equivaleˆncia
Definic¸a˜o Seja A um conjunto e P uma partic¸a˜o em A.
A relac¸a˜o induzida por P e´ a relac¸a˜o em A definida por:
∼P = {(a, b) ∈ A× A : existe X ∈ P tal que a, b ∈ X}.
Partic¸a˜o e equivaleˆncia
Proposic¸a˜o Seja A um conjunto e P uma partic¸a˜o em A. Temos
que ∼P e´ uma relac¸a˜o de equivaleˆncia em A.
Problema
(1) Quais sa˜o as classes de equivaleˆncia de ∼P?
(2) Qual e´ o conjunto quociente A/∼P?
Equivaleˆncia e partic¸a˜o
Proposic¸a˜o Seja A um conjunto e R uma relac¸a˜o de equivaleˆncia
em A. O conjunto quociente A/R e´ uma partic¸a˜o de A.
Exerc´ıcios
1. Exerc´ıcios do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo, 2006).
3. Exerc´ıcios da Lista 13.
	União generalizada
	Interseção generalizada
	Partição