### Infinity and Logic

Last Saturday, we had two speakers Eric Brattain (me, our organizer) and Patrick Weed.

I spoke about a topic usually called countability. This is actual a fairly terrible name since it’s about precisely that which can’t be counted in the usual sense, infinite quantities of things. We used the classic example of the Hilbert Hotel to get a feeling for how to map infinite sets into each other.

Imagine a hotel where the rooms are numbered 1,2,3,4,… and for every whole number, there’s a room labeled with that number (maybe in very small font). Now, suppose that when you arrive, the hotel is full! Well, no problem! You can simply request that the hotel manager scoot everybody down one room, 1->2, 2->3, etc. Then, room #1 is available for you! This means that there are not more numbers in the list 1,2,3,4,… than in 2,3,4,5,… which is a little strange.

Since that worked out so well, the next time you visit the Hilbert Hotel, you bring a busload of friends. They are sitting in seats numbered 1,2,3,4,… and for every whole number there is an occupied seat with that number. The hotel manager objects, saying that he can’t possibly have all of the guests march down the hallway forever. Besides, they’d never make enough room for everybody that way! Luckily, being a mathematical enthusiast, you know there’s a simpler way. Simply have each guest double their room number and go to that room. Then, only the even-numbered rooms will be occupied, and you and your party can take the odd-numbered rooms! Hurray! Once again, it’s a bit strange that there are no more whole numbers than there are even numbers. This kind of thinking leads to one of my favorite examples of mathematical ingenuity. We appear to have reached a paradox when we say a subset of numbers has no fewer numbers in it despite leaving some out (like the first one or even all of the odd numbers). What do we do? Declare that this is the definition of an infinite set! Bam!

The next day, you find the hotel manager arguing with somebody who has just brought another infinite busload of visitors. The problem is that the seats in the bus are numbered by fractions! For every fraction a/b, there is an occupied seat. The hotel manager claims that there are simply not enough rooms in the hotel, and it is full besides. The visitor objects that infinity is infinity, so if they accommodated your party, then they must be able to do so for hers. So, we know how to make infinitely many rooms available, but what instructions will allow each fraction-numbered passenger to know what room to go to?

To start, let’s assume they’re positive fractions, a/b, with a,b>0. If we pick a numerator and go through all possible denominators, then we end up with infinitely many… but there are infinitely many numerators to pick from! Infinitely many infinities? Uh oh! We need to be a little more clever. If we restrict our attention to fractions with a+b=n for some n>0, then we only have finitely many. For example, if n=2, then we have just 1/1=1. If n=3, then we get 2/1=2 and 1/2. For n=4, there’s 1/3, 2/2=1, and 3/1=3. There’s just n-1 numbers to consider. Notice that some numbers repeat, like 1/1 and 2/2. To make really good instructions, you’d have to keep track of this if the seats are all in the form of reduced fractions. I’ll leave that as an exercise for you. Basically, for each n, we assign the n-1 passengers with a+b=n to the next available n-1 hotel rooms.

An almost identical system lets you deal with an infinite number of infinite busloads all at once! Check out the picture below from an old NYtimes column by Strogatz.

Now we reach a much deeper conundrum. Yes, it gets deeper than infinity infinities is still infinity. One dark and stormy night, a shuttle arrives where the seats are numbered by decimal numbers, a.k.a. real numbers, like etc. What clever way can we provide these people with hospitality? There is no way! Contemplate this:

No matter how you assign the passengers (imagine the list above as being who goes to room 1,2,3,…), I can always find at least one that is left out despite your claim that you have them all. So… some infinities are bigger than others! Well, no problem. Send the bus down the road to Cantor’s Paradise Resort with rooms labeled by colors. Exercise: Why did that last sentence sort of make sense?

Can you find sets that are bigger than the real numbers? For those of you who’ve held on this long, here’s a little tidbit to knock you off the rails. Is there a set with more elements than 1,2,3,… but less than the decimals? Why or why not? It turns out that the answer to this question is fundamentally undecidable. Math doesn’t always have the answers!

By the way, this wondrous madness came from the mind of Georg Cantor:

If you like this infinity stuff, I highly recommend the graphic novel Logicomix: An Epic Search for Truth.

Speaking of logic, Patrick Weed gave you an entertaining introduction to symbolic logic. Doing serious math or programming without knowing symbolic logic is like deciding to be a writer without knowing basic grammar. No, most writers don’t get excited about grammatical details, but they sure do know them well enough to make jokes about those who don’t.

Here’s a copy of the handout that he provided. Patrick Weed’s Math Circle on Logic

Also, there was some talk of how to map a line onto a plane. By onto, I mean so that every point in the plane is hit by a point from the line. This seems impossible, but if you ponder this illustration of a Hilbert curve, then it will still seem impossible. But it works! :-p

### Mathematical Biology

It sounds like everybody enjoyed our day of mathematical biology brought to you by Professor Mogilner and Swati Patel. Applications of mathematics to science are vast, deep, and ever-expanding. Many people are surprised to hear that mathematics can be so successfully applied to biology, probably since these topics haven’t made it very far into the high school curriculum.

Prof. Mogilner’s talk on allometric scaling was based on research published in the 1990s (West_Brown_Enquist_1997) that has been cited thousands of times. Since wikipedia is always a mere click away, you should try to read this. Here is an article that explains the paper a little more clearly than the original: Demystifying the West, Brown & Enquist model of the allometry of metabolism. And, here is an article talking a bit more about the biology of allometry using the example of fiddler crabs with one ginormous claw and one itty-bitty claw. I guess they look like they’re playing the fiddle? Cellist crab might be more apt.

Once you learn about fractals, it’s hard not to see them everywhere in nature.

Swati’s talk about modeling populations provided ideas that get your foot in the door to understanding chaos theory. And who wouldn’t want to know more about chaos??

The only limit to the applications of math is the imagination of the mathematician. We’ll have more professors and graduate students share some examples of applied math with you later this quarter.

### Math Skill Comes from Practice!

I recently read an interesting article supporting what many of us who work in math and mathematics education believe from experience: practice makes you better at math.

http://www.sciencedaily.com/releases/2013/12/131216102844.htm

However, this somehow manages to be simultaneously completely obvious and nearly impossible to convince people of. Better at algebra than geometry? Practice some more geometry. Trouble with word problems? Practice them as well as your reading in general. The analogy with athletics is completely apt.

As students, we tend to do more of what makes us feel good, which is of course what we are already good at. I have seen many students pride themselves so much on their ability at one thing that they neglect other studies and activities. This will of course lead to the student becoming better and better at that one activity and worse and worse at everything else. Many believe that students showing this one-dimensionality were somehow born different, but I’d venture to say that the vast, vast majority of such students have just engaged in overly narrow practice. Of course, there are a handful of people out there with such enormous capacity at such a young age that it doesn’t seem possible for there to have been sufficient hours in their life for their abilities to be due to practice alone, but I bet the differences between their inherent ability and that of others is much smaller than most people suppose.

What is the point of this rant? You can be good at math! Hurray! The difference between math people and non-math people is that math people do more math, not that they were born with some sort of abstract antenna in their brain that makes them sensitive to mathematical ideas or whatever.

Speaking of getting better at these things, see you at AMC practice on Saturday at 1pm! If you will be joining us for lunch, bringing a few bucks to cover cost of pizza would be much appreciated (but not required).

Email me if you’d like electronic copies of a few old AMC exams for practice.

### Math Circle Schedule for Winter 2014

This Saturday, George Mossessian will discuss the geometry and topology (he’ll tell you what that means) of 2D surfaces like beach balls, doughnuts, and Klein bottles. As always, only mathematical enthusiasm (not knowledge) is required, and this one should be quite hands-on and fun.

### Math Circle Redux and AMC 10

We had a great turnout on Saturday for both the Math Circle portion and the AMC time. In future AMC sessions, now that we have some measure of where you all are, we’ll focus on a particular topic and/or strategy. Remember that doing well on these problems means getting anything at all! We hope you enjoy learning outside of school in a zero-stress environment.

Email me to register for the AMC 10 or 12 which will be at 7pm in MSB 2112 (the usual place) on February 4th and 19th. If you’re not sure which, just tell me your grade and which date works better for you. You can take it on both dates if you like.

Jamie introduced some of you to the wonderful game of Set, and those who had already played learned about some of the mathematics hidden in the structure of the game. Anything so elegant must involve math!

Oops! Wrong Set. The talk was about this one:

Family fun! Not desert storms and chaos.

For a more mind-bending (but honestly less fun) experience, try ProSet, a version of Set created by thinking about the projective plane. Ever wonder what happens when you sew a Möbius strip to a disk?

A version of the projective plane, duh!

Eric gave an introduction to harmonic numbers and hinted at applications to prime numbers, leaning towers, randomized algorithms, and rovers. Expanded notes for Eric’s talk.

Next week, George will give a very accessible talk about surfaces and knots. He has experience teaching with Cosmos, so come and enjoy!

If you plan on staying for lunch between our two events, donating to help for the cost of food is much appreciated but not required. Any money made on this site goes to support Math Circle.

### Math Circle in Winter Quarter (Jan-March)

Hello Everybody!

I hope you enjoyed the winter break. We will be meeting again starting on Saturday Jan 11 at 10am-noon in our same location of MSB 2112. We will also do some practice focusing more on math competition skills after math circle for those who interested in competitions like the AMC 10/12, ARML, mathcounts, etc. We will meet every Saturday unless otherwise stated.

Speaking of mathcounts, UCD will be hosting for this region! Let us know if you are interested in participating.

And now for a few cool things I’ve read about recently:

### Prime Progress

Some of you may have heard of the recent discovery by Tom Zhang that proves the existence of a bound on the spacing of prime numbers. I highly recommend a short article in Wired that explains the unfolding story quite well. Mathematically, this relates to the Twin Prime Conjecture: There are infinitely many pairs of prime numbers whose difference is 2, like 29 and 31 or 18,409,199 and 18,409,201. So simple to state, yet so hard to prove! This ongoing research says that we now know that there are infinitely many primes with a difference less than 600 (down from 70,000,000 in the groundbreaking result of Zhang). Part of the drama of this research is that a young mathematician named James Maynard discovered the bound of 600 entirely independently of Zhang’s work at almost exactly the same time! Centuries of stalemate followed by simultaneous results! This brings to mind a famous quote of Farkas Bolyai about mathematical discovery from a letter to his son János,

“When the time is ripe for certain things, these things appear in different places in the manner of violets coming to light in early spring.”

János went on to become one of the founders of non-Euclidean geometry, which in turn led to the development of the theory of general relativity, a completely new way of thinking about space, time, and gravity. Also, isn’t it odd to think that emails with your parents might become part of the historical record and be quoted two hundred years from now?

After the initial publication by Zhang, a vast online collaboration known as Polymath8 got together to improve his result. Here we see two extremes in the way mathematical research is done. On the one hand, a lone individual quietly works in isolation for many years to develop a private insight with little connection to other people in his field. Often, this is the picture presented in the media of how mathematicians work. However, this is exceedingly rare! Mathematicians talk to one another and benefit from collaboration just like everybody else. This is exemplified by the Polymath8 group that brings together the expertise of a broad range of people from around the world to contribute to different pieces of the problem. Crowdsourcing! The more standard approach to good research can be seen in the success of Maynard who decided to be thorough by looking back at some neglected work by others and found a way to incrementally improve upon it in order to achieve a radical new discovery, a classic combination of “luck and pluck.”

All of these people are quite intelligent and creative, but mathematical discovery is not a magical “genius” activity. It’s hard yet rewarding work that you can do, too!

**Exercise:** Prove that there infinitely many prime numbers. [Suppose there is a biggest prime. Can you derive a contradiction?]

**Hard Exercise:** Prove that . [Hint: Start by thinking of for $k=1,2,3,4$ and see if you can get a lower bound with an easy formula.]

**Hard Challenge:** Prove that . [This is pretty tough. Let me know if you want to see a relatively approachable proof.]

**Easier than it looks:** Let S be all positive integers that don’t have the digit 7 anywhere (written in the usual base 10). Show that . [This time, you want to get an upper bound for which you can find a formula instead of a lower bound. ]

**Non-Euclidean Riddle:** A woman on a hike steps out of her tent, walks one mile south, then one mile east, and finally one mile north back to her tent. She finds a bear getting into her peanut butter! What color is the bear?