Hindman’s Theorem write-up

It came to my attention that Leo Goldmakher had written up notes for a lecture I gave in August 2011 on the proof of Hindman’s Theorem via ultrafilters. The notes are quite nice so I thought I would share them.

Here is a link to the notes (pdf) and here is Leo’s website.

The lecture I gave follows the papers:

  • “An Algebraic Proof of van der Waerden’s Theorem” by Vitaly Bergelson, Hillel Furstenburg, Neil Hindman and Yitzhak Katznelson. (L’enseignement Mathematique, t. 35, 1989, p. 209-215)
  • “Ultrafilters: Some Old and some New Results” (pdf) by W.W. Comfort. (Bulletin of the AMS, Volume 83, Number 4, July 1977)

The Battery Problem – Math for my Mom

(After writing some posts directed at other mathematicians, here is one for everybody.)

I’ve never actually done this.

I was sifting through some old issues of Crux Mathematicorum last Friday. For those of you who don’t know, this is a wonderful magazine that contains tons of math questions generally like those you would see in a math contest or olympiad, and the difficulty ranges from elementary school to undergraduate. In the September 2009 issue, I stumbled upon the following nice problem originally from the 2005 Brazilian Mathematical Olympiad. It is one of those problems that is mathematical in flavour and doesn’t need any previous math knowledge to begin thinking about the problem. For me, a nice problem is one that rewards you for thinking about it and can be attacked from many different angles.

So here’s the problem as stated:

We have four charged batteries, four uncharged batteries, and a flashlight which needs two charged batteries to work. We do not know which batteries are charged and which ones are uncharged. What is the least number of attempts that suffices to make sure the flashlight will work? (An attempt consists of putting two batteries in the flashlight and checking if the flashlight works or not.)

Continue reading The Battery Problem – Math for my Mom

A Taste of Infinite Combinatorics

When people ask me what I do I often give the ‘sexy answer’ that I study different sizes of infinity. This usually dazzles the listener and lets me talk about why I think math is beautiful as opposed to why it is useful “for getting chicks and dollar bills”.

Of course when a mathematician asks me what I do I need to give a more precise answer. (Also, I feel like, to many mathematicians, the study of cardinality seems like a parlor trick. “Been there, done that.”) So I’m going to give two (easy) facts that illustrate the types of results that go past the study of cardinality and peek into the world of infinite combinatorics.

The first observation is that people in set theory and set theoretic topology are obsessed with the real numbers (affectionately, “the reals”). Often discussions start with “This fact is true of the reals, but what about in other spaces?”. (For example, the reals have a countable dense subset – the rationals – and this is important enough that we gave it a name – separable.) Often in set theoretic topology we work under the heuristic that “everything is true in the reals”, and we look for which particular topological properties give us those facts.

So, it shouldn’t be surprising that we look for copies of the reals wherever we can.

Fact 1. There is a copy of the reals inside of the partial order (\mathcal{P}(\mathbb{N}), \subset^*)

Here A \subset^* B means A\setminus [0, n] \subset B for some n \in \mathbb{N} . This just means that A is almost contained in B . Another way to think of this partial order is that two sets are equivalent when they differ in only finitely many places. In plainspeak, besides finitely many exceptions, every element of A is also in B . (Also, \mathcal{P}(\mathbb{N}) is the family of all subsets of the natural numbers.)

proof of Fact 1. We need to construct a family of sets \{W_x : x \in \mathbb{R}\} such that when x < y we get W_x \subset^* W_y . Also, we should make sure that we didn’t construct something trivial. We should make sure that when x \neq y that W_x and W_y disagree on an infinite set.

Fix a bijection f: \mathbb{N} \rightarrow \mathbb{Q} . Let W_x := \{n \in \mathbb{N} : f(n) \leq x\} .

Sure enough, this has the above property that x < y implies W_x \subset W_y . The non triviality condition is given because whenever x < y there are infinitely many rationals between x and y . [QED]

There are other things to say about this partial order (along the lines of “It contains a copy of every countable partial order”), but I will leave those for another time.

The next thing is a standard fact that is often given as a challenge exercise for undergraduates.

Fact 2. There is a family \{W_x \subset \mathbb{N} : x \in \mathbb{R}\} such that if x \neq y then W_x \cap W_y is finite.

We will also have that each W_x is infinite. (Can you see what happens if we don’t insist on this?)

As a warm up, try finding an infinite (not necessarily uncountable) family with that property. (In this case you can do much better; you can make is so that the intersection of any two sets is empty.)

proof of Fact 2. Fix a bijection f: \mathbb{Q} \rightarrow \mathbb{N} . For each x \in \mathbb{R} , fix a sequence S_x of rationals that converges to x .

Note that if x \neq y then S_x \cap S_y is finite, because the two sequences are converging to two different reals.

So \{f[S_x] : x \in \mathbb{R} \} is the desired family. [QED]

There you go! Two facts that show how infinite combinatorics goes beyond just showing that \vert \mathbb{N} \vert < \vert \mathbb{R} \vert .

My Recent Talks on Itzkowitz’ Problem

On Friday May 18th, I gave the following presentation (here) at the Ottawa Mathematics Conference 2012. It was 25 minutes long and went over well.

