Can Strong Induction Be Used to Prove the Infinite Case

elementary-set-theory

I started real analysis and picked up a book called Understanding Analysis by Stephen Abbott. I understand why induction cannot be used prove the infinite case. From my understanding, induction proves that a statement is true for all natural numbers but not the infinite case because it only takes into consideration one case at a time (Is this correct?). Abbot uses the example $\bigcap^{n}_{i=1}A_i\ne \emptyset
$
while
$\bigcap^{\infty}_{i=1}A_i=\emptyset$ when $A_i$ is defined as a subset of $\mathbb{N}$ to show why induction would not work. Would strong induction suffice as a proof instead? What led me to this was how Abbott proved that for a set $A_n$=$\mathbb{N}\cap[n,\infty)$ and n $\in\mathbb{N}$, $\bigcap^{\infty}_{n=1}A_n=\emptyset$ using strong induction:

Suppose we had some natural number m which satisfies $m\in\bigcap^{\infty}_{n=1}A_n$. But since $m{\notin}A_{m+1}$, we have a contradiction so $\bigcap^{\infty}_{n=1}A_n=\emptyset$.

It seems as if strong induction uses all the previous cases to imply that the next case would be true so I was wondering if it would work for the infinite case. Apparently, transfinite induction extends to infinity which I learned from:

Why doesn't induction extend to infinity? (re: Fourier series)

and it seems very similar to strong induction such as the successor case which requires P($\alpha$) and sometimes P($\beta$) to be true for all $\beta\lt\alpha$ in order to prove P($\alpha$+1). This may be wrong though because I know nothing about ordinals. Here is the link: https://en.wikipedia.org/wiki/Transfinite_induction. Thank you for your time.

Best Answer

The proof that $\bigcap_{n\ge 1}A_n=\varnothing$ when $A_n=\Bbb N\cap[n,\to)$ doesn’t use induction at all. It’s clear that the intersection is a subset of $\Bbb N$, since each of the sets $A_n$ is, so to show that the intersection is empty, we need only show that it contains no element of $\Bbb N$. And that follows immediately from the definition of intersection: for any $k\in\Bbb N$, $k\notin A_{k+1}$, so $k\notin\bigcap_{n\ge 1}A_n$.

By the way, strong induction is equivalent to ordinary induction: anything that can be proved using one can be proved using the other, though converting a proof by strong induction to a proof by ordinary induction typically makes it a little more complicated.

Related Question