Bad Math Books and Cantor Cardinality

A bunch of readers sent me a link to a tweet this morning from Professor Jordan Ellenberg:

The tweet links to the following image:

(And yes, this is real. You can see it in context here.)

This is absolutely infuriating.

This is a photo of a problem assignment in a math textbook published by an imprint of McGraw-Hill. And it’s absolutely, unquestionably, trivially wrong. No one who knew anything about math looked at this before it was published.

The basic concept underneath this is fundamental: it’s the cardinality of sets from Cantor’s set theory. It’s an extremely important concept. And it’s a concept that’s at the root of a huge amount of misunderstandings, confusion, and frustration among math students.

Cardinality, and the notion of cardinality relations between infinite sets, are difficult concepts, and they lead to some very un-intuitive results. Infinity isn’t one thing: there are different sizes of infinities. That’s a rough concept to grasp!

Here on this blog, I’ve spent more time dealing with people who believe that it must be wrong – a subject that I call Cantor crackpottery – than with any other bad math topic. This error teaches students something deeply wrong, and it encourages Cantor crackpottery!

Let’s review.

Cantor said that two collections of things are the same size if it’s possible to create a one-to-one mapping between the two. Imagine you’ve got a set of 3 apples and a set of 3 oranges. They’re the same size. We know that because they both have 3 elements; but we can also show it by setting aside pairs of one apple and one orange – you’ll get three pairs.

The same idea applies when you look at infinitely large sets. The set of positive integers and the set of negative integers are the same size. They’re both infinite – but we can show how you can create a one-to-one relation between them: you can take any positive integer i, and map it to exactly one negative integer, 0 - i.

That leads to some unintuitive results. For example, the set of all natural numbers and the set of all even natural numbers are the same size. That seems crazy, because the set of all even natural numbers is a strict subset of the set of natural numbers: how can they be the same size?

But they are. We can map each natural number i to exactly one even natural number 2i. That’s a perfect one-to-one map between natural numbers and even natural numbers.

Where it gets uncomfortable for a lot of people is when we start thinking about real numbers. The set of real numbers is infinite. Even the set of real numbers between 0 and 1 is infinite! But it’s also larger than the set of natural numbers, which is also infinite. How can that be?

The answer is that Cantor showed that for any possible one-to-one mapping between the natural numbers and the real numbers between 0 and 1, there’s at least one real number that the mapping omitted. No matter how you do it, all of the natural numbers are mapped to one value in the reals, but there’s at least one real number which is not in the mapping!

In Cantor set theory, that means that the size of the set of real numbers between 0 and 1 is strictly larger than the set of all natural numbers. There’s an infinity bigger than infinity.

I think that this is what the math book in question meant to say: that there’s no possible mapping between the natural numbers and the real numbers. But it’s not what they did say: what they said is that there’s no possible map between the integers and the fractions. And that is not true.

Here’s how you generate the mapping between the integers and the rational numbers (fractions) between 0 and 1, written as a pseudo-Python program:

 i = 0
 for denom in Natural:
   for num in 1 .. denom:
      if num is relatively prime with denom:
         print("%d => %d/%d" % (i, num, denom))
         i += 1

It produces a mapping (0 => 0, 1 => 1, 2 => 1/2, 3 => 1/3, 4 => 2/3, 5 => 1/4, 6 => 3/4, …). It’ll never finish running – but you can easily show that for any possible fraction, there’ll be exactly one integer that maps to it.

That means that the set of all rational numbers between 0 and 1 is the same size as the set of all natural numbers. There’s a similar way of producing a mapping between the set of all fractions and the set of natural numbers – so the set of all fractions is the same size as the set of natural numbers. But both are smaller than the set of all real numbers, because there are many, many real numbers that cannot be written as fractions. (For example, \pi. Or the square root of 2. Or e. )

This is terrible on multiple levels.

  1. It’s a math textbook written and reviewed by people who don’t understand the basic math that they’re writing about.
  2. It’s teaching children something incorrect about something that’s already likely to confuse them.
  3. It’s teaching something incorrect about a topic that doesn’t need to be covered at all in the textbook. This is an algebra-2 textbook. You don’t need to cover Cantor’s infinite cardinalities in Algebra-2. It’s not wrong to cover it – but it’s not necessary. If the authors didn’t understand cardinality, they could have just left it out.
  4. It’s obviously wrong. Plenty of bright students are going to come up with the the mapping between the fractions and the natural numbers. They’re going to come away believing that they’ve disproved Cantor.

I’m sure some people will argue with that last point. My evidence in support of it? I came up with a proof of that in high school. Fortunately, my math teacher was able to explain why it was wrong. (Thanks Mrs. Stevens!) Since I write this blog, people assume I’m a mathematician. I’m not. I’m just an engineer who really loves math. I was a good math student, but far from a great one. I’d guess that every medium-sized high school has at least one math student every year who’s better than I was.

