¿Tiene el siguiente conjunto de fórmulas un modelo finito?

Question

Así que este es el problema:

¿Las siguientes 3 fórmulas tienen un modelo finito:
1. $\forall x \forall y (p(x,y) \Rightarrow \neg p(y,x))$
2. $\forall x \forall y (p(x,y) \Rightarrow \exists z (p(x,z) \& p(z,y)))$
3. $\exists x \exists y p(x,y)$

Cualquier sugerencia será apreciada.

Answer 1

Sí. El Dígrafo de Paley en $7$ vértices es un modelo finito. Concretamente, el conjunto de vértices de este grafo es $\mathbb{F}_7 = \{0,1,2,3,4,5,6\}$ y establecemos $p(a,b)$ si y sólo si $b-a$ es un cuadrado en $\mathbb{F}_7$ (es decir $b-a = 1$ , $2$ o $4$ mod $7$ ).

Ahora se cumple 1., ya que si $b-a = 1$ , $2$ o $4$ mod $7$ entonces $a-b = 6$ , $5$ o $3$ mod $7$ . Y 3. se cumple (cada par de elementos distintos tiene una arista en un sentido u otro). Para comprobar 2, observe que $1 = 4+4$ , $2 = 1+1$ y $4 = 2+2$ mod $7$ . Así, por ejemplo, el correspondiente a la arista de $0$ a $1$ tenemos aristas $0$ a $4$ y $4$ a $1$ .

---

De forma más abstracta, sus tres frases son ciertas en el torneo aleatorio $R$ El límite de Fraïssé de la clase de todos los torneos finitos (un torneo es un grafo dirigido sin dos bucles propios, de tal manera que para cualquier par de elementos distintos hay exactamente una arista entre ellos, en una u otra dirección). Es bien sabido que la clase de los torneos finitos tiene una ley de cero-uno, y que la teoría asimétrica coincide con $\text{Th}(R)$ y, por tanto, que $\text{Th}(R)$ es pseudofinito (tiene la propiedad de modelo finito). Esto se puede demostrar fácilmente utilizando un argumento probabilístico no constructivo - casi exactamente igual que para la clase de grafos finitos y la teoría del grafo aleatorio (no dirigido). Como la conjunción de sus tres frases es una frase en $\text{Th}(R)$ , tenemos la garantía de que tiene algunos modelo finito.

Ahora bien, también es conocido (¡pero más difícil de demostrar!) que las teorías de los dígrafos de Paley convergen a la teoría del torneo aleatorio. Así que para encontrar un modelo explícito para tus tres frases, sólo tenemos que mirar el grafo de Paley en $q$ vértices, donde $q$ es un primo suficientemente grande que equivale a $3$ mod $4$ . Empecé con $7$ y, por suerte, eso fue suficiente.

Answer 2

Sí, por ejemplo, que $p \ge 4$ sea un número primo congruente con $3$ mod $4$ , elige $M = \Bbb Z/p\Bbb Z$ y $P(x,y) = \exists z \neq 0 (y = x+z^2)$ .

Entonces el axioma $1$ es cierto porque $-1$ no es un mod cuadrado $p$ y el axioma $2$ es cierto porque los círculos tienen $(p+1)$ puntos, lo cual es suficiente ( $> 4$ ) para obtener descomposiciones no triviales.