Logic Question (predicate logic)

Question

Consider the formula F =∀x∃y∃z (¬(x=y)∧¬P(x,y)∧¬(x=z)∧P(x,z))

Let n ≥ 3 be a natural number. Find a universe U with n elements (i.e., |U | = n) and a predicate P : $U^{2}$ → {0,1} such that F is true. The Universe and the predicate P have to be defined in terms of n, but how would a universe and a predicate look like that satisfy the above formula?

Answer 1

I would consider first with the set of integers from $0$ to $n-1$. Then to get a $P$, we can start by using the subtraction, modulo $n$. We then just need to assign to the result of the subtraction the $0$ or $1$ values. There are many ways to do that. Here are two examples:

1. $$P=\begin{cases}1,(x-y)\mod n=1\\0,(x-y) \mod n\ne 1\end{cases}$$
2. $$P=\begin{cases}1,(x-y)\mod n=2k, k\in\mathbb N\\0,(x-y) \mod n=2k+ 1, k\in\mathbb N\end{cases}$$

In these examples, the subtraction modulo $n$ takes all values from $0$ to $n-1$. In your case $n\ge 3$ means that you have at least $0,1,2$ as possible values. You get $0$ in the subtraction when $x=y$. But you get at least two different values for any $x$, one for $(x-y)\mod n=1$, one for $2$. So you just need to assign them different truth values in defining the predicate $P$.