Let's begin with the guessing game that I found in my old Pascal book -- you know, the one I talked about in my last post. We found out that if I were thinking about a natural number, you can easily come up with an algorithm to guess it -- just guess all the natural numbers in order. Similarly, if I were thinking about an integer, you can also come up with an algorithm to guess it -- first guess 0, then 1 and -1, then 2 and -2, then 3 and -3, and so on.
Now the Pascal author only considered natural numbers and integers, but we, being math teachers, can easily come up with more sets of numbers:
-- Suppose I am thinking of a fraction. Is there an algorithm to guess my number?
-- Suppose I am thinking of a decimal. Is there an algorithm to guess my number?
As it turns out, both of these questions have known solutions. It was the German mathematician Georg Cantor who discovered the answers to these. Yes, this is the same Cantor for whom the Cantor set fractal was named. But actually, Cantor is best known not for the Cantor set, but Cantor's set theory -- especially the theory of infinite sets. Kung begins the lecture by telling us about Cantor -- a mathematician whose best years were the decade from 1874 to 1884. Afterwards, he suffered from a mental illness -- many believe it's because his work was criticized so often that he simply couldn't handle all the stress.
So let's describe how Cantor would have answered the question about fractions. According to Kung, there are two ways to solve this problem. One is to notice that, since fractions can have any natural number in the numerator and another natural number in the denominator, we can imagine the denominator as the bus number and the numerator as the seat number. Actually, to prevent equivalent fractions from being counted twice, Kung assumes that only reduced fractions are actually sitting in each bus. So now we've reduced this to a problem that we've already solved. We already know how to load infinitely many passengers from infinitely many buses into Hilbert's Hotel -- take the first fraction from the first bus into Room 1, then one fraction from each of the first two buses into Rooms 2 and 3, then one from each of the first three buses into Rooms 4-6, and so on.
Then you can call out all of the occupants of the rooms in order -- the order works out to be:
1, 2, 1/2, 3, 3/2, 1/3, 4, 5/2, 2/3, 1/4, 5, 7/2, 4/3, 3/4, 1/5, 6, 9/2, 5/3, 5/4, 2/5, 1/6, 7, ...
and provides an algorithm for you to guess my fraction, no matter what it is. Notice that, just as the Common Core distinguishes between fractions (which must be positive) and rational numbers (which can be zero or negative as well), we can play the game with the full set Q of rationals as well. We just use the same trick that we used for the set Z of integers -- start with 0, then call out the each positive rational with each negative rational, as in 1 and -1, 2 and -2, 1/2 and -1/2, 3 and -3, and so on. Kung likens this to a zipper, one side with all the positive rationals, and the other side with zero and the negative rationals. We just pull up the zipper, and then we have a guessing algorithm for the rationals:
0, 1, -1, 2, -2, 1/2, -1/2, 3, -3, 3/2, -3/2, 1/3, -1/3, 4, -4, 5/2, -5/2, 2/3, -2/3, 1/4, -1/4, 5, -5, ...
Let's remind ourselves what we're really doing here. This above list contains all rationals. It tells us how to fit all the rationals into Hilbert's Hotel:
Room 1: 0
Room 2: 1
Room 3: -1
Room 4: 2
Room 5: -2
Room 6: 1/2
Room 7: -1/2
Room 8: 3
Room 9: -3
It therefore gives us a 1-1 correspondence between N and Q. Set theorists often use a special word, bijection, to refer to such a function, but we'll follow Kung and call it a 1-1 correspondence. It shows us that N and Q have the same cardinality -- or in U of Chicago notation, that N(N) = N(Q). My old set theory book would say that Q is a denumerable set. Actually, the word "denumerable" isn't used that often any more (recall that my book was written about three-quarters of a century ago). Instead, I will use the word that Kung and most other set theorists use nowadays -- countable.
Kung states that there's a second way to show that Q is countable. Instead of using infinitely many buses, we use another trick based on the Fundamental Theorem of Arithmetic. To assign a rational to a room, we raise 3 to the power of the numerator times 5 to the power of the denominator. If our rational is negative, we just double the product. So now every rational is in a room -- but of course, there are lots of empty rooms.
Kung solves this by using the Cantor-Schroder-Bernstein Theorem -- if there are two sets S and T with a 1-1 function from S to T (which isn't necessarily a 1-1 correspondence because it may skip some elements of T -- the empty rooms) and another 1-1 function from T to S, then there also exists a 1-1 correspondence from S to T and so N(S) = N(T). We've already placed the fractions in rooms, so mapping each fraction to its room number is a 1-1 function from Q to N. Kung doesn't mention what 1-1 function maps N to Q, but this is trivial -- just map 1 to 1/1, 2 to 2/1, 3 to 3/1, and so on. That is, just map each natural number to itself, since every natural is rational. (This function has a special name -- the inclusion map.) Then by Cantor-Schroder-Bernstein, N(N) = N(Q).
So we see that N, Z, and Q are all countable sets. Before Cantor, we might have thought that Q is larger than Z, which in turn is larger than N -- Euclid once said that the whole is always larger than the part. But after Cantor, we now know that all three sets have the same cardinality.
There's one more question that we have yet to answer -- is there an algorithm for our guessing game as played using decimals? First of all, keep in mind that decimals can be very complicated. A decimal such as 1/2 = 0.5 is simple, but look at 1/3 = 0.333..., a repeating decimal. And of course, we celebrate one of the most famous decimals every March 14th -- 3.14159265358979..., which doesn't even repeat, much less terminate.
This reminds us of the eighth grade Common Core Standard: "Know that numbers that are not rational are called irrational. Understand informally that every number has a decimal expansion." If there were no irrational numbers, we could simply convert all of the rationals currently in Hilbert Hotel to decimals and we'd be done. But we have to work in all of the irrationals as well.
As Kung points out, after seeing the examples with Z and Q, most people are now just waiting for the clever trick that will allow us to fit all of the decimals into Hilbert's Hotel. But as it turns out, this isn't so simple. But Cantor's solution is one of the best-known theorems in all of mathematics -- and it astounded me when I first read about it in my set theory book back when I was a high school senior.
We begin as Cantor did -- let's imagine what a solution would look like. We would have every decimal in a room -- and we'd be able to prove it by giving a list of all of the decimals. So all we have to do is check the list -- if all the decimals are listed then we have a 1-1 correspondence, and if there's a decimal missing then we don't have a 1-1 correspondence.
But how can we tell whether there's a decimal missing from the list? Kung suggests playing another game -- a game of Dodgeball. So let's modify our guessing game a little. Instead of having you try to guess my number, I will instead try to dodge your guesses. Each time you give a guess, I'll give a digit that will avoid all of your guesses. If I can avoid all of your guesses, then I have a number that isn't on the list and I win -- if I can't, then you win. Of course, if you have a complete list of decimals (a 1-1 correspondence) then there would be no way for me to dodge all of them.
To make the game simpler, Kung suggests having only five digits, and letting each digit be either zero or one. So on your turn, you post five binary digits, and on my turn, I add one more binary digit to my one number. The game ends after five turns. If I was forced to choose one of your numbers then you win, and if I dodged all of your numbers, then I win. So let's play:
Your Turn: 01000
My Turn: 1
Your Turn: 11101
My Turn: 00
Your Turn: 10100
My Turn: 000
Your Turn: 10010
My Turn: 0000
Your Turn: 10000
My Turn: 10001
Let's see who won: your numbers are 01000, 11101, 10100, 10010, and 10000, while my number turns out to be 10001. I dodged all your numbers, so I won!
Of course, now you may be saying that it's easy for me to win. Each time you wrote a zero in a given place, I wrote a one, and each time you wrote a one, I wrote a zero. So it's easy for me to win. But that is precisely the point.
Now let's play with actual real numbers:
Your Turn: .9293020214...
My Turn: .6
Your Turn: .8569378772...
My Turn: .66
Your Turn: .3578110034...
My Turn: .666
Your Turn: .1769761505...
My Turn: .6666
Your Turn: .4552619933...
My Turn: .66668
Your Turn: .6835320759...
My Turn: .666686
Your Turn: .9302868685...
My Turn: .6666866
Your Turn: .2668818128...
My Turn: .66668666
Your Turn: .7235519668...
My Turn: .666686668
Your Turn: .7981213176...
My Turn: .6666866688...
Notice that I always choose to write a six -- unless you wrote a six, when I write eight instead. After my first turn, we know that my number won't be in Room 1. After my second turn, we know that my number won't be in Room 2. After my third turn, we know that my number won't be in Room 3. So after infinitely many turns, we know that my number won't be in any of the rooms. This is called Cantor's Diagonal Argument, since the digits we focus on fall on a diagonal of the list. Using Cantor's Diagonal trick, I win every single time you give me a list.
This trick works for any list that you can give me. In particular, it works for a list that you claim is a 1-1 correspondence between N and the set of decimals. But how can it, when by definition, every decimal is on the list, so that there's no decimal left for me to win?
The answer is -- you only assumed that every decimal is on the list. I just showed that the assumption that every decimal is on the list leads to a contradiction. And so, we actually just gave an indirect proof of something -- but of what? We assumed that there exists a 1-1 correspondence between N and the set of decimals, so we actually just proved that no such 1-1 correspondence exists. QED
The set of all decimals has a special name -- the set of real numbers, symbolized R. So what we just proved is that N(R) > N(N). The set of reals is uncountable. And so the answer to our original problem is that there is no algorithm that will allow you to win the game with real numbers (whether as the original Pascal guessing game or as the Dodgeball game). As the title of this episode implies, there is more than one type of infinity.
So my old intuition was right -- there are more real numbers than integers. But my way of thinking about it was completely wrong -- it has nothing to do with there being infinitely many reals between the integers (since there are infinitely many rationals between them, yet these are countable). In particular, it is misleading to say that there are "infinity" integers and "infinity^2" reals. Instead, Cantor shows us how to use 1-1 correspondences to determine set size, or cardinality.
Here are a few more things I want to say about cardinality. My old set theory book also shows that there is another special set that has Q as a subset yet is still countable -- the algebraic numbers. These are the numbers x for which there exists a polynomial P, with integer (or rational) coefficients, such that P(x) equals 0. The number sqrt(2) is algebraic, and we can even count complex numbers such as sqrt(-1), which is i. But numbers like pi or e still aren't algebraic -- they are transcendental.
Many people have trouble realizing that Q is countable and R is uncountable, yet I had no problem with either of these. Instead, I couldn't believe that the set of algebraic numbers -- a set that contains irrationals (and even some complex numbers) yet is still countable. My set theory book explained that there is a trick similar to infinitely many buses -- the bus number can be the degree of the polynomials and the seating can be arranged by the sum of the absolute values of the coefficients.
Now think about this -- R is uncountable, while there are countably many rationals. So what about the set of all irrationals? It's easy to come up with an indirect proof to show that the set of irrationals is uncountable: first assume that the set of irrationals is countable. Then it would be easy to show that the set of all reals would also be countable, using the integer or zipper tricks -- just place the rationals on one side and the irrationals on the other, and pull up the zipper. But this is a contradiction, since the set of all reals is uncountable. So the assumption that the set of the set of irrationals is countable leads to a contradiction -- therefore the set of irrationals is uncountable. QED
So we now have two uncountable sets -- R and the set of irrationals (often written R \ Q). One of my favorite questions is, is there a 1-1 correspondence from R to R \ Q? As it turns out, there does exist such a 1-1 correspondence, and we can prove it. Let's think of in terms of a Hilbert's Hotel -- except it's an uncountable hotel with a room for every irrational. Now a bus arrives containing all of the rational numbers. How can we fit them into the hotel?
Well, let's take our favorite irrational, pi, and so we add pi to every rational. We see that the sum of a rational and an irrational is irrational, and so we can ask each rational to go to the room where that irrational is presently sitting. And where do those irrationals already in those rooms go? By now we should know the Hilbert's Hotel pattern -- they add pi to themselves to get new irrationals, and then go to the room where those new irrationals are. In other words:
The number x + n * pi (x, rational, n a whole number) goes to room x + (n + 1)pi.
Of course, we must be careful that x + (n + 1)pi isn't accidentally rational. But there is an indirect proof that it's always irrational: assume that x + (n + 1)pi = y is rational. Then rearranging the equation, we obtain pi = (y - x) / (n + 1), the quotient of two rationals, so is itself rational. So we get that pi is rational -- a contradiction since pi is irrational. Therefore x + (n + 1)pi is irrational. QED
We notice that in this case, there are uncountably many rooms, yet only countably many occupants need to change rooms. Most irrationals don't have to move -- in particular, sqrt(2) doesn't move, neither does e, and neither does -pi.
Here's another thing I've noticed -- sets of numbers that are special, or fit some sort of pattern, tend to be countable, while sets of numbers that don't fit patterns tend to be uncountable. The natural numbers fit the ultimate pattern -- 1, 2, 3, so they are countable. The rational numbers are countable (they fit the pattern a / b), while the irrationals are countable. The algebraic numbers are countable (they fit into polynomials), while the transcendental numbers are uncountable.
What about the set of all numbers consisting of the digits 0 and 1 only -- is it countable? Even though this may sound like a pattern, it really isn't. After all, in binary, all reals consist of only two digits, so consisting of two digits isn't special enough to make the set countable. The set of reals with only two digits is uncountable, regardless of which digits or the base. (In the special case of 0 and 1, we can play Kung's original Dodgeball game to see why.) If the digits are 0 and 2, and the base is changed to ternary (base 3), we obtain a famous uncountable set -- the Cantor fractal set!
The Quick Conundrum for today involves Kung taking a vacuum tube, grabbing one end of it, and spinning it around over his head. This causes a sound to be heard -- a musical note. He points out that we might expect there to be a full uncountable continuum of possible notes -- but instead, only countably many notes are possible. And these notes follow a pattern. I recognized one of the notes as F, the next higher note as A, and then the next note as a high C.
Hmmm, F-A-C -- musicians should recognize this as a F major chord. I mentioned last April that musical notes aren't random, but instead they follow a pattern based on the harmonic series. In this case the fundamental tone corresponds to the length of the tube, and then the second harmonic is half the length, the third is one-third the length, and so on. The notes I heard on the video, F, A, C, correspond to the fourth, fifth, and sixth harmonics. I also heard one more note -- the seventh harmonic, which sounds sort of like Eb (E-flat). (I discussed the problems musicians have with the seventh harmonic in another post back in May.) As it turns out, air flowing through a tube to produce these harmonics are exactly how woodwinds work.
Look at this post so far -- I'm such a nerd that most of my posts are about math, and when I finally do something else such as watch a DVD, the DVD ends up being about math -- and then I spend a great deal of time writing about it on the blog. Well, here's something I'm enjoying now that's not math, but music (speaking of which) -- I am about to read Marcia Davenport's 1932 biography about one of the most famous musicians of all time -- Wolfgang Amadeus Mozart. I'm timing it so that I finish the biography on January 27th -- the classical musician's 260th birthday. (Yeah, and when I do read something about music, it's not one who's alive now, but one who lived centuries ago -- which still, apparently, makes me a nerd. But no, I won't devote any blog posts to Mozart.)
Indeed, I found the following article which describes a link between math and classical music. Of course one of the musicians mentioned in the article is Mozart:
http://www.schillerinstitute.org/fid_91-96/944_math_music.html
A few excerpts from the article:
All Classical musical composition is inherently paradoxical. The beauty of a musical composition increases with the ability of the composer to maintain a unity of effect throughout the composition, while increasing the complexity (density of change) in the composition.
[paradoxical -- hey, that reminds me of Kung's course on paradoxes -- dw]
Such increases in power can themselves be ordered according to what Georg Cantor defined in mathematical terms as cardinalities. Each higher cardinality is characterized by a unity (One), of increasing complexity (Many). Each higher cardinality subsumes all lower ones. Each successive higher cardinality is generated as a solution to a fundamental paradox existing in its predecessor. Such paradoxes are perceived by our senses, in this case hearing, as mathematical discontinuities or singularities. As we will see, the generation of rising powers (cardinalities) of creative thought, is the subject matter of great Classical musical composition.
[Cantor and cardinalities -- doesn't that sound familiar? -- dw]
With all of this talk about two of my favorite subjects -- infinity and music -- is there any room left in this post for the actual blog topic, Geometry? Well, let's get on with it.
The topic for this week are the concurrency theorems. There are four of them -- circumcenter, orthocenter, incenter, and centroid. I would spend a day on each one, except that I want to be finished with all of them in just three days. I will cover the two simpler ones -- circumcenter and orthocenter -- in today's post. As it turns out the orthocenter of one triangle is the circumcenter of a larger triangle, so these two are related.
This is what I wrote last year about the circumcenter and orthocenter of a triangle:
As it turns out, Hung-Hsi Wu proves all four of these concurrency theorems, as opposed to the U of Chicago, which only discusses one of them. We know enough to prove two of them using results from Chapter 5 and before -- the circumcenter and orthocenter -- the other two are more difficult and must wait until later this week. Therefore, most of this post will be cut-and-paste from the proofs given by Wu.
We begin with the circumcenter, the intersection of the perpendicular bisectors. This is the only concurrency theorem mentioned in the U of Chicago. (The theorem numbering is Wu's.) The first part of Wu's proof is nearly identical to the U of Chicago's:
Theorem 13.
(i) The perpendicular bisectors of the three sides of a triangle meet at
a point, called the
circumcenter of the triangle. (ii) There is a unique circle that
passes through the vertices of a triangle, and the center of this circle
(the circumcircleof the triangle) is the circumcenter.
Proof.
Let the triangle be ABC, as shown, and let M, N be the midpoints of BC andAC, respectively. Also let the perpendicular bisectors of BC, AC be m and n,
respectively. Let
m and n meet at O.
Since
O lies on the perpendicular bisector of BC, OB = OC (Perpendicular Bisector Theorem). Similarly,OC = OA. Together, we have OB = OA = OC, i.e.,
O is equidistant from A, B and C. In particular, O is equidistant from A and .B
By the Converse of the Perpendicular Bisector Theorem, O lies on the perpendicular bisector of AB. As
O already lies on the perpendicular bisectors of BC and AC, this proves the rst
part of the theorem.
To prove the second part, we have to rst prove that there is a circle with center at
O that passes through the vertices A, B, and C, and that any such circle must
coincide with this circle. Consider the circle
K with center O and radius OA. K
must pass through
B and C, on account of OB = OA = OC, so we have proved
the existence of such a circle. Next,we have to show that any other circle
K0 passing throughA, B and C must coincide with K. Let the center of K0 be O0. Since O0 is
by definition equidistant from
B and C, O0 lies on the perpendicular bisector of BC(Converse to PBT), and therefore lies on
must also lie on
n, the perpendicular bisector of AC. Therefore O0 is the point of
intersection of
m and n, which is O. This shows O = O0. Since K0 passes through A,
the radius of
K0 is also OA. Hence K0 = K because they have the same center and
the same radius. The proof of the theorem is complete.
But then, as I pointed out earlier, part of this proof depends on some Parallel Postulate. I want, in fact, to use our version of the Fifth Postulate, since all that's needed for the proof was the part about Perpendicular to Parallels. But unfortunately, I couldn't find a way to avoid an indirect proof. (Wu, in a Remark, also refers to this fact that m and n don't necessarily intersect at any point, much less O, without a Parallel Postulate. In non-Euclidean hyperbolic geometry, this theorem is in fact false.)
Assume that m and n don't intersect -- that is, that they are parallel. It's given that m is perpendicular to BC and n is perpendicular to AC. So, by the Fifth Postulate, both BC and AC are perpendicular to m, so, by the Two Perpendiculars Theorem, BC | | AC. But C is on each line. So lines BC and AC are identical, and the three points are collinear. But A, B, and C are the vertices of a triangle, so they can't be collinear. This is a contradiction. Therefore m and n intersect. QED
Notice the similarity between this and the proof of the Two Reflection Theorem for Translations. I point out that the key difference is that in the latter, we were trying to prove that three points are collinear, whereas here, we use the fact that three points aren't collinear to derive a contradiction in an indirect proof.
Now for the other proof -- the orthocenter proof. I will cut and paste Wu's proof. In his proof, he ends up showing that the orthocenter of a triangle is the circumcenter of a larger triangle!
The three altitudes of a triangle meet at a point, called the orthocenter
of the triangle.
Proof.
Let the altitudes of triangle ABC be AD, BE and CF. Through each vertex,
draw a line parallel to the opposite side, resulting in a triangle which we denote by
triangle A0B0C0.
By construction, the quadrilaterals
AC0BC, ABCB0 are parallelograms. Therefore,
by the Parallelogram Theorem (opposite sides are congruent)
C0A = BC = AB0. Thus A is the midpoint of
C0B0. Moreover, since AD perpendicular BC and BC | | C0B0, we also know that AD perpendicular C0B0
(by our Fifth Postulate). It follows that
Line AD is the perpendicular bisector of C0B0. Similarly,
Line FC and Line BE are perpendicular bisectors of A0B0 and C0A0, respectively.
By Theorem 13,
Line AD, Line FC and Line BE meet at the circumcenter of triangle A0B0C0. The proof
is complete.I provide no exercises for this lesson/activity -- since the proofs are difficult enough on their own.
Let's end this post with one more thing about Cantor's infinities. So far, we found out that contrary to our belief that there should be only infinity, Cantor showed that there are two infinities. The first infinity, called countable infinity, is the cardinality of the set of naturals, the set of integers, and the set of rationals. Another infinity is uncountable, and is the cardinality of the set of irrationals and the set of all real numbers. So now we ask, are there only two infinities? Kung hints that he will answer that question in his next lecture, so stay tuned!
No comments:
Post a Comment