What did Banach's Wife think of the Banach-Tarski Paradox?

I recently read and reviewed The Pea and The Sun by Leonard Wapner, which is about the Banach-Tarski Paradox. Recall that the Banach-Tarski Paradox is actually a theorem (not a paradox) that says you can take apart a ball of volume 1 into a finite number of pieces (some of the pieces will be VERY funky) and reassemble to get a ball of volume 2. By repeating this process you can take a pea and get a ball the size of the sun. (My review is here).

When I told my wife this theorem (she has a Masters in Comp Sci and knows some math) she said Math is Broken!!!. She later wondered why mathematicians didn't just toss out The Axiom of Choice (for uncountable sets) since it leads to such an obviously false theorem.

By coincidence, Leonard Wapner had just emailed me to thank me for my review (and to agree that MacArthur Park is the worst song ever written, see this article on my website). SO I put the question to him- why didn't mathematicians just toss out AC since it leads to BT? What follows is an edited version of our back and fourth emails.

BILL: I told my wife the Banach-Tarski Paradox and she wonders why mathematicians didn't just IMMEDIATELY toss out the Axiom of choice for uncountable sets since BT is so obviously false.

LEONARD: I do not believe BT is obviously false. I believe it to be true, based on the axioms of set theory, including AC. Your wife is claiming there are no real world manifestations of the phenomenon. She is not alone with this feeling. Personally, I am highly skeptical of there being any real world models of the BT result. (Those given in the book were clearly labeled as speculations at best.

But, I also believe we can't rule out the possibility, based on mathematical and physical discoveries, to date. BT does not contradict any theorem or axiom. And, it's no more counterintuitive than some Baby BTs (mini version of BT that proceeded it that are also counter-intuitive) and some physical phenomena (relativity, quantum mechanics, etc.)

BILL: By the time BT was proven AC was embedded into the math culture. Many things had already been build on it. Is that why Math folks didn't just toss it out? Would anything important be lost if we tossed uncountable AC out?

LEONARD: I believe it wasn't tossed out because there was no mathematical justification (in the way of a mathematical contradiction) to do so. If AC were to produce a mathematical contradiction, then, being a questionable axiom, it might be tossed. But, there is no mathematical contradiction and I think most mathematicians accept AC. In any case, it would be even more counterintuitive for some to drop it than accept the BT result. AC allows for surprises, but no mathematical contradictions.

I suspect that there are useful theorems, relying on AC, which would be lost if AC were to be tossed. I can't give a specific example now, but I do know that there have been proofs relying on AC which have encouraged others to prove those same theorems without AC. BT, in its usual form, requires AC. Some variations of it do not.

BILL: BT is obv false in the real world. Is this enough of a reason to toss it out (my wife things so).

LEONARD: Coincidentally, my wife asks me the exact same question. And, this is precisely what intrigues me about BT and other paradoxes. As I write above, I prefer to say it is "apparently" false in the real world, rather than obviously false. I can't rule out that which I've not seen simply because I've not seen it.

Afterthoughs on Banach Tarski and the Miracle of loaves and Fishes

I posted about using the Banach-Tarski Paradox(BT)  to explain the miracle of Loaves and Fishes (LF) here.

Darling says that whenever I fool my readers or my students then I have to tell them later, so I'll tell you now: The story about me meeting with Pope and talking about the BT Paradox (that would be a good name for a rock band: B-T-Paradox) was not true. I think my readers know that.

 

1) I first learned the Banach-Tarski Paradox as a grad student in 1981 when I read Hillary Putnam's article Models and Reality where he writes on Page 470:

One cannot simply sit down in one's study and ``decide'' that ``V=L'' is to be true, or that the axiom of choice is to be true. Nor would it be appropriate for the mathematical community to call an international convention and legislate these matters. Yet , it seems to me that if we encountered an extra-terrestrial species of intelligent beings who had developed a high level of mathematics, and it turned out they rejected the axiom of choice (perhaps because of the Tarski-Banach Theorem), it would be wrong to regard them as simply making a mistake. To do that would, on view, amount to saying that acceptance of the axiom of choice is built into our notion of rationality itself; that does not seem to me to be the case.

I agree with him and I wonder if we accept AC too readily. See my blog post on the BT paradox and my wife's strong opinion (she's against it).    

2) Back in 1981 my first thought was I wonder if someone has thought to use the BT paradox to explain the LF? And if so, were they serious or was it some kind of  joke? And does the Pope really get a discount at Pope-Yes? 

I also had the meta-thought (which I could not have said as cleanly as I will now):

 I wonder how I could find out if anyone else has thought of the BT-LF connection? 

Recall that back in 1981 the Internet was but a glint in Al Gore's eyes.  So back then I could not find out if anyone else had that thought of BT-LF. 

But now I can! And indeed, as I expected, some other people have made the connection of BT to LF: 

A tweet and a Reddit thread discussing the tweet: here. Not serious 

A serious article, I think, here   

A 24-page article about Holy Water and BT.  I can't imagine an article that long being a parody so I think its serious, see here. On the other hand, there is a 12-page article about Ramsey Theory and History that I think is supposed to be a parody, see here. (My proofreader points out that a different definition of parody is A feeble or ridiculous imitation so the article may well be a parody in that sense.

A parody article, I think, here

I am sure there are more. 

3) I had thought of doing a blog post about BT and LF  a long time ago,  but Pope Leo having a math degree was the final push I needed.

4) The word cardinal has three very different meanings: (a) a type of infinity, (b) a position in the Catholic church, (c) the bird.  Same for large cardinal.

5) One of my students who proofread the post thought that people will know it's a hoax since I am a vegetarian and hence would not eat at Pope-Yes, even if the Pope was paying. 

 

Solutions to some Hat Problem AND some points of interest.

In my last blog here I asked three (known) hat problems since they may be new to you (one of them I just learned last week) and I had a point to make about them. I have WRITTEN UP the proofs  here since html is clumsy with math (or I'm clumsy with html-math), so this post is mostly about the points to make about these problems. I would urge you to read the writeup pointed to before reading the post.

1) N people 1,...,N, two colors R,B, Hats put on RANDOMLY (no adversary).

People are in a line and pe sees person j's hat iff i ≤ j .

There is a well known strategy where nobody passes which guarantees n-1 get it right (see here), but that strategy has EVERYONE get it right 1/2 of the time. We want MORE than that. LOTS more.

The following strategy works: For i=1,2,..., N person i does the following: if nobody has said RED yet AND ALL of the hats i sees are BLUE then i says RED. Otherwise Red passes

This fails on B^n. It works on everything else with the last R getting it right and everyone else passing. So the prob of getting it right is 1- 1/2^n.

POINT: I originally didn't have one to make, but a commenter misread the problem (or I miswrote it) in an interesting way. My problem was: Hats put on randomly, players are deterministic. They thought it was Hats put on by an adversary but players can use a randomized strategy. That problem (which frankly is more intersting) has a similar solution to the above: the players get a random string of R,B of length n and treat that like I treat B^n above.

2) omega people: 1,2,3,... and as above. We want to get all but a finite number of people get it right. See my writeup of it pointed to above. The proof I use uses the Axiom of choice and this is needed (see here).

POINT: some of my students didn't like that the players need uncountable memory. How much does this bother me: not even a little. A fellow blogger thought this result was so non-intuitive that he now thinks the axiom of choice is wrong (see here) Personally I am a lot more bothered by the Banach Tarski Paradox (see here), though that paradox has lead to what my wife calls either the best or the most obscure math joke ever: what is an anagram of Banach-Tarski? Answer: Banach-Tarski Banach-Tarski.

