Erdös numbers

By Micheal Pawliuk | Published: May 16, 2012

(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.

Read More »

Posted in Full Article, Presentation | Tagged , , | Leave a comment

Another Combinatorial Result

By Micheal Pawliuk | Published: April 4, 2012

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.

Posted in Full Article, Presentation | Tagged , , | Leave a comment

Facts about the Urysohn Space – Some useful, some cool

By Micheal Pawliuk | Published: March 6, 2012

(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 isomorphism 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.

Read More »

Posted in Full Article, Presentation | Tagged , , , , , , | 1 Comment

MA and its effect on Tree Partitions

By Micheal Pawliuk | Published: February 28, 2012

(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$.

Read More »

Posted in Full Article, Presentation | Tagged , , , | 3 Comments

The Delta-System Lemma

By Micheal Pawliuk | Published: February 12, 2012

This is a delta system of rivers. I didn't know this until last year.

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.

Read More »

Posted in Full Article, Uncategorized | Tagged , , , , | 3 Comments

A Practical Guide to Using Countable Elementary Submodels

By Micheal Pawliuk | Published: January 26, 2012

Elementary submodels are like dollhouses in your real 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. Read More »

Posted in FAQ, Full Article | Tagged , , , , | 6 Comments

Secret Santa 3: The Paradox.

By Micheal Pawliuk | Published: January 17, 2012

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.

Read More »

Posted in Full Article, Problem Solving | Tagged , , | 3 Comments

The Secret Santa Problem (Part 2)

By Micheal Pawliuk | Published: January 4, 2012

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!

 

Posted in Problem Solving, Uncategorized | Tagged , , | 1 Comment

The Secret Santa Problem

By Micheal Pawliuk | Published: December 20, 2011

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 the each person in the office have exactly one person for whom they are buying a gift and also do 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.)

Read More »

Posted in Full Article, Problem Solving | Tagged , | 3 Comments

Reading the Dictionary

By Micheal Pawliuk | Published: November 29, 2011

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”.

Read More »

Posted in Full Article | Tagged , , , , , | Leave a comment