¿Existe algún tipo de correspondencia entre grupos y particiones de un conjunto?

Question

¿Existe algún tipo de correspondencia entre grupos y particiones de un conjunto?

Matemáticas
teoría de grupos
partición conjunto
álgebra abstracta

D Izquierda Adyacente a U

Cada acción de grupo en un set $S$ divide el conjunto en órbitas. Por el contrario, para cada partición de $S$ ¿Existe una acción de grupo tal que el conjunto de órbitas de la acción de grupo sea igual a la partición?

Mi intento. Dejar $P = \{S_1,\dots, S_k\}$ sea una partición de un conjunto finito $S$ de orden $n$ . Luego hay elementos de $G = Perm(S)$ , el conjunto de permutaciones de $S$ , que dejan fijo cada subconjunto, es decir $g\in G$ tal que $g\cdot S_i = \{gs : s\in S_i\} = S_i, \forall i$ . Piensa en las permutaciones que arreglan todo $S$ excepto permutas $S_i$ posiblemente de alguna manera no trivial. Si $g, h$ son tales elementos entonces $gS_i = S_i, \forall i$ , entonces $g^{-1} S_i = S_i$ , siendo la acción también una acción sobre los subconjuntos. Similarmente $g\cdot h S_i = g S_i = S_i$ . Así, el conjunto de todos $P$ -elementos estabilizadores es un subgrupo de $G$ .

Los grupos se conocen en correspondencia con los subgrupos de $G$ . Por favor comenta.

Motivación: ¿existe una forma teórica de grupo para contar particiones de un conjunto de tamaño $n$ ? De modo que tal vez pueda ayudar a probar fórmulas sobre este último.

Según m_l en un comentario, aquí no hay ninguna aplicación para contar particiones aquí que no lleve a tener que contar las particiones de la manera conocida.

Estaba pensando, todavía no hemos considerado, al menos yo no, el conjunto de particiones de $S$ mismo, llámalo $P(S)$ , y el grupo $G = Perm(S)$ actuando sobre ello. lo bueno de $G = Perm(S)$ es que todo grupo finito es isomorfo a un subgrupo del mismo. Así que si $H \leqslant G$ , y $H'$ es el grupo presentado de alguna otra manera, entonces casi todo lo que decimos sobre $H$ se puede aplicar a $H'$ con respecto a las acciones grupales sobre $S$ o $P(S)$ . Con suerte, así que mantengamos eso en el fondo de nuestras mentes. En otras palabras, cada partición corresponde a una partición del conjunto de subgrupos de $G$ . Pero deberíamos decir más al respecto que eso. Me estoy desviando del camino aquí, así que sigo adelante...

Defina la acción de $G$ en $P(S),$ ser $g \cdot P = \cup_{i=|P|} \{ g\cdot S_i \}$ , dónde $g\cdot S_i$ es el elemento $g$ actuando en el bloque $S_i$ demandando la multiplicación simple de clases laterales. Relacionado con esto, hay una manera obvia de hacer $G$ actuar sobre el conjunto de todos los subconjuntos de $S$ .

De todos modos. Como puede ver la acción en $P(S)$ define una acción de grupo. Prueba: La permutación de identidad obviamente arregla una partición. Y $g(h P) = g\cdot\cup_{i=1..|P|} \{ h\cdot S_i \}$ . Tenga en cuenta que desde $g$ actúa sobre el conjunto de subconjuntos de $S$ , $g(hP) = (gh)P. \$ El resto de la prueba se deja al lector.

Cambiemos un poco la notación. $P\in P(S)$ ahora sera llamado $p$ , y $P(S)$ sera llamado $P$ .

Una órbita es simplemente $O_p = G\cdot p \subset P(S)$ . Tenemos la ecuación de clase

$|P(S)| = \sum_{orbits} |O_p|$

Lema de Burnside:

# órbitas $= 1/|G| \sum_{g\in G}|P^g|, \$ dónde $P^g$ es el conjunto de todas las particiones fijado por $g$ .

y la fórmula de conteo de índices

$|G| = |H_p||O_p| = |H_p|[G:H_p], \$ dónde $H_p = Stab(p)$ es el estabilizador de la partición $p$ .

sammy negro

Te has topado con el subgrupo.

Σ_{λ_{1}} \times \dots \times Σ_{λ_{k}}

$\Sigma_{\lambda_1} \times \cdots \times \Sigma_{\lambda_k}$ de

Σ_{n}

$\Sigma_n$ , dónde

(λ_{1}, \dots, λ_{k})

$(\lambda_1, \dots, \lambda_k)$ es la partición de

n

$n$ .

D Izquierda Adyacente a U

¿Tienes un nombre para eso? no puedo googlear eso

sammy negro

Creo que la palabra que estás buscando es "bloquear". Si todo el grupo simétrico actúa sobre el

n

$n$ -conjunto de elementos

S

$S$ , entonces el subgrupo que mencioné es el estabilizador de los bloques ( es decir, partes de la partición). en.wikipedia.org/wiki/Block_(permutation_group_theory)

m_l

Los bloques generalmente se consideran para acciones transitivas y los bloques se pueden asignar entre sí mediante una acción. Pero si, el estabilizador de

P

$P$ como una lista en el grupo simétrico en

S

$S$ es exactamente el producto directo de los grupos simétricos en el

S_{i}

$S_i$ .

D Izquierda Adyacente a U

¿Hay alguna forma de contar las particiones de

S

$S$ ¿usando esto?

D Izquierda Adyacente a U

Respuestas bienvenidas. Mi motivación fue otro problema que mostraba

p (n)^{2} < p (n^{2} + 2 n)

$p(n)^2 \lt p(n^2 + 2n)$ o algo similar donde

p

$p$ es el número de particiones de un conjunto de tamaño

n

$n$ . Me preguntaba si hay una forma teórica de grupo para mostrar eso. Gracias por el complemento.

m_l

No veo una forma de contar particiones usando esta correspondencia que no implique contar particiones. El enfoque obvio sería contar los productos directos

S_{λ_{1}} \times \dots \times S_{λ_{k}}

$S_{\lambda_1} \times \ldots \times S_{\lambda_k}$ , pero esto es exactamente lo mismo que contar las particiones. Tenga en cuenta también la diferencia algo sutil entre el estabilizador de

P

$P$ y el subgrupo que estabiliza cada

S_{i}

$S_i$ (el estabilizador de

P

$P$ todavía puede permutar

S_{i}, S_{j}

$S_i, S_j$ como bloques si

| S_{i} | = | S_{j} |

$|S_i| = |S_j|$ ).

m_l

Una cosa más que me viene a la mente es la teoría de la representación del grupo simétrico. El número de particiones de

{1, \dots, n}

$\{1,\ldots,n\}$ es igual al número de representaciones irreducibles de

S_{n}

$S_n$ .

Marc van Leeuwen

Estos subgrupos (al menos de grupos simétricos finitos) se denominan subgrupos de Young. Y no sirven para contar particiones; cada subgrupo de Young corresponde a una partición, pero eso solo equivale a una forma bastante complicada de describir las particiones. Los métodos teóricos de grupo generalmente se adhieren a un solo grupo; dentro del grupo simétrico, el subgrupo Young es solo una pequeña subclase de todos los subgrupos.

Respuestas (1)

¿Existe algún tipo de correspondencia entre grupos y particiones de un conjunto?

Te has topado con el subgrupo. $\Sigma_{\lambda_1} \times \cdots \times \Sigma_{\lambda_k}$ de $\Sigma_n$ , dónde $(\lambda_1, \dots, \lambda_k)$ es la partición de $n$ .
Creo que la palabra que estás buscando es "bloquear". Si todo el grupo simétrico actúa sobre el $n$ -conjunto de elementos $S$ , entonces el subgrupo que mencioné es el estabilizador de los bloques ( es decir, partes de la partición). en.wikipedia.org/wiki/Block_(permutation_group_theory)
Los bloques generalmente se consideran para acciones transitivas y los bloques se pueden asignar entre sí mediante una acción. Pero si, el estabilizador de $P$ como una lista en el grupo simétrico en $S$ es exactamente el producto directo de los grupos simétricos en el $S_i$ .
¿Hay alguna forma de contar las particiones de $S$ ¿usando esto?
Respuestas bienvenidas. Mi motivación fue otro problema que mostraba $p(n)^2 \lt p(n^2 + 2n)$ o algo similar donde $p$ es el número de particiones de un conjunto de tamaño $n$ . Me preguntaba si hay una forma teórica de grupo para mostrar eso. Gracias por el complemento.
No veo una forma de contar particiones usando esta correspondencia que no implique contar particiones. El enfoque obvio sería contar los productos directos $S_{\lambda_1} \times \ldots \times S_{\lambda_k}$ , pero esto es exactamente lo mismo que contar las particiones. Tenga en cuenta también la diferencia algo sutil entre el estabilizador de $P$ y el subgrupo que estabiliza cada $S_i$ (el estabilizador de $P$ todavía puede permutar $S_i, S_j$ como bloques si $|S_i| = |S_j|$ ).
Una cosa más que me viene a la mente es la teoría de la representación del grupo simétrico. El número de particiones de $\{1,\ldots,n\}$ es igual al número de representaciones irreducibles de $S_n$ .
Estos subgrupos (al menos de grupos simétricos finitos) se denominan subgrupos de Young. Y no sirven para contar particiones; cada subgrupo de Young corresponde a una partición, pero eso solo equivale a una forma bastante complicada de describir las particiones. Los métodos teóricos de grupo generalmente se adhieren a un solo grupo; dentro del grupo simétrico, el subgrupo Young es solo una pequeña subclase de todos los subgrupos.

monstruoso · Answer 1

Dejar $S$ ser un conjunto (no necesariamente finito) y $\mathcal{P}=\{P_i\}_{i\in I}$ alguna partición de $S$ . Definir

{GRAMO}_{i} := {F : {PAG}_{i} \to {PAG}_{i} | F es invertible}

$G_i:=\{f:P_i\to P_i\ |\ f\mbox{ is invertible}\}$

