Ahora sí estamos en condiciones de dar una definición general de estructura. Daremos una definición matemática de "Estructura de tipo \(\tau\)". En virtud de nuestras estructuras conocidas uno podría intentar definir estructura de tipo \(\tau\) como cierta \(n\)-upla pero esto trae problemas ya que en un tipo \(\tau\) los nombres de \(\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\) no tienen por que estar ordenados y aparte puede haber infinitos nombres. De todas maneras la idea es muy similar y nos aproximaremos primero con ejemplos para entender mas fácilmente el concepto.
Sea \(\tau\) el tipo \[(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},\{(\mathrm{MAS},4),(\mathrm{P},1),(\mathrm{Her},3)\})\] Intuitivamente hablando, una estructura de tipo \(\tau\) consiste en un conjunto no vacío \(A\) (que se llamara el universo de dicha estructura) junto con una interpretación de cada uno de los nombres del conjunto \(\{\mathrm{uno},\mathrm{doli},\mathrm{MAS},\mathrm{P},\mathrm{Her}\}\). Esta interpretación debe asignarle
adhocprefix-adhocsufix a la palabra \(\mathrm{uno}\) un elemento de \(A\)
adhocprefix-adhocsufix a la palabra \(\mathrm{doli}\) un elemento de \(A\)
adhocprefix-adhocsufix a la palabra \(\mathrm{MAS}\) una operación 4-aria sobre \(A\)
adhocprefix-adhocsufix a la palabra \(\mathrm{P}\) una operación 1-aria sobre \(A\)
adhocprefix-adhocsufix a la palabra \(\mathrm{Her}\) una relación 3-aria sobre \(A\)
Lo que debe quedar claro es que estos elementos, operaciones y relaciones pueden ser cualesquiera, es decir no deben cumplir nada en especial. Por ejemplo si tomamos \(\mathbf{R}\) como universo podemos interpretar
adhocprefix-adhocsufix la palabra \(\mathrm{uno}\) como el número \(\pi\)
adhocprefix-adhocsufix la palabra \(\mathrm{doli}\) como el número \(0\)
adhocprefix-adhocsufix la palabra \(\mathrm{MAS}\) como la operación \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & 2x+4y \end{array}\]
adhocprefix-adhocsufix la palabra \(\mathrm{P}\) como la operación \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 5^{x} \end{array}\]
adhocprefix-adhocsufix la palabra \(\mathrm{Her}\) como la relación \[\{(x,y,z)\in\mathbf{R}^{3}:x.y.z=9\}\]
O también podemos interpretar
adhocprefix-adhocsufix la palabra \(\mathrm{uno}\) como el número \(100\)
adhocprefix-adhocsufix la palabra \(\mathrm{doli}\) como el número \(1000\)
adhocprefix-adhocsufix la palabra \(\mathrm{MAS}\) como la operación \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & y \end{array}\]
adhocprefix-adhocsufix la palabra \(\mathrm{P}\) como la operación \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 9 \end{array}\]
adhocprefix-adhocsufix la palabra \(\mathrm{Her}\) como la relación \[\{(1,5,9),(0,0,0)\}\]
Por supuesto esto produce dos estructuras de tipo \(\tau\) distintas pero con el mismo universo.
Análogamente, si \(\tau\) es el tipo de los posets, es decir \(\tau=(\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\), una estructura de tipo \(\tau\) consistirá de un conjunto no vacío \(A\) (que se llamara el universo de dicha estructura) junto con una interpretación del símbolo \(\leq\), la cual nos dirá que relación binaria sobre \(A\) denotará \(\leq\). Pero esta relación binaria puede ser cualquiera por lo cual habrá muchas estructuras del tipo de los posets que no se corresponderán con posets. Solo aquellas en las que el símbolo \(\leq\) se interpreta como un orden parcial sobre su universo se corresponderán con los posets.
Ahora sí daremos la definición matemática de estructura de tipo \(\tau\): Una estructura o modelo de tipo \(\tau\) será un par \(\mathbf{A}=(A,i)\) tal que:
adhocprefix(1)adhocsufix \(A\) es un conjunto no vacío
adhocprefix(2)adhocsufix \(i\) es una función con dominio \(\mathcal{C}\cup\mathcal{F}\cup\mathcal{R},\) tal que:
adhocprefix(a)adhocsufix \(i(c)\) es un elemento de \(A\), para cada \(c\in\mathcal{C}\)
adhocprefix(b)adhocsufix \(i(f)\) es una operación \(n\)-aria sobre \(A\), para cada \(f\in\mathcal{F}_{n}\), \(n\geq1\)
adhocprefix(c)adhocsufix \(i(r)\) es una relación \(n\)-aria sobre \(A\), para cada \(r\in\mathcal{R}_{n}\), \(n\geq1\)
Si \(\mathbf{A}=(A,i)\) es una estructura de tipo \(\tau\), el conjunto \(A\) es llamado el universo de \(\mathbf{A}\) y la función \(i\) es llamada la función interpretación de \(\mathbf{A}\). Si \(p\in\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\), diremos que \(i(p)\) es la interpretación de \(p\) en \(\mathbf{A}\). Algunos ejemplos:
adhocprefix(E1)adhocsufix Si \(\tau\) es el tipo \[(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},\{(\mathrm{MAS},4),(\mathrm{P},1),(\mathrm{Her},3)\})\] entonces \((\mathbf{R},i)\) es una estructura de tipo \(\tau\), si definimos \(i\) igual a la función con dominio \(\{\mathrm{uno},\mathrm{doli},\mathrm{MAS},\mathrm{P},\mathrm{Her}\}\) dada por
adhocprefix-adhocsufix \(i(\mathrm{uno})=\pi\)
adhocprefix-adhocsufix \(i(\mathrm{doli})=0\)
adhocprefix-adhocsufix \(i(\mathrm{MAS})\) igual a la operación \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & 2x+4y \end{array}\]
adhocprefix-adhocsufix \(i(\mathrm{P})\) igual a la operación \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 5^{x} \end{array}\]
adhocprefix-adhocsufix \(i(\mathrm{Her})=\{(x,y,z)\in\mathbf{R}^{3}:x.y.z=9\}\)
adhocprefix(E2)adhocsufix Sea \(\tau=(\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\). Nótese que por definición una estructura de tipo \(\tau\) es un par \((A,i)\) donde \(A\) es un conjunto no vacío y \(i\) es una función con dominio \(\{\leq\}\) tal que \(i(\leq)\) es una relación binaria sobre \(A\). Algunos ejemplos de estructuras de tipo \(\tau\):
adhocprefix-adhocsufix \((\{1,2,3\},\{(\leq,\emptyset)\})\)
adhocprefix-adhocsufix \((\{1,2,3\},\{(\leq,\{2,3\}\times\{1\})\})\)
adhocprefix-adhocsufix \((\{1,\{2\},\emptyset\},\{(\leq,\{(1,\{2\})\})\)
adhocprefix-adhocsufix \((\mathbf{N},i)\), con \(i\) dada por \(i(\leq)=\{(1,2),(1000,1),(1,1)\}\)
Nótese que aunque \(\tau\) es llamado el tipo de los posets, ninguna de las estructuras anteriores tiene mucho que ver con un poset. Consideremos ahora la estructura \((\mathbf{N},i)\), donde \(i\) es la función con dominio igual a \(\{\leq\}\) dada por \[i(\leq)=\{(x,y)\in\mathbf{N}^{2}:x|y\}\] Nótese que estrictamente hablando \((\mathbf{N},i)\) no es un poset ya que \(i\) no es un orden parcial sobre \(\mathbf{N}\) pero es claro que a nivel de información \((\mathbf{N},i)\) y \((\mathbf{N},|)\) son la misma cosa. O sea que aquellas estructuras de tipo \(\tau\) en las cuales \(\leq\) se interpreta como un orden parcial sobre el universo de la estructura son "esencialmente posets". Dejamos al lector dar una biyección entre el conjunto formado por todos los posets y un subconjunto del conjunto de todas las estructuras de tipo \(\tau\)
adhocprefix(E3)adhocsufix Sea \(\tau\) el tipo de los reticulados terna, es decir \(\tau=(\emptyset,\{\mathsf{s},\mathsf{i}\},\emptyset,\{(\mathsf{s},2),(\mathsf{i},2)\})\). Entonces \((\mathbf{N},i)\), donde \(i=\{(\mathsf{s},\max),(\mathsf{i},\min)\}\), es una estructura de tipo \(\tau\) (aquí \(\max\) y \(\min\) denotan las operaciones binarias sobre \(\mathbf{N}\), máximo y mínimo respectivamente). Nótese que estrictamente hablando \((\mathbf{N},i)\) no es un reticulado terna ya que es una \(2\)-upla y los reticulados terna son \(3\)-uplas. Pero es claro que a nivel de información \((\mathbf{N},i)\) y \((\mathbf{N},\max,\min)\) son la misma cosa. Otras estructuras de tipo \(\tau\) son por ejemplo:
adhocprefix-adhocsufix \((\mathbf{R},\{(\mathsf{s},+),(\mathsf{i},+)\})\)
adhocprefix-adhocsufix \((\{0,1,2\},\{(\mathsf{s},f),(\mathsf{i},g)\}\) donde \(f:\{0,1,2\}^{2}\rightarrow\{0,1,2\}\) es la función constantemente 1 y \(g:\{0,1,2\}^{2}\rightarrow\{0,1,2\}\) es la función constantemente 2
Por supuesto, ninguna de las dos puede considerarse un reticulado terna ya que en ambas los símbolos \(\mathsf{s}\) y \(\mathsf{i}\) no se interpretan como las operaciones supremo e ínfimo provenientes de un orden parcial. Dejamos al lector dar una biyección entre el conjunto formado por todos los reticulados terna y un subconjunto del conjunto de todas las estructuras de tipo \(\tau\)
adhocprefix(E4)adhocsufix Sea \(\tau\) el tipo de los grafos bicoloreados, es decir \(\tau=(\emptyset,\emptyset,\{r,R\},\{(r,2),(R,1)\})\). Entonces \((\{1,2\},i)\), con \(i=\{(r,\{(1,2),(2,1)\}),(R,\{1\})\}\), es una estructura de tipo \(\tau\). Nótese que \[(\{1,2\},i(r),i(R))=(\{1,2\},\{(1,2),(2,1)\},\{1\})\] es un grafo bicoloreado el cual esencialmente es lo mismo que la estructura \((\{1,2\},i)\) (a nivel de información). De todas maneras estrictamente hablando \((\{1,2\},i)\) no es un grafo bicoloreado. Otra estructura de tipo \(\tau\) la cual es "esencialmente" un grafo bicoloreado es el par \((\omega,i)\), donde \(i\) es la función con dominio \(\{r,R\}\) dada por \[\begin{aligned} i(r) & =\{(x,x+1):x\in\omega\}\cup\{(x+1,x):x\in\omega\}\\ i(R) & =\{x\in\omega:x\text{ es par}\} \end{aligned}\] Tal como en los otros ejemplos vistos, hay estructuras de tipo \(\tau\) las cuales no pueden considerarse grafos bicoloreados. Por ejemplo, la estructura \((\mathbf{N},\{(r,\{(1,2)\}),(R,\{3\})\})\). Dejamos al lector dar una biyección entre el conjunto formado por todos los grafos bicoloreados y un subconjunto del conjunto de todas las estructuras de tipo \(\tau\).
Para seguir entendiendo la amplitud del concepto de estructura, a continuación daremos algunos ejemplos de conteo de estructuras. Antes un lema general de conteo que nos será de suma utilidad.
7.1. Se tiene que:
adhocprefix(1)adhocsufix Dados \(A,B\) conjuntos finitos no vacíos, hay \(\left\vert B\right\vert ^{\left\vert A\right\vert }\) funciones tales que su dominio es \(A\) y su imagen esta contenida en \(B\)
adhocprefix(2)adhocsufix Si \(A\) es un conjunto finito, entonces hay \(2^{\left\vert A\right\vert }\) subconjuntos de \(A\)
Proof. (1) Supongamos \(A=\{a_{1},...,a_{n}\}\), con \(n=\left\vert A\right\vert\). Sea \(Fu=\{f:D_{f}=A\) y \(I_{f}\subseteq B\}\). Es fácil ver que la siguiente función es biyectiva \[\begin{array}{rcl} Fu & \rightarrow & B^{n}\\ f & \rightarrow & (f(a_{1}),...,f(a_{n})) \end{array}\]
(2) Ya que los subconjuntos de \(A\) están en correspondencia biunívoca con las funciones de \(A\) en \(\{0,1\}\) (por que?) podemos aplicar (1).
Ahora sí los ejemplos. Sea \[\tau=(\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\] Nos interesa saber cuantas estructuras de tipo \(\tau\) hay que tengan al conjunto \(\{1,2,3\}\) como universo. Una estructura de tipo \(\tau\) con universo \(\{1,2,3\}\) es un par \((\{1,2,3\},i)\) donde \(i\) es una función tal que su dominio es \(\{\leq\}\) y tal que
adhocprefix-adhocsufix \(i(\leq)\) es una relación 2-aria sobre \(\{1,2,3\}\), es decir es un subconjunto de \(\{1,2,3\}^{2}\)
O sea que una estructura de tipo \(\tau\) con universo \(\{1,2,3\}\) es un par de la forma \[(\{1,2,3\},\{(\leq,S)\})\] donde \(S\) es cualquier subconjunto de \(\{1,2,3\}^{2}\). Ya que, por el lema anterior, hay \(2^{9}\) subconjuntos del conjunto \(\{1,2,3\}^{2}\), tenemos que hay exactamente \(2^{9}\) estructuras de tipo \(\tau\) cuyo universo es \(\{1,2,3\}\). Nótese que, estrictamente hablando, ninguna de estas estructuras es un poset. Sin embargo aquellas en las cuales \(S\) es un orden parcial sobre \(\{1,2,3\}\) pueden considerarse como posets ya que esencialmente están determinadas por un orden parcial.
Otro ejemplo, tomemos \[\tau=(\{\mathrm{un},\mathrm{do}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},\{(\mathrm{MAS},4),(\mathrm{P},1),(\mathrm{Her},3)\}\] Nos interesa saber cuantas estructuras de tipo \(\tau\) hay que tengan al conjunto \(\{1,2,3\}\) como universo. Una estructura de tipo \(\tau\) con universo \(\{1,2,3\}\) es un par \((\{1,2,3\},i)\) donde \(i\) es una función tal que su dominio es \(\{\mathrm{un},\mathrm{do},\mathrm{MAS},\mathrm{P},\mathrm{Her}\}\) y tal que
adhocprefix-adhocsufix \(i(\mathrm{un})\) y \(i(\mathrm{do})\) pertenecen a \(\{1,2,3\}\)
adhocprefix-adhocsufix \(i(\mathrm{MAS})\) es una operación 4-aria sobre \(\{1,2,3\}\)
adhocprefix-adhocsufix \(i(\mathrm{P})\) es una operación 1-aria sobre \(\{1,2,3\}\)
adhocprefix-adhocsufix \(i(\mathrm{Her})\) es una relación 3-aria sobre \(\{1,2,3\}\), es decir es un subconjunto de \(\{1,2,3\}^{3}\)
Nótese que hay
adhocprefix-adhocsufix 3 posibilidades para \(i(\mathrm{un})\)
adhocprefix-adhocsufix 3 posibilidades para \(i(\mathrm{do})\)
adhocprefix-adhocsufix 3\(^{(3^{4})}\) posibilidades para \(i(\mathrm{MAS})\) (por (1) del lema anterior con \(A=\{1,2,3\}^{4}\) y \(B=\{1,2,3\}\))
adhocprefix-adhocsufix 3\(^{3}\) posibilidades para \(i(\mathrm{P})\) (por (1) del lema anterior con \(A=\{1,2,3\}\) y \(B=\{1,2,3\}\))
adhocprefix-adhocsufix 2\(^{(3^{3})}\) posibilidades para \(i(\mathrm{Her})\) (por (2) del lema anterior con \(A=\{1,2,3\}^{3}\))
O sea que hay exactamente \(3.3.3^{(3^{4})}.3^{3}.2^{(3^{3})}\) estructuras de tipo \(\tau\) que tienen al conjunto \(\{1,2,3\}\) como universo.
Nótese que la definición de tipo es muy libre en lo que respecta a que palabras componen los conjuntos \(\mathcal{C}\), \(\mathcal{F}\) y \(\mathcal{R}\), es decir salvo por ciertas restricciones leves, ellas pueden ser cualquier palabra. Además no es necesario que las palabras de \(\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\) se interpreten en la estructura de tipo \(\tau\) (vía la función \(i\)) como usualmente se interpretan en matemática. Algunos ejemplos:
adhocprefix(E1)adhocsufix \(\tau=(\{\leq\},\emptyset,\emptyset,\emptyset)\) es un tipo y en las estructuras de tipo \(\tau\) el símbolo \(\leq\) se interpretara como un elemento del universo y no como un orden parcial. Por ejemplo \((\{1,2,3\},\{(\leq,2)\})\) es una estructura de tipo \(\tau\).
adhocprefix(E2)adhocsufix \(\tau^{\prime}=(\emptyset,\emptyset,\{\leq\},\{(\leq,3)\})\) es un tipo pero en las estructuras de tipo \(\tau^{\prime}\) el símbolo \(\leq\) se interpreta como una relación 3-aria sobre el universo. Por ejemplo \((\mathbf{N},i)\), con \(i\) dada por \(i(\leq)=\{(x,y,z)\in\mathbf{N}^{3}:x=y=z\}\), es una estructura de tipo \(\tau^{\prime}\). En esta estructura el símbolo \(\leq\) no se interpreta como un orden parcial sino como una relación ternaria ya que en \(\tau^{\prime}\) el símbolo \(\leq\) es un nombre de relación de aridad \(3\)
adhocprefix(E3)adhocsufix \(\tau^{\prime\prime}=(\emptyset,\{1\},\emptyset,\{(1,3)\})\) es un tipo y en las estructuras de tipo \(\tau^{\prime\prime}\) el símbolo \(1\) se interpretara como una función 3-aria sobre el universo (tener cuidado al leer \((\emptyset,\{1\},\emptyset,\{(1,3)\})\) ya que en esta expresión \(1\) es el numeral uno y \(3\) es el número tres). Por ejemplo si denotamos con \(f\) a la operación \[\begin{array}{rcl} \mathbf{Z}^{3} & \rightarrow & \mathbf{Z}\\ (x,y,z) & \rightarrow & x+y+z \end{array}\] entonces \((\mathbf{Z},i)\), con \(i\) dada por \(i(1)=f\), es una estructura de tipo \(\tau^{\prime\prime}\)
Esta libertad en la definición de tipo y también en la definición de estructura de tipo \(\tau\) (i.e. las estructuras interpretan a los nombres de \(\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\) con total independencia de la fisonomía de dichos nombres) es clave a la hora de fortalecer la separación entre sintaxis y semántica, idea fundamental en el desarrollo de la lógica.