How to analyse satisfiability in mathematical logic?

Question

I have a course on logic, and I have some exercises in which I need to decide if a formula is satisfiable, unsatisfiable or a tautology. For example:

$\forall x \; \exists y\; r(x, y) \to \exists x \; \forall y \; r(x, y)$

$r$ should be a predicate, and $x, y$ are variables. The thing is in my course material there is no clear answer given for why this is satisfiable. Is there any particular way in which you can approach a problem like this? I don't even know how to start. Thanks in advance!

Answer 1

For proving satisfiability you have to find an interpretation for the symbols in the formula such that the interpreted formula is true.

We can try with the domain $\mathbb N$ of natural numbers and interpret the binary predicate $r$ with the "less-equal" ($\le$) relation.

Thus, the interpreted formula will mean :

$∀x∃y \ (x \le y) \to ∃x∀y (x \le y)$

and we can see that it is true in $\mathbb N$.

---

In general, given a formula $\varphi$ of a first-order language $\mathcal L$, a structure $\mathfrak A$ for the language $\mathcal L$ and a variable assignment function

$s : Var \to |\mathfrak A|$

i.e. a function from the set $Var$ of all variables of the language into the domain (or universe) $|\mathfrak A|$ of $A$, we have that $\mathfrak A$ satisfy $\varphi$ with $s$, in symbols:

$\mathfrak A \vDash \varphi[s]$

if and only if the "translation" of $\varphi$ determined by $\mathfrak A$, where the variable $x$ is translated as $s(x)$ wherever it occurs free, is true.