Demostraciones Matematicas problemas ejercicios preguntas consultas dudas ayuda apoyo, tareas. Foros. Tex, Latex Editor. Latexrender. Math help

Como un "Background" del tema es necesario entender, de forma simple, qué es un autómata.

Un autómata $A = (D,Q,\phi,\lambda)$
donde $D = \{0,1,2,\ldots,d-1\}$ con $d \in \mathbb{N}$ es el grupo lenguaje.
Q es el conjunto de estados del autómata
$\phi : QxD \longrightarrow{Q}$ es una función que asocia un estado y un símbolo del lenguaje a un nuevo estado
$\lambda : QxD \longrightarrow{D}$ es una función que calcula el "output" de un estado del autómata.

Def: Se dice que un autómata $A= (D,Q,\phi,\lambda)$ es reversible si $\forall q \in Q$ se tiene que
$\lambda(q,.)$ es una permutación(luego $\lambda(q,\cdot{})$ es una biyección)

de D.

A los autómatas, por claridad, los veremos como un grafo.

Sea $A=(D,Q,\phi,\lambda)$ un automata, denotaremos como $\rho(A)=(Q,C)$ el grafo que describe al autómata siendo Q(conjunto de estados) los nodos del grafo y las conexiones estarán dadas por $C=\{(x,y) \in Q^2 : (\exists p \in D)(\phi(x,p)=y)\}$ , luego es un grafo dirigido que depende de las funciones de transición del autómata.

Como ejemplo: ver imagen (Maquina aditiva)

Def: $A_q=(D,Q,\phi,\lambda,q)$ con $q \in Q$ se dice que es un autómata inicial con estado inicial q.

Def: $D^{\omega}$ es el conjunto de secuencias de símbolos de D.
Tome un automata inicial A con e.i q, entonces se ve como un procedimiento en D a la función
$q:D^{\omega}\longrightarrow{D^{\omega}}$
tal que
$q(\epsilon)=\lambda(q,\epsilon)$ si $\epsilon \in D$
y
$q(\overline{\epsilon W})=\overline{\lambda(q,\epsilon)(\phi(q,\epsilon))(W)}$ con $W \in D^{\omega}$

Ejemplo: Maquina aditiva

está definida por $A = (\{0,1\},\{a,b\},\phi,\lambda)$ con
$\lambda(a,0)=1$ $\phi(a,0)=b$
$\lambda(a,1)=0$ $\phi(a,1)=a$
$\lambda(b,0)=0$ $\phi(b,0)=b$
$\lambda(b,1)=1$ $\phi(b,1)=b$

luego asumiendo a como estado inicial(si asumimos a b como estado inicial dejará intacto el input) con input $\overline{1100}_2=3$ (Siendo el primer bit el menos significativo)
$a(\overline{1100})=\overline{\lambda(a,1)(\phi(a,1))(\overline{100})}=\overline{0a(\overline{100})}=\overline{00a(\overline{00})}=\overline{001b(0)}=\overline{0010}_2=4$

Así que el autómata lo que hace es modelar la suma binaria así que para alguna cadena arbitraria de 0 y 1, le da ese numero más 1.

Bien, viendo ese "background de autómatas" estamos listos para definir lo que es un grupo auto-similar.

Def: Sea G un grupo y X un conjunto no vacío, una acción de G en $X^{\omega}$ se dice autosimilar si
$\forall g \in G$ $\forall x \in X$ $\exists h \in G \wedge \exists y \in X$ tales que

$\forall w \in X^{\omega}$

Def: Un grupo se dice autosimilar si define una relación autosimilar.

Def: El grupo generado por un automata A, llámese G(A) es el grupo de permutaciones de $A^{\omega}$ generados por los estados de A.

