0
$\begingroup$

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!

ADDENDUM

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?

  • 0
    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$.2012-09-14
  • 1
    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".2012-09-14
  • 0
    I guess you need to familiarize yourself with the concepts of [countable sets](http://en.wikipedia.org/wiki/Countable_set) and [uncountable sets](http://en.wikipedia.org/wiki/Uncountable_set).2012-09-14
  • 0
    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".2012-09-14
  • 0
    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.2012-09-14
  • 0
    @Tim: that depends on what you mean by "iterated through". As suggested by William, assuming axiom of choice we can use well-ordering principle to "iterate through" an arbitrary set in the sense that we can use transfinite induction and/or recursion to do something with it or show something about it. But you certainly can't "iterate through" an infinite set in a finite number of steps.2012-09-14
  • 0
    I seems that completely iterating through seems to be a mapping from $\mathbb{N}$ to your set. When you iterate, there is a first thing, a second thing, third thing ... This is exactly what $f(1), f(2), f(3), ...$ means.2012-09-14
  • 0
    @Tim Are you thinking of things like mathematical induction, where we show that, where P(n) is a proposition about the number n, if P(1) is true and we show that P(k) implies P(k+1), then we've shown that P(n) holds for every n in \mathbb{N}? There is a sense in which that sort of a proof invokes the idea of iteration over an infinite set.2012-09-14
  • 0
    I was not. I realize it can be demonstrated mathematically that certain characteristics apply to every item in a set, without actually "touching" every item. I was wondering more if it were actually possible to "touch" every single item in an infinite set, one after another. Perhaps a physics or philosophy forum would be a better place to pursue this... Thanks everyone!2012-09-14

2 Answers 2

1

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

  • 0
    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.2012-09-14
0

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.