Are we allowed to compare infinities?

Question

I'm in middle school and had a question (my dad is helping me with formatting).

We're learning about infinity in math class and there are a lot of problems like how it's not a number and how if you add one to infinity it doesn't change value.

But can you have one infinity be more than another? There are an infinite amount of odd numbers and an infinite amount of even numbers, so are there the same number of odd and even numbers?

I think so, because for every odd number $n$ there is an even number $n+1$. So the odd numbers are $1,3,5,7,\ldots$ while the even numbers are $2,4,6,8,\ldots$, and as long as you stop counting at an even number the two lists will have the same number of numbers.

But there are also an infinite amount of multiples of $2$ and an infinite amount of multiples of $3$, but I don't think there are the same amount of both. The multiples of $2$ are $2,4,6,8,\ldots$ while the multiples of $3$ are $3,6,9,12,\ldots$ So, no matter which number you stop at, the multiples of $2$ will have more numbers.

---

(Side question (this is dad speaking, now): is there an easy way to explain why we need to put dollar signs around mathematical expressions to make them look prettier? My daughter doesn't know what $\LaTeX$ is, but I want to give her an explanation that isn't horribly hand-wavy.)

Answer 1

In response to the side question: it alerts the system that you want them to be rendered as symbols rather than left alone. You don't want the system to try to render everything as math because then it looks like $this which is really hard to read$ (unless you force it to insert spaces etc. by hand). In this question it wasn't really all that necessary.

As for the question: there are two main kinds of infinity that come up frequently in mathematics. The one that is mentioned here is called infinite cardinality. This means you have some collection of things, and there are infinitely many things in it. We say a collection is infinite in mathematics if whenever you list any number $n$ of the elements of the collection, then your list will be missing an element.

For example, with the integers, if I have $n$ integers in a list, I can find the biggest one. If that's $N$, then $N+1$ is an integer not on the list. So there are infinitely many integers (as you know).

The idea being used here is pairing off elements of your collection with the integers $1,2,\dots,n$. If I can pair off each element of my collection with exactly one of the integers $1,2,\dots,n$, then my collection and $1,2,\dots,n$ have the same number of elements, namely $n$.

We define infinite cardinality in the same way: two infinite collections have the same cardinality ("number of elements") if I can pair off each element of one with exactly one element of the other. The tricky thing with infinite collections is this word "can". You might think that there are fewer even positive integers than there are positive integers, because all even positive integers are positive integers but odd positive integers exist. What you've done is paired off each even positive integer with a positive integer in one way, by matching $n$ with $n$. But I can pair off each even positive integer with a positive integer in a different way: I can match $n$ with $n/2$. Then I've actually paired off each positive integer with each even positive integer. So they have the same "size", at least if we decide to define size this way.

A surprising fact discovered by Georg Cantor in the 1800s is that not all infinite collections have the same cardinality. The most familiar infinite collections with different cardinalities are the integers and the real numbers. There are more real numbers than there are integers.

The way that Cantor showed this is basically the same way that we showed that there are infinitely many positive integers: pair off each positive integer with a real number (producing an infinite list of numbers) and then present a real number which isn't on the list. The hard part is again this word "can": he had to come up with a recipe for a number not on the list no matter what list he was given, so his recipe for the "missing" number has to depend on the given list in a clever way. Cantor also showed that there are infinitely many different infinite cardinalities, using basically the same idea.

Answer 2

This is a wonderful question; unfortunately many of the answers jump directly to explaining cardinality as if that is somehow THE only valid response to your musings.

Now, there's nothing wrong with cardinality -- it is an interesting and important concept in mathematics, and often useful. But there's no rule thats says it is how you must think about the size of infinite sets.

If you need to do something that cardinalities are not well suited for, it is completely allowed to use a different concept instead. In mathematics we're always free to choose the concepts and definitions that will help us reach our goal, as long as we're clear about what we're doing (and as long as our choice of definitions doesn't change what the goal is, of course. If someone else sets a goal for you, you cannot wiggle out of that by redefining the words they used to mean something different from what they had in mind).

