Á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 ${\displaystyle A_{}^{}}$, es decir, ${\displaystyle a,b\in A}$, se llama a ${\displaystyle <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 ${\displaystyle <c,d>_{}^{}}$ exclusivamente en este orden, primero a con c y luego b con d.

Producto cartesiano

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

Palabras sobre un alfabeto

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

${\displaystyle {\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 ${\displaystyle A_{}^{}}$ al conjunto de las sucesiones finitas de elementos de A definido como el conjunto ${\displaystyle 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 ${\displaystyle A_{}^{1}}$ son elementos notados por ${\displaystyle x:=<x_{}^{}>}$ donde ${\displaystyle x\in A.}$

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

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

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

• Para determinar el contenido de un elemento ${\displaystyle a\in A_{}^{n}}$ se indica como ${\displaystyle a=<a_{1},\;\dots ,\;a_{n}^{}>}$ donde ${\displaystyle 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 ${\displaystyle a^{n},b^{n}\in A^{n}}$, entonces

${\displaystyle a^{n}=<a_{1},\;\dots ,\;a_{n}>=<b_{1}^{},\;\dots ,\;b_{n}>=b^{n}\Leftrightarrow }$ ${\displaystyle 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 ${\displaystyle <a_{1}^{}>=<b_{1}>}$ por notación sabemos que ${\displaystyle a_{1}^{}=b_{1}.}$

Si n=2, es decir un par ordenado, se tiene ${\displaystyle <a_{1},\;a_{2}>=<b_{1},\;b_{2}^{}>}$ por comparación de un par ordenado ${\displaystyle a_{1}=b_{1}^{}}$ y ${\displaystyle 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 ${\displaystyle a^{n-1}=<a_{1},\;\dots ,\;a_{n-1}^{}>=}$ ${\displaystyle <b_{1},\;\dots ,\;b_{n-1}^{}>=b^{n-1}\Leftrightarrow }$ ${\displaystyle a_{i}=b_{i},\;\forall i\in \{1,\;\dots ,\;n-1\}}$, y ahora se tiene que comprobar para el caso n:

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

Sucesiones de diferente longitud

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

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

Informalmente es evidente que ${\displaystyle a_{1}^{}=}$ ${\displaystyle <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 ${\displaystyle a_{1}^{}=}$ ${\displaystyle <b_{1},\;\dots ,\;b_{k+1}^{}>}$, y por tanto es cierto.

Si m=2, se tiene que ${\displaystyle <a_{1}^{},\;a_{2}>=}$ ${\displaystyle <<b_{1},\;\dots ,\;b_{k+1}>,\;b_{k+2}>}$, como par ordenado, sucede que ${\displaystyle a_{1}^{}=}$ ${\displaystyle <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 ${\displaystyle <<a_{1},\;\dots ,\;a_{m-1}^{}>,\;a_{m}>=}$ ${\displaystyle <<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 ${\displaystyle A_{}^{}}$ sin elementos expresados mediante sucesiones finitas de sus propios elementos, si ${\displaystyle a,b\in A_{}^{\ast }:a=b}$ entonces:

• a y b son de la misma longitud,

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

Concatenación

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

${\displaystyle {\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 ${\displaystyle <A^{\ast },\;\circ >}$ es un grupoide libre generado por el conjunto ${\displaystyle A_{}^{}}$.

Para hacer referencia al mismo objeto matemático, se escribe por comodidad simplemente ${\displaystyle a_{1}\dots a_{n}:=}$ ${\displaystyle <a_{1},\;\dots ,\;a_{n}>=}$ ${\displaystyle <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