Definable relations

First-Order Formulas can be used to define relations in structures. For this purpose we use formulas with free variables and interprete those $A$-assignents over the free variables as tuples of a relation that evaluate the formula to one.

Motivating examples

Example Let $\mathcal N$ be the structure of the natural numbers in the signature $\{\dot 0, \dot 1, {\dot +}/\!/2, {\dot \cdot}/\!/2, {\dot <}/2\}$. The fact that a number $x_0$ is a prime number can be expressed by the formula $\varphi$ given by \begin{align} \varphi = \forall x_1 \forall x_2 (x_1 \dot \cdot x_2 \doteq x_0 \rightarrow (x_1 \doteq 1 \wedge \neg x_2 \doteq 1) \vee (x_2 \doteq 1 \wedge \neg x_1 \doteq 1)) \enspace. \end{align}

Similarly, the fact that $x_0$ is a prime factor of $x_1$ can be expressed by \begin{align} \varphi \wedge \exists x_2 (x_0 \dot \cdot x_2 \doteq x_1) \enspace. \end{align}

Example Let $\mathcal S$ be the signature determined by $\mathcal S = \{E/2\}$. Then every $\mathcal S$-structure can be viewed as a directed graph with loops. The formula \begin{align} x_0 \doteq x_1 \vee E(x_0,x_1) \vee \exists x_2 (E(x_0,x_2) \wedge E(x_2,x_1)) \end{align} expresses that the distance of $x_1$ from $x_0$ is at most $2$. (Note that distance may be asymmetric for directed graphs.)

Formal definition

Definition Given a signature $\mathcal S$, a natural number $n$, an $\mathcal S$-formula with $\text{fvars}(\varphi) \subseteq \{x_0, \dots, x_{n-1}\}$, and an $\mathcal S$-structure $\mathcal A$, the $n$-ary relation defined by $\varphi$ in $\mathcal A$ is denoted $\langle n, \varphi\rangle^\mathcal A$ and defined by \begin{align} \langle n, \varphi\rangle^\mathcal A = \{\langle a_0, \dots, a_{n-1}\rangle \mid \mathcal A, \{x_0 \mapsto a_0, \dots, x_{n-1} \mapsto a_{n-1}\} \mymodels \varphi\} \enspace. \end{align} Note that this is well-defined by the coincidence lemma.

Definition Given a signature $\mathcal S$, an $\mathcal S$-structure $\mathcal A$, and an $n$-ary relation over $A$, this relation is said to be definable if it is defined by some appropriate first-order formula.

Example From the previous examples, we conclude that 'being a prime number' is definable in the natural numbers; the same is true for 'being a prime factor of'.

Definition Let $\mathcal S$ be a signature, $n$ a natural number, and $\mathfrak C$ a class of $\mathcal S$-structures. Further, assume that for every $\mathcal A \in \mathfrak C$, there is an $n$-ary relation $R_\mathcal A \subseteq A^n$. Then this family of relations is said to be definable if there is an $\mathcal S$-formula $\varphi$ with $\text{fvars}(\varphi) \subseteq \{x_0, \dots, x_{n-1}\}$ such that $\langle n, \varphi\rangle^\mathcal A = R_\mathcal A$ for every $\mathcal A \in \mathfrak C$.

Example In the class of all directed graphs, 'is within distance 2 of' is definable.

Exercises

Exercise

1. Die Signatur $\mathcal S$ sei definiert durch $\mathcal S = \{E/2\}$. Geben Sie formale Definitionen (in der Form $\langle n, \varphi\rangle$) für die folgenden Relationen in $\mathcal S$-Strukturen (also gerichteten Graphen) an:
   1. Es gibt eine Kante von $x_1$ nach $x_0$.
   2. Der Knoten $x_0$ ist ein Knoten ohne Eingangskanten.
   3. Ausgehend vom Knoten $x_0$ kommt man in höchstens zwei Schritten zu jedem anderen Knoten. (Ein Schritt ist der Übergang von einem Knoten, der am Anfang einer Kante sitzt, zu dem Knoten, der am Ende dieser Kante sitzt.)
2. Im Folgenden betrachten wir die natürlichen Zahlen in der Signatur $\{\dot{0}, \dot{1}, {+}/\!/2, {\cdot}/\!/2, {<}/2\}$. Geben Sie formale Definitionen für die folgenden Relationen in den natürlichen Zahlen an.
   1. Die Zahlen $x_0$, $x_1$ und $x_2$ bilden ein pythagoreisches Tripel.
   2. Die Zahlen $x_0$ und $x_1$ sind Primzahlzwillinge.
   3. Die Zahl $x_0$ ist eine gerade Zahl, auf die die Goldbachsche Vermutung zutrifft.

Lösung

---

1. Sei $\mathcal S=\{E/2\}$.
   1. $\langle 2, E(x_1,x_0)\rangle$
   2. $\langle 1, \forall\, x_2 \neg E(x_2,x_0)\rangle$ oder $\langle 1, \neg\exists x_2\, E(x_2,x_0)\rangle$
   3. $\langle 1, \forall\, x_2 \left(E(x_0,x_2)\vee \exists x_1 (E(x_0,x_1)\wedge E(x_1,x_2)) \right)\rangle$ oder
      $\langle 1, \neg\exists\, x_2 \neg\left(E(x_0,x_2)\vee \exists x_1 (E(x_0,x_1)\wedge E(x_1,x_2)) \right)\rangle$
2. Sei $\mathcal S=\{0, 1, +/\!\!/2,\cdot/\!\!/2,</2\}$. Definiere zunächst für die letzten beiden Relationen die Formel $\varphi=(1<x_0) \wedge \forall x_4\forall x_5 \left((x_4\cdot x_5)\dot{=} x_0 \rightarrow (x_4\dot{=}1\vee x_5\dot{=}1)\right)$, die für eine Belegung $\beta$ wahr ist, wenn $\beta(x_0)$ eine Primzahl ist. Achtung, es sollten keine Substiutionen auf $x_4,$ oder $x_5$ geben.
   1. $\langle 3, (x_0\cdot x_0)+(x_1\cdot x_1)\dot{=}(x_2\cdot x_2)\rangle$
   2. $\langle 2, x_1\dot{=} (x_0 + 1) + 1 \wedge \varphi \wedge \varphi\{x_0\mapsto x_1\} \rangle$
   3. $\langle 1, \exists x_1 (x_1\cdot(1+1) \dot{=} x_0) \wedge \exists x_1\exists x_2 (x_1 + x_2 \dot{=}x_0 \wedge \varphi\{x_0\mapsto x_1\}\wedge \varphi\{x_0\mapsto x_2\}) \rangle$