Para cada relación, la frase es verdadera o falsa.
¿Existe una taxonomía de las frases en este sentido? Muchas parecen converger a 0 o 1, ¿hay algunas que convergen a valores intermedios?
Respuesta
¿Demasiados anuncios?
Tu pregunta se responde con la ley del cero uno para la lógica de primer orden en un lenguaje relacional finito. Creo que la mejor referencia para esto es Un modelo de teoría más corto por Hodges (Teorema 6.4.6).
Dejemos que $L$ sea un lenguaje relacional finito, y escriba $\text{Str}_L(X)$ para el conjunto de todos los $L$ -estructuras con conjunto subyacente $X$ . Para un número natural $n$ , dejemos que $[n] = \{0,\dots,n-1\}$ . Entonces, para cualquier $L$ -sentencia $\varphi$ podemos definir la probabilidad asintótica $P(\varphi)$ que $\varphi$ se satisface: $$P(\varphi) = \lim_{n\to\infty} \frac{|\{A\in \text{Str}_L([n])\mid A\models \varphi\}|}{|\text{Str}_L([n])|}.$$ Este es el límite como $n$ va a $\infty$ del porcentaje de $L$ -con un dominio fijo de tamaño $n$ que satisfacen $\varphi$ .
Teorema: Para cualquier $L$ -sentencia $\varphi$ , $P(\varphi) = 0 \text{ or }1$ .
Aún más notable, $P(\varphi) = 1$ si y sólo si $M_L\models \varphi$ , donde $M_L$ es el límite de Fraïssé de la clase de todos los finitos $L$ -(se trata de una estructura particular contablemente infinita $L$ -estructura). Es decir, $P(\varphi) = 1$ si y sólo si $\varphi\in T_L = \text{Th}(M_L)$ .
Ahora podemos dar una axiomatización explícita (computable) para $T_L$ (de nuevo, véase la sección 6.4 de Hodges), y una teoría completa axiomatizable computacionalmente es decidible: existe un algoritmo que determina, para cada $L$ -sentencia $\varphi$ , ya sea $P(\varphi) = 0\text{ or }1$ . La forma más simple de este algoritmo sólo busca pruebas de $\varphi$ y $\lnot \varphi$ a partir de los axiomas de $T_L$ . Un algoritmo de eliminación de cuantificadores es probablemente un poco más eficiente.
Es importante señalar que nada de lo anterior es válido para los lenguajes con símbolos de función.
En los comentarios, escribiste:
Pensaba en las relaciones como una generalización de las funciones, no estoy seguro de si hay alguna diferencia, ya que las afirmaciones sobre ellas pueden reescribirse en la otra forma.
Es cierto que podemos sustituir los símbolos de función por símbolos de relación nombrando sus grafos y reescribir las oraciones de primer orden de forma correspondiente. El problema de esta traducción es que no preserva la cuenta en la definición de $P(\varphi)$ . Es decir, si $L = \{f\}$ , donde $f$ es un símbolo de función binaria, y $L' = \{R\}$ es el lenguaje relacional correspondiente, donde $R$ es un símbolo de relación ternaria, entonces $\text{Str}_{L'}$ también incluye $L'$ -estructuras en las que $R$ no es la gráfica de una función - es mucho más grande que $\text{Str}_{L}$ .
Y si dejamos que $\varphi$ sea la sentencia $\forall x\forall y\exists^! z R(x,y,z)$ afirmando que $R$ es la gráfica de una función binaria $f(x,y) = z$ entonces tendremos $P(\varphi) = 0$ . Es decir, en casi todos los $L'$ -estructuras, $R$ es no la gráfica de una función binaria. Así que se puede pensar en imponer la restricción de que $R$ es la gráfica de una función como condicionante de una medida $0$ conjunto.
Para un ejemplo explícito del fracaso de la ley del cero-uno fuera del contexto relacional, hay que pensar en el ejercicio 8 de la sección 6.4 de Hodges. Sea $L = \{f\}$ , donde $f$ es un símbolo de función unario, y sea $\varphi$ sea la sentencia $\forall x\, f(x)\neq x$ . Entonces $$P(\varphi) = \frac{1}{e}.$$
