Thursday, January 14, 2016

Review for Final Exam (Day 84)

Lecture 10 of David Kung's Mind-Bending Math is called "Godel Proves the Unprovable." In this lecture, Dave Kung discusses one of the most amazing, yet most important, proofs of all.

As he often does, Dave Kung begins by telling us a little about the mathematician himself. Kurt Godel was born in Austria, but changed citizenship several times due to various wars before eventually moving to the United States. (By the way, the name "Godel" should be spelled with an umlaut -- two dots above the letter "o." Sometimes the German o-umlaut is transliterated into English as "oe," so technically I should be spelling his name "Goedel" if I want to write the name in ASCII. But the spelling "Godel" is so common that I use it.)

Kung alluded to Godel back in the first lecture. He mentioned that Godel showed that the statement "This statement is unprovable" is true yet unprovable. There's a similar-sounding statement, Curry's Paradox, that has no impact on mathematics because it's not a mathematical statement. But Godel's statement can be written using numbers, and so it does affect mathematics -- it demonstrates that there are statements that aren't provable. Before Godel, mathematicians beginning with Hilbert were hoping that all true statements can be proved to be true, but the Austrian showed them that they were wrong.

Kung devotes the rest of the lecture to showing how "This statement is unprovable" can be written as a mathematical statement. He mentions various tricks using the primes and the Fundamental Theorem of Arithmetic -- each word and symbol corresponds to a number, the exponent of a prime, and so entire statements end up being associated with very large numbers -- its Godel number.

By the way, notice that because Godel's proof refers to arithmetic, it doesn't refer to other unrelated mathematical systems, such as Geometry. So Euclidean geometry is safe -- all true geometrical statements are provable. In other words, Geometry is complete. But arithmetic isn't complete.

The Quick Conundrum for today is on optical illusions. Kung shows us two such illusion -- one where lines that appear to bend are actually parallel, and another where circles appear to be spirals. I provide the following link to some neat optical illusions:

I've heard of Godel numbering before watching this lecture, but I admit that it's a bit complex for me to understand, even after Kung's explanation. Rather than attempt to describe Kung's lecture for today in this post, I will take a few steps back and say a few more things about some misconceptions I had as I was learning about set theory from my old 1940's text.

In an earlier lecture, Kung tells us that not only are there are infinitely many infinities, but the cardinality of the set of infinite cardinals is larger than any infinite cardinal -- a paradox known as Cantor's Paradox. This was stated in my old set theory text, but naturally it confused me.

In that old text, the smallest infinite cardinal -- countable infinity -- was called a. If a set has cardinality a, its power set has cardinality 2^a, or c -- c is the cardinality of the set of real numbers. If a set has cardinality c, then its power set has cardinality 2^c, or f, and so on. Nowadays, the symbols a and f are not used any more -- but the letter c, which stands for "continuum" (as in the continuum of the real numbers), is still used occasionally,

I once thought that the number of infinities, while infinite, was countable. Here's why -- let's fit the cardinals into Hilbert's Hotel. We place the cardinal a in Room 1, then c in Room 2, then f in Room 3, then the cardinality of its power set 2^f in Room 4, and so on. So in each room, we take the power set of the previous cardinal and place it in the next room. So there are infinitely many cardinals inside of Hilbert's Hotel. But any set that fits in the hotel is countable, of cardinality a -- and the cardinal a sits in Room 1, the smallest cardinal in the hotel. So how can the number of cardinals be more than the largest cardinal in the hotel -- which is Cantor's Paradox?

I thought the reason was that I had skipped the cardinals between the cardinals in the rooms. Kung tells us how Cantor came up with the Continuum Hypothesis, which states that there is no cardinal between a (countable infinity) and c (the size of the reals). Cantor was hoping to prove it, but he was unable to. It was Godel and another mathematician, Paul Cohen, who ultimately proved that trying to prove or disprove CH from the other axioms is as futile as trying to decide Euclid's Fifth Postulate from the other four axioms. (That's the point of today's lecture -- some things are unprovable!) But I believed that there must be some cardinals that don't fit in the rooms in order to trigger Cantor's Paradox -- that is, even if there is no cardinal between a and c, there must be a cardinal between the one in Room n and the one in Room n + 1, for some n. Even if CH is true, I thought that the Generalized Continuum Hypothesis (GCH) was provably false.

