0
$\begingroup$

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.

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

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)$

$\endgroup$

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.