Mike Pawliuk – Mathematics – Page 10 – Assistant Professor, Teaching Stream, at the University of Toronto Mississauga

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

Every Day I’m Simulating

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

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”