Seja
um conjunto munido de uma operação binária *. Dizemos que
é um elemento idempotente para
se
.
(a) Suponhamos que
seja associativa. Mostre que
é anti-comutativa se, e somente se,
e
, para todos
.
(b) Mostre se * é associativa e anti-comutativa, então
, para todos
. (Sugestão: Considere
.)
(a) Suponhamos que
(b) Mostre se * é associativa e anti-comutativa, então
Passo 1
O enunciado dá um conjunto
com uma operação binária
. Define-se que
é idempotente se
. Há duas partes:
(a) Supondo que
é associativa, provar a equivalência:
é anti-comutativa se, e somente se, para todos
valem
e
(b) Supondo que
é associativa e anti-comutativa, mostrar que para todos
Antes de começar, preciso explicitar qual definição de “anti-comutativa” vou usar (essa é a definição padrão usada aqui): \emph{a operação
é anti-comutativa} significa
para todos
. Ou seja, sempre que dois elementos comutar (o produto nas duas ordens é igual) eles são iguais. Vou trabalhar com essa definição ao longo da resolução.
Passo 2
Vamos provar a direção "se
é anti-comutativa então
e
para todos
". Vou mostrar cada identidade separadamente, explicando passo a passo.
Primeiro, mostro que
para todo
.
- Pelo que significa associatividade: para quaisquer
, temos
Isto é simplesmente reescrever
e
; por associatividade não há ambiguidade na ordem de aplicação e as duas expressões coincidem. Assim, os dois produtos
com
(nas duas ordens) são iguais, isto é
. Em outras palavras,
e
comutam.
- Aplicando a definição de anti-comutatividade: se dois elementos comutam então eles são iguais. Como
e comutam, concluímos . Assim, para todo vale
ou seja, todos os elementos são idempotentes. (Explicação didática: associatividade nos dá a igualdade do produto nas duas ordens; anti-comutatividade transforma essa igualdade de produtos em igualdade dos fatores.)
Agora, mostro que
para todos
.
- Considere os elementos
e . Calcule e . Usando associatividade:
e
Mas já provamos que
. Substituindo
em cada expressão obtém-se
e
Assim
, ou seja,
e
comutam.
- Aplicando anti-comutatividade (comutação implica igualdade), obtemos
Mas
é exatamente
(notação sem parênteses, pela associatividade). Portanto
para todos
.
Resumo desta direção: a associatividade nos permitiu identificar pares que comutam; a hipótese de anti-comutatividade transforma essa comutação em igualdade dos elementos, produzindo as identidades pedidas.
Passo 3
Agora provamos a direção contrária: se, para todos
,
e
, então
é anti-comutativa (i. e., se
então
). Novamente, vou fazer passo a passo e explicar o raciocínio.
Sejam
tais que
Queremos provar
.
- Multiplico a igualdade
à direita por . Pela associatividade:
Avalio cada lado usando as hipóteses:
- O lado esquerdo é
. Pela hipótese (com , ) temos . - O lado direito é
. Pela hipótese temos . Usando a igualdade inicial não é ainda necessário; basta observar que .
Assim a igualdade
dá
- Agora multiplico essa nova igualdade
à direita por :
Avalio o lado direito:
. Pela hipótese
(com
,
) vale
. Portanto
- Mas da etapa 1 temos
. Usando a igualdade inicial (hipótese do começo), a etapa 2 nos dá e pela etapa 1 . Concluímos então
Portanto, sempre que
obtemos
. Isso prova que
é anti-comutativa sob as hipóteses dadas.
Comentário didático: a estratégia foi “colocar” um fator
ou
à direita para possibilitar usar a identidade
e a idempotência
; isso reduz produtos compostos a elementos simples e permite finalizar a igualdade.
Passo 4
Provar (b): supondo que
é associativa e anti-comutativa, mostrar
para todos
.
- Primeiro, por (a) já sabemos (ou podemos repetir o argumento) que anti-comutatividade + associatividade implicam as duas identidades fundamentais válidas para todos os elementos:
Vou usá-las livremente nesta parte.
-
Considere o produto
. Pela associatividade podemos reagrupá-lo de duas maneiras (isto é permitido por associatividade; vou escolher duas escritas que facilitam aplicar as identidades): - Agrupando à esquerda:
Observe que. Aplicando a identidade com e obtemos Assim, a expressão anterior reduz aLogo, pela primeira maneira de agrupar,- Agrupando de outra forma (colocando
juntos):
Agora use a identidadecom e , que dá . Substituindo, Assim, pela segunda forma de agrupar, -
As duas igualdades valem simultaneamente (são duas formas diferentes de avaliar a mesma expressão
), portanto
Reescrevendo, obtemos para todos
que é exatamente o que se queria mostrar.
Comentário sobre a ideia: a dica do enunciado (\emph{considere
}) é justamente explorar que, por associatividade, a mesma cadeia de fatores pode ser reagrupada de maneiras que permitem aplicar as identidades
com escolhas diferentes de
e
, levando à eliminação do fator do meio
.
Resposta
(a) A operação
é anti-comutativa (isto é,
) se, e somente se, para todos
valem
e
.\n(b) Se
é associativa e anti-comutativa então
para todos
.