# Are there more Lebesgue measurable or more non Lebesgue measurable functions?

Are there more Lebesgue measurable or more non Lebesgue measurable functions?

-
How do you define "more"? – Jonas Teuwen Nov 10 '11 at 16:10
The cardinality of the class of all functions from $\mathbb{R}$ to itself is $c^c$, where $c=|\mathbb{R}|$. I suspect the cardinality of the set of Lebesgue-measuarble functions is smaller. – Michael Hardy Nov 10 '11 at 16:14
@Michael: my suspicion is that the cardinality of functions with Lebesgue measure 0 is $c^c$ (perhaps even just looking at functions which are non-zero only on the Cantor set). – Henry Nov 10 '11 at 16:21
Is that true that Lebesque-measureable functions is smaller? Given a $1-1$ correspondence between $\mathbb R$ and the Cantor set, $C$, any function $\mathbb{R}\rightarrow \mathbb R$ can be associated with a function with support $C$. Since $C$ has measure $0$, the corresponding function is measureable. – Thomas Andrews Nov 10 '11 at 16:24

The sets are the same cardinality.

Given a single unmeasurable function $g$, and any measurable function $f$, $f\rightarrow f+g$ is a 1-1 function from the set of measurable functions to the set of unmeasurable functions.

On the other hand, let $C$ be the Cantor set (or any measure-zero subset of $\mathbb R$ with the same cardinality as $\mathbb R$.) Then let $\phi:\mathbb R \rightarrow C$ be a 1-1 correspondence, and, for any unmeasurable function $f:\mathbb R \rightarrow \mathbb R$, define $f^\phi:\mathbb R \rightarrow \mathbb R$ as $f^\phi(x)=0$ if $x\not\in C$ and $f^\phi(x)=f(\phi^{-1}(x))$ if $x\in C$. Then $f^\phi$ is measurable (since it's support is a subset of $C$) and $f^\phi = g^\phi$ if and only if $f=g$. Therefore, we have a 1-1 map from the set of unmeasurable functions to the set of measurable functions.

So we have that the two sets are the same cardinality.

If we define an equivalence relation $f \cong g$ if $\{x:f(x)\neq g(x)\}$ is measure zero, are the two sets, modulo this equivalence, still the same?

Also, is there a Baire category-like sense in which the non-measurable functions are "larger?"

-
Doh, of course! – Thomas Andrews Nov 10 '11 at 19:04
@Thomas Andrews: Regarding your question on a Baire category-like sense, the following related result may be of interest. Let $N[0,1]$ be the collection of subsets of $[0,1]$ modulo the equivalence relation $\sim$ defined by $E \sim F \Leftrightarrow \lambda^{*}(E \Delta F) = 0$, where $\lambda^{*}$ is outer Lebesgue measure. The set $N[0,1]$ can be made into a complete metric space by defining $d(E,F) = \lambda^{*} (E \Delta F).$ In the reference that follows it is proved that $N[0,1]$ is a perfect nowhere dense set in $N[0,1].$ comment continues – Dave L. Renfro Nov 10 '11 at 19:26
@Thomas Andrews: continuation of previous comment Thus, in this setting the collection of measurable subsets of $[0,1]$ makes up a very tiny part of the collection of all the subsets of $[0,1].$ Nobuyuki Kato, Tadashi Kanzo, and Oharu Shinnosuke, A note on the measure problem, International Journal of Mathematical Education in Science and Technology 19 (1988), 315-318. [Zbl 637.28002] – Dave L. Renfro Nov 10 '11 at 19:27
@Thomas: The measurable functions under the equivalence relation you mention gives $L^0(\mathbb{R})$, which is a complete separable metric space (in fact, an F-space) en.wikipedia.org/wiki/F-space. So, it has cardinality $\mathfrak{c}$. In fact, it is an uncountable Polish space, so it Borel-isomorphic with $\mathbb{R}$. – George Lowther Nov 10 '11 at 21:25
I think the set of all functions under that equivalence will be at least as large as $2^\mathfrak{c}$, just by considering Vitali sets. – George Lowther Nov 10 '11 at 21:31

The total number of functions from $\mathbb{R}$ to itself is (assuming the Axiom of Choice for the cardinal arithmetic): $$\mathfrak{c}^{\mathfrak{c}} = (2^{\aleph_0})^{2^{\aleph_0}} = 2^{\aleph_02^{\aleph_0}} = 2^{2^{\aleph_0}} = |\mathcal{P}(\mathbb{R})|.$$ I.e., it is equal to the cardinality of the power set of $\mathbb{R}$.

As Thomas Andrew notes, if $N$ is any subset of $\mathbb{R}$ that is of measure $0$, then any function that is supported in $N$ is Lebesgue measurable; in particular, all characteristic functions of subsets of $N$ are Lebesgue measurable. There are $$|\mathcal{P}(N)| = 2^{|N|}$$ such functions.

Letting $C$ be the Cantor set (or any measurable uncountable set of measure $0$), we obtain a lower bound for the set of Lebesgue measurable functions of $$\Bigl|\{\chi_A\mid A\subseteq C\}\Bigr| = \Bigl|\mathcal{P}(C)\Bigr| = 2^{|C|} = 2^{2^{\aleph_0}}.$$

Thus, the set of Lebesgue measurable functions has cardinality $2^{2^{\aleph_0}}$.

In particular, there can be no more non-measurable functions than measurable functions.

Conversely, still assuming the Axiom of Choice, let $V$ be a Vitali subset of $\mathbb{R}$ contained in $[0,1]$, and let $A=V+2$, so that $A$ is a nonmeasurable subset of $\mathbb{R}$, $A\subseteq [2,3]$. If $D$ is any subset of the Cantor set, then $A\cup D$ is nonmeasurable, so $\chi_{A\cup C}$ is a nonmeasurable function. Therefore, there are at least $$|\mathcal{P}(C)| = 2^{|C|} = 2^{2^{\aleph_0}}$$ nonmeasurable functions, and so there are exactly that many.

Therefore, assuming the Axiom of Choice, the cardinality of the set of Lebesgue-measurable functions from $\mathbb{R}$ to $\mathbb{R}$, and the cardinality of the set of non-Lebesgue-measurable functions from $\mathbb{R}$ to $\mathbb{R}$, are equal, and equal the cardinality of the set of all functions from $\mathbb{R}$ to $\mathbb{R}$.

I believe the use of the Axiom of Choice is important here, since Solovay proved that it is consistent with ZF that all subsets of $\mathbb{R}$ are Lebesgue measurable, in which case every function would be Lebesgue measurable.

-
The cardinal arithmetic you use does not use AC. However, to show that indeed there are unmeasurable functions you do need it. In fact it is possible for all the sets to be Borel, which is even "worse" :-) – Asaf Karagila Nov 10 '11 at 18:43
@Asaf Karagila: what would be so bad about all sets being Borel? However, in the absence of choice, you should really modify the definition of a Borel set anyway. – George Lowther Nov 10 '11 at 19:21
I resolved my confusion: the problem is that Asaf is referring to the other definition of Borel. It is not possible for all sets of reals to be $\Delta^1_1$, which would be very strange. – Carl Mummert Nov 10 '11 at 19:23
@Carl Mummert: it's a fact that without choice, it is consistent that the reals is a countable union of countable sets (as has been mentioned several times on both math.SE and math.MO). – George Lowther Nov 10 '11 at 19:24
@George: What do you purpose as the definition of a Borel set? I think that "an element of the smallest $\sigma$-algebra containing the open intervals" is a fine definition. – Asaf Karagila Nov 10 '11 at 19:26

