7
$\begingroup$

So this is the problem:

Do the following 3 formulas have a finite model:
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)$

Any suggestions will be appreciated!

$\endgroup$

2 Answers 2

8
$\begingroup$

Yes. The Paley digraph on $7$ vertices is a finite model. Concretely, the set of vertices of this graph is $\mathbb{F}_7 = \{0,1,2,3,4,5,6\}$, and we set $p(a,b)$ if and only if $b-a$ is a square in $\mathbb{F}_7$ (i.e. $b-a = 1$, $2$, or $4$ mod $7$).

Now 1. is satisfied, since if $b-a = 1$, $2$, or $4$ mod $7$, then $a-b = 6$, $5$, or $3$ mod $7$. And 3. is satisfied (every pair of distinct elements has an edge in one direction or the other). To check 2, note that $1 = 4+4$, $2 = 1+1$, and $4 = 2+2$ mod $7$. So, for example, corresponding to the edge from $0$ to $1$, we have edges $0$ to $4$ and $4$ to $1$.


More abstractly, your three sentences are true in the random tournament $R$, the Fraïssé limit of the class of all finite tournaments (a tournament is a directed graph with no two self-loops such that for any pair of distinct elements, there is exactly one edge between them - in one direction or the other). It is well-known that the class of finite tournaments has a zero-one law, and that the asympotic theory agrees with $\text{Th}(R)$, and hence that $\text{Th}(R)$ is pseudofinite (has the finite model property). This can be easily proven using a nonconstructive probabilistic argument - almost exactly the same as for the class of finite graphs and the theory of the random (undirected) graph. Since the conjunction of your three sentences is a sentence in $\text{Th}(R)$, we are guaranteed that it has some finite model.

Now it's also well-known (but harder to prove!) that the theories of the Paley digraphs converge to the theory of the random tournament. So to find an explicit model for your three sentences, we just have to look at the Paley graph on $q$ vertices, where $q$ is a large enough prime which is equivalent to $3$ mod $4$. I started with $7$, and luckily that was sufficient!

$\endgroup$
1
  • 1
    $\begingroup$ This is absolutely beautiful. +1! $\endgroup$ Commented Jun 15, 2016 at 19:09
3
$\begingroup$

Yes, for example, let $p \ge 4$ be a prime number congruent to $3$ mod $4$, pick $M = \Bbb Z/p\Bbb Z$ and $P(x,y) = \exists z \neq 0 (y = x+z^2)$.

Then axiom $1$ is true because $-1$ is not a square mod $p$ and axiom $2$ is true because circles have $(p+1)$ points, which is enough ($> 4$) to get nontrivial decompositions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .