Set consists of the following formulas.
- ∃xA(x) ∧ ∃xB(x)
- ¬∃x( A(x) ∧ B(x) )
- ∀x¬R(x,x)
- ∀x∀y( R(x,y) → R(y,x) )
- ∀x( A(x) → ∃y( B(y)∧ R(x,y) ) )
- ∀x( B(x) → ∃y( B(y)∧ R(x,y) ) )
The question is asking if the set of formulas in the language of predicate calculus is satisfiable.
One solution for interpretation has been provided so that the set is satisfiable.
However, I am wondering if there is any tip or guideline for this type of problem. From the set, I can see the symmetric property of $R$.
$$(∀x∀y( R(x,y) → R(y,x) ))$$
Other than that, it is like finding a needle in a haystack.
Any help would be appreciated. Thank you.
Two sets $A$, $B$ are non-empty. Let's start with $A(a), B(b)$ (though possibly $a=b$).
The sets are disjoint: so the start is good, and we must add $\neg A(b), \neg B(a)$ (and now we're certain $a\neq b$) .
$R$ is irreflexive.
$R$ is symmetric, as you noted.
We have $A(a), B(b)$ so let's claim that $R(b,a)$, Symmetry says $R(a,b)$ also
We have $B(b)$ but we can't say $R(b,b)$ because $R$ is irreflexive. Also we've already affirmed $\neg B(a)$. So we must add a new distinct literal, $c$, to our universe, and $B(c), R(b,c)$ to our facts, and of course $R(c,b), \neg A(c)$ by previous rules. Now check that $B(c)\to\exists y~(B(y)\wedge R(c,y))$ and we're done: yes $B(b), R(c,b)$ have already bee added.
So our universe is $\{a,b,c\}$ with $A=\{a\}$, $B=\{b,c\}$, $R=\{(a,b),(b,a),(b,c),(c,b)\}$
Another approach; top-down; start as wide as possible and narrow down. $A$, $B$ are non-empty and disjoint, such as odd and even (natural)numbers. $R$ is irreflexive and symmetric, such as the $\neq$ comparison --everything is related to everything but itself. For every odd number, there exists an even number which it does not equal $\checkmark$ so we don't have to change a thing. For every even number, there exists an even number which it does not equal $\checkmark$ so we don't have to change a thing. That'll do.