Full Article – Page 3 – Mike Pawliuk

The Battery Problem – Math for my Mom

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

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)

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

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.