3) omega people: 1,2,3,... and as above but now we want to get at most ONE wrong. You CAN do this! see the writeup.

POINT: When I first learned problem (2) I assumed you could not get it down to a finite bound. And I was sure I could prove it, though I never got around to it, prob because I thought it was true and easy. Well, my turn to eat humble pie (an expression only said on TV and not in real live)--- you CAN do this with only one error.  The problem where you have an infinite number of people, they all see each others hats, and they all shout at the same time- that one I am sure you can't do with at most 1 error. I might need to eat humble pie once again.

4) n people, c colors, everyrone sees everyone else's hat, simul shouting, deterministic, and want to maximize how many get it right. OH- and adversarial.

Can do it with floor(n/c) but can't to better. See writeup.

POINT: The argument that you can't do better is a probabilistic argument! That's great! It may help bridge the gap between recreational and serious math (is there even a gap anymore?) that we use a Prob method on a fun hat problem! 

What are Galois Games?

How are math concepts named?

1. After the people who was involved with it. Examples: The Cook-Levin Theorem, Goldbach Conjecture, Ehrenfeucht-Fraisse games,
   Banach-Tarski Paradox.
   
2. A descriptive name:
   Examples: Chromatic Number; Girth of a graph (length of shortest cycle). This resembles the definition of Girth in English though I have only heard the word used in mathematics;
   Duplicator-Spoiler games.
   
3. A name that conjures up a nice image. Examples: Dining Philosophers problem;
   The Monty Hall Paradox (though future historians will think he was a great Probabilist).
   
4. Name may have very little connection to the concept. Example: The Pell equation.
   

I saw an article whose title was Greedy Galois Games. I wondered what this game could be.

1. Do the players alternate picking polynomials and if the composition is solvable by radicals then (say) Player I wins.
   
2. Did Galois invent some game?
   

The first game I thought of might be interesting; however, the paper was not about that. Nor was it about some game Galois invented. So---what is a Galois game? Aside from being a mathematician what else is known about Galois:

He died in a duel!

In the article Greedy Galois Games they study a DUEL between two BAD DUELISTS. The idea is that if both have prob of hitting p (and p is small) and they want to make it fair, first Alice shoots, then Bob shoots the min number of times so that the prob of Bob winning exceeds Alice's, then Alice shoots a number of times so that her prob of winning exceeds Bob's, etc. The paper ends up involving the Thue-Morse sequence. They are NOT using the name Galois the way we use Banach in Banach-Tarski Paradox, nor the way we use Monty Hall in The Monty-Hall Paradox. The fact that Galois was a mathematician has nothing to do with the naming,  The authors are using  Galois because he is a  famous duel-loser. They could have used Alexander Hamilton (who lost a Duel to Aaron Burr) and then called them Greedy Hamiltonian Games, in which case I would assume that the game involved
Hamiltonian cycles or Quaternions.

RaTLoCC (Ramsey Theory in...)

I was at RatLoCC last week which stands for Ramsey Theory in Logic, Combinatorics and Complexity. The idea was to bring in researchers for all three areas (actually its more than three) and have them learn about each others areas.

