Ahora si estamos en condiciones de dar una definicion general de estructura. Daremos una definicion matematica de "Estructura de tipo \(\tau\)". En virtud de nuestras estructuras conocidas uno podria 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 facilmente 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 vacio \(A\) (que se llamara el universo de dicha estructura) junto con una interpretacion de cada uno de los nombres del conjunto \(\{\mathrm{uno},\mathrm{doli},\mathrm{MAS},\mathrm{P},\mathrm{Her}\}\). Esta interpretacion debe asignarle
adhocprefix-adhocsufix a \(\mathrm{uno}\) un elemento de \(A\)
adhocprefix-adhocsufix a \(\mathrm{doli}\) un elemento de \(A\)
adhocprefix-adhocsufix a \(\mathrm{MAS}\) una operacion 4-aria sobre \(A\)
adhocprefix-adhocsufix a \(\mathrm{P}\) una operacion 1-aria sobre \(A\)
adhocprefix-adhocsufix a \(\mathrm{Her}\) una relacion 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 \(\mathrm{uno}\) como el numero \(\pi\)
adhocprefix-adhocsufix \(\mathrm{doli}\) como el numero \(0\)
adhocprefix-adhocsufix \(\mathrm{MAS}\) como la operacion \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & 2x+4y \end{array}\]
adhocprefix-adhocsufix \(\mathrm{P}\) como la operacion \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 5^{x} \end{array}\]
adhocprefix-adhocsufix \(\mathrm{Her}\) como la relacion \[\{(x,y,z)\in\mathbf{R}^{3}:x.y.z=9\}\]
O tambien podemos interpretar
adhocprefix-adhocsufix \(\mathrm{uno}\) como el numero \(100\)
adhocprefix-adhocsufix \(\mathrm{doli}\) como el numero \(1000\)
adhocprefix-adhocsufix \(\mathrm{MAS}\) como la operacion \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & y \end{array}\]
adhocprefix-adhocsufix \(\mathrm{P}\) como la operacion \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 9 \end{array}\]
adhocprefix-adhocsufix \(\mathrm{Her}\) como la relacion \[\{(1,5,9),(0,0,0)\}\]
Por supuesto esto produce dos estructuras de tipo \(\tau\) distintas pero con el mismo universo.
Analogamente, si \(\tau\) es el tipo de los posets, es decir \(\tau=(\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\), una estructura de tipo \(\tau\) consistira de un conjunto no vacio \(A\) (que se llamara el universo de dicha estructura) junto con una interpretacion del simbolo \(\leq\), la cual nos dira que relacion binaria sobre \(A\) denotara \(\leq\). Pero esta relacion binaria puede ser cualquiera por lo cual habra muchas estructuras del tipo de los posets que no se corresponderan con posets. Solo aquellas en las que el simbolo \(\leq\) se interpreta como un orden parcial sobre su universo se corresponderan con los posets.
Ahora si daremos la definicion matematica de estructura de tipo \(\tau\): Una estructura o modelo de tipo \(\tau\) sera un par \(\mathbf{A}=(A,i)\) tal que:
adhocprefix(1)adhocsufix \(A\) es un conjunto no vacio
adhocprefix(2)adhocsufix \(i\) es una funcion 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 operacion \(n\)-aria sobre \(A\), para cada \(f\in\mathcal{F}_{n}\), \(n\geq1\)
adhocprefix(c)adhocsufix \(i(r)\) es una relacion \(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 funcion \(i\) es llamada la funcion interpretacion de \(\mathbf{A}\). Si \(s\in\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\), diremos que \(i(s)\) es la interpretacion del simbolo \(s\) 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 funcion con dominio \(\{\mathrm{uno},\mathrm{doli},\mathrm{MAS},\mathrm{P},\mathrm{Her}\}\) dada por
\(i(\mathrm{uno})=\pi\)
\(i(\mathrm{doli})=0\)
\(i(\mathrm{MAS})\) igual a la operacion \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & 2x+4y \end{array}\]
\(i(\mathrm{P})\) igual a la operacion \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 5^{x} \end{array}\]
\(i(\mathrm{Her})=\{(x,y,z)\in\mathbf{R}^{3}:x.y.z=9\}\)
adhocprefix(E2)adhocsufix Sea \(\tau=(\emptyset,\emptyset,\{\leq\},\{(\leq,2)\})\). Notese que por definicion una estructura de tipo \(\tau\) es un par \((A,i)\) donde \(A\) es un conjunto no vacio y \(i\) es una funcion con dominio \(\{\leq\}\) tal que \(i(\leq)\) es una relacion binaria sobre \(A\). Algunos ejemplos de estructuras de tipo \(\tau\):
\((\{1,2,3\},\{(\leq,\emptyset)\})\)
\((\{1,2,3\},\{(\leq,\{2,3\}\times\{1\})\})\)
\((\{1,\{2\},\emptyset\},\{(\leq,\{(1,\{2\})\})\)
\((\mathbf{N},i)\), con \(i\) dada por \(i(\leq)=\{(1,2),(1000,1),(1,1)\}\)
Notese 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 funcion con dominio igual a \(\{\leq\}\) dada por \[i(\leq)=\{(x,y)\in\mathbf{N}^{2}:x|y\}\] Notese 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 informacion \((\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 biyeccion 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\) (aqui \(\max\) y \(\min\) denotan las operaciones binarias sobre \(\mathbf{N}\), maximo y minimo respectivamente). Notese 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 informacion \((\mathbf{N},i)\) y \((\mathbf{N},\max,\min)\) son la misma cosa. Otras estructuras de tipo \(\tau\) son por ejemplo:
\((\mathbf{R},\{(\mathsf{s},+),(\mathsf{i},+)\})\)
\((\{0,1,2\},\{(\mathsf{s},f),(\mathsf{i},g)\}\) donde \(f:\{0,1,2\}^{2}\rightarrow\{0,1,2\}\) es la funcion constantemente 1 y \(g:\{0,1,2\}^{2}\rightarrow\{0,1,2\}\) es la funcion constantemente 2
Por supuesto, ninguna de las dos puede considerarse un reticulado terna ya que en ambas los simbolos \(\mathsf{s}\) y \(\mathsf{i}\) no se interpretan como las operaciones supremo e infimo provenientes de un orden parcial. Dejamos al lector dar una biyeccion 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\). Notese 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 informacion). 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 funcion 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 biyeccion 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 continuacion daremos algunos ejemplos de conteo de estructuras. Antes un lema general de conteo que nos sera de suma utilidad.
7.1. Se tiene que:
adhocprefix(1)adhocsufix Dados \(A,B\) conjuntos finitos no vacios, 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 cualquiera, 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 facil ver que la siguiente funcion 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\) estan en correspondencia biunivoca con las funciones de \(A\) en \(\{0,1\}\) (por que?) podemos aplicar (1)
Ahora si 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 funcion tal que su dominio es \(\{\leq\}\) y tal que
adhocprefix-adhocsufix \(i(\leq)\) es una relacion 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\}\). Notese 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 estan 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 funcion tal que su dominio es \(\{\mathrm{un},\mathrm{do},\mathrm{MAS},\mathrm{P},\mathrm{Her}\}\) y tal que
\(i(\mathrm{un})\) y \(i(\mathrm{do})\) pertenecen a \(\{1,2,3\}\)
\(i(\mathrm{MAS})\) es una operacion 4-aria sobre \(\{1,2,3\}\)
\(i(\mathrm{P})\) es una operacion 1-aria sobre \(\{1,2,3\}\)
\(i(\mathrm{Her})\) es una relacion 3-aria sobre \(\{1,2,3\}\), es decir es un subconjunto de \(\{1,2,3\}^{3}\)
Notese que hay
3 posibilidades para \(i(\mathrm{un})\)
3 posibilidades para \(i(\mathrm{do})\)
3\(^{(3^{4})}\) posibilidades para \(i(\mathrm{MAS})\) (por (1) del lema anterior con \(A=\{1,2,3\}^{4}\) y \(B=\{1,2,3\}\))
3\(^{3}\) posibilidades para \(i(\mathrm{P})\) (por (1) del lema anterior con \(A=\{1,2,3\}\) y \(B=\{1,2,3\}\))
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.
Notese que la definicion 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. Ademas no es necesario que las palabras de \(\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\) se interpreten en la estructura de tipo \(\tau\) (via la funcion \(i\)) como usualmente se interpretan en matematica. Algunos ejemplos:
adhocprefix-adhocsufix \(\tau=(\{\leq\},\emptyset,\emptyset,\emptyset)\) es un tipo y en las estructuras de tipo \(\tau\) el simbolo \(\leq\) se interpretara como un elemento del universo y no un orden parcial. Por ejemplo \((\{1,2,3\},\{(\leq,2)\})\) es una estructura de tipo \(\tau\).
adhocprefix-adhocsufix \(\tau^{\prime}=(\emptyset,\emptyset,\{\leq\},\{(\leq,3)\})\) es un tipo pero en las estructuras de tipo \(\tau^{\prime}\) el simbolo \(\leq\) se interpreta como una relacion 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 simbolo \(\leq\) no se interpreta como un orden parcial sino como una relacion ternaria ya que en \(\tau^{\prime}\) el simbolo \(\leq\) es un simbolo de relacion de aridad \(3\)
adhocprefix-adhocsufix \(\tau^{\prime\prime}=(\emptyset,\{1\},\emptyset,\{(1,3)\})\) es un tipo y en las estructuras de tipo \(\tau^{\prime\prime}\) el simbolo \(1\) se interpretara como una funcion 3-aria sobre el universo (tener cuidado al leer \((\emptyset,\{1\},\emptyset,\{(1,3)\})\) ya que en esta expresion \(1\) es el "numeral uno" y \(3\) es el numero tres). Por ejemplo si denotamos con \(f\) a la operacion \[\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 definicion de tipo y tambien en la definicion 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 fisonomia de dichos nombres) es clave a la hora de fortalecer la separacion entre sintaxis y semantica, idea fundamental en el desarrollo de la logica.