# Is it faster to count to the infinite going one by one or two by two? [closed]

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:

• In both case it will take an infinite time.
• Skipping half of the number should be really faster.

Which brings me this question:

Could an infinite be greater than another one?

-

## closed as too broad by Zev Chonoles, Thomas Andrews, Asaf Karagila, apnorton, Tobias KildetoftFeb 7 '14 at 8:14

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

It almost like comparing $\infty$ and $\frac{\infty}{2}$ both of which are infinity. You can never compare infinity with another infinity as you do not exactly know what it is. – lsp Feb 3 '14 at 10:17
so to finalize this question,simple talk to child that there is no different,because infinity is not number – dato datuashvili Feb 3 '14 at 10:26
You then could ask a follow-up question: what is faster, counting one-by-one, or, counting all the odd numbers first, and after that counting all the even (i.e. $\omega$ versus $\omega+\omega$)? – dtldarek Feb 3 '14 at 11:38
After each counting step your distance to the goal $\infty$ equals $\infty$ itself and stays constant, so in both cases your speed is zero :) – flonk Feb 3 '14 at 15:30
I recommend that any kid who has this question, should read The Phantom Tollbooth. Then again, I recommend that any kid at all read The Phantom Tollbooth, but in any case, it has a great chapter on exactly this concept. (Though sadly, it doesn't introduce the concept of different cardinalities. It totally should have.) – neminem Feb 3 '14 at 23:23

YES and NO.

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

-
+1 For the proper and simple mathematical explanation, and a wonderful conclusion! – Sawarnik Feb 3 '14 at 15:39
Another word for "denumerable" is "countable". You might encounter the terms "countably infinite" and "uncountably infinite" in your travels. – Arkamis Feb 3 '14 at 16:32
Note that it is not necessarily the case that the real numbers are of "the second type" of infinity. The cardinality of the continuum is not definitively known. The notion that |\mathbb{R}|=\aleph_1$is called the continuum hypothesis, which is in fact independent of ZFC. – JSQuareD Feb 3 '14 at 17:29 @MauroALLEGRANZA I'm not saying you should go into the specifics here, but it's certainly worth it trying to avoid such inaccuracies when possible. Overall, I think you wrote a very clear and accessible answer :) – JSQuareD Feb 3 '14 at 17:35 @JSQuareD I don't really see what you are objecting to. Regardless of the CH, the reals have a strictly larger cardinality than the natural numbers. I don't see even in an edited version where anyone made a claim that is equivalent to the CH – Tim Seguine Feb 4 '14 at 8:43 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 ... - And he'll certainly pick the second one but he'll be wrong... – Thomas Feb 3 '14 at 10:51 I saw that kind of table as a fifth grader and even now, some decades later I remember the astonishment I've felt at that moment: I substituted$x\to2x$by$x\to3x$and even by$x\to100x$and my astonishment grew even more. – Michael Hoppe Feb 3 '14 at 13:42 I was even more astonished when the math teacher demonstrated that card(N) == card(Z) by drawing a path that numerates the fractions on a 2d board. – njzk2 Feb 3 '14 at 18:40 @njzk2 You're right, but after my experience I was not surprised that card(Q)=card(N). – Michael Hoppe Feb 3 '14 at 18:45 @njzk2 My teacher drew 2 lines on the board. One longer than the other. Then started picking points on one, and mapping it to the corresponding point in the other line. It quickly became clear that, for each point in either line, there is EXACTLY one matching point in the other line. (this is more akin to the example in this answer, not Q vs. N) – Cruncher Feb 3 '14 at 19:24 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. - You point at (one of) the idea of infinity : counting is basically "adding one", and you can always "win" playing the game of askin to the child : "think to a big number !" and then answer with : "+1 !". – Mauro ALLEGRANZA Feb 3 '14 at 13:43 @MauroALLEGRANZA I remember when me and my friends first learned of the concept of different aleph numbers. Suddenly, instead of it going, "I hate you!", "I hate you times a hundred!", "I hate you times infinity!", and nobody being able to top that, suddenly it was all, "I hate you times aleph-1!" "I hate you times aleph-infinity!" "I hate times aleph-infinity to the aleph-infinity!" (Cause that last one totally makes any sense. :D) – neminem Feb 3 '14 at 23:21 @neminem - ... and this is the heart of "our problem" with infinite; we don not know it, we have a lot of problem (paradoxes) thinking to it, centuries of philosophical reflections did not tame it ... but it is "with us" from the beginning, form the first days when we learn to speak (becuase, the "recursive" process of producing an unlimited number of sentences starting from few basic building blocks is related to counting) and to count. – Mauro ALLEGRANZA Feb 4 '14 at 7:26 @Mauro: Actually, centuries of philosophical reflections did tame it: philosophers are generally satisfied these days that mathematicians have figured out how to treat the concept properly. IMO the biggest problem is all the misinformation out there. – Hurkyl Feb 4 '14 at 22:24 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. - If we define it in terms of speed, then it does not matter whether we start counting at -1, 0, 1, or INFINITY-100 - if we allow that. – emory Feb 3 '14 at 14:42 @emory: Does it matter for you? Then you should rephrase... ;-) – André Caldas Feb 3 '14 at 15:00 I just realized I am not answering the question posed! Well... I like my answer anyway... :-) – André Caldas Feb 3 '14 at 15:10 I think this is the best answer, and it can be summed up as "speed is not dependent on a destination". There's no need to complicate it beyond that simple fact, which may be all the kid really needs in order to reach clarity. – nmclean Feb 3 '14 at 15:10 @njzk2: I think in this question, the kid doesn't even know exactly what s/he wants to know. There might be concurring concepts that work just well in the finite case, but are incompatible in the infinite case. The first thing to do is realize that. One must realize the definitions are not that obvious and s/he doesn't really know what s/he is talking about. – André Caldas Feb 4 '14 at 0:00 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. - 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. - That's if the finite number is even. If it's odd you'll skip over it. – Zaid Masud Feb 3 '14 at 14:46 @Zaid I'm using "reaching it" in a greater-than-or-equal-to sense. – alex.jordan Feb 3 '14 at 14:55 As in, "the population of the planet has reached 7 billion". That statement in everyday English means that the population is currently at or over 7 billion. – alex.jordan Feb 3 '14 at 15:56 Such language hawks :) I'd also skip over any numbers that are irrational. Should I specify that too? I still maintain that you can reach something by going past it. If twins were born at the exact same time, taking the world population from$6{,}999{,}999{,}999$to$7{,}000{,}000{,}001$, could I say that the population had never reached 7 billion? – alex.jordan Feb 3 '14 at 22:43 This is a good answer. Correct, but still accessible to a child. – Beska Feb 4 '14 at 3:00 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. - I tried to add the asterisk, but apparently it doesn't show on SE. – Juann Strauss Feb 3 '14 at 14:48 +1 and back at 0! – Pinch Feb 3 '14 at 15:08 The javelin analogy doesn't work at all. When you fly in a plane, you can get the seat-back TV screen to tell you how far you are from your start point, before you've landed. By your argument, that is impossible. – David Richerby Feb 4 '14 at 16:34 No, by my argument, you can't measure how far the plane has traveled from beginning to end while the plane is still in the air, moving and stuff. Search your feelings. – Juann Strauss Feb 5 '14 at 8:12 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. - You are right, but I think we are again facing the same problem (see Galileo) : some of our "naive" understanding fails with infinite set. Which one ? If I "measure" my travel in term of distance from the starting point, I can say that, if after one hour the distance is double the distance travelled by my friend, then I'm going twice faster. With "finite" travel, this amount to say that the distance to the goal is less then the distance that my friend still have to travel to reach the goal. With infinite travel, this conclusion does not hold. – Mauro ALLEGRANZA Feb 3 '14 at 17:26 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. - Yes, an infinite can be bigger than another, BUT, the E set (the set composed by all the even numbers) is equal to the N set (the set composed by all the natural numbers. There are 2 types of infinite: 1) numerable infinite: you can count it examples. N , E .... 2) NON-numerable infinite: you can NOT count it examples. all the real numbers all the NON-numerable infinites > all the numerable infinite all the NON-numerable infinites are equally infinite all the numerable infinite are equally infinite. To answer your question clearly, althought it may seem a non-sense N = E - Your answer is ill redacted. The vocabulary is not standard (we say countable, or denumberable). And its is false : all uncountable infinities aren't equally infinite ; more precisely there exists some cardinal$\kappa$such that$\kappa > 2^{\aleph_0}$for example. – Pece Feb 3 '14 at 15:31 The E set and N set are most certainly not equal: Only the latter has 1 as a member. They do have equal cardinality, however. – Ben Voigt Feb 3 '14 at 16:24 @ Ben Voigt: you are right I completly forgot about cardinality – user3105485 Feb 12 '14 at 21:09 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$. - 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$. :-) - Upvote for out-of-the-box answer. – LeartS Feb 3 '14 at 21:06 Hmm, but in the "fast" non-skipping version we still have to say all the "slow" even numbers, and additionally some more between them. How can this be faster? – Paŭlo Ebermann Feb 4 '14 at 17:35 @PaŭloEbermann Agreed, of course its all about the numbering of the sequence. We didn't properly define "slow". If we say "slow" means that it takes a longer time to spell the first$N$members of the sequence then counting by two is slower, at least in binary it is. This is not a statement about the usual "slow" in mathematics: convergence speed. – vanguard2k Feb 5 '14 at 7:38 # Hilbert's paradox of the Grand Hotel This makes a nice puzzle for young people interested in infinity. Consider a hypothetical hotel with infinite rooms, all of them occupied. 1. An extra guest arrives. Can you accomodate him? 2. A neighboring, infinite hotel burned down. An infinite number of guests arrive. Can you accomodate all of them? 3. 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. - And then the guests decide that, for each collection of guests, they want to have a seminar and invite a speaker for those. Now Hilbert has a bit of a problem finding room for all those speakers. – Tobias Kildetoft Feb 4 '14 at 8:35 I'm having a hard time seeing how the answer to number 3 is yes - if you have an infinite number of buses, each containing an infinite number of people, isn't that uncountable? – Michael Feb 4 '14 at 15:01 @michael Put the person from seat$j$on bus$i$in room$(p_i)^j$, where$p_i$is the$i$th prime number. – David Richerby Feb 4 '14 at 16:31 @DavidRicherby The critical difference when you let$k\to\infty$in a bijection to$\Bbb N$depends on whether you allow infinite subsets or not (or infinite sequences that are not eventually zero). Thus using Tobias' example, we can fit the speakers as long as we agree not to have any infinitely large seminars (the hotel only has finitely large rooms, after all). – Mario Carneiro Feb 4 '14 at 22:49 @gerrit You mean why Hilbert will no longer have room for everyone? Consider the following: We allow Hilbert to build a new hotel across the road from the current one, and let him place the speakers in this new hotel. Now consider the collection of people who will not be going to the talk of the speaker in the room opposite them. This collection of them will need to attend some seminar, but who can now live across from the speaker at this seminar? – Tobias Kildetoft Feb 5 '14 at 9:56 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. 1. "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. 2. "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". 3. "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. - @Chad: That makes no sense.$\infty$cannot be treated like a real number, or a natural number, without justifications. And you have no given any justifications for that (because there aren't any in this case). – Asaf Karagila Feb 3 '14 at 17:59 Ugh. You're either being terse on purpose, or you really have no clue what you're talking about (which means that you shouldn't be making statements like "You're wrong." but rather questions of the form "Isn't this and that?"). If this is the former, I have no intention of continuing this conversation, if it is the latter, I apologize but I haven't got the time nor resources (at the moment) to write a six-parts comment about this topic. It probably has been covered before, and you might want to browse the infinity tag for such questions. – Asaf Karagila Feb 3 '14 at 18:05 Let me just add one last thing, which is the root of your mistake, $$\Large\textbf{Infinity is not a real number.}$$ – Asaf Karagila Feb 3 '14 at 18:05 Infinity is not a real number, so why should the limit of two functions as they approach infinity equal their values at infinity? I might compare it to "does the sequence 1, 2, 3 ... reach 133 faster then the sequence 2, 4, 6 ...?" The limit gets the wrong answer because only one sequence ever gets there; why should it work when neither gets there in finite time? – prosfilaes Feb 3 '14 at 23:33 You are comparing the growth rates all wrong. Only if the growth ratio is 0 or infinite can we conclude anything at all from the growth rate test. Otherwise, we'd have to start considering things like$\sum_{n=1}^\infty (-1)^n$and all that garbage. – AJMansfield Feb 4 '14 at 0:51 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. - 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. - 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. - Why would "infinity" map to "infinity"? – Tobias Kildetoft Feb 4 '14 at 8:27 @TobiasKildetoft. By simply defining your function to do so. – Gene Tunney Jul 25 '14 at 3:22 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." - 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? - Can we prove that if we can't biject a set S to the first N integers, for some N, then it must necessarily be bijectable to a proper subset of itself? – Evgeni Sergeev Feb 5 '14 at 11:47 Dedekind showed that in paragraph 160. A set is finite or infinite according to whether or not it is in bijection with a set of n elements for some n. – David Joyce Feb 5 '14 at 17:29 @EvgeniSergeev: Not in$\mathrm{ZF}$set theory, but with some additional axiom, such as axiom of countable choice ($\mathrm{AC}_\omega$), you can. ETA: You can check the wikipedia page on the Dedekind infinite for some details. – Stan Liou Feb 6 '14 at 12:57 Dedekind was using a principle like countable choice in the proof of the previous paragraph 159, which he used to prove paragraph 160. This was all before Zermelo came up with axioms for set theory. Dedekind spent much of that work developing an intuitive set theory in order to be able to develop foundations for the natural numbers. – David Joyce Feb 6 '14 at 20:44 Summary: the trick is to take a countable subset (if it doesn't have enough elements for that, then it's finite), do the one-by-one-->two-by-two bijection on that, and for the rest of the bijection, it maps elements to themselves. The Axiom of Countable Choice is needed to be able to pick a countable subset from a horrible set. – Evgeni Sergeev Feb 6 '14 at 23:07 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 • At each step, you do [something] to get to the next step 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 • To get to any step that doesn't have an immediate predecessor, do [something else] 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 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. - Counting by ones or by twos requires a visit to each element of the set, so if each visit happens at the same length of time, it really doesn't matter. Humans can do the pairing in parallel to counting, so counts by two can proceed at the same concious rate as counts by ones. Thus in any finite time, one can get to a higher number by pairs than individually. Likewise, the grouping of numbers into cycles of 20 or so make counting faster too. Infinity is generally considered a large number. While Cantor's theory suggests that one can complete a count to infinity, in practice, there are numbers whose digits exceed any count (because the count itself spells out a number larger than that). Even if you seek your inspiration for infinity from other sources, the whole point of infinity is that fuzziness that comes from a vague equal sign comes to play, and this really can't happen if you're visiting every number. On the other hand, infinity is a member of a groups of indefinites, some of which are abidingly finite. For example, the instances of cases where a prime p divides its own period is necessarily unbounded, (it's related to$\sum_{1}^{\infty} \frac 1n$). But both of these sums are of the form of$\log \log n$. The known count for 10 is an indefinite number 3 or greater, for base 120, 4 are known. A two's count will get you out there faster, but there is plenty more road in front of you. - 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. - "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!

-

## protected by Willie WongFeb 3 '14 at 15:58

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.