7
$\begingroup$

In ZFC, every construction of a Lebesgue or Borel non-measurable set uses the axiom of choice. None of them that I've seen use choice to define a unique set, even though it's entirely possible to do so (e.g. under the AoC, if $\kappa = |A|$ is the cardinality of set $A$, then $\kappa$ is unique). So I've been wondering lately whether the strength of the AoC is enough by itself to construct a non-measurable set.

Here's an attempt at a specific question. In the language of set theory (first-order logic with equality extended with the ZFC axioms), is there a formula without parameters that identifies a unique, Lebesgue/Borel non-measurable set?

Improve this question
$\endgroup$
5
  • $\begingroup$ It seems to me that this would imply the existence of non-measurable sets in the Gödel's L, where AC is true. $\endgroup$
    – Martin Brandenburg
    Commented Jul 3, 2011 at 20:07
  • $\begingroup$ I think it would, but I don't see anything in the construction of, say, the Vitali sets, that excludes it from L. And Googling around, I see that it's known that there are "non-measurable $\Delta^1_2$ sets" (I assume w.r.t. the Lebesgue $\sigma$-algebra) in L. $\endgroup$
    – Neil Toronto
    Commented Jul 3, 2011 at 20:19
  • 2
    $\begingroup$ How about Lusin's set of continued fractions such that there exists an infinite increasing sequence $i_1 \lt i_2 \lt i_3 \lt \cdots$ with $a_{i_1} \mid a_{i_2}, \; a_{i_2} \mid a_{i_3}, \ldots$ which is Lebesgue (in fact analytic) but not Borel (Fund. Math 10, 1927, p. 77), see also planetmath.org/encyclopedia/… $\endgroup$
    – Theo Buehler
    Commented Jul 3, 2011 at 20:39
  • 5
    $\begingroup$ non-Borel and non-Lebesgue sets: two completely different questions. $\endgroup$
    – Gerald Edgar
    Commented Jul 3, 2011 at 20:54
  • $\begingroup$ @Gerald: Yes. I am sneakily asking two questions by parameterizing one question on two values. $\endgroup$
    – Neil Toronto
    Commented Jul 4, 2011 at 4:59

5 Answers 5

Reset to default
10
$\begingroup$

The answer below has been edited in light of other answers and comments.

There are all sorts of models of $ZFC$ in which every set is definable without parameters, including nonmeasurable sets; indeed a recent paper of Hamkins, Linetsky, and Reitz is devoted to such "pointwise definable" models.

Also, as pointed out in Theo Buehler's comment to the question, there certainly exist definable subsets of reals that are $ZFC$-provably not Borel.

However, the situation is completely different for measurability. The classical work of Solovay [using an inacessible] shows that there is a model of $ZFC$ in which every subset of reals in $OD(\Bbb{R})$ is Lebesgue measurable. Recall that $X$ is in $OD(\Bbb{R})$ if $X$ is definable with parameters from $Ord \cup \Bbb{R}$.

As pointed out in Demer's answer, Krivine [without an inaccessible] provided a model of $ZFC$ in which every ordinal definable subset of reals is measurable. Moreover, as shown by Harvey Friedman, here, there is a model of $ZFC$ [which is a generic extension of Solovay's model] in which the following property holds:

(*) Every equivalence class of sets of reals modulo null sets that is in $OD(\Bbb{R})$ consists of Lebesgue measurable sets.

Note that (*) implies that no non-measurable subset of reals in definable, since if $X$ is any definable subset of reals that is not measurable, then the equivalence class $\[X\]$ of $X$ modulo null sets satisfies the following two properties:

(1) $\[X\]$ definable,

(2) No member of $\[X\]$ is measurable.

So, to sum-up, the answer to the question for Lebesgue measurability is negative, i.e., there is no formula $\phi(x)$ in the language of set theory for which $ZFC$ proves "there is a unique nonmeasurable subset of reals satisfying $\phi$".

However, if $ZFC$ is strengthened to $ZFC+V=L$ then such a formula does exist, as pointed out in Goldstern's answer.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ali, thank you for mentioning my paper with Linetsky and Reitz. But it should also be mentioned that Ali himself has done important work on exactly the same topic (as we mention in our paper). See, for example, academic2.american.edu/~enayat/DO.pdf, and perhaps Ali can post other suitable links. $\endgroup$
    – Joel David Hamkins
    Commented Jul 4, 2011 at 1:28
  • $\begingroup$ I am a bit confused. I think that already Solovay's theorem provides a negative answer to the original question (if you read "identifies a unique set" as "defines a set"). $\endgroup$
    – Goldstern
    Commented Jul 4, 2011 at 12:32
  • $\begingroup$ @Martin: you are right, Solovay's result already does the job, and Friedman's extends it further. I will edit to clarify this point. $\endgroup$
    – Ali Enayat
    Commented Jul 4, 2011 at 16:28
  • $\begingroup$ I am in awe at how deep the answer to this question is. Thanks! $\endgroup$
    – Neil Toronto
    Commented Jul 5, 2011 at 1:04
  • $\begingroup$ Ali, I think that the result of Krivine that you mention gets only that all OD sets are Lebesgue measurable. For OD$(\mathbb R)$ sets you really need a Solovay-style argument, using an inaccessible. $\endgroup$
    – Andreas Blass
    Commented Jul 5, 2011 at 4:02