1. During Szemeredi's talk he said I am not an expert on Ramsey Theory. He meant to say I am not an expert on Ramsey Numbers, e.g., the current upper and lower bounds on R(5).
2. An anagram of Banach-Tarski is Banach-Tarski Banach-Tarski.
3. Bertinoro hosted both RaTLoCC and SUBLINEAR (a workshop on ... SUBLINEAR things) at the same time. We had some shared activities with them. They were a younger, hipper crowd. Ronitt Rubinfeld (who was there) told me they had LESS women than they thought they would have- only 4. We had MORE women then we thought we would have- 2 (we had 0 last time).
4. There were several blogs about the SUBLINEAR workshop: Day 1a Day 1b Day 2a Day 2b Day 3 Day 4a Day 4b
5. One measure of how much you get out of a workshop or conference is how many papers you are inspired to read when you get back home (or perhaps how many pages-of-papers or theorems, or some measure.) With that in mind, here is a list of some of the papers that inspired me. (Slides and abstracts are posted at the workshop's website.)
   1. Szemeredi talked on Arithmetic progressions in sumsets. Here is a sample theorem. Throughout A is a subset of {1,...,n} and n is large. A+A is the set of all sums of two elements of A. LA is A+A+...+A (L times). Sample theorem: For all C there exists c such that if |LA| > Cn then LA has a cn-AP (an arithmetic progression of length cn.) These theorems look HARD but it inspires me to read some papers on Alon's website on this topic, and also my own writeup of sum-product theorems (He used C and c in his talk- though some of them looked the same.)
   2. Noga Alon talked on List Coloring and Euclidean Ramsey Theory. A graph is L-List colorable if there is a way to assign each vertex L colors so that there IS a coloring of the graph where each vertex uses on of the colors assigned to it. Let G be the unit distance graph in the plane: vertices are points in the plane and two points are connected if they are distance one apart. This graph is known to be 7 colorable, known to NOT be 3-colorable. All else is open. Noga talked about his proof (co-author Kostochka) that G is NOT list-s-colorable for any s. The paper is on his website and I am INSPIRED to read it. (ADDED LATER- THE DEFINITION I GAVE ABOVE IS NOT CORRECT. SEE COMMENT BELOW.)
   3. Peter Cholak talked on Reverse Mathematics of Ramsey Theory. Reverse mathematics is a field where they have set up several axiom systems for mathematics (in a hierarchy) and, for MANY theorems of math, they know EXACTLY which system is needed. Infinite Ramsey Theory for PAIRS seems to be stubborn- it is not in any of the usual systems. (formally: RCA cannot prove it, but ACA is too much). It is provably DIFFERENT from Infinite Ramsey for TRIPLETS (which is equivalent to the theorem for 4-tuples, 5-tuples, etc, and for all of them ACA is exact.) My question: when I prove Ramsey for triples I do not feel the earth move or think MY GOODNESS- THAT STEP WAS NONCONSTRUCTIVE!!!! or anything else that is different from Ramsey for pairs. They told me that there IS a proof of Ramsey for pairs that, once you see it, you DO NOT know how to generalize to triples. I may try to look into this. I may not. The paper is at Peter Cholak's webpage and is titled On the strength of Ramsey's theorem for pairs. (co-authored by Jockusch and Slaman)
   4. David Conlon's talk Hypergraph Ramsey Numbers was about Ramsey's theorem for triples. For this case the upper bound is double-exp but the lower bound is single-exp. They made some progress on this, but the upper and lower bounds are still, pretty much, what they were. Still- proofs look very interesting. Progress here is unpredictable--- Conlon said that the problem could be solved next week or next month or not for one hundred years. Also, the proofs are clever- so Erdos COULD HAVE done them. (As opposed to results that use mathematics unknown to anyone in Math at the time.) I am INSPIRED to read this paper by Conlon, Fox, and Sudakov. The case of 3-hypergraph is interesting because, if the lower bound can be gotten up to double exp then for k-hypergraphs we will know that upper and lower bounds are roughly tower(k-1). (Uses the STEPPING UP Lemma.)
   5. Swastik Kopparty talked on The complexity of computing roots and residuosity in finite fields. Say you are in a ints mod p and you want to know whether x is a cube root or not by a constant depth circuit. This will take exp number of gates. Framework is the same as the Parity not in ACC_0 proof, but requires lots more math. MIGHT want to read it. MIGHT be too hard.
   6. Imre Leader gave an excellent talk on Euclidean Ramsey Theory. Here is the basic problem: Let S be a set of points in Rⁿ. IS it the case that, for all c there exists a finite set T in R^m. (m \ge n) such that, no matter how you c-color T there will be a CONGRUENT copy of S? The unit line has this property. If so then S is RAMSEY. It is known that if S is Ramsey then S lies on the surface of some (many dim) sphere. The Main conjecture is that the converse is true. NO says Imre! He has an alternative conjecture here. This paper I am INSPIRED to read.
   7. Jan-Christoph Schlage-Puchta (that is one person) gave an application of VDW's theorem to Completely Multiplicative Automatic Functions This one I NEED to read to put in my book on VDW's theorem. Its here
6. The best talks were those that really TOLD YOU WHAT THE PROBLEM WAS so that the no-specialist could at least here that and then TOLD YOU WHY THEY CARE (even if you don't care you should know why they care) and TOLD YOU SOMETHING ABOUT THE TECHNIQUES. Not all of the talks did this. Also, the best talks were on BLACKBOARD- it forces you to go slower. Not possible at STOC/FOCS etc since the audience is too big, but quite possible here. Only drawback- can't put blackboard talks on the web so easily (though you can if you videotape).
7. The youngest participant: James Pinkerton, my High School Student, gave his talk on Duplicator Spoiler Games that go on an ordinal number of moves. The talk was AWESOME! Before hand he was not scared. He said Whats the worst they can do? Throw red and blue tomatoes at me?
8. One of the people there wore a T-shirt that said Stand back, I'm doing SCIENCE! that had a picture (stick figure really) of a scientists with a test tube. He wore it two days in a row. I commented: Nonconstructive proof that you are a supernerd. Either (1) You wore the same T-shirt two days in a row, so you are a supernerd, OR (2) you have two copies of the same nerdy T-shirt, so you are a supernerd. Of course, in these surroundings, being called a nerd or a supernerd is not an insult.

Math on FUTURAMA and LAW AND ORDER:CI

MATH ON TV

FUTURAMA mentions the Banach-Tarski Paradox! In the June 23, 2011 episode Professor Farnsworth invents a Banach-Tarski-Dupla-Shrinker which takes a blueprint of an object (like a sweater or Bender) and some matter and then produces two smaller but otherwise identical copies of the original. The real Banach Tarski Paradox takes one object and produces two of the exact same type. The writers might have felt that was just a little too weird. See here for a full description of the episode. The episode aired on thursday, and today, Tuesday, a full description is on Wikipedia. This surprised me (so fast!) but did not surprise my great nieces and nephews.

LAW AND ORDER: CRIMINAL INTENT had its last episode Sunday June 26, 2011, thus ending a rather long running show which was part of a rather long running (and still running) franchise. Here is the whole list: Law and Order (1990-2010, 456 episodes), Law and Order: Criminal Intent (2001-2011, 195 episodes), Law and Order: LA (2010-2011, 22 episodes), Law and Order: SVU (1999-2011, 272 episodes, and still going), Law and Order: Trial by Jury (2005-2006, 13 episodes), Law and Order: UK (2009-2011, 26 episodes, and still going). 456 episodes is HUGE! Check out this list of long running TV shows. The list is only updated once a year This surprised my great nieces and nephews (so slow!) but did not surprise me.

I recall three episode of Law and Order:Criminal Intent that mentioned math. I am sure there are more.

In the episode Bright Boy there was a school for gifted children in math that tried to get 10 year olds to work on the Riemann Hypothesis. It was not clear if they wanted them to solve it as children (which seems absurd) or as adults later in life (not absurd but a real long shot). The reason I find it absurd that a 10 year old could solve RH is that cleverness and brilliance is not enough- you have to actually have learned a great deal of math, perhaps too much for a 10 years old to have learned. Problems that need lots of KNOWLEDGE really can't be solved by bright 10 years olds or amateurs, no matter how brilliant they are. (See here for a post of Lipton's about of when amateurs helped solve math problems.) Getting kids interested in math by having them work on RH is the opposite of using Math competitions. Lance and I discussed math competitions as a way to interest kids in math here. Which is better? Even if you get bright pre-high school students working on problems, having them work on RH would just lead to frustration. Are there math programs that have student work on real open problems? How about phony open problems (the mentor knows the answer ahead of time). Some REU's do this for College students, but is there anything like this for High School Students?

The episode Inert Dwarf involved a brilliant physicist who, for medical reasons, was in a wheelchair (modeled vaguely after Stephen Hawking). One point of interest: he had a password that was based on hard physics and hence uncrackable. Gee, I thought that you just need to make sure your password is (1) not a word in any language (2) long enough, and (3) used Upper Case (easy for ME), lower case, numbers, and punctuation symbols. Unless it was some sort of quantum system (the episode did not indicate this) I can't see how hard physics can make a password uncrackable.

In some episode this season (I forget which one) Goren (the detective) was given the following riddle by his psychologist: There are two doors and two guards. One of the doors leads to heave, the other to hell. One of the guards always tells the truth and one always lies. You get to ask one guard one question and then you must pick a door. Goren is supposed to some sort of genius who also knows a great deal of stuff so I'm surprised he didn't know it. In the last episode of the entire series, To the boy in the blue knit cap, he answers it correctly. I think that was supposed to be symbolic or meaningful or something, but I didn't see why. (Bad writing? I'm being dense?) (ADDED LATER- ACTUALLY GOREN ASKED THE PSYCHOLOGIST THE QUESTION WHICH MAKES MORE SENSE IN TERMS OF WHO-KNOWS-WHAT.)

Bright Boy and Inert Dwarf had the same problem that many TV shows have: If the real world fact do not make the plot work, the writers change the real world facts. Numb3rs did this with Math quite a lot.

If I was a tweeter (is that a word?)

Since Lance is not tweeting this week, I will take up the slack. So, here is my once-in-a-while post

If I tweeted AND if tweets didn't have to be so short, here is what I would tweet:

1. Possibly the youngest blogger: a 7-year old has a blog called Life Before The Dinosaurs. It's about... life before the dinosaurs. It's serious. It's not a stunt. His mom types it in for him.
2. More money in SOLVING problems then showing they are UNSOLVABLE:
   1. Decision Problem: Solvable cases of the Quantificational Formulas costs $80.00 used, on amazon.
   2. Decision Problem: Unsolvable cases of the Quantificational Formulas costs $9.00 used, on amazon.
3. Math on TV: On NCIS, the episode Red Cell McGee and Abby argue over whether the math they are looking at is homology or cohomology. I couldn't tell who was right.
4. Other blog (not this one of course) have a problem with nasty comments. Why? See here for a possibly explanation.
5. The new Minister at my church has a math degree. I'll ask him if Jesus used the Banach-Tarski Paradox to perform the the miracle of the five loaves and two fish.
6. A use of Banach-Tarski in Norse mythology: here.
7. A play with some math themes called Completeness. Sounds interesting but I'm not going to pay $70.00 to find out.
8. There were identical twins in my Discrete Math class. GREAT for You have n people. Two are identical twins that you cannot tell apart. How many different ways can they appear to line up? TERRIBLE for If I was to ask everyone in this room their birthday what is the probability that two of them have the same one?

Mathematics is not commutative

In my poll of P vs NP and other issues, one of the questions was


                             Is factoring in P?

One of the most interesting answers was


                             I don't really see why it shouldn't be. - Peter Shor

Recall that Peter Shor proved Factoring is in Quantum-P which lead to intense interest in Quantum Computing.

1) What if factoring was in P and this was shown before Shor's algorithm? Would Shor or someone else have ever proven factoring in quantum P? Would there be as much intense interest in quantum computing as there is now? Perhaps by physicists more than CS people?

2) What if factoring was in P and this was shown before RSA? Where would crypto be now? Zip drives with a googleplex random (or nearly random) bits and more 1-time pads? More lattice based crypto? Or RSA but with larger numbers? This may depend on how good the factoring algorithm is.

