# How complicated is the formula expressing that a set is non-measurable?

The question is exactly stated by the title, i.e. how complicated is the formula $\psi(x)$ (in the language of set theory) expressing that a given set of reals $x$ is non-measurable?

A second question would be: can this formula be deduced from a formula (possibly with ordinal parameters or a countable sequence of ordinals) which involves only quantification over reals and natural numbers?

PS: By "deduced" I mean, given a formula $\varphi(x)$ defining a set $x$, then can we have $ZFC \vdash \forall x (\varphi(x) \rightarrow \psi(x))$.

• No, it cannot be deduced (from $\mathsf{ZFC}$, I assume). It is consistent that all the sets you suggest are Lebesgue measurable. Do not call them projective, that is an established term for a different concept. For some references, see Neeman's book on determinacy of long games (Chapter 7), and Woodin's talk at the proceedings of the 2002 ICM. The sets that are usually called projective are determined as well under appropriate assumptions, by the way. Dec 7, 2013 at 17:12
• Related question: Are larger large cardinals less expressible?
– user43940
Dec 14, 2013 at 13:36

Let me first consider the case where we use the usual notion of projectively definable set of reals, where $\varphi(x)$ is a property of the reals that might become a member of the set $X$ we are defining. Suppose that $X=\{ x\in\mathbb{R}\mid \varphi(x,z)\}$ is a projective set of reals, defined with a projective formula $\varphi$, which means that all quantifiers range only over reals and natural numbers, in a suitable language, with real parameter $z$. (One doesn't ordinarily allow ordinal parameters in a projective definition, and it isn't clear how one could use them anyway if all the quantifiers only range over reals and natural numbers.)

To say that $X$ is measurable is equivalent to the assertion that we may cover $X$ and its complement with open sets, whose intersection has as small a measure as we like: for every positive $\epsilon$, there are open sets $U\supset X$ and $V\supset\mathbb{R}\setminus X$ with $\mu(U\triangle V)\lt\epsilon$. Quantifying over open sets amounts to a real quantifier, since every open set is a countable union of rational intervals; and we may take $\epsilon=\frac1n$.

Thus, if $X$ has complexity $\Delta^1_n$ in the projective hierarchy, then the assertion "$X$ is measurable" has complexity at most $\Sigma^1_{n+1}$, and the assertion "$X$ is not measurable" has complexity at most $\Pi^1_{n+1}$, and these assertions are only a little bit more complicated than $X$ itself. In particular, these assertions are also projective.

For your second question, you seem to be asking whether there is a particular projective definition of a set of reals that we can prove (from ZFC?) that it is definitely not measurable. The answer is that we should not expect to do this, because the existence of certain large cardinals implies that every projective sets of reals is Lebesgue measurable, and so succeeding in your task would refute the consistency of those large cardinals, which would be an unexpected and amazing development. Meanwhile, of course, we cannot say for certain that we cannot find an example of what you seek, since the nonexistence of such a formula implies at the very least that ZFC is consistent, which is also something that, if true, we cannot prove.

Now let us consider your rather more idiosyncractic notion of definablity, where $\varphi(X)$ is a property of the set $X$ of reals, perhaps defined using only quantification over natural numbers and reals, where we allow $X$ to appear as a predicate in atomic subformulas of $\varphi$. The point to make now is that "$X$ is nonmeasurable" is expressible using quantifiers only over the natural numbers and the reals. So the family of all non-measurable sets is definable by a definition of your favored type. In this case, we can say, yes, indeed, there is a formula $\varphi(X)$ which ZFC proves holds of some sets, such that ZFC proves that $\forall X\ \varphi(X)\to X$ is not measurable, since in fact ZFC proves $\varphi(X)\leftrightarrow X$ is not measurable.

• You cannot assume $U$ and $V$ to consist of only finitely many intervals. This would in fact define Jordan–Peano measurability (consider $X=\mathbb Q$). Dec 7, 2013 at 18:19
• You are completely right, and I have now edited to correct this. Dec 7, 2013 at 18:23
• In your first paragraph, concerning quantification over ordinals for projective formulae, one could allow quantification for $\alpha < \omega_1$ because countable ordinals are coded by reals (The $WO$ set). If $x^{\#}$ exists for every $x \in \mathbb{R}$ then one could also code ordinals up to $u_{\omega}$, the $\omega$-th uniform indiscernible, by reals (under $AD, u_{\omega}=\aleph_{\omega}$. Dec 7, 2013 at 19:44
• If $\varphi(x)$ is not a definition of a set of reals, but rather a property shared by a family of sets of reals, does the same reasoning applies? Dec 7, 2013 at 19:48
• Carlo, yes, of course, but this is still really only using reals as parameters. My point was that if the formula allows only quantification over $\omega$ and over $\mathbb{R}$, then the formulas simply cannot distinguish between any two infinite ordinals as parameters, since they have all the same elements below $\omega$ and in $\mathbb{R}$. So it is not sensible to have ordinal parameters directly. Rather, one wants to use codes for ordinals in the manner you are suggesting, with real parameters. Dec 7, 2013 at 19:50

Let me add to Joel's excellent answer the following remarks: it follows from the classical work of Foreman, Magidor and Shelah that if there is a supercompact cardinal then all sets of reals in $L(\mathbb{R})$ are measurable. This means that starting with a supercompact cardinal, one can't contruct a wellordering of $\mathbb{R}$ in $L(\mathbb{R})$. In particular if there are $\omega$ Woodin cardinals, there is no projective wellordering of $\mathbb{R}$. So any formula expressing the non measurability of some set of reals would imply some anti-large cardinal statement (This is what Joel's is mentionning in his last paragraph). In other words under large cardinals, there are no wellorderings of a large initial segment of the Wadge Hierarchy (The Wadge Hierarchy is the hierarchy of complexity of the sets of reals, it goes all the way to $\Theta$ which is $\mathfrak{c}^+$ under $AC$ but it is very very large under large cardinals.)

• Could you address the case that $\varphi(x)$ (as in my question above) is not a definition of a set of reals but rather a property shared by a family of sets of reals? Dec 7, 2013 at 20:56
• Say I consider all sets of reals Wadge reducible to some set $A$. So the sets of reals having this property form a pointclass $\Gamma(A)$. So basically one would be looking at the complexity of the strategy (or function, strategies are basically Lipschitz continuous functions) occurring in the Wadge game. I guess this is given by the 3rd Periodicity theorem: if the payoff set is in some pointclass $\Lambda$ then the strategy $\tau$ will be in $\Game \Lambda$. But if you take a different $\phi$ you might get some other complexity, so I don't know if there is a way to make sense of your question Dec 8, 2013 at 6:32