For example, if we're talking about sets of points in the plane, then cardinality is often too crude a way to speak about their size. A square of side length 1 cm and a square of side length 2 cm both contain infinitely many point -- and according to cardinality they both have the same infinite cardinality becuase we can match up the points one to one. But it is still reasonable to want to say that the 2cm square is $4$ times as large as the 1cm square -- so for that we choose to speak of area (or, in fancier words, "measure") instead of cardinality. And that is completely all right.

In your example, you have two different sets of natural numbers, $$ \{2,4,6,8,\ldots\} \quad\text{and}\quad \{3,6,9,12,\ldots\}$$ and cardinality says they have the same size. And sometimes the kind of size cardinality talks about is what you need, and if that is the case you go on thinking of them as equivalent.

For other purposes, though, you might need to express the intuitive fact that the first set contains half again as many numbers as the second. That's fine too; we just need to find something else than cardinality for making that intuition precise.

For this purpose we can use the limiting density that Julian Rosen speaks about: When we have a set of numbers we can ask for how many numbers are less than $k$, for any possible $k$ -- and we can then also ask about the fraction of numbers less than $k$ that are in our set, namely the fraction $$ \frac{\text{count of numbers in the set less than }k}{k} $$ Now in both of the cases $\{2,4,6,8,\ldots\}$ and $\{3,6,9,12,\ldots\}$ it happens that there's a certain number $d$ such that when $k$ is large, the fraction above is always close to $d$. (In technical terms, $d$ is called the "limit" of the fraction, and there's a precise definition for what we mean by that, but you won't have learned that yet in middle school). In that case we can call $d$ the density of numbers in the set. The density of $\{2,4,6,8,\ldots\}$ and $\{1,3,5,7,\ldots\}$ are both $\frac12$, confirming your intuition that they have the same size. But the density of $\{3,6,9,12,\ldots\}$ is only $\frac13$, so in the sense of densities there are indeed less multiples of 3 than there are even (or odd) numbers.

This concept doesn't solve everything, though. First, there are sets of numbers that don't even have a density according to this definition -- for example, the set of numbers that are written with an odd number of digits in base ten. In that case the fraction above keeps taking different values between between $\frac1{11}$ and $\frac{10}{11}$ as $k$ increases, never closing in on a single limit.

Second, sometimes we'd like to compare the sizes of sets that have the same density -- for example, the set of perfect squares and the set of prime numbers both have density $0$, but it turns out that, in an appropriate sense there are still "more" primes than there are perfect squares. Namely, the number of primes less than $k$ grows definitely faster than the number of perfect squares less than $k$, when viewed as functions of $k$. This too can be made precise if we put sufficient work into it.

Answer 3

Here's the classic story:

the Hilbert's Hotel Paradox.

Once upon a time in Hilbertland there was a Hotel which was an infinite Hotel. Indeed Mr Hilbert, the owner, explicitly asked for an infinite number of rooms since booking a room during the high season was a really big issue in Hilbertland and it was common not to find a place.

So what did Mr Hilbert think? "Well let's construct a Hotel which has an infinite number of rooms, a room for every natural number that exists, i.e. 1,2,3,... This way I should not have to worry if some guest doesn't make a reservation. I should always have a vacancy".

But what happened that year was that tourism peaked and even if the hotel was infinite during summer there was a night when it was full. Of course Mr Hilbert was happy and thinking "what a smart idea I had to make an infinite Hotel..." and about to go to sleep when suddenly a new guest, i.e. Mr LastMinute, arrived.

"Oh what a shame! Mr Hilbert said "I thought planning for an infinite number of guest would be enough! But instead I should have been planning for infinite plus 1!".

Mr Hilbert was about to give up with the whole hotel industry when had a brilliant idea. "What about if I just tell to eevry one to switch rooms with the one to their left so that the guest in number 1 goes in room number 2, the guest in number 2 in number 3 and so on? Then I should have left room number 1 for the new guest! Mr LastMinute you don't need to go away"

