Suppose that $ n\in\mathbb{N}$ with $n\neq0$. Show that $0\in n$. (Hint: if the set $X$ satisfies Peano's axioms, then every $x\in X$, other than $0_x$, is $S(y)$ for some $y\in x$. Also use induction.)

Here the base case clearly cannot be $0$ because $n\neq0$ and $0 \notin 0$. So the base case should start with 1?

My question is, is starting the base case with 1 legit? Because then the induction would cover only $\mathbb{N}-\{0\} $ instead of the entire natural number domain.

Base case with 1: $1=\varnothing \cup\{\varnothing\}$, thus $\varnothing\in1$.

Induction step: assume $\varnothing \in n$, show that $\varnothing \in n+1$.

$n+1=n\cup\{n\}=\forall x(x\in n\lor x\in\{n\})$. But inductive hypothesis shows that $\varnothing \in n$, therefore $\varnothing\in n\cup\{n\}$.


Your intuition is right - your base case is always the smallest value you want to use to start the induction chain, and when you prove the induction you are proving true for all values from that base case onwards. So here you would start with 1, and thus prove it true for $\mathbb{N} \setminus 0$.

(To step away from Peano for a moment, it's not hard to prove that induction from an arbitrary base case $z$ works because you can define a new proposition $P'(s) = P(s + z)$, i.e. you shift all the values so that the new proposition starts at 0 but is proving the same thing as the original one.)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.