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 \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 \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: \N \rightarrow \Q$. Let $W_x := \{n \in \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 \N : x \in \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: \Q \rightarrow \N$. For each $x \in \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 \R \}$ is the desired family. [QED]

There you go! Two facts that show how infinite combinatorics goes beyond just showing that $\vert \N \vert < \vert \R \vert$.