3) More generally, how much does the order of events matter for science?

a) If the Banach-Tarski paradox was discovered early on, would we have just tossed out the Axiom of Choice before so much more was build on it? Darling thinks we should toss out AC NOW because of Banach-Tarski.

b) In the model of set theory L you can do ALL of math except some parts of set theory and maybe a few other things (note quite: Harvey Friedman has found some combinatorial statements that need large cardinals to prove). Had L been discovered earlier then could we all now be working in L (except a few people who look at other models, but they are not in the mainstream)? We might know more about L and less about forcing. We would KNOW that AC and CH are true. Or we would think we know.

c) If  Engineers were the first ones to look at SAT and reductions, might they have been content to know that  if SAT \le A then A is probably hard? No need for the Cook-Levin Theorem! And then when someone proved Cook-Levin would the Engineers not really cares since they already knew SAT was hard?

d) I can imagine Ramsey's Theorem being discovered much later for some application, or perhaps never being discovered at all.

e) VDW's theorem has so few application, I can imagine it never being discovered. 

4) There are cases where if A was discovered before B then B has an easy proof, whereas if B was discovered before A, then B has a hard proof. I'll give one example:

Given HALT is undecidable, Godel's theorem is easy.

Assume HALT is undecidable. 

Let STAT(e) be the statement M_e(0) does not  halt.

There is some e such that M_e(0) does not halt  but ZFC cannot prove this.

PROOF: Assume, By Way of Contradiction that for all e such that M_e(0) does not halt,

ZFC could prove this. Then HALT is DECIDABLE:

Given e, run M_e(0) and at the same time enumerate all proofs in ZFC. It is guaranteed that

you will either find M_e(0) halts or a proof that M_e(0) does not halt. Hence you will,

in finite time, know if M_e(0) halts OR NOT.

END OF PROOF

Is the sequence of events where HALT is proven undecidable  before Godel's theorem plausible.

I  think so

I INVITE my readers to give there own examples of when Math is not commutative- meaning that

the order of events matters.

Whats your Game Mr. Bond- The sequel!

(I will post about CCC 2010 later in the week.)

The word Game is used in many different contexts within math and computer science. I list out all that a group of us at last years Dagstuhl thought of:

1. Duplicator-Spoiler Games are used in Descriptive Complexity theory and Logic. They are also called Ehrenfeucht-Fraisse games. (The pointer, a Wikipedia entry, has a pointer to EXCELLENT slides on these games.) Example result: wellfoundness for linear orders is not first order definable.
2. Every A &sub {0,1}^&omega gives rise to the following game: Alice picks c₁ &isin {0,1} Bob picks c₂ &isin {0,1} Alice picks c₃ &isin {0,1} Bob picks c₄ &isin {0,1} etc. If c₁c₂c₃ ... is in A then Alice wins. If not then Bob wins. The Axiom of Determinacy states that, for every A, one of the two players has a winning strategy. This has been proven for Borel sets A. Full AD contradicts Full AC. See here. I have posted on it before here.
3. Banach Games. Let A be a subset of R. All numbers picked are in R. Alice picks x₁. Bob picks x₂ < x₁. Alice picks x₃ < x₂. Bob picks x₄ < x₃. etc. If &sum x_i &isin A then Alice wins, otherwise Bob Wins. For more on these see here.
4. Banach Mazur Games. (I am not quite sure of this one since I could not find stuff on the web and it looks too much like the games for AD. If this is incorrect please comment.) Similar to the games under AD; however, instead of picking an element of {0,1} the players pick an element of {0,1}₊. This has been used to define when a set is meager and has been extended to poly-time settings. Also has been extended to graphs: see here
5. Martingales. Let A &sub {0,1}^&omega. x is in A, but the player does not know what it is. The player starts out with one dollar (wow!). When the player sees the first n bits of x he bids on the (n+1)st bit. Can he win? Depends on A. Has been used to define measure 0 and has been adapted to the poly time setting. Jack Lutz has worked a lot on this stuff.
6. Complexity Classes have been defined via games. Usually a prover wins if he can convince a verifier that x &isin A. Many parameters can be changed to get many classes (number of rounds, number of provers, strength of verifier, strength of prover(s), prob of error allowed). I would include the Unique Game Conjecture in this use of the word game.
7. Pebble Games have been used to get time-space trade offs on simple models of computation. More recently they have been used to get lower bounds on resolution theorem provers. For a survey see the first paper on this page. Warning- the survey is 200 pages!
8. Games have been used to prove theories decidable. Originally S2S (Second order theory with two successors, essentially the theory of infinite strings of 0's and 1's) was proven decidable by Michael Rabin. Later Gurevich and Harrington had a simpler proof using games. See this paper. Another excellent article on this, which alas is not on line, is Infinite Games played on Finite Graphs by Robert McNaughton, Annals of Pure and Applied logic, Volume 65, Issue 2, Pages 149-184.
9. Combinatorial Games like NIM have been well studied.
10. Game Theory needs no commentary here.
11. Richman Games are a way to combine Combinatorial Games with Game Theory. See this paper.
12. In adversary arguments in lower bounds we picture an adversary who is playing a game with the algorithm or with any possible algorithms.
13. Communication Complexity Games. Not sure these are really games, but the term is used.
14. Surreal numbers are actually games. See Conways book On Numbers and Games.
15. A lot of computer science and graphics go into video games.
16. There has been some study of strategies on real games like monopoly and chess. I gave one classification of games in this post. Note that GO and Chess are EXPTIME complete.

Note that most of these games are not fun.

Disproving the Myth that many early logicians were a few axioms short of a complete set

While I was working on this post another blogger posted on the same topic here and I found a book review of Logicomix that touched on some of the same issues here. (For MY review of Logicomix see here.) They are very good sources and I will refer to them in this post.

There is a notion that logicians who work in foundations early on in the field were crazy. I give examples of where this is said and then I look at the real evidence.

1. In Rudy Rucker's post about Turing he writes

   ... it really does seem possible that Turing killed himself. Like the other logicians Godel and Cantor, he seems to have been somewhat nuts. Funny how many logicians are crazy and irrational. A paradox.

2. In Logicomix, a great comic book about the foundations of logic, there is an allusion to Logicians being crazy.
3. In Gian-Carlo Rota Indiscrete Thoughts he writes: it cannot be a complete coincidence that several outstanding logicians of the 20th century found shelter in asylums at some point in their lives: Cantor, Zermelo, Godel, and Post are some.

I've also seen an explanation for this alleged phenomena: Logicians were searching for absolute certainly and either it can drive you crazy or thinking you can find absolute certainly means you were crazy ahead of time.

So the people above, and others, give some examples of logicians being crazy and then claim that many logicians are crazy. I am reminded of people who say It was cold the other day, looks like Global warming is wrong.

Let us look at the actual record. I will look at all of the logicians in Wikipedia's list of logicians who

1. were born between 1845 and 1912. (1845 is when Cantor was born, 1912 is when Turing was born.)
2. I ruled out a few people who were really philosophers, and also Banach who I don't think would call himself a logician.

For each logician on the list who meets my criteria I say if I think they are sane or a few axioms short of a complete set. I am not a historian--- corrections are more than welcome. I also freely admit that crazy is not well defined.

You may well disagree with what years I pick and my opinions. The point is to get an intelligent discussion going.

