Álgebra de las palabras

El álgebra de las palabras estudia la formalización gramatical de las construcciones de palabras sobre un alfabeto para un lenguaje, desde una perspectiva matemática que permita, de un modo firme, afirmar o rechazar diversos resultados necesarios para fundamentar cualquier modelo matemático de un lenguaje, y más inmediatamente el lenguaje proposicional.

El álgebra de las palabras sobre un alfabeto

Los alfabetos se asocian a conjuntos que pueden ser finitos, numerables de símbolos.

Introducción

La notación matemática utilizada es la desarrollada en teoría de conjuntos, por lo que requiere una base mínima para un rápido trabajo y asimilación con simplicidad y fluidez de los nuevos conceptos.

Para introducir nociones que permitan unir símbolos se necesita las siguientes definiciones.

Par ordenado

Dado un par de elementos de un conjunto $A_{}^{}$, es decir, $a,b\in A$, se llama a $<a,b>_{}^{}$ un par ordenado.

Nota:

Estos pares pueden ser formalmente elementos de nuevos conjuntos sin ningún impedimento, y se pueden comparar con otros pares ordenados $<c,d>_{}^{}$ exclusivamente en este orden, primero a con c y luego b con d.

Producto cartesiano

Se llama producto cartesiano de dos conjuntos $A_{}^{}$ y $B_{}^{}$ al conjunto $A\times B:=\{<a,\;b>:a\in A,\;b\in B\}.$

Palabras sobre un alfabeto

Dado un conjunto $A_{}^{}$ y un número natural $n\geq 1_{}^{}$, se define el conjunto de las sucesiones finitas de longitud n de elementos de $A_{}^{}$, $A_{}^{n}$, como el n-ésimo conjunto de la lista siguiente definida por inducción:

${\begin{matrix}A^{1}&=&A\\A^{2}&=&A\times A\\&\vdots &\\A^{n}&=&A^{n-1}\times A\\&\vdots &\end{matrix}}$

Se llaman palabras sobre un alfabeto $A_{}^{}$ al conjunto de las sucesiones finitas de elementos de A definido como el conjunto $A^{\ast }=\bigcup _{n\geq 1}A^{n}$, es decir, las palabras son por definición una colección de todas las sucesiones finitas de elementos de un mismo alfabeto.

Notaciones:

• Los elementos de $A_{}^{1}$ son elementos notados por $x:=<x_{}^{}>$ donde $x\in A.$

• Los elementos de $A_{}^{2}$ son pares ordenados, notados como $<a,\;b>:=<<a>,\;b_{}^{}>$ donde $a,b\in A.$

• Los elementos de $A_{}^{3}$ son ternas ordenadas, notadas como $<a,\;b,\;c>:=<<a,\;b>,\;c_{}^{}>$ donde $a,b,c\in A.$

• En general, para $A_{}^{n}$ se tienen sucesiones finitas de longitud n notadas como $<a_{1},\;\dots ,\;a_{n-1}^{},\;a_{n}>:=$ $<<a_{1},\;\dots ,\;a_{n-1}^{}>,\;a_{n}>$ donde $a_{i}\in A$, $\forall i\in \{1,\;\dots ,\;n\}.$

• Para determinar el contenido de un elemento $a\in A_{}^{n}$ se indica como $a=<a_{1},\;\dots ,\;a_{n}^{}>$ donde $a_{i}^{}$ será el i-ésimo termino de la sucesión.

Esta última notación permite, ya, comparar palabras, son destacables los resultados siguientes:

Sucesiones de igual longitud

Dado dos elementos $a^{n},b^{n}\in A^{n}$, entonces

$a^{n}=<a_{1},\;\dots ,\;a_{n}>=<b_{1}^{},\;\dots ,\;b_{n}>=b^{n}\Leftrightarrow$ $a_{i}=b_{i},\;\forall i\in \{1,\;\dots ,\;n\}.$

No es necesario definirlo así, pues se puede demostrar a partir de las definiciones que ya se tiene, la demostración habitual, para sucesiones, es comparando los elementos ordenadamente según existan, es decir, mediante inducción:

Si n=1, se tiene $<a_{1}^{}>=<b_{1}>$ por notación sabemos que $a_{1}^{}=b_{1}.$

Si n=2, es decir un par ordenado, se tiene $<a_{1},\;a_{2}>=<b_{1},\;b_{2}^{}>$ por comparación de un par ordenado $a_{1}=b_{1}^{}$ y $a_{2}=b_{2}^{}.$

Supóngase que para el caso n-1 es cierto, véase que también lo es para n, es decir, que es cierto que $a^{n-1}=<a_{1},\;\dots ,\;a_{n-1}^{}>=$ $<b_{1},\;\dots ,\;b_{n-1}^{}>=b^{n-1}\Leftrightarrow$ $a_{i}=b_{i},\;\forall i\in \{1,\;\dots ,\;n-1\}$, y ahora se tiene que comprobar para el caso n:

$<<a_{1},\;\dots ,\;a_{n-1}>,\;a_{n}^{}>=<<b_{1},\;\dots ,\;b_{n-1}>,\;b_{n}>$, es decir, $<<a^{n-1}>,\;a_{n}>=<<b^{n-1}>,\;b_{n}^{}>$, es decir, $<a^{n-1},\;a_{n}>=<b^{n-1},\;b_{n}^{}>\Leftrightarrow$ $a^{n-1}=b_{}^{n-1}$ y $a_{n}=b_{n}^{}$ como se vio en el caso n=2.

Sucesiones de diferente longitud

Dado dos elementos $a^{m},b^{m+k}\in A^{\ast }$ tales que $a_{}^{m}=$ $<a_{1},\;\dots ,\;a_{m}^{}>=$ $<b_{1}^{},\;\dots ,\;b_{m+k}>=$ $b_{}^{m+k}$ con k>0 y m>1, entonces:

$a_{1}^{}=<b_{1},\;\dots ,\;b_{k+1}^{}>$ y $a_{i}=b_{i+k}^{}$, $\forall i\in \{1,\;\dots ,\;m\}.$

Informalmente es evidente que $a_{1}^{}=$ $<b_{1},\;\dots ,\;b_{k+1}^{}>$ debido al resultado anterior para sucesiones de igual longitud, para demostrarlo formalmente se procede del modo siguiente:

Si m=1, se tiene directamente que $a_{1}^{}=$ $<b_{1},\;\dots ,\;b_{k+1}^{}>$, y por tanto es cierto.

Si m=2, se tiene que $<a_{1}^{},\;a_{2}>=$ $<<b_{1},\;\dots ,\;b_{k+1}>,\;b_{k+2}>$, como par ordenado, sucede que $a_{1}^{}=$ $<b_{1},\;\dots ,\;b_{k+1}^{}>.$

Supóngase que el caso m-1 es cierto, véase ahora que también lo es para m:

Por hipótesis se puede tomar el par ordenado $<<a_{1},\;\dots ,\;a_{m-1}^{}>,\;a_{m}>=$ $<<b_{1},\;\dots ,\;b_{(m-1)+k}>,\;b_{m+k}^{}>$, esto prueba la certeza, pues tienen las mismas hipótesis para una k>0 fijada.

Corolario

Dado un conjunto $A_{}^{}$ sin elementos expresados mediante sucesiones finitas de sus propios elementos, si $a,b\in A_{}^{\ast }:a=b$ entonces:

• a y b son de la misma longitud,

• $A_{}^{n}\cap A^{m}=\emptyset$ para $n\neq m_{}^{}.$

Concatenación

Se llama operación concatenación entre sucesiones finitas a:

${\begin{matrix}\circ :&A^{\ast }\times A^{\ast }&\longrightarrow &A^{\ast }\\&<<a_{1},\;\dots ,\;a_{n}>,<b_{1},\;\dots ,\;b_{m}>>&\longmapsto &<a_{1},\;\dots ,\;a_{n}>\circ <b_{1},\;\dots ,\;b_{m}>=<a_{1},\;\dots ,\;a_{n},\;b_{1},\;\dots ,\;b_{m}>.\end{matrix}}$

Por tanto la estructura $<A^{\ast },\;\circ >$ es un grupoide libre generado por el conjunto $A_{}^{}$.

Para hacer referencia al mismo objeto matemático, se escribe por comodidad simplemente $a_{1}\dots a_{n}:=$ $<a_{1},\;\dots ,\;a_{n}>=$ $<a_{1}>\circ \cdots \circ <a_{n}>.$

Véase también

• Lenguaje proposicional
• Lógica de primer orden

Bibliografía

• Herbert B. Enderton, Elements of set theory, Academic Press, INC. 1977.

Contiene normas para la correcta lectura del texto.

• Herbert B. Enderton, A mathematical introduction to logic, A Harcourt Science an Technology Company 2001.

Exposición propia del álgebra de las palabras.

• Nino B. Cocchiarella and Max A. Freund, Modal Lógica An Introduction to Its Syntax and Semantics, Oxford 2008.

Contiene un resumen en el primer tema con cierta informalidad.

• Datos: Q6172678