Uncategorized – Page 2 – Mike Pawliuk

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

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!

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

Helly’s Theorem (2/2)

Last week we looked at the concepts of a collection of sets being n-linked or having the finite intersection property. The key theorem was Helly’s theorem which says:

Helly’s Theorem: If a (countable) family of closed convex sets (at least one of which is bounded) in the plane are 3-linked, then they have a point in common, as they have the FIP.

Now I will look at some of the generalizations that Alexander Soifer, author of “The Mathematical Coloring Book”, makes in Chapter 28 of that book. More than pure generalizations they are the combination of Ramsey theory and Helly’s Theorem

Continue reading Helly’s Theorem (2/2)

My first entry! “Helly’s Theorem”

I love compactness. I really do. It turns infinite things into (almost) finite things. I could gush about how great it is, but instead let me tell you about one problem where compact sets act as the delimiter.

Here is one way to characterize compactness:

A space X is compact if and only if any family of closed sets with the Finite Intersection Property (FIP) has a common point.

[Remember that a collection has the FIP if every finite subcollection has a common point (i.e. has non-empty intersection).]

This has a pretty clear connection to filters, as filters are collections of sets with the FIP (and the intersection is in the filter!) and closed under supersets. One example of a filter is the collection of all subsets of the real line that contain a closed interval around 0.

A closely related notion is that of being 2-linked. A collection A is 2-linked if any two sets in A have non-empty intersection. For example the collection of real intervals $\{(n,n+2): n \in \mathbb{Z}\}$ is 2-linked. Another example is the set of sides of a ~~polygon~~ triangle. (Why not a square?)

Then of course we can talk about being 3-linked which means that any 3 sets have non-empty intersection (we will now say that this is called ‘meeting’). Obviously, $\{(n,n+2): n \in \mathbb{Z}\}$ is 2-linked, but not 3-linked. (edit: Yeah, so not only is this not obvious, but it is not true! I address this here.)

Then we could go on to define n-linked for an arbitrary natural number n.

Question 1: How is the FIP related to being n-linked?
Question 2: Can you find, for each n, an example of a collection that is n-linked but not n+1 linked?
Question 3: How is n-linkedness related to the dimension of the real line?

I’ll get to these later. But you should think about them. 1 and 2 are not hard. 3 takes some thought, but just try to come up with a conjecture.

Continue reading My first entry! “Helly’s Theorem”