# Is it possible to iterate through an infinite set?

Is it coherent to suggest that it is possible to iterate, one-by-one, through every single item in an infinite set? Some have suggested that it is possible to iterate (or count) completely through an infinite set with no start (or lower bound), making infinite regress a genuinely possible reality.

Mathematically, is this possible?

I don't know much about math proofs, so the more basic (with the least symbols) you can keep your answer, the more likely I will understand and appreciate it.

Thank you very much!

When I write an infinite loop into my computer code, the code begins to execute and will never complete it's looping (unless it crashes or I stop it). I am wondering if it is mathematically possible, adding one to another, to ever arrive at the completion of an infinite set, like the set of negative integers, or will it continue permanently?

-
If the infinite set countable, i.e. in bijection with $\mathbb{N}$, then you can. For instance, if $X$ is an infinite set and if $f : \mathbb{N} \rightarrow X$ is a bijection, then $f(1), f(2), f(3), ..$ is an enumeration of $X$. –  William Sep 14 '12 at 1:37
Sets a priori have no order on them whatever, so no set has a "lower bound"; that is, until you give them additional structure. It is an axiom that every set can be endowed with an order in which it has such a "lower bound". –  Alex Becker Sep 14 '12 at 1:39
I guess you need to familiarize yourself with the concepts of countable sets and uncountable sets. –  user2468 Sep 14 '12 at 1:39
Using the axiom of choice, every set has an ordinal $\alpha$ which is in bijection with it. Let $f : \alpha \rightarrow X$ be such a bijection. $(f(\beta))_{\beta < \alpha}$ is an $\alpha$ enumeration of $X$. Although, I don't know if you would consider an enumeration of length $\omega_1$ to be "iterable". –  William Sep 14 '12 at 1:40
I apologize for not being clear. I wasn't wondering if it could be mapped to N. I was wondering if it could be completely iterated through. It seems like iterating through an infinite set would necessarily be ongoing and a permanent task. –  Tim Sep 14 '12 at 1:43

We may count through the integers by listing them $0,1,-1,2,-2,\dots$. This is an infinite set without a lower bound. In general, if you have a bijection $f:\mathbb{N} \to X$ where $X$ is an infinite set, then you can "iterate" through them by listing $f(1),f(2),f(3), \dots$.

-
Doing this would only start to list them. But since N is unbound topside, you would never complete a listing of them. You would start and then go and go forever. If you can map the set to N then the set cannot be completely iterated through as I mean in my question. I was wondering more about mapping to -N and coming all the way to 0, without ever "starting". I was wondering if iterating through such a set, from negative infinity to 0, presented any mathematical impossibilities. –  Tim Sep 14 '12 at 11:49

Here is a way to iterate... To me, it is like mixing math and computers. You can find the ideas described in much more detail in Generatingfunctionology by Wilf. Knowing Calculus is very helpful for this.

Let me explain. We would like to iterate through infinity and stop. To do this, we will use a function that is like a set. It is called a "generating function". You can find a description in more advanced English here. The idea is that we use numbers (integers) to give order to the set. (This makes it a sequence). We start with the number 0 (like people often do with computers) and give it a value from the set. Suppose we give it the value 53. Then we say this as a generating function by saying $f(x)$, our function of $x$, is equal to $53 x^0$:

$$f(x) = 53x^0$$

It is like a power series, if you are familiar with calculus. We raise $x$ to the 0th power, and then multiply it by 53. If we want to add a second number, say 42, we use $x$ to the first power:

$$f(x) = 53 x^0 + 42 x^1$$

The idea is that the powers of $x$ let us order the numbers. This also helps us seperate the numbers. If we add the numbers 8, 71, and 32, can you guess how to write this? The answer is:

$$f(x) = 53x^0 + 42x^1 + 8x^2 + 71x^3 + 32x^4$$

I hope this idea is clear. Now we want to create an infinite series. To do this, many people study power series. Many Calculus books study these. For example, a common one is:

$$f(x) = 1x^0 + 1x^1 + 1x^2 + 1x^3 + \dots$$

This is an like an infinite set of ones. It can be written as:

$$\frac{1}{1-x} = 1x^0 + 1x^1 + 1x^2 + 1x^3 + \dots$$

This means that the fraction on the left side is the same as the right side of the equals sign.

They are a function. The type of function is again a generating function.

The series of ones was given as:

$$\frac{1}{1-x} = 1x^0 + 1x^1 + 1x^2 + 1x^3 + \dots$$

Set $x$ to some value, and you will have iterated through an infinite amount of values. The result may be somewhat suprising, so I'll leave it up to you to pick a value. Remember that you can't divide by zero, so you'll have to be careful to avoid that. The study of Calculus and, in particular, limits helps provide a solution to that problem.

-