Each part below gives a set of facts about a predicate P(x). Select all the parts where P(x) is guaranteed to be true for all positive integers x.

Question

Each part below gives a set of facts about a predicate P(x). Select all the parts where P(x) is guaranteed to be true for all positive integers x.

 

P(1) is true: for all y > 0 , if P(y) is true then P(y+1) and P(y+2) are both true.

 
P(1), P(2), P(3) are all true. For all y >0, if P(y) is true then P(y+3) is true.

 
P(1) is true. For all y > 1, if P(y) is true then P(y+1) is true.

 
P(1), P(2), ... P(10) are all true. If [ y >5 and for all z with 1 < z < y, P(z) is true ] then P(y) is also true.

Answer 1

This is a nice question because it makes you think about the principle of induction.

Take the first part: P(1) is true, and for all y>0, if P(y) is true, then P(y+1) and P(y+2) are both true.
It is important that the "if then" is for all y >0, since the first case you are given to be true is P(1), and therefore P(x) in this case must be true for all positive integers.

The second case shows a small twist on induction. Given that P(1), P(2) and P(3) are true, and that if P(y) is true then P(y+3) is true, tells you that P(4), P(5, and P(6) are true. Repeating this clearly gives you all positive integers(eventually) so in this case it is also true for all positive integers.

In the third case you again know P(1) is true but now the statement is that for all y > 1, if P(y) is true then P(y+1) is true. Since 1 is not greater than 1, you can't conclude that P(2) is true, and without that you can't conclude that it is true for all positive integers.

P(1), P(2), ... P(10) are all true. If [ y >5 and for all z with 1 < z < y, P(z) is true ] then P(y) is also true.

In the final case it is showing you something called the Principle of Strong Induction. Here you can assume that the statement is true for all numbers below the one you are testing, not just the one before it. Suppose P(x) is as given in that case, and consider P(11), then the "if" condition is satisfied so P(11) is true. And then again for P(12)...These two forms of induction are in fact equivalent(and also equivalent to something called the well ordering principle).