Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
A child asked me this question yesterday:
Would it be faster to count to the infinite going one by one or two by two?
And I was split with two answers:
Which brings me this question:
Could an infinite be greater than another one?
YES and NO.
Galileo made the "discovery", the so-called Galileo's paradox, that if you start with the succession of natural numbers:
$1, 2, 3, ...$
and you map it into the succession of even numbers :
$2, 4, 6, ...$
you may map (i.e.associate) every number into its double (today, we call it one-to-one mapping).
So, you have the same "number" of numbers and of even numbers.
Modern set theory (from Cantor on) solved the paradox extending the "counting" process to infinite sets, but proving that the euclidean common notion that "The whole is greater than the part" [see Euclid, The Elements, trans T.L.Heath, Dover, Common notions 5] will not hold for an infinite set.
According to modern set theory, the two above sets can be put in one-to-one correspondence, so they have the same cardinal number, and their "type" of infinity is called denumerable (a set is called denumerable exactly when it can be put in one-to-one correspondence with the set of natural numbers).
But, again by a result of Cantor, not all infinite sets can be put in one-to-one correspondence: there are infinite sets "more infinite" than another. A set of "a larger kind" of infinity is the set of real numbers; it is not denumerable, in the meaning defined above.
As for counting "faster": of course, if you count two by two, after a while you will be way "ahead" of your friend that is counting by one. The only problem is that you will not "end" before him, because there is no final goal to be reached!
Fast or slow has to do with speed. So, if you properly define speed, and if you assume additional hypothesis, like "one count per second", then you can say that counting two by two is faster.
In fact, if you count one by one, then you will count one number per second. If you count two by two, it will be two counts per second. And since $2 > 1$, two by two is faster.
After you two agree that two by two is faster, the kid should be able to realize that this isn't exactly what s/he wanted to ask. As the kid rephrases the question, s/he should get closer and closer to being able to answer by perself. My conclusion is:
Two by two is faster, but it is kind of "useless", since you will not be able to finish anyway.
Asking questions is more important then answering them.
Contrary to the common layman assumption, there is no unique context in which mathematics is being done. Words, especially coming from natural language, can be interpreted in different ways when changing the context.
In this case, the word "faster" can be interpreted in different ways, and it will affect the answer.
"Faster" as a real valued limit. We can think about this as two functions, $f(n)=n$ and $g(n)=2n$. These can be thought as sequences of real numbers, and we can ask whether or not one sequence dominates the other, and what is the limit of their ratios? $$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\frac12$$ Since $\frac12<1$ we have that indeed $g$ is the faster sequence.
"Faster" as a computational process. This is similar to the above case, we define two sequences and calculate the limit of their ratios. However this time we say that if the ratio is a positive (but finite!) constant, then they are more or less the same speed. In this case both sequences have the same "speed".
"Faster" as a set theoretic process (cardinality). This is not similar to the two cases above, in this case we only measure the cardinality of the output of the sequence. We can ask whether or not the cardinality, which is the rawest notion of "size" for sets, of the two sets $\Bbb N$ and $\{2n\mid n\in\Bbb N\}$ are the same, despite one being a proper subset of the other.
The answer here is that the cardinality is the same, because there is a bijection between the two sets, indeed $g(n)=2n$ is this bijection. So the two methods of counting end up having the same "speed" again.
There are definitely more ways to define which sets go "faster" to infinity. And the result will definitely change from one context to another. The point is that there are different ways we can measure how fast a particular set of integers, or a sequence if you will, thins out as it grows, and it is useful to consider different ways in different contexts.
If you want to explain to a child about the importance of context in which a term is interpreted, ask them what it is easier to carry a $5\ \rm kg$ of iron cast into one block, or a balloon containing $1\ \rm kg$ of air which is huge ($0.85\rm m^3$ in volume). While the iron is definitely heavier, the balloon is definitely much larger and more difficult to handle.
So carrying it by hand makes the iron easier to carry. But if you have a cart on which you can put both objects, then the balloon is much easier to carry because you are pulling a lighter object and you have to put less effort into that.
Therefore there are two ways to interpret "easier to carry" and they depend on the the tools that you have, and so "faster" in mathematics depends on the context in which you are asking the question.
Show your kid this table: $$\begin{matrix} 1&2&3&4&5&6&7\\ \hline 2&4&6&8&10&12&14 \end{matrix}$$ Now let him decide which counting takes longer ...
To answer this, lets try to think like a child and find:
Ironically, counting two by two should be actually slower!
If you count up to the $N$th element of the corresponding sequences ($\mathbb{N}$ and $2\mathbb{N}$), we observe the following pattern: the more digits the number has the longer it takes to spell it.
Take for example $N=8$, the time you need to spell
"one, two, three, four, five, six, seven, eight"
is considerably shorter than the time you need to spell
"two, four, six, eight, ten, twelve, fourteen, sixteen".
One can imagine that this holds true for "most" of the $N$, so skipping the odd numbers will be slower.
Of course, this is far away from a mathematical proof, but probably a child would like the way of thinking. One could bring up the whole Cantor/countability problem at a later point in time, for example after clarifying what we mean by "count".
I did not attempt to prove this "claim". :-) Maybe one can find a subsequence that, after fixing the counting times for the digits, has longer counting times in the first version, who knows...
EDIT: If we represent the numbers with their binary coefficients (for example $(0,1,0,\ldots)$ for 2) and if we assume that one neets equal amounts of time for each syllable we have that the time $\ell((0,1,0,\ldots))$ it needs spell the binary number is $3$: $1$ for "one" and $2$ for "ze-ro". So if we spell $a_n = n$ in its binary representation it takes $\ell(a_n)$ time to do so. Since multiplication by two corresponds to a shift in binary space (add a zero) we have $\ell(b_n)=\ell(2a_n)=\ell(a_n)+2 > \ell(a_n)$. Therefore it always takes longer to spell the even sequence. Asymptotically, of course, the speed is the same: $\frac{\ell(b_n)}{\ell(a_n)}=1+\frac{2}{\ell(a_n)} \rightarrow 1$ as $n \rightarrow \infty.$ A fun fact is, that this is independent of the language. Just replace the number $2$ by the number of syllables used for $0$. :-)
Counting by $2$s, you'll reach any finite number faster. But in either case you will never reach $\infty$. Putting it this way validates the feeling that counting by $2$s should be faster without violating the mathematics of the infinite.
This makes a nice puzzle for young people interested in infinity.
Consider a hypothetical hotel with infinite rooms, all of them occupied.
An extra guest arrives. Can you accomodate him?
A neighboring, infinite hotel burned down. An infinite number of guests arrive. Can you accomodate all of them?
Infinitely many buses with infinitely many guests arrive. Can you accomodate all of them?
The answer each time is yes, you can assign each existing guest and each new guest a unique room number. The existing guests have to move to a new room each, though.
All of these sets are countable infinite, aka $\aleph_0$, Aleph-naught. See: Aleph number
Things get messy once you try to enumerate an infinite number of infinite subsets. As long as you have finite sets, you can encode each set using a $2^n$ binary number; which obviously is a unique mapping from integers to finite subsets. Once you want to be able to also accomodate any infinite subset in your enumeration - i.e. have a mapping from each infinite set to a finite number - things get, well, impossible. Roughly, by the same argument that the rational numbers are not equivalent to the irrational numbers. (You may want to read up on Cantor for this, around 1874). So in the end, it boils down to: why is pi not finite, e.g. the question: Pi might contain all finite sets, can it also contain infinite sets?
I.e. it's about rational vs. irrational numbers. Counting to infinity going by one or two just means counting in a different basis; but you will still miss $\pi$ and almost every other irrational number.
The answer to the final question "can one infinite [quantity] be greater than another" is positive (there are many degrees of infinity in set theory), but that is not what the question is about. The question about going to infinity is similar to the question "would it be faster to travel to the moon on foot or by train?". The point is, although going by train is "faster" in terms of speed, it is not so in terms of reaching the goal: neither method will ever attain the goal that was set, so it is pointless to claim that one method gets there faster than the other. It is only a figment of our mental representation of infinity that we can approach infinity by going to ever larger numbers; doing so, we still remain infinitely distant from our target at all times.
It is the same question as "which set is bigger, the natural numbers or the even numbers?"
Two sets $A$ and $B$ have same number of elements if there exists reversible transformation between those sets. In this case this transformation is simple:
$$f(x) = 2x$$
Hence both sets have the same cardinality.
Is it faster to count to the infinite going one by one or two by two?
Since neither method will actually help you reach your destination, the question is meaningless. “To travel faster” and to “travel faster towards a specific destination” are two completely different things For instance, a man flying by plane travels faster than one going there by boat, but it's obvious that neither method of transportation will take either one of them faster to the Moon, for instance.
Feynman had a nice approach to this. He bet a child of a friend of his that there were "twice as many numbers as there are numbers." He told the kid to pick a number (young enough that only integers mattered). Kid says "six," Feynman says "twelve." etc.
In this case, the child was bright enough to come right back and say, "Hey Mr. Feynman, I bet there are three times as many numbers as there are numbers."
You can't count to $\omega$, you can only count towards $\omega$.
(Here, I am using $\omega$ to refer to the smallest infinite ordinal number. Don't make the mistake of confusing it with the cardinal number $\aleph_0$ or the extended real number $\infty$!)
The two counting procedures you indicate never reach $\infty$. After one step, the first procedure has reached $1$, and the second has reached $2$. After a thousand steps, the first procedure has reached $1000$, and the second has reached $2000$. After a trillion steps, the first procedure has reached $1,000,000,000,000$ and the second has reached $2,000,000,000,000$.
The point is, each step in your counting procedure is a natural number of steps away from the starting point. As such, the number you have reached at any step cannot be $\omega$!
The problem is that when you define an algorithm of the sort
that can only get you as far as natural numbers. If you want to "count" further, or more generally talk about any other transfinite process, you need to include a second rule. A typical one is to have the steps of your transfinite process labelled by ordinal numbers, and then include a rule of the sort
For example, when counting by ones, [something else] might be "move onto the smallest ordinal you haven't reached or passed yet". In that case, at step $\omega$, you have counted to $\omega$. Then at step $\omega + 1$ you've counted to $\omega + 1$ and continue on.
But when counting by twos' you might use the same [something else]. Then at step $\omega$, you've still only reached $\omega$, since prior to $\omega$ -- i.e. at the finitely-numbered steps -- you've only reached natural numbers! But then you continue counting by $2$ and at step $\omega + 1$, you've reached $\omega + 2$, then $\omega + 4$, and so forth.
Actually, there's another gotcha: when you said you were counting by $1$'s, you thought you were counting natural numbers. But $\omega$ isn't a natural number: what does it mean to count by one or by two from $\omega$? It does make sense to continue on to the next ordinal number from there to count by ones (i.e. adding by one on the right: if you care to learn arithmetic of ordinals, note that $1 + \omega = \omega \neq \omega + 1$), and skipping every other successive ordinal to count by twos. I've assumed that's what you do in the above paragraphs.
Of course, don't try to do this in the "real world" in any fashion where you have to spend one unit of time per step -- there aren't enough units of time to reach $\omega$! Other fashions are possible, though: e.g. the description of events in Zeno's paradox can be continued by setting step $\omega$ to be where Achilles has actually reached the finish line.
Another common means of passing to the transfinite is taken in geometry / analysis, by adding points "at infinity". e.g. the numbers $+\infty$ and $-\infty$ that are the endpoints of the extended real line. When we have a function defined for real numbers like $\arctan x$ or $1/x$, and the function has limits at $+\infty$, it is customary to extended the function by continuity to have the limiting value. e.g. $\arctan(+\infty) = \pi/2$ or $1/(+\infty) = 0$. But this method is mostly unrelated to discrete processes like counting or executing algorithms one step at a time.
Maybe the trouble is how we imagine infinity. If you imagine it as say the vanishing point on the horizon (or a distant star etc, i.e. just a really big finite number), then skipping half is faster. How about imagining it as a moving target? I.e. a bit bigger than whatever number you like.
E.g. you could say "to count to infinity we have to count to at least 10 more than we've already counted". Then whether you skip half or not, your target still stretches out of reach just as quickly.
The original question was turned into a definition of infinity by Dedekind.
In his Was sind und was sollen die Zahlen? of 1888, Dedekind defined infinite sets in paragraph 64:
A set is said to be infinite when it is similar [in bijection with] to a proper subset of itself, otherwise it is said to be finite.
Dedekind’s footnote to this definition contains some important historical notes.
In this form I submitted the definition of the infinite which forms the core of my whole investigation in September, 1882, to G. Cantor and several years earlier to Schwarz and Weber. All other attempts that have come to my knowledge to distinguish the infinite from the finite seem to me to have met with so little success that I think I may be permitted to forego any criticism of them.
Thus, being able to count the even integers shows, according to Dedekind's definition, that the set of all integers is infinite.
Notes on Richard Dedekind’s Was sind und was sollen die Zahlen?
Since you never reach an end, speed is not of importance. You don't have strictly defined end point of what you are counting, so you won't be able to compare both approaches.
My answer is that it won't be faster, the counting will never end and you won't be able to decide.
The only thing that you may be sure (besides it will be a waste of time) is that, using the second method, at any given point you have skipped twice as many numbers.
Maybe you can answer it by saying:
Suppose you and I go to another planet and start walking around its equator. And keep walking forever. I have longer legs, so I will take steps twice as long as yours. So I will walk twice as fast as you. Which one of us will reach the end first?
This helps link the mysterious infinity with a more everyday concept.
Yes, infinities come in different sizes (not exactly sizes), but...
No, counting by twos isn't faster: Comparing different methods of counting to infinity is like a race to an unreachable place. If you can't ever get there, it doesn't matter how fast you go.
This answer is not meant to seriously attempt to solve the question, but to show that the question has plethora of answers because its (mathematical) context is ill-defined.
Assume that Alice and Bob walk on the road $\mathbb N = \{0,1,2,\dots\}$ : each second, Alice move from its place $a$ to $a+1$, while Bob moves from its place $b$ to $b+2$. Now, I will (arbitrary, but irrevocably) said that X moves faster than Y if, at the same second, the distance between $X$ and $0$ is greather than the distance between $Y$ and $0$. Seems legit.
But wait, what is the distance between one's place and $0$ ? Well, for the sake of my point (see the first sentence of the post) and because one always likes being the centre of everything, I decide to norm $\mathbb N$ by the $2$-adic distance : that is the distance between $n$ and $0$ is $$ |n|_2 = 2^{-\nu_2(n)} $$ where $\nu_2(n)$ is the exponent of $2$ in the prime decomposition of $n$. (You can go ahead and verified that this respects what we want of a distance : the distance between $0$ and $0$ is $0$, the distance between $n + m$ and $0$ is less than the one between $0$ and $n$ added with the one between $0$ and $m$.)
So now, after $n$ seconds, Alice is in place $n$ while Bob is in place $2n$. I let you verify that $|2n|_2 = \frac 1 2 |n|_2$. So it seems that in those $n$ seconds, Alice made double the distance Bob did. Hence counting one by one is faster than $2$ by $2$.
Infinity isn't a number. This is why there is so much confusion and "paradoxes" associated with it. It is treated as a number, yet it is NOT a number, but rather it is an indicator of an unending sequence of numbers (like the asterisk in "1/3 = 0.3*"). Counting to infinity is meaningless because it is akin to measuring the distance a javelin is thrown while it is still flying through the air.
Doesn't matter whether you use centimeters or meters, you can't measure the distance because the total distance hasn't been traversed yet. Only once the javelin falls to the ground can you start measuring. But if it carries on flying infinitely, you might as well have a cup of tea.
You can form a bijection from the set of all positive integers to a set of all even integers. If infinity were a quantity, then infinity would map to infinity. Mathematically then you'd reach infinity at the same time.
"Could an infinite be greater than another one?"
YES, and in more than one sense!
Many answers pointed out cardinality, i.e. a way to define size between sets, mathematical objects with no other structure than the relationship $x\in y$. This is defined by function injection. If you can map uniquely members of one set into another, the former is smaller than the latest. And if you can do it both ways, they are equal in size.
And one answer above brought another possible way to define bigger: ordinals. Ordinal size is different. $\omega$ is the ordinal corresponding to our intuitive notion of counting, one number after another; although it is defined by the concept of total ordering, and order where every subset has a least element. Here, you need little more structure, $x\in y$ and $x < y$ to workout this definition of size.
So, with ordinals you can have the full sequence of numbers 1, 2, 3, one after another, very well ordered; call it $\omega$. Now, and just because you like it, put the same sequence afterwards as if you were able to finish counting the first one (here the paradox of Achilles and the tortoise may help), then you start counting again. How fun is that?! And you have $\omega + \omega$, repeat this $\omega$ times and, yes, you got it $\omega * \omega$ = $\omega^2$, and repeat and repeat, $\omega^\omega$, $\omega^{\omega^\omega}$ and then you got all sort of infinities, one smaller than the other, without leaving the cardinality of $N$.
So, in mathematics one encounters infinity in different ways; counting as you said, and I already pointed out two possible ways to look at counting. But you have the infinity $\infty$ one see in calculus, which can be treated formally using, for example, non standard analysis which requires lot more structure to work through.
So, I know that this will be harder to explain to a little kid, but what's infinity depends on how you look and compare size; and different ways of looking gives you different infinities. Maths is fun!
Counting out all the numbers and counting out only the even numbers, gets you to infinity equally quickly, so says function growth analysis.
In big-O notation we have the following definition
$$ O(f) = \{ g : \mathbb N \to \mathbb R \mid \exists n_0 > 0,\, k > 0 \;\forall n > n_0 \,.\, | g(n) | \le k| f(n)| \}$$
"Big-O of a function f is the set of all functions ($g$s), which f, multiplied by a constant ($k$), will eventually ($n_0$) overtake in magnitude."
That is, if we compare $f(n) = n$ and $g(n) = 2n$, we see that $f \in O(g)$ because $ |g(1)| = 2 \le 3 = 3|f(1)| $ but also $ g \in O(f) $ becuase $ |f(1)| = 1 \ge 2 = 1|g(1)|$.
Therefore the functions $f(n) = n$ and $g(n) = 2n$ grow equally fast.