Mr Hilbert thought that that was enough for the evening but when he was just about to go to bed, the neighboring infinite hotel just round the corner (which was also full) was suddenly closed for security reasons. So what happened was that a new infinity of new guest (Guest 1 of hotel 2, guest 2 of hotel 2, guest 3 of hotel 2, etc.) came to Mr Hilbert's Hotel.

This time Hilbert didn't think so much and said "Not a problem, not a problem at all. I'll just say to any of my guest to switch room and leave the room on their left free so that you guest of the other hotel can just go there". So what happened was that the guest in number 1 Mr LastMinute remained in number 1, the guest in number 2 went in number 3, the guest in number 3 went in number 5, the guest in number 4 went in number 7 and so on.

"And now every new guest can take the same room he had in the previous hotel, just multiply you number by two since you were in the second hotel". And so the guest 1 of hotel 2 went in the room number 2, guest 2 of hotel 2 went in room number 4 and so on.

So the same hotel could host an whole number of natural infinity guest such as the double of it.

Answer 4

In mathematics, we often (but not always) compare the "size" of two collections $A$ and $B$ by associating elements between them. For example, if $A=\{1,3,5,\ldots\}$ and $B=\{2,4,6,\ldots\}$, we might (as you pointed out yourself) make the following association: $$ \begin{array}{cccc} 1 & 3 & 5 & \cdots\\ \updownarrow & \updownarrow & \updownarrow\\ 2 & 4 & 6 & \cdots \end{array} $$ Since each element in $A$ is associated to an element in $B$, we say that $A$ and $B$ have the same size.

If instead, as in your second example, $A=\{2,4,6,8,\ldots\}$ and $B=\{3,6,9,12,\ldots\}$, we might make the following association: $$ \begin{array}{ccccc} 2 & 4 & 6 & 8 & \cdots\\ \updownarrow & \updownarrow & \updownarrow & \updownarrow\\ 3 & 6 & 9 & 12 & \cdots \end{array} $$ Once again, we conclude that $A$ and $B$ have the same size.

---

Let's call $\mathbb{N}=\{1,2,3,\ldots\}$ the collection of natural numbers. Consider now the collection of all positive fractions, denoted $\mathbb{Q}^+$. This includes numbers such as $1/2$ or $5/4$.

Since all natural numbers are fractions (e.g. $2$ can be written $2/1$), we see immediately that $\mathbb{Q}^+$ is at least as large as $\mathbb{N}$. Intuitively, we might think that $\mathbb{Q}^+$ is even larger than $\mathbb{N}$ in size--after all, there must certainly be more fractions than natural numbers! However, this intuition is incorrect when we use the definition of size given by associations as above.

To see why, consider the following picture (made by Cronholm144):

Starting at the top left ($1/1$) and following the arrows, we get the following association between $\mathbb{Q}$ and $\mathbb{N}$:

$$ \begin{array}{ccccc} \frac{1}{1} & \frac{2}{1} & \frac{1}{2} & \frac{1}{3} & \cdots\\ \updownarrow & \updownarrow & \updownarrow & \updownarrow\\ 1 & 2 & 3 & 4 & \cdots \end{array} $$

In very much the same way, we can show that the set of all fractions (including negatives), denoted $\mathbb{Q}$, has the same size as the natural numbers. Let's record this fact below:

$\mathbb{N}$ and $\mathbb{Q}$ have the same size.

---

Note that all of the collections that we have disussed so far have the same size as the natural numbers. We say that all such sets are countable. However, as you might have guessed...

There are collections that are not countable.

One such collection is the real number line, denoted $\mathbb{R}$ and pictured below.

This collection includes all the numbers in $\mathbb{Q}$, and is thus at least as large as $\mathbb{Q}$. Moreover, it contains numbers that cannot be written as fractions (also referred to as irrationals), such as $\sqrt{2}$ or $\pi$. The proof that $\mathbb{R}$ is larger in size than $\mathbb{N}$ is a bit involved, but I encourage you to revisit it in the future.

To bring this back to your original question, we now have an example of a collection (i.e. $\mathbb{R}$) whose infinite size is strictly larger than that of another collection (e.g. $\mathbb{Q}$ or $\mathbb{N}$). Therefore, it is possible to compare infinities. Have fun, and best of luck in your studies! :-)