1. Wilhelm Ackerman (1896-1962): He defined the function that bares his name. He also worked on the epsilon-calculus which formed the basis for Bourbaki's logic. Reading Bourbaki might drive one crazy; however, forming the basis for it does not. He was quite sane (Ackerman that is-- Bourbaki had multiple personality disorder.)
2. Alice Ambrose (1906-2001): She had the longest lifespan of anyone on this list. She studied with Moore and Wittgenstein and got two PhD's. (In those days a women had to do twice as much as a man to get a job.) She was more on the philosophy side of logic, but certainly had math training. She wrote a textbook with her husband, known as Ambrose and Lazerowitz. Sane!
3. Paul Bernays (1888-1977): He worked with Hilbert on alternative set theories. Sane!
4. Evert Willem Beth (1908-1964): He helped to establish Logic as a discipline. Sane!
5. L.E.J. Brouwer (1881-1966): He thought that all math should be constructive. This point of view lost the battle if ideas; however, that does not make him crazy. The Wikipedia article quotes Martin Davis as saying: he felt more and more isolated, and spend his last years under the spell of totally unfounded financial worries and a paranoid fear of bankruptcy, persecution, and illness. However, Dirk van Dal en wrote a scholarly two-volume biography of Brouwer that indicates that Brouwer was not crazy. And I agree. Sane!
6. Georg Cantor (1845-1918): He had a new way of looking at infinity that was brilliant and is now accepted. That does not make him crazy. He was also convinced that Bacon wrote the plays of Shakespeare and that Joseph of Arimathea was the father of Jesus Christ. That does not make him crazy. However, he was obsessed with these views and was in and out of sanitariums. A few axioms short of a complete set.
7. Rudolph Carnap (1891-1970): I originally thought he was more of a philosopher; however, he published in thermodynamics and the foundations of probability. He fled Hitler's regime and later refused to sign a loyalty oath in America (during the McCarthy Era). His second wife committed suicide. He led an interesting life but was sane.
8. Alonzo Church (1903-1995): He invented (discovered?) The Lambda Calculus, proved that Peano Arithmetic was undecidable, and articulated what is now called the Church-Turing Thesis. These are all sane things to do. (Bob Soare distinguishes Church's Thesis from Turing's Thesis here.)
9. Haskell Curry (1900-1982): He worked in combinatory logic. There is a programming logic named after his first name! (see here). Sane!
10. Adolf Fraenkel (1891-1965): The F in ZF-set-theory. Provably Sane!
11. Gottlob Frege (1848-1925) He hated Jews, Catholics, and the French. That might make him unpleasant to hang around, especially if you are a French Jew who converts to Catholicism. However, that does not make him crazy. He is often given as an example of someone who was crazy, though the links ( here and here) argues for Frege being sane. I defer to the two links. Sane!
12. Gerhard Gentzen (1909-1945): He made the cut- Sane!
13. Kurt Godel (1906-1978): He stopped eating because he thought people were trying to poison his food. They weren't. A few axioms short of a complete set.
14. Jean Van Heijenoort (1912-1986): Best known in Logic for writing From Frege to Godel, a history of Logic from ... Frege to Godel (duh). Best known outside of logic for being Trotsky's secretary and later a historian of that movement. He was killed by his estranged fourth spouse. An interesting life, an interesting death, but he was sane.
15. Jacques Herbrand (1908-1931) Has the shortest lifespan (died at 23 in a mountaineering accident) of anyone on this list. He worked in proof theory. Sane!
16. Arend Heyting (1898-1980) He continued Brouwer's work on intuitionism. Sane!
17. David Hilbert (1862-1943): In Logiccomix they claim that Hilbert's son Franz had a mental illness and Hilbert cut off all contact with him. However, this refutes this and claims that Hilbert's son was only put away for 3 years and then re-joined his family. One may question if David Hilbert deserves a World's Greatest Father mug, but one cannot question his sanity.
18. Clarence Irving (1883-1964): He took exception to Principia's use of material implication. I'm impressed that he read and understood Principia enough to have objections. Sane!
19. Stanislaw Jaskowski (1906-1965): He worked in Intuitionistic Logics. Since I can't prove that he was crazy I assume he was sane.
20. William Ernest Johnson (1858-1931): He wrote three volumes on logic which showed technical expertise but was superseded by Principia Mathematica. This did NOT drive him crazy. Sane!
21. Philip Jourdain (1879-1919): He was interested in paradoxes and formed the card version of the liar's paradox. He also worked on algebraic logic. Quite sane. His sister Eleanor Jourdain claimed to have traveled through time and seen ghosts, but was not a logician.
22. Stephen Kleene (1909-1994): Kleene hierarchy, Kleene star, Kleene algebras are all named after him. He also proved the recursion theorem. Did this go to his head and make him insane? NO- he was totally sane.
23. Christine Ladd-Franklin (1847-1930): Her PhD was on Algebra and Logic. She faced problems being a women in a man's field but kept her sanity.
24. Stanislaw Lesniewski (1886-1939): He rejected axiomatic set theory (because of Russell's paradox) and tried to obtain other formal systems to replace it. A noble effort that failed. Still, he kept his sanity.
25. Adolf Lindenbaum (1904-1941): He proved Lindenbaum's Lemma- every consistent theory of predicate logic can be extended to a complete consistent theory. Like many major advances, profound at the time, easy to prove now. Certainly sane.
26. Leopold Lowenheim (1878-1957): The Lowenheim of Lowenheim-Skolem. See Skolem for more on that. A model of sanity.
27. Jan Lukasiewicz (1978-1956) Wikipedia says He thought innovatively about traditional propositional logic. Is innovatively a word? My spell checker does not think so but whoever wrote his Wikipedia entry thinks so. Sane.
28. Saunders Mac Lane (1909-2005) (He preferred the space between Mac and Lane.) His PhD thesis was on Logic and he also worked in Category theory. But he also did lots of Algebra. Sane.
29. Carew Arthur Meredith (1904-1976): He worked on obtaining short axiom basis for logic systems. Sane.
30. John von Neumann (1903-1957): Calling him a logician seems odd since he contributed to so many fields. Sane.
31. Jean Nicod (1893-1924): Co-discovered the Sheffer Stroke from which you can do everything in prop logic. Sane.
32. Pyotr Novikov (1901-1975): He proved the word problem for groups undecidable. His son Sergei Novikov won a Fields Medal in 1970 and, more importantly, is a professor at The University of Maryland! Sane.
33. Giuseppe Peano (1858-1932): His Wikipedia entry calls him the founder of Mathematical Logic and Set Theory. That seems over-the-top, but not by much. His axiom system is still the standard. Sane.
34. Emil Post (1897-1954) He introduced Turing Degrees. In the mid 1940's he posed Post's Problem which is to find a r.e. set (now called c.e.) that is neither decidable nor complete. This was solved in 1956 by Friedberg and Munhnik independently. He suffered from mental illness. A few axioms short of a complete set.
35. Mojzesz Presburger (1904-1943): Presburger proved Presburger Arithmetic was decidable. What are the odds of that!? Sane!
36. William Quine (1908-2000): He was more of a philosopher; however he did do some math. At Harvard he taught Symbolic Logic every fall for 50 years. That might drive some crazy; however, he was quite sane.
37. Frank Ramsey (1903-1930): The paper where he proved what is now known as Ramsey Theory was titled A Problem in Formal Logic and solved a case of the Decision Problem. He regarded himself as a logician so we shall too. Speculation: He would be surprised at where his work lead to (combinatorics) and then pleased that it lead back to logic again : The Large Ramsey Theorem (see also here) and much work in the reverse mathematics of Ramsey's theorem".
38. Raphael Robinson (1911-1995): He worked in Logic and Number Theory. He is probably best known for his work on tiling the plane. He married Julia Bowman (who changed her name to Julia Robinson) who was also a logician but born in 1919--- a little too late to be on this list. Having two academics in the same area get married might drive some crazy, but not them. Sane!
39. J. Barkley Rosser (1907-1989): He strengthened Godel's incompleteness theorem. Sane!
40. Bertrand Russell (1872-1970): He was obsessed with the quest for certainty; however, that does not make him crazy. He had several wives (not at the same time) and believed in open marriage. He was not crazy, just ahead of his time. Sane.
41. Moses Schonfinkel (1889-1942): He worked in Combinatory Logic. By 1927 he was in a sanitarium. The only non-famous logician on my list who was a few axioms short of a complete set.
42. Thoralf Skolem (1887-1963): He is best known for the Lowenheim-Skolem theorem: The notion that any consistent set of axioms has a countable model is very interesting--- One corollary: there is a countable model of the reals. Thinking about that might drive some crazy, but not him. Sane!
43. Alfred Tarski (1901-1983): The Banach-Tarski paradox is crazy; however, Tarski was not. Sane.
44. Alan Turing (1912-1954): He defined Turing Machines, though he didn't call them that. The story I had assumed was true is that the British Government made him take hormones (or something) to cure him of his homosexuality, and this drove him to suicide. But the story doesn't quite work with the timeline. He committed suicide a few years after he was forced to take drugs. Delayed reaction? Suicide for some other reason? Really was an accident? In any case, since his possible suicide is the only evidence that he was crazy I say Sane!
45. Nicolai Vasilev (1880-1940): The originator of non-Aristotelian logics. Sane.
46. Alfred North Whitehead (1861-1947): In Russell-Whitehead's Principia Mathematica they spend 300 pages proving that 1+1=2. This might drive some insane but not him. Whitehead was stark raving sane.
47. Ludwig Wittgenstein (1889-1951): He gave away all his money and seemed to be a self-hating Jew. Odd yes, but he was sane. (NOTE- Scott Aaronson left a comment that argues that Wittgenstein should be classified as a few axioms short of a complete set. I believe his arguments (they are backed up by facts) and may later redo the stats at the end of this post.)
48. Ernest Zermelo (1871-1953): The Z in ZF set theory. He disapproved of Hitler's Regime. Hardly crazy. Rota says that Zermelo was crazy but neither I nor this post have been able to find any evidence of this. Zermelo did spend time in a hospital for lung problems, which may have confused Rota.

So what to make of all of this?

1. Cantor, Godel, Post and Schonfinkel were crazy. So we have 4 out of 48 were crazy. That's around 8%. This website claims that 6% of all people are crazy. So 8 seems high, but the sample space is pretty small. Conclusion: Same as the posts on the same topic referenced at the beginning: the notion that people in logic are crazy is not well founded. In addition, this post argues that the problems Cantor, Godel, and Post had were unrelated to their study of logic. (There was no comment on Schonfinkel.)
2. AH- but Rota said that so many outstanding logicians were crazy. Since three of the four who I say were crazy were outstanding there may be a point here. One could look at who on my list was outstanding and see what percent of them logicians were crazy. However, determining who was outstanding is even harder than determining who was crazy, so I leave it to others to continue this work.
3. There were some on the list that in my opinion were sane but others think were crazy: Brouwer, Frege, Turing, Zermelo. Perhaps more. If enough of them turn out to be crazy then there may be something to this logicians are crazy theme; however, I doubt this will happen.
4. Was it crazy to spend so much time and effort on this one post? I am not on the logic list, nor was I born between 1845 and 1912 so the answer is not relevant to the study.
5. This blog posting has a crazy number of links: 71. That breaks the record for this blog which was held by this entry which had around 37.

Lincoln's Dog-Tail question (in honor of Presidents Day)

(Posted in Honor of Presidents Day.)

The following is NOT a trick question; however, I have heard two different answers for it.

How many legs would a dog have if we called the dog's tail a leg?

1. The answer is clearly 5- since 4+1=5. Duh.
2. Calling the tail a leg does not make it a leg. A dog has 4 legs. Duh.
3. I have seen people on either side not be able to even understand the other side's point.
4. This question has been attributed to Abraham Lincoln; however, just as Bogart never said Play it again Sam and Kirk never said Beam me up Scotty, Lincoln (likely) never said calling a tail a leg does not make it a leg (though he might have said Play it again Sam or Beam me up Scotty). See this interesting and serious post for information on what Lincoln said.
5. In our terminology Lincoln's point was that definitions should conform to reality and if they do not then it is the definitions that are wrong. I suspect he would not have liked the Banach-Tarski Pardox.

How would you answer the question? Do you understand the opposing viewpoint?

Global Warming and the Axiom of Choice

Who was the first scientist to warn of Global Warning? These questions are complicated, but I would say it was Bing Crosby in a paper called White Christmas. Here are the first two lines:

I'm dreaming of a white christmas
Just like the ones I used to know

Why are there no more white christmas's? Because global warming made it stop snowing!

Why do otherwise intelligent people refuse to believe that Global Warming is real and is caused by humans and we we need to do something about it? I have a conjecture and an analog. Here is what I think the reasoning is

1. Republicans have the following AXIOM (until they are in office): government IS the problem, not the solution. More than this, they think that there is NO problem that requires government action.
   
2. Consequence: Government should do NOTHING about Global Warming.
   
3. Since Government shouldn't do anything about Global Warming, it is not a problem.
   

Rather than rethink their AXIOM they accept the conclusion that Global Warming is either not a problem or not caused by humans. The shame of it is that there ARE economically viable ways, perhaps moderate republican ways, to fight global warming- some version of Cap-and-trade, or pay-to-pollute. And getting off of Fossil Fuels would be good for other reasons. I can picture history going a different way so that Republicans want more fuel-eff cars to get us off of Mideast Oil. I can picture a history where the insurance companies are more powerful than the oil companies for lobbying and hence Government takes LOTS of action against global warming.

Are their things in math where people accept an axiom despite its absurd consequences?Yes:

1. Most math people believe the Axiom of Choice.
   
2. Consequence: the Banach-Tarski Paradox
   

Rather than rethink their AXIOM they accept the absurd conclusion that you can break a ball into 5 pieces, reassemble, and get twice the volume. Fortunately, believing this does not endanger the planet.

Revisiting the Continuum Hypothesis

I have been thinking about CH lately for two reasons

1) I reread the article

Hilbert's First Problem: The Continuum Hypothesis by Donald Martin from Proceedings of Symposia  in Pure Mathematics: Mathematical developments arising from Hilbert Problems. 1976. (For a book review of the symposia and, The Honor Class, also about Hilbert's problems, see here.)

The article takes the point of view that CH CAN have an answer. He discusses large cardinals (why assuming they exist is plausible, but alas, that assumption does not seem to resolve CH) and Projective Det.  (why assuming it is true is plausible, but alas, that assumption does not seem to resolve CH).

(A set A \subseteq {0,1}^omega is DETERMINED if either Alice or Bob has a winning strategy in the following non-fun game: they alternate picking bits a_1, b_1, a_2, b_2, ... with Alice going first. If a_1 b_1 a_2 b_2... IS IN A then Alice wins, IF NOT then Bob wins. Martin showed that all Borel sets are determined. Proj Det is the statement that all projections of Borel sets are determined. AD is the axiom that ALL sets A are determined. It contradicts AC.)

But what really inspired this post is the last paragraph:

Throughout the latter part of my discussion, I have been assuming a naive and uncritical attitude towards CH. While this is in fact my attitude, I by no means wish to dismiss the opposite viewpoint.  Those that argue that the concept of set is not sufficiently clear to fix the truth-value of CH have a position that is at present difficult to assail. As long as no new axiom is found which decides CH, their case will continue to grow stronger, and our assertions that the meaning of CH is clear will sound more and more empty.

