32
$\begingroup$

I recently watched a video about different infinities. That there is $\aleph_0$, then $\omega, \omega+1, \ldots 2\omega, \ldots, \omega^2, \ldots, \omega^\omega, \varepsilon_0, \aleph_1, \omega_1, \ldots, \omega_\omega$, etc..

I can't find myself in all of this. Why there are so many infinities, and why even bother to classify infinity, when infinity is just... infinity? Why do we use all of these symbols? What does even each type of infinity mean?

$\endgroup$
  • 68
    $\begingroup$ We're sorry. We meant no harm. $\endgroup$ – Will Jagy Apr 28 '16 at 0:33
  • 6
    $\begingroup$ Part of it is ordinals vs. cardinals. These are quite different, more so than in the finite case (where ordinals mean "the $m$th thing" while cardinals mean "$m$ things"). As for why there are so many cardinals, Cantor's theorem says that you can make a bigger cardinality by taking the power set. That gives you a whole bunch of infinities, called $\beth_0,\beth_1,\dots$. Combining all these together gives $\beth_\omega$, and then we can take further power sets to get even more infinities. There are in fact more infinite cardinals than you can fit into any one set in ZFC. $\endgroup$ – Ian Apr 28 '16 at 0:34
  • 11
    $\begingroup$ tl;dr -- the "infinities" you listed are not the same. $\endgroup$ – galois Apr 28 '16 at 0:48
  • 4
    $\begingroup$ I know this is not a direct explanation, but you might find the following video interesting: youtube.com/watch?v=SrU9YDoXE88; it's an awesome Vsauce video that offers an answer to this very question, and I found it very intuitive. $\endgroup$ – Itai Ferber Apr 28 '16 at 3:37
  • 4
    $\begingroup$ @ItaiFerber that's funny because that's the same video I watched before I asked the question and I was confused. But I watched it again after asking the question and I get it now. ;) $\endgroup$ – KKZiomek Apr 28 '16 at 3:39
29
$\begingroup$

As an insight, think of the size of the usual sets of numbers.

Think of the set of all positive integers, and the set of all positive multiples of 5. It's a bit strange to the "uninitiated", but it's ultimately not hard to wrap your head around the fact that there's the same amount of each, because we can list them side by side without any problem:

$$\begin{align*}1 &\to 5\\2&\to10\\3&\to15\\&\dots \end{align*}$$

Each is an infinite set, and while you may be tempted to think that there's five times more numbers in set of positive integers than the set of multiples of 5, I just showed above that you can make a 1-to-1 correspondence between them, so in fact they are the same size. I'm just making up this notation, but we can call this $\infty_1$.

Now think about the set of all numbers between $0$ and $1$. There's no possible way, no matter how you try, to get a 1-to-1 correspondence with the set of positive integers like we did above. We can try:

$$\begin{align*}1 &\to 0\\2&\to0.1\\3&\to0.01\\&\dots \end{align*}$$

But what about all the numbers between $0$ and $0.1$ that we're missing? We get this rough intuition that there's more numbers in the second set this time than in the first. We can call this $\infty_2$.

Already we have described two "different infinities", just by looking at a couple sets of numbers. $\infty_1$ is countable, as we saw in the first enumeration, but $\infty_2$ is not.

To develop the entire concept of aleph numbers and transfinite sets and etc requires some pure mathematics that is past my pay grade. But maybe you can see how infinities can be classified as different.

In the mathematical world, $\infty_1=\aleph_0$ and $\infty_2=2^{\aleph_0}$, so you'll see it written that way. As @Milo Brandt pointed out, for those who are more interested in the rigor of transfinite sets, etc, keep in mind that $2^{\aleph_0}$ is not necessarily $\aleph_1$.

