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:
- 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)?