6
$\begingroup$

The other answers are excellent. But since you have adopted such a strong notion of definability, let me augment them with a positive observation.

The fact is that any particular set can be made definable without parameters in a forcing extension of the universe $V$. Indeed, there is a single definition $\varphi(x)$, such that for any set $A$ at all, there is a forcing extension $V[G]$ in which $A$ is the unique set such that $\varphi(A)$. Furthermore, one can arrange that the forcing extension $V[G]$ agrees with $V$ far beyond the reals, so that it has the same reals, the same sets of reals, the same measurable sets and so on for quite a long way.

In particular, there is a single definition such that for any non-Lebesgue measurable set $A$ that you favor, there is a forcing extension $V[G]$, an alternative set-theoretic universe, in which $A$ is defined by $\varphi$ and still non-measurable there.

Let me explain the proof. Fix any set $A$. Let $\kappa$ be the cardinality of the transitive closure $\text{TC}(\{A\})$. Thus, there is binary relation $E$ on $\kappa$ for which $\langle\kappa,E\rangle\cong\langle\text{TC}(\{A\}),{\in}\rangle$. This isomorphism is unique, since it is precisely the Mostowski collapse. Let $E_0\subset\kappa$ be the set of ordinals coding pairs in $E$. In the style of Easton's theorem, let $\mathbb{P}$ be the forcing notion coding the GCH pattern on the regular cardinals above $2^{\aleph_0}$ to first have a block of length exactly $\kappa$ on which the GCH holds, and then an violation of GCH and then a sequence of length $\kappa$ on which the GCH pattern on the regular cardinals matches the elements of $E_0$. In the resulting forcing extension $V[G]$, the cardinal $\kappa$ and the set $E_0$ and hence $E$ and hence $A$ are definable without parameters. Because the forcing is sufficiently closed, it does not adds new reals or sets of reals and it does not affect measurability. So in the extension, the set $A$ is definable by the formula $\varphi$ that expresses the decoding of the GCH pattern to $E_0$ and hence $E$ and hence $A$. This coding idea is due originally to K. McAloon.

