6
$\begingroup$

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

Does anybody see how to answer this. Please do tell.

  • 2
    How do you define "more"?2011-11-10
  • 0
    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.2011-11-10
  • 0
    @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).2011-11-10
  • 3
    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.2011-11-10

3 Answers 3

6

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?"

  • 0
    Doh, of course!2011-11-10
  • 0
    @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**2011-11-10
  • 0
    @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]2011-11-10
  • 0
    @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) http://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}$.2011-11-10
  • 0
    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.2011-11-10
  • 0
    Assuming the existence of at least one nonmeasurable function (which is equivalent to the existence of at least one nonmeasurable subset), your injection from measurable to unmeasurable functions still works and respect the equivalence of equal a.e., so the cardinality of the set of nonmeasurable functions is at least as large as that of measurable ones. As George Lowther notes, the latter has cardinality $\mathbb{c}$, so it's a question of whether there are more nonmeasurable functions than that or not...2011-11-11
2

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.

  • 0
    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" :-)2011-11-10
  • 0
    @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.2011-11-10
  • 0
    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.2011-11-10
  • 0
    @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).2011-11-10
  • 0
    @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.2011-11-10
  • 0
    @Asaf: Sorry, just a typo, fixed now. Without choice you should represent each set in terms of a tree structure (or something similar) describing how it is built up from the underlying sets generating the sigma algebra. Otherwise you would have difficulty developing any measure theory. Fremlin describes this in one of the volumes of his book "Measure Theory".2011-11-10
  • 0
    @Asaf: $\Delta^1_1$ of course. Is there a mathematical reason for taking the other definition in the absence of choice, where it cannot be proved to have any strength?2011-11-10
  • 0
    @Carl: I am not sure what you mean by $\Delta^1_1$, is this boldface or lightface? What is the "other definition"?2011-11-10
  • 0
    @George: If it is nearly impossible to develop other things without the axiom of choice, why should measure theory be any different? :-)2011-11-10
  • 0
    For what it's worth, the characteristic function of any subset of the Cantor middle thirds set, considered as a function from $[0,1]$ to $\mathbb R,$ is Riemann integrable, so there are also $2^{\mathfrak{c}}$ many Riemann integrable functions on $[0,1].$ **comment continues**2011-11-10
  • 0
    **continuation of previous comment** This collection was incorrectly claimed by Cantor [Math. Annalen 21 (1883), p. 590] to have cardinality $\mathfrak{c}.$ (Cantor actually gives $\aleph_{1},$ but the full wording suggests he may have been identifying $\mathfrak{c}$ with $\aleph_{1}.$) The correct cardinality of $2^{\mathfrak{c}}$ was proved by Philip E. B. Jourdain around 1903 [Messenger of Mathematics 33 (1903-04), 78-79].2011-11-10
  • 0
    @Asaf: Good to know I don't need AC; but I'd been burned enough times to include the disclaimer...2011-11-11
  • 0
    @Arturo: You are supposedly using some AC for $\aleph_0\cdot\frak c=\frak c$. However this step can be skipped by using $\mathbb R$ instead, since $\mathbb R\times\mathbb N$ is still continuum. I would guess an even better claim would hold, that if $\frak k\cdot\frak k=\frak k$ then $2^\frak k=\frak k^\frak k$.2011-11-11
0

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!

  • 0
    Sure, given the right axiom system, all $f:\mathbb R \to \mathbb R$ are continuous.2011-11-10
  • 0
    @Thomas: Do you have a reference to that?2011-11-10
  • 0
    @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...2011-11-10
  • 1
    @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.2011-11-10
  • 0
    @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. :-)2011-11-10
  • 0
    And sorry, I haven't found a link yet.2011-11-10
  • 0
    @Thomas: I was thinking that you were talking about ZF-like theory, but if you think about constructivism, I am certain I can find my way to D. Zeilberger's page and read about it if I wish to. I guess I was just expecting a whole other framework in which "all functions are continuous"...2011-11-10
  • 0
    For example if you said, $f(x)=0$ if $x<0$ and $f(x)=1$ if $x\geq 0$, then I could find a computable sequence of rationals such that it is undecidable whether the limit is $<0$ or $\geq 0$. So you would not, in fact, have fully defined $f(x)$ for all real $x$. At least, not in an effective way.2011-11-10