2) Scott Aaronson mentioned in a blog post (see here) that  he has read and understood the proof that CH is independent of set theory.

SO, this seemed like a good time to revisit thoughts on CH.

 I took a very short poll, just two people, about CH: Stephen Fenner (in a perfect world he would be a set theorists) and Scott Aaronson (having JUST read the proof that CH is ind.  he has thought about it recently).

Here are some thoughts of theirs and mine

1) All three of us are Platonists with regard to the Naturals (I was surprised to find recently that there are people who are not!) but not with regard to the reals.  So we would be OKAY with having CH have no answer.

2) All three of us  agree that it would be nice if SOME axiom was both

a) Intuitively appealing or aesthetically appealing ,  and

b) resolved CH.

I always thought that (a) would be the hard part-- or at least getting everyone (not sure who we are talking about) to AGREE on a new axiom. But even getting an axiom to resolve CH seems hard.  Large cardinals don't seem to do it, and various forms of Determinacy don't seem to do it.

Scott reminded me of Freiling's Axiom of Symmetry (see here) which IS intuitive and DOES resolve CH (its false) though there are problems with it--- a minor variant   of it contradicts AC (I am QUITE FINE with that since AC implies Banach-Tarski which Darling says shows `Math is broken'.)

Stephen recalled some of Hugh Woodin's opinions of CH, but Hugh seems to have changed his mind from NOT(CH): 2^{aleph_0} = aleph_2, to CH:  2^{aleph_0} = aleph_1.(See here.)

3) All three of would be okay with V=L, though note that this would put many set theorists out of work. All the math that applies to the real world would still be intact.  I wonder if in an alternative history the reaction to Russell's paradox would be a formulation of set theory where V=L. We would KNOW that CH is true, KNOW that AC is true. We would know a lot about L but less about forcing.

4) Which Geometry is true: Euclidian, Riemannian, others? This is now regarded as a silly question: Right Tool, Right Job! If you build a bridge use Euclid. If you are doing astronomy use Riemann. Might Set Theory go the same way? It would be AWESOME if Scott Aaronson found some quantum thing where assuming 2^{aleph_0} = aleph_2 was the right way to model it.

5) If I was more plugged into the set theory community I might do a poll of set theorists, about CH. Actually, someone sort-of already has. Penelope Maddy has two excellent and readable articles where she studies what set theorists believe and why.

Believing The Axioms I: here

Believing The Axioms II: here

Those articles were written in 1988. I wonder if they need an update.

A Game Theory Conference! That sounds like fun!

Bill: Lance just came back from Games, a conference on Game Theory.

Darling: That sound like fun! From what you tell me there is some nice math behind
Monopoly(see here for a paper on Monopoly as a Markov Process), Risk (see here for a paper on using Markov chains in the game Risk. Was Markov a game player?) and other FUN games.

Bill: Uh, I don't think they talked much about those kinds of games.

Darling: Darn. Did they talk about those really boring math games like Dup-Spoiler games, those games that AD is about, Gale-Stewart Games, Banach-Mazur games, Martingales, Pebble games, Communication complexity games. Oh, and Combinatorial games like NIM which can be sort of fun.Or did they talk about computers that play Chess and similar games? Or did they have talks on things like Chess being EXPTIME complete. Or did they talk about the Unique Game Conjecture.

Bill: Most of the talks were about setting up a system so that all players acting in their own best interest is also good for the system. Like an auction system where it is a players best interest to bid what they actually think the item is worth.

Darling: So there are no Games at a Game Theory conference?

Bill: There were a few papers on Poker, but that's it.

Darling: They should change the name of the field.

Bill:  Lance tells me that Ehud Kalai has suggested  Game Science. 

Darling: So long as the word Game is in the title they should have fun games there. Oh well.

Theorems that you simply don't believe

There are some theorems that are surprising. I've already blogged on that (I can't seem to find the link). However, there are some theorems that some people simply do not believe. I mean people who understand the proofs and still don't believe them. Let me give you a contrast- I DO believe that NSPACE(n) is closed under complementation because, while surprising, the proof really does tell you why its true. For the following surprising results the proof does not help. Or at least does not help the people who were surprised by it.

1. Barrington's theorem. I've read it, talked to Barrington about it, and even taught it. I still don't believe that (say) the set of strings that have the number of 1's equivalent to 0 mod 101 can be done by a width 5 branching program.
2. Banach Tarski Paradox A CS grad students who knows some math says that it shows that mathematics is broken. I would prefer to say it casts doubt on the axiom of choice.
3. The classification of finite simple groups. Does any one person even know the proof? Couldn't they have missed some group? Counter argument: the list is on Wikipedia so it has to be correct.
4. The rationals and naturals are the same size. I know someone who knows the proof and is happy to say they are the same cardinality but refuses to say they are the same size. (I think they are wrong and this is important- using the term size DOES matter.)
5. A well known theorist told me that he used to believe both P ≠ BPP and there were problems in DTIME(2^O(n)) that require circuits of size 2^&Omega(n);. Oh well.
6. Lance Fortnow tells me he has a hard time believing the Recursion Theorem. Perhaps because the proof is completely uninformative. (Ted Slaman, a well known recursion theorists, agrees that the proof is uninformative. Bob Soare thinks the proof is quite intuitive- a failed diag argument.)
7. Probability has a few of these: The Central Limit Theorem says that stuff is all normal. That can't be true! I've done the calculations for Birthday Paradox but it still seems suspect to me. And don't get me started on The Monty Hall Paradox.
8. Local Lovasz Lemma has gone from being something I didn't believe to something I now understand and believe. The original proof just looked like symbols being pushed around, but Moser's and later Moser-Tardos's constructive versions makes sense to me.
9. We all know that Godel's theorem surprised people- but were there people who did not believe it? This theorem does not surprise Generation Xers who are not at all surprised to find out certain problems cannot be solved. Their response: Whatever.
10. The existence of Geometries that are as valid as Euclidean but not Euclidean. Again, this surprised people, but were there those who did not believe it? In this age of moral relativism people have no problem with different geometries that are all valid.

How about you? Are there any theorems that you simply don't believe?

Two Candidates for an Ig Noble in Mathematics

(This is a sequel to my post on the Ig Nobel Prize.)

Two candidates for an Ig Nobel prizes in Mathematics. They deserve it for opposite reasons. (They are old results and hence, I assume, do not qualify.) (ADDED LATER- I checked with the Ig Nobel Committee- they DO allow old results to be submitted and have even given the prize out to people who are dead.)

1. The Banach Tarski paradox deserves an Ig Nobel since it is obviously false.
2. The Jordan Curve Theorem deserves and Ig Nobel since it is obviously true.

I helped the Pope's with his latest Encyclical (His Math Background Helped)

I blogged about Pope Leo XIV here. Pope Leo XIV has an undergraduate degree in mathematics. He saw my post and asked for my help with his latest encyclical. 

LEO: Let's have lunch together at Popeyes.

BILL: Why Popeyes?

LEO: The name is Pope-yes so I get a discount.

BILL: Your treat. [We met at Pope-yes and had the following discussion.]

LEO: I am working on an encyclical to resolve the tension between miracles in the Bible and modern science. 

BILL: What's the issue?

LEO: The Bible has miracles in it that seem to violate the laws of science. There are a few ways to resolve this cosmic conflict.

a) The miracles are allegorical. This is insulting to both God and Man. 

b) The miracles can be explained by natural phenomena. For example:

The Red Sea was split by  a big wind. This is acceptable. The timing of the big wind is the miracle.

