This web page provides answers, or hints and clues, to exercises
from Chapter 3 of The Mathematics of Logic

and also some additional
information on some of the examples.

Exercise 3.14.

By induction on the length of a derivation, the iduction hypothesis being that is $\sigma $ is derived from ${\Sigma}_{0}$ in $n$ steps or fewer then $\sigma $ contains a $0$.

For the Given rule, if ${\Sigma}_{0}\u22a2\sigma $ by Given then $\sigma \in {\Sigma}_{0}$ so contains a zero, as all elements of ${\Sigma}_{0}$ do.

For the Shortening rule, if ${\Sigma}_{0}\u22a2\sigma $ where the last step is Shortening then ${\Sigma}_{0}\u22a2\sigma 0$ and ${\Sigma}_{0}\u22a2\sigma 1$ by shorter derivations, so by the induction hypothesis both $\sigma 0$ and $\sigma 1$ contain zeros, in particular $\sigma 1$ and hence $\sigma $ does.

For the Lengthening rule, if ${\Sigma}_{0}\u22a2\sigma $ where the last step is Lengthening then $\sigma =\tau i$ where$i=0$ or $1$ and ${\Sigma}_{0}\u22a2\tau $ in fewer steps. So by induction, $\tau $ contains $0$ hence $\sigma $ does too.

Exercise 3.15.

If ${\Sigma}_{0}\u22a2\perp $ then by 3.14 $\perp $ would contain $0$, but $\perp $ is the empty string so contains no characters at all. So ${\Sigma}_{0}\u22ac\perp $.

Exercise 3.16.

Let $H\left(n\right)$ be the statement
Suppose $\sigma $ is a string of $n$ 1's.
Then ${\Sigma}_{0}\cup \left\{\sigma \right\}\u22a2\perp $

.

$H\left(0\right)$ is true as a string of $0$ 1's is $\perp $ and ${\Sigma}_{0}\cup \left\{\perp \right\}\u22a2\perp $ by the Given rule.

Suppose $n\u2a7e0$ and $H\left(n\right)$ holds. Write ${1}^{n}$ for a string of $n$ 1's. Then ${\Sigma}_{0}\cup \left\{{1}^{n+1}\right\}\u22a2\perp $ since we may write down: ${1}^{n+1}$ (Given); ${1}^{n}0$ (Given, in ${\Sigma}_{0}$); then ${1}^{n}$ (Shortening); and follow this with the proof from ${\Sigma}_{0}\cup \left\{{1}^{n}\right\}$ of $\perp $ given by $H\left(n\right)$. Thus $H\left(n\mathrm{+1}\right)$ holds and so $H\left(n\right)$ holds for all $n$ by induction.

Exercise 3.17.

Suppose $\sigma $ contains $0$. Look at the first $0$ in it. It follows that $\sigma ={1}^{n}0\tau $ for some $n$ (possibly zero) and some $\tau \in {2}^{*}$.

Then if $\tau ={\tau}_{0}{\tau}_{1}\dots {\tau}_{k-1}$
where each ${\tau}_{i}$ is $0$ or $1$ we
have the derivation:
${1}^{n}0$ (Given, in ${\Sigma}_{0}$);
${1}^{n}0{\tau}_{0}$ (Lengthening);
${1}^{n}0{\tau}_{0}{\tau}_{1}$ (Lengthening);

Exercise 3.18.

Let $X=\{\Sigma \subseteq {2}^{*}:{\Sigma}_{0}\subseteq \Sigma ,\Sigma \u22ac\perp \}$. Let ${\Sigma}^{+}$ be the set ${\Sigma}^{+}=\{\tau \in {2}^{*}:\tau \text{contains a}0\}$. We claim that ${\Sigma}^{+}\in X$ and is maximal.

For the first, each $\tau \in {\Sigma}_{0}$ contains $0$ so ${\Sigma}_{0}\subseteq {\Sigma}^{+}$ and also for $\tau \in {\Sigma}^{+}$ we have ${\Sigma}_{0}\u22a2\tau $ by 3.17, hence any proof of the form ${\Sigma}^{+}\u22a2\sigma $ can be rewritten to make it a proof of ${\Sigma}_{0}\u22a2\sigma $. By we know $\Sigma \u22ac\perp $ by 3.15 so ${\Sigma}^{+}\u22ac\perp $, hence ${\Sigma}^{+}\in X$.

If $\sigma \notin {\Sigma}^{+}$ then it doesn't contain any $0$ hence $\sigma ={1}^{n}$ for some $n$ (possibly zero). Hence ${\Sigma}^{+}\cup \left\{\sigma \right\}\u22a2\perp $ since by 3.16 ${\Sigma}_{0}\cup \left\{\sigma \right\}\u22a2\perp $ and ${\Sigma}^{+}\supseteq {\Sigma}_{0}$. Thus ${\Sigma}^{+}\cup \left\{\sigma \right\}\notin X$, as required to show maximality.

