A relation on a structure defined as a set? Help with an example from Dalen's Logic and structure

Question

I'm not able to understand the folowing example from Dirk van Dalen's logic and structure. What is confusing me is the relation defined on the structure and the predicate $P $.

We have a set $A=\{0,1 \} $ and a relation defined on $A $ as the set with two elements $\{\langle 0.1 \rangle , \langle 1,0 \rangle \}$. I'm not sure what to make of this relation (being used to relations such as $<, = $ etc on say $\mathbb N $) . (Maybe the elements should just be thougt of as saying, $0 $ is in relation with $1 $ and $1 $ is in relation with $0 $.)

Then I'm not sure of how the predicate $\phi := P(x,y) $ is defined. (But he speaks of $\langle 0,1 \rangle $ being an element of $P $ and thus it should be thought of as a set?)

Answer 1

The structure [see page 54] $\mathcal{A}$ is "made of" :

• a domain $A=\{ 0,1 \}$

• a (binary) relation $P^A = \{ ⟨0,1⟩,⟨1,0⟩ \}$ on $A$ as interpretation for the predicate symbol $P$. Thus $P^A \subseteq A \times A$. [Note : $⟨0,1⟩$ and $⟨1,0⟩$ are the couples defining the relation : you can think at $P^A$ as : "___ is brother of :::"].

See page 64 for the semantics.

The structure is of type $⟨2;-;0⟩$ because [see page 55] we have only one predicate symbol with arity $2$ (thus : $2$), no function symbol (thus : $-$) and no constant (thus : $0$).

---

You can as well use $\mathbb N$ for a counterexample, considering the "natural" ordering $<$.

Of course :

$\mathbb N \vDash \forall x \exists y \ (x < y)$ (for each natural $n$, it is enough to choose $n+1$);

but :

$\mathbb N \nvDash \exists y \forall x \ (x < y)$ (there is no natural number that is greater than any number).

Answer 2

Here, the author wants to disprove a formula $P$. He wants to do it by exhibiting a model where $P$ is false. A model is a set $A$, plus an interpretation of all relations (a $n$-ary relation is just interpreted as a subset of $A^n$).

Here, he gives $A = \{0,1\}$, and $varphi$ is interpreted as the relation $P$ such that $(0,1) \in P,(1,0)\in P$.

Then this model $\mathfrak A = (A,P)$ is a counter-model of the formula, because it is false in it.

As a true formula have to be true in every model, the considered formula is not true.