1. Demonstrar que o menor subgrupo de S_{n} que contém ( 1,2 ) e (1,2, \ldots, n) é S_{n}. (Em outras palavras, êstes ciclos geram S_{n}.)

Passo 1

Enunciado e dados (o que o problema pede e o que é dado):
  • É dado o grupo simétrico sobre n elementos e duas permutações em S_n:
    • a transposição (1\,2);
    • o n-ciclo (1\,2\,\dots\,n).
  • O que o enunciado pede: mostrar que o menor subgrupo de S_n que contém (1\,2) e (1\,2\,\dots\,n) é o próprio S_n. Em outras palavras, provar que as duas permutações dadas geram S_n.

Passo 2

Primeira ideia útil (conceito de conjugação e sua ação em transposições).
  • Definição rápida (sem jargão): se \sigma e \tau são permutações em S_n, a conjugação de \tau por \sigma é a permutação \sigma\tau\sigma^{-1}. Ela corresponde a “relabelar” os elementos segundo \sigma.
  • Propriedade chave que vamos usar e provar rapidamente: \sigma\,(a\,b)\,\sigma^{-1}=(\sigma(a)\,\sigma(b)),isto é, a conjugação envia a transposição (a\,b) para a transposição que troca \sigma(a) com \sigma(b).
  • Justificativa simples dessa propriedade: pegue um elemento arbitrário x.
    • Se x=\sigma(a) então \sigma^{-1}(x)=a, aplicando (a\,b) obtemos b, e depois \sigma volta para \sigma(b). Logo \sigma(a) vai para \sigma(b).
    • Se x=\sigma(b) análogo: vai para \sigma(a).
    • Se x não é nem \sigma(a) nem \sigma(b), então \sigma^{-1}(x) não é a nem b, então (a\,b) fixa \sigma^{-1}(x), e portanto \sigma\tau\sigma^{-1} fixa x.
      Assim, \sigma\,(a\,b)\,\sigma^{-1} troca exatamente \sigma(a) com \sigma(b), isto é, é (\sigma(a)\,\sigma(b)).

Passo 3

Aplicar a propriedade ao caso concreto com o n-ciclo \sigma=(1\,2\,\dots\,n).
  • Denote \sigma=(1\,2\,\dots\,n). Considere potências \sigma^{t} com t\in\{0,1,\dots,n-1\}.
  • Pela propriedade de conjugação: \sigma^{t}\,(1\,2)\,\sigma^{-t} = (\sigma^{t}(1)\\ \sigma^{t}(2)).
  • Observação sobre \sigma^{t}: \sigma^{t}(k)=k+t (adição feita módulo n, entendendo n+1 como 1, etc.). Portanto \sigma^{t}\,(1\,2)\,\sigma^{-t} = (1+t\\\ 2+t),onde as adições são moduladas por n.
  • Para t=0,1,\dots,n-2 obtemos explicitamente as transposições adjacentes (1\,2),\\ (2\,3),\\ \dots,\\ (n-1\\ n).(Para t=n-1 aparece a transposição (n\\\ 1), que também é válida, mas já temos as n-1 transposições adjacentes padrão.)

Passo 4

Mostrar que as transposições adjacentes (i\\ i+1) geram todo S_n.
  • Fato clássico (que vou demonstrar de forma elementar): as transposições adjacentes (1\,2),(2\,3),\dots,(n-1\\ n) geram todas as transposições arbitrárias (i\,j) com 1\le i<j\le n. E como qualquer permutação é produto de transposições, segue que essas transposições geram S_n.
  • Construção explícita de (i\,j) a partir das adjacentes (assuma i<j): (i\,j) = (i\,i+1)(i+1\,i+2)\cdots(j-1\,j)\,(j-2\,j-1)\cdots(i\,i+1).Vou explicar o porquê disso funcionar:
    • A parte da esquerda (i\,i+1)\cdots(j-1\,j) “empurra” o elemento i para a posição de j atravessando sucessivamente as posições; de forma análoga ela desloca outros elementos para a esquerda.
    • Em seguida, a parte (j-2\,j-1)\cdots(i\,i+1) “recoloca” todos os elementos, exceto trocando i com j.
    • Para checar formalmente, verifique a ação sobre cada rótulo:
      • O elemento i é enviado pela primeira sequência até j, e depois a segunda sequência o fixa em j.
      • O elemento j é movido para j-1,\\ j-2,\\ \dots,\\ i pela segunda sequência invertida e acaba em i.
      • Qualquer elemento fora do intervalo \{i,\dots,j\} é preservado por todas essas transposições.
    • Assim o produto tem exatamente o efeito de (i\,j).
  • Portanto, conhecendo todas as transposições adjacentes, podemos formar qualquer transposição (i\,j).

Passo 5

Concluir que as permutações dadas geram S_n.
  • Do

Passo 6

  • Do

Passo 7

  • Logo o subgrupo de S_n gerado por (1\,2) e (1\,2\,\dots\,n) contém todas as transposições e assim contém todo S_n. Sendo este subgrupo contido em S_n por definição, ele é exatamente S_n.

Resposta

S_n

Exercícios relacionados