Abstract vs Natural model - which one do I choose?

Question

I have the problem described below:
Describe the model such that ∀x∀y (A(x,y) → x ≠ y) is false. Does anyone have any hints on how to solve this problem? I know that it is possible to solve this type of problem with an abstract model and a natural model, which one do I chose?

Answer 1

Here's a worked example that spells everything out. Please think about each step with some skepticism.

Try negating the sentence in first order logic and then take a look at it and see if any strategies for producing a model jump out.

$$ \forall x \forall y \mathop. A(x, y) \to x \ne y $$

rewrite in negative normal form

$$ \forall x \forall y \mathop. \lnot A(x, y) \lor x \ne y $$

negates to

$$ \exists c \exists d \mathop. A(c, d) \land c = d $$

We can skolemize (trivially), producing an equisatisfiable theory.

$$ A(c, d) \land c = d $$

So

$$ A(c,d) \;\;\text{and}\;\; c = d $$

So

$$ A(c, c) $$

So, if we pick $\{c\}$ as our domain of discourse and pick $\{(c, c)\}$ as our interpretation of $A$, we now have a model in which $\forall x \forall y \mathop. A(x, y) \to x \ne y $.

In order to check, note that our domain has a single element $c$.

$$ A(c, c) \to c \ne c $$ $$ \top \to \bot $$ $$ \bot $$

Therefore the original sentence is indeed false as desired.