Predicate logic models understanding relations

Question

I am having issues understanding the answer to the following question:

Describe a model for the following formula:

$$∀x \big(∃y(P (x, y)∨ P (y, x))∧ (¬P (x, x)∧ (Q(x)→∃y P (x, y))) \big)$$

Answer:

Since there are no function symbols or constants we only need to define the domain, $P$ and $Q$.

Let $J$ be the interpretation such that the $dom(J) = \mathbb{N}$ (where $\mathbb{N}$ is the set of natural numbers) and

$$P^J= \{(x, y) ∈ \mathbb{N} \times \mathbb{N} \mid x \neq y\}$$

and

$$Q^J= \{x ∈ \mathbb{N} \mid x < 0\}.$$

How do I come to the conclusion that $P$ and $Q$ are these relations? Am I supposed to just see this from the formula or is there anyway to go about for getting a correct answer?

Answer 1

You can go through the mathematical definitions of the formal semantics of the logical operators involved, and thus (rather painstakingly) work out that with your interpretation, the sentence will indeed evaluate to True.

Or, you can just do this a little more informally:

Is it true that for any $x$, we have $P(x,y)$ or $P(y,x)$ for some $y$? Clearly yes: you can just pick $x+1$ for $y$

Is it true that $\neg P(x,x)$ for any $x$? Given your interpretation for $P$, clearly yes.

And is it true that $Q(x) \to ...$? Given your clever pick of $Q$ to be empty, clearly yes.

And that's it to convince yourself and others that you interpretation is indeed a model for the sentence. ... and every normal human being working in this area will be perfectly satisfied.

But: if your instructor is looking for a hard-nosed formal semantics-based mathematical proof, then you'll have to painstakingly go through all the little steps using however that formal semantics is precisely defined (and, unfortunately, there can be slight differences in how different texts define that semantics, so I can't really give you a precise proof ... nor have the appetite to go through that :P )

Answer 2

So, $P$ and $Q$ might not be these relations, this is just one possible model.

For example, we have another slightly different interpretation $J'$ with the same domain. $P^{J'}=P^J$ and $Q^{J'} = \mathbb{N}$.

If you're after an intuition, the signature $P \subset D \times D$ and $Q \subset D $ strongly suggests a graph to me. If you have no function symbols, single predicate of arity 2, and no predicates of arity greater than 2, then the language of graph theory is often a good way to talk about models.

We can rewrite that one condition equivalently as three. These three conditions have natural interpretations in the graph setting.

$ \forall x (\exists y P(x, y) \lor P(y, x)) $ says every node in our graph has positive in-degree or positive out-degree or both. There are no totally isolated points.

$ \forall x (\lnot P(x, x)) $ says that we do not have any self-loops.

$\forall x (Q(x) \to \exists x P(x, y))$ says that $Q$ picks out a subset of the nodes with positive out-degree.

Answer 3

You just have to check that the formula

$$ ∀x \big(∃y(P (x, y)∨ P (y, x))∧ (¬P (x, x)∧ (Q(x)→∃y P (x, y))) \big)$$

holds when $P$ and $Q$ are interpreted as $P^J$ and $Q^J$ respectively, and the domain of the quantifiers is $\mathbb{N}$. Concretely, it amounts to check that the formula below is true.

\begin{equation} \begin{split} ∀x \in \mathbb{N} \ \big(&∃y \in \mathbb{N} ((x, y) \in P^J ∨ (y, x) \in P^J) \\ &∧ \ ((x, x) \neq P^J ∧ (x \in Q^J →∃y\in \mathbb{N} (x, y) \in P^J)) \big) \end{split} \end{equation}

Given the interpretations $P^J= \{(x, y) ∈ \mathbb{N} \times \mathbb{N} \mid x \neq y\}$ and $Q^J= \{x ∈ \mathbb{N} \mid x < 0\} = \emptyset$, the formula above can be rewritten as

\begin{equation} \begin{split} ∀x \in \mathbb{N} \ \big(&∃y \in \mathbb{N} (x \neq y ∨ y \neq x) &∧ \ (x =x ∧ (x \in \emptyset →∃y\in \mathbb{N} \, x \neq y)) \big) \end{split} \end{equation}

which is clearly true. Indeed, given $x \in \mathbb{N}$, take $y = x+1 \in \mathbb{N}$ and you have $x \neq y$; moreover, clearly $x = x$, and $(x \in \emptyset →∃y\in \mathbb{N} \, x \neq y)$ is vacuously true.

Note that there are many other models of the original formula, that is, many other interpretations of that formula make it true. For instance, the interpretation $I$ where $dom(I) = \{0,1\}$ with $P^I = \{(0,1)\}$ and $Q^I= \{0\}$.