# Does the existence of a minimal cover for a subset of reals need some form of choice?

In Kanamori's book, "The Higher Infinite" p. 376, he defines a minimal cover of some $$A \subseteq \omega^\omega$$, to be any $$B \subseteq \omega^\omega$$, such that $$A\subseteq B$$ and that $$B$$ is Lebesgue measurable and if $$Z \subseteq B-A$$ is Lebesgue measurable, then $$m_L(Z) = 0$$. And he claims that picking some $$B$$ with $$A\subseteq B$$ and $$m_L(B)$$ minimal, does the job. [Here $$m_L$$ denotes the Lebesgue measure.]

Now here is my problem. The whole premise of this chapter is that we don't want to use choice to do these things. But any way I try to construct such a $$B$$, I inevitably use some form of choice. The best I can do is $$\mathsf{AC}_\omega(\omega^\omega)$$. Is there some choice-free way to do this?

A sketch of a proof with $$\mathsf{AC}_\omega(\omega^\omega)$$: Let $$x = \inf\{m_L(B): A\subseteq B \text{ and } B \text{ is Lebesgue measurable}\}$$. By $$\mathsf{AC}_\omega(\omega^\omega)$$, let $$\langle B_n: n<\omega\rangle$$ be a sequence such that $$A\subseteq B_n$$ and $$m_L(B_n) \rightarrow x$$ as $$n \rightarrow \infty$$. Now $$B = \bigcap_n B_n$$ is the desired minimal cover. $$\square$$

• Measure theory without at the very least $\sf AC_\omega(\Bbb R)$ is nothing short of terrifying. Aug 12, 2020 at 17:48
• Okay, another question, what is the Borel $\sigma$-algebra? Aug 12, 2020 at 17:57
• @ShervinSorouri In ZF alone that could be the full powerset of the reals. See e.g. here. Aug 12, 2020 at 17:59
• So in the Feferman–Levy model, where every set of reals is a countable union of countable sets, how do you define a measure on the Borel sets which is both countably additive and non-trivial? Aug 12, 2020 at 17:59
• @ShervinSorouri Well it means for example that measure isn't countably additive anymore. Aug 12, 2020 at 18:01

This is in fact a theorem of ZF. The Caratheodory construction of Lebesgue measure works in ZF, though without choice it need not be $$\sigma$$-additive. Every Borel codable set of reals is measurable but not necessarily every Borel set. See the paper cited below.

Let $$U_i$$ enumerate the basic open sets of $$\omega^{\omega}.$$ By (finite) subadditivity of $$\lambda^*$$ and adjusting the proof of the Lebesgue density theorem, we have that for any $$X$$ with $$\lambda^*(X)>0$$ and $$\epsilon >0,$$ there is $$U_i$$ such that $$\lambda^*(X \cap U_i) > (1-\epsilon) \lambda(U_i).$$

Define $$S_n$$ recursively by having $$i \in S_n$$ if $$\lambda^*(A \cap U_i \setminus \bigcup_{j\frac{n-1}{n} \lambda(U_i).$$ Let $$V_n = \bigcup_{i \in S_n} U_i$$ and $$V = \bigcap_{n<\omega} V_n.$$

By our density lemma, each $$A \setminus V_n$$ is null. Since $$\lambda^*$$ is additive among subsets of disjoint measurable sets, we have

$$\lambda(V_n) - \frac{1}{n} \le \frac{n-1}{n}\lambda(V_n) \le \sum_{i \in S_n} \lambda^*\left (A \cap U_i \setminus \bigcup_{j

We compute $$\lambda^*(A \setminus V) \le \inf_{n<\omega} \left ( \lambda^*\left (\bigcap_{i

Therefore, $$B := A \cup V$$ is measurable, with

$$\lambda^*(A) \le \lambda(B) = \lambda(V) \le \inf_{n<\omega} \lambda(V_n) \le \inf_{n<\omega} \left (\lambda^*(A) + \frac{1}{n} \right) = \lambda^*(A).$$ So $$B$$ is as desired.

Foreman, Matthew; Wehrung, Friedrich, The Hahn-Banach theorem implies the existence of a non-Lebesgue measurable set, Fundam. Math. 138, No. 1, 13-19 (1991). ZBL0792.28005.

• This is very cool, thanks! So in light of the other answer, the usual notions of real analysis seem to malfunction in the absence of choice. I'm wondering to what extent do the usual theorems and "definitions" go through in this setting; like the one you showed above. Would you know if there a systematic account of this available? Apr 24, 2022 at 22:16
• Fremlin's Measure Theory Vol. 5 goes into the measure theory of Borel-codable sets. Most of concrete measure theory has choiceless analogues in this setting. There isn't much written about what works and what doesn't in choiceless measure theory in more general settings. I'm working on filling that gap. See also this post: mathoverflow.net/a/393162/109573 Apr 25, 2022 at 3:26
• Oh I see, very nice. Thanks. Apr 25, 2022 at 20:32

This answer is purely a compilation of the ideas in the comments, given by Asaf Karagila and Noah Schweber. I have also made this a "Community Wiki", so I won't gain any reputation from any upvotes.

The thing is that in choiceless setting, most of our definitions in measure theory either don't make sense, or have different non-equivalent forms. To see an example look here. And also in certain cases we fail to have a measure on the Borel sets. For example in the Feferman–Levy model every set of reals is a countable union of countable sets and so it is not possible to have a measure on the Borel sets which is both countably additive and non-trivial. This is why some level of choice is required to even get started. And so the use of $$\mathsf{AC}_\omega(\omega^\omega)$$ in the above proof is justified.