Exercises and examples from Chapter 3

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⊢\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⊢\sigma$ where the last step is Shortening then ${\Sigma }_0⊢\sigma 0$ and ${\Sigma }_0⊢\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⊢\sigma$ where the last step is Lengthening then $\sigma =\tau i$ where$i=0$ or $1$ and ${\Sigma }_0⊢\tau$ in fewer steps. So by induction, $\tau$ contains $0$ hence $\sigma$ does too.

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

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

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

Suppose $n⩾0$ 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\}⊢\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.

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); $1^{n}0{\tau }_0{\tau }_1\dots {\tau }_{k-1}$ (Lengthening); showing ${\Sigma }_0⊢\sigma$.

Let $X=\left\{\Sigma \subseteq 2^{*}:{\Sigma }_0\subseteq \Sigma ,\Sigma ⊬\perp \right\}$. Let ${\Sigma }^{+}$ be the set ${\Sigma }^{+}=\left\{\tau \in 2^{*}:\tau \text{contains a}0\right\}$. 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⊢\tau$ by 3.17, hence any proof of the form ${\Sigma }^{+}⊢\sigma$ can be rewritten to make it a proof of ${\Sigma }_0⊢\sigma$. By we know $\Sigma ⊬\perp$ by 3.15 so ${\Sigma }^{+}⊬\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\}⊢\perp$ since by 3.16 ${\Sigma }_0\cup \left\{\sigma \right\}⊢\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 ⊬\perp$. Then if ${\Sigma }_0⊢\sigma$ we must have $\sigma \in \Gamma$ for $\Gamma \supseteq {\Sigma }_0$ so $\Gamma \cup \sigma ⊢\perp$ would imply that $\Gamma ⊢\perp$ by replacing each instance of $\sigma$ by Given in the proof by the proof of $\sigma$ from ${\Sigma }_0$. But $\Gamma ⊬\perp$ hence $\Gamma \cup \sigma ⊬\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.

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=\left\{1^n:n\in \mathbb{N}\right\}$ and this is indeed a path as you can check.

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\}⊭\sigma$ hence by the Soundness Theorem ${\Sigma }_0\setminus \left\{\sigma \right\}⊬\sigma$.

$\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.)

Since by RAA $\Sigma ⊢\sigma$ iff $\Sigma \cup \left\{\tau \right\}⊢\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 ⊢\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 ⊬\perp$ and if not then $\Sigma ⊢\perp$. (Why?)

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

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.

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)