Apuntes del curso

El lema del diamante
Mariano Suárez-Álvarez
20 de mayo, 2015
Índice
1
2
3
4
5
6
7
Monoides libres
Álgebras libres
Órdenes monomiales
Sistemas de reescritura
El lema del diamante
Ejemplos
Ejercicios
1
4
8
13
17
18
18
§1. Monoides libres
1.1. Sea X un conjunto, cuyos elementos llamamos letras o variables. Si n ∈ N0 , una palabra
de longitud n en las letras de X es una función w : JnK → X, y en ese caso escribimos |w| = n.
Cuando n es positivo, denotaremos siempre a w por la secuencia finita w(1)w(2) · · · w(n) de
sus valores escritos en el orden natural. Así, x, yyyy y xyxxyxxy son palabras en las letras
del conjunto {x, y} de longitud 1, 4 y 8, respectivamente. Como J0K = ∅, hay exactamente una
palabra de longitud 0, a la que llamamos la palabra vacía y escribimos 1.
1.2. Si n ∈ N0 , escribimos X n al conjunto de todas las palabras de longitud n en las letras de X
S
y hXi = i≥0 X n al conjunto de todas las palabras; notemos que esta unión es disjunta.
La función w ∈ X 1 7→ w(1) ∈ X es evidentemente una biyección, a la que consideraremos
siempre como una identificación. En vista de esto, consideramos a los elementos de X como
palabras de longitud 1 y tenemos una función ι : X → hXi, la inclusión de X 1 en hXi, que es
claramente inyectiva.
1.3. Si u, v ∈ hXi son dos palabras de longitudes n y m, respectivamente, entonces la concatenación de u y v es la palabra u · v ∈ X n+m de longitud n + m tal que

u(i),
si 1 ≤ i ≤ n;
(u · v)(i) =
v(i − n), si n < i ≤ n + m.
1
De la definición misma de esta operación se sigue que
|u · v| = |u| + |v|.
(1)
{eq:monoide:abs}
{prop:monoide}
Proposición. El conjunto hXi dotado de la operación · de concatenación es un monoide. El
elemento neutro de hXi es la palabra vacía 1 y el conjunto X genera a hXi como monoide.
Demostración. Tenemos que mostrar que la operación de concatenación es asociativa y que tiene
a la palabra vacía como elemento neutro, y esto último es inmediato. Si n, m, k ∈ N0 y u ∈ X n ,
v ∈ X m y w ∈ X K , entonces se sigue de la definición que

(u · v)(i),
si 1 ≤ i ≤ n + m;
((u · v) · w)(i) =
w(i − n − m), si n + m < i ≤ n + m + k;
=



u(i),
si 1 ≤ i ≤ n;
v(i − n),



