Álgebra e Topologia

Vista previa del material en texto

Índice general
1. Álgebra, Topoloǵıa y Autómatas Celulares 3
1.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Acciones de grupos . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1. Acciones de grupos y ejemplos . . . . . . . . . . . . . . 4
1.2.2. Órbitas y estabilizadores . . . . . . . . . . . . . . . . . 6
1.3. Topoloǵıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1. Espacios topológicos . . . . . . . . . . . . . . . . . . . 8
1.3.2. Funciones continuas . . . . . . . . . . . . . . . . . . . . 11
1.3.3. Topoloǵıa producto . . . . . . . . . . . . . . . . . . . . 13
1.4. Autómatas celulares . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.1. Espacio de configuraciones . . . . . . . . . . . . . . . . 16
1.4.2. Definición de autómatas celulares y ejemplos . . . . . . 19
1.4.3. Propiedades básicas . . . . . . . . . . . . . . . . . . . . 23
1.4.4. Teorema de Curtis-Hedlund . . . . . . . . . . . . . . . 24
1
2 ÍNDICE GENERAL
Caṕıtulo 1
Álgebra, Topoloǵıa y
Autómatas Celulares
Alonso Castillo Ramı́rez
Alfonso Manuel Hernández Magdaleno
Juan Manuel Márquez Bobadilla
1.1. Introducción
Los autómatas celulares, inventados por John von Neumann en la década
de 1940, son importantes modelos computacionales discretos que se han con-
vertido en una herramienta fundamental en diversas áreas de la ciencia. Por
mucho, el ejemplo más famoso es el Juego de la Vida inventado por John H.
Conway. En este caṕıtulo presentamos los fundamentos modernos de la teoŕıa
de autómatas celulares, los cuales provienen principalmente de la teoŕıa de
grupos y la topoloǵıa.
Nuestro objetivo principal es demostrar el famoso Teorema de Curtis-
Hedlund1, el cual caracteriza a los autómatas celulares sobre alfabetos fini-
tos como funciones G-equivariantes y continuas en la topoloǵıa prodiscreta
del espacio de configuraciones. Para llegar a esto, primero revisamos temas de
acciones de grupos y topoloǵıa, y luego presentamos la definición de autóma-
tas celulares sobre grupos junto con algunos ejemplos importantes.
1También llamado Teorema de Curtis-Hedlund-Lyndon.
3
4CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
1.2. Acciones de grupos
1.2.1. Acciones de grupos y ejemplos
Suponemos que el lector ya ha llevado un curso de álgebra que incluye los
rudimentos básicos de la teoŕıa de grupos, a saber: definición y propiedades
de los grupos, el concepto de subgrupo y subgrupo normal, el concepto de
clase lateral (en inglés, coset) y homomorfismos de grupos.
Definición 1.1 (acción de grupo) Una acción de un grupo G sobre un
conjunto X es una función
G×X → X
(g, x) 7→ g · x
que satisface:
a) e · x = x para todo x ∈ X, donde e es la identidad del grupo G.
b) g · (k · x) = gk · x, para todo x ∈ X y para todos g, k ∈ X.
Una acción de un grupo también se puede considerar como un homomor-
fismo de grupos G → Sym(X).
Ejemplo 1.2 (conjugación) Si X = G, tenemos una acción
G×G → G dada por g · x := gxg−1.
Verifiquemos que se cumplen las dos propiedades de la definición:
a) e · x = exe−1 = x, para todo x ∈ G.
b) g · (k · x) = g(kxk−1)g−1 = (gk)x(gk)−1 = gk · x, para todo x ∈ X y
para todos g, k ∈ X.
Ejemplo 1.3 (multiplicación derecha) También, cuando X = G, tene-
mos una acción
G×G → G dada por g · x := gx.
Es rutinario verificar que se cumplen las propiedades a) y b).
1.2. ACCIONES DE GRUPOS 5
Ejemplo 1.4 (clases laterales izquierdas) Para cualquier subgrupo H de
G, sea G/H = {gH : g ∈ G} el conjunto de clases laterales izquierdas de H
en G. Entonces, tenemos una acción
G×G/H → G/H dada por k · gH := kgH.
Nuevamente, es rutinario verificar que se cumplen las propiedades a) y b).
Ejemplo 1.5 (clases laterales derechas) Para cualquier subgrupo H de
G, sea H\G = {Hg : g ∈ G} el conjunto de clases laterales derechas de H
en G. Entonces, tenemos una acción
G×H\G → H\G dada por k ·Hg := Hgk−1.
Verifiquemos que se cumplen las dos propiedades de la definición:
a) e ·Hg = Hge−1 = Hg, para todo Hg ∈ H\G.
b) s · (k ·Hg) = Hgk−1s−1 = Hg(sk)−1 = sk ·Hg, para todo Hg ∈ H\G
y s, k ∈ G.
Ejemplo 1.6 (acción derecha) Teniendo una acción izquierda G ×X →
X dada por (g, x) 7→ g · x, podemos definir una acción derecha X ×G → X
v́ıa x•g := g−1 ·x. Verifiquemos que se cumplen las dos propiedades análogas
en la definición de acción derecha:
a) x • e = e−1 · x = x, para todo x ∈ X.
b) (x • g) • k) = k−1 · (g−1 ·x) = k−1g−1 ·x = (gk)−1 ·x = x • gk, para todo
x ∈ X y g, k ∈ G.
Ejemplo 1.7 (sobre conjunto de funciones) Sean X y Y conjuntos. El
conjunto de todas las funciones con dominio X y codominio Y se denota por:
Y X := {φ : X → Y }.
Supongamos que tenemos una acción G × X → X dada por (g, x) 7→ g · x.
Ahora, podemos definir una acción de G× Y X → Y X de la siguiente forma:
para cualquier φ ∈ Y X y g ∈ G, tenemos que g • φ ∈ Y X es la función dada
por
g • φ(x) = φ(g−1 · x), ∀x ∈ X.
Verifiquemos que se cumplen las dos propiedades de la definición:
6CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
a) e • φ(x) = φ(e−1 · x) = φ(x), para todo x ∈ X, y entonces e • φ = φ,
para toda φ ∈ Y X , g, k ∈ G.
b) k • (g • φ)(x) = (g • φ)(k−1 · x) = φ(g−1 · (k−1 · x)) = φ((kg)−1 · x) =
kg • φ(x), para todo x ∈ X, y entonces k • (g • φ) = kg • φ para toda
φ ∈ Y X , g, k ∈ G.
1.2.2. Órbitas y estabilizadores
Una acción G × X → X permite definir una relación ∼ sobre X de la
siguiente forma:
∀x, y ∈ X, x ∼ y ⇐⇒ ∃g ∈ G : y = g · x.
Es rutinario verificar que ∼ es una relación de equivalencia.
Definición 1.8 (órbita) La órbita de x ∈ X es la clase de equivalencia
[x] = {y ∈ X : x ∼ y} bajo la relación de equivalencia ∼ de arriba, y se
simboliza como Orb(x), es decir
Orb(x) := {g · x : g ∈ G}.
Como las diferentes clases de equivalencia forman una partición de X
entonces tenemos que
X =
⊔
a∈X
Orb(a),
la cual es conocida como la partición orbital de X.
Definición 1.9 (estabilizador) El estabilizador de x ∈ X es el conjunto
St(x) = {g ∈ G : g · x = x}.
Lema 1.10 El estabilizador St(x) es un subgrupo de G.
Demostración: Sean g, h ∈ St(x) entonces g · x = x tanto como h · x = x.
Observemos que
h−1 · x = h−1 · (h · x) = h−1h · x = e · x = x
y además
h−1g · x = h−1 · (g · x) = h−1 · x = x.
1.3. TOPOLOGÍA 7
Por lo tanto, h−1g ∈ St(x), lo que demuestra el lema.
El siguiente teorema usa fuertemente el siguiente criterio para la igualdad
de clases laterales: para H ≤ G y a, b ∈ G, tenemos que
Ha = Hb si y solo si ab−1 ∈ H y
aH = bH si y solo si a−1b ∈ H.
Teorema 1.11 Para cualquier x ∈ X, existe una biyección
φ : Orb(x) −→ G/St(x).
Demostración: Cualquier elemento de Orb(x) puede verse como g · x, para
algún g ∈ G. La asignación g · x 7−→ gSt(x) o bien, φ(g · x) := gSt(x) está
bien definida y es una biyección:
1. φ está bien definida:
Sean g · x, h · x ∈ Orb(x) tales que g · x = h · x. Entonces h−1g · x = x
y h−1g ∈ St(x). Esto implica que gSt(x) = hSt(x) y φ(g · x) = φ(h · x).
2. φ es inyectiva:
Spongamos que φ(g · x) = φ(h · x). Entonces, gSt(x) = hSt(x), lo que
implica que h−1g ∈ St(x). Luego, h−1g · x = x y aśı g · x = h · x.
3. φ es sobreyectiva:
Si gSt(x) es una clase lateral genérica en G/St(x), es claro que su
preimagen bajo φ es g · x.
Como consecuencia podemos obtener el siguiente corolario.
Corolario 1.12 Para cualquier x ∈ X,
|Orb(x)| = [G : St(x)].
donde [G : St(x)] es el ı́ndice de St(x) en G, es decir, el número de clases
laterales de St(x) en G.
1.3. Topoloǵıa
Esta sección incluye solo aquellos resultados relevantes de topoloǵıa que
usaremos más adelante, y omite muchas demostraciones. Para una introduc-
ción más amigable a la topoloǵıa, recomendamos al lector consultar [8] o
[9].
8CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
1.3.1. Espacios topológicos
Definición 1.13 (espacio topológico) Sea X un conjunto. Una topoloǵıa
para X es una colección T de subconjuntos de X que cumplen las siguientes
propiedades:(T1) ∅ ∈ T y X ∈ T .
(T2) La unión de cualquier colección arbitraria de conjuntos en T también
está en T .
(T3) La intersección de cualquier colección finita de conjuntos en T también
está en T .
En tal caso, el par (X, T ) se llama un espacio topológico.
Cuando la topoloǵıa está clara en el contexto, denotamos a un espacio
topológico (X, T ) simplemente por X y nos referimos a los elementos de T
como conjuntos abiertos. Decimos que un subconjunto C ⊆ X es cerrado
si X − C es abierto.
Ejemplo 1.14 (topoloǵıa discreta) Sea X cualquier conjunto y sea T =
P(X) el conjunto potencia de X (es decir, la colección de todos los subconjun-
tos de X). Entonces, a T es una topoloǵıa para X que se llama la topoloǵıa
discreta de X.
Ejemplo 1.15 (topoloǵıa indiscreta) Sea X cualquier conjunto y T =
{X, ∅}. Entonces T es una topoloǵıa para X que se llama la topoloǵıa indis-
creta de X.
Ejemplo 1.16 Consideremos el conjunto X = {a, b, c} y
T = {X, ∅, {a, b}, {b}, {b, c}}.
Es rutinario verificar que T es una topoloǵıa para X (porque cumple los
axiomas T1-T3 de la definición).
Ejemplo 1.17 (topoloǵıa subespacio) Sea (X, T ) un espacio topológico
y sea A un subconjunto de X. Entonces la colección
TA := {A ∩ U : U ∈ T }
es una topoloǵıa para A, conocida como la topoloǵıa subespacio. Verifiquemos
que se cumplen los axiomas de la definición:
1.3. TOPOLOGÍA 9
(T1) ∅ = A ∩ ∅ ∈ TA y A = A ∩X ∈ TA.
(T2) Si {Wi : i ∈ I} es cualquier colección abiertos en TA, entonces Wi =
A ∩ Ui donde Ui ∈ T , y por lo tanto
⋃
i∈I
Wi =
⋃
i∈I
A ∩ Ui = A ∩
(
⋃
i∈I
Ui
)
∈ TA.
(T3) Si W1, . . . ,Ws es una colección finita de abiertos en TA, entonces Wi =
A ∩ Ui donde Ui ∈ T , y por lo tanto
s
⋂
i=1
Wi =
s
⋂
i=1
A ∩ Ui = A ∩
(
s
⋂
i=1
Ui
)
∈ TA.
Definición 1.18 (base) Sea (X, T ) un espacio topológico. Una base para
(X, T ) es una colección B de conjuntos abiertos tal que cualquier conjunto
abierto A ∈ T puede escribirse como una unión arbitraria de elementos de
B.
Ejemplo 1.19 Si X es un espacio topológico discreto, entonces la colección
de conjuntos unipuntuales {{x} : x ∈ X} es una base.
Teorema 1.20 (base) Sea X un conjunto. Una colección B de subconjun-
tos de X es la base de alguna topoloǵıa si y sólo si satisface las siguientes
propiedades:
(B1) Para toda x ∈ X existe B ∈ B tal que x ∈ B.
(B2) Para toda B1, B2 ∈ B y toda x ∈ B1 ∩ B2 existe B3 ∈ B tal que
x ∈ B3 ⊆ B1 ∩ B2.
Demostración: Supongamos que B es la base de una topoloǵıa T . Demos-
traremos que se cumplen (B1)-(B2):
(B1) Como X ∈ T , por definición de base tenemos que existe BX ⊆ B tal
que X =
⋃
B∈BX
B. Esto demuestra (B1).
(B2) Sean ahora B1, B2 ∈ B. Como B1 y B2 son abiertos, entonces B1 ∩ B2
también es abierto y se puede escribir como una unión de elementos de
la base. Esto demuestra (B2).
10CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
Supongamos ahora que B satisface (B1)-(B2) y definamos la siguiente
colección de subconjuntos de X:
T := {A ⊆ X : ∀a ∈ A, ∃B ∈ B tal que a ∈ B ⊆ A}.
Demostraremos que (X, T ) es un espacio topológico (llamado el espacio to-
pológico generado por B).
(T1) Claramente ∅ ∈ T y X ∈ T , por (B1).
(T2) Sea A ⊆ T y consideremos U :=
⋃
A∈A
A. Para todo u ∈ U , existe A ∈ A
tal que u ∈ A. Por definición de T , existeB ∈ B talque u ∈ B ⊆ A ⊆ U .
Luego, U ∈ T .
(T3) Sean A1, A2, . . . An ∈ T . Por definición, para todo x ∈
n
⋂
i=1
Ai existen
B1, . . . , Bn tales que x ∈ Bi ⊆ Ai. Luego x ∈
n
⋂
i=1
Bi, y la propiedad
(B2) implica que existe B ∈ B tal que x ∈ B ⊆
n
⋂
i=1
Bi ⊆
n
⋂
i=1
Ai. Por lo
tanto,
n
⋂
i=1
Ai ∈ T .
Definición 1.21 (subbase) Sea (X, T ) un espacio topológico. Decimos que
una colección de abiertos S es una subbase para T si todo conjunto abierto
puede escribirse como la unión arbitraria de intersecciones finitas de conjun-
tos en S.
En otras palabras, la definición anterior establece que S es una subbase
para T si y solo si para cualquier U ∈ T existe una colección {Bi : i ∈} tales
que U =
⋃
i∈I Bi, donde Bi = S1
i ∪ ... ∪ Sr
i para algunos Sk
i ∈ S. Entonces
U =
⋃
i∈I
(
r
⋂
k=1
Sk
i
)
.
Definición 1.22 (vecindad) Sea (X, T ) un espacio topológico y x ∈ X.
Una vecindad de x es simplemente un conjunto abierto U tal que x ∈ U .
1.3. TOPOLOGÍA 11
Definición 1.23 (Hausdorff) Un espacio topológico X se dice que es de
Hausdorff si para todo x1, x2 ∈ X, x1 6= x2, existen vecindades U1 y U2 de x1
y x2, respectivamente, que son disjuntas.
Una de las caracteŕısticas importantes de los espacios de Hausdorff es que
es posible demostrar que el ĺımite de cualquier sucesión convergente en único.
Definición 1.24 (Espacio Compacto) Un espacio topológico (X, T ) es com-
pacto si para toda colección A ⊆ T tal que X =
⋃
A∈A
A, existe una subcolec-
ción finita A′ ⊆ A tal que X =
⋃
A∈A′
A.
Dos resultados importantes son que los conjuntos cerrados de un espa-
cio compacto son espacios compactos en śı mismos, y que los subespacios
compactos de uno de Hausdorff son cerrados.
1.3.2. Funciones continuas
Definición 1.25 (función continua) Una función f : X → Y entre espa-
cios topológicos es continua si para todo abierto V en Y , el conjunto
f−1(V ) := {x ∈ X : f(x) ∈ V }
es abierto en X.
En términos de conjuntos cerrados: f : X → Y es continua si y sólo si
para cada cerrado E en Y se tiene que f−1(E) es cerrado en X.
Lema 1.26 Sea f : X → Y una función entre espacios topológicos y sea S
una subbase de Y . La función f : X → Y es continua si y sólo si, para todo
S ∈ S, el conjunto f−1(S) es abierto en X.
Demostración: Esto es un resultado directo de las siguientes identidades
que se cumplen para cualquier función:
f−1
(
⋃
i∈I
Bi
)
=
⋃
i∈I
f−1(Bi),
f−1
(
⋂
i∈I
Bi
)
=
⋂
i∈I
f−1(Bi).
12CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
Teorema 1.27 Sean f : X → Y y g : Y → Z funciones continuas entre
espacios topológicos. Entonces, la composición g ◦ f : X → Z también es
continua.
Demostración: Sea U abierto en Z, entonces g−1(U) es abierto en Y y a su
vez f−1(g−1(U)) es abierto en X. Pero f−1 ◦ g−1 = (g ◦ f)−1. Por lo tanto,
(g◦f)−1(U) que es abierto enX para cualquier abierto U en Z, lo que permite
establecer la continuidad de g ◦ f .
Lema 1.28 Una función entre espacios topológicos f : X → Y es continua
si y sólo si para todo x ∈ X y toda vecindad W de f(x) en Y existe una
vecindad U de x tal que f(U) ⊆ W .
Demostración: Supongamos que f : X → Y es continua. Sean x ∈ X y
W una vecindad de f(x). Por definición de función continua, U := f−1(W )
es abierto en X. Claramente x ∈ U (por lo que U es una vecindad de x) y
f(U) = W .
Ahora demostraremos el converso. Sea W un conjunto abierto en Y . Para
cualquier x ∈ f−1(W ), W es una vecindad de f(x) y, por hipótesis, existe
una vecindad Ux de x tal que f(Ux) ⊆ W . Luego Ux ⊆ f−1(W ) y
f−1(W ) =
⋃
x∈f−1(W )
Ux.
Como la unión de abiertos es abierto, f−1(W ) es abierto en Y , y f es una
función continua.
Lema 1.29 Si f : X → Y es una función continua entre espacios topológi-
cos, donde X es compacto, entonces f(X) es un subespacio compacto de Y .
Teorema 1.30 Si f : X → Y es una biyección continua, donde X es com-
pacto y Y es Hausdorff, entonces f−1 : Y → X es continua.
Demostración: Debemos demostrar que la función g := f−1 : Y → X es
continua. Sea W abierto en X. Entonces, E = X − W es cerrado en X.
Como X es compacto y E es un subconjunto cerrado, entonces E también es
compacto. Aśı f(E) es compacto en Y , pero, siendo Y de Hausdorff, entonces
f(E) también es cerrado. Luego, Y − f(E) es abierto en Y . Observemos que
Y − f(E) = g−1(X − E) = g−1(W ),
porque g−1 = f y W = X−E. Con esto demostramos que g−1(W ) es abierto
siempre que W es abierto en X, lo que implica que g = f−1 es continua.
1.3. TOPOLOGÍA 13
1.3.3. Topoloǵıa producto
Definición 1.31 (topoloǵıa producto) Sean (X, T1) y (Y, T2) espacios to-
pológicos. La topoloǵıa producto en X × Y es la topoloǵıagenerada por la
base
B := {A1 × A2 : A1 ∈ T1, A2 ∈ T2}.
Por lo tanto, los conjuntos abiertos en el espaico topológico X × Y son
uniones arbitrarias de los básicos en B.
Podemos describir más floklóricamente la topoloǵıa de X × Y usando las
dos proyecciones
πX : X × Y → X, πY : X × Y → Y,
definidas por πX(x, y) = x y πY (x, y) = y. Observemos que para cualesquiera
abiertos A1 en X y A2 en Y ,
π−1
X (A1) = {(x, y) : x ∈ A1} y π−1
Y (A2) = {(x, y) : y ∈ A2}.
Esto muestra que las proyecciones son funciones continuas porque
π−1
X (A1) = A1 × Y ∈ B
π−1
Y (A2) = X × A2 ∈ B,
los cuales son conjuntos abiertos en X × Y . Además, cualquier básico puede
verse como la intersección de preimágenes de proyecciones
A1 × A2 = π−1
X (A1) ∩ π−1
Y (A2),
lo que implica que la siguiente colección es una subbase para X × Y :
S :=
{
π−1
X (A1), π
−1
Y (A2) : A1 ∈ T1, A2 ∈ T2
}
.
La definición de arriba puede entonces, generalizarse a un producto car-
tesiano arbitrario. Sea I un conjunto de ı́ndices, y supongamos que tenemos
una familia espacios topológicos {(Xi, Ti) : i ∈ I}. El producto cartesiano de
la familia de conjuntos {Xi : i ∈ I} se define como sigue:
∏
i∈I
Xi :=
{
f : I →
⋃
i∈I
Xi | f(i) ∈ Xi
}
.
14CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
Figura 1.1: Subbásicos y básicos en la topoloǵıa producto.
Definición 1.32 (topoloǵıa producto arbitraria) Sea I un conjunto de
ı́ndices y sea {(Xi, Ti) : i ∈ I} una colección de espacios topológicos. La
topoloǵıa producto para
∏
i∈I Xi es la topoloǵıa generada por la base
B :=
{
∏
i∈I
Ai : Ai ∈ Ti y Ai 6= Xi sólo para un número finito de i’s
}
.
Similarmente al caso finito, podemos considerar las proyecciones πk :
∏
i∈I Xi → Xk y obtener una subbase para
∏
i∈I Xi dada por
S :=
{
π−1
k (Ak) : Ak ∈ Tk, k ∈ I
}
.
El siguiente teorema es muy importante y tiene una demostración com-
plicada que usa el Lema de Zorn.
Teorema 1.33 (Tychonoff) El producto de espacios topológicos compactos
es compacto.
El teorema anterior puede deducirse como consecuencia del Lema de la
Subbase de Alexander.
Lema 1.34 (Alexander) Sea X un espacio topológico y S una subbase para
la topoloǵıa de X. Supongamos que para cada colección de subbásicos que
cubren a X existe una subcolección finita que cubre a X. Entonces X es
compacto.
1.3. TOPOLOGÍA 15
Demostración: Supongamos que X no es compacto. Entonces existe una
cubierta abierta C (de conjuntos básicos) que no tiene una subcubierta finita.
Construyamos la familia:
F = {las cubiertas abiertas de X que no tienen subcubiertas finitas}
Este conjunto está parcialmente ordenado y cada subcolección de ésta que
esté totalmente ordenada tiene una cota superior. Entonces, por el Lema de
Zorn, ∃C0 ∈ F una cubierta maximal, y esto implica que C0 es una cubierta
abierta de básicos que no tiene subcubierta finita.
Sea Uα ∈ C0 básico, entonces existen finitos subbásicos Sα1
, ..., Sαr
tales
que
Uα = Sα1
∩ · · · ∩ Sαr
.
Afirmamos que al menos uno de los Sαi
∈ C0. Para probar esto supongamos
que todos los Sα1
, ..., Sαr
6∈ C0.
Si cada Sαi
/∈ C0, ∀αr, entonces: C0∪{Sαi
} /∈ F , y aśı se tiene que hay una
subcubierta finita de C0∪{Sαi
} que cubre a X y lo anterior implica que cubre
a X − Sαi
con finitos elementos de C0 ∪ {Sαi
}, en otras palabras, X − Sαi
se
cubre con finitos elementos de C0.
Pero
X − Uα = (X − Sα1
) ∪ · · · ∪ (X − Sαr
).
Si cada X−Sαi
se cubre con finitos elementos de C0 entonces X−Uα también
y como X = (X − Uα) ∪ Uα entonces X seŕıa cubierto con finitos elementos
de C0, lo cual es una contradicción.
Ahora, si para cada Uβ ∈ C0 existe un subbásico Sβ con Uβ ⊆ Sβ, luego
X también tiene una cubierta de subbásicos para X. Por hipótesis tenemos
finitos subbásicos para cubrir a X, lo que implica que hay finitos básicos Uα
para cubrir a X, lo cual contradice la elección de C0. Entonces la familia F
es vaćıa y la suposición de que X no es compacta es falsa,por lo tanto X es
compacto
Queda como ejercicio para el lector demostrar el Teorema de Tychonoff
usando el Lema de la Subbase de Alexander.
16CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
1.4. Autómatas celulares
1.4.1. Espacio de configuraciones
Definición 1.35 (configuración) Sea G un grupo y A un conjunto. Una
configuración x : G → A es simplemente una función con dominio G y
codominio A. El espacio de configuraciones se denota por AG, es decir
AG := {x : G → A | x es una función}.
El espacio de configuraciones AG puede identificarse con el producto car-
tesiano
∏
g∈G
A, ya que cada función x : G → A puede identificarse intuitiva-
mente con una tupla (x(g))g∈G. De hecho, como vimos en la sección anterior,
un producto cartesiano arbitrario está definido mediante funciones.
Definición 1.36 (acción de traslación) Definimos la acción de traslación
de G en AG como sigue: para cada g ∈ G y x ∈ AG, la función g · x ∈ AG
está dada por
(g · x)(h) := x(g−1h), ∀h ∈ G.
Lema 1.37 Efectivamente, la acción de traslación de G en AG es una acción
de grupos.
Demostración: Verificamos que se cumplen las dos propiedades de acciones
de grupos:
1. (e · x)(h) = x(h), ∀h ∈ G, aśı que e · x = x, ∀x ∈ AG.
2. g2 · (g1 · x)(h) = x(g−1
1 g−1
2 h) = x((g2g1)
−1h) = (g2g1 · x)(h), ∀h ∈ G,
aśı que
g2 · (g1 · x) = g2g1 · x, ∀x ∈ AG.
Ejemplo 1.38 Sea G = Z y A = {0, 1}. Una configuración x ∈ AZ es
formalmente una función x : Z → A, pero puede verse como una sucesión
bi-infinita como sigue
x = . . . , x−2, x−1, x0, x1, x2, . . .
1.4. AUTÓMATAS CELULARES 17
donde xi := x(i), ∀i ∈ Z. La acción de traslación de n ∈ Z en AZ es
n · x = . . . , x−2−n, x−1−n, x−n, x1−n, x2−n, . . .
Por ejemplo, si x = . . . , 0, 0, 1, 0, 0, . . . , entonces
0 · x = . . . , 0, 0, 1, 0, 0, . . .
1 · x = . . . , 0, 0, 0, 1, 0, . . .
(−1) · x = . . . , 0, 1, 0, 0, 0, . . .
Definición 1.39 (tipos de configuraciones) Sea x ∈ AG.
1. Decimos que x es invariante si St(x) = G.
2. Decimos que x es aperiódica si St(x) = {e}.
3. Decimos que x es periódica si St(x) 6= {e}.
Observación 1.40 Una configuración x ∈ AG es invariante si y sólo si es
una función constante. Para probar esto, veamos que
St(x) = G ⇐⇒ g · x = x, ∀g ∈ G
⇐⇒ g · x(e) = x(e), ∀g ∈ G
⇐⇒ x(g−1) = x(e), ∀g ∈ G.
Como g ∈ G es arbitraria, la última afirmación significa que x evaluada
en cualquier elemento del grupo es igual a x(e) ∈ A. En otras palabras, x es
una función constante.
Ejemplo 1.41 Sea G = Z y A = {0, 1}. Las configuraciones invarian-
tes son k0 = . . . , 0, 0, 0, 0, 0, . . . y k1 = . . . , 1, 1, 1, 1, 1, . . . , mientras que
y = . . . , 0, 0, 1, 0, 0, . . . es un ejemplo de una configuración aperiódica y
z = . . . , 1, 0, 0, 1, 0, 0, . . . (donde el patrón 1, 0, 0 se repite infinitamente en z)
de una configuración periódica con St(z) = 3Z. En este caso, las G-órbitas
de y y z son infinita y finita, respectivamente. Expĺıcitamente:
Orb(y) = {x ∈ AZ : xi = 1 para un, y sólo un, i ∈ Z},
Orb(z) = {. . . , 1, 0, 0, 1, 0, 0, . . . ; . . . , 0, 1, 0, 0, 1, 0, . . . ; . . . , 0, 0, 1, 0, 0, 1, . . . }.
En particular la órbita Orb(z) tiene sólo 3 elementos, lo cual coincide con el
hecho que [Z : 3Z] = 3.
18CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
Definición 1.42 (topoloǵıa prodiscreta) La topoloǵıa prodiscreta de AG ∼=
∏
g∈G
A es la topoloǵıa producto de la topoloǵıa discreta en cada componente A.
Lema 1.43 Las siguientes afirmaciones se cumplen en la topoloǵıa prodis-
creta de AG:
1. La colección
B :=
{
∏
g∈G
Ug : Ug ⊆ A y Ug 6= A sólo para un número finito de g ∈ G
}
.
es una base para la topoloǵıa prodiscreta de AG.
2. Las proyecciones πg : A
G → A, definidas como πg(x) = x(g) son conti-
nuas.
3. La colección
{
π−1
g ({a}) : g ∈ G, a ∈ A
}
,
donde π−1
g ({a}) = {x ∈ AG : x(g) = a} es una subbase de la topoloǵıa.
4. AG es un espaico de Hausdorff.
5. AG tiene la topoloǵıa discreta si y sólo si G es finito.6. AG es compacto si y sólo si A es finito.
7. Una función τ : AG → AG es continua si y sólo si πg ◦ τ : AG → A es
continua ∀g ∈ G.
Demostración: Este lema resume muchas propiedades abordadas en la sec-
ción previa sobre topoloǵıa. Algunos puntos, como (5.) y (6.) son ejercicios
sencillos, mientras que otros, como (4.) y (7.), pueden consultarse en [8] o
[9].
Observación 1.44 Los conjuntos π−1
g ({a}) son escencialmente el conjunto
de todas las configuraciones de AG que tienen a a ∈ A en su “coordenada”
g.
1.4. AUTÓMATAS CELULARES 19
Observación 1.45 Sea x ∈ AG. Para cualquier subconjunto finito K ⊆ G
podemos construir una vecindad de x como sigue:
V (x,K) := {z ∈ AG : z|K = x|K} =
⋂
k∈K
π−1
k ({x(k)}).
En otras palabras, V (x,K) contiene a todas las configuraciones de AG que
coinciden con x en K.
Lema 1.46 La acción de traslación de G en AG es continua.
Demostración: Hay que demostrar que ϕg : A
G → AG, definida por ϕg(x) =
g ·x, es continua, para toda g ∈ G. Para toda h ∈ G, πh ◦ϕg(x) = (g ·x)(h) =
x(g−1h) = πg−1h(x), aśı que las funciones πh ◦ ϕg = πg−1h son continuas.
Si x ∈ AG, entonces x|S denota la restricción de la función x a S. El
siguiente lema será de utilidad posteriormente.
Lema 1.47 Sea K ⊆ G un subconjunto finito. La función ResK : AG → AK
definida por ResK(x) = x|K es continua.
Demostración: Por el Lema 1.43, AK tiene la topoloǵıa discreta, porque K
es finito. Luego, la colección de conjuntos unipuntuales {{x} : x ∈ AK} es
una subbase. Por el Lema 1.26, la función ResK es continua si y sólo si, para
toda x ∈ AK , los conjuntos Res−1
K (x) son abiertos en AG. Observemos que
Res−1
K (x) = {z ∈ AG : z|K = x} = V (x′, K),
donde x′ ∈ AG es cualquier extensión de x a AG. Por lo tanto, Res−1
K (x) es
abierto para toda x ∈ AK .
1.4.2. Definición de autómatas celulares y ejemplos
La siguiente definición de autómata celular es una generalización de la
definición original de Von Neumann y se debe a Ceccherini-Silberstein y
Coornaert [4].
Definición 1.48 (autómata celular sobre un grupo) Sea G un grupo y
A un conjunto. Un autómata celular sobre AG es una función
τ : AG → AG
20CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
tal que existe un subconjunto finito S ⊆ G (llamado el conjunto memoria de
τ) y una función local µ : AS → A que satisfacen
τ(x)(g) = µ((g−1 · x)|S),
para toda x ∈ AG, g ∈ G.
El escenario clásico, y más estudiado, es cuando G = Z
d, d ∈ N, y A es un
conjunto finito. Una excelente revisión de este escenario puede encontrarse
en [5].
Ejemplo 1.49 (Regla 110) Sea G = Z y A = {0, 1}.
Sea S = {−1, 0, 1} ⊆ G y definamos µ : AS → A por medio de la siguiente
tabla
x ∈ AS 111 110 101 100 011 010 001 000
µ(x) 0 1 1 0 1 1 1 0
El autómata celular τ : AZ → AZ definido por S y µ es el autómata
celular elemental conocido como Regla 110.
Por ejemplo,
τ : . . . 0001000 . . . 7→ . . . 0011000 . . .
La Regla 110 es un ejemplo particular de un autómata celular elemental.
Definición 1.50 (autómata celular elemental) Un autómata celular ele-
mental es un autómata celular τ : {0, 1}Z → {0, 1}Z cuyo conjunto memoria
es S = {−1, 0, 1}.
Los autómatas celulares elementales se etiquetan como ‘Regla M ’, donde
M es un número entre 0 y 255. En cada caso, la regla local µM : AS → A
está determinada como sigue: sea M1 . . .M8 la representación binaria de M
y escribamos los elementos de AS en orden lexicográfico decreciente, es decir,
111, 110, . . . , 000; entonces, la imagen del i-ésimo elemento de AS bajo µM
es Mi.
Observación 1.51 Dado un autómata celular τ : AG → AG es posible en-
contrar su función local µ simplemente evalúandolo en la identidad del grupo,
ya que
τ(x)(e) = µ((e−1 · x)|S) = µ(x|S), ∀x ∈ AG.
1.4. AUTÓMATAS CELULARES 21
Observación 1.52 En general, el conjunto memoria de un autómata celular
τ : AG → AG no es único. Sin embargo, el conjunto memoria mı́nimo S de τ
puede obtenerse analizado todas las coordenadas x(h) que afectan la imagen
de la función local τ(x)(e); es decir, h ∈ S si y sólo si τ(x)(e) 6= τ(y)(e),
para algunos x, y ∈ AG tales que x(h) 6= y(h). Cualquier subconjunto finito
S ′ ⊆ G tal que S ⊆ S ′ también es un conjunto memoria para τ ya que las
coordenadas x(k) donde k ∈ S ′ − S no afectan las imágenes de la función
local.
Ejemplo 1.53 (Laplaciano discreto) Sean G = Z y A = R. El Lapla-
ciano discreto es el autómata celular ∆ : RZ → R
Z definido por
∆(x)(n) := 2x(n)− x(n− 1)− x(n+ 1), ∀x ∈ R
Z, n ∈ Z.
De esta definición se deduce que la función local para ∆ está dada por
µ(x) = τ(x)(0) = 2x(0)− x(−1)− 2(1).
De aqúı, observamos que el conjunto memoria mı́nimo para ∆ es S = {−1, 0, 1}.
Ejemplo 1.54 (Juego de la Vida) Sea G = Z
2 y A = {0, 1}. El Juego de
la Vida es el autómata celular τ : AG → AG definido por el conjunto memoria
S = {(0, 0), (1, 0), (0, 1), (1, 1), (−1, 0), (0,−1), (−1,−1), (−1, 1), (1,−1)},
y la función local µ : AS → A dada por
µ(x) =
{
1 si
(
∑
s∈S x(s) = 3
)
∨
(
(
∑
s∈S x(s) = 4) ∧ (x(0, 0) = 1)
)
0 en otro caso.
Las siguientes imágenes muestran algunos ejemplos de cómo se aplica el
Juego de la Vida. Cada configuración x ∈ AZ
2
está representada por una
cuadŕıcula infinita donde cada celda puede tener uno de dos colores: blanco
que corresponde a 0 ∈ A, o verde que cooresponde a 1 ∈ A.
22CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
Figura 1.2: Conjunto memoria del Juego de la Vida.
Figura 1.3: Sobrevivencia.
Figura 1.4: Nacimiento.
Figura 1.5: Muerte por soledad.
1.4. AUTÓMATAS CELULARES 23
Figura 1.6: Muerte por sobrepoblación.
1.4.3. Propiedades básicas
Ahora demostraremos algunas propiedades algebraicas y topológicas de
los autómatas celulares sobre grupos.
Lema 1.55 Todo autómata celular τ : AG → AG es una función continua
en la topoloǵıa prodiscreta.
Demostración: Usaremos el Lema 1.43 (7). Sea S el conjunto memoria de
τ y µ : AS → A su función local. Para cualquier g ∈ G, tenemos que
πg ◦ τ(x) = τ(x)(g) = µ((g−1 · x)|S) = µ ◦ ResS ◦ ϕg−1(x), ∀x ∈ AG,
donde ϕg−1 : AG → AG y ResS : AG → AS están definidas en la Sección 1.4.1.
La función ϕg−1 es continua por el Lema 1.46, mientras que la función ResS
es continua por el Lema 1.47. Además, µ : AS → A es continua al ser una
función entre espacios topológicos discretos. Por lo tanto, para toda g ∈ G,
πg ◦ τ es igual a la composición de funciones continuas µ ◦ResS ◦ϕg−1 , lo que
implica que es continua.
La demostración presentada aqúı del resultado anterior de debe a Miriam
Bocardo Gaspar (en comunicación privada).
Definición 1.56 (G-equivariante) Una función τ : AG → AG es G-equivariante
si conmuta con la acción de tralsación de G, es decir
τ(g · x) = g · τ(x), ∀x ∈ AG, g ∈ G.
Lema 1.57 Todo autómata celular τ : AG → AG es G-equivariante.
24CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
Demostración: Sean S y µ : AS → A un conjunto memoria y función local
de τ , respectivamente. Para todo g, h ∈ G y x ∈ AG tenemos lo siguiente
τ(g · x)(h) = µ((h−1 · (g · x))|S)
= µ(((h−1g) · x))|S)
= µ((g−1h)−1 · x)|S)
= τ(x)(g−1h)
= g · τ(x)(h).
Por lo tanto, τ(g · x) = g · τ(x).
Teorema 1.58 Sean τ : AG → AG y σ : AG → AG autómatas celulares.
Entonces τ ◦ σ : AG → AG también es un autómata celular.
Demostración: Ver [4].
Por el resultado anterior, el conjunto
CA(G;A) := {τ : AG → AG | τ es un autómata celular },
equipado con la composición de funciones, es un monoide (es decir, un conjun-
to equipado con una operación binaria asociativa y con elemento identidad).
Este monoide ha sido estudiado en detalle en [1, 2, 3].
1.4.4. Teorema de Curtis-Hedlund
Cuando el conjunto A es finito, el Teorema de Curtis-Hedlund caracteriza
los autómatas celulares.
Teorema 1.59 (Curtis-Hedlund) Sea G un grupo y A un conjunto fini-
to. Una función τ : AG → AG es un autómata celular si y sólo si es G-
equivariante y continua en la topoloǵıa prodiscreta.
Demostración: El converso queda demostradopor los Lemas 1.55 y 1.57, y
no requiere la finitud de A.
Supongamos que τ : AG → AG es una función G-equivariante y continua.
Consideremos la función µ̂ : AG → A dada por
µ̂(x) := τ(x)(e), ∀x ∈ AG,
1.4. AUTÓMATAS CELULARES 25
donde e ∈ G es la identidad del grupo. Debido a que µ̂ = πe ◦ τ , el Lema 1.43
(7.) implica que µ̂ es una función continua. Por lo tanto, para toda x ∈ AG y
toda vecindad V de µ̂(x) existe una vecindad V (x,Kx) de x (donde Kx ⊆ G
es finito) tal que µ̂(V (x,Kx)) ⊆ V (Lema 1.28). Si tomamos V = {µ̂(x)},
tenemos que
µ̂(x) = µ̂(z), ∀z ∈ V (x,Kx). (1.1)
La colección {V (x,Kx) : x ∈ AG} es una cubierta abierta de AG. Debido
a que A es finito, AG es compacto por el Lema 1.43 (6.), aśı que existe un
subconjunto finito F ⊆ AG tal que {V (x,Kx) : x ∈ F} es una cubierta
abierta de AG. Definamos el siguiente subconjunto finito de G:
S :=
⋃
x∈F
Kx.
Sean y, z ∈ AG tales que y|S = z|S, y sea x0 ∈ F tal que y ∈ V (x0, Kx0
).
Como Kx0
⊆ S, tenemos que y|Kx0
= z|Kx0
, y por lo tanto z ∈ V (x0, Kx0
).
Luego, por la propiedad (1.1) de arriba,
µ̂(y) = µ̂(x0) = µ̂(z).
Esto demuestra que la imagen de cualquier z ∈ AG bajo µ̂ sólo depende de
z|S, y podemos definir la función µ : AS → A como µ(z′) := µ̂(z), para toda
z′ ∈ AS, donde z es culaquier configuración en AG tal que z′ = z|S. Por
G-equivarianza, tenemos que para cualquier x ∈ AG, g ∈ G,
τ(x)(g) = g−1 · τ(x)(e) = τ(g−1 · x)(e) = µ̂(g−1 · x) = µ((g−1 · x)|S).
Aśı, τ es un autómata celular con conjunto memoria S y función local µ :
AS → A.
Corolario 1.60 Sea G un grupo y A un conjunto finito. Si τ ∈ CA(G;A)
es biyectivo, entonces τ−1 ∈ CA(G;A).
Demostración: Debido a que τ : AG → AG es biyectiva existe su función in-
versa τ−1 : AG → AG. Demostraremos que τ−1 es G-equivariante y continua,
lo que implicaŕıa, por el Teorema de Curtis-Hedlund, que τ−1 ∈ CA(G;A).
1. τ−1 es G-equivariante.
26CAPÍTULO 1. ÁLGEBRA, TOPOLOGÍA Y AUTÓMATAS CELULARES
Sean g ∈ G y y ∈ AG arbitrarios. Como τ es biyectivo, existe un único
x ∈ AG tal que y = τ(x). Debido a que τ ∈ CA(G;A) tenemos que
τ(g · x) = g · τ(x).
Aplicando τ−1 en la identidad anterior, y usando el hecho que x = τ−1(y),
obtenemos que
τ−1τ(g · x) = τ−1(g · τ(x))
g · τ−1(y) = τ−1(g · y).
Esto demuestra que τ−1 es G-equivariante.
2. τ−1 es continua.
Para demostrar esto usaremos el Teorema 1.30, el cual establece que τ−1 es
continua si el dominio de τ (i.e. AG) es compacto y el codominio de τ (i.e.
AG) es Hausdorff. Como A es finito por hipótesis, entonces es compacto. Por
el Teorema de Tychonoff, AG también es compacto. Además AG es Hausdorff
por el Lema 1.43. Por lo tanto, τ−1 es continua.
Usando el Teorema de Curtis-Hedlund, es sencillo demostrar el Teorema
1.58 cuando A es finito.
Corolario 1.61 Sea A un conjunto finito y sean τ : AG → AG y σ : AG →
AG autómatas celulares. Entonces τ ◦ σ : AG → AG también es un autómata
celular.
Demostración: Primero observemos que τ ◦ σ es continua porque la com-
posición de funciones continuas es continua. Además, τ ◦σ es G-equivariante
porque
τ(σ(g · x)) = τ(g · σ(x)) = g · τ(σ(x)).
Por el Teorema de Curtis-Hedlund, τ ◦ σ es un autómata celular.
Bibliograf́ıa
[1] Castillo-Ramirez, A., Gadouleau, M.: Ranks of finite semigroups of one-
dimensional cellular automata. Semigroup Forum 93, 347–362 (2016).
[2] Castillo-Ramirez, A., Gadouleau, M.: On Finite Monoids of Cellular Au-
tomata. In: Cook, M., Neary, T. (eds.) Cellular Automata and Discrete
Complex Systems. AUTOMATA 2016. LNCS 9664, pp. 90–104, Springer
International Publishing Switzerland (2016).
[3] Castillo-Ramirez, A., Gadouleau, M.: Cellular Automata and Finite
Groups. Nat. Comput. (Online First, 2017) 1–14.
[4] Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and
Groups. Springer Monographs in Mathematics, Springer-Verlag Berlin
Heidelberg (2010).
[5] Kari, J.: Theory of cellular automata: A Survey. Theoret. Comput. Sci.
334, 3–33 (2005).
[6] Márquez Bobadilla J.M. Notas de Teoŕıa de Grupos 2007-2014. Álgebra
Moderna III. Departamento de Matemáticas del CUCEI.
[7] Milne J.. Group Theory 2013. Free Online.
[8] Morris, S. A.: Topology without tears, 2017. Disponible en
http://www.topologywithouttears.net/.
[9] Munkres, J. R.: Topoloǵıa. Segunda Edición. Pearson Educación, 2002.
27
	Álgebra, Topología y Autómatas Celulares
	Introducción
	Acciones de grupos
	Acciones de grupos y ejemplos
	Órbitas y estabilizadores
	Topología
	Espacios topológicos
	Funciones continuas
	Topología producto
	Autómatas celulares
	Espacio de configuraciones
	Definición de autómatas celulares y ejemplos
	Propiedades básicas
	Teorema de Curtis-Hedlund