The different sizes of infinity

Factual Questions
1

A few comments/corrections on the discussion of infinities:

http://chicago.straightdope.com/sdc2010infinity.php

> The different sizes of infinity we’re talking about are those
> involving numbers.

Actually, they are those involving the sizes of sets. Sets of numbers are good/interesting sets to look at, but we could look at sets containing other things.

> Ergo, these infinities are the same size.

Better to say, “these sets are the same size”.

> You can match up the counting numbers with any set of rational
> numbers. (Rational numbers can be expressed as the quotient of two
> integers, provided you don’t divide by zero.) For example, consider
> the set of numbers of the form 1/x — that is, 1/1, 1/2, 1/3 … This
> set gets infinitely small, and never exceeds 1, whereas the counting
> numbers get infinitely large. Doesn’t matter. The two sets can be
> matched up — these infinities are the same size.

The set does not “get infinitely small”. There are numbers in the set that are arbitrarily close to zero, but the set itself isn’t doing anything.

The set of numbers of the form 1/x (for x a counting number) is a subset of the rationals. So, the fact that it is countable tells us nothing about the rationals. Every infinite set has an infinite countable subset. The question is whether the entire set can be put in one-to-one correspondence with the counting numbers. It is true that the set of rationals is countable, but you haven’t shown this.

The usual way to show that the set of rationals is countable is to first arrange the (positive) rationals in a grid:

1/1 1/2 1/3 1/4 …
2/1 2/2 2/3 2/4 …
3/1 3/2 3/3 3/4 …
.
.
.

(Some numbers appear more than once in the grid, but this doesn’t really matter.) Then list them (count them) in this order: 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3 … I.e., go up and down the diagonals that run from top right to bottom left.

> You can match up the counting numbers with many sets of irrational
> numbers. (An irrational number is any number that, duh, isn’t
> rational. For example, the square root of two, 1.41421356 …, is
> irrational; the decimal never repeats.) Consider numbers of the form
> square root of x — that is, square root of 1, square root of 2,
> square root of 3 … This set can be matched up with the counting
> numbers. These two infinities are the same size.

The set of numbers of the form square root of x (for x a counting number) is countable. However, the set of irrational numbers is not countable. Every real number is either rational or irrational. The set of rational numbers is countable. The set of real numbers is not countable. Therefore, the set of irrational numbers is not countable. And, there are more irrational numbers than rational numbers.

> You can match up the counting numbers with any other set of numbers
> that can be generated algebraically — which is to say, through the
> ordinary operations of mathematics. All these sets are infinities of
> the same size.

I don’t think you meant what you wrote. You probably meant that the set of algebraic numbers is countable. The set of algebraic numbers consists of those numbers that are roots of polynomial equations with rational coefficients. There may or may not be a formula involving the arithmetic operations for such a number.

> Since there’s no way to systematically generate transcendental
> numbers, they can’t be matched up with the counting numbers and thus
> can’t be counted.

Whether you can “systematically generate” the set (whatever that means) isn’t relevant. However, it is true that the set of transcendental numbers is not countable.

> The real numbers, then, include numbers that can be counted and
> other numbers (the transcendentals) that can’t.

It isn’t numbers “that can be counted”; it is sets of numbers. The set of real numbers is not countable. Therefore some subsets of real numbers are countable and some are not.

> The implication, if you think about it, is that there are more real
> numbers than counting numbers.

Correct.

> The proof of this was devised by the aforementioned Georg Cantor and
> makes use of an ingenious diagonal argument. I won’t attempt to
> explain it here, but the gist is that for any possible list of
> numbers you could devise, there’s some additional number that isn’t
> on the list and thus won’t be counted.

The statement, “for any possible list of [real] numbers you could devise, there’s some additional number that isn’t on the list”, is just another way of saying that the set of real numbers is not countable. Cantor’s diagonal argument shows how, given a list of real numbers, to construct a number not on the list. This proves that the set of real numbers is not countable.

> In fact, it can be shown that most real numbers (or better, “most”
> real numbers, since we’re comparing infinite quantities) are
> transcendental and thus not countable,

Every real number is either algebraic or transcendental. The set of algebraic numbers is countable, and the set of real numbers is not countable. Therefore, the set of transcendental numbers is not countable. And, there are more transcendental numbers than algebraic numbers.

> from which it follows that, as infinities go, the counting numbers
> don’t amount to squat.

Countable sets are the smallest infinity. Every infinite set contains a subset that is countable.

2

Countable infinity is the “smallest” size of infinity - includes integers, or rational numbers. Uncountable is the next size - which includes the real numbers, for example. Of course, after that are an infinite number of infinities…