Así pues, esos grupos se pueden ver como un autómata ya que la relación que definimos antes en los autómatas es una relación autosimilar y definiriamos el autómata $A(G)=(G',X,\phi,\lambda)$ siendo X el conjunto sobre el cual G tiene una acción autosimilar y G' un generador de G.
Ejemplo:
Retomando la maquina aditiva, podemos ver que $a^n(\overline{\underbrace{00\ldots00}_{\rm \lfloor log_2(n)\rfloor +2 }})$ da como output el número n, en notación binaria. Luego quiere decir que a genera todos los enteros bajo la operación de suma, luego podemos afirmar que $(\mathbb{Z},+,0)\approx{(\{0,1\},\{a,b\},\phi,\lambda)}$ con $\phi$ y $\lambda$ definidas como en la máquina aditiva.

El grupo 4-Klein es AutoSimilar?

Recordando, el grupo 4 de Klein es generado por dos de sus elementos (p,q) y la relación que ellos manejan es

Luego, podemos definir un autómata de dos estados tales que sus funciones procedimiento nos cumplan que

y fuera de eso los estados conmuten?

La respuesta es sí. Es simplemente considerar $A=(\{0,1\},\{p,q\},\phi,\lambda)$ definiendo:
$\phi(q,0)=p$ $\lambda(q,0)=0$
$\phi(q,1)=p$ $\lambda(q,1)=1$
$\phi(p,0)=q$ $\lambda(p,0)=1$
$\phi(p,1)=q$ $\lambda(p,1)=0$

Luego como el estado q, es sólo la identidad disfrazada y siempre le bota el proceso a p, es fácil ver que los procesos conmutan.
Además, como q es la identidad

es la identidad y como

funciona como un or-exclusivo el cuadrado de su proceso volverá a ser el mismo. Luego ese autómata $A(G) \approx{C_2\oplus{C_2}}$ .

Grupo de Baumslag-solitair
El grupo de Baumslag-solitar se define con dos enteros n,m y $B(n,m)=<a,b | b^{-1}a^nb=a^m>$

Los elementos de ese grupo se pueden ver de la forma $a=\begin{bmatrix}{1}&{1}\\{0}&{1}\end{bmatrix}$ y $b=\begin{bmatrix}{\displaystyle\frac{n}{m}}&{0}\\{0}&{1}\end{bmatrix}$
donde es fácil verificar la igualdad
$b^{-1}a^nb=a^m$ osea
$\begin{bmatrix}{\displaystyle\frac{n}{m}}&{0}\\{0}&{1}\end{bmatrix}^{-1}\begin{bmatrix}{1}&{1}\\{0}&{1}\end{bmatrix}^n\begin{bmatrix}{\displaystyle\frac{n}{m}}&{0}\\{0}&{1}\end{bmatrix}=\begin{bmatrix}{\displaystyle\frac{m}{n}}&{0}\\{0}&{1}\end{bmatrix}\begin{bmatrix}{1}&{n}\\{0}&{1}\end{bmatrix}\begin{bmatrix}{\displaystyle\frac{n}{m}}&{0}\\{0}&{1}\end{bmatrix}=\begin{bmatrix}{\displaystyle\frac{m}{n}}&{m}\\{0}&{1}\end{bmatrix}\begin{bmatrix}{\displaystyle\frac{n}{m}}&{0}\\{0}&{1}\end{bmatrix}=\begin{bmatrix}{1}&{m}\\{0}&{1}\end{bmatrix}=\begin{bmatrix}{1}&{1}\\{0}&{1}\end{bmatrix}^m$

Y un caso particular, que es de nuestro interes, es cuando tenemos B(m,1), ya que también podemos ver ese grupo como composiciones de las funciones

Donde también se cumple la relación de la generación
$b^{-1}\circ{a^m}\circ{b}(x)=b^-1(a^m(mx))=b^-1(mx+m)=x+1=a(x)$
luego si tomamos un conjunto $A= \{0,1,\ldots\,n-1\}$ con

tendremos que

es un grupo autosimilar sobre un alfabeto

teniendo

estados distintos representando las distintas composiciones módulo M.
ejemplo:
B(3,1) sobre el lenguaje $A=\{0,1\}$ como

podemos definir los tres estados módulo m
Sea $d \in \{0,1\}^{\omega}$

Grupo de Grigorchuk y solución problema de Burnside

Problema de Burnside:
Será que todo grupo finitamente generado y con un orden finito en cada uno de sus elementos debe ser finito?
....

El grupo de Grigorchuk:
Para definir este grupo, es necesario tener claridad sobre automorfismos sobre un arbol binario T=(V,E) donde $V=\{0,1\}^{\omega}$ y $E=\{(w,v) \in \{0,1\}^{\omega}x\{0,1\}^{\omega} : v=\overline{wa} \mbox{ con } a \in \{0,1\}\}$ .

Ya que éste grupo es generado por cuatro automorfismos de allá. Entonces

def: $Aut(T) = \{\alpha:V \longrightarrow{V} : \alpha(\emptyset)=0 \wedge \alpha$ permuta subarboles en subarboles del mismo nivel $L(k)\}$ definiendo $L(k)=\{w\in \{0,1\}^{\omega}\ : |w|=k\}$

def:

es un subarbol de T con raiz i, osea que $\forall x \in T_i$ $x=\overline{iy}$ con $y \in \{0,1\}^{\omega}$

Ahora definiremos un morfismo $\delta_i : T \longrightarrow{T_i}$ tal que $\delta_i(p)=\overline{ip}$
osea lleva una cadena de $\{0,1\}^{\omega}$ del arbol hacia el subarbol concatenando las secuencias de 0's y 1's
que será el que nos ayudará a poder definir los estados del autómata.

Ahora definamos unos automorfismos:

$a : V \longrightarrow{V}$
definida como $a(w)=\overline{\hat{w_0}w_1\ldots w_n}$ donde $\hat{p}=\begin{Bmatrix} 0 & \mbox{ si }& p=1\\1 & \mbox{si}& p=0\end{matrix}$ y $p \in \{0,1\}$
sea $w \in \{0,1\}^{\omega}$ donde $w=\overline{w_0w_1\ldots w_n}$
$b(w)=\begin{Bmatrix}\delta_{w_0}\circ{a}\circ{\delta_{w_0}^{-1}}& \mbox{ si }& w_0=0\\ \delta_{w_0}\circ{c}\circ{\delta_{w_0}^{-1}} & \mbox{si}& w_0=1\end{matrix}$
$c(w)=\begin{Bmatrix} \delta_{w_0}\circ{a}\circ{\delta_{w_0}^{-1}}& \mbox{ si }& w_0=0\\ \delta_{w_0}\circ{d}\circ{\delta_{w_0}^{-1}} & \mbox{si}& w_0=1\end{matrix}$
$d(w)=\begin{Bmatrix} w & \mbox{ si }& w_0=0\\ \delta_{w_0}\circ{b}\circ{\delta_{w_0}^{-1}} & \mbox{si}& w_0=1\end{matrix}$

Luego en T podemos definir unas relaciones autosimilares, osea que si tomo $A(G)=(\{a,b,c,d\},\{0,1\},\phi,\lambda)$
definiendo las relaciones de la siguiente manera:
$\phi(a,0)=e$ $\lambda(a,0)=1$
$\phi(a,1)=e$ $\lambda(a,1)=0$
$\phi(b,0)=a$ $\lambda(b,0)=0$
$\phi(b,1)=c$ $\lambda(b,1)=1$
$\phi(c,0)=a$ $\lambda(c,0)=0$
$\phi(c,1)=d$ $\lambda(c,1)=1$
$\phi(d,0)=e$ $\lambda(d,0)=0$
$\phi(d,1)=b$ $\lambda(d,1)=1$
donde e se define como

osea es un estado identidad.
tendremos que esos elementos forman un grupo autosimilar, llamado el grupo de Grigorchuk.

Proposición: El grupo de Grigorchuk es infinito.
Para ver ésto se usa el estabilizador sobre un subarbol de T.
$St(k)=\{\alpha \in Aut(T) : (\forall x \in T(k)) \alpha(x)=x\}$
y se ve que es subgrupo normal de Aut(T), usando $f:Aut(T)\longrightarrow{Aut(T(k))}$ que basicamente lo que hace es restringir a los automorfismos de T a su funcionalidad en el subarbol T(k).
de Ahí, St(k) es el núcleo de ese homomorfismo, luego se tiene el ser subgrupo normal de Aut(T).
Después, lo que se hace, es definir un homomorfismo que lleva a $St_{A(G)}(1)\longrightarrow{A(G)}$ de forma sobre. Luego uno termina concluyendo que $|A(G)|\geq{\aleph_0}$
Proposición2: Todo elemento del grupo de Grigorchuk tiene orden

con $n \in \mathbb{N}$

De esas dos proposiciones y de la construcción del grupo tenemos que es un grupo finitamente generado, cuyos elementos tienen orden finito, pero que es infinito. Luego da solución, como contra ejemplo, al problema de Burnside.

	Autor	Tema: Exposición Grupos Auto Similares (Leído 806 veces)
0 Usuarios y 1 Visitante están viendo este tema.