# Choosing suitable structures

I was given a problem and was wondering if there is some way to solve this rather than the method I have been using so far (unsuccessfully) which was to guess for ways it could work. Is there a better way to solve this type of problem?

Give a suitable structure such that a1 is false, a2 and a3 are true

(a.1) ∀x∀y∀z((P(x,y) ∧ P(y,z)) → P(x,z))

(a.2) ∀x∀y((P(x,y) ∧ P(y,x)) → x = y)

(a.3) ∀x∀y(P(a,y) → P(x,b))

I've tried defining P to be P = {(m,n) | m != n} or 2m = n but the first one always messes it up. How should I be solving this problem other than blind guessing?

• What are $a$ and $b$?
– bof
Jul 13 '17 at 3:55
• They're constants that must exist in the chosen domain Jul 13 '17 at 3:56
• How about taking the domain $\{1,2,3,4\}$ with $P=\{(1,2),(2,3)\}$ and $a=b=4?$
– bof
Jul 13 '17 at 3:58
• Why does that make a.1 false? Can't P(x,z) be assigned either of those two and still be true? Jul 13 '17 at 4:00
• If we assign $x=1$ and $y=2$ and $z=3$ then what? Is $P(x,y$ true? Is $P(y,z)$ true? Is $P(x,z)$ false?
– bof
Jul 13 '17 at 4:07

Well, a systematic way to attack such a problem would be to look at tableaux. But you don't really need to learn the entire proof system. At heart, the idea is to first consider the formulas where your choices are constrained. For example, here we have three universal statements: $\forall x \forall y \forall z ((Pxy \land Pyz) \to Pxz)$, $\forall x \forall y ((Pxy \land Pyx) \to x=y)$, and $\forall x \forall y (Pay \to Pxb)$. The first we want to be false and the other two we want to be true.
The only way for a universal statement to be false is for there to be some element in the domain which makes it false. That is, we know that however our structure turns out, it has to have elements $u, v, w$ such that $(Puv \land Pvw) \to Puw$ is false. So we start to build the structure by putting such elements in the domain. We need $u, v, w$ with $u$ $P$-related to $v$, $v$ $P$-related to $w$, and $u$ not $P$-related to $w$. As long as these elements are there, the first universal statement will be false.
Then we consider the formulas which don't really constrain our choices much, the other two universals. The way to go about this is just to see if we have to add anything to the structure in order to satisfy these statements. Since they're both conditionals, we're in luck: we can satisfy them both vacuously. We just need our structure to have $Pxy \land Pyx$ false everywhere and $Pay$ false everywhere.
But hey, check it out, if we just add some elements named $a$ and $b$ to the domain and no more $P$-relations to the structure, we're done.
So our structure (call it $\mathbf{A}$) should have domain $A = \{u, v, w, a, b\}$ and the extension of $P$ should be $P^A = \{(u,v), (v,w)\}$. (And after completing this construction, you'll notice that there's nothing special about what the element $b$ is, you can take it to be $a, u, v$, or $w$, which should correspond to the solution(s) given in the comments.)