Question

Are the following statements true or false?

1. Let P(n) be the statement "If any string of length n over {a, b} has more a's than b's, then it has two a's in a row". We can prove this statement is true for all n with n ≥ 2 by proving P(2), P(3), and "for all n: P(n) → P(n+2)".

2. Let P(x) be a predicate with one free variable x of type natural. If I prove P(0), "for all x: P(x) → P(x+2)", and "for all x: P(x) → P(x+3)", I may conclude "for all x: P(x)".

Answer 1

1.

For n=3, we take the string "aba" of length 3. It is a string over (a,b) that has more a's than b's, but without two a's in a row. Thus, P(3) is not true.

2.

Let P(x) be a predicate with one free variable of type natural.

Let us suppose that , and have been proved.

Then,

and together give us the proof for .

and together give us the proof for .

and together give us the proof for .

and together give us the proof for .

and together give us the proof for .

The last two statements are a generalisation for all the proofs we can obtain. However, we can see that for no value of m, can we obtain the proof for P(1) anywhere. So, there is no way to determine the truth of P(1).

Therefore, we cannot conclude ""