I have an exercise that I cannot really understand:

Let $P(n)$ be a property over the naturals (i.e., $n \in N$). The induction axiom, taking $0$ for the base-case instance, is the formula:

$$[P (0) \land (\forall k \in \mathbb{N} P(k) \rightarrow P(k + 1))] \rightarrow \forall n \in \mathbb{N} P(n)$$

Take some time to understand clearly what this formula tells you. Then consider the following . I ask a friend of mine to select a sequence of numbers, starting with an odd one. I want to prove that all the numbers my friend will select will be odd.

  • Base case:

    my friend selects the first number, that has to be odd. $P(1)$ holds trivially.

  • Induction step:

    assume $P(n)$ holds for an arbitrary $n \in \mathbb{N}^+$: consider the sequence $\{s_1, \dots , s_{n+1}\}$ of the selected numbers, $n + 1$ too. Split the sequence in two parts: $S_1 = \{s_1\}$ and $S_2 = \{s_2, \dots , s_{n+1}\}$. We know that $P(1)$ holds therefore $S_1$ contains an odd number. Moreover, since we assumed that $P(n)$ holds for any arbitrary $n$, the sequence $S_n$ (with $n$ elements) contains only odd numbers. The union of the two sequences of odd numbers is a sequence of odd numbers, so the sequence $\{s_1, \dots ,s_{n+1}\}$ contains only odd numbers, proving that $P (n + 1)$ holds. This concludes the proof:we showed by induction that $P(n)$ holds for all $n \in\mathbb{N}^+$.

First of all, I don't understand what has the formula above to do with the proof.

Then regarding the correctness of the proof, I have some ideas:

  1. The fact that base case is true (if he selects just a number, then it's an odd number), does not mean that s1 in the first sequence is odd, right? If yes, could you explain better why?

Are there other problems in the proof (if my guess 1 is correct)?

  • 2
    $\begingroup$ You can disprove this via direct counterexample. I pick (1,2). $\endgroup$ – Benjamin Roycraft Jan 14 '15 at 1:03
  • $\begingroup$ Where is $P(0)$ as a base case? Also when you use induction you only assume that $P(n)$ holds. Not that $P(0),\ldots,P(n)$ hold. So you cannot use $P(1)$ unless you prove it explicitly. $\endgroup$ – Asaf Karagila Jan 14 '15 at 1:04
  • 4
    $\begingroup$ The invalid step is "since we assumed that P(n) holds for any arbitrary n, the sequence Sn (with n elements) contains only odd numbers". P(n) involves the first n numbers chosen, not any arbitrary n-length sub-sequence of the numbers chosen. $\endgroup$ – M.M Jan 14 '15 at 1:04
  • 1
    $\begingroup$ It's a junk proof, perhaps trying to convince you not to give up your intuition :-) . What is $P(x)$, after all? It seems to have been replaced by a dragon that can do anything. $\endgroup$ – Joffan Jan 14 '15 at 1:06
  • 5
    $\begingroup$ This is the standard all horses are of the same colour "proof." The $n=1$ case works, and if $n\ge 2$ we can deduce $P(n+1)$ from $P(n)$. But the induction step from $n=1$ to $n=2$ fails. $\endgroup$ – André Nicolas Jan 14 '15 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.