# Exercises and examples from Chapter 3

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 $σ$ is derived from $Σ 0$ in $n$ steps or fewer then $σ$ contains a $0$.

For the Given rule, if $Σ 0 ⊢ σ$ by Given then $σ ∈ Σ 0$ so contains a zero, as all elements of $Σ 0$ do.

For the Shortening rule, if $Σ 0 ⊢ σ$ where the last step is Shortening then $Σ 0 ⊢ σ 0$ and $Σ 0 ⊢ σ 1$ by shorter derivations, so by the induction hypothesis both $σ 0$ and $σ 1$ contain zeros, in particular $σ 1$ and hence $σ$ does.

For the Lengthening rule, if $Σ 0 ⊢ σ$ where the last step is Lengthening then $σ = τ i$ where$i = 0$ or $1$ and $Σ 0 ⊢ τ$ in fewer steps. So by induction, $τ$ contains $0$ hence $σ$ does too.

Exercise 3.15.

If $Σ 0 ⊢ ⊥$ then by 3.14 $⊥$ would contain $0$, but $⊥$ is the empty string so contains no characters at all. So $Σ 0 ⊬ ⊥$.

Exercise 3.16.

Let $H ( n )$ be the statement Suppose $σ$ is a string of $n$ 1's. Then $Σ 0 ∪ σ ⊢ ⊥$ .

$H ( 0 )$ is true as a string of $0$ 1's is $⊥$ and $Σ 0 ∪ ⊥ ⊢ ⊥$ by the Given rule.

Suppose $n ⩾ 0$ and $H ( n )$ holds. Write $1 n$ for a string of $n$ 1's. Then $Σ 0 ∪ 1 n + 1 ⊢ ⊥$ since we may write down: $1 n + 1$ (Given); $1 n 0$ (Given, in $Σ 0$); then $1 n$ (Shortening); and follow this with the proof from $Σ 0 ∪ 1 n$ of $⊥$ given by $H ( n )$. Thus $H ( n +1 )$ holds and so $H ( n )$ holds for all $n$ by induction.

Exercise 3.17.

Suppose $σ$ contains $0$. Look at the first $0$ in it. It follows that $σ = 1 n 0 τ$ for some $n$ (possibly zero) and some $τ ∈ 2 *$.

Then if $τ = τ 0 τ 1 … τ k - 1$ where each $τ i$ is $0$ or $1$ we have the derivation: $1 n 0$ (Given, in $Σ 0$); $1 n 0 τ 0$ (Lengthening); $1 n 0 τ 0 τ 1$ (Lengthening); $1 n 0 τ 0 τ 1 … τ k - 1$ (Lengthening); showing $Σ 0 ⊢ σ$.

Exercise 3.18.

Let $X = Σ ⊆ 2 * Σ 0 ⊆ Σ , Σ ⊬ ⊥$. Let $Σ +$ be the set $Σ + = τ ∈ 2 * τ contains a 0$. We claim that $Σ + ∈ X$ and is maximal.

For the first, each $τ ∈ Σ 0$ contains $0$ so $Σ 0 ⊆ Σ +$ and also for $τ ∈ Σ +$ we have $Σ 0 ⊢ τ$ by 3.17, hence any proof of the form $Σ + ⊢ σ$ can be rewritten to make it a proof of $Σ 0 ⊢ σ$. By we know $Σ ⊬ ⊥$ by 3.15 so $Σ + ⊬ ⊥$, hence $Σ + ∈ X$.

If $σ ∉ Σ +$ then it doesn't contain any $0$ hence $σ = 1 n$ for some $n$ (possibly zero). Hence $Σ + ∪ σ ⊢ ⊥$ since by 3.16 $Σ 0 ∪ σ ⊢ ⊥$ and $Σ + ⊇ Σ 0$. Thus $Σ + ∪ σ ∉ X$, as required to show maximality.

It remains to show that $Σ +$ is the only maximal element of $X$. Suppose $Γ ∈ X$ is maximal, so $Γ ⊇ Σ 0$ and $Γ ⊬ ⊥$. Then if $Σ 0 ⊢ σ$ we must have $σ ∈ Γ$ for $Γ ⊇ Σ 0$ so $Γ ∪ σ ⊢ ⊥$ would imply that $Γ ⊢ ⊥$ by replacing each instance of $σ$ by Given in the proof by the proof of $σ$ from $Σ 0$. But $Γ ⊬ ⊥$ hence $Γ ∪ σ ⊬ ⊥$ so by maximality $σ ∈ Γ$.

Now as each string containing $0$ is provable in $Σ 0$ (3.17) we have $Γ ⊇ Σ +$. By maximailty of $Σ +$ it follows that $Γ = Σ +$ as required.

Exercise 3.19.

Let $p = 2 * ∖ Σ +$. This is a path, as proved in the proof of the Completeness theorem, using the fact that $Σ +$ is maximal. But $Σ +$ is the set of $τ ∈ 2 *$ containing a zero, so $p = 1 n n ∈ ℕ$ and this is indeed a path as you can check.

Exercise 3.20.

Let $σ = 1 n 0$ and define a path $q = ⊥ 1 1 1 1 1 1 … 1 n 1 n 0 1 n 0 0 1 n 0 0 0 …$. Then $Σ 0 ∩ q = 1 n 0$ so $( Σ 0 ∖ σ ) ∩ q = ∅$ and $q$ is an infinite path containing $σ$ so $Σ 0 ∖ σ ⊭ σ$ hence by the Soundness Theorem $Σ 0 ∖ σ ⊬ σ$.

Exercise 3.21.

$Σ$ is consistent iff there is no proof of $⊥$ from $Σ$ obeying the rules. (This is the official definition.)

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

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

Exercise 3.22.

Since by RAA $Σ ⊢ σ$ iff $Σ ∪ τ ⊢ ⊥$, where $σ$ and $τ$ are negations (or opposites of each other) it suffices (and is slightly easier) to give an algorithm for when $Σ ⊢ ⊥$.

Suggestion: Separate $Σ = Σ + ∪ Σ -$ the set $Σ +$ of positive sentences in $Σ$ and the set $Σ -$ of negative sentences in $Σ$. (We may assume $⊥ ∉ Σ$ for if it is the answer is easy by Given.) Now define the transitive closure of $Σ +$ to be the set of all sentences provable from $Σ +$ by the Transitivity rule and the Given rule. Since $Σ +$ is finite, the transitive closure of $Σ +$ is also finite. (Why?) Explain why the transitive closure of $Σ +$ can be computed from $Σ +$. The algorithm goes by computing the transitive closure of $Σ +$ and checking none is of the form $a a$ nor $a b$ for some $a b ∈ Σ -$. If these checks work then $Σ ⊬ ⊥$ and if not then $Σ ⊢ ⊥$. (Why?)

Exercise 3.23.

The easiest semantics is $⊨ | 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 $M U$ cannot be derived. Also that in any derivable string there always exactly one $M$ at the beginning. Thus $M U I M U I$ 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)