# Is Induction applicable only to well-ordered sets that are not bounded above?

I think the set needs to be bounded below to avoid occurrence of infinite descending chains for induction to be applicable but couldn't decide if it can be bounded above as well.

Inductive step is P(n) implies P(n+1). But if the set on which we are applying induction contains a greatest element, say a. And if P(a) is true then what can we say about P(a+1). I think induction would still be applicable whether or not a+1 belongs to the set.

I would really appreciate if an example could be provided in which induction is being applied on a set bounded above.

• It's funny that you bring up the transfinite-induction tag, as induction could be viewed as transfinite induction with an upper bound! – Theo Bendit Jan 26 '18 at 13:52

## 1 Answer

You're right: you can still do induction if a set has an upper bound ... you just need to be careful in your formulation of what it is that you prove with the step.

That is, if $a$ is your upper bound, then with the step you could say that what you are going to show is that: for all $0 \le n < a$: if $P(n)$ then $P(n+1)$