It remains to show that ${\Sigma}^{+}$ is the only maximal element of $X$. Suppose $\Gamma \in X$ is maximal, so $\Gamma \supseteq {\Sigma}_{0}$ and $\Gamma \u22ac\perp $. Then if ${\Sigma}_{0}\u22a2\sigma $ we must have $\sigma \in \Gamma $ for $\Gamma \supseteq {\Sigma}_{0}$ so $\Gamma \cup \sigma \u22a2\perp $ would imply that $\Gamma \u22a2\perp $ by replacing each instance of $\sigma $ by Given in the proof by the proof of $\sigma $ from ${\Sigma}_{0}$. But $\Gamma \u22ac\perp $ hence $\Gamma \cup \sigma \u22ac\perp $ so by maximality $\sigma \in \Gamma $.

Now as each string containing $0$ is provable in ${\Sigma}_{0}$ (3.17) we have $\Gamma \supseteq {\Sigma}^{+}$. By maximailty of ${\Sigma}^{+}$ it follows that $\Gamma ={\Sigma}^{+}$ as required.

Exercise 3.19.

Let $p={2}^{*}\setminus {\Sigma}^{+}$. This is a path, as proved in the proof of the Completeness theorem, using the fact that ${\Sigma}^{+}$ is maximal. But ${\Sigma}^{+}$ is the set of $\tau \in {2}^{*}$ containing a zero, so $p=\{{1}^{n}:n\in \mathbb{N}\}$ and this is indeed a path as you can check.

Exercise 3.20.

Let $\sigma ={1}^{n}0$ and define a path $q=\left\{\perp ,1,11,111,\dots ,{1}^{n},{1}^{n}0,{1}^{n}00,{1}^{n}000,\dots \right\}$. Then ${\Sigma}_{0}\cap q=\left\{{1}^{n}0\right\}$ so $({\Sigma}_{0}\setminus \left\{\sigma \right\})\cap q=\varnothing $ and $q$ is an infinite path containing $\sigma $ so ${\Sigma}_{0}\setminus \left\{\sigma \right\}\u22ad\sigma $ hence by the Soundness Theorem ${\Sigma}_{0}\setminus \left\{\sigma \right\}\u22ac\sigma $.

Exercise 3.21.

$\Sigma $ is consistent iff there is no proof of $\perp $ from $\Sigma $ obeying the rules. (This is the official definition.)

$\Sigma $ is consistent iff there is no proof of $\perp $ from a finite subset of $\Sigma $ obeying the rules. (This is from the official definition, observing all proofs are finie.)

$\Sigma $ is consistent iff there is a a partial order on $X$ making $\Sigma $ true. (Left to right is the completeness theorem; right to left is Soundness.)

Exercise 3.22.

Since by RAA $\Sigma \u22a2\sigma $ iff
$\Sigma \cup \left\{\tau \right\}\u22a2\perp $, where
$\sigma $ and $\tau $ are negations (or opposites

of each other) it suffices (and is slightly easier) to
give an algorithm for when $\Sigma \u22a2\perp $.

Suggestion: Separate $\Sigma ={\Sigma}^{+}\cup {\Sigma}^{-}$ the set ${\Sigma}^{+}$ of positive sentences in $\Sigma $ and the set ${\Sigma}^{-}$ of negative sentences in $\Sigma $. (We may assume $\perp \notin \Sigma $ for if it is the answer is easy by Given.) Now define the transitive closure of ${\Sigma}^{+}$ to be the set of all sentences provable from ${\Sigma}^{+}$ by the Transitivity rule and the Given rule. Since ${\Sigma}^{+}$ is finite, the transitive closure of ${\Sigma}^{+}$ is also finite. (Why?) Explain why the transitive closure of ${\Sigma}^{+}$ can be computed from ${\Sigma}^{+}$. The algorithm goes by computing the transitive closure of ${\Sigma}^{+}$ and checking none is of the form $aa$ nor $ab$ for some $ab\in {\Sigma}^{-}$. If these checks work then $\Sigma \u22ac\perp $ and if not then $\Sigma \u22a2\perp $. (Why?)

Exercise 3.23.

The easiest semantics is $\models {|}^{n}-{|}^{k}={|}^{l}$ holds iff $n+k=l$. The rest involves proving Soundness and Completeness Theorems.

Exercise 3.24.

Hint: Show by induction that the number of $I$s is any derivable string cannot be divisible by 3. In particular $MU$ cannot be derived. Also that in any derivable string there always exactly one $M$ at the beginning. Thus $MUIMUI$ cannot be derived. The rest are either derivable or are not derivable by similar arguments.

Exercise 3.25.

Some suggestions:

KENNEDY: No, I don't accept that. I think you're quibbling here
about semantics quite frankly.

PAXMAN: I think you're the one who's quibbling with semantics

(from http://news.bbc.co.uk/1/hi/programmes/newsnight/archive/2136776.stm)

and

MICHAEL ANCRAM: Alistair (Darling) was talking about having
reduced unemployment over a million over the last three and a half
years, that is actually a slower rate than over the last three and a
half years ours of our government. What we're talking about here, is
not the semantics, it is about what actual people realise is happening
in their own lives.

(from http://news.bbc.co.uk/1/hi/events/newsnight/1114288.stm)