Connecting elements in the set of Natural numbers

Question

Lets say we "connect" two numbers in the set of Natural numbers in a way, that we draw an arrow between them. In each step we draw an arrow from a number to the number which is next to it. If we drew an arrow from a number to another we don't draw another one from the number we arrived in the same step.

Example: 1 2 3 4 5 6 7 8 ...

First step: 1->2 3->4 5->6 7->8 ... (since we connected 1 and 2 from 2 draw a line in this step)

Second step 1->2->3->4 5->6->7->8 ... (since we connected 2 and 3 we dont draw a line from 4 in this step)

Third step 1->2->3->4->5->6->7->8 ... (since we connected 4 and 5 we dont draw a line from 8 in this step)

So my question is: If we keep connecting the numbers in this way infinite amount of times, than will they ever connect into one single line or not?

Personally I don't think they ever will, since after every step there will be a number which isn't connected to another number. However if we repeat this infinite amount of times, than that would mean that at some point we reach every number so this way maybe they will connect to a single line. I would really appriciate any help to clarify this.

Answer 1

Yes, all numbers will end up on a single line starting at 1.

We can use induction to prove this.

Inductive Base: It is trivial that $1$ will be on a line starting with $1$

Inductive Step: Suppose $n$ will be on a line starting with $1$. Then if $n+1$ is not already on a line starting with $1$, then an arrow is guaranteed to be drawn between $n$ and $n+1$, since that is the first possible arrow to be drawn given the defined process of drawing arrows. So, if $n$ will be on a line starting with $1$, then $n+1$ will be on a line starting with $1$ as well.

Answer 2

The short answer to your specific question is: yes, at the end all the numbers are connected in a single line.

You are concerned:

after every step there will be a number which isn't connected to another number

And you are right to be concerned. This is the paradox of infinity. This has been one of the central concerns of mathematics for at least 2500 years.

Examples of this appear over and over:

1. In Zeno's paradox, the speedy warrior Achilles is racing against a tortoise. The tortoise has a ten-meter head start. After one second, Achilles has run 10m, but the tortoise has moved on so it is still ahead of him by a meter. It takes Achilles 0.1 second to catch up, but the tortoise has already moved another 100 cm. Achilles can catch up to where the tortoise was in another 0.01 second, but by then the tortoise is still 10cm ahead. The tortoise is always ahead, and Achilles never catches up! Except, of course, we know that he really does because Achilles is much faster than a tortoise.

2. Each of the sets $\{1\}, \{1,2\}, \{1,2,3\}, \ldots$ is finite. But their union is infinite.

3. Consider the sequence $1,\frac12,\frac13,\frac14\ldots$. Every element of this sequence is positive. But when you follow it to infinity, you end at $0$, which is not positive.

4. Consider the numbers from $1$ through $n$. If we try to match each number with its square, most of the numbers are unmatched. For example, in $1\dots 20$ the four numbers $1,2,3,4$ can be matched with their squares $1, 4, 9, 16$, but the numbers $5 \ldots 20$ can't be matched with squares. $80\%$ of the numbers didn't get matched, and only $20\%$ had matches. As we let $n$ grow larger, the fraction of matched numbers approaches zero. When $n=10000$ only $1\%$ of numbers are matched with their squares. But somehow when $n$ reaches infinity, every number can be matched with its square. (This is Galileo's paradox.)

5. Take a bag; in the bag is a marble with the number $1$. Every minute, take out the marble with the smallest number $n$, throw it away, and put in marbles with numbers $2n$ and $2n+1$. So after one second, take out marble $1$ and put in $2$ and $3$; next take out marble $2$ and put in $4$ and $5$, and so on. The number of marbles in the bag is always increasing. But after an infinite number of steps, the bag is empty, because every marble is taken out of the bag and thrown away. (This is the Ross–Littlewood paradox, very similar to your connected-graph example.)

6. Consider the process which takes a fraction $\frac ab$ and replaces it with $\frac{a+2b}{a+b}$. Start with $\frac 01$. This is replaced with $\frac{0+2}{0+1} = \frac 21$, which is replaced with $\frac{2+4}{2+1} = \frac 43$, and so on: $\frac 43\to \frac{10}7 \to\frac{24}{17}\to\frac{58}{41}\to\ldots$. Every element of this sequence is a rational number. But the end result is not. (It is $\sqrt 2$.) We are used to this now, but when it was first discovered it was considered extremely strange.

7. Think of a computer program $P_1$ where I put in one number and it computes some function and prints out a result. And suppose I can be certain that if I wait long enough, the program will always finish and print its result. Now suppose I have a family or programs $P_1, P_2, \ldots$ and I need answers from all of them. If the family is finite, there's no problem; I can wait until they all finish. But if it is infinite, this doesn't work. Even though every program finishes on its own, there might never be a time when they have all finished.

8. The Cantor Set is a famous example in topology. We take the set of numbers $x$ where $0\le x\le 1$. Then we remove the middle third of the set, leaving $0\le x\le \frac 13$ and $\frac23\le x\le 1$. Then we remove the middle third of each of those two parts, leaving $0\le x\le \frac19$ and $\frac29\le x\le\frac 13$ on the left and $\frac23\le x \le\frac79$ and $\frac89\le x\le 1$ on the right. We keep doing that forever. Every set along the way is a collection of connected intervals. But the Cantor set itself, the endpoint of this process, does not contain any connected interval.

This kind of “limiting” process is everywhere in mathematics and a large part of mathematics concerns how it works, when it makes sense and when it doesn't, and what the result is. It's the main idea of calculus, and understanding how it worked just in calculus took 200 years.

Good questions are the ones that are short to ask but long to answer. This is a great question.