Para generalizar el concepto de estructura es clave primero dar definiciones generales de los conceptos de operación y de relación sobre un conjunto.
Sea \(A\) un conjunto y sea \(n\in\mathbf{N}\). Por una operación \(n\)-aria sobre \(A\) entenderemos una función cuyo dominio es \(A^{n}\) y cuya imagen esta contenida en \(A\). Por una relación \(n\)-aria sobre \(A\) entenderemos un subconjunto de \(A^{n}\). Notar que por la definición anterior una relación 1-aria sobre \(A\) no es ni mas ni menos que un subconjunto de \(A\).
Como venimos viendo, hay una variedad de tipos de estructuras las cuales tienen un sentido o interés matemático claro y todas son de un formato similar, a saber uplas formadas por una primera coordenada que es un conjunto no vacío (llamado el universo de la estructura) y luego ciertas operaciones, relaciones y elementos distinguidos, dependiendo del caso. Otra cosa a notar es que para cada tipo de estructura hay ciertos símbolos fijos que usamos en forma genérica para denotar sus relaciones, operaciones y elementos distinguidos. Por ejemplo:
adhocprefix-adhocsufix Para los posets usamos el símbolo \(\leq\) para denotar su relación 2-aria de orden parcial, en un sentido genérico.
adhocprefix-adhocsufix Para el caso de los reticulados terna usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones 2-arias de supremo e ínfimo
adhocprefix-adhocsufix Para el caso de los reticulados acotados usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones 2-arias de supremo e ínfimo y los numerales \(0\) y \(1\) para denotar sus elementos distinguidos, a saber mínimo y máximo respectivamente.
adhocprefix-adhocsufix Para el caso de los reticulados complementados usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones 2-arias de supremo e ínfimo, el símbolo \(c\) para denotar su operación \(1\)-aria de complementación y los numerales \(0\) y \(1\) para denotar sus elementos distinguidos, a saber mínimo y máximo respectivamente.
adhocprefix-adhocsufix Para el caso de los reticulados cuaterna usamos en forma genérica los símbolos \(\mathsf{s}\) e \(\mathsf{i}\) para denotar sus operaciones 2-arias de supremo e ínfimo y el símbolo \(\leq\) para denotar su relación 2-aria de orden parcial
adhocprefix-adhocsufix Para las median algebras usamos genéricamente el símbolo \(M\) para denotar su operación \(3\)-aria.
adhocprefix-adhocsufix Para los grafos usamos el símbolo \(r\) para denotar en forma genérica su relación 2-aria.
adhocprefix-adhocsufix Para los grafos bicoloreados usamos el símbolo \(r\) para denotar en forma genérica la relación 2-aria del grafo y el símbolo \(R\) para denotar genéricamente la relación 1-aria que determina el bicoloreo
O sea que para cada uno de los tipos de estructuras estudiadas se distinguen tres conjuntos de símbolos:
adhocprefix-adhocsufix Un conjunto \(\mathcal{C}\) formado por los símbolos que denotarán genéricamente los elementos distinguidos de las estructuras
adhocprefix-adhocsufix Un conjunto \(\mathcal{F}\) formado por los símbolos que denotarán genéricamente las operaciones de las estructuras
adhocprefix-adhocsufix Un conjunto \(\mathcal{R}\) formado por los símbolos que denotarán genéricamente las relaciones de las estructuras
Mas concretamente:
adhocprefix-adhocsufix Posets: \(\mathcal{C}=\emptyset\ \ \ \ \ \mathcal{F}=\emptyset\ \ \ \ \ \mathcal{R}=\{\leq\}\)
adhocprefix-adhocsufix Reticulados terna: \(\mathcal{C}=\emptyset\ \ \ \ \ \mathcal{F}=\{\mathsf{s},\mathsf{i}\}\ \ \ \ \ \mathcal{R}=\emptyset\)
adhocprefix-adhocsufix Reticulados acotados: \(\mathcal{C}=\{0,1\}\ \ \ \ \ \mathcal{F}=\{\mathsf{s},\mathsf{i}\}\ \ \ \ \ \mathcal{R}=\emptyset\)
adhocprefix-adhocsufix Reticulados complementados: \(\mathcal{C}=\{0,1\}\ \ \ \ \ \mathcal{F}=\{\mathsf{s},\mathsf{i},c\}\ \ \ \ \ \mathcal{R}=\emptyset\}\)
adhocprefix-adhocsufix Reticulados cuaterna: \(\mathcal{C}=\emptyset\ \ \ \ \ \mathcal{F}=\{\mathsf{s},\mathsf{i}\}\ \ \ \ \ \mathcal{R}=\{\leq\}\)
adhocprefix-adhocsufix Median algebras: \(\mathcal{C}=\emptyset\ \ \ \ \ \mathcal{F}=\{M\}\ \ \ \ \ \mathcal{R}=\emptyset\)
adhocprefix-adhocsufix Grafos: \(\mathcal{C}=\emptyset\ \ \ \ \ \mathcal{F}=\emptyset\ \ \ \ \ \mathcal{R}=\{r\}\)
adhocprefix-adhocsufix Grafos bicoloreados: \(\mathcal{C}=\emptyset\ \ \ \ \ \mathcal{F}=\emptyset\ \ \ \ \ \mathcal{R}=\{r,R\}\)
Por supuesto aquí es muy importante no confundir los símbolos con las operaciones que eventualmente ellos denotan. O sea en todos los ejemplos anteriores los elementos de \(\mathcal{C}\), \(\mathcal{F}\) y \(\mathcal{R}\) son símbolos, es decir su \(Ti\) es PALABRA.
Otra información importante que está implícita en cada uno de los tipos de estructuras estudiadas es la aridad de las operaciones que denotan los símbolos de \(\mathcal{F}\) y la aridad de las relaciones que denotan los símbolos de \(\mathcal{R}\). A esto lo representaremos con una función \(a:\mathcal{F}\cup\mathcal{R}\rightarrow\mathbf{N}\) la cual le asocia a cada símbolo de \(\mathcal{F}\) la aridad de las funciones que dicho símbolo denota y a cada símbolo de \(\mathcal{R}\) la aridad de las relaciones que dicho símbolo denota. Tenemos entonces:
adhocprefix-adhocsufix Posets: \(a=\{(\leq,2)\}\)
adhocprefix-adhocsufix Reticulados terna: \(a=\{(\mathsf{s},2),(\mathsf{i},2)\}\)
adhocprefix-adhocsufix Reticulados acotados: \(a=\{(\mathsf{s},2),(\mathsf{i},2)\}\)
adhocprefix-adhocsufix Reticulados complementados: \(a=\{(\mathsf{s},2),(\mathsf{i},2),(c,1)\}\)
adhocprefix-adhocsufix Reticulados cuaterna: \(a=\{(\mathsf{s},2),(\mathsf{i},2),(\leq,2)\}\)
adhocprefix-adhocsufix Median algebras: \(a=\{(M,3)\}\)
adhocprefix-adhocsufix Grafos: \(a=\{(r,2)\}\)
adhocprefix-adhocsufix Grafos bicoloreados: \(a=\{(r,2),(R,1)\}\)
Lo anterior motiva la siguiente definición de tipo (de estructura). Antes de darla recordemos que si \(\alpha,\beta\) son palabras cualesquiera, decimos que \(\alpha\) es subpalabra (propia) de \(\beta\) cuando (\(\alpha\notin\{\varepsilon,\beta\}\) y) existen palabras \(\delta,\gamma\) tales que \(\beta=\delta\alpha\gamma\). También recordemos que dado un alfabeto \(\Sigma\) se tiene que \(\Sigma^{+}=\Sigma^{\ast}-\{\varepsilon\}\).
Ahora sí, nuestra definición de tipo: Por un tipo (de primer orden) entenderemos una 4-upla \(\tau=(\mathcal{C},\mathcal{F},\mathcal{R},a)\) tal que:
adhocprefix(1)adhocsufix Hay alfabetos finitos \(\Sigma_{1}\), \(\Sigma_{2}\) y \(\Sigma_{3}\) tales:
adhocprefix(c)adhocsufix \(\mathcal{C}\subseteq\Sigma_{1}^{+}\), \(\mathcal{F}\subseteq\Sigma_{2}^{+}\) y \(\mathcal{R}\subseteq\Sigma_{3}^{+}\)
adhocprefix(b)adhocsufix \(\Sigma_{1}\), \(\Sigma_{2}\) y \(\Sigma_{3}\) son disjuntos de a pares.
adhocprefix(c)adhocsufix \(\Sigma_{1}\cup\Sigma_{2}\cup\Sigma_{3}\) no contiene ningún símbolo de la lista
\(\forall\ \exists\;\lnot\;\vee\;\wedge\;\rightarrow\;\leftrightarrow\;(\;)\;,\;\equiv\;\mathsf{X\;}\mathit{0}\;\mathit{1\;}...\;\mathit{9}\;\mathbf{0}\;\mathbf{1}\ ...\;\mathbf{9}\)
adhocprefix(2)adhocsufix \(a:\mathcal{F}\cup\mathcal{R}\rightarrow\mathbf{N}\) es una función que a cada \(p\in\mathcal{F}\cup\mathcal{R}\) le asocia un número natural \(a(p)\), llamado la aridad de \(p\).
adhocprefix(3)adhocsufix Ninguna palabra de \(\mathcal{C}\) (resp. \(\mathcal{F}\), \(\mathcal{R}\)) es subpalabra propia de otra palabra de \(\mathcal{C}\) (resp. \(\mathcal{F}\), \(\mathcal{R}\)).
Nótese que los elementos de \(\mathcal{C}\), \(\mathcal{F}\) y \(\mathcal{R}\) pueden ser palabras y no solo símbolos como en los casos de los tipos de estructuras conocidas. Mas adelante cuando definamos las fórmulas de tipo \(\tau\) se entenderán las restricciones puestas en (1)(c) y en (3).
Algunos ejemplos de tipos:
adhocprefix(E1)adhocsufix \((\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\). (Nótese que podemos tomar \(\Sigma_{1}=\emptyset\), \(\Sigma_{2}=\emptyset\) y \(\Sigma_{3}=\{\leq\}\) los cuales son alfabetos que cumplen (a), (b) y (c) de (1) de la definición de tipo).
adhocprefix(E2)adhocsufix \((\{0,1\},\{\mathsf{s},\mathsf{i},c\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2),(c,1)\})\). (Nótese que podemos tomar \(\Sigma_{1}=\{0,1\}\), \(\Sigma_{2}=\{\mathsf{s},\mathsf{i},c\}\) y \(\Sigma_{3}=\emptyset\) los cuales son alfabetos que cumplen (a), (b) y (c) de (1) de la definición de tipo).
adhocprefix(E3)adhocsufix \((\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},a)\), con \(a:\{\mathrm{MAS},\mathrm{P},\mathrm{Her}\}\rightarrow\mathbf{N}\) dada por \(a(\mathrm{MAS})=4\), \(a(\mathrm{P})=1\) y \(a(\mathrm{Her})=3\). (Nótese que podemos tomar \(\Sigma_{1}=\{\mathrm{u},\mathrm{n},\mathrm{o},\mathrm{d},\mathrm{l},\mathrm{i}\}\), \(\Sigma_{2}=\{\mathrm{M},\mathrm{A},\mathrm{S},\mathrm{P}\}\) y \(\Sigma_{3}=\{\mathrm{H},\mathrm{e},\mathrm{r}\}\) los cuales son alfabetos que cumplen (a), (b) y (c) de (1) de la definición de tipo).
adhocprefix(E4)adhocsufix \((\{0,1\},\{+,\times\},\emptyset,a)\), con \(a:\{+,\times\}\rightarrow\mathbf{N}\) dada por \(a(+)=2\) y \(a(\times)=2\).
adhocprefix(E5)adhocsufix \((\{\square\},\{\clubsuit\clubsuit,\mathrm{Pic}\},\{\vartriangleright,\Vert\},a)\), con \(a:\{\clubsuit\clubsuit,\mathrm{Pic},\vartriangleright,\Vert\}\rightarrow\mathbf{N}\) dada por \(a(\clubsuit\clubsuit)=6\), \(a(\mathrm{Pic})=1\), \(a(\vartriangleright)=4\) y \(a(\Vert)=1\)
adhocprefix(E6)adhocsufix \((\{\mathrm{dod},\mathrm{dood},\mathrm{doood},...\},\{\mathrm{Fu}\},\{\mathrm{He}\},a)\), con \(a:\{\mathrm{Fu},\mathrm{He}\}\rightarrow\mathbf{N}\) dada por \(a(\mathrm{Fu})=1\) y \(a(\mathrm{He})=3\). Nótese que este tipo tiene infinitos nombres de constante.
Al tipo \((\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\) lo llamaremos el tipo de los posets. Al tipo \((\emptyset,\{\mathsf{s},\mathsf{i}\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2)\})\) lo llamaremos el tipo de los reticulados terna. Al tipo \[(\{0,1\},\{\mathsf{s},\mathsf{i}\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2)\})\] lo llamaremos el tipo de los reticulados acotados. Al tipo \[(\{0,1\},\{\mathsf{s},\mathsf{i},c\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2),(c,1)\})\] lo llamaremos el tipo de los reticulados complementados. Al tipo \[(\emptyset,\{\mathsf{s},\mathsf{i}\},\{\leq\},\{(\mathsf{s},2),(\mathsf{i},2),(\leq,2)\})\] lo llamaremos el tipo de los reticulados cuaterna. Al tipo \((\emptyset,\{M\},\emptyset,\{(M,3)\})\) lo llamaremos el tipo de las median algebras. Al tipo \((\emptyset,\emptyset,\{r\},\{(r,2)\})\) lo llamaremos el tipo de los grafos. Al tipo \[(\emptyset,\emptyset,\{r,R\},\{(r,2),(R,1)\})\] lo llamaremos el tipo de los grafos bicoloreados.
A los elementos de \(\mathcal{C}\) (resp. \(\mathcal{F}\), \(\mathcal{R}\)) los llamaremos nombres de constante (resp. nombres de función, nombres de relación) de tipo \(\tau\). Para cada \(n\in\mathbf{N}\), definamos \[\begin{aligned} \mathcal{F}_{n} & =\{f\in\mathcal{F}:a(f)=n\}\\ \mathcal{R}_{n} & =\{r\in\mathcal{R}:a(r)=n\} \end{aligned}\] Observación: No deberíamos confundir el concepto de tipo aquí desarrollado, que esencialmente representa un “tipo de estructuras”, con el “tipo de objeto matemático” dado por la función \(Ti\). Esta función asigna a cada objeto matemático una palabra que describe que tipo de objeto matemático es dentro de un menú bien definido de tipos de objetos matemáticos.
No la usaremos en general en las guías o en este apunte pero si en la tómbola a la siguiente notación. Cuando demos un tipo usaremos supraíndices en las palabras de \(\mathcal{F}\cup\mathcal{R}\) para dar cuanto vale la función \(a\) en cada uno de ellos. Por ejemplo escribiremos \((\{\mathrm{tot}\},\{\mathrm{f}^{1},\mathrm{g}^{5},+^{3}\},\emptyset,a)\) en lugar de \((\{\mathrm{tot}\},\{\mathrm{f},\mathrm{g},+\},\emptyset,\{(\mathrm{f},1),(\mathrm{g},5),(+,3)\})\) o \((\{\mathrm{ce},\mathrm{un}\},\{\mathrm{FU}^{2}\},\{\mathrm{V}^{1}\},a)\) en lugar de \((\{\mathrm{ce},\mathrm{un}\},\{\mathrm{FU}\},\{\mathrm{V}\},\{(\mathrm{FU},2),(\mathrm{V},1)\})\), etc.