---

P.S. ~ As several people have pointed out, this is not the only valid way to "size up" a collection. See Henning Makholm's answer for an alternative.

P.P.S. ~ See the comments below for some nice references.

Answer 5

If we count up to some large number $N$, about half the numbers will be even (the proportion is exactly half if $N$ is even, slightly less if $N$ is odd). Because of this, people say the even numbers have density $\frac{1}{2}$. The odd numbers also have density $\frac{1}{2}$, so we could say there are as many even numbers as odd numbers.

The density of the multiples of $3$ is $\frac{1}{3}$: if we count up to some large number, only about a third of the numbers are multiples of $3$. We could say there are fewer multiples of $3$ than there are multiples of $2$, because the density of the multiples of $3$ is lower.

Answer 6

There have been many answers already, but I'd thought maybe I could try to provide an easier explanation of how cardinality works.

Consider the three infinite sets $A = \{1,2,3,...\}$, and $B = \{1,2,3,...\}$ and $C = \{1,2,3,...\}$, that is to say, each of them are just all natural numbers. Surely you agree that they have the same size, regardless of how we calculate it.

We now change $B$ a bit: We add 5 to every number in it. So now $B = \{6,7,8,...\}$. Adding 5 to every number surely does not change the number of elements in $B$. So we can say that the size of $A$ and $B$ are still the same.

Now let's do something different: Let's multiply all numbers in $A$ by 2 and all numbers in $C$ by 3. This surely does not change the number of elements in them - we only shuffled around the values a bit.

But now we also see that $A = \{2,4,6,...\}$ and $C = \{3,6,9,...\}$ - the sets we initially looked for! This means that, strangely enough, they have the same number of elements in them. That's why we say both sets are of the same size.

So why did we initially think that $\{2,4,6,...\}$ has more elements than {3,6,9,...}? That's because we implicitly used the natural numbers as a scale to measure how far we went in the sequence - we compared the elements by their numeric value, not by their index in the sequence.

And that's absolutely not wrong in itself, but we must remind ourselves that this only shows us how quickly the values in the sets grow compared to the natural numbers. That is just something different from the number of elements they contain (in relation to each other).

In math speak, our initial idea refers not to the cardinality, but the density, and the answer of @Henning Makholm covered it very nicely.

Another example

It may also be helpful if you consider this example: You know fractions, right? They are made of a numerator and a denominator like $\frac{a}{b}$. Let's look at the two sequences $\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, ...$ and $\frac{1}{1}, \frac{2}{1}, \frac{3}{1}, ...$. From their construction, it's intuitive to say they have the same number of elements - we always added 1 to either the numerator or denominator in each element.

But at the same time, the former sequence only occupies the space between 0 and 1, while the latter is equal to all natural numbers (which looks a lot larger). So the absolute values involved in a sequence are no indicator of how many elements it contains (again: different concepts!).

Answer 7

So, no matter which number you stop at, the multiples of 2 will have more numbers.

The problem of thinking in infinities is that you must force yourself to not think about stopping. If you stop counting, you have a finite sequence and in that case, the number of odd and even numbers will depend on where you began and where you stopped. In infinity it will always be infinity.

Answer 8

It turns out that there are actually lots of meaningful ways to define infinity. One good example of this is the infinite hotel paradox which explains very well. There is also an excellent and very accesible chapter on this and related matters in Science of Discworld III by Terry Pratchett and Jack Cohen (a book which is well worth reading for anybody interested in science and mathematics).

It is also worth bearing in mind that mathematical concepts don't necessarily have to be 'real' as long as they are internally consistent and useful. Maths isn't exactly the same as science in that it is not restricted to describing the real world. It is a thing of itself which may or may not be useful in practical fields. Ultimately is is way of describing things in a way which makes them easier to understand.

Answer 9

To see if two collections have the same number of elements, you put them in pairs. If there's no element left alone, the numbers are equal.

For instance $\{ 1, 2, 3\}$ vs. $\{ a, b, c \}$ yields three pairs $(1,a),(2,b),(3,c)$ and nothing left.