BILL: Let me guess the problem: There are some miracles that cannot fit into modern science.

LEO: Exactly!  And I hope that Christians who are scientists (not to be confused with Christian Science, see here) will take up the study of miracles and see how they can fit into modern science.

BILL: Give me an example of a miracle that cannot be resolved with modern science and we'll see what we can do about that.

LEO:  Recall the miracle of loaves and fishes:

---------------------------------------------

A crowd of 4000 came to hear Jesus preach. When he was done they were hungry. 

Jesus told his disciples: 

I have compassion for these people; they have already been with me three days and have nothing to eat.  I do not want to send them away hungry, or they may collapse on the way. What food do we have?

The disciples responded:

Seven loaves and a few small fish.

Jesus told the crowd to sit down on the ground. Then he took the seven loaves and the fish and when he had given thanks, he broke them and gave them to the disciples, and they in turn gave to the people. They all ate and were satisfied. There were even leftovers. 

--------------------------------------------

So how could Jesus take seven loaves of bread and a few fish and feed thousands of people? How can this be explained with modern science?

BILL: I have a way to resolve it but you may not like it.

LEO: Let's hear it.

BILL: Jesus used the Banach-Tarski paradox  (see here) --- when he broke the bread,  he divided one loaf into 5 pieces, some of which were not measurable, and put them back together to get two loaves. Repeat until you can feed 5000 people. Same with the fishes.

LEO: Great! Why wouldn't I like that?

BILL: It only works if you're pro-(axiom of) choice. 

LEO: I'll have to run this by a subset of my advisors.

BILL: Which subset?

LEO: The Large Cardinals

Axioms: What should we believe?

Some misc thoughts on set theory inspired by yesterdays comments and other things.

1. Geometry: Use Euclidean Geometry when appropriate, for example if you are designing a bridge, use Riemannian geometry when looking at space time, and use geometries when they are appropriate. So there is no correct geometry, its more of a right tool for the right job thing. So far Set Theory does not seem to have a strong enough connection to the real world for this to make sense. I supposed you use ZFC when dealing with most of mathematics, but I doubt you would ever say something like: When dealing with Quantum Mechanics its best to assume AD. So what can you use to decide what axioms to use? You may decide what axioms to use based on your tastes. For example see this prior blog posting. This is good for an individual but will not really work for the whole community. For example, I happen to like AD since I like a world where the Banach Tarski paradox is false. But that's just me.
2. People concerned with these issues in the early 1900's were much more passionate then we are today. They had strong opinions on foundations and on non-constructive proofs. Mathematicians commonly carried firearms. We are far less passionate today on these issues. As an example, there are today people who study constructive proofs and prefer them, but I doubt anyone today would reject a theorem that was proven nonconstructively. Why the change of heart? Possibly Godel's theorem, but also the fact that people in different parts of math can't talk to each other so they can't argue.
3. Another axiom of interest: The existence of Inaccessible cardinals. MOTIVATION: Take omega. If |X| < omega then |powerset(X)| < omega. Does any other cardinal have this property? Why should omega be so unique? Kappa is an inaccessible cardinal is such that if |X| < Kappa then |powerset(X)| < Kappa. Do such cardinals exist? The existence of an inaccessible cardinal large than omega cannot be proven in ZFC. An inaccessible cardinal would be a model of ZFC and hence would prove that ZFC is consistent (omega does not prove ZFC consistent since no proper subset of omega is infinite). It is known that ZFC cannot prove its own consistency (I think that's true of any theory but there may be some conditions.)
4. Penelope Maddy has two nice articles on why mathematicians believe what they do: believing the axioms I believing the axioms II Also good to read: Shelah's Logical Dreams

Super Asymmetry on The Big Bang Theory: How Realistic?

The TV show The Big Bang Theory portrays academia so I am naturally curious how realistic it is. I have posted about this before (see here) in the context of whether actual things they say about physics are true. Today I post about a recent arc where Amy and Sheldon are working on Super asymmetry.


SPOILER ALERT

1) The name: Super Asymmetry. Its not a field but it could be. I assume its about particle physics but I'm not sure they ever say this. A fine name!

2) Amy is a neurobiologist (this was flagged as not being word, but I think it  is) working with Sheldon on a physical theory that I would assume requires hard math.  Physics is hard! So I wonder how realistic this is. Actually, more important than being hard is that you need a lot of background knowledge. So the questions of interest is: Can an amateur still help in a discovery of a new physical theory? This may depend on the definitions of amateur, discovery, new, and physical.  Alone I would doubt it. But with help from Sheldon, I can believe it. Still, making new discoveries in an old field is hard.

3) Amy and Sheldon first had the idea for super asymmetry on their honeymoon. Most married couples have other things to do on their honeymoon. (I did ask my darling to prove the primes were infinite on our wedding day before I married her. She was nervous so couldn't do it, but normally she could. I know a mathematician who made her spouse memorize the definition of a Banach Space before they got married, and recite it to her on their wedding day before they got married.)

4) After they do most of the work they THEN go track down references. This seems stupid but not unrealistic. You can get excited about a theory and work on it at breakneck speed and not want to slow down to check references. But see next point.

5) Sheldon was counting on this for a Nobel Prize. I would think you would check refs before even thinking in those terms.

6) An article in Russian was found that proved the theory could not work. There are a few things wrong with this:

a) The article used the exact same phrase ``Super Asymmetry'' - that seems unlikely.

b) They seemed to not READ the article, just the first page, and then say. DARN, all that work down the tubes.

c) They seemed to not even try to say `OKAY, they did BLAH, we did BLAH BLAH, how do they compare and contrast' (ADDED LATER- I just saw the episode afterwards. They probably DO have something after all. They should have listened to my advice before going into a funk.)

d) If they did all of that work I am sure SOMETHING can be recovered from it.

7) This is not really a post about The Big Bang Theory. I want to know more about your experiences with research: have you worked on a problem and found out it didn't work or was already done, or something like that. And what happened?

Why did 1+1=2 take Russell and Whitehead 300 pages?

In my post about the myth that Logicians are crazy I mentioned in passing that Whitehead and Russell spend 300 pages proving 1+1=2 (but were both sane). Two people privately emailed me:

Are you sure Russell and Whitehead weren't a few axioms short of a complete set? How could they take 300 pages to prove 1+1=2. Isn't it... to obvious to be worth proving?

I responded by saying that they had to define 1, +, =, and 2 rigorously. One of them responded Are you a few limit points short of Banach space? That aside, there are some questions the 1+1=2 proof brings up:

1. How did they spend 300 pages proving 1+1=2?
2. Is it easier in ZFC?
3. How important is or was Principia Mathematica? Wikipedia says PM is widely considered by specialists in the subject to be one of the most important and seminal works in mathematical logic and philosophy since Aristotle's Organon. The Modern Library places it 23rd in a list of the top 100 English-Language nonfiction books of the twentieth century. Here is the list they are referring to. The other books look... readable.
4. I had thought that nobody reads PM anymore; however, its entry on amazon says it has a rank of roughly 294,000. This is far better than a book that truly nobody reads. For example this book has an Amazon rank roughly 5,300,000.
5. While more people are buying it than I thought, are people actually reading it? Did they ever? My guess is no and no, but I really don't know.
6. Can a book be influential if few people read it? Yes if they are the right people. Godel read it and I think it inspired him. (Its mentioned in the title of his Incompleteness paper.)
7. PM was an early attempt to formalize all of math from the ground up. This may be one of those tasks that you are almost destined to do in a clunky way before doing it smoothly.
8. I am talking in a vacuum here, having never read it. If any of my readers have actually read it and want to comment on what it was really like, you are more than invited to do so.