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)


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)