3

Countable infinity (also called aleph-null or aleph_0, i.e., the Hebrew letter aleph with a subscript of zero) is the smallest infinity. However, all larger infinities are uncountable (since “uncountable” means not countable). The next infinity is aleph_1. The infinity of the real numbers is 2 raised to the aleph-null power (in symbols 2^{aleph_0}). It is independent of the usual axioms of set theory whether 2^{aleph_0} is aleph_1 or larger. Recently, a new axiom has been proposed that would imply that 2^{aleph_0} is aleph_2.

4

Of course, but my examples all involved numbers, and I wanted to reassure the math-averse that I wasn’t going to get overly technical.

Not really. The point of the column is that infinities may be of different sizes. I’m not trying to explain set theory.

You have me there. I’ll correct this.

You misunderstand what I’m trying to accomplish here. Most people think infinity is infinite, period, and that there can’t be gradations (or if you prefer, “gradations”). I’m trying to back them off this belief without creating misconceptions in the process. I do this by proceeding in baby steps. People learn in childhood that there can be infinitely many numbers within a bounded range; I’m simply trying to reassure them that this can be (although isn’t always) the “same size infinity” as the counting numbers, which aren’t bounded.

I wasn’t trying to provide a rigorous proof that the rationals are countable, and wanted to avoid presenting arrays of numbers - this is a sure way to frighten off non-mathematicians. By presenting examples, I felt people would intuitively understand that the rationals were countable. I’m well aware that I haven’t demonstrated this.

Yes, of course. I’m trying to make the point that SOME sets of irrationals are countable. The divide of interest isn’t between the rationals and irrationals, but between the countable numbers (the algebraic numbers) and the uncountable ones (the transcendants).

I understand that the set of algebraic numbers is countable, but that wasn’t the point I was trying to make. I was simply observing that if you do have a formula, the result is countable. This played into the notion of an algorithm, discussed below.

On the contrary, it seems to me this is a central point. For a set to be countable, you need an algorithm that will let you generate its members. That’s what the diagonal procedure you describe above does. I’m puzzled that you think this is irrelevant, and fear I have expressed myself poorly.

I think it was reasonably clear what I meant. We’re coming at this from opposite directions. I don’t want to start with the assumption (or demonstration) that the real numbers aren’t countable; that’s what I’m trying to get people to understand. That said, I’d be better off amending the cited sentence to read, “The real numbers include sets of numbers that can be counted and another set of numbers, the transcendentals, that can’t.”

Just my point.

Again, we’re coming at this from opposite directions. I didn’t want to start with Cantor’s diagonal argument; I felt non-mathematicians would find it confusing. Instead I wanted to edge into the notion that some real numbers (if you insist, some sets of real numbers) were countable and others weren’t, and use this to make the point that there could be different sizes of infinities.

No argument here.

5

If we’re nitpicking, then I have a different sentence to nitpick.

Technically, this is wrong. There are hundreds, possibly a countable infinity, of ways of producing pi algebraically. The wiki page on Pi lists a good many of them. These are exact. We couldn’t know what pi was an approximation of without these.

It’s true that you cannot express pi in a finite number of steps, and wherever you stop the iterative process produces only an approximation of pi. But that’s true of rational numbers as well. 0.333~ produces only an approximation of 1/3 no matter how many physical steps you take.

What I think you mean is this definition:

That’s not the same as what you wrote. (And it’s also not the same as saying that pi can’t appear as a term in an equation, as in Euler’s famous e^{i * pi} + 1 = 0.)

I don’t have any problem with trying to simplify infinity for non-mathematicians. As for keeping sets out of the explanation, well, we’re about the same age, meaning we took math before teaching sets was part of the New Math. Would younger readers want sets? I just don’t know.

The trap lays in simplifying yet getting every aspect completely and technically correct. I don’t think you managed. It’s only a small correction, though.

6

Are you speaking of ways to estimate pi? This is what I meant by approximations. If pi could be produced algebraically - and yes, by this I mean as the root of a non-constant polynomial etc. - it wouldn’t be a transcendent number.

This is a fundamentally different issue, and is purely a function of the fact that we use a base-10 counting system as opposed to base-3 or something. To conflate the two cases confuses things.

Yes, of course this is what I meant. For obvious reasons I wanted to avoid saying “root of a non-constant polynomial…” It seemed to me that saying pi couldn’t be produced algebraically was a simpler way of putting this. I can see that some mathematicians agree me with there and some don’t.

I wasn’t trying to come up with a rigorous proof - obviously I skipped some important steps, for example the demonstration that the rational numbers are countable. I did hope to provide enough steps to enable non-mathematicians to grasp the concept intuitively. Once you do, the diagonal argument, which is initially a little off-putting, makes perfect sense. I concede I might have done a better job of explaining than I did.