Con composición de función estándar $G_i$ es un grupo Si $P_i$ es finito, entonces es el grupo simétrico estándar $S_{|P_i|}$ . actúa sobre $P_i$ a través de $(f, x)\mapsto f(x)$ . Eso lo puedes comprobar facilmente $P_i$ es transitiva (es decir, sólo tiene una órbita) bajo esta acción.

Ahora pon $G:=\prod G_i$ y definir la acción

((F_{i}), X)) \mapsto F_{j} (X) si X \in {PAG}_{j}

$\big((f_i), x)\big)\mapsto f_j(x)\mbox{ if }x\in P_j$

Eso lo puedes comprobar facilmente $S/G=\mathcal{P}$ .

Nota al margen: si asumimos el axioma de elección o asumimos que cada $P_i$ es como mucho contable entonces podemos hacer $G$ menor. solo define $G_i:=P_i$ con cualquier estructura de grupo y poner de nuevo $G:=\prod G_i$ . Tenga en cuenta que la declaración "cualquier conjunto se puede convertir en un grupo" es equivalente al Axioma de Elección. Sin embargo, es cierto como máximo para conjuntos contables independientes del axioma de elección.

Nota al margen 2: El $G$ se puede refinar aún más si cada $P_i$ es finito y $I$ es finito Definir $G:=\mathbb{Z}_n$ dónde $n=lcm(|P_i|)$ (minimo común multiplo). Desde $P_i$ es equinumero con $G/H$ para algunos $H$ entonces puede equiparse fácilmente con acción transitiva. Eso es probablemente el más pequeño $G$ podemos obtener para el caso finito.

Nota al margen 3:

lo bueno de $G=Perm(S)$ es que todo grupo finito es isomorfo a un subgrupo del mismo.

No. Eso no es algo bueno. De hecho, es algo épicamente horrible, porque significa que probar cualquier cosa sobre $G$ es al menos tan difícil como probar cualquier cosa sobre cualquier otro grupo.

"Esa es probablemente la más pequeña $G$ podemos obtener para el caso finito". No de lejos: un grupo cíclico de orden $|P_i|$ Será suficiente.
@HenningMakholm $P_i$ puede diferir en tamaño por lo que $G$ de orden $|P_i|$ ni siquiera tiene sentido. Y como todo conjunto transitivo tiene un tamaño que divide $|G|$ entonces no creo que podamos mejorar entonces lcm over $|P_i|$ .
x @freakish: Tu $G_i$ tiene orden $|P_i|!$ dónde $|P_i|$ seria suficiente. multiplicando esos $G_i$ s juntos después no va a ayudar a eso.
@HenningMakholm ¿qué? Como he escrito claramente $P_i$ puede ser infinito, $|P_i|!$ simplemente no tiene sentido. También he escrito en notas al margen cómo $G_i$ y $G$ se puede reducir en caso finito. no entiendo tus comentarios
x @freakish: Lo que claramente escribiste fue: "Esa es probablemente la G más pequeña que podemos obtener para el caso finito ". Esta es una cita directa: copié y pegué, ni siquiera escribí nada, excepto para resaltar "para el caso finito". Esto, que ha escrito claramente, es falso: la construcción que está describiendo HACE NO dar el grupo más pequeño cuando $P_i$ es finito El hecho de que $P_i$ también podría ser infinito no hace su declaración incorrecta sobre lo que sucede cuando $P_i$ ES finito dejar de estar equivocado. No entiendo tu insistencia en que no escribiste lo que hiciste
@HenningMakholm ya veo. Ese comentario estaba fuera de lugar, se suponía que estaba en el comentario 2. No sé por qué sucedió antes. Por eso me resultó confuso. Obviamente tienes razón, he actualizado la respuesta.

¿Existe algún tipo de correspondencia entre grupos y particiones de un conjunto?

D Izquierda Adyacente a U

sammy negro

D Izquierda Adyacente a U

sammy negro

m_l

D Izquierda Adyacente a U

D Izquierda Adyacente a U

m_l

m_l

Marc van Leeuwen

Respuestas (1)

monstruoso

hmakholm sobra a Monica

monstruoso

hmakholm sobra a Monica

monstruoso

hmakholm sobra a Monica

monstruoso

¿De qué sirve dividir un grupo en clases laterales?

¿Qué quiere decir Aluffi con 'conjunto puntiagudo' en el libro Álgebra: Capítulo 0?

¿Qué sucede cuando dividimos G en clases de equivalencia inducidas por su grupo de automorfismos?

Cualquier conjunto con asociatividad, identidad izquierda, inversa izquierda es un grupo

Un MMM monoide finito es un grupo si y solo si tiene un solo elemento idempotente

¿La acción regular de grupo de GGG sobre sí misma es doblemente transitiva? [cerrado]

Contando centralizadores de una matriz sobre un campo finito con un polinomio mínimo particular

Izquierda acción regular isomorfa a la derecha acción regular

Pregunta sobre grupos abelianos finitamente generados: A/H≅GA/H≅GA/H \cong G

Existencia de elemento neutro