$\endgroup$
  • 7
    $\begingroup$ This is one of the best answers yet, I'll just wait for another answers before I accept $\endgroup$ – KKZiomek Apr 28 '16 at 1:02
  • 1
    $\begingroup$ The second-to-last paragraph is the important bit, btw. You may have heard of "countable" and "uncountable" sets. The whole idea boils down to if you can create a 1-to-1 correspondence (called a bijection) between a set and the positive integers. en.wikipedia.org/wiki/Bijection $\endgroup$ – galois Apr 28 '16 at 1:04
  • 2
    $\begingroup$ This answer doesn't quite go there, but it would not be unreasonable for one to extrapolate from this answer the statement that $\aleph_1=2^{\aleph_0}$, which is a common misconception. This statement is called the continuum hypothesis, and, in a sense, cannot be proven true or false with our usual system. (So, in particular, there may be smaller uncountable sets than $\mathbb R$) $\endgroup$ – Milo Brandt Apr 28 '16 at 2:51
  • 2
    $\begingroup$ Good post (+1). One thing: I would use a different example for showing that $[0,1]$ is not countable than "$0.1, 0.01, 0.001"$ since that doesn't really show the intuition why it's uncountable. You say "what about all the numbers between 0 and 0.1 we're missing", but by counting differently we can get at least "a lot" of the numbers between such as 0.01, 0.02, etc. and a new reader might be confused why there are actually more numbers in $[0,1]$. Of course we can biject $\mathbb{N}$ to every finite decimal in $[0,1]$. The problem are the non-terminating, non-repeating decimals. $\endgroup$ – MCT Apr 28 '16 at 18:26
  • 6
    $\begingroup$ In your "all numbers between 0 and 1" example you should put more emphasis on the fact that you're talking about real numbers, since rational numbers are countable and can be mapped to the natural numbers. This is especially confusing since the values you mention explicitly are all rational. $\endgroup$ – CodesInChaos Apr 28 '16 at 20:41
11
$\begingroup$

I won't comment on your more philosophical questions, but I will give what I think is one of the more important applications of different sizes of infinity.

There is a rigorous mathematical way of thinking about a computer program, called a Turing machine. One can show that the cardinality of the set of Turing machines is $\aleph_0$, however the set of all possible problems you might want a computer program to solve is strictly bigger (cardinality of $\mathbb{R}$). The very real application in this case is the conclusion that there are some problems which are not solvable by any computer program.

$\endgroup$
  • $\begingroup$ I understand, but what does it have to do with all the other infinities and all the diversity of symbols? $\endgroup$ – KKZiomek Apr 28 '16 at 0:41
  • 2
    $\begingroup$ This is just an example to show that there is a real meaningful difference between different kinds of infinity. If there are many meaningfully different kinds of infinity, then we need lots of symbols in order to refer to them. $\endgroup$ – Christian Gaetz Apr 28 '16 at 0:43
  • $\begingroup$ @KKZiomek: Actually, the diagonalization argument does not indicate difference in size, but rather in complexity. Any countable first-order theory has a countable model, and hence ZFC too has a countable model. In this model the set of real numbers is countable when viewed from the meta-system outside. Inside you can prove that there is no surjection from the set of natural numbers to the set of real numbers, but outside there is indeed a surjection. So the correct conclusion is that cardinality does not correctly reflect size. $\endgroup$ – user21820 Apr 28 '16 at 5:32
  • $\begingroup$ "the set of all possible problems you might want a computer program to solve is strictly bigger (cardinality of ℝ)" Oh, I want to solve many more problems than the cardinality of R ... ;) $\endgroup$ – ypercubeᵀᴹ Apr 28 '16 at 16:34
11
$\begingroup$

One issue not yet addressed is why we have both $\aleph$s and $\omega$s. These both exist because Cantor introduced two separate concepts about infinite sets - their sizes ($\aleph$) and their order-types ($\omega$). Everyone else explained sizes, so I won't go over that.

For order-types, begin by considering the following set:

{ 1/2, 2/3, 3/4, ..., N/N+1, ... }

This is of course an infinite set of size $\aleph_0$. But the elements can also be ordered by <, and so this is also a set of a particular infinite order-type, which Cantor chose to name $\omega$. Now consider a variant of this set:

{ 1/2, 2/3, 3/4, ..., N/N+1, ..., 1 }

This is also of size $\aleph_0$ (I leave proof to you). But it is a different order-type, because its internal ordering is structurally different - i.e it is NOT possible to biject the two sets preserving order. This can be seen by noting that the element 1 in the second set has infinitely many predecessors, which no element in the first set has. Cantor names this set's order-type $\omega+1$. If I added 2 into the second set, the resutling order-type would then be $\omega+2$; and so on. Actually, that doesn't do it justice - there are an infinity of 'and so on's coming - compounded 'to infinity and beyond'.

So what Cantor discovered is a very sophisticated notation for describing highly complicated sets of real numbers (or as he thought of it, points on the number line), a notation which he realized could be abstracted to a system of actually infinite numbers having its own rules of arithmetic (inferred from the point sets resulting from catenating other point sets).

$\endgroup$
  • 1
    $\begingroup$ Your second displayed set is unclear. I know you meant that the list is infinite and is followed by 1, but the uninitiated might think it means the list is finite and ends with 1 (at least until midway through the next paragraph). You should clarify IMO. But +1: good explanation otherwise. $\endgroup$ – msh210 Apr 28 '16 at 21:02