On Friday May 25th, I gave an expanded talk (here) at the Toronto Set Theory and Topology Seminar. The talk lasted about 55 minutes and afterwards I had some interest from two of the participants.

Pictures to follow!

Erdös numbers

(This talk was given as part of the What We Talk About lecture series at No One Writes to the Colonel on May 17, 2012)

Paul Erdös

Math is many things: beautiful, fundamental, universal, but ultimately, math is hard. So hard in fact that mathematicians often need to phone up their other mathematician friends for help. The idea of the crazy-maned recluse furiously working in his office alone is an outdated one. While some modern mathematicians still fit this bill, collaboration is increasingly the norm. By the year 2000, the number of mathematics papers with a single author had shrunk to 50%. More and more people are tackling difficult math problems as a team.

No one embodies the idea of mathematical collaboration more than Paul Erdös (pronounced err-desh or air-dish), a Hungarian mathematician who lived in the twentieth century. A legendary figure in mathematics, Erdös published around 1500 papers and had around 500 co-authors. To contrast, most mathematicians write 7 papers in their entire life! Erdös was heavily in support of working together to solve math problems and questions, and also had incredible mathematical taste. He asked very interesting questions and would often attach a dollar amount to the questions. If you were clever enough to solve one of these Erdös questions, Paul Erdös himself would send you a cheque. These cheques were so revered in mathematics that often people frame them rather than cash them. More information on his very interesting life is available here.

Continue reading Erdös numbers

Another Combinatorial Result

Here is Chris Eagle’s presentation from Stevo Todorcevic’s class “Combinatorial Set Theory”.

From the abstract:

We prove that MA + \mathfrak{c} = \aleph_2 implies \mathfrak{c} \not\rightarrow (\mathfrak{c}, \omega+2)^2 . The exposition is based on hand-written notes provided by S. Todorcevic. The result itself is due to R. Laver.

This is the analogous result to “MA implies (NonSpecial Tree) \not\rightarrow (NonSpecial Tree, \omega+2)^2 “, which I explained here.

Facts about the Urysohn Space – Some useful, some cool

(This is almost verbatim the talk I gave recently (Feb 23, 2012) at the Toronto Student Set Theory and Topology Seminar. I will be giving this talk again on April 5, 2012)

I have been working on a problem involving the Urysohn space recently, and I figured that I should fill people in with the basic facts and techniques involved in this space. I will give some useful facts, a key technique and 3 cool facts. First, the definition!

Definition: A metric space U has the Urysohn property if

  • U is complete and separable
  • U contains every separable metric space as an isometric copy.
  • U is ultrahomogeneous in the sense that if A,B are finite, isometric subspaces of U then there is an automorphism of U that takes A to B .

You might already know a space that satisfies the first two properties – The Hilbert cube [0,1]^\omega or C[0,1] the continuous functions from [0,1] to [0,1] . However, these spaces are not ultrahomogeneous. Should a Urysohn space even exist? It does, but the construction isn’t particularly illuminating so I will skip it.

Continue reading Facts about the Urysohn Space – Some useful, some cool

MA and its effect on Tree Partitions

(This is the presentation I gave for Stevo Todorcevic’s course Combinatorial Set Theory on Feb 28, 2012. The material comes from Stevo’s 1983 paper “Partition Relations for Partially Ordered Sets”.)

In partition relations for ordinals, it has been established that:

Theorem (Erdos-Rado). \omega_1 \rightarrow (\omega_1, \omega+1)^2

Later it was shown that this is the best you can do, as the strengthenings are consistent:

Theorem(Hajnal). Under CH, \omega_1 \not\rightarrow (\omega_1, \omega+2)^2
Theorem (Todorcevic). Under PFA, for any countable ordinal \alpha , \omega_1 \rightarrow (\omega_1, \alpha)^2

Moving on, we can ask the same questions about non-special trees, which in some way are the tree analogue of “uncountable” or “large”.

Theorem (Todorcevic). Nonspecial Tree \rightarrow (Nonspecial Tree, \omega+1)^2

This is the analogue or the Erdos-Rado theorem.

Recall that a tree T is nonspecial if T \rightarrow (\omega)^1_\omega , which means that any countable partition T contains an infinite set. (This is a generalization of uncountable, because for countable sets you can always put one element per colour.)

We will show the following:

Theorem (Todorcevic). Under MA, for T a tree with no uncountable chains and \vert T \vert = 2^{\aleph_0} we have T \not\rightarrow (T, \omega+2)^2 .

Continue reading MA and its effect on Tree Partitions

The Delta-System Lemma

colorado_river_delta

Now that you know the basics of countable elementary submodels (CESM), you might think that you are in the clear. “Mike”, you say arrogantly, “I know all the most basic properties of CESMs, without proof I remind you, what else could I possibly want?”. I gently and patiently remind you that CESMs are worthless unless you know how to apply them properly.

So let’s do that.

Here are two theorems whose proofs you might already know, but that can be proved using elementary submodels. I will show you a proof of the \Delta -system lemma (a fundamental lemma in infinitary combinatorics) and a topological theorem of Arhangel’skii. Both of these proofs are taken from Just & Weese’s book “Discovering Modern Set Theory 2”, chapter 24.

Continue reading The Delta-System Lemma