si n < i ≤ n + m;
w(i − n − m), si n + m < i ≤ n + m + k.
Es fácil ver que u · (v · w) es exactamente la misma función.
Nos queda ver que hXi está generado por X como monoide. Para ello, mostremos, haciendo
0
inducción sobre n, que X n está contenido en el submonoide hXi generado por X. Esto es evidente
si n = 0. Sea entonces n ≥ 0 y sea w ∈ X n+1 . Si ponemos w0 = w|JnK , que es un elemento de X n ,
y x = w(n + 1) ∈ X, entonces w = w0 · x y la hipótesis inductiva implica que
0
0
w = w0 · x ∈ X n · X ⊆ hXi · X ⊆ hXi ,
0
de manera que X n+1 ⊆ hXi .
1.4. Una consecuencia inmediata de esta Proposición 1.3 y de la igualdad (1) es que la función {p:abs}
longitud | | : hXi → N0 es un morfismo de monoides.
1.5. A la siguiente observación evidente la vamos a usar frecuentemente —de hecho, la usamos
ya en el final de la prueba de la Proposición 1.3.
Lema. Sea w ∈ hXi una palabra de longitud l ≥ 0. Si k ∈ N0 es tal que 0 ≤ k ≤ l, entonces
existe un único par de palabras u, v ∈ hXi tales que |u| = k, |v| = l − k y w = u · v.
Demostración. Las palabras u = w|JkK y v : i ∈ Jl − kK 7→ w(i − k) ∈ X satifacen la condición. Si
u0 ∈ X k y v 0 ∈ X l−k es otro par de palabras tal que w = u0 ·v 0 , tenemos que u0 (i) = (u0 ·v 0 )(i) = w(i)
si i ∈ JkK, de manera que u0 = w|JkK = u, y
v 0 (i) = (u0 · v 0 )(k + i) = w(k + i) = (u · v)(k + i) = v(i)
para cada i ∈ Jl − kK, de manera que v 0 = v.
1.6. La propiedad fundamental del monoide hXi es que es libre, es decir, la siguiente:
2
{prop:monoide:libre}
Proposición. Sea M un monoide. Si φ : X → M es una función, entonces existe exactamente
un morfismo φ¯ : hXi → M tal que conmuta el diagrama
X
ι
φ
M
¯
φ
hXi
Demostración. Definimos una sucesión de funciones (φn : X n → M )n≥0 de manera inductiva,
empezando con φ0 : X 0 → M la función tal que φ0 (1) = 1M . Si n ≥ 0 y ya tenemos a la
función φn , entonces definimos φn+1 : X n+1 → M de la siguiente manera: si w ∈ X n+1 , existen
w0 ∈ X n y x ∈ X tales que w = w0 · x y ponemos
φn+1 (w) = φn (w0 ) · φ(x).
S
El producto · que aparece a la dereche en esta igualdad es el de M . Como hXi = n≥0 X n y
¯ X n = φn para todo
la unión es disjunta, hay exactamente una función φ¯ : hXi → M tal que φ|
n ≥ 0. Mostremos que φ es un morfismo de monoides.
¯
Se sigue de la construcción misma que φ(1)
= 1M . Sean u, v ∈ hXi dos palabras: tenemos
¯ · v) = φ(u)
¯
¯
que probar que φ(u
· φ(v)
y lo hacemos por inducción en la longitud de v.
¯
Si v tiene longitud 0, entonces v es la palabra vacía, u · v = u y φ(v)
= 1M por construcción,
¯
¯
¯
¯
¯
así que φ(u · v) = φ(u) = φ(u) · 1M = φ(u) · φ(v). Supongamos ahora que la longitud de v es l ≥ 1.
En ese caso existen una palabra v 0 de longitud l − 1 y una letra x tales que v = v 0 · x, y entonces
¯ · v) = φ(u
¯ · (v 0 · x)) = φ((u
¯
φ(u
· v 0 ) · x).
¯ · v 0 ) · φ(x). Por otro lado, como v 0 tiene
De la definición de φ¯ se sigue que esto es igual a φ(u
¯ · v 0 ) = φ(u)
¯
¯ 0 ) y poniendo todo junto
longitud l − 1, la hipótesis inductiva nos dice que φ(u
· φ(v
vemos que
¯ · v) = φ(u
¯ · v 0 ) · φ(x) = (φ(u)
¯
¯ 0 )) · φ(x) = φ(u)
¯
¯ 0 ) · φ(x)).
φ(u
· φ(v
· (φ(v
¯ 0 ) · φ(x) = φ(v
¯ 0 · x) = φ(v),
¯
¯ esto es igual a φ(u)
¯
¯
Como φ(v
otra vez por la definición de φ,
· φ(v).
La existencia del morfismo φ¯ queda así establecida. Para ver la unicidad, supongamos que
ψ : hXi → M es otro morfismo de monoides tal que φ = ψ ◦ ι y consideremos el conjunto
¯
E = {w ∈ hXi : φ(w)
= ψ(x)}. Es inmediato verificar que es un submonoide de hXi, y es claro
de las hipótesis que X ⊆ E. La Proposición 1.3 nos dice que X genera a hXi como monoide y
esto implica que E = hXi.
1.7. Un ejemplo representativo de aplicación de esta proposición es el siguiente. Consideremos
la función φ : X → N0 tal que φ(x) = 1 para todo x ∈ X. Si vemos a N0 con su estructura
usual de monoide aditivo, la proposición nos dice que existe un único morfismo de monoides
¯
φ¯ : hXi → N0 tal que φ(x)
= 1 para todo x ∈ X. Por otro lado, observamos en 1.4 que la función
longitud | | : hXi → N0 es un morfsmo de monoides tal que |x| = 1 para todo x ∈ X. Se sigue,
¯
entonces, que φ(w)
= |w| para cualquier w ∈ hXi.
3
{prop:monoide:reg}
1.8. Proposición. Si u, v, v 0 ∈ hXi son tales que u · v = u · v 0 o v · u = v 0 · u, entonces v = v 0 .
Demostración. Supongamos, por ejemplo, que uv = uv 0 . Como |u| + |v| = |uv| = |uv 0 | = |u| + |v 0 |,
es |v| = |v 0 |; sean m este número y n = |u|. Para cada i ∈ JmK es
v(i) = (u · v)(n + i) = (u · v 0 )(n + i) = v 0 (i)
y esto significa qu v = v 0 .
§2. Álgebras libres
2.1. Sea k un anillo conmutativo, sea X un conjunto y sea khXi el k-módulo libre con base hXi. Precisamente porque hXi es una base de khXi, existe exactamente una función k-bilineal
? : khXi × khXi → khXi tal que u ? v = u · v para cada par de palabras u, v ∈ hXi. Esta operación ? es asociativa: para verlo alcanza con mostrar que (u ? v) ? w = u ? (v ? w) si u, v, w ∈ hXi,
y esto es consecuencia inmediata de que la operación de concatenación en hXi es asociativa. De
manera similar, la palabra vacía 1 de hXi es el elemento identidad de khXi. Así, el espacio
vectorial khXi dotado de la multiplicación ? es una k-álgebra.
2.2. Que el monoide hXi sea libre en el sentido de la Proposición 1.6 tiene la siguiente consecuencia:
{prop:algebra:libre}
Proposición. Sea ι : X → khXi la función inclusión y sea A una k-álgebra. Si φ : X → A
es una función, entonces existe exactamente un morfismo φ¯ : khXi → A de k-álgebras tal que
conmuta el diagrama
X
ι
φ
A
¯
φ
khXi
Demostración. De acuerdo a la Proposición 1.6, y viendo a A como un monoide para la multiplicación, existe un morfismo de monoides φ0 : hXi → A tal que φ0 (x) = φ(x) para todo x ∈ X.
Como hXi es una k-base de khXi, existe entonces un morfismo de k-módulos φ¯ : khXi → A
¯
¯
tal que φ(u)
= φ0 (u) para todo u ∈ hXi; en particular, tenemos que φ(x)
= φ0 (x) = φ(x) para
todo x ∈ X, de manera que conmuta el diagrama del enunciado. Esta función φ¯ es un morfismo
de álgebras. En efecto, como hXi genera a su dominio como k-módulo, para verlo alcanza con
¯ ? v) = φ(u)
¯
¯
mostrar que φ(u
· φ(v)
cuando u, v ∈ hXi, y esto sigue de que
¯ ? v) = φ(u
¯ · v) = φ0 (u · v) = φ0 (u)φ˙ 0 (v) = φ(u)
¯
¯
φ(u
· φ(v).
Finalmente, si ψ : khXi → A es otro morfismo de k-álgebras tal que ψ ◦ ι = φ, entonces el
¯
conjunto E = {a ∈ A : ψ(a)
= ψ(a)} es una k-subalgebra de khXi que contiene a X, así que,
¯
como X genera a khXi, es E = khXi y esto significa que ψ = φ.
4
{prop:algebra:reg}
2.3. Proposición.(i) Un elemento de hXi no es un divisor de cero en khXi.
(ii) Si en k no hay divisores de cero, entonces en khXi tampoco.
Demostración. (i) Sean u ∈ hXi y a ∈ khXi tales que ua = 0. Hay un conjunto finito V ⊆ hXi
P
y una función λ : V → k tal que a = v∈V λ(v)v, así que
ua =
X
λ(v)uv = 0.
(2)
{eq:algebra:reg}
v∈V
De acuerdo a la Proposición 1.8 la función v ∈ V 7→ uv ∈ hXi es inyectiva y entonces, como hXi
es un subconjunto linealmente independiente de khXi, se sigue de la igualdad (2) que λ(v) = 0
para todo v ∈ V , esto es, que a = 0.
(ii) Supongamos que existen dos elementos no nulos a, b ∈ khXi tales que ab = 0. Existen
P
conjuntos finitos U , V ⊆ hXi y funciones λ : U → k y µ : V → k tales que a = u∈U λ(u)u y
P
b = v∈V µ(v)v. Sin perdida de generalidad podemos suponer que λ(u) 6= 0 para todo u ∈ U y
que µ(v) 6= 0 para todo v ∈ V . Por otro lado, como a 6= 0 y b 6= 0, es necesariamente U 6= ∅ y
V 6= ∅. Como
X
X X
ab =
λ(u)µ(v)uv =
λ(u)µ(v) w,
u∈U,v∈V
w∈hXi u∈U,v∈V
uv=w
para todo w ∈ hXi vale que
X
λ(u)µ(v) = 0.
(3)
{eq:algebra:reg:2}
u∈U,v∈V
uv=w
Sean u0 ∈ U y v0 ∈ V tales que |u0 | = max{|u| : u ∈ U } y |v0 | = max{|v| : v ∈ V }. Si u ∈ U
y v ∈ V son tales que uv = u0 v0 , entonces |u| + |v| = |u0 | + |v0 | y, como |u| ≤ |u0 | y |v| ≤ |v0 |,
vemos que |u| = |u0 | y |v| = |v0 | y, en consecuencia, que u = u0 y v = v0 . La igualdad (3) con
w = u0 v0 , entonces, nos dice que λ(u0 )µ(v0 ) = 0. Esto es imposible porque en k no hay divisores
de cero.
2.4. Proposición. Sean X e Y dos conjuntos. Entonces khXi y khY i son álgebras isomorfas si
y solamente si X e Y tienen el mismo cardinal.
Demostración. Supongamos que vale la condición y sea f : X → Y es una biyección. De la
Proposición 2.2 sabemos que existen morfismos de álgebras φ : khXi → khY i y ψ : khY i → khXi
tales que φ(x) = f (x) para cada x ∈ X y ψ(y) = f −1 (y) para cada y ∈ Y . La composición
ψ ◦ φ : khXi → khXi es entonces un morfismo de álgebras tal que (ψ ◦ φ)(x) = x para todo x ∈ X,
así que la afirmación relativa a la unicidad de la Proposición 2.2 implica que ψ ◦ φ = idkhXi . De
la misma forma podemos ver que φ ◦ ψ = idkhY i y, en consecuencia, que φ es un isomorfismo.
Nos resta mostrar la necesidad de la condición de la proposición. Sea primero X un conjunto.
De acuerdo a la Proposición 2.2 existe un único morfismo de álgebras : khXi → k tal que
(x) = 0 para todo x ∈ X, y es claro que se trata de una sobreyección. Si I0 = ker es su núcleo,
entonces el morfismo induce un isomorfismo de álgebras khXi/I0 ∼
= k.
5
{prop:algebra:rango}
Es claro que I0 tiene como base, en tanto k-submódulo de khXi, al conjunto X ≥1 . Se sigue de
esto que el cuadrado I02 está generado en tanto submódulo por el conjunto de todo los productos
de dos elementos de X ≥1 , y este conjunto es evidentemente X ≥2 . Como X ≥2 es linealmente
independiente sobre k, vemos así que, de hecho, I02 tiene a X ≥2 como base.
Consideremos la función π : x ∈ X 7→ x + I02 ∈ I0 /I02 . Esta función es inyectiva: en efecto, si
x e y son elementos de X tales que π(x) = π(y), entonces x − y ∈ I02 , y esto es absurdo ya que
todo elemento de I02 es una combinación lineal de palabras de longitud al menos dos y x − y no
lo es. Más aún, el conjunto B = {π(x) : x ∈ X} es una k-base de I0 /I02 .
• Si u ∈ I0 , entonces u es una combinación lineal de palabras de longitud al menos 1, así
que existe una familia de escalares (λx )x∈X y un elemento u0 que es combinación lineal de
P
palabras de longitud al menos 2 tales que λx = 0 para casi todo x ∈ X y u = x∈X λx x + u0 .
P
P
Se tiene entonces que u + I02 = x∈X λx x + I02 = x∈X λx π(x). Esto nos dice que el
conjunto B genera a I0 /I02 como espacio vectorial.
• Supongamos ahora que (λx )x∈X es una familia de elementos de k con λx = 0 para casi
P
P
2
todo x ∈ X tal que
x∈X λx π(x) = 0 en I0 /I0 . Esto significa que
x∈X λx x es un
elemento de I02 , lo que es absurdo, ya que no es una combinación lineal de palabras de
logitud al menos 2.
Vemos así que I0 /I02 es un k-módulo libre de rango igual al cardinal de X. Hemos probado que
∼ k en tanto álgebras y tal
existe en khXi un ideal bilátero I0 con khXi/I0 =
2
que I0 /I0 es un k-módulo libre de rango igual al cardinal de X.
(4)
{eq:free:i0}
(5)
{eq:free:jj}
Mostremos ahora que, de hecho, vale que
si J es un ideal bilátero de khXi tal que khXi/J ∼
= k en tanto álgebras,
2
entonces el cociente J/J es un k-módulo libre de rango igual al cardinal de X.
Sea J un ideal tal que hay un isomofismo φ : khXi/J ∼
= k de k-álgebras. Sea p : khXi → khXi/J
es la proyección canónica y para cada x ∈ X pongamos αx = φ(p(x)) ∈ k. De la Proposición 2.2
sabemos que existen morfismos de álgebras α, β : khXi → khXi tal que α(x) = x+αx y β(x) = xαx
para todo x ∈ X. Como la composición α ◦ β : khXi → khXi es tal que (α ◦ β)(x) = x para todo
x ∈ X, esa misma proposición nos dice que α ◦ β = idkhXi . Razonando de manera simétrica,
vemos que también β ◦ α = idkhXi y, entonces, que α es un isomorfismo de álgebras.
Sea J 0 el ideal de khXi generado por el conjunto {x − αx : x ∈ X}. Como φ(p(x − αx )) = 0
para todo x ∈ X, tenemos que J 0 ⊆ K. Por otro lado, es α(x − αx ) = x cualquiera sea x ∈ X:
como X genera a I0 y α es un automorfismo, esto nos dice que α(J 0 ) = I0 y, en particular, que
α induce un isomofismo α
¯ : khXi/J 0 → khXi/I0 . Vemos así que khXi/J 0 ∼
= k.
Si u ∈ J, entonces este último isomorfismo implica que existe λ ∈ k tal que u − λ1 ∈ J 0 y,
khXi/J
como J 0 ⊆ J, que λ1 ∈ J. En consencuencia, la función lλ
: ξ ∈ khXi/J 7→ λξ ∈ khXi/J es
nula. Como khXi/J es isomorfa en tanto k-álgebra con k, la función η : a ∈ k 7→ a1 + J ∈ kX/J
6
es un isomorfismo y conmuta el diagrama
k
lλ
k
η
k
η
khXi/J
khXi/J
lλ
khXi/J
en el que lλk : k → k y lλk (a) = λa para todo a ∈ k. Esto implica, por supuesto, que λ = 0 y,
entonces, que u ∈ J 0 . Concluimos de esta forma quee J = J 0 y que α(J) = I0 .
Finalmente, como α : khXi → khXi es un isomorfismo de álgebras y α(J) = I0 , es claro que
α induce un isomofismo de k-módulos J/J 2 → I0 /I02 , así que la última afirmación de (5) sigue de
la última afirmación de (4). Esto completa, por lo tanto, la prueba de (5).
Combinando (4) y (5), vemos que
el conjunto J (X) de los ideales J de khXi tales que khXi/J ∼
= k es no vacío,
y que cualquiera sea J ∈ J (X) el k-módulo J/J 2 es libre de rango igual al
cardinal de X.
(6)
Si ahora Y es otro conjunto y φ : khXi → khY i es un isorfismo de álgebras, entonces es
inmediato verificar que para cada J ∈ (X) se tiene que φ(J) ∈ J (Y ) y que el isomofismo φ
induce un isomorfismo de k-módulos J/J 2 → φ(J)/φ(J)2 . En particular, en vista de (6), X e Y
tienen el mismo cardinal.
2.5. En vista de la Proposición 2.2, llamamos a khXi la k-álgebra libre generada por X. Por
otro lado, decimos que un álgebra A es libre si existe un conjunto X tal que A ∼
= khXi y, en ese
caso, que su rango es el cardinal del conjunto X; que esto último tiene sentido es consecuencia
directa de la Proposición 2.4.
2.6. Proposición. Sea A un álgebra. Si X es un subconjunto de A que la genera como álgebra,
entonces hay un morfismso sobreyectivo de álgebras φ : khXi → A tal que φ(x) = x para todo
x ∈ X. En particular, si I = ker φ, entonces hay un isomorfimo de álgebras A ∼
= khXi/I.
Demostración. Sea X ⊆ A como en el enunciado. La existencia de un morfismo de álgebras
φ : khXi → A tal que φ(x) = x para todo x ∈ X es consencuencia de la Proposición 2.2. Es
claro que la imagen de φ es una subálgebra de A que contiene a X. La elección de X, entonces,
implica que φ es sobreyectivo.
2.7. Si A es un álgebra, una presentación de A es una terna ordenada (X, S, φ) en la que X es
un conjunto, S un subconjunto de khXi y φ : khXi → A es un morfismo sobreyectivo de álgebras
cuyo núcleo esta generado por S en tanto ideal bilátero de khXi.
Toda álgebra A posee presentaciones. En efecto, si φ : khXi → A es el morfismo de álgebras
tal que φ(a) = a para todo a ∈ A, entonces (A, ker φ, φ) es una presentación de A. En general,
sin embargo, estamos interesados en presentaciones (X, S, φ) más eficientes, en el sentido de que
el conjunto X y/o el conjunto S sea lo más chico posible.
2.8. Decimos que un álgebra A es afín si posee una presentación (X, S, φ) en la que el conjunto X
es finito; claramente, un álgebra es afín si y solamente sí es finitamente generada en tanto álgebra.
7
{eq:free:q}
Por otro lado, decimos que A es finitamente presentada si posee una presentación (X, S, φ)
en la que tanto X como S sean conjuntos finitos.
§3. Órdenes monomiales
3.1. Sea X un conjunto y X ∗ el monoide libre generado por X. Un orden monomial sobre X ∗
es un orden parcial ĺ sobre X ∗ si
{sect:orden}
• 1 ĺ v para todo v ∈ X ∗ y
• para todo u, v, v 0 , w ∈ X ∗ vale que
v ĺ v 0 =⇒ uvw ĺ uv 0 w.
3.2. La siguiente observación es útil y es la razón por que imponemos la primera condición en la
definición de los órdenes monomiales:
Lema. Si ĺ es un orden monomial, entonces si u, v ∈ X ∗ y u es un factor de v, entonces u ĺ v.
Demostración. Si u es un factor de v, entonces existen w1 , w2 ∈ X ∗ tales que v = w1 uw2 . Como
1 ĺ w1 y 1 ĺ w2 , tenemos entonces que u = 1u1 ĺ w1 uw2 = v.
Ejemplos
3.3. Sea n ≥ 1 y sea X = {x1 , . . . , xn } un conjunto con n elementos distintos. Fijemos un orden {p:deglex}
total E sobre X. El orden graduado-lexicográfico u orden deglex asociado a E es el orden ĺ
sobre el monoide X ∗ tal que si u y v son dos elementos de X ∗ se tiene que u ĺ v si y sólo si
• o bien |u| < |v|
• o bien |u| = |v| y existen w, u0 , v 0 ∈ X ∗ y a, b ∈ X tales que u = wau0 , v = wbv 0 y a E b.
En otras palabras, es u ĺ v si o bien u es estríctamente más corto que v en tiene la misma
longitud que v y la primera letra en la que u difiere de v es menor o igual que la correspondiente
letra de v con respecto al orden de X.
Por ejemplo, si X = {x, y, z} y x E y E z, entonces los monomios de longitud 3 se ordenan
con respecto al orden deglex de la siguiente manera:
xxx,
xxy,
xxz,
xyx,
xyy,
xyz,
xzx,
xzy,
xzz,
yxx,
yxy,
yxz,
yyx,
yyy,
yyz,
yzx,
yzy,
yzz,
zxx,
zxy,
zxz,
zyx,
zyy,
zyz,
zzx,
zzy,
zzz.
3.4. Podemos generalizar la construcción hecha en 3.3 para el orden deglex. Sean n ≥ 1,
X = {x1 , . . . , xn } un conjunto con n elementos distintos, E un orden total en X y ω : X → R≥0
una función con valores reales estrictamente positivos. Vemos a R≥0 como un monoide con
respecto a la suma usual. De la Proposición 1.6 sabemos que existe una único morfismo de
monoides ω
¯ : hXi → R≥0 . El orden ω-graduado-lexicográfico u orden ω-deglex asociado
8
a E y a ω es el orden ĺ sobre hXi tal que si u y v son elementos de hXi se tiene que u ĺ v si y
solo sí
• o bien ω
¯ (u) < ω
¯ (v)
¯ (u) = ω
¯ (v) y existen w, u0 , v 0 ∈ X ∗ y a, b ∈ X tales que u = wau0 , v = wbv 0 y
• o bien ω
a E b.
Por ejemplo, si X = {x, y, z}, x E y E z, y ω(x) = 3, ω(y) = 2 y ω(z) = 1, entonces los
monomios de longitud 3 se ordenan con respecto al orden ω-deglex de la siguiente manera:
zzz,
yzz,
zyz,
zzy,
xzz,
yyz,
yzy,
zxz,
zyy,
zzx,
xyz,
xzy,
yxz,
yyy,
yzx,
zxy,
zyx,
xxz,
xyy,
xzx,
yxy,
yyx,
zxx,
xxy,
xyx,
yxx,
xxx.
3.5. De manera similar, si n ≥ 1, X = {x1 , . . . , xn } es un conjunto con n elementos distintos y
E es un orden total sobre X, el orden graduado-lexicográfico inverso u orden degrevlex
asociado a E es el orden ĺ sobre X ∗ tal que si u y v son dos elementos de X ∗ se tiene que u ĺ v
si y sólo sí
• o bien |u| < |v|
• o bien |u| = |v| y existen w, u0 , v 0 ∈ X ∗ y a, b ∈ X tales que u = u0 aw, v = v 0 bw y b E a.
Así, es u ĺ v si o bien u es estríctamente más corto que v o bien tiene la misma longitud y
la última letra en la que u difiere de v es mayor o igual que la correspondiente letra de v con
respecto al orden de X.
Por ejemplo, si X = {x, y, z} y x E y E z, entonces los monomios de longitud 3 se ordenan
con respecto al orden deglex de la siguiente manera:
zzz,
yzz,
xzz,
zyz,
yyz,
xyz,
zxz,
yxz,
xxz
zzy,
yzy,
xzy,
zyy,
yyy,
xyy,
zxy,
yxy,
xxy
zzx,
yzx,
xzx,
zyx,
yyx,
xyx,
zxx,
yxx,
xxx.
3.6. Supongamos que X = {x, y}. A cada palabra u = u1 · · · un ∈ hXi de longitud n ≥ 0 le {p:areas}
asignamos la poligonal en el plano con vértices v0 , . . . , vn tales que v0 = (0, 0) y

v
i−1 + (1, 0), si ui = x,
vi =
vi−1 + (0, 1), si ui = y,
Escribimos η(u) a la altura del punto más alto de la curva y α(u) al area que delimita junto con
9
xxxxx
xxxxy
xxxyx
xxyxx
xyxxx
yxxxx
xxxyy
xxyxy
xyxxy
xxyyx
yxxxy
xyxyx
yxxyx
xyyxx
yxyxx
yyxxx
xxyyy
xyxyy
yxxyy
xyyxy
yxyxy
xyyyx
yyxxy
yxyyx
yyxyx
yyyxx
xyyyy
yxyyy
yyxyy
yyyxy
yyyyx
yyyyy
Figura 1. Las 32 palabras de longitud 5 sobre X = {x, y} ordenadas de acuerdo
al orden monomial del ejemplo 3.6.
{fig:areas}
el eje de abcisas. Por ejemplo, a la palabra u = xyxxyxyxxxy le corresponde la poligonal
(7, 4)
η(u)
α(u)
y es η(u) = 4 y α(u) = 13.
Hay un orden monomial en hXi para el cual si u, v ∈ hXi se tiene u ĺ v sii
• |u| < |v|,
• o |u| = |v| y η(u) < η(v),
• o |u| = |v|, η(u) = η(v) y α(u) = α(v).
En la Figura 1 están dibujadas las poligonales correspondientes a todas las palabras de longitud 5 {[email protected]}
{[email protected]}
ordenadas de acuerdo a este orden.
10
La condición de cadena descendente
3.7. Decimos que un conjunto ordenado P satisface la condición de cadena descendente si no
existe ninguna sucesión (pi )i∈N tal que pi ŋ pi+1 para todo i ∈ N. Equivalentemente, P satisface
la condición de cadena descendente si cada vez que (pi )i∈N es una sucesión descendente en P , de
manera que pi ľ pi+1 para todo i ∈ N, existe i0 ∈ N tal que pi = pi0 para todo i ≥ i0 —es decir,
si toda sucesión en P no creciente a la larga se estabiliza.
Por otro lado, decimos que un conjunto totalmente ordenado P está bien ordenado si todo
subconjunto no vacío de P tiene un mínimo. El ejemplo fundamental de conjunto bien ordenado
es N, cuando está dotado de su orden usual.
3.8. Cuando el conjunto está bien ordenado, estos dos conceptos coinciden:
Lema. Un conjunto totalmente ordenado está bien ordenado si y solamente si satisface la
condición de cadena descendente.
Demostración. Sea P un conjunto totalmente ordenado. Si existe una sucesión estrictamente
decreciente (pi )i∈N en P , es claro que el conjunto {pi : i ∈ N} no tiene mínimo: esto muestra
que la condición del enunciado es necesaria. Recíprocamente, supongamos que Q ⊆ P es un
subconjunto no vacío que no tiene mínimo. Sea p1 ∈ Q un elemento arbitrario. Como Q no
tiene mínimo, p1 no es el mínimo de Q y, entonces, existe p2 ∈ Q tal que o bien p1 y p2 no son
comparables o bien p2 ň p1 y, como P está totalmente ordenado, la primera posibilidad no puede
ocurrir. De la misma forma, p2 no es un mínimo de Q, así que existe p3 ∈ Q tal que p3 ň p2 y,
continuando de esta forma, podemos construir una sucesión (pi )i∈N de elementos de P que es
estrictamente decreciente.
3.9. Necesitaremos el siguiente lema en la prueba del Teorema 3.10.
{lema:subsec}
Lema. Si P es un conjunto bien ordenado, entonces toda sucesión de elementos de P posee una
subsucesión no decreciente.
Demostración. Consideremos una sucesión (pi )i≥1 en P . Construimos una sucesión (µi )i≥1
de elementos de P y otra (ji )i≥1 de enteros positivos de forma inductiva, empezando con
µ1 = min{pi : i ≥ 1} y j1 = min{i ∈ N : pi = µ1 }. Si k ≥ 1 y ya construimos µk y jk , entonces
ponemos µk+1 = min{pi : i > jk } y jk+1 = min{i : i > jk , pi = µk+1 }.
Es claro de la construcción que jk < jk+1 para todo k ≥ 1 y que pj1 = µ1 ĺ pj2 , y si k ≥ 2,
entonces
pjk = µk = min{pi : i > jk−1 } ĺ min{pi : i > jk } = µk+1 = pjk+1 .
Esto muestra que (pjk )k≥1 es una subsucesión de (pi )i≥1 que es no decreciente.
3.10. Teorema. Si X = {x, y} tiene dos elementos, entonces todo orden monomial sobre X ∗
satisface la condición de cadena descendente.
Demostración. Supongamos que hay una sucesión de monomios (wi )i≥1 en X ∗ que es estrictamente
decreciente para el orden ĺ. Como la sucesión (xwi )i≥1 tiene entonces la misma propiedad,
podemos suponer, de hecho, que todos los monomios wi empiezan con la letra x.
11
{teo:dos}
Si w ∈ X ∗ es un monomio, sea φ(w) la cantidad de veces que xy aparece en w, esto es,
φ(w) = #{(u, v) ∈ X ∗ × X ∗ : w = uxyv}
Supongamos que la sucesión (φ(wi ))i≥1 de enteros no es acotada. Si l = |w1 |, existe t ≥ 1 tal que
φ(wt ) > l, y entonces hay monomios α0 , . . . , αl ∈ X ∗ tales que
wt = α0 xyα1 xyα2 · · · xyαl .
Si w = a1 · · · al con a1 , . . . , al ∈ X, entonces es ai ĺ xyαi para cada i ∈ JlK, porque ai es un
factor de xyαi , y se sigue de esto que
w1 = a1 · · · al ĺ xyα1 · · · xyαl ĺ wt .
Esto es absurdo, porque w1 ŋ wt .
Vemos así que la sucesión (φ(wi ))i≥1 es acotada. Es claro que existe entonces s ∈ N0 tal que
el conjunto {i ∈ N : φ(wi ) = s} es infinito y, a menos de reemplazar a la sucesión (wi )i≥1 por una
de sus subsucesiones, podemos asumir que, de hecho, φ(wi ) = s para todo i ≥ 1.
Si fuese s = 0, tendríamos que para cada i ≥ 1 existe ni ∈ N0 con wi = xni y, como
xni = wi ŋ wi+1 = xxi+1 ,
que ni > ni+1 . Esto es imposible y debe ser, en consecuencia, s > 0. Se sigue de esto que para
cada i ≥ 0 hay enteros positivos mi,1 ,. . . , mi,2s tales que
wi = xmi,1 y mi,2 xmi,3 y mi,4 · · · xmi,2s−1 y mi,2s .
De acuerdo al Lema 3.9, existe una subsucesión de la sucesión (mi,1 )i≥1 que es no decreciente.
Reemplazando a la sucesión (wi )i≥1 por una de sus subsucesiones, entonces, podemos suponer
sin pérdida de generalidad que, de hecho, mi,1 ≤ mi+1,1 para todo i ≥ 1. Hecho esto, otra vez
usando aquel lema vemos que existe una subsucesión de (mi,2 )i≥1 que es no decreciente y que, en
consecuencia, podemos suponer que mi,2 ≤ mi+1,2 para todo i ≥ 1.
Continuando de esta forma, concluimos que podemos suponer, de hecho, que mi,j ≤ mi+1,j
para todo i ≥ 1 y todo j ∈ J2sK. En particular, tenemos que xm1,2j−1 ĺ xm2,2j−1 e y m1,2j ĺ y m2,2j
para cada j ∈ JsK y, en consecuencia, que
w1 = xm1,1 y m1,2 xm1,3 y m1,4 · · · xm1,2s−1 y m1,2s
ĺ xm2,1 y m2,2 xm2,3 y m2,4 · · · xm2,2s−1 y m2,2s = w2 .
Esto es absurdo, ya que w1 ŋ w2 por hipótesis. Esta contradicción muestra que no puede ocurrir
que la sucesión (φ(wi ))i≥1 sea acotada, y completa la prueba del teorema.
3.11. Teorema. Todo orden monomial total en un monoide libre es un buen orden.
Demostración. To be done
3.12. Todo orden en un conjunto puede refinarse a un orden total,
12
§4. Sistemas de reescritura
4.1. Fijemos un conjunto X y un anillo conmutativo k.
4.2. Si u ∈ hXi, hay una única función k-lineal cf u : khXi → k tal que cf u (u) = 1 y cf u (v) = 0
para todo v ∈ hXi distinto de u. Si a ∈ khXi, llamamos a cf u (a) el coeficiente de u en a,
decimos que u aparece en a si cf u (a) 6= 0 y, en ese caso, que el elemento cf u (a)u de khXi es un
término de a. Se sigue inmediatamente del hecho de que hXi es una base de khXi que si a ∈ A,
entonces hay un numero finito de palabras de hXi que aparecen en a, que a tiene entonces un
numero finito de términos y que, de hecho, es igual a la suma de éstos.
4.3. Llamamos a los elementos de hXi × khXi reglas. Si σ ∈ hXi × khXi, escribimos wσ y fσ a
las componentes de σ, de manera que σ = (wσ , fσ ) y, cuando sea conveniente, escribimos a σ en
la forma wσ
fσ . Una reducción básica es una terna ordenada r = (u, σ, v) en la que u y v
son palabras y σ es una regla; si queremos poner de manifiesto a la segunda componente de r
decimos que está asociada a σ. Escribimos R al conjunto de todas las reducciones básicas y
llamamos reducciones a los elementos del monoide libre hRi generado por R.
Si r = (u, σ, v) ∈ R, hay una función k-lineal rˆ : khXi → khXi tal que para cada a ∈ khXi es
rˆ(a) = a − cf uwσ v (a)u(wσ − fσ )v.
(7)
{eq:hatr}
Si a ∈ khXi es tal que rˆ(a) = a, decimos que r actúa trivialmente sobre a. Es rˆ = idkhXi si y
solamente si wσ = fσ . En efecto si vale la condición es claro de (7) que rˆ is la función identidad
y, recíprocamente, si wσ 6= fσ , entonces uwσ v − rˆ(uwσ v) = u(wσ − fσ )v 6= 0, ya que ni u ni v son
divisores de cero en khXi, de acuerdo a la Proposición 2.3.
Si vemos a Endk (khXi) como un monoide con la composición como operación, la Proposición 1.6 nos dice que existe un único morfismo de monoides hRi → Endk (khXi) que extiende
a la función r ∈ R 7→ rˆ ∈ Endk (khXi). Escribiremos rˆ a la imagen de un elemento arbitrario r
de hXi por ese morfismo, extendiendo la notación usada para reducciones básicas. Es claro que
si r = rn · · · r1 es una reducción con r1 , . . . , rn ∈ R, entonces rˆ = rˆn ◦ · · · ◦ rˆ1 .
4.4. Un sistema de reescritura es un subconjunto Σ ⊆ hXi × khXi tal que
para todo σ ∈ Σ es wσ 6= fσ .
Escribimos RΣ al conjunto de reducciones básicas asociadas a las reglas de Σ, a las que llamamos
simplemente reducciones básicas de Σ, y los elementos del submonoide hRΣ i de hRi son las
reducciones de Σ.
A Σ asociamos el ideal bilátero IΣ de khXi generado por el conjunto SΣ = {wσ − fσ : σ ∈ Σ}
y el álgebra AΣ = khXi/IΣ . Si φ : khXi → A es la proyección canónica, entonces (X, SΣ , φ) es
una presentación del álgebra AΣ .
4.5. Un elemento a ∈ khXi es irreducible con respecto a Σ si rˆ(a) = a para todo r ∈ RΣ y en
ese caso, por supuesto, tenemos más generalmente que rˆ(a) = a para toda reducción r de Σ.
13
{prop:sigma:irr}
Proposición. Un elemento de khXi es irreducible si y solamente si no aparece en él ningún
monomio de hXi que tiene un factor de la forma wσ con σ ∈ Σ. El subconjunto khXiirr de khXi
de los elemento irreducibles es un k-submódulo.
Demostración. Si a ∈ khXi, la ecuación (7) deja en claro que a es irreducible sii cf uwσ v (a) = 0
para toda reducción básica (u, σ, v), esto es, si no aparece en a ningún monomio de la forma uwσ v
T
con σ ∈ Σ, como afirma la proposición. Es khXiirr = r∈RΣ ker(ˆ
r − idkhXi ) y para cada r ∈ RΣ
la función rˆ − idkhXi es k-lineal, así que khXiirr es un k-submódulo de khXi.
elemento a es de reducción finita con respecto a Σ si cada vez que (ri )i≥1 es una sucesión
de reducciones de Σ existe i0 ≥ 1 tal que para todo i > i0 la reducción ri actúa trivialmente sobre
(ri−1 · · · r1 )ˆ(a). Notemos que si i0 tiene esta propiedad, cualquier entero más grande también la
tiene; por otro lado, para que a sea de reducción finita es suficiente que la condición se cumpla
para sucesiones de reducciones básicas.
Proposición. El conjunto khXifin de los elementos de reducción finita de khXi es un k-submódulo.
Si r es una reducción, entonces rˆ(khXifin ) ⊆ khXifin .
Demostración. Sean a, b ∈ khXi dos elementos de reducción finita y sea λ ∈ k. Sea (ri )i≥1 una
sucesión de reducciones de Σ. Por hipótesis, existe i0 ≥ 1 tal que para cada i > i0 la reducción ri
actúa trivialmente tanto sobre (ri−1 · · · r1 )ˆ(a) como sobre (ri−1 · · · r1 )ˆ(b) y entonces también
actúa trivialmente sobre (ri−1 · · · r1 )ˆ(a + λb). Esto muestra que a + λb es de reducción finita.
Sean ahora a ∈ khXi un elemento de reducción finita y r una reducción. Sea (ri )i≥1 es una
sucesión de reducciones y consideremos la nueva sucesión (si )i≥1 con s1 = r y si = ri−1 para cada
i ≥ 1. Como a es de reducción finita, existe i0 ≥ 1 tal que para cada i > i0 la reducción si actúa
trivialmente sobre (si−1 · · · s1 )ˆ(a) y podemos suponer, de hecho, que i0 > 1. Esto significa, ni
más ni menos, que para cada i > i0 − 1 la reducción ri actúa trivialmente sobre (ri−1 · · · r1 )ˆ(ˆ
r(a)).
Vemos de esta forma que rˆ(a) es de reducción finita.
4.6. Si a ∈ khXi y r es una reducción de Σ, decimos que r es final para a si rˆ(a) es irreducible.
Proposición. Si a ∈ khXi es de reducción finita, entonces existe una reducción r que es final
para a.
Demostración. Consideremos el conjunto W de todas las sucesiones finitas de reducciones
(ri )1≤i≤n de longitud n ≥ 0 tales que para cada i ∈ JnK la reducción ri actúa no trivialmente
sobre (ri−1 · · · r1 )ˆ(a). Definimos un orden ĺ sobre W : si ρ = (ri )1≤i≤n y σ = (si )1≤i≤m son
dos elementos de W , ponemos ρ ĺ σ si y solamente si n ≤ m y ri = si para cada i ∈ JnK; es
inmediato verificar que de esta forma obtenemos en efecto una relación de orden.
Afirmamos que hay en W elementos maximales. Si no fuese ése el caso, existiría una sucesión
(ρj )j≥1 de elementos de W con ρj ň ρj+1 para todo j ≥ 1. Si ρj = (rj,i )1≤i≤nj para cada
j ≥ 1, entonces tenemos que nj < nj+1 para todo j ≥ 1, de manera que, de hecho, nj ≥ j
cualquiera sea j. Pongamos si = ri,i para cada i ≥ 1 y consideremos la sucesión (si )i≥1 ; se tiene
que si = rj,i siempre que 1 ≤ i ≤ j. Si i ≥ 1, entonces si = ri,i actúa no trivialmente sobre
(si−1 · · · s1 )ˆ(a) = (ri−1,i−1 · · · r1,1 )ˆ(a) = (ri,i−1 · · · ri,1 )ˆ(a) porque ρi ∈ W . Esto es imposible,
ya que a es de reducción finita.
14
{prop:sigma:fin}
Sea, entonces, ρ = (ri )1≤i≤n un elemento maximal de W y consideremos la reducción
r = rn · · · r1 . El elemento rˆ(a) es irreducible: si no lo fuera, existiría una reduccción rn+1 de Σ
que actúa no trivialmente sobre rˆ(a) y, entonces, la secuencia ρ0 = (ri )1≤i≤n+1 sería un elemento
de W . Como ρ ň ρ0 , esto es absurdo. Vemos así que r es una reducción final para a.
4.7. Un elemento a ∈ khXi es de reducción única si es de reducción finita y existe rΣ (a) ∈ khXi
tal que para cada reducción r ∈ hRΣ i que es final para a es rˆ(a) = rΣ (a). Notemos que como
a es de reducción finita, entonces existen efectivamente reducciones que son finales para a,
y en consecuencia el elemento rΣ (a) está unívocamente determinado por a. Si escribimos
khXiuniq al conjunto de los elementos de reducción única, obtenemos de esta forma una función
rΣ : khXiuniq → khXiirr .
4.8. Una propiedad fundamental de los elementos de reducción única es la siguiente:
Proposición. Si a ∈ khXi es de reducción única y r es una reducción, entonces existe una
reducción r0 tal que rˆ0 (ˆ
r(a)) = rΣ (a). El elemento rˆ(a) es de reducción única y rΣ (ˆ
r(a)) = rΣ (a).
Demostración. Construimos una sucesión de reducciones básicas (ri )i≥1 inductivamente, empezando con r1 = r.Si i ≥ 1 y ya elegimos las reducciones r1 , . . . , ri , entonces o bien el elemento
b = (ri · · · r1 )ˆ(a) es irreducible o no: en el primer caso, elegimos ri+1 en RΣ arbitrariamente,
y en el segundo elegimos ri+1 ∈ RΣ de manera que rˆi+1 (b) 6= b. Como a es de reducción finita,
existe i0 ≥ 1 tal que para cada i > i0 la reducción ri actúa trivialmente sobre (ri−1 · · · r1 )ˆ(a).
La forma en que construmos la sucesión (ri )i≥1 implica entonces que si ponemos r0 = ri0 · · · r2 , se
tiene que rˆ0 (ˆ
r(a)) = (ri0 · · · r1 )ˆ(a) es irreducible, de manera que la reducción r0 r es final para a.
Como a es de reducción única, vemos entonces que rˆ0 (ˆ
r(a)) = rΣ (a).
De la Proposición 4.5 sabemos que rˆ(a) es de reducción finita. Si s es una reducción final
para rˆ(a), entonces la parte del lema que ya probamos nos dice que existe una reducción t
tal que tˆ(ˆ
s(ˆ
r(a))) = tˆ((sr)ˆ(a)) = rΣ (a). Como s es final para rˆ(a), el elemento sˆ(ˆ
r(a)) es
irreducible, y entonces t actúa trivialmente sobre él: esto nos dice que, de hecho, sˆ(ˆ
r(a)) = rΣ (a).
El lado derecho de esta última igualdad no depende de r, así que rˆ(a) es de reducción única y
rΣ (ˆ
r(a)) = rΣ (a). Esto completa la prueba de la proposición.
4.9. Un corolario inmediato de esta proposición es el siguiente resultado que nos permite reconocer
la forma final de un elemento de reducción finita.
Corolario. Si a ∈ khXi es de reducción única y r es una reducción tal que rˆ(a) es irreducible,
entonces rΣ (a) = rˆ(a).
Demostración. En efecto, en ese caso la reducción r0 cuya existencia afirma la proposición actúa
trivialmente sobre rˆ(a) y, en consecuencua, rˆ(a) = rΣ (a).
4.10. Proposición. khXiuniq es un k-submódulo de khXifin y la función rΣ : khXiuniq → khXiirr
es k-lineal. Si r es una reducción, entonces rˆ(khXiuniq ) ⊆ khXiuniq .
Demostración. Sean a y b dos elementos de khXi de reducción única y sea λ ∈ k. De acuerdo a
la Proposición 4.5 el elemento c = a + λb es de reducción finita.
Sea r una reducción final para c. Como a es de reducción única, hay una reducción r1 tal que
15
{prop:sigma:unique}
rˆ1 (ˆ
r(a)) = rΣ (a), y como b es de reducción única, hay una reducción r2 tal que rˆ2 (ˆ
r1 (ˆ
r(b))) = rΣ (b).
Tenemos entonces que
rˆ(c) = rˆ2 (ˆ
r1 (ˆ
r(x)))
porque rˆ(x) es irreducible
= rˆ2 (ˆ
r1 (ˆ
r(a))) + λˆ
r2 (ˆ
r1 (ˆ
r(b)))
= rˆ2 (rΣ (a)) + λrΣ (b)
= rΣ (a) + λrΣ (b)
porque rΣ (a) es irreducible.
El último miembro de esta cadena de iguadades es independiente de r, así que c es de reducción
única y, de hecho, rΣ (c) = rΣ (a) + λrΣ (b). Esto prueba las dos primeras afirmaciones de la
proposición.
Para ver la tercera, sea a ∈ khXi un elemento de reducción única y r una reducción. De la
Proposición 4.5 sabemos que rˆ(a) es de reducción finita. Si s es una reducción final para rˆ(a),
entonces sˆ(ˆ
r(a)) es irreducible e igual a (sr)ˆ(a). Como a es de reducción única, esto implica que,
de hecho, sˆ(ˆ
r(a)) = rΣ (a). Así, sˆ(ˆ
r(a)) no depende de s y rˆ(a) es de reducción única.
4.11. Proposición. Sean a, b, c ∈ khXi tales que cada vez que u, v, w ∈ hXi son monomios
que aparecen en a, b y c, respectivamente, el producto uvw es de reducción única. Si r es una
reducción de Σ, entonces aˆ
r(b)c es de reducción única y rΣ (aˆ
r(b)c) = rΣ (abc).
Notemos que la hipótesis implica, de acuerdo a la Proposición 4.10, que abc es de reducción
única, y entonces tiene sentido hablar de rΣ (abc).
Demostración. Sea r una reducción. Si u1 , . . . , un , que v1 , . . . , vm y w1 , . . . , wp son los
Pn
monomios que aparecen en a, en b y en c, respectivamente, de manera que a = i=1 cf ui (a)ui ,
Pm
Pp
b = j=1 cf vj (b)vj y c = k=1 cf wk (c)wk , entonces
aˆ
r(b)c =
X
cf ui (a) cf vj (b) cf wk (c) ui rˆ(vj )wk
1≤i≤n
1≤j≤m
1≤k≤p
y, como khXiuniq es un k-submódulo, vemos que para mostrar que aˆ
r(b)c es de reducción única
alcanza con mostrar que ui rˆ(vj )wk lo es cualquier sean i ∈ JnK, j ∈ JmK y k ∈ JpK. Esto significa
que para probar a proposición alcanza con mostrar que es cierta en el caso particular en el que
a, b y c son monomios. Pongámonos entonces en ese caso.
Supongamos que r = rn · · · r1 con r1 , . . . , rn reducciones básicas de Σ y que para cada
i ∈ JnK es ri = (ui , σi , vi ). Podemos entonces considerar para cada i ∈ JnK la reducción
básica si = (aui , σi , vi c) y la reducción s = sn · · · s1 . Como abc es de reducción única, la
Proposición 4.10 nos dice que sˆ(abc) es de reducción única y existe entonces una reducción t
tal que tˆ(ˆ
s(abc)) = rΣ (abc). Como sˆ(abc) = aˆ
r(b)c, esto nos dice, por un lado, que aˆ
r(b)c es de
ˆ
ˆ
reducción única y, por otro, que rΣ (aˆ
r(b)c) = rΣ (abc) ya que t(aˆ
r(b)c) = t(ˆ
s(abc)) = rΣ (abc) y
este último elemento es irreducible.
16
§5. El lema del diamante
5.1. Fijemos un conjunto X, un anillo conmutativo k y un sistema de reescritura Σ ⊆ hXi × khXi.
5.2. Consideremos una 5-upla α = (σ, τ, u, v, w) con σ, τ ∈ Σ y u, v, w ∈ hXi. Decimos que α es
una ambigüedad por solapamiento de Σ si los monomios u, v y w tienen longitud positiva,
wσ = uv y wτ = vw y que es resoluble si existen reducciones r, r0 tales que rˆ(fσ w) = rˆ0 (ufτ ).
Por otro lado, la 5-upla α es una ambigüedad por inclusión si σ 6= τ , wσ = v y wτ = abc
y en ese caso es resoluble si existen reducciones r y r0 tales que rˆ(ufσ w) = rˆ0 (fτ ).
5.3. Sea ĺ un orden monomial sobre hXi. Decimos que ĺ es compatible con Σ si para cada
σ ∈ Σ y cada monomio u que aparece en fσ tenemos que u ň wσ . Si ese es el caso, para cada
monomio w ∈ hXi consideramos el k-submódulo Iw de khXi generado por el conjunto
{u(wσ − fσ )v : u, v ∈ hXi, σ ∈ Σ, uwσ v ň w}
Si w0 es otro monomio y w0 ň w, es claro que Iw0 ⊆ Iw .
5.4. Proposición. Si existe un orden monomial ň en hXi compatible con Σ y que satisface la
condición de cadena descendente, entonces todo elemento de khXi es de reducción finita.
Demostración. Sea a ∈ khXi, sea (ri )i≥1 una sucesión de reducciones y, para llegar a un absurdo,
supongamos que para todo i ≥ 1 la reducción ri actúa no trivialmemente sobre (ri−1 · · · r1 )ˆ(a).
5.5. Si α = (σ, τ, u, v, w) es una ambigüedad de Σ, decimos que α es resoluble con respecto
al orden ĺ si fσ w − ufτ ∈ Iuvw en caso que α sea una ambigüedad por solapamiento y si
ufσ w − fτ ∈ Iuvw en caso que α sea una ambigüedad por inclusión.
Lema. Una ambigüedad de Σ que es resoluble es resoluble con respecto a cualquier orden monomial
compatible con Σ.
Demostración. Supongamos que u es un monomio y r = (a, σ, c) una reducción básica de Σ. Si
u 6= awσ c, entonces rˆ(u) = u; si en cambio u = awσ c, es rˆ(u) = afσ c y esto es un elemento de Iu
porque el orden ĺ es compatible con Σ. En cualquier caso, entonces, tenemos que u − rˆ(u) ∈ Iu .
5.6. Estamos por fin en condiciones de enunciar el resultado que motiva estas notas:
Teorema. Sea X un conjunto, k un anillo conmutativo, Σ ⊆ hXi×khXi un sistema de reescritura
y ĺ un orden monomial en hXi que es compatible con Σ y que satisface la condición de cadena
descendente. Las siguienes afirmaciones son equivalentes:
(a) Todas las ambigüedades de Σ son resolubles.
(b) Todas las ambigüedades de Σ son resolubles con respecto a ĺ.
(c) Todos los elementos de khXi son de reducción única con respecto a Σ.
(d) Se tiene que khXi = IΣ ⊕ khXiirr .
Demostración.
17
{teo:diamante}
§6. Ejemplos
§7. Ejercicios
(i) Si X e Y son dos conjuntos y k un cuerpo, lás k-álgebras khXi y khY i son isomorfas
si y solamente si X e Y tienen el mismo cardinal.
1.
(ii) No toda subálgebra de un álgebra libre es libre; por ejemplo, k[x2 , y 3 ] es una subálgebra
de k[x] que no es libre. P. Cohn dio en [Coh64] una caracterización de las subálgebras
que son libres.
†
(iii) Si X es un conjunto con más de un elemento, entonces existen en khXi subálgebras
libres de rango numerable y, entonces, subálgebras libres de todos los rangos finitos.
2. Muestre que los órdenes descriptos en los ejemplos de la Sección 3 son efectivamente órdenes
monomiales.
Referencias
[Coh64] P. M. Cohn, Subalgebras of free associative algebras, Proc. London Math. Soc. (3) 14 (1964), 618–632.
MR0167504 (29 #4777) ↑18
18