This reasoning is used to compare infinite sets. If you can pair the elements, the "infinities" are equal.

As you can establish the correspondences

$$(1,3),(2,6),(3,9),(4,12)\cdots$$

there are as many multiples of $3$ as there are integers. (If you are given an integer, you can find the corresponding multiple of $3$ and conversely, so that there is no leftover.)

Answer 10

The trick to determining if two infinities are equal often come through whether or not you can connect one object to another for every object in the set.

For example, which has more numbers:

$$\lbrace1,2,3,\dots\rbrace\text{ or }\lbrace2,3,4,\dots\rbrace$$

Both have an infinite amount of numbers, but which has more? Since every number or the left corresponds to another on the right, they have the same amount of numbers, every number $n$ corresponds to $n+1$.

If we compare $\lbrace1,2,3,\dots\rbrace$ and $\lbrace1,4,9,\dots\rbrace$, they both have the same amount of numbers as well because every number $n$ on the left corresponds to $n^2$ on the right.

However, not all infinities are equal, for example:

$$\lbrace1,2,3,\dots\rbrace\text{ or }\lbrace0\dots1\rbrace$$

The right set has all of the numbers between $0$ and $1$.

Amazingly, there are more numbers between $0$ and $1$ than there are whole numbers. If we try to match the numbers to prove they are the same, we actually get that the whole numbers correspond to the rational values between $0$ and $1$, leaving the infinitely many irrational numbers on the right, so there must be more. A more famous argument involves the Cantor Diagonal Argument, which you can look up.

And a nice video would be vsauce's "How to count past infinity" video, on youtube.

Answer 11

I wish to propose another simple, perhaps, less mathematical but more intuitive understanding of 'infinities'.

It also happens to be by an author that you may possibly be familiar with:

“There are infinite numbers between 0 and 1. There's .1 and .12 and .112 and an infinite collection of others. Of course, there is a bigger infinite set of numbers between 0 and 2, or between 0 and a million. Some infinities are bigger than other infinities." - John Green, The Fault In Our Stars

Answer 12

You can compare sets using numerosity.

Numerosity satisfies the Euclid's principle "the whole is greater than part", so the numerosity of a subset is smaller than the numerosity of the superset.

There is a clear way to express numerosities of sequences via $\omega$, which is the germ of the identity function at infinity or half the numerosity of $\mathbb{Z}$. It also can be considered a surreal number. This measure is more accurate than asymptotic density, because it gives the exact value.

Suppose you have a strictly increasing sequence $a_k\ge0$, where $k\in\mathbb{Z}, k\ge0$.

To find the numerosity, you have to

1. Perform operator $D\Delta^{-1}$ on your sequence, where $\Delta^{-1}$ is anti-difference (indefinite sum). This is quite sandard operator in umbral calculus.
2. Find inverse function of the resulting expression.

In other words, apply to your sequence the operator $N(a_k)=\left(D\Delta^{-1}a_k\right)^{[-1]}(\omega)$, where $f^{[-1]}$ is the inverse function.

The following Wolfram Language code does the thing:

a[k] := k^2
SolveValues[D[Sum[a[k], k], k] == \[Omega], k] /. C[1] -> 0 //
   FullSimplify // Expand

So, some examples:

• $N(2k)=\frac{\omega}{2}+\frac{1}{2}$ (we allow $k$ to be zero, but if you want non-zero naturals, subtract $1$ from this)

• $N(2k+1)=\frac{\omega}2$

• $N(k+5)=\omega -\frac{9}{2}$

• $N(k^2)=\frac{1}{2}+\frac{1}{6} \sqrt{36 \omega +3}$ (again, subtract $1$ if you do not count zero)

• $N(1/3+k+k^2)=\sqrt{\omega}$

• $N(k^4)=\frac{1}{30} \sqrt{30 \sqrt{900 \omega +30}+225}+\frac{1}{2}$

• $N(7^k)=\log_7 \left(\frac{6 \omega }{\ln (7)}\right)$

So, yes, the numerosity of positive even numbers is by $1/2$ greater than the numerosity of positive odd numbers.