In this article, we aim to give an introduction to the set theoretic study (Jech 2003) of relation between regularity properties of the reals and the Axiom of Choice. Broadly conceived, regularity properties are desirable properties of set of real that appears in various different fields in mathematics. Among them, we are going to sketch Lebesgue Measurability (LM) and Ramsey Property (RP). Diverse and seemingly unrelated they are, it turns out that they share a surprisingly similar pattern. We are going to show that with Axiom of Choice, we can show the existence of sets that break LM and RP respectively. Moreover, due to a celebrated result of Robert M. Solovay (Solovay 1970), via the method of forcing, we are able to show that the full Axiom of Choice is necessary to break these regularity properties. The negative result was proved by constructing a model where all usual of Zermelo–Fraenkel axioms hold and Axiom of Choice fails, yet ALL sets of reals have LM and RP.
1. Axiom of Choice
The Axiom of choice is the statement that:
Axiom of Choice: For any family $A$ of pairwise disjoint nonempty sets, then there is a choice function $f$ s.t. $f(A)\in A$.
Russell famously gave an
analogy
to help understand the axiom. Say a millionare owns infinitely many
pairs of shoes $Shoes_i,i\in I$, then there is always a way to choose
one shoe out of each pair: you may choose the left shoe out of each pair
since the left shoe and the right one are different. The function is
described by $Shoes_i\mapsto {=tex}$ the only element $s$ in $S_i$
s.t. $s$ is the left one. Axiom of Choice is not involved here.
However, the case for socks $Socks_i,i\in I$ are different. It is conceivable that the socks for left and right feet are indistinguishable, so there is no specific rule you can apply to choose a sock out of each pair. This illustrates where the Axiom of Choice comes into play. The Axiom asserts that nevertheless, there is a function that chooses from each pair: there is $f$ s.t. $f(Socks_i)\in Socks_i$.
2. Regularity Properties
2.1 Lebesgue Measurability (LM)
Lebesgue measurability is one of the most crucial concept in analysis and probability theory. Rather than giving a detailed account of the theory, we are satisfied with informally saying that a set $X\subseteq \mathbb{R}$ is Lebesgue measurable means that it is regular in the sense that the result of measuring its size from the outside is equal to measuring its size from the inside (The outer measure of $X$ is equal to its inner measure). In this sense, a LM set cannot be too chaotic.
In 1905, with the help of Axiom of Choice, Giuseppe Vitali showed that there is a set that is not LM. Such sets are now known as the Vitali sets.
2.2 Ramsey Property (RP)
In combinatorial, the infinite Ramsey theorem states that any infinite binary graph contains an infinite homogeneous set, a set whose elements are either pairwise connected or pairwise disconnected. Indeed, the theorem is true for any $n$-ary graphs, whose edges connect $n$ elements instead of $2$.
Thinking beyond the finite case, we can ask whether the similar strutural pattern emerges for graphs with infinite aried edges. For a set $X$, we denote by $[X]^\omega$ the set of subset of $X$ of size $\omega$.
Definition 1.1 Let $\mathcal{R}\subseteq [\mathbb{N}]^\omega$ be a set of infinite subset of $\mathbb{N}$, $\mathcal{R}$ is said to have the Ramsey Property if there is a infinite homogeneous set $A\subseteq \mathbb{N}$. i.e. $[A]^\omega\subseteq R$, or $[A]^\omega\cap \mathcal{R} = \emptyset$.
A set $\mathcal{R}\subseteq [\mathbb{N}]^\omega$ is thus conceived as the infinite aried edges of a infinite graph on underlying set $\mathbb{N}$, and is said to have RP if there is a subgraph that is totally connected or totally disconnected. The property does not seem outright to be a property of sets of real numbers, but rather a property of subsets of $[\mathbb{N}]^\omega$. However, from a set theoretic point of view, $[\mathbb{N}]^\omega$ and $\mathbb{R}$ are of course equinumerous and there is a way to view $[\mathbb{N}]^\omega$ as sharing similar properties as the real line $\mathbb{R}$. So for now we indulge ourselves in calling RP a regular property of the set of reals.
And you guessed it, as the Axiom of Choice comes into play, we can show the existence of a set failing RP.
Proposition 1.2 (AC) There is a set without the RP.
Here is the idea of the proof. We consider the equivalence relation $\equiv_{fin}$ on $[\mathbb{N}]^{\omega}$ s.t. $X\equiv_{fin} Y$ iff their symmetric difference is finite.
By axiom of choice, for each equivalent class of the relation we can pick a representative. Consider the function $f$ that takes an equivalent class $[X]$ to an element in it, $f([X])\in [X]$. Now we consider the following set $\mathcal{S}\subseteq [\mathbb{N}]^\omega$:
$$X\in \mathcal{S}\iff |X\Delta f([X])| \text{ is even}$$We invite the readers to check that the set $\mathcal{S}$ cannot have RP, basically because the property $|X\Delta f([X])| \text{ is even}$ can be made to fail by altering $X$ finitely, but which equivalence class $X$ belongs to does not change so easily.
3. Solovay Model and Full Regularity
In our above discussion, the standard story is that there is a desired regularity property which we wish it to be true for all sets of the reals, yet the Axiom of Choice comes into play and ruins our day.
Hence it is natural to ask whether Axiom of Choice is necessary for the existence of these irregular sets. Is it possible to prove the failure of LM and RP on some sets without using the Axiom? In 1970 Solovay answered the question negatively for LM and later Mathias showed that Solovay’s argument works for RP too (Mathias 1977).
Solovay’s theorem states that assuming that ZFC, the Zermelo–Fraenkel Axioms with choice is consistent with some large cardinal assumption, then
Theorem 1.3 (Solovay and Mathias) It is consistent with ZF that all sets of reals are LM and RP.
Let’s forget about the part of the assumption that mentions large cardinal assumption, which is not a key point for our topic. We have to assume the consistency of ZFC basically because by Gödel’s second incompleteness theorem, we can never prove that ZFC is consistent.
The method with which Solovay established the result was forcing, allowing one to start from a model of set theory and construct a new one. By starting from a model of ZFC and some large cardinal assumption, Solovay constructed a new model with a submodel where AC fails, yet all sets have LM and RP. This submodel was known as the Solovay model.
Perhaps more surprisingly, in the Solovay model the principle of Dependent Choice, a marginally weaker version of the Axiom of choice holds. This means that existence of pathological sets assumes the full power of AC. This perhaps serves as an argument against full AC, depending on our philosophical view.
Moreover, the story for LM and RP are happening again and again. There are other regularity properties discussed in various field of mathematics: perfect set property in set theory; the property of Baire in topology and etc. Under AC, the aspiring regularity property of sets of the reals does not hold on all sets of the reals. However, AC is necessary for the existence of such pathological sets, as all these regular properties hold for all sets of the reals in the Solovay model.
Wrapping things up, in this article we peaked into an ‘ideal world’ where regularity prevails on the realm of reals. And the Axiom of Choice does not distort things and produce chaotic objects that does not have the notion of size, does not have a homogeneous part, etc.
The set theoretic study of regularity does not end with the Solovay model. Measuring the complexity of a set of real with the projective hierarchy, with sets higher up the hierarchy viewed more complicated in definability sense, descriptive set theorists discovered that with stronger and stronger set theoretic assumptions, regularity climbs up the ladder: more and more sets in the projective hierarchy enjoys all the regular properties.
Bibliography
Jech, Thomas. 2003. Set Theory: The Third Millennium Edition. Springer.
Mathias, A. R. D. 1977. “Happy Families.” Annals of Mathematical Logic 12 (1): 59–111. https://doi.org/ https://doi.org/10.1016/0003-4843(77)90006-7 .
Solovay, Robert M. 1970. “A Model of Set-Theory in Which Every Set of Reals Is Lebesgue Measurable.” Annals of Mathematics 92 (1): 1–56. http://www.jstor.org/stable/1970696 .