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.

  • 5
    $\begingroup$ Possibly this is related: en.wikipedia.org/wiki/Transfinite_induction $\endgroup$ – Lopsy Dec 27 '11 at 19:43
  • $\begingroup$ 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. $\endgroup$ – 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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Dec 27 '11 at 22:34
  • $\begingroup$ My intentions are fully preserved. Thank you! $\endgroup$ – Michael Greinecker Dec 27 '11 at 22:36

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.