# Infinite induction “valid”

As you may know, induction works only when we have a statement involving natural numbers. For instance,

For every $n$, the intersection of $n$ open sets is open.

Now, the corresponding statement for infinite (here infinite means countable, not uncountable) intersection that is false; e.g., $\bigcap_{n \in \mathbb{N}} (-1/n,1/n) = \{0\}$.

I want to know if there are any equalities that are preserved following transferring from finite to infinite that you know about?

I've left this vague to attract wider responses.

• Possibly this is related: en.wikipedia.org/wiki/Transfinite_induction – Lopsy Dec 27 '11 at 19:43
• It's not clear what you mean by an "equality." The example you give before-hand is not an equality under any reasonable definition of the term. – Thomas Andrews Dec 27 '11 at 20:03

There is a top-down approach to induction that works in a very general setting. Let $\Omega$ be a set and $f:\Omega^I\to\Omega$ be a function (what I say generalizes to having many such functions) where $I$ is a nonempty set and $\Omega^I$ the set of all functions from $I$ to $\Omega$. If $I=\{1,2\}$, $f$ is essentially a binary operation. But there are also infinitary operations. We can write infinite sums of nonnegative real numbers together with "infinity" this way. Let $\Omega$ consist of all nonnegative real numbers and $I=\mathbb{N}$ we let $f(x_1,x_2,x_3,\ldots)=\sum_{n=1}^\infty x_n$. In this case $f$ is an "infinitary" operation.

Now let $S\subseteq \Omega$ be a set in which each element has a certain property $P$ and let $f$ be such that whenever $x_i$ has the property $P$ for all $P$, then $f\big((x_i)\big)$ has property $P$. Now let $\mathcal{C}$ be the collection of all subsets $C$ of $\Omega$ such that $f$ restricted to $C^I$ has only values in $C$. The collection $\mathcal{C}$ is nonempty since $\Omega\in\mathcal{C}$. Let $S^*$ be the intersection of all sets in $C$ that contain $S$. Then all elements of $S^*$ have property $P$.

This kind of argument is often easier than using transfinite induction directly and can be justified by transfinite induction.

To see that it is a form of induction, let $\Omega=\mathbb{R}$, $I=\{1\}$ and $f$ be given by $f(r)=r+1$. So $\mathcal{C}$ consists of all sets of real number such that they contain with every number the same number plus one. Now let $S=\{1\}$. Then $S^*=\mathbb{N}$! So if we have a property that holds for $1$ and such that if it holds for $n$, it holds also for $n+1$, it holds for all of $\mathbb{N}$.

Let’s do an easy infinite induction. Let $\Omega$ again be the set of all real numbers together with infinity, $f$ be infinite summation and let $S=\{2\}$. Every element in $S$ has the property of being larger than one. Now if $x_1,x_2,\ldots$ are larger than one, then $\sum_{n=1}^\infty x_n$ is larger than one. So $S^*=\{2,\infty\}$ has indeed the property that all elements are larger than one.

The approach outlined is intimately related to Moore closures.

• There were a couple of bad typos in the mathematics, and I fixed a couple of non-mathematical typos as well; please check to make sure that I didn’t change your intention anywhere. – Brian M. Scott Dec 27 '11 at 22:34
• My intentions are fully preserved. Thank you! – Michael Greinecker Dec 27 '11 at 22:36