# Definable collections of non measurable sets of reals

Is there a definable (in Zermelo Fraenkel set theory with choice) collection of non measurable sets of reals of size continuum? More verbosely: Is there a class A = {x: \phi(x)} such that ZFC proves "A is a collection, of size continuum, consisting of non Lebesgue measurable subsets of reals"?

-
Doesn't the set of translates of the Vitali set have this property? – Qiaochu Yuan Dec 18 '09 at 22:16
As Qiaochu says, as long as you have 1 nonmeasurable set, which you do with ZFC, taking all of its translates should do the trick. Or you could fix a nonmeasurable set A and take the set of sets A\S where S is a countable subset of A. Maybe there are additional properties you want? – Jonas Meyer Dec 18 '09 at 22:26
But why should there be a definable Vitali set? Of course, some models of set theory have definable Vitali sets, because sometimes there is even a definable well-ordering of the reals, but the question asks for a parameter-free definition that provably works in every model of set theory. – Joel David Hamkins Dec 19 '09 at 18:55
Joel, I will speak only for myself of course; my comment should have been phrased as a question if left at all, because I did not understand what was meant by definable. Thank you for providing so much food for thought! – Jonas Meyer Dec 20 '09 at 6:17
To Qiaochu: Like Joel said, it is consistent to have no definable non measurable set of reals, even if you allow countably many ordinal parameters. – Ashutosh Dec 20 '09 at 7:29

(Edit.) With a closer reading of your question, I see that you asked for a very specific notion of definability.

If you allow the family to have size larger than continuum, there is a trivial Yes answer. Namely, let phi(x) be the assertion "x is a non-measurable set of reals". In any model of ZFC, this formula defines a family of non-measurable sets of reals, and it is not difficult to show in ZFC that there are at least continuum many such sets (for example, as in the comment of Qiachu Yuan). Thus, ZFC proves that {x | phi(x)} is a family of non-measurable sets of size at least continuum.

But if you insist that the family have size exactly the continuum, as your question clearly states, then this trivial answer doesn't work. Indeed, one can't even take the class of all Vitali sets in this case, since there are 2^continuum many sets of reals that contain exactly one point from each equivalence class for rational translations.

Qiachu Yuan's suggestion about translations of a single Vitali set does have size continuum, but there is little reason to expect the Vitali set to be definable in the way that you have requested, and so it does not provide the desired definable family.

In my earlier posted answer, I considered the possibility that you might have meant some other notion of definability, or whether parameters are allowed in the definition, and so on. And I find some of these other versions of the question to be quite interesting and subtle.

I pointed out that it is surely consistent with ZFC that there is the desired definable family of non-measurable sets, since in fact any set at all can be made definable in a forcing extension that adds no reals and no sets of reals. So you can take any family of non-measurable sets that you like and go to a forcing extension where this family is definable.

Perhaps a stronger notion of definibility would be to use the notion of projective definitions, where one wants to define the sets within the structure of the reals, using quantification only over reals and natural numbers (rather than over the entire set-theoretic universe). Thus, we want a projective formula phi(x,z), such that A_z={x | phi(x,z)} is always non-measurable for any z and all A_z are different. Such a formula would be a strong example of the phenomenon you seek.

The first answer to this way of asking the question is that it is consistent with ZFC that there is such a projective family. The reason is that I have mentioned in a number of questions and answers on this site, under the Axiom of Constructibility V=L, there is a projectively definable well-ordering of the reals. Thus, under V=L, one can projectively define a Vitali set, and then take the family of its translations. There is no need for a parameter in this definition, since a particular Vitali set can be projectively defined without parameters from the projectively definable well-ordering of the reals.

The second answer to this version of the question, however, is that under certain set-theoretic assumptions such as Projective Determinacy, every projective set of reals is Lebesgue measurable. In this case, there can be no such projectively defined family of non-measurable sets. The assumption of PD is consistent with ZFC from large cardinals, but perhaps one needs a much weaker hypothesis meerely to get every projective set measurable.

In summary, if one wants a projectively definable family of non-measurable sets, then it is independent of ZFC, if large cardinals are consistent. (Perhaps the need for large cardinals can be reduced.)

-
An inaccessible is required and sufficient for your last paragraph, and Harvey's paper mentioned in Ashutosh's answer shows it also suffices to give (consistently) a negative answer to the original question. – Andrés Caicedo Sep 30 '10 at 20:06

The following appears in On definability of non measurable sets, Harvey Friedman, Canadian Journal of Mathematics, Vol. 32, No. 3, 1980.

Let $M$ be the Solovay's model for $ZF + DC + V = L(R) +$ every set of reals is Lebesgue measurable etc. Let $\kappa$ be a regular cardinal of cofinality bigger than $\omega_1$ in $M$. Then forcing with countable partial functions from $\kappa$ to $2$ gives a model $N$ which satisfies choice and the statement: "Every definable, with ordinal and real parameters, set of sets of reals of size less than continuum has only Lebesgue measurable sets".

-
Ashutosh, if possible, please replace $L[R]$ with $L(R)$. It is unfortunate that both notations mean different things and they used to be confused (in print!) a few decades ago. – Andrés Caicedo Sep 30 '10 at 20:07
You're right. The distinction does matter here. – Ashutosh Sep 30 '10 at 23:19