First Conundrum:

If possible, describe an induction principle for the set of

{0,−1,−2, . . .}. If this is not possible, give a brief explanation of why

it is not possible.

Second Conundrum:

Determine if there is a problem with the following proof by

induction that ‘all Canadians live inWaterloo.’ Give a brief explanation

of the problem.

Base case: consider the group of 0 Canadians; clearly all the Canadians

in the group live in Waterloo.

I.H. For any group of 0 <= k Canadians, all those k Canadians live in

Waterloo.

Consider a group of k + 1 Canadians. Remove Canadian c from the

group. The group consists of k Canadians, by the I.H. all those k

Canadians live in Waterloo. Pick one of the k Canadians, say d, d

lives in Waterloo. Remove d from the group and replace d with c. The

group still has k Canadians so, by the I.H., they all live in Waterloo.

Therefore all the k + 1 Canadians live in Waterloo.