What's the correct way of concluding an induction proof?

Question

I had to prove that for every set $s$, the number of subsets with odd cardinalities is $2^{n-1}$.

I concluded that this formula holds everytime $|s| \geq 1$ and then I used an inductive process to prove that my predicate $P(n) \Rightarrow P(n+1)$...

However I am a bit confused on how to express this final conclusion.

I originally concluded that:

$[\forall n \in \mathbb{N}, (P(n) \wedge n \geq 1 \Rightarrow P(n+1))] \Rightarrow \forall n \in \mathbb{N}, P(n)$

But then my confusion arose because I thought it could be better concluded in this way: $[\forall n \in \mathbb{N}, P(n) \Rightarrow P(n+1)] \Rightarrow \forall n \in \mathbb{N}, n \geq 1 \wedge P(n)$

But finally, an implication also made sense... $[\forall n \in \mathbb{N}, P(n) \Rightarrow P(n+1)] \Rightarrow \forall n \in \mathbb{N}, n \geq 1 \Rightarrow P(n)$

or

$[\forall n \in \mathbb{N}, (P(n) \wedge n \geq 1 \Rightarrow P(n+1))] \Rightarrow \forall n \in \mathbb{N}, n \geq 1 \Rightarrow P(n)$

Can you help me?

Answer 1

What we are essentially looking for is a formulation of the principle of induction.

As you probably know, the principle of induction consists of:

• A base step: $P(0)$ holds (or $P(1)$, or $P(n_0)$ for some appropriate base value $n_0$ -- in this case, $n_0 = 1$);
• An inductive step: $P(n)$ implies $P(n+1)$ for all $n \ge n_0$;
• The conclusion that $\forall n \ge n_0: P(n)$.

The first two are the premises, and the latter is the conclusion. Thus a correct and precise formulation of the principle of induction in symbolic form would be:

$$\Big(P(n_0) \land \forall n: n \ge n_0 \land P(n) \implies P(n+1)\Big) \implies \forall n: n \ge n_0 \implies P(n)$$

Of course, when $n_0$ is the smallest value in $\Bbb N$ ($0$ or $1$, depending on your convention), the $n \ge n_0$ part can be done away with.

---

Now to your suggestions, if we take the point of view that $0 \notin \Bbb N$, they are all equivalent (can you see what goes wrong with several of them if $0 \in \Bbb N$?).

However, all of them miss the critical premise that $P(1)$ holds.