7
$\begingroup$

One natural use for smallish infinite ordinals, which makes clear that different infinite ordinals have distinct properties, is the length of games.

I'm playing a chess-like (turn-taking, deterministic, complete information) board game of some kind against an opponent. My teammate is also playing a separate game against my opponent's teammate. Moves are made in both games at the same time.

Sadly, I'm losing my game, and can no longer do anything to avoid an eventual loss. Luckily, my teammate is winning, and the rules are such that as long as I can delay my loss for long enough for my teammate to force their win, we're OK.

Borrowing chess terminology, my opponent's position can be described as win in $n$ inductively, by saying that they win in $0$ if they've already won, and they win in $k+1$ if no matter my next move, they will be able to guarantee ending up in a win-in-$k$ position.

I'm losing, so my opponent has win-in-$p$ for some $p$. My teammate has win-in-$q$ for some $q$. I'm OK exactly if $p > q$ (what happens if $p = q$ isn't important for what follows).

So far, it seems like we can measure the length of winning sequences using natural numbers. But then I spot something interesting: I actually have infinitely many moves available to me, and I can see a move that leaves me $1$ step from defeat, one which loses in $2$, one which loses in $3$, and so on. Every move seems to lose ultimately, each in a fixed finite number of steps, but I can at least choose how long it takes for me to lose. So if my teammate is in a win-in-$k$ position, I just need to pick the move that loses in $k+1$ moves and I'm all right!

In some sense, then, the winning sequence (losing sequence) that I'm facing is "longer" than any finite sequence my teammate might need, despite the fact that in all circumstances I lose in a finite number of moves. For this particular situation, we might say I will lose in $\omega$ moves, where $\omega$ is some kind of special number (spoiler: ordinal) that is bigger than any natural number.

However, I notice my teammate is actually in the same exact situation: they will win, but their opponent will be able to choose, on their next move, how long it takes. Once they've made that choice, their fate is sealed, but if they make their choice at the same time as I make mine, I can't ensure that they won't pick a longer finishing sequence than me. So I need to find a move such that I can put off my decision until my next turn, see what my teammate's opponent picks, and just pick a longer losing sequence. If you remember our inductive definition of win-in-$k$ from before, you might say that I'm looking for a lose-in-$(\omega + 1)$ situation, i.e. for a way to ensure that I'm in a lose-in-$\omega$ situation next turn.

Once you can imagine that, you can perhaps imagine losing in $\omega + 7$ moves, or even $\omega + \omega$, $\omega + \omega + \omega$, even $\omega^2$ and things more exotic than that. You can come up with a natural comparison ordering of these game lengths that precisely corresponds to whether or not I'll be able to guarantee that my teammate wins before I lose. If you do that, you have a game length for every natural number, then you have a game length which is larger than any natural number, then you have many more, still larger, game lengths. We can consider each of these long game lengths as a variety of infinite numbers that are each distinct and comparable with each other in meaningful ways, and as you might've guessed there's a meaningful addition (or at least concatenation) concept on these lengths which satisfies some (but not all) of the properties of addition on natural numbers. These are (some of) the ordinal numbers.

All this to say, there isn't simply one infinity that sits at the top of all numbers. There are many objects that don't seem to have this property or characteristic of "finiteness", indeed as rich and diverse a variety of non-finite objects as there are finite ones.

$\endgroup$
5
$\begingroup$

The major motivation for classifying infinities (other then the intrinsic enjoyment of mathematics) is that different infinities permit different properties.

Countable infinities can be reasoned about using inductive proofs. On the other hand many of the properties analysis makes use of requires uncountable sets.

Having different infinities often makes showing that two sets are not isomorphic by allowing us to determining the cardinality of both.

$\endgroup$
4
$\begingroup$

If it's any consolation, in practice you won't encounter more than two different types of infinity: that corresponding to the natural numbers, and that corresponding to the real numbers (cardinality of the continuum).

The reason why it's necessary to differentiate between those two is that the "size" (cardinality) of the real numbers corresponds to the cardinality of the power set of the natural numbers.

An elementary theorem states that the "size" (cardinality) of any set is always strictly smaller than that of its power set, and the same holds true for the natural numbers.

Hence many of the tricks that work for the "infinity" associated with the natural numbers do not work for the "infinity" associated with their power set/the real numbers.

For example, you can "add up" some sequences of "infinitely many" non-zero numbers and still get a finite result, provided that the infinity involved corresponds to that of the natural numbers.

However, if the infinity involved corresponds to the real numbers (i.e. an uncountable sum of non-zero numbers), the sum will always be infinite, no matter how small you try to make the individual terms.

It is discrepancies like these which necessitate that we differentiate (in particular) between these two different types of infinities. However, at least speaking as someone who specializes in probability and statistics, any other type of infinity does not occur as often.

$\endgroup$
  • 1
    $\begingroup$ reddit.com/r/math/comments/3uzuno/… $\endgroup$ – Ian Apr 28 '16 at 0:49
  • $\begingroup$ Thanks for the link! That's a really cool discussion. $\endgroup$ – Chill2Macht Apr 28 '16 at 0:50
  • 1
    $\begingroup$ I think the power set concept is important here, since the power set of the reals has an even bigger cardinality. So the OP can see an easy way to understand that even two infinities isn't enough. $\endgroup$ – jdods Apr 28 '16 at 1:14
  • $\begingroup$ Yeah, I probably should have emphasized that sort of process can be iterated indefinitely. I think you said it perfectly -- you can definitely edit my post if you want to. $\endgroup$ – Chill2Macht Apr 28 '16 at 1:16
  • $\begingroup$ I'd be interested in a more rigorous justification (or at least a formal statement) of "...if the infinity involved corresponds to the real numbers, the sum will always be infinite". I'm curious as to whether this is strictly true and, if so, whether the resultant sum is necessarily uncountable. Though I suppose I can ask my own question! $\endgroup$ – S. G. Apr 28 '16 at 18:08
3
$\begingroup$

Your question touches on issues both mathematical and philosophical; in fact, you might enjoy an introductory text in philosophy of mathematics and logic, or on the foundations of mathematics.

Truth is, an infinity is not just an infinity. One reason for this peculiarity is due to the seminal work of Georg Cantor.

Cantor proved that the set of real numbers is greater than the set of natural numbers.

Crazy.

Even crazier is how he used grade-school concepts, such as a one-to-one correspondence, to do so.

But none of this really answers Why?. Maybe I can give you something of an answer. Mathematics is a language rigorously defined. It's one thing to throw around a natural-language word like infinity, and totally different to empower that word with a thoroughly defined meaning in a formal language.

Put more poetically, Cantor provided a definition of infinity by showing that infinite sets of things can be classed and organized like books on a shelf.

$\endgroup$
  • 1
    $\begingroup$ As a philosophy major, I am particularly intrigued by infinite sets and the concept of infinity. An interesting debate therein surrounds the existence of so-called 'actual infinities": that is, an infinite set which obtains in the real world, like an infinite pile of ants, an infinite number of cells, or -- in cases of philosophy of science and religion -- an infinite set of causal agents (e.g., an infinite regress of divine causers). $\endgroup$ – Cody Rudisill Apr 28 '16 at 1:34
  • 1
    $\begingroup$ Also, for further reading on the subject written in an especially interesting and not-as-technical-as-could-be way: "Everything and More: A Compact History of Infinity" by David Foster Wallace $\endgroup$ – Cody Rudisill Apr 28 '16 at 1:37
  • $\begingroup$ Your answer isn't an answer either. The concept "infinity", however defined, mathematically, philosophically or otherwise, is still a finite concept, unless it is so vague as to be meaningless. Mathematically especially, there is a first-order formula $φ$ over ZFC with 1 parameter such that $φ(x)$ is true iff $x$ is infinite. $φ$ itself is a finite string of symbols. What about $x$? The problem is that you can never describe $x$ to me unless it has a finite description. What if I don't accept the existence of anything you cannot describe? Godel's constructible universe $L$ is exactly that. $\endgroup$ – user21820 Apr 28 '16 at 5:37
  • $\begingroup$ In simpler terms, unless you give some ontological justification for the existence of an actually infinite object, all the mathematical infinities are merely concepts that have no instantiation. Classifying them then amount to nothing more than arranging first-order formulae on a shelf. $\endgroup$ – user21820 Apr 28 '16 at 5:39
  • $\begingroup$ I'm by no means attempting to provide a rigorous answer to the OP's question. Just a semblance of one in an easily digestable manner. $\endgroup$ – Cody Rudisill Apr 28 '16 at 13:29
1
$\begingroup$

infinity is just... infinity?

This is your problem; this is simply wrong. Now, to be fair, it's a fairly well entrenched wrong idea because mankind has spent thousands of years trying to reason about the infinite, and we've only really figured out how to do so in the past hundred years or so, and there hasn't really been enough time for this knowledge to seep into the 'common knowledge' of laypersons.

Most of the things you wrote down are ordinal numbers. Ordinal numbers are used to quantify things called well order types, and collectively formalize a particular generalization of the idea of 'counting'. We have "so many symbols" because we need to be able to write down the quantities we're talking about — it's the same reason we have lots of symbols for integers, such as $1, 2, 3, 10, 11, 20, 134301, 10^{100}, \ldots$

One thing I want to point out now: ordinal numbers and cardinal numbers are different ideas, but fairly closely related. They have absolutely nothing to do with the symbol $\infty$ that you encounter in calculus. For that, look up the extended real numbers.

An order type is basically the 'shape' of an ordered set. The ordinal number $\omega$ is the shape of the natural numbers, although there are lots of other ordered sets with the same shape, for example:

  • The set of all even natural numbers, with their usual ordering
  • The set of all powers of 2, with their usual ordering

An example of a different, but still infinite order type is that of the integers. We can easily see that the integers and the natural numbers have different order types, because the natural numbers have a least element, but the integers do not.

The integers do not form a well order type, though, so there isn't an ordinal number to quantify them.

The important thing to realize is that order types can have infinitely many values... and then still have even more, larger values. As a simple example, the real numbers (with their usual ordering) have an order type (again, it's not a well-order type). There are infinitely many values in the interval $(0,1)$, but nonetheless there are more real numbers even larger than all of those!

Now, consider the set of values $X = \{ 0, 1/2, 3/4, 7/8, 15/16, \ldots \} $; i.e. the values of the form $1 - 2^{-n}$ for natural numbers $n$. This may be familiar from Zeno's paradoxes.

This set of numbers with its usual ordering is a well-order type — it's yet another example of the order type $\omega$.

Now, let $Y$ be the set you get from $X$ by adding an additional point that is larger than everything already in $X$. Let's consider specifically the set $Y = X \cup \{ 1 \}$ with its usual ordering.

The ordered set $Y$ is a well-order type, and an infinite one at that, but it's not $\omega$. Two particular features of $Y$ are:

  • $Y$ has a largest element $1$
  • $1$ does not have an immediate predecessor, despite there existing smaller values

We call this well-order type $\omega + 1$, since we got it by starting with $X$ (which has well-order type $\omega$), and afterwards adding one extra point (which has well-order type 1).

$\endgroup$
0
$\begingroup$

The preoccupation expressed in the OP's question goes back (at least) to the 17th century, when Nieuwentijt objected to Leibnizian hierarchy of infinite numbers by claiming that there should be only one level of infinity, and reciprocally, only one level of infinitesimal, say $\epsilon$ (though Nieuwentijt didn't denote it that way), so that the square of $\epsilon$ would be zero: $\epsilon^2=0$. Leibniz and his school objected to this by saying essentially that this would involve a violation of the law of continuity. A modern formalisation of the Leibnizian law of continuity is the transfer principle of Robinson's framework. For a discussion of these issues in a historical context see Guillaume's review.

$\endgroup$
  • $\begingroup$ This is neat, but it isn't really related to the classification of infinities in the sense of ordinals and cardinals, though, which is what the OP is asking about. $\endgroup$ – Noah Schweber Oct 29 '16 at 2:56
  • $\begingroup$ @NoahSchweber, I just read carefully the OP's question and he says not a word about ordinals and cardinals. He spoke specifically about infinity. What you write is your interpretation of what he is asking. Your interpretation is influenced by the Cantorian perspective you learned in graduate school. The idea that this is the "true" and only intepretation of infinity is a common one, but it is an idea that can be challenged. This is precisely what I did in my answer. $\endgroup$ – Mikhail Katz Oct 29 '16 at 16:59
  • $\begingroup$ On April 29th, the OP added the tags "ordinals" and "cardinals." Additionally, the text of their answer includes as examples "$\aleph_0$, then $\omega, \omega+1, \ldots 2\omega, \ldots, \omega^2, \ldots, \omega^\omega, \varepsilon_0, \aleph_1, \omega_1, \ldots, \omega_\omega$, etc..". Finally, they've accepted an answer, so that gives some information as to what they were asking. I'm sorry, but I really don't think your answer is related to their question. (I didn't ever say that the Cantorian interpretation of infinity couldn't be challenged, by the way.) $\endgroup$ – Noah Schweber Oct 29 '16 at 17:02
  • $\begingroup$ The question also features the tag infinity. Therefore other interpretations of infinity may also be envisioned. The fact that there is a tag on cardinals does not mean that it is the exclusive interpretation. $\endgroup$ – Mikhail Katz Oct 29 '16 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.