multiconjuntos

Prévia do material em texto

Anotac¸o˜es sobre Multiconjuntos
Rodrigo Carlos Silva de Lima ‡
rodrigo.uff.math@gmail.com
‡
1
Suma´rio
1 Multiconjuntos 3
1.0.1 Notac¸o˜es de multiconjuntos . . . . . . . . . . . . . . . . . . . . . . 3
1.0.2 Unia˜o no sentido de conjuntos . . . . . . . . . . . . . . . . . . . . . 5
1.0.3 Intersec¸a˜o no sentido de conjuntos . . . . . . . . . . . . . . . . . . . 6
1.1 Unia˜o sobre multiconjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Soma sobre multiconjunto . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Nu´mero de elemento e ocorreˆncia . . . . . . . . . . . . . . . . . . . 11
1.2 Produto sobre multiconjunto . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Aplicac¸o˜es de multiconjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Ra´ızes de polinoˆmios . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Multiconjunto e fatorac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2
Cap´ıtulo 1
Multiconjuntos
Definic¸a˜o 1 (Multiconjunto). Seja Ω 6= ∅ um conjunto dado, que sera´ nosso conjunto de
discurso ( ou conjunto universo). Sejam A ⊂ Ω propriamente, g : Ω→ R o par composto
pelo conjunto A e a func¸a˜o g, denotado por (A, g) e´ um multiconjunto se
g(x) = 0, x ∈ Ac.
Em que Ac e´ o complementar de A em Ω. Podemos denotar o multiconjunto como
(A, gA) para deixar claro que g se anula fora de A . Diremos tambe´m que (Ω, f) e´ um
multiconjunto para qualquer f : Ω→ R.
1.0.1 Notac¸o˜es de multiconjuntos
Definic¸a˜o 2 (Notac¸a˜o para multiconjunto). Usaremos a seguinte notac¸a˜o para multicon-
juntos
(A, g) = {kg(k) | k ∈ A}.
O valor g(k) em kg(k) pode ser chamados de ı´ndice do elemento k, o ı´ndice pode ser
intepretado, como nu´mero de vezes que um elemento aparece no multiconjunto, se for
negativo como d´ıvida do multiconjunto . Por exemplo
{mapa2, estrela5}
3
CAPI´TULO 1. MULTICONJUNTOS 4
seria um multiconjunto com 2 mapas e 5 estrelas .
{Dinheiro−100}
um multiconjunto para simbolizar que se deve 100 unidades de um tipo de dinheiro .
{casa1, casa0, camisas20}
neste multi conjunto, casa na˜o e´ um elemento pois possui ı´ndice 0 , temos nele 20 camisas
e uma casa.
Definic¸a˜o 3 (Igualdade de multiconjuntos). Dizemos que
(A, g) = (B, f)
se g = f em Ω.
Observac¸a˜o 1. Com essa definic¸a˜o podemos ver que do ponto de vista formal um multi-
conjunto e´ equivalente a uma func¸a˜o, pore´m damos a esse conceito uma interpretac¸a˜o que
vai ale´m disso, assocciando, por exemplo a conjuntos em que cada elemento possui um
peso ou nu´mero associado a ocorreˆncia do elemento , entre outras interpretac¸o˜es poss´ıveis.
Enta˜o o que difere em nossa abordagem e´ a interpretac¸a˜o do objeto formal, que da´
um certo sentido ao objeto definido .
Definic¸a˜o 4 (Pertineˆncia). Dizemos que xt ∈ (A, g) ⇔ x ∈ Ω e g(x) = t > 0. Dizemos
que xt e´ elemento de (A, g), se t > 0 , se t < 0 dizemos que e´ anti-elemento ou d´ıvida de
(A, g).
Definic¸a˜o 5 (Multiconjuntos e conjuntos). Um multiconjunto (A, g) e´ dito ser um con-
junto, quando g assume apenas valores em {0, 1}, fazemos nesse caso a associac¸a˜o
(A, g) := A.
Propriedade 1. Se (∅, g) e´ multiconjunto, enta˜o g e´ a func¸a˜o nula .
CAPI´TULO 1. MULTICONJUNTOS 5
Demonstrac¸a˜o. Pela condic¸a˜o de (A, g) ser multiconjunto, temos que ter g vazia em
Ac, com A = ∅, Ac = Ω, logo g e´ a func¸a˜o nula e o u´nico multiconjunto da forma (∅, g) e´
(∅, 0) .
Propriedade 2. Vale que (A, 0) = (Ω, 0) para qualquer A ⊂ Ω.
Demonstrac¸a˜o. (A, g︸︷︷︸
g=0
), g e´ func¸a˜o nula em Ω , tambe´m em (Ω, 0), logo sa˜o iguais,
pela definic¸a˜o de igualdade de multiconjuntos.
Definic¸a˜o 6 (Unia˜o no sentido de multiconjuntos). Dados dois multiconjunto (A, g) e
(B, f) sua unia˜o (no sentido de multiconjuntos), denotada por
(A, g) ] (B, f),
e´ definida como
(A ∪B, g + f).
Ale´m disso (A∪B, g+f), e´ multiconjunto, isto e´, g+f se anula em (A∪B)c . A operac¸a˜o
de unia˜o e´ fechada.
Usaremos o s´ımbolo ] para tal unia˜o no sentido de multiconjuntos , para diferenciar
da unia˜o no sentido de conjuntos que definiremos a seguir .
Demonstrac¸a˜o. Caso A ou B sejam Ω, temos A ∪ B = Ω e da´ı (A ∪ B, g + f) e´
multiconjunto por definic¸a˜o . Agora o caso de A e B como subconjuntos pro´prios de Ω.
Como (A, g) e (B, f) sa˜o multiconjuntos, temos que g se anula em Ac, f se anula em
Bc, g+ f deve ter que se anular em (A∪B)c = Ac ∩Bc que e´ subconjunto de Bc e de Ac,
portanto g e f se anulam em (A∪B)c e da´ı sua soma g+ f , como quer´ıamos demonstrar
.
1.0.2 Unia˜o no sentido de conjuntos
Definic¸a˜o 7 (Unia˜o no sentido de conjuntos). Dados dois multiconjuntos (A, g) e (B, f),
definimos sua unia˜o no sentido de conjuntos como
(A, g) ∪ (B, f) = (A ∪B,max{g, f}).
Sendo que (A ∪B,max{g, f}) ainda e´ um multiconjunto .
CAPI´TULO 1. MULTICONJUNTOS 6
Demonstrac¸a˜o. Temos que mostrar que max{g, f} se anula fora em (A ∪ B)c =
Ac ∩Bc. Demonstramos que g e f se anulam em Ac ∩Bc, logo tambe´m seu ma´ximo .
Corola´rio 1 (Comutatividade). Vale que (A, g)∪(B, f) = (B, f)∪(A, g) pois max{g, f} =
max{f, g} e A ∪B = B ∪ A.
Propriedade 3. Se (A, g) e (B, f) sa˜o conjuntos enta˜o (A, g) ∪ (B, f) e´ conjunto .
Demonstrac¸a˜o. Vale pois max{g, f} assume valor 1 ou 0 .
Corola´rio 2 (Idempoteˆncia). Vale a propriedade de idempoteˆncia para unia˜o no sentido
de conjuntos
(A, g) ∪ (A, g) = (A ∪ A,max{g, g}) = (A, g).
Propriedade 4 (Associatividade da unia˜o ). Vale que
(C, h) ∪ [(A, g) ∪ (B, f)] = [(C, h) ∪ (A, g)] ∪ (B, f)
Demonstrac¸a˜o. A igualdade segue de max{h,max{f, g}} = max{h, f, g} = max{f,max{h, g}}.
1.0.3 Intersec¸a˜o no sentido de conjuntos
Definic¸a˜o 8 (Intersec¸a˜o no sentido de conjuntos). Dados dois multiconjuntos (A, g) e
(B, f), definimos sua intersec¸a˜o no sentido de multiconjuntos como
(A, g) ∩ (B, f) = (A ∩B,min{g, f}).
Demonstrac¸a˜o. (A ∩ B,min{g, f}) e´ um multiconjunto , pois g e f sa˜o nulas em
Ac ∩Bc logo tambe´m o mı´nimo .
Corola´rio 3 (Comutatividade). Vale que
(A, g) ∩ (B, f) = (B, f) ∩ (A, g).
Pois A ∩B = B ∩ A e min{g, f} = min{f, g}.
Propriedade 5. Se (A, g) e (B, f) sa˜o conjuntos enta˜o (A, g) ∩ (B, f) e´ conjunto .
CAPI´TULO 1. MULTICONJUNTOS 7
Demonstrac¸a˜o. Vale pois min{g, f} assume valor 1 ou 0 .
Propriedade 6. Vale que
A ]B = (A ∪B) ] (A ∩B),
em que A e B sa˜o multiconjuntos quaisquer .
Demonstrac¸a˜o. Temos que
(A, g) ] (B, f) = (A ∪B, g + f),
[(A, g) ∪ (B, f)] ] (A, g) ∩ (B, f) = (A ∪B,max g, f) ] (A ∩B,min g, f) =
= (A ∪B,max g, f +min g, f) = (A ∪B, g + f)
logo vale a propriedade .
Propriedade 7 (Existeˆncia do elemento neutro). Existe um elemento neutro da unia˜o
de multiconjuntos, que e´ (Ω, 0).
Demonstrac¸a˜o.
(Ω, 0) ∪ (A, g) = (A, 0) ] (A, g) = (A ∪ A, g + 0) = (A, g),
onde usamos que (Ω, 0) = (A, 0) e idempoteˆncia da unia˜o de conjuntos A ] A = A.
Corola´rio 4. Vale que
(Ω, gA) = (A, gA).
Propriedade 8 (Existeˆncia de inverso). Vale que
(A, gA) ] (A,−gA) = (Ω, 0)
por isso (A,−gA) e´ o inverso de (A, gA), todo elemento possui inverso .
Demonstrac¸a˜o. Pois vale
(A, gA) ] (A,−gA) = (A ∪ A, gA − gA) = (A, 0) = (Ω, 0).
CAPI´TULO 1. MULTICONJUNTOS 8
Corola´rio 5. Vale que a unia˜o de multiconjuntos tambe´m e´ associativa e comutativa,
pois unia˜o de conjuntos e adic¸a˜o de func¸o˜es tambe´m o sa˜o . Por isso temos um grupo
abeliano .
Definic¸a˜o 9 (Multiconjunto finito e infinito). Um multiconjunto (A, g) possui uma quan-
tidade finita de tipos de elementos se existe B ⊂ A finito tal que g 6= 0 em B e g = 0 ∈ Bc
, caso g 6= 0 em um subconjunto infinito de A dizemos que (A, g) possui quantidade
infinita de tipos de elementos .
Vamos considerar a partir de agora multiconjuntos finitos .
1.1 Unia˜osobre multiconjunto
Sejam dados Ak multiconjuntos para todo k ∈ Z; Definimos
t⊎
k=t
(A, gk) = (A, gt) ∀t ∈ Z.
b⊎
k=a
(A, gk) =
p⊎
k=a
(A, gk) ∪
b⊎
k=p+1
(A, gk) ∀p, a, b ∈ Z.
Corola´rio 6 (Unia˜o vazia). Em
b⊎
k=a
(A, gk) =
p⊎
k=a
(A, gk) ∪
b⊎
k=p+1
(A, gk)
tomando p = a− 1 tem-se
b⊎
k=a
(A, gk) = (
a−1⊎
k=a
(A, gk)) ∪
b⊎
k=a
(A, gk)
por isso
a−1⊎
k=a
(A, gk) deve ser o elemento neutro da unia˜o de multiconjuntos , (Ω, 0).
Tomando agora b = a− 1 em
b⊎
k=a
(A, gk) =
p⊎
k=a
(A, gk) ∪
b⊎
k=p+1
(A, gk),
CAPI´TULO 1. MULTICONJUNTOS 9
segue que
a−1⊎
k=a
(A, gk)) = (Ω, 0) =
p⊎
k=a
(A, g(k)) ∪
a−1⊎
k=p+1
(A, gk)
o que implica
p⋃
k=a
(A, gk)) = −
a−1⋃
k=p+1
(A, gk))
tomando a = 1 e substituindo p por −p
−p⊎
k=1
(A, gk) = −
0⊎
k=−p+1
(A, gk) =
= −((A, g(−p+1)) ∪ ∪(A, g(−p)) ∪ · · · (A, g(−1)) ∪ (A, g0) = −
p−1⊎
k=0
(A, g(−k)).
Logo se p ≥ 1
−p⊎
k=1
(A, gk) = −
p−1⊎
k=0
(A, g(−k)).
Exemplo 1. Damos sentido enta˜o a soma
n∑
k=1
f(k) ∀n ∈ Z,
como a soma sobre um multiconjunto .
tal soma para n ≥ 1 e´ uma soma sobre o multiconjunto unia˜o
{11, · · · , n1} = {11} ∪ {21} · · · {n1} =
= {· · · , 00, · · · 11, · · · , n0} ∪ {· · · , 00, · · · 10, 21, · · · , n0} ∪ · · · ∪ {· · · , 00, · · · 00, · · · , n1} =
usando a func¸a˜o delta de kronecker que satisfaz δ(k, k) = 1 e δ(k, j) = 0 se k 6= j enta˜o
= (Z, δ(1, ) ) ∪ (Z, δ(2, ) ) ∪ · · · ∪ (Z, δ(n, ) ) =
n⋃
k=1
(Z, δ(k, ) ),
Se n ≥ 1 tem-se
n⋃
t=1
(Z, δ(k, ) ) = (Z,
n∑
t=1
δ(t, ) ), logo
∑
k∈
n⋃
t=1
(Z,δ(t, ) )
f(k) =
∑
k∈(Z,
n∑
t=1
δ(t, ) )
f(k) =
∑
k∈Z
[
n∑
t=1
δ(t, k)]f(k) =
∞∑
k=−∞
n∑
t=1
δ(t, k)f(k) =
CAPI´TULO 1. MULTICONJUNTOS 10
=
n∑
t=1
f(t).
Logo a definic¸a˜o recupera o sentido comum de soma quando n ≥ 1. Se n = 0 , temos
a unia˜o vazia
n⋃
t=1
(Z, δ(t, ) ) = (Z, 0), portanto
∑
k∈
0⋃
t=1
(Z,δ(t, ) )
f(k) =
∑
k∈(Z,0)
f(k) =
∑
k∈Z
0.f(k) = 0 =
0∑
k=1
f(k),
soma chamada de soma vazia . Agora se n ≤ −1, escrevendo n = −p segue que
−p⋃
k=1
(A, gk) =
p−1⋃
k=0
(A,−g(−k)) = (A,−
p−1∑
k=0
g(−k)),
enta˜o ∑
k∈
−p⋃
t=1
(Z,δ(t, ) )
f(k) =
∑
k∈(Z,−
p−1∑
t=0
δ(−t, ) )
f(k) =
=
∑
k∈Z
[−
p−1∑
t=0
δ(−t, k)]f(k) = −
p−1∑
t=0
f(−t) =
−p∑
t=1
f(k).
Podemos mostrar que essa extensa˜o de conceito para somato´rio, tambe´m sai se defi-
nirmos
b∑
k=a
f(k) =
p∑
k=a
f(k) +
b∑
k=p+1
f(k),∀a, b, p ∈ Z,
com a condic¸a˜o inicial,
s∑
k=s
f(k) = f(s) ∀s ∈ Z.
Que implicam com argumento semelhante ao aplicado para os multiconjuntos, que
−
p−1∑
t=0
f(−t) =
−p∑
t=1
f(k)
e
s−1∑
k=s
f(k) = 0 ∀s ∈ Z.
Podemos assumir esse somato´rio como ja tendo a propriedade estendida e definir a
unia˜o a partir dos somato´rios, como fazemos a seguir .
CAPI´TULO 1. MULTICONJUNTOS 11
Definic¸a˜o 10 (Unia˜o de multiconjuntos-segunda definic¸a˜o). Definimos
n⋃
k=1
(A, gk)) = (A,
n∑
k=1
gk),
onde para cada k inteiro temos uma func¸a˜o gk : A→ R.
1.1.1 Soma sobre multiconjunto
Definic¸a˜o 11 (Soma sobre multiconjuntos ). Definimos∑
k∈(A,g)
f(k) :=
∑
k∈A
g(k)f(k).
1.1.2 Nu´mero de elemento e ocorreˆncia
Definic¸a˜o 12 (Nu´mero de ocorreˆncias de um elemento). O nu´mero de ocorreˆncia de um
elemento k ∈ A de (A, g) e´ dado por g(k).
Definic¸a˜o 13 (Nu´mero de elementos e anti-elementos de um multiconjunto ). Definimos
o nu´mero de tipos de elementos de um multiconjunto (A, g) como a soma
N(A) =
∑
k∈D
1
em que D ⊂ A e g e´ na˜o nula em D .
Definimos o nu´mero total de (A, g) como
Nt(A) =
∑
k∈A
|g(k)|.
Separamos A = B ∪C em que B e´ tal que g(k) ≥ 0 em B e C e´ tal que g(k) ≤ 0 ∈ C.
Definimos o nu´mero de elementos de A como
Ne(A) =
∑
k∈B
g(k),
e o nu´mero de anti-elementos (ou d´ıvidas) como
Nd(A) = −
∑
k∈C
g(k),
valendo
Ne(A) +Nd(A) = Nt(A).
CAPI´TULO 1. MULTICONJUNTOS 12
Exemplo 2. O multiconjunto {Banana10, casa1, carro1, dinheiro−1, Hotel0} possui 4 ti-
pos de elementos, nu´mero total de 13, uma d´ıvida e 12 elementos .
1.2 Produto sobre multiconjunto
Definic¸a˜o 14 (Produto sobre multiconjunto). Seja (A, g) um multiconjunto definimos o
produto´rio sobre ele como ∏
k∈(A,g)
f(k) =
∏
k∈A
f(k)g(k)
supondo f(k)g(k) bem definido .
1.3 Aplicac¸o˜es de multiconjuntos
1.3.1 Ra´ızes de polinoˆmios
Para estudar ra´ızes de polinoˆmios com coeficientes sendo nu´meros complexos, podemos
considerar nosso conjunto universo como sendo Ω = C o conjunto dos nu´meros complexos
. As ra´ızes podem aparecer com multiplicidade , por exemplo P (x) = (x − 1)2 , possui
raiz 1 com multiplicidade 2, podemos representar suas ra´ızes pelo multiconjunto
A = {12}.
Em geral, um polinoˆmio qualquer P (x) de C[x] pode ser escrito como P (x) =
n∏
k=1
(x−
ak)
αk , logo suas ra´ızes sa˜o os elementos do multiconjunto
A = {(a1)α1 , (a2)α2 , · · · , (an)αn},
os ind´ıces sa˜o a multiplicidade das ra´ızes .
Propriedade 9. Sejam p e g polinoˆmios com multiconjuntos de ra´ızes associados Ap e
Ag respectivamente, enta˜o o polinoˆmio produto p.g possui como multiconjunto associado
para raizes a unia˜o Ap ∪ Ag. Em s´ımbolos, vale que
Ap ∪ Aq = Aq.p.
CAPI´TULO 1. MULTICONJUNTOS 13
Demonstrac¸a˜o.
Sejam A o conjunto de ra´ızes de p, B conjunto de ra´ızes de q, enta˜o seja A ∪ B =
{a1, · · · , an}, se uma dessas ra´ızes na˜o aparece na fatorac¸a˜o de p ou q, colocamos seu
expoente como nulo, e por isso podemos escrever
p(x) =
n∏
k=1
(x− ak)ck , g(x) =
n∏
k=1
(x− ak)dk ⇒ p(x).g(x) =
n∏
k=1
(x− ak)dk+ck
Por isso o multiconjunto de soluc¸o˜es de p e´
Ap = {(a1)c1 , · · · , (an)cn}
o multiconjunto de soluc¸o˜es de q e´
Aq = {(a1)d1 , · · · , (an)dn}
o multiconjunto de soluc¸o˜es de pq e´
Aq.p = {(a1)d1+c1 , · · · , (an)dn+cn}
pore´m a unia˜o dos multiconjuntos e´
Ap ∪ Aq = {(a1)d1+c1 , · · · , (an)dn+cn},
pois somamos as func¸o˜es, portanto vale que
Ap ∪ Aq = Aq.p.
Exemplo 3. Seja p(x) =
n∏
k=1
(x−ak)ck , enta˜o podemos escrever o polinoˆmio como produto
sobre o multiconjunto de suas ra´ızes Ap = {(a1)c1 , · · · , (an)cn},
p(x) =
∏
k∈Ap
(x− k) =
∏
k∈A
(x− k)ck
1.4 Multiconjunto e fatorac¸a˜o
Exemplo 4. Um nu´mero fatorado como
n =
m∏
k=1
pαkk ,
CAPI´TULO 1. MULTICONJUNTOS 14
pode ser escrito como produto sobre o multiconjunto
{(p1)α1 · · · (pm)αm} = (A, g),
n =
∏
k∈(A,g)
k =
∏
k∈A
kαk .
Exemplo 5 (mmc). O mmc de dois nu´meros
n =
t∏
k=1
pαkk , m =
t∏
k=1
pckk
e´ dado por
mmc(n,m) =
t∏
k=1
p
max{αk,ck}
k
corresponde a um nu´mero com multiconjunto associado a unia˜o (no sentido de conjunto),
dos multiconjuntos associados a n e m .
Exemplo 6 (mdc). O mdc de dois nu´meros
n =
t∏
k=1
pαkk , m =
t∏
k=1
pckk
e´ dado por
mdc(n,m) =
t∏
k=1
p
min{αk,ck}
k
corresponde a um nu´mero com multiconjunto associado a intersec¸a˜o (no sentido de con-
junto), dos multiconjuntos associados a n e m .
Exemplo 7 (Produto). O produto de dois nu´meros
n =
t∏
k=1
pαkk , m =
t∏
k=1
pckk ,
corresponde ao produto´rio sobre a unia˜o no sentido de multiconjuntos dos multiconjuntos
associados a n e m .