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

A Practical Guide to Using Countable Elementary Submodels

doll-house

So, you may have heard about these things called countable elementary submodels. You may have heard that they work like magic and do all sorts of amazing things. “Mathematical voodoo” some might say. “Witchcraft!” others declare. Hearing this you become intrigued and set out to harness this black power. You quickly realize that there are very few places to learn this dark art; the protectors of this knowledge don’t want it leaking out.

Here I hope to lay out the essential things you need to know (and omit the things you don’t need to know) so that you can start using countable elementary submodels. I am going to lay out as little of the machinery as possible and display only the relevant applicable facts you will need for most proofs involving elementary submodels.

1. A Countable Submodel of What?

The universe of all sets V is a ‘model’ for set theory, but it is too big. If we did have a model for set theory we would know that there is a countable submodel of it, by Lowenheim-Skolem. Of course we can’t assert that set theory has a model as this would be equivalent to asserting the consistency of set theory. The clever way around this is to realize that any proof in mathematics only ever uses finitely many axioms of set theory and references only finitely many specific sets. It is always possible to find a model H of those finitely many axioms and special sets. (Aside, for those of you who have seen this before, why doesn’t this violate the compactness theorem? It’s tricky.) Here H will be our copy of the universe, just for a given proof, and we will take a countable submodel of H , not V . This is where the language “Take a large enough fragment of ZFC” comes from.

As it turns out there is a class of sets that we usually draw H from. We usually take H to be a set H(\alpha) , where \alpha is a cardinal and H(\alpha) is the set of all sets hereditarily of cardinality less than \alpha . This doesn’t really matter at all. So don’t fret about this. Continue reading A Practical Guide to Using Countable Elementary Submodels

Secret Santa 3: The Paradox.

Last time I discussed the solution to Sam’s problem:

Sam’s Problem. Is it possible for two people to each choose a natural number so that both numbers are exactly 1 apart and neither person knows who has the larger of the two numbers?

I established, by induction, that it is impossible to do this. Great. We write “QED” and move on. There is a very convincing counter-argument that was brought to my attention by Jacob Tsimerman and a student at the Winter Canadian IMO camp. They proposed a method that seems like it should solve Sam’s problem in the positive. What exactly is going on in their method? Where is the mistake?

Jacob’s method. Player 1 chooses a large enough number N (say greater than 100); this is now their number. Player 1 writes down the numbers N+1 and N-1 on different pieces of paper and presents them face-down to Player 2. Player 2 chooses one of them and burns the other one without looking at it. The number Player 2 sees is their number.

Continue reading Secret Santa 3: The Paradox.

The Secret Santa Problem (Part 2)

Last time, just in time for Christmas, we looked at the Secret Santa Problem. Basically the problem is to set up a secret santa type gift exchange without using any external aids like random number generators. A similar problem given to me by Sam Coskey is the following:

Sam’s Problem. Is it possible for two people to each choose a natural number so that both numbers are exactly 1 apart and neither person knows who has the larger of the two numbers?

When Sam gave the problem to me he intended that each player would choose a natural number and then they would sequentially ask questions to each other, possibly refining their original numbers. In this sense it is more like a game of Guess Who than secret santa.

After much thinking, it turns out that there is a fairly easy solution to this problem.

Part 1. Can either player choose the number 0?

Well no, because that person would know that they have a smaller number than the other player.

Part 2. If both players know that 1, 2, \dots, k cannot be chosen then k+1 cannot be chosen (as k+1 would have to be the smaller of the two numbers). So by induction, no number can be chosen by either player.

The lesson here is that induction is a very useful technique! This sounds naive but, when problem solving for contests, induction is often overlooked. Here is another related problem:

Father/Son problem. Is it possible for two players to each choose a human being so that the two humans are father and son, but neither player knows who has the father and who has the son?

The solution is again fairly simple, and uses induction. This time we need a different type of induction. We observe that no player can pick the first ever human being (as they would have the father of the other player’s choice). Now if there is a set S of humans that cannot be chosen, then the sons of people in S cannot be chosen either.

There you go, induction wins again!

 

The Secret Santa Problem

Happy holidays everyone! As Christmas approaches so do the Christmas related problems. I’m not talking about the long lines at stores or the busy days filled with errands, I’m talking about Christmas math problems. Here is one I learned at my department holiday party from Eric Hart and Jeremy Voltz.

This whole post is going to be directed at a general audience.

Secret Santa Problem (simplified). An office needs to determine how to set up a secret santa gift exchange, but they have lost all of their dice and paper! How can each person in the office have exactly one person for whom they are buying a gift and also each person does not know who is buying them a gift?