As it turns out, I was wrong. GCH is just as undecidable as CH. The answer is that I lacked the imagination to come up with greater cardinals -- the ones that lead to Cantor's Paradox. Suppose we go back to infinitely many buses, but instead of placing just one cardinal on each bus, we place an infinite number of passengers -- and the number of passengers is a different cardinal each time. So on the first bus there are a passengers, then c passengers on the second bus, f passengers on the third bus, 2^f passengers on the fourth, and so on. So how many passengers are there on all the buses? The total number of passengers on all the buses must be greater than the number of passengers on any individual bus -- so there we have it, a brand new cardinal. Set theorists refer to this new cardinal as a limit cardinal. And of course, we can take the power set of this new limit cardinal, and keep on going higher and higher. So that's why, as Kung tells us, there is no set of all cardinals -- if it existed, its cardinality would be larger than the largest cardinal, a contradiction.

Speaking of CH, here's another misconception I once had. I read somewhere that Godel and Cohen proved that CH is undecidable, and then I read somewhere else that Godel and Cohen proved that the Axiom of Choice is undecidable. So I actually believed that AC and CH were equivalent -- that is, we could use one to prove the other. As it turns out, I was wrong again -- indeed, Cohen used two different models to show that AC and CH are each independent of the other axioms.

My old set theory book also mentions that there are other infinities -- ordinal infinities rather than cardinal infinities. I mentioned these ordinals in an earlier post in October, back when we had the viral Common Core horror story about 5 * 3 equaling 5 + 5 + 5 or 3 + 3 + 3 + 3 + 3. As it turns out, with ordinals, order makes a difference -- and it works the opposite from that viral worksheet. The Common Core worksheet stated that 5 * 3 = 3 + 3 + 3 + 3 instead of 5 + 5 + 5, but if we use the ordinal "omega," we find out that omega * 3 = omega + omega + omega.

Why do I spend so much time discussing my old misconceptions about set theory and logic? I keep comparing it to Geometry -- in order to remind myself that many of my students consider Geometry to be as difficult as I once found set theory. So the next time I have a student who is confused about, say, the Parallel Postulate, I should think back to how I was once bewildered by set theory's Parallel Postulate -- the Axiom of Choice. It's the same reason I spent so much time discussing Mandelbrot's fractal dimension. By challenging myself, I can empathize with my students who are finding my Geometry curriculum a challenge.

Meanwhile, it's time to begin reviewing for the final exam. This is what I wrote last year about the big end-of-semester test:

In the district whose calendar I'm following, Tuesday, Wednesday, and Thursday are the official finals days next week. This means that today and tomorrow are excellent days for review.

Now I don't presume to know what your district is giving for a final. Most likely, your district is already giving some sort of common final, so I wouldn't need to post my own final. But I've decided that I will post my own final this week, as well as a review for that final. You, as a teacher, can still give my final review, if it can help your students review for your final.

All of these questions are based on the SPUR objectives from the U of Chicago text. I chose to leave out Chapter 1, since we only covered parts of that chapter. For Chapters 2-7, the breakdown by chapter will be as follows:

Chapter 2: 8 questions
Chapter 3: 10 questions
Chapter 4: 6 questions
Chapter 5: 8 questions
Chapter 6: 9 questions
Chapter 7: 9 questions

Like most high school finals, the exam will be multiple choice -- since most teachers don't have time to grade free-response finals before grades are due. But the review worksheets for this final will not be multiple choice, since it's just the review.

A few notes about the questions included on this review worksheet, which covers mostly Chapters 2 through 4 of the U of Chicago text (with two questions that require parallels from Chapter 5):

Question 8 requires a TI calculator, since it's a TI-BASIC question from Chapter 2. On the actual final, if the students don't have a calculator, they can simply use the formula to compute the number of diagonals in some polygon without needing a calculator at all.

Questions 11 and 17 require the students to draw angles of a certain measure. Hopefully, the students at least have protractors. The multiple choice questions on the final will be written such that students won't need the protractors.

Questions 14 and 18 require constructions -- that is, straightedge and compass. If these are not available to the students, then they can just freehand the necessary lines.

This is the final lecture on set theory and logic, so you readers are spared any more long discussions about complicated set theory. But at the end of this lecture, Kung tells the story of how Godel, just before he was to take the U.S. citizenship test, tried to point out to the examiner there's a loophole in the Constitution that would allow our country to devolve into a dictatorship. Believe it or not, this actually leads to the topic of Kung's next lecture...

No comments:

Post a Comment