MORE in some sense... In ZF we can explicitly write down countably many Lebesgue measurable functions. (For example, a rational constant.) But we cannot explicitly write down (and prove in ZF) even one non-Lebesgue measurable function. SO in this sense there are more measurable functions!

-
Sure, given the right axiom system, all $f:\mathbb R \to \mathbb R$ are continuous. – Thomas Andrews Nov 10 '11 at 19:05
@Thomas: Do you have a reference to that? – Asaf Karagila Nov 10 '11 at 19:14
@GEdgar: This is because you cannot explicitly write even one non-Borel set as well. Even with the axiom of choice you cannot go much further than $\Sigma^1_3$ or so... – Asaf Karagila Nov 10 '11 at 19:15
@AsafKaragila: In, for example, constructive mathematics, all such functions are continuous. In constructivism, a real number has to be a necessarily computable sequence of rationals along with a proof that the sequence is Cauchy. Two such sequences are equal if you can prove that their difference converges to zero. Now, if you want to define a function on the real numbers, you necessarily have to define it in such a way that the choice of sequence representation doesn't matter, and this forces that a "constructive" function is necessarily continuous. – Thomas Andrews Nov 10 '11 at 20:32
@Thomas: I see. As a set theory grad student whose primary interest is AC consistency questions, I have to admit that I would find this set of axioms very constrictive. :-) – Asaf Karagila Nov 10 '11 at 20:34