The proof I came up with is absolutely trivial, and I’d expect tons of bright math-geek kids to come up with something like it. Here goes:

  1. The set of fractions is a strict subset of the set of ordered pairs of natural numbers.
  2. So: if there’s a one-to-one mapping between the set of ordered pairs and the naturals, then there must be a one-to-one mapping between the fractions and the naturals.
  3. On a two-d grid, put the natural numbers across, and then down.
  4. Zigzag diagonally through the grid, forming pairs of the horizontal position and the vertical position: (0,0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3).
  5. This will produce every possible ordered pair of natural numbers. For each number in the list, produce a mapping between the position in the list, and the pair. So (0, 0) is 0, (2, 0) is 3, etc.

As a proof, it’s sloppy – but it’s correct. And plenty of high school students will come up with something like it. How many of them will walk away believing that they just disproved Cantor?

24 thoughts on “Bad Math Books and Cantor Cardinality

  1. dtm0

    I think it might be acceptable to cover the cardinality of infinite sets in an enrichment section – and that’s what this text does.

    However, I don’t think it’s acceptable to write it without having it reviewed by a math PhD (I’m sure McGraw-Hill keeps a few on staff) to ensure that you don’t make obvious errors like this and then leave “derive Cantor’s argument” as a little exercise for the reader! (See the exercises on the last page; note exercise 3)

    1. markcc Post author

      I agree with you: I think it’s absolutely fine to cover the cardinality of infinite sets in an algebra class. It’s not something that I think is a required topic for algebra-2, but it’s an interesting thing that’s perfectly reasonable to cover.

      But if you’re writing a textbook for algebra-2, it’s not a required topic – so if you don’t understand it, don’t include it. It’s better to omit an interesting but optional topic than to include it but get it completely wrong.

  2. David Starner

    The context page implies that there’s worse to be found. The very first page is about Relations and Functions, one-to-one, onto, etc., looks very correct. Then the example:

    “State the domain and range of the relation. Does the relation represent a function?” and then a table I will represent as:

    {x, y}: {-1, -5}, {0, -3}, {1, -1}, {2, 1}, {3, 3}

    Okay? So it’s a function from the integers between -1 and 3, inclusive, to a subset of the integers. Their answer: “The domain and range are both all real numbers. Each element of the domain corresponds with exactly one element of the range, so it is a function.” No. The domain is -1, 0, 1, 2, 3; it could be taken as a subset of the real numbers, but the domain is not all real numbers. If it’s a subset of a larger relation (which nothing on that page implies), we have no reason to assume that it relates every element of the reals once and only once to another real number.

    I don’t know what to answer for the rest of the questions based on that answer. It’s like they copied the definitions, but didn’t understand them.

    1. markcc Post author

      I’ll defend them just a tiny bit on that one. It’s wrong, but it’s not quite so egregiously wrong. I’ve definitely seen things in my kids math texts that do things like use a generalized range for a function – so they’ll talk about a function from integers to integers, when it’s really a function from {1, 2, 3} to {4, 5, 6}.

      The domain and range of that relation do consist of real numbers, so if you’re playing that generalization game, it would be sort-of all right.

      The problem, though, is that the simplifications were in fifth grade general math textbooks; not high-school algebra-2 textbooks. A simplification that’s acceptable for a fifth grader becomes a glaring problem in an advanced high school class.

      1. David Starner

        Part of the problem is I don’t know how to answer the questions that follow; do they really keep asking “what’s the domain, what’s the range”, and expecting “the reals, the reals”, over and over?

  3. Clément

    “what they said is that there’s no possible map between the real numbers and the fractions. And that is not true.”

    Wouldn’t that be “integers” instead of “real numbers”?

    1. markcc Post author

      D’oh, yeah. Sometimes my fingers get ahead of my brain; but my brain still knows what it meant to say.. Fixed!

    1. decourse

      That is very beautiful indeed.

      While we’re on this topic: Mark, how about a blog post on the Cantor-Bernstein-Schroeder theorem? It’s come up before, because it’s a nice way to show that pretty much all Cantor crackpottery is wrong even without the axiom of choice, but I don’t think you devoted a blog post to it.

  4. Matti

    I’m a little confused of why you got so angry. A much bigger problem with school textbooks is that they are so incredibly boring, full of useless terminology and make students think math is super tedious and pointless. If someone thinks they have disproved Cantor, isn’t that exciting to them? Wouldn’t that make them interested?

    I understand some of those people are annoying to you, and that there are people trying to fool money with all kinds of ways (such as their own value of pi). That’s unlikely to change any time soon.

    1. David Starner

      You don’t see a problem teaching students that they can’t trust what’s in their textbooks? If the students distrust everything they’re being taught, school is a worthless waste of time on all sides. You fundamentally can’t be taught something if you don’t believe the teacher or textbooks are accurate, and you have no reason to believe they’re accurate if it’s obvious they aren’t.

      Trying to learn from a work with a lot of errors can be a incredibly frustrating experience.

      1. Matti

        Teaching students not to blindly believe the textbooks is actually one of the most valuable things you can teach them. Thinking that teacher or books are infallible is not a basis for a democratic society or independent thinking, that’s just learning to obey the authority.

        Textbooks shouldn’t be that central to teaching anyway, and having a few mistakes in them is not the end of the world. If you teach in a way that they become an issue, your problems are elsewhere.

        1. David Starner

          I wouldn’t worry that children get the idea that teachers and textbooks are infallible; if one excellent pair convince them of that, the next will disabuse them of the idea. If all else fails, we’ll send in the DARE dog who will remind them that most people who smoke pot instantly explode.

          Some teachers barely touch the textbook, some need the textbook to remind them of what they touched on way back when they were in school, some lean quite heavily on the books, and some abdicated teaching to them. Maybe that could be changed over decades and billions of dollars; more likely the political will, bureaucracy and human nature would stymie any such attempt. Textbooks are easy to change; every teacher, not so much. Moreover, some students learn best at the foot of a teacher, but some are visual learners with little tolerance for long lectures. Not worrying about textbooks will leave students with the wrong teach or wrong learning style in the lurch.

          Finally, if the textbooks don’t matter, why are we shelling out so much for them? We’re looking at $50-$100 a book, when there are decent public domain algebra textbooks that can be printed for $10-$15 a hardback volume in lots of 1,000. That’s a lot of money for stuff with major errors that don’t matter.

        2. John Fringe

          > Thinking that teacher or books are infallible is not a basis for a democratic society or independent thinking

          Here I’m a bit puzzled about your position. Exposing textbooks’ errors is not against dismantling the concept of infallibility of authority, that’s for sure. Textbooks have errors, that’s a fact, and exposing those errors is a better way to make people doubt about infallibility than conciously allow errors to go unnoticed, isn’t it?

    2. Lone Wolf

      Wrong statements in math textbooks are likely to inspire more confusion that excitement, especially if wrong and correct concepts are integrated in the mind (“But I don’t understand why this is so, it makes no sense to me, guess either I am bad at math or it’s all nonsense, anyway”).

  5. LoneWolf

    I don’t think that they meant to write about Cantor’s diagonal at all… Nothing in their “explanation” points to a misunderstood Cantor proof of real number – prime number different cardinalities. They genuinely seem to think that the set of fractions has a different cardinality than the set of primes. This mistake likely follows from the correspondence not being immediately intuitively clear.

  6. Shay Guy

    Another method I remember, which has a name I don’t recall:

    Imagine an infinite binary tree. The root is 1. Each element p/q, where p and q are natural numbers, has children p/(p+q) and (p+q)/q. Now do a breadth-first traversal. You get all positive rationals: “1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4…”

    This has the advantage that you don’t have to remove duplicates.

  7. Carl Sjostrom

    If I were a teacher, I would be glad to have a textbook like this. I would show it to my students and, for homework, I would ask them to bring a proof of the rational numbers being uncountably infinite. Naturally they would go to Google and very quickly, and with great joy, find that the book is wrong. Then I would talk to the students about “critical thinking” and why we should always verify everything that we are taught, and that would be the real purpose of the exercise.

    Now for the student who brings in a proof (even though it is wrong) I would give extra credit for actually thinking about it rather than relying on Wikipedia. I would be curious to know how many high school math teachers could explain why such a proof would be wrong?

    A proof might look something like this…

    Assume that the set Q is countably infinite.

    Then all the members of Q can be listed A(1)/x, A(2)/x, A(3)/x, … so that every numerator is an A(i) for some i and every denominator x is a number that makes the term unique and in simplest terms.

    We define another number A/x where A is a multiple of all the i’s where i > 0 and i is not a factor of the A(i) that it is paired with.

    But A/x is a member of Q so A/x = A(j)/x for some j. But this means

    1. If j is a factor of A then j is not a factor of A.

    2. If j is not a factor of A then j is a factor of A.

    We have a contradiction, since j must either be a factor of A or not a factor of A.

    Therefore Q is not countably infinite.

    The student gets an A+, and I get the sad chore of explaining to her why her proof fails.

  8. Tom Keel

    “… the set of all fractions is the same size as the set of natural numbers. But both are smaller than the set of all real numbers, because there are many, many real numbers that cannot be written as fractions.”

    That many reals are not fractions is not a proof that there are more reals than fractions. Otherwise, you could use the same kind of argument to prove that there are more fractions than integers. Right?

    1. John Armstrong

      That only shows that there are at least as many reals as rationals.

      Though, in fact, this highlights a choice of phrasing that Mark might want to change. The section you quote does not, in fact, prove what it claims to prove; just because there are many real numbers that cannot be written as fractions does not prove that the sets are not of the same cardinality. There are many rational numbers which cannot be written as integers either.


Leave a Reply