7

True, but 1/3 produces the exact value. Base-ten expansions are not the only way of expressing numbers.

And while “numbers that can be generated algebraically” isn’t synonymous with “algebraic numbers”, it’s still a countable set. In fact, the set of all numbers which can be expressed using a finite amount of notation in any given notation system is a countable set.

8

Oh, and presenting an example of a countable subset of the rationals (like 1, 1/2, 1/3, 1/4, …) is not a good way to motivate the idea that the rationals are countable. It’s also not too hard to come up with a countable set of transcendental numbers (say, pi, pi+1, pi+2, pi+3, …).

9

More to the point, 1/3 = .3333… can be expressed exactly as “x” where 3x-1=0. It’s polynomial in other words; whereas Pi can only be expressed as the limit of an infinite iteration of an algorithm.

I’ve heard that Aleph-2 is the number of all possible curves of a given length. One site explained it this way:
“Aleph-two: one example is the number of open curves of length 1. Imagine you’re driving from the start to the end of one particular curve. Any particular point on the curve, you could be turning to the left or to the right. Since there’s aleph-one particular points on the curve, it takes aleph-one bits of information just to describe one particular curve. The set of all of them is larger.”

Is this correct?

10

By the way, before any of the professional mathematicians get in here, aleph-1 isn’t technically defined as the size of the set of reals; it’s defined as the size of the smallest infinite set which is strictly larger than the integers (and likewise, aleph-2 is the size of the smallest set strictly larger than a set of size aleph-1, and so on). It’s common to postulate that aleph-one is the size of the set of reals (an idea known as the Continuum Hypothesis), but that can’t be proven or disproven in standard mathematics: One can construct models of mathematics in which it is true, and one can construct models where it’s false, and both are equally valid.

11

It is certainly true that the set of functions from the reals to the reals is strictly larger than the set of reals, but most of those functions, most folks wouldn’t call “curves”. You’d have to precisely pin down what other properties a “curve” has to have to be able to answer that one.

12

The number of continuous functions from the reals to the reals is 2^c = 2^{beth_1} = beth_2 (at least, in the same classical framework as everything else here). Under the generalized continuum hypothesis (i.e., assuming that the beth and aleph series coincide), this is aleph_2, but of course, as properly pointed out above, in standard formalizations of set theory without such an axiom tossed in by hand, the beth and aleph series are perfectly free to come apart.

(I realize I forgot to explain what the beth series is; the beth series is what a lot of people assume the aleph series is: beth_0 = cardinality of the integers, beth_{n+1} = 2^{beth_n}, and beth_a for positive limit ordinals a is the supremum of all previous beth numbers)

13

Wait, what was I saying? The number of continuous functions from reals to reals is beth_1 = c, not beth_2 (a continuous function f is completely specified by saying which rationals q and r satisfy r < f(q); that is, it is completely specified by a subset of pairs of rationals, of which there are only beth_1; thus, the number of continuous functions is at most beth_1, and it’s easy to see that it’s at least beth_1 as well (since, for example, there are constant functions outputting each real)). My bad.

So, yeah. With just the modest requirement of continuity, there aren’t aleph_2 many curves, unless you take beth_1 to equal aleph_2 (which, to be fair, some people do, as mentioned above… (Goedel, for instance)).

14

True, but irrelevant to my point.

Yes, this is equivalent to saying it’s not transcendental. Again, it’s irrelevant to the fact that pi can be expressed as the limit (sum) of an algebraic set of processes.

It was the terminology I was disageeing with, not the underlying concept.

15

> > Better to say, “these sets are the same size”.

> Not really. The point of the column is that infinities may be of
> different sizes. I’m not trying to explain set theory.

The material you are presenting is part of set theory. Whether “infinities may be of different sizes” depends on what you mean by “infinities”, since this isn’t a standard locution. Using standard terminology helps the reader communicate with other people and read more on a subject. What you wrote is fine for a title, but the article should then explain what you mean. There are other infinities in Mathematics. For example, the infinities you are discussing are different from the oo symbol (the “8” on its side) that many people have encountered in Calculus class.

I fear I wasn’t clear what I found problematic about your examples. The problem is they are subsets of the sets whose size you are considering rather than being the entire set. I fear this obscures the point.

> I’m trying to make the point that SOME sets of irrationals are
> countable. The divide of interest isn’t between the rationals and
> irrationals, but between the countable numbers (the algebraic
> numbers) and the uncountable ones (the transcendants).

This seems to me to be misleading or wrong. The irrationals are uncountable. So, in terms of size, the divide between the rationals and irrationals is exactly the same as the divide between the algebraics and transcendentals.

Your discussion seems to give the impression that the type of number in the set is important rather than just how many there are.

Why do you call the algebraic numbers the “countable numbers”? Perhaps you think that this is the largest subset of the reals that is countable? This isn’t true.

Also, the word is “transcendentals”, not “transcendents”.

> For a set to be countable, you need an algorithm that will let you
> generate its members. That’s what the diagonal procedure you
> describe above does. I’m puzzled that you think this is irrelevant,
> and fear I have expressed myself poorly.

You do not need an algorithm. There is nothing in the definition of “countable” that mentions algorithms. For the examples you will find in an introductory discussion, we prove a set is countable by exhibiting the one-to-one correspondence. But, this is not required.

There are only a countable number of algorithms, but there are an uncountable number of subsets of the natural numbers. Hence, most subsets of the natural numbers cannot be generated by an algorithm. All of these subsets are countable (since the natural numbers are countable).

> That said, I’d be better off amending the cited sentence to read,
> “The real numbers include sets of numbers that can be counted and
> another set of numbers, the transcendentals, that can’t.”

I agree this is better (in particular, you use the word “set”), but it could be better still. There is nothing special about the real numbers in this regard. Any uncountable set contains countable subsets. The word “contain” is better terminology than “include”. Saying, “and another set”, gives the impression that this is the only uncountable subset of the real numbers, which is not true.

> > > The proof of this was devised by the aforementioned Georg Cantor
> > > and makes use of an ingenious diagonal argument. I won’t attempt
> > > to explain it here, but the gist is that for any possible list
> > > of numbers you could devise, there’s some additional number that
> > > isn’t on the list and thus won’t be counted.
> >
> > The statement, “for any possible list of [real] numbers you could
> > devise, there’s some additional number that isn’t on the list”, is
> > just another way of saying that the set of real numbers is not
> > countable. Cantor’s diagonal argument shows how, given a list of
> > real numbers, to construct a number not on the list. This proves
> > that the set of real numbers is not countable.
>
> Just my point.

Sorry. Maybe I wasn’t clear. The problem is that you wrote “the gist is”. What you wrote is not the gist of the proof, but merely a restatement of what is to be proved using slightly different words.

> Instead I wanted to edge into the notion that some real numbers (if
> you insist, some sets of real numbers) were countable and others
> weren’t

The phrase “some real numbers are countable” seems to say that some real numbers can be in a countable set and others can’t. Anyone who understands the material knows this isn’t true, but I fear that people who don’t know the material will get this impression. Any real number (even transcendental ones) may be in a countable set, as long as there aren’t too many of them in the set.

I have nothing against edging into the notion. My concern is that some of your examples are more confusing than enlightening.

> Yes, of course this is what I meant. For obvious reasons I wanted to
> avoid saying “root of a non-constant polynomial…” It seemed to me
> that saying pi couldn’t be produced algebraically was a simpler way
> of putting this.

The problem is that by using new terminology without clearly saying what you mean, you run the risk of being misunderstood. The phrase “produced algebraically” seems to mean that the number can be expressed using the basic arithmetic operations (addition, subtraction, multiplication, division, roots) applied to the natural numbers. I doubt someone who wasn’t already familiar with the material would realize that this isn’t what you mean. In general, there is no such expression for the roots of polynomials above degree four.

The “non-constant” isn’t needed. Someone should fix Wikipedia. They probably meant “non-zero”, although this is kind of obvious, and could certainly be left out in an expository article. So, the choices are “root of a polynomial” or “produced algebraically”. I hope most high school students know what the former means.

> I can see that some mathematicians agree me with there and some
> don’t.

Not everyone who knows some mathematics is a mathematician.

16

It is hard to know if what you say is correct unless you are more precise. What do you mean by “produce pi algebraically” and “express pi in a finite number of steps”?

17

I’m not sure what what you mean by “expressed”. Giving an equation that the number is the root of is not usually considered to be expressing the number.

pi is not defined using an iterative algorithm. It is usually defined either as the ratio of the circumference of the unit circle to its diameter or (more conveniently these days) the area of the unit circle.

18

If someone wants to assume the Continuum Hypothesis, they will explicitly state it in the hypotheses of the particular theorem. I think it is rather uncommon for an author to assume it for all they are doing.

19

I didn’t know Gödel did that. Do you know what his reasons were?

20

I disagree, it is fairly standard to say that pi cannot be expressed algebraically as it is generally understood that an algerbraic expression contains only integers and a finite numer of steps (or can be re-written as such).