Counting Things

We can construct a bijection by following our noses. Let's start with an $a$ in $X$ and iteratively consider $a,f\left(a\right),g\left(f\right(a\left)\right),f\left(g\right(f\left(a\right)\left)\right),\dots$. This chain either consists of infinitely many unique elements or eventually repeats from $a$. If it ever repeats, say $g\left(f\right(a\left)\right)=g\left(f\right(g\left(f\right(g\left(f\right(a\left)\right)\left)\right)\left)\right)$ then by the injectivity of $f$ and $g$ we can strip off the outer $g$'s and $f$'s to get $a=g\left(f\right(g\left(f\right(a\left)\right)\left)\right)$.

Suppose the forward chain never terminates. Then let us go backwards. It could be that some element of $Y$ maps to $a$ and then some element of $X$ maps to that element and so on. Because of the injectivity of $f$ and $g$ those elements are unique if they exist. We're not guaranteed to be able to go backwards and at some step of the process we may fail, at either $X$ or $Y$. Or the process could go on indefinitely. So we have four cases for our chains,

• A loop, $$a\to f\left(a\right)\to g\left(f\right(a\left)\right)\to \cdots \to a.$$
• A bidirectional infinite chain, $$\cdots \to g^{-1}\left(a\right)\to a\to f\left(a\right)\to g\left(f\right(a\left)\right)\to \dots .$$
• An $X$ terminated chain, $$f^{-1}\left(g^{-1}\right(a\left)\right)\to g^{-1}\left(a\right)\to a\to f\left(a\right)\to \dots .$$
• A $Y$ terminated chain, $$g^{-1}\left(a\right)\to a\to f\left(a\right)\to g\left(f\right(a\left)\right)\to \dots .$$

These four cases partition all the elements of $X$ and $Y$ into chains. Each element of $X$ and $Y$ falls into exactly one unique chain. So we have simply to describe a mapping on elements of $X$ for those that fall into each of these chains in such a way that it's clear we get all the elements of $Y$.

• For loops just keep our original mapping $f$.
• Same for our bidirectional infinite chains. Just map with $f$.
• Same thing if we have a one sided infinite chain ending in $X$.
• One sided infinite chains ending in $Y$ are the only case where we need to do something different. Simply push everything backwards. The inverse $g^{-1}$ is defined for the elements of $X$ in these chains.

One should check that every element of $Y$ is indeed mapped to by some $X$ and we have our bijection!

The Löwenheim-Skolem Theorem

This section will be a little more hand wavy than the earlier sections. To really be precise here one would have to develop model theory and the theory of first order logic, which is a little beyond the scope of my casual blog. But I think the theorem is interesting enough and relevant enough to the understanding of infinite sets that I would like to say something.

Basically we have models and we have theories. Models are the mathematical object itself. Suppose I tell you I have the natural numbers. You ask what that means. And I explain, "well there's 0, 1, 2 ...". Theories are a set of sentences describing the mathematical object. I tell you I have the natural numbers. You ask what that means. And I explain, "Well there's a first element. And for each element there's a successor. And the successor of an element is never 0. And every nonzero element is the successor of some element".

Basically there are two ways of thinking of mathematical objects. One can think of them as existing as some set somewhere. Or one can just have a system of statements about the object and try to deduce things from there. For example one can reason about Groups as a collection of symmetries or as an object satisfying some axioms. Both perspectives are valuable.

Let's look more carefully at the sentences I used to describe the natural numbers. Notice this set of sentences don't uniquely describe a mathematical object. For example the disjoint union of the natural and the integers satisfy all those sentences. So you might complain that I missed an important sentence, "every element can be reached by taking the iterated successor of zero". But that sentence can not be written down in first order logic. It is the conjunction of infinitely many clauses: All naturals are either 0 or the successor of 0 or the successor of the successor of 0 or ...

In first order logic all our sentences are finite and built up from or, and, not, for all and there exists. So any first order theory of the naturals which only knows about $0$ and succession (as opposed to also knowing about addition, and multiplication etc.) will not be able to distinguish the naturals as we think of them from these other mathematical objects.

It turns out this example isn't an exceptional case due to our under specified theory but the general phenomena.

Theorem (Löwenheim-Skolem) A first-order theory which has an infinite model has an infinite model of every infinite cardinal.

In our example of the naturals we could take any number of copies of the integers. We need the condition that there are some infinite models because for example our theory could have a sentence which says "every element equals 0" in which case there would only be finite models.

This theorem seems to say something paradoxical about sets. We observed earlier that there are infinite sets which are not bijective. But sets are usually understood to be axiomatized by the Zermelo-Fraenkel with Choice (ZFC) axioms [2]. The important thing is that ZFC is a countable first order theory. So if there is a model of ZFC [3] then there there must be infinite models of every cardinality, in particular there must be countable models. But we've already seen that we can infer the existence of uncountable sets from axioms of set theory. So what gives?

One interpretation is that ZFC is really something very weird. We may give the axioms human understandable labels like 'This one says there is an infinite set' and 'this one says you can take the power set', but really the axioms say what they say, and we hope one of their models captures our intuitive notion of set but some of its models are quite exotic and unintuitive.

I like to take it as emphasizing that we didn't show that the power set of $X$ is 'larger' than $X$. All we showed is that there is no bijection between them. Maybe they both sit inside some countable model but we just don't have enough functions in our model to map them to each other. Maybe the hierarchy of infinities doesn't say something about the abundance of infinite sets but about the relative paucity of functions we have on hand to map them to each other.

[1]: This is an approximation. Based on the acidity of the water there may be a surplus or deficit of hydrogen, and there may be oxygen molecules dissolved into the water.

[2]: The axioms say nice things like: one can take power sets, unions, set differences, subsets, the set containing two other sets, the image of a set under some function. And also that sets are equal if they have the same elements, a set contains an element from which it is disjoint, there is some infinite set, and the arbitrary product of nonempty sets is nonempty.

[3]: For there to be a model of ZFC it must be consistent. But if it is consistent its consistency is independent of ZFC. So in so far as ZFC captures mathematics for you the fact that there are models of ZFC must remain open. But it seems likely to me that it is consistent.