Here we allow some of the employees to have private conversations if they wish.

Attempt 1: The obvious first thing to do (that doesn’t work) is to have one person tell everyone whose gift they are buying. You can tell right away why this won’t work: It is too much work for that one person the designator will have to designate someone to buy a gift for the designator!

Attempt 1.a: Have the boss tell everyone what they should do. Well… I don’t think the boss is going to like this idea. We should really try to find an internal solution. That is, let’s try to find a solution that does not use anything external (like random number generators, extra people, secret santa consultants, etc.)

Continue reading The Secret Santa Problem

Reading the Dictionary

I have a confession to make: I am a bibliophile. Reading, owning, perusing, lending, alphabetizing and buying books are all things that make me happy. High on my list are hardcover graphic novels and quality dictionaries. One of the skills you learn quickly while reading a dictionary (so I hear) is how to look up words. Of course the words in a dictionary are laid out in a very orderly fashion; first the ‘A’s then the ‘B’s, etc.. This order turns out to be a useful example of an interesting linear order.

Example: Consider \{a,b,c\}\times\{a,b\} with the dictionary ordering. We get aa < ab < ba < bb < ca < cb .

In general to get a dictionary ordering on A\times B out of two linear orders A,B we do the following:

  1. Compare first elements. If they are the different, use the ordering on A.
  2. If the first coordinates are different, compare the second coordinates. If the second coordinates are different, use the ordering on B . If the second coordinates are the same, the elements you are comparing are the same (as they have the same first and second coordinates).

You can extend this process if you want and compare third, fourth or fifth coordinates if you start with three, four or five linear orders. Of course this is just saying something you already know; I don’t need to tell you how to figure out whether ‘oscillate’ comes before ‘ossifrage‘.

Example: Now my fellow sesquipedalians might be interested in the following linear order: Let D = \{*, a,b,c, \ldots, z\} where * < a < b < \ldots < z and * stands for a blank space. Now consider D^{189819} with the dictionary ordering. This will contain every English word both technical and non-technical. Granted it will also contain silly non-words like: “this*word*asserts*that*it*is*a*silly*word”.

Continue reading Reading the Dictionary

Every Day I’m Simulating

You can simulate buying this shirt!

 

Have you ever tried to explain/inflict forcing on your non-set theory friends? Let me tell you it is hard. In my ongoing effort to try to explain everything to everyone here is my attempt at explaining the idea of forcing, without explaining forcing.

First, I direct you to this post which explains the simulation argument.

tl; dr – Imagine that our civilization could simulate (artificially) intelligent civilizations. They wouldn’t know that they are in a simulation and could also run their own simulations.

Reading this post reminded me about forcing. Here is my reply to the OP (who happens to be my brother-in-law), and I would appreciate feedback on this so that I can refine my analogy:

Cool. This illustrates a key observation that underlies a lot of the mathematics (set theory) that I do. It goes like this for the interested parties:

We run a simulation as you’ve described, but we make sure that the simulation only has “a small number of things in it”. Perhaps we have some sort of minimal simulation, like we don’t include the letter Z in their languages or something (Call this SIM1). Now we check that the simulation can come up with its own simulations. It can? Great! So now we know that “having the letter Z in your language” is not a requirement for coming up with simulations. Or we could add a whole bunch of new crazy letters (in say SIM2) and see if they can still run simulations. Lets say they can still come up with simulations. Continue reading Every Day I’m Simulating

Creeping Along

In my ongoing love affair with compactness I am constantly revisiting a particular proof of the Heine-Borel theorem, a characterization of compactness in \mathbb{R} . There are two proofs that I know of: the standard “subdivision” proof and the “creeping along” proof. I am going to focus on the creeping along proof.

Heine-Borel Theorem. A subset A \subseteq \mathbb{R} is compact if and only if it is closed and bounded.

To do some creeping we need to collect some useful facts.

Fact 1. A subset \mathcal{A} \subseteq \mathbb{R} is bounded if and only if is contained in some closed interval [a,b]

Fact 2. The set \mathbb{R} is complete (as a linear order) because every non-empty set A \subseteq \mathbb{R} with an upper bound has a least upper bound, called \sup A .

Fact 3. Closed subsets of compact subsets of \mathbb{R} are in fact themselves compact. With fact 1 this means that it is enough to show that closed and bounded intervals in \mathbb{R} are compact. (In general closed subsets of compact T_2 spaces are compact.)

So now let us creep:

Continue reading Creeping Along