The conclusion is that there is a kind of universal definition $\varphi$, which can serve to define any object at all, if only you apply the definition in the correct set-theoretic universe.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That is really cool, but it seems like cheating! "Indeed, there is a single definition $\phi(x)$, such that <i>for any set $A$ at all</i>..." So you can invent a universe in which $\phi$ uniquely identifies any set that you like. But then, in the meta-set-theory in which you build this universe, that set $A$ may be defined in some non-unique way. If you handed me this set-theoretic universe and such a $\phi$, I couldn't tell precisely which set $\phi$ defines. It's more like you would have handed me a <i>collection</i> of universes. Is that right? $\endgroup$
    – Neil Toronto
    Commented Jul 5, 2011 at 1:03
  • $\begingroup$ Sort of, yes. The forcing method allows us to build extensions of any given set-theoretic universe, and we can build them in such a way that the definition I mentioned succeeds in defining a given desired set $A$, no matter which $A$ we use (each $A$ gets its own forcing extension). The issue here is that the notion of definable-in-the-language-of-set-theory is extremely powerful and general, perhaps much more general than the kind of definitions that you may have intended. It would make sense to restrict to, say, projective definitions, which are addressed by the other answers. $\endgroup$
    – Joel David Hamkins
    Commented Jul 5, 2011 at 1:24
  • 2
    $\begingroup$ @Neil: If Joel "handed me [a] set-theoretic universe and such a $\phi$," then it would be completely determined what set $\phi$ defines in that universe. That "I couldn't tell precisely which set $\phi$ defines" is just the result of my inability to fully inspect an infinite universe. (The same inability prevents me from telling exactly what the set of prime numbers is, even though that's the same in all models of set theory whose natural numbers are standard.) What's special about Joel's $\phi$ is how dramatically its extension varies from universe to universe. $\endgroup$
    – Andreas Blass
    Commented Jul 5, 2011 at 4:10
  • $\begingroup$ @Neil: Another comment about "if you handed me this set-theoretic universe and such a $\phi$" --- Joel has, in effect, handed us $\phi$. His argument specifies a particular formula $\phi$. Handing you a universe is admittedly harder, because each set-theoretic universe is infinite. $\endgroup$
    – Andreas Blass
    Commented Jul 5, 2011 at 4:14
4
$\begingroup$

There is no simple formula that invariably describes a set of reals which is not Lebesgue measurable. The reason is that the existence of certain large cardinals imply that all simply definable subsets of $\mathbb{R}$ are Lebesgue measurable.

For example, if there are infinitely many Woodin cardinals with a measurable above, then $L(\mathbb{R})$ satisfies the Axiom of Determinacy and hence all sets in $L(\mathbb{R})$ are Lebesgue measurable. Here, $L(\mathbb{R})$ is the smallest transitive model of ZF that contains all the ordinals and all the reals; this universe contains all the projective sets and much more.

It seems that the situation is hopeless, but this is not quite true. There has been a lot of recent research which shows that the existence of definable wellorderings of $\mathbb{R}$ is not incompatible with some of the largest cardinals we know. However, the definition of these wellorderings of $\mathbb{R}$ is necessarily very complex.

Improve this answer
$\endgroup$
4
$\begingroup$

Concerning Borel measurability, it was already pointed out that there is an explicit formula s(x) such that ZFC proves "The set { x in R: s(x) } is not Borel". (This is not true for ZF, as was pointed out elsewhere.)

Concerning Lebesgue measurability, ZFC neither proves nor refutes the following:

There is an OD-definition (or: OD(R)-definition) of a subset of the reals which is non-measurable.

There is a slight fuzziness here, because there are many non-equivalent notions of definability; OD(R)-definability is perhaps the most prominent and useful.

But an explicit formula can be given: There is a formula phi(x) in the language of set theory (without parameters) such that ZFC neither proves nor refutes

"The set { x in R : phi(x) } is non-measurable".

In fact, phi(x) can be of a rather simple form ($\Delta^1_2$, as you remarked above). Here is an abbreviated version of phi: For each real number x, let $x_1$ be the number obtained from x by deleting all even decimal places, $x_2$ by deleting all odd decimal places (do what you want for the countably many reals where this is not well-defined). This defines a measure-preserving Borel map from $\mathbb R$ to $\mathbb R\times \mathbb R$. Now consider the set M of all reals x for which there is some $\alpha$ such that $x_1\in L_\alpha$, but $x_2\notin L_\alpha$. ZFC does neither prove nor refute that M is Lebesgue-measurable.

(I think that the fact that ZFC does not prove that M is measurable is already due to Gödel.)

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ @Martin: as an example of a $\Delta^1_2$ non-measurable set in $ZF+V=L$ isn't it easier to look at the well-ordering $W$ of the reals of order-type $\aleph_1$ in $L$? Sierpinski had already observed, using Fubini's theorem, that no such $W$ can be measurable. $\endgroup$
    – Ali Enayat
    Commented Jul 4, 2011 at 17:29
  • 1
    $\begingroup$ Martin's example is very close to the well-ordering suggested by Ali. The former is the pre-well-ordering obtained from the latter by obliterating the distinction between reals that are constructed simultaneously. Since the resulting equivalence classes are countable, Sierpinski's argument seems adequate for handling the pre-well-ordering as well as the well-ordering. $\endgroup$
    – Andreas Blass
    Commented Jul 5, 2011 at 4:24
  • $\begingroup$ Thank you, Andreas. I prefer the preorder that I gave over the (possibly more usual) well-order for two reasons: It is as canonical as the hierarchy of $L_\alpha$'s; well-ordering the countable differences $L_{\alpha+1} \setminus L_\alpha$ is less canonical, as you have to introduce some arbitrary order on the formulas (or Gödel operations). The second reason is related: In an exposition of $L$, this preorder can appear right after the definition of $L$, half a page before the well-order on $L$ is introduced. $\endgroup$
    – Goldstern
    Commented Jul 6, 2011 at 12:53
  • $\begingroup$ Thanks for pointing out that it was probably Sierpinski, not Gödel, who showed that a well-order of the reals in type omega1 yields a nonmeasurable set. $\endgroup$
    – Goldstern
    Commented Jul 6, 2011 at 12:54
3
$\begingroup$

http://en.wikipedia.org/wiki/Solovay_model

"In particular Krivine (1969) showed there was a model of ZFC
in which every ordinal-definable set of reals is measurable."


If all subsets of $\mathbb{R}$ are ordinal-definable then there is such a formula.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For the second part, you only need that every real is ordinal definable since that already gives a definable wellordering of $\mathbb{R}$. $\endgroup$
    – François G. Dorais
    Commented Jul 3, 2011 at 22:04
  • $\begingroup$ (And thanks for pointing out that Krivine paper!) $\endgroup$
    – François G. Dorais
    Commented Jul 3, 2011 at 22:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .