X.3.5 Exercise. Let $M$ be a nonempty set and $R\subseteq M\times M$ a binary relation over $M$. Let $M_a = \{b\mid Rab\}$ and $D = \{b\mid \neg Rbb\}$. And let $R\xi a$ be true if and only if $\xi$ is the Gödel number of a program $P$ such that $P: a\rightarrow\text{halt}$.

A subset $A$ of $M$ is decidable if there is a program which for all $a\in M$ halts and outputs a truthy value if $a\in A$.

1. $D$ is distinct from all $M_a$.

   For any $a\in M$, either $Raa$ or $\neg Raa$. If $Raa$, then $a\not\in D$ and $a\in M_a$. If $\neg Raa$, then $a\in D$ and $a \not\in M_a$. So $a$ cannot be an element of both $M_a$ and $D$, so the two sets must differ by at least $a$.

2. All decidable subsets of $M$ occur among $M_a$.

   For any decidable subset $A$ of $M$, let $P$ be a decision procedure for $A$. Let $P'$ be a program which for $a\in M$ halts if and only if $P$ decides $a\not\in A$. Supposing $\xi_{P'}$ is $P'$'s Gödel number, $M_{\xi_{P'}}\equiv A$.

3. $D$ is undecidable.

   Per (1) and (2).

4. The set $\Pi_{\text{halt}'}=\{P \mid P:\xi_P\rightarrow \text{halt}\}$ is undecidable.

   Suppose $\Pi_{\text{halt}'}$ was decidable by a program $P$. Then $D$ is decidable with $P$ (For an input $a\in M$, if $a$ is the Gödel number for a program $P_a$, use $P$ to determine if $P_a$ is an element of $\Pi_{\text{halt}'}$. If $P_a\in\Pi_{\text{halt}'}$, then $a\not\in D$. If $P_a\not\in\Pi_{\text{halt}'}$, $a\in D$.). But this contradicts (3), so $\Pi_{\text{halt}'}$ is undecidable.

5. There is not a program which decides if an arbitrary program halts.

   If there were $\Pi_{\text{halt}'}$ would be decidable, a contradiction to (4).

X.1.10 Exercise. Let $\mathbb{A}_1$ and $\mathbb{A}_2$ be finite alphabets such that $\mathbb{A}_1 \subseteq \mathbb{A}_2$, and suppose $W \subseteq \mathbb{A}_1^*$. Show $W$ is decidable (enumerable) with respect to $\mathbb{A}_1$ if and only if it is decidable (enumerable) with respect to $\mathbb{A}_2$.

Because $\mathbb{A}_1$ and $\mathbb{A}_2$ are alphabets, $\mathbb{A}_1^*$ and $\mathbb{A}_2^*$ are enumerable by 1.5 (p. 150). Let $\mathfrak{E}_{\mathbb{A}_2^*}$ be a procedure which enumerates $\mathbb{A}_2^*$. $\mathbb{A}_2^*\setminus\mathbb{A}_1^*$ is enumerable by a procedure which filters out elements of $\mathfrak{E}_{\mathbb{A}_2^*}$'s output containing only elements of $\mathbb{A}_1$. $\mathbb{A}_1^*$ is decidable with respect to $\mathbb{A}_2^*$ by Theorem 11.8 (p. 151) by the enumerability of $\mathbb{A}_2^*\setminus\mathbb{A}_1^*$ and $\mathbb{A}_1^*$. Let $\mathfrak{D}_{\mathbb{A}_2^*\rightarrow\mathbb{A}_1^*}$ be a decision procedure for $\mathbb{A}_1^*$ with respect to $\mathbb{A}_2^*$. Suppose $W$ is decidable with respect to $\mathbb{A}_1$. Call $\mathfrak{D}_{\mathbb{A}_1^*\rightarrow W}$ that decision procedure. Then $W$ is decidable with respect to $\mathbb{A}_2$ with a decision procedure which checks its input satisfies $\mathfrak{D}_{\mathbb{A}_2^*\rightarrow\mathbb{A}_1^*}$ and $\mathfrak{D}_{\mathbb{A}_1^*\rightarrow W}$. Suppose $W$ is decidable with respect to $\mathbb{A}_2$. Call $\mathfrak{D}_{\mathbb{A}_2^*\rightarrow W}$ that decision procedure. Because $\mathbb{A}_1\subseteq\mathbb{A}_2$, $\mathfrak{D}_{\mathbb{A}_2^*\rightarrow W}$ is also a decision procedure for $W$ with respect to $\mathbb{A}_1$. So $W$ is decidable with respect to $\mathbb{A}_1$.

5.10 Exercise. Show (a) The relation $\lt$ ("less-than") is elementarily definable in $(\mathbb{R}, +, \cdot, 0)$, i.e., there is a formula $\varphi \in L_2^{\{+,\cdot,0\}}$ such that for all $a, b \in \mathbb{R}$,

$(\mathbb{R}, +, \cdot, 0) \models \varphi[a,b] \leftrightarrow a \lt b.$

(b) The relation $\lt$ is not elementarily definable in $(\mathbb{R}, +, 0)$.

Proof. (a) is easily satisfied by $\varphi=\exists k\in\mathbb{R},a+k\cdot k\equiv b\land a\not\equiv b$.

For (b) consider the automorphism $\pi(x)=-x$. I'll derive a contradiction. Say there were a $\phi$ satisfying $a\lt b\leftrightarrow (\mathbb{R}, +, 0) \models \varphi[a,b]$.

But $a\lt b \leftrightarrow -a\lt -b$ is a contradiction, so $\lt$ is not elementarily definable in $(\mathbb{R}, +, 0)$.

4.15 Exercise. Let $I$ be a nonempty set. For every $i \in I$, let $\mathfrak{A}_i$ be an $S$-structure. We write $\prod_{i\in I} \mathfrak{A}_i$ for the direct product of the structures $\mathfrak{A}_i$, that is, the $S$-structure $\mathfrak{A}$ with domain

which is determined by the following conditions (where for $g \in \prod_{i\in I} A_i$ we also write $\langle g(i) | i \in I \rangle$):

For $n$-ary $R \in S$ and $g_1, \dots, g_n \in \prod_{i \in I} A_i,$

For $n$-ary $f \in S$ and $g_1, \dots, g_n \in \prod_{i \in I} A_i,$

and $c^{\mathfrak{A}} := \langle c^{\mathfrak{A}_i} \mid i \in I\rangle$ for $c \in S.$

Show: If $t$ is an S-term with $\text{var}(t) \subseteq \{v_0, \dots, v_{n-1}\}$ and if $g_0, \dots, g_{n-1} \in \prod_{i \in I} A_i,$ then the following holds:

Proof. I'll use induction on S-terms.

$t=x$: Suppose $j \in 0,\dots,(n-1)$ is the index in the variable assignment list corresponding to $x$. As $t$ is a variable and variables take on the value assigned to them when interpreted, $t^{\mathfrak{A}_i}[g_0(i), \dots, g_{n-1}(i)]=g_j(i)$. Thus,

$t=c$: As $t$ is a constant, $\text{var}(t)=\varnothing$. Thus by the Coincidence Lemma (p. 34), variable assignments don't change the value of $t$ under interpretation.

$t=ft_1\dots t_n$: First, for a S-interpretation $\mathfrak{J}$, $\mathfrak{J}(ft_1\dots t_n)$ is $f^{\mathfrak{J}}\mathfrak{J}(t_1)\dots\mathfrak{J}(t_n)$; I make use of this in the first step below. Second, per the induction hypothesis, $t^{\mathfrak{A}}[g_0, \dots, g_{n-1}](i)$ is $t^{\mathfrak{A_i}}[g_0(i), \dots, g_{n-1}(i)]$; I make use of this in the second step below.

This concludes the proof via induction on S-terms.

4.16 Exercise. Formulas which are derivable in the following calculus are called Horn formulas.

1. For $n \in \mathbb{N}$ and atomic S-formulas $\phi_1, \dots, \phi_n, \phi$:
   $$\frac{}{(\neg\phi_1 \lor \dots \lor \neg\phi_n \lor \phi)}$$
2. For $n \in \mathbb{N}$ and atomic S-formulas $\phi_1, \dots, \phi_n$:
   $$\frac{}{\neg\phi_1 \lor \dots \lor \neg\phi_n}$$
3. For Horn formulas $\phi$ and $\psi$:
   $$\frac{\phi, \psi}{(\phi \land \psi)}$$
4. For Horn formula $\phi$:
   $$\frac{\phi}{\forall x \phi}$$
5. For Horn formula $\phi$:
   $$\frac{\phi}{\exists x \phi}$$

Horn formulas without free variables are called Horn sentences. Show: If $\phi$ is a Horn sentence and $\forall i\in I$ $\mathfrak{A}_i$ is a model of $\phi$, then for $\mathfrak{A}:=\prod_{i \in I} \mathfrak{A}_i$, $\mathfrak{A} \models \phi$.

Proof. I'll use induction on Horn formulas. First, a lemma.

I show this is true for both forms of atomic S-formula.

$\psi=t_1\equiv t_2$: Recall from Exercise 4.15 $\mathfrak{A}(t) = \langle \mathfrak{A}_i(t) \mid i \in I \rangle$.

$\psi=Rt_1\dots t_n$: Another consequence of Exercise 4.15 is $\mathfrak{A}(t)(i)$ is $\langle \mathfrak{A}_i(t) \mid i \in I \rangle(i)$ is $\mathfrak{A}_i(t)$ which I use in the 3rd step below.

Now, induction on Horn formulas.

$\psi=(\neg\phi_1 \lor \dots \lor \neg\phi_n \lor \phi)$:

Note:

Which together with Lemma 1 and the observation $\mathfrak{A}\models \psi\leftrightarrow\exists m\leq n,\mathfrak{A}\models \neg\phi_m\lor\mathfrak{A}\models \neg\phi$ means:

$\psi=\neg\phi_1 \lor \dots \lor \neg\phi_n$:

$\psi=(\phi \land \varphi)$:

$\psi=\forall x \phi$:

This follows from Exercise 4.15, which establishes (with different notation) $\mathfrak{A}\frac{a}{x}(t)\equiv\langle\mathfrak{A}_i\frac{a(i)}{x}(t)\mid i\in I\rangle$. This can be propogated through Lemma 1 and the other steps of this proof to see it holds for $\phi$.

$\psi=\exists x \phi$:

This concludes the proof via induction on Horn formulas.

4.14 Exercise. A set $\Phi$ of sentences is called independent if there is no $\phi \in \Phi$ such that $\Phi \setminus \{\phi\} \models \phi$. Show that the set of group axioms and the set of axioms for equivalence relations are independent. (p. 36)

I'll start with equivalence relations, their axioms being:

1. $\forall x, Rxx$
2. $\forall xy, Rxy \rightarrow Ryx$
3. $\forall xyz, (Rxy \land Ryz) \rightarrow Rxz$

This exercise asks for a proof none of the axioms of equivalence relations are redundant. Letting $(1)$, $(2)$, and $(3)$ correspond to the axioms above and setting $\Phi = \{(1), (2), (3)\}$, we'd like to show:

Which unrolls to three cases.

1. $\lnot \{(2), (3)\} \models (1)$
2. $\lnot \{(1), (3)\} \models (2)$
3. $\lnot \{(1), (2)\} \models (3)$

$\Beta \models \beta$, read "$\Beta$ models $\beta$", is true if all interpretations which are true for the sentences in $\Beta$ are also true for $\beta$. To show $\lnot \Beta \models \beta$, it is sufficent to find an interpretation which is true for the sentences in $\Beta$ and false for $\beta$. As we're dealing with relations, we look for relations which satisfy only two of the three axioms.

A relation on a set $X$ is a subset $R$ of $X\times X$. $Rxy$ is true $\leftrightarrow (x,y)\in R$. Three relations then satisfying the expressions above are:

For $R_1$ suppose the domain is non-empty. In this case, the second and third axioms are vacuously true, but $(1)$ is not satisfied. $R_2$ satisfies the first and third axiom, but violates the second one as $(1,2)\in R_2$ but $(2,1)\notin R_2$. $R_3$ satisfies the first and second axiom, but voilates the third one as $(2,1)\in R_3 \land (1,3) \in R_3$ but $(2,3)\notin R_3$. Thus, the axioms of equivalence relations are independent.

For $\lnot \{(2), (3)\} \models (1)$ there is a more general solution.

$R$ is not reflexive if $\exists x,(x,x)\notin R$. By Lemma 1, for $R$ satisfying the second and third axiom to not also satisfy the first axiom, there must exist $x$ not in the domain or range of $R$. Thus, starting from a relation $R$ satisfying all three axioms, one can generate $R'$ satisfying only the second and third by selecting $B\subseteq A$ and $R'=\{p \mid p\in R \land p \notin B\times B\}$. Setting $B=A$ yields $\varnothing$ i.e. $R_1$ above.

Independence of Group Axioms

A 2-ary function $f$ is a group over the domain $A$ if it satisfies identity, inverse, and associativity. These are satisfied if for some constant $e$ in $A$:

1. $\forall x, fxe \equiv x$, i.e. identity.
2. $\forall x, \exists x^{-1}, fxx^{-1}\equiv e$, i.e. inverse.
3. $\forall xyz, fxfyz\equiv ffxyz$, i.e. associativity.

As with equivalence relations, there are three cases.

1. $\lnot \{(2), (3)\} \models (1)$. For the group addition over the integers, $e$ would normally take on the value $0$, but without $(1)$ $e$ can be $1$ (i.e. $x^{-1}=-x+1$). With this new value of $e$, $(2)$ and $(3)$ are satisfied, but $(1)$ is not.
2. $\lnot \{(1), (3)\} \models (2)$. For $fab=a\times b$ over the set $\mathbb{Q}^{2 \times 2}$ of matricies with rational entries, $e$ is $\begin{pmatrix}1 & 0 \\0 & 1\end{pmatrix}$, matrix multiplication is associative, but not all matricies are invertable.

For the third case, $\lnot \{(1), (2)\} \models (3)$, we'd like to find an operation and domain which satisfies identity and inverse but not associativity. Let the domain $A$ be $\{a,b,e\}$ and let $f:A\times A \rightarrow A$ be defined as follows:

$fab$ corresponds to the value in row $a$ and column $b$, i.e. $b$. From the table, $x^{-1}$ is $x$, left and right identity are satisfied, but associativity is not satisfied.

So the axioms of group theory are independent.

Thanks Pete for the book recomendation.