# Is there any example of a non-measurable set whose proof of existence doesn't appeal to the Axiom of choice?

Is there any example of a non-measurable set whose proof of existence doesn't appeal to the Axiom of choice?

What would it imply if there was such an example?

EDIT: For instance, maybe this will help understand the kind of example I had in mind, it is known that an important feature to determine that the AC is needed in the Banach-Tarski case is the non-transitivity of rotations on Euclidean space, one might find an example of a transitive group for some given space keeping the rest equal and make the AC unnecessary?

I guess then it might be said that this transitivity will be in this particular case equivalent to the AC or some amount of it, but I guess that it would be important to show this if it hadn't been realized before.

• Although the timing is a bit odd, could this possibly be related to the new PBS Infinite Series video about non-measurable sets and AC? Commented Sep 9, 2017 at 2:09
• I often find this question irritating. Not because it's bad. It's a very natural question to ask, of course, but because it sort of mixes syntax and semantics in a terrible way. Since ZF is consistent with "all sets are measurable" or even with the far more extreme "there is no nontrivial countably additive measure which vanishes on singletons", it is clear that ZF itself cannot prove that any definable set is measurable. But your question is talking about "sets which exist, and we just can't prove they are [non-]measurable". Exist where? Commented Sep 9, 2017 at 2:11
• (The point is that we can write a certain definition for a set to be either the least set in L which is non-measurable in the universe if such set exists, or empty otherwise. We certainly don't need to use choice to prove this set exists; but we need even more than just choice in order to prove that it is non-measurable. And yes, this is the usual "ugh, I hate talking to mathematicians/logicians/whatever" sort of answer, but it points a significant flaw in the naive formulation of the question.) Commented Sep 9, 2017 at 2:14
• Also, just a quick search in my posts brought up a couple of related questions: math.stackexchange.com/q/133999; math.stackexchange.com/q/1620692; and a handful of vaguely-related threads about independence results of this flavor, or otherwise measure-related questions. Commented Sep 9, 2017 at 2:24
• @Asaf Karagila Hi, thanks for commenting! 1) I had no idea about the PBS series, I just googled it and it was publised a day after I asked, (this might be what you refer to by odd timing which it would be more than odd if their was a direct relation due to the nature of time, but maybe you were wondering if I'm from PBS and had taken part in the making of it). Commented Sep 9, 2017 at 9:47

No, there is not - it is consistent with ZF that every set of reals is Lebesgue measurable, so some amount of the axiom of choice is needed.

This is even true if we assume dependent choice, a certain reasonably strong choice property (enough to do most useful theorems from analysis): this was proved by Solovay. He needed an additional assumption, though: that the theory ZFC+"There is an inaccessible cardinal" is consistent. It was later shown by Shelah to be necessary: we can prove that ZF+"There is an inaccessible cardinal" is consistent if and only if ZF+DC+"All sets of reals are measurable" is consistent.

In lieu of choice, I believe the consistency of ZF+"All sets of reals are measurable" from merely the consistency of ZF (the weakest possible assumption here) was proved by Truss. However, it's worth pointing out that in ZF alone, "measurable" doesn't necessarily mean what you think. For example, it's consistent with ZF that $\mathbb{R}$ is a countable union of countable sets, and in that context basic analytic properties like measurability go absolutely bonkers. So really the right base theory to look at, in my opinion, is ZF+DC; and then it's a very interesting fact that an inaccessible is needed.

• +1. I'd like to point out that on the other hand you can have non-measurable sets in $ZF\neg C$. It really depends on which $ZF\neg C$ system you're talking about, there are a lot of them and some of them are quite different from others.
– Ian
Commented Sep 6, 2017 at 19:31
• @Noah Schweber:well, "some amount of the axiom of choice" but not the explicit axiom itself might be shown to be implicit or hidden and unbeknownst so far in some assumption in certain mathematical structure. On the other hand I think that ZF+Hahn-Banach theorem is enough for the Banach-Tarski theorem proof, so that might be what you are referring to by "some amount of the AC is needed". In a way this is an answer in the affirmative of my question given that it was meant to refer to the explicit AC. I might edit the question to make it clearer what I was asking. Commented Sep 6, 2017 at 22:03
• @bonif Ah, are you just asking for a proof which doesn't appear to invoke Choice? (It will have to invoke something which can't be proved in ZF alone, so ...) Commented Sep 6, 2017 at 22:10
• @Noah Schweber Yes, that doesn't invoke it explicitly, so I guess I'm considering the possibility that certain math results that don't need proofs outside ZF might have implicitly certain amounts of AC. The fact that ZF is consistent with AC and its negation is attributed to its independence but it might also mean that is not strong enough to deal with some element of inconsistency in some of its implications. Commented Sep 6, 2017 at 22:41
• @bof Well, the natural way to say that would be to ask for a formula $\varphi$ such that (i) ZF proves that there is exactly one set of reals satisfying $\varphi$ and (ii) ZFC proves that that set is nonmeasurable. I think that's perfectly precise, and I don't know the answer off the top of my head. (If we replace C with V=L, then it has an easy positive answer since V=L gives canonical nonmeasurable sets (e.g. the $<_L$-least such), but C alone doesn't provide that kind of canonical structure.) Commented Sep 7, 2017 at 13:51

Yes.

Or more precisely,

Theorem: We can explicitly construct in ZF a set $S$ that ZF cannot prove to be measurable.

The set $S$ could then be proven non-measurable by assuming a suitable choice principle. So the role of choice is not in the existence of the set $S$, but in the proof it is nonmeasurable.

The proof of this theorem involves the constructible universe. In particular, one can explicitly define in ZF a well-ordering on the class of constructible sets.

One can construct $S$ by carrying out one's favorite construction of a non-measurable set inside the constructible universe, using the aforementioned explicitly constructible well-ordering instead of invoking the well-ordering theorem.

One cannot prove in ZF that $S$ is actually a non-measurable set. However, you can do so if you further assume the axiom of constructibility.

I think bof's interpretation of my original question is reasonable. I'm compelled to the following argument as an anwer to it in those terms but I'm certainly no set theorist so any correction is welcome: It seems to me that an affirmative answer would imply that ZF is not powerful enough to produce proofs about set measurability without the aid of the AC, probably because the AC (or the relavant part of it that bears on measurability) may be a direct consequence of the primitive notion of set that is needed to construct the ZF axioms and therefore ZF without an explicit extra axiom like AC cannot prove the existence of such an unmeasurable set. Unfortunately this would mean this affirmative answer could not be proved within ZF so it ultimately has to appeal to the AC wich would actually answer the original answer in the negative, leading to a situation of undecidability of the question within ZF to avoid contradiction.

• This sounds like a really-over-complicated way of saying "The existence of a non-measurable set is independent of ZF," which is exactly what I said in my answer - or is there something more here? Commented Sep 10, 2017 at 15:50
• You are right that it amounts to basically this, if anything the something more that I might mention is that, using reciprocity derived from LEM, the existence of nonmeasurable sets being independent of ZF seems to suggest that the existence of measurable sets may also be independent of ZF. See also: math.stackexchange.com/questions/142499/… Commented Sep 10, 2017 at 20:21
• No, ZF easily proves that e.g. the emptyset is measurable; the problem is entirely with non-measurability. This kind of reciprocity is not at all a consequence of LEM. Commented Sep 10, 2017 at 20:25
• You are right. For nonempy finite sets it is hard for me not to link existence of this property and its negation. Commented Sep 10, 2017 at 21:02