Sistemas Algébricos_2013

Prévia do material em texto

Sistemas Algébricos
Estruturas Discretas 2013
Heloisa
HAC ED2013 1
Sistemas Algébricos
• Esta seção introduz algumas noções da álgebra abstrata, especialmente os 
sistemas algébricos chamados grupos.
• Sistemas algébricos tratam das propriedades de operações binárias 
definidas sobre um conjunto específico.
• As estruturas algébricas modelam diversos tipos de aritmética:
– adição de inteiros;
– multiplicação de números reais positivos
HAC ED2013 2
Operações
Aprendemos operações como:
– adição e divisão de números inteiros;
– ∧ (E) e ∨ (OU) no conjunto {V, F};
– ⊕ e ⊗ no conjunto Zn.
• Nesta parte do curso estudaremos com maior 
profundidade, e de forma genérica, operações definidas 
sobre conjuntos e suas propriedades algébricas.
HAC ED2013 3
Definição (Operação)
Seja A um conjunto. Uma operação em A é uma função cujo domínio 
contém A × A. 
Assim, uma operação em A é uma função cuja entrada é um par de 
elementos de A.
Essa definição implica:
– A operação está definida para todo par de elementos de A (caso 
contrário, não seria função).
– O resultado da operação é único para cada entrada (caso contrário não 
seria função).
– O resultado não está necessariamente em A. Se estiver, dizemos que a 
operação tem uma propriedade particular, de fechamento.
HAC ED2013 4
Exemplo
• Quais das operações +, -, ×, ÷ são operações em N?
• Adição: SIM. Função cujo domínio inclui qualquer par de números 
naturais.
• Multiplicação: SIM. Função cujo domínio inclui qualquer par de 
números naturais.
• Subtração: SIM, porém o resultado pode não ser um elemento de 
N.
• Divisão: NÃO. Divisão por zero não é definida.
HAC ED2013 5
Exemplo de operação
Seja f: Z × Z→ Z
definida por f(a, b) = |a - b|
A função f dá a distância entre a e b.
Dizemos que f é uma operação em Z.
Notação: 
A notação f(a,b) está correta, mas geralmente escrevemos um símbolo 
da operação entre os dois elementos:
a f b
Símbolo para denotar uma operação genérica: *
Em vez de f(a, b) = |a - b|
Podemos escrever a * b = |a - b|
HAC ED2013 6
Propriedades das operações
• Propriedade Comutativa
Seja * uma operação sobre um conjunto A. Dizemos que * é comutativa
sobre A se e somente se
∀ a, b ∈ A, a * b = b * a.
• Propriedade de Fechamento
Seja * uma operação sobre um conjunto A. Dizemos que * é fechada em 
A se e somente se
∀ a, b ∈ A, a * b ∈ A.
(A subtração não é fechada em N, mas é fechada em Z.)
HAC ED2013 7
propriedades...
• Propriedade Associativa
Seja * uma operação sobre um conjunto A. Dizemos que * é associativa
em A se e somente se
a, b, c ∈ A, (a * b)*c = a*(b * c).
(As operações + e × são associativas mas a subtração não é.)
Exemplo:
Considere a operação de subtração sobre Z
(2 – 5) – 4 = -7 Mas 2 – (5 – 4) = 1
HAC ED2013 8
• Elemento Identidade
Seja * uma operação sobre um conjunto A. Um elemento e ∈ A é 
chamado elemento identidade (ou simplesmente identidade) para * 
desde que 
a ∈ A, a * e = e * a = a.a ∈ A, a * e = e * a = a.
Os elementos identidades devem “funcionar” em ambos os lados da 
operação.
Exemplos: Considere o conjunto Z
– 0 é elemento identidade para +
– 1 é elemento identidade para ×
– A subtração de inteiros não tem elemento identidade.
HAC ED2013 9
• Proposição
Seja * uma operação definida em um conjunto A. Então, * pode ter, no 
máximo, um elemento identidade.
• Prova:
Suponha, por contradição que haja dois elementos identidade e e e´ em A, 
com e ≠ e´.
Considere e * e´. 
Como e é um elemento identidade, e * e´= e´. 
Como e´ é um elemento identidade, e * e´= e.
Então temos que e´ = e * e´ = e uma contradição à hipótese e ≠ e´.
⇒⇐
HAC ED2013 10
Inversos
• Seja * uma operação sobre um conjunto A e suponhamos que A tenha 
um elemento identidade. Seja a ∈ A. Dizemos que b é um inverso de a
se e somente se 
a * b = b * a = e.a * b = b * a = e.
(O inverso de um elemento deve “funcionar” em ambos os lados da 
operação.)
HAC ED2013 11
Exemplos
• Considere a operação + sobre os inteiros.
O elemento identidade para + é o 0.
Todo inteiro a tem um inverso:
a + (-a) = (-a) + a = 0a + (-a) = (-a) + a = 0
• Considere a operação * sobre os racionais (Q).
O elemento identidade para multiplicação é o 1.
Quase todos os números racionais tem um inverso:
Se x ∈Q, então 1/x é o inverso de x, exceto quando x=0.
HAC ED2013 12
O inverso deve ser único?
Para a maioria das operações conhecidas, os elementos têm no máximo 
um inverso:
Exemplos:
• Se a ∈ Z, existe um único b tal que a+b = 0.• Se a ∈ Z, existe um único b tal que a+b = 0.
• Se a ∈Q, existe no máximo um número racional b tal que ab=1.
• Se a ∈ Zn, existe no máximo um b ∈ Zn, tal que a⊗b = 1.
Entretanto, é possível que um elemento tenha mais que um inverso, 
dependendo da operação e do conjunto A.
HAC ED2013 13
Exemplo – elemento com mais de um 
inverso
• Operação * definida em {a, b, c, e}
* e a b c
e e a b c
a a a e e
HAC ED2013 14
a a a e e
b b e b e
c c e e c
� O elemento e é um elemento identidade.
� Tanto b como c são inversos de a, pois
a*b = b*a = e e a*c = c*a = e
Grupo
• Um grupo, assim como todas as estruturas algébricas, generaliza 
algumas operações.
• A noção de grupo decorre dos seguintes fatos:
– A maioria das operações que encontramos são associativas;
– A associatividade acarreta unicidade de inversos
• Um grupo é uma generalização das seguintes operações (entre 
outras):
– + em Z
– * nos racionais positivos
– ⊕ em Zn
HAC ED2013 15
Grupo
• Definição
Seja * uma operação definida em um conjunto G. Dizemos que o par (G,*) é 
um grupo se e somente se:
1. O conjunto G é fechado sob a operação *, isto é, 
∀ g, h ∈ G, g*h ∈ G.∀ g, h ∈ G, g*h ∈ G.
2. A operação * é associativa, isto é, 
∀ g, h, k ∈ G, (g*h)*k = g*(h*k).
3. Existe um elemento identidade e ∈ G para *, isto é, 
∃ e ∈ G, ∀ g ∈ G, g*e = e*g = g.
4. Para todo elemento g ∈ G existe um elemento inverso h ∈ G, isto é,
∀ g ∈ G, ∃ h ∈ G, g* h = h* g = e.
HAC ED2013 16
• Exemplos: 
1. (Z, +) é um grupo referido como “inteiros com adição”.
2. O exemplo dado anteriormente - operação * definida em {a, b, c, e} não 
é um grupo, pois o elemento a tem dois inversos.é um grupo, pois o elemento a tem dois inversos.
� Muitas vezes não é utilizado um símbolo genérico (como *) para denotar 
a operação de um grupo. Usa-se apenas a letra G representando o 
conjunto, assumindo-se que existe uma operação de grupo definida 
sobre ele.
HAC ED2013 17
Unicidade de inversos no grupo
Em um grupo, todo elemento tem um inverso e esse inverso é único.
• Proposição
Seja (G,*) um grupo. Todo elemento de G tem um inverso único em G.
• Prova:
Sabemos, por definição, que todo elemento em G tem um inverso. A 
questão é se é ou não possível um elemento de G ter dois (ou mais) 
inversos.
Suponhamos, por contradição, que g∈ G tenha dois inversos distintos h
e k.
HAC ED2013 18
Isto significa
g*h = h*g = g*k = k*g = e
onde e ∈ G é o elemento identidade para *. 
Pela propriedade associativa,
h*(g*k) = (h*g)*k.
Além disso,Além disso,
h*(g*k) = h*e = h e
(h*g)*k = e*k = k.
(Estamos levando em conta que k e h são inversos de g, e que e é um 
elemento identidade.)
Logo, h=k, contradizendo o fato que h≠k. ⇒⇐
HAC ED2013 19
Grupos Abelianos
• A operação de grupo não é necessariamente comutativa. Os grupos em 
que a operação * é comutativa têm um nome especial.
• Definição (Grupos Abelianos)
(são também chamados de grupos aditivos ou grupos comutativos.)
Seja (G,*) um grupo. Dizemos que este grupo é abeliano se * é uma 
operação comutativa em G, isto é, 
∀ g, h ∈ G, g*h = h*g.
• Exemplos:
(Z, +)e (Z10, ⊕) são abelianos.
HAC ED2013 20
Revendo os exemplos de grupo:
• (Z,+) inteiros com adição formam um grupo.
• (Q,+) racionais com adição formam um grupo.
• (Q,×) Racionais com multiplicação NÃO formam um grupo, pois • (Q,×) Racionais com multiplicação NÃO formam um grupo, pois 
0∈Q não tem inverso.
• (Q+,×) Racionais positivos com multiplicação formam um grupo.
• (Q - {0},×) racionais sem o zero com multiplicação formam um 
grupo.
HAC ED2013 21
Exemplos
• (Zn,⊕) é um grupo para todos os inteiros positivos n.
� (Zn,⊗) não é um grupo, por que o 0 não tem inverso.
� (2A, ∆) é um grupo. (A é um conjunto e ∆ é a diferença simétrica)� (2A, ∆) é um grupo. (A é um conjunto e ∆ é a diferença simétrica)
(demonstração: exercício)
HAC ED2013 22
Que elementos retirar de Zn para que (Zn,⊗) 
seja um grupo?
� (Zn,⊗) não é um grupo, por que o 0 não tem inverso.
� O problema é análogo a (Q,×).
� Se quisermos eliminar elementos de Zn para obter um grupo, o 
problema não é tão simples: não podemos simplesmente descartar o 0:problema não é tão simples: não podemos simplesmente descartar o 0:
� Em (Z10 - {0}, ⊗) a operação ⊗ não é fechada, pois:
2, 5 ∈Z10 - {0}, mas 2 ⊗ 5 = 0 ∉ Z10 - {0}
� Além disso, 2 e 5 não tem inverso.
HAC ED2013 23
• Para definir um subconjunto X de Zn de maneira que (X,⊗) seja um 
grupo, devemos eliminar todos os elementos que não tenham inversos.
• Ficamos com todos os elementos que são relativamente primos com n 
e eliminamos os demais.
Que elementos retirar de Zn para que (Zn,⊗) 
seja um grupo?
e eliminamos os demais.
• Em Z10 ficamos com {1, 3, 7, 9}.
• ({1, 3, 7, 9},⊗) forma um grupo.
HAC ED2013 24
⊗ 1 3 7 9
1 1 3 7 9
Tabela de operações para o grupo ({1, 3, 7, 9},⊗):
HAC ED2013 25
1 1 3 7 9
3 3 9 1 7
7 7 1 9 3
9 9 7 3 1
• Definição (ZZZZ*n)
Seja n um inteiro positivo. Definimos
Z*n = { a ∈ Zn | mdc(a, n) = 1}.
Exemplo: Exemplo: 
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}.
Elementos invertíveis em Z14 são: 1, 3, 5, 9, 11, 13.
Z*14 = {1, 3, 5, 9, 11, 13.}.
Inversos:
1-1 = 1 3-1 = 5 5-1 = 3
9-1 = 11 11-1 = 9 13-1 = 13
HAC ED2013 26
• Para todos os valores de n, retirando de Zn os elementos que não 
tem inverso, encontramos um conjunto que, com a operação de 
multiplicação modular, é um grupo.
• Proposição:• Proposição:
Seja n um inteiro positivo. Então (ZZZZ*n,⊗) é um grupo.
HAC ED2013 27
Z*14 = {1, 3, 5, 9,11,13}.
Tabela de operações para o grupo (Z*14,⊗):
Exemplo
1 3 5 9 11 13
1 1 3 5 9 11 131 1 3 5 9 11 13
3 3 9 1 13 5 11
5 5 1 11 3 13 9
9 9 13 3 11 1 5
11 11 5 13 1 9 3
13 13 11 9 5 3 1
HAC ED2013 28
Z*8 = {1, 3, 5, 7}.
Tabela de operações para o grupo (Z*8,⊗):
Exemplo
⊗ 1 3 5 7⊗ 1 3 5 7
1 1 3 5 7
3 3 1 7 5
5 5 7 1 3
7 7 5 3 1
HAC ED2013 29
Isomorfismo de grupos
• Dois grupos são isomorfos se são exatamente o mesmo, a menos dos 
nomes de seus elementos.
• Considere os grupos: (Z4,⊕ ) e (Z5*,⊗ )
(Z ,⊕ ) (Z* , ⊗ )
HAC ED2013 30
⊕ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
⊗ 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1
(Z4,⊕ ) (Z*5, ⊗ )
• São grupos diferentes porque são definidos em conjuntos diferentes.
• Para serem isomorfos, o primeiro requisito é que o conjunto tenha o 
mesmo numero de elementos:
|Z|Z|Z|Z4| = |Z*= |Z*= |Z*= |Z*5| = 4|Z|Z|Z|Z4| = |Z*= |Z*= |Z*= |Z*5| = 4
• Além disso:
– 1 e 3 são inversos um do outro em Z4
– 2 e 3 são inversos um do outro em Z5
– Somente 2 é seu próprio inverso em (Z4,⊕) (fora a identidade).
– Somente 4 é seu próprio inverso em (Z*5, ⊗) (fora a identidade).
HAC ED2013 31
• Podemos definir um emparelhamento entre os elementos dos 
grupos :
(Z4,⊕ ) (Z5*,⊗ )
HAC ED2013 32
0 ↔ 1
1 ↔ 2
2 ↔ 4
3 ↔ 3
⊕ ⊗ 0 1 1 2 2 4 3 3
Podemos superpor as tabelas de operação, trocando na tabela 
para (Z5*,⊗ ) as linhas e as colunas para os elementos 3 e 4.
0 1 0 1 1 2 2 4 3 3
1 2 1 2 2 4 3 3 0 1
2 4 2 4 3 3 0 1 1 2
3 3 3 3 0 1 1 2 2 4
HAC ED2013 33
• Mais formalmente, esse emparelhamento pode ser definido por:
Seja f: Z4→ Z5* definida por
• f(0) = 1 f(2) = 4
• f(1) = 2 f(3) = 3
• f é uma bijeção e 
f(x ⊕ y) = f(x) ⊗ f(y)
Os grupos (Z4,⊕ ) e (Z5*,⊗ ) são essencialmente o mesmo grupo e são 
ditos isomorfos.
HAC ED2013 34
Exemplo – grupos NÃO isomorfos
• Comparando (Z4,⊕ ) com (Z8,⊕ )
• No grupo (Z8,⊕ ) todo elemento é seu próprio inverso, o que não 
ocorre com os outros dois grupos.
• Assim, esses dois grupos não são isomorfos.
(Z4,⊕ ) (Z , ⊗ )
HAC ED2013 35
⊕ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
(Z4,⊕ ) (Z8, ⊗ )
⊗ 1 3 5 7
1 1 3 5 7
3 3 1 7 5
5 5 7 1 3
7 7 5 3 1
Exemplo – grupos NÃO isomorfos
• Comparando (Z4,⊕ ) com grupo-4 de Klein 
• No grupo-4 de Klein todo elemento é seu próprio inverso, o que não 
ocorre com os outros dois grupos.
• Assim, esses dois grupos não são isomorfos.
(Z4,⊕ ) Grupo-4 de Klein
HAC ED2013 36
⊕ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
* (0,0) (0,1) (1,0) (1,1)
(0,0) (0,0) (0,1) (1,0) (1,1)
(0,1) (0,1) (0,0) (1,1) (1,0)
(1,0) (1,0) (1,1) (0,0) (0,1)
(1,1) (1,1) (1,0) (0,1) (0,0)
(Z4,⊕ ) Grupo-4 de Klein
Isomorfismo de grupos
• Definição
Sejam os grupos (G,*) e (H, •). Uma função f: G → H é um isomorfismo
(de grupo) se e somente se f é um-a-um e sobre e verifica
g, h ∈ G, f(g*h) = f(g) • f(h).
Se existe um isomorfismo de G para H, dizemos que G é isomorfo a H e 
escrevemos G≅H.
HAC ED2013 37
• A relação isomorfo para grupos é uma relação de equivalência; isto 
é,
• Para qualquer grupo G, G ≅ G, (reflexiva)
• Para dois grupos quaisquer G e H, se G ≅ H então H ≅ G (simétrica)
• Para três grupos quaisquer G, H e K, se G ≅ H e H ≅ G, então G ≅ K 
(transitiva).
HAC ED2013 38