Yet another counterexample challenge

[micromass]

Ba function with an uncountable discontinuity set cannot be Riemann integrable.

Why not?

 

[andrewkirk]

Why not?

It's not since its set of discontinuity points is uncountable.

(referring to fresh_42's suggestion in the preceding post that the indicator function of the rationals was Riemann integrable.)

 

[micromass]

(referring to fresh_42's suggestion in the preceding post that the indicator function of the rationals was Riemann integrable.)

Ah. Sorry, my post 59 is incorrect. What I should have said is that it's not Riemann integrable since its discontinuity set does not have measure zero. Sorry.

 

[andrewkirk]

Ah well, I shall have to think about it some more. It's late here and no doubt thinking about it will soon send me to sleep. Good night all.

 

[andrewkirk]

Good morning. I thought I'd just set out where I thought number 10 is up to, to help my own clarity of mind.

To be a counterexample, a set $S\subset[0,1]$ must have the following properties:

1. Measure of $S$ is zero. I presume here we mean Lebesgue measure (is that correct, Micromass?). If we were allowed to consider other measures then new avenues of inquiry might open up.
2. $S$ is uncountable [I'll explain why below].
   
3. One of these two must hold:
   1. There is no function from $[0,1]$ to $\mathbb R$ whose discontinuity set is $S$; or
   2. There may be such functions, but they are are not Riemann integrable.

$S=\mathbb Q$ fails on 2, and the Cantor Set fails 3.2 (as the Cantor Set's indicator function turns out to be Riemann integrable)

Here's why 2 is necessary. It is known that any function with a countable discontinuity set is R-integrable, and we can construct such a function as follows (a generalisation of my above proof for $\mathbb Q$):

For $S$ countable, with bijection $g:S\to\mathbb N$, define $f$ by $f(x)=x+\frac1{g(x)}$ for $x\in S$ and $f(x)$ otherwise. Then $f$ is discontinuous at $x\in S$ because $f(x)= x+\frac1{g(x)}\not= f(x)=\lim_{\substack{y\to x\\y\notin S}}f(y)$. But $f$ is continuous at $x\in[0,1]-S$ because for any $\epsilon>0$ we can choose $\delta>0$ such that (1) $\delta<\frac\epsilon 2$ and (2) for all $y=g^{-1}(n)\in S\cap (x-\delta,x+\delta)$ we have $n>\frac2\epsilon$, in which case we have

$$|f(y)-f(x)|\leq |f(y)-y|+|y-f(x)|=\frac1n+|y-x|< \frac\epsilon2+\frac\epsilon2=\epsilon$$

Currently, I think 2.1 may be more promising, if only because it has been less explored than 3.2 thus far in the thread.

The other possibility is that there is no counter-example. I only just noticed the clever rider in the OP that one of the ten propositions is actually true, which adds spice to the exercise. We could try to attack that by trying to prove the proposition, by making a construction of a suitable function, given a set $S$. The strong link between measure and integration would be the theme.

 

[micromass]

I presume here we mean Lebesgue measure (is that correct, Micromass?).

Correct.

Clever analysis of the situation in your post.

 

[andrewkirk]

Theorem
The indicator function of a subset of [0,1] with Lebesgue measure zero is Riemann integrable.

Proof. [Which contains an error, the identification of which is left as an exercise for anybody that prefers this sort of activity to Sudoku]

Let $S\in\mathbb R$ have Lebesgue measure zero and let $f$ be its indicator function. Then for any $\epsilon>0$ there exists a sequence of open real intervals $I_1,..,I_n$ that cover $S$ and $\sum_k |I_k|<\frac\epsilon2$. We can take closures of the intervals and remove overlaps to make this a sequence of intervals $J_1,...J_m$ (with $m\leq n$) such that the upper bound of each $J_k$ is less than or equal to the lower bound of $J_{k+1}$.

Now construct the following set of intervals $D_1...D_r$. First define $h=\frac\epsilon{4(m+1)}$. For each connected component $(a,b)$ of $[0,1]-\bigcup_k J_k$ define $l=\min(b,a+h)$ and $h=\max(l,b-h)$. This will be one or two points and so will divide $[a,b]$ into one, two or three non-trivial components. Where there are three non-trivial components, call the central component 'insulated' and the other two 'buffers'. Include the closures of the non-trivial components in the set of $D_k$.

Call the set of intervals obtained from insulated components $F_1,...,F_u$ (with $u\leq m+1$). These intervals are all entirely contained within $[0,1]-S$.

Then the sets of $J_k$ and $D_k$ together determine a partition $P$ of [0,1]. We tag this partition by selecting the lower bound of each interval as the tagged point.

Since each insulated interval $F_k$ is interior to $[0,1]-S$, the value of of $f(x)$ is zero everywhere on the interval, and remains so at all tagged points therein for any refinement of $P$. So for any refinement, the Riemann Sum for $f$ cannot exceed the measure of all the $J_k$ and the buffers. There are at most $2(m+1)$ buffers and the measure of each is no larger than $h$. So the sum of the lengths of the buffers is less than or equal to $2(m+1)h=2(m+1)\frac\epsilon{4(m+1)}=\frac\epsilon2$. And the sum of the lengths of all the $J_k$ is less than or equal to that for all the $I_k$, which is less than $\frac\epsilon2$.

Hence, since the indicator function is bounded above at 1, the Riemann Sum of any refinement of $P$ is less than $1\cdot\frac\epsilon2+1\cdot\frac\epsilon2=\epsilon$.

Hence $f$ is Riemann-integrable. $\square$

What's next:

So, unless I have made a mistake, this knocks out the possibility of 3.2. So if there is a counterexample to number 10, it must be an uncountable set of measure zero that is not the discontinuity set of any function.

We can stop thinking about Riemann Integrability.
EDIT: Ha Ha, no we can't, as the next post demonstrates.

 

[micromass]

Theorem
The indicator function of a subset of [0,1] with Lebesgue measure zero is Riemann integrable.

$\mathbb{Q}\cap [0,1]$ is a counterexample.

 

[andrewkirk]

Hmm. I see that I assumed the sequence of intervals $I_k$ is finite. But of course it may be infinite, in which case the proof does not work, as $\mathbb Q$ demonstrates.

 

[mfb]

I would be surprised if 3 has counterexample.

(10):
A counterexample set has to be uncountable, as discussed before.
If the set is dense nowhere, we can use the indicator function and integrate it. I would expect this to work for all sets. Therefore, our set has to be dense somewhere.

 

[fresh_42]

By the way: I like to say thank you to @micromass for your patience and constructive discussions. In fact I like to think that a discussion on errors is at least as valuable as a perfect solution for it shows and reminds me (and hopefully one or another reader as well) how easyly pitfalls can be overlooked.

 

[andrewkirk]

I believe I may have a proof that 3 is correct, in which case there is no counter-example. Here it is. I wonder if it has any fewer errors than my last attempted proof.

Theorem

If the sequence $\sum_{n=0}^\infty a_n$ is absolutely convergent with limit $L$, and ${\pi:\mathbb N\times\mathbb N\to\mathbb N}$ is a bijection, then
$L'\equiv\sum_{k=0}^\infty\sum_{l=0}^\infty a_{\pi(k,l)}=L$.

Proof (attempted)

Given $\epsilon>0$, use absolute convergence to choose $N\in\mathbb N$ such that ${\sum_{n=N+1}^\infty|a_n|<\frac\epsilon3}$. Then set

$$M\equiv\max_{k\in\{1,2,...,N\}}\left(\pi^{-1}(k)\right)_1$$

where the 1 subscript indicates the first component of an element of $\mathbb N\times\mathbb N$.

Then
\begin{align}
|L'-L|&=\left|\sum_{k=0}^\infty\sum_{l=0}^\infty a_{\pi(k,l)}-\sum_{n=0}^\infty a_n\right|\\
&=\left|\sum_{k=0}^M\sum_{l=0}^\infty a_{\pi(k,l)}+
\sum_{k=M+1}^\infty\sum_{l=0}^\infty a_{\pi(k,l)}
-\sum_{n=0}^N a_n
-\sum_{n=N+1}^\infty a_n\right|\\
&\leq
\left|\sum_{k=0}^M\sum_{l=0}^\infty a_{\pi(k,l)}-\sum_{n=0}^N a_n\right|+
\left|\sum_{k=M+1}^\infty\sum_{l=0}^\infty a_{\pi(k,l)}\right|+
\left|\sum_{n=N+1}^\infty a_n\right|\\
&\leq
\left|\sum_{k=0}^M\sum_{l=0}^\infty a_{\pi(k,l)}-\sum_{n=0}^N a_n\right|+
\sum_{k=M+1}^\infty\sum_{l=0}^\infty \left|a_{\pi(k,l)}\right|+
\sum_{n=N+1}^\infty \left|a_n\right|\\
&<
\left|\sum_{k=0}^M\sum_{l=0}^\infty a_{\pi(k,l)}-\sum_{n=0}^N a_n\right|+
\sum_{k=M+1}^\infty\sum_{l=0}^\infty \left|a_{\pi(k,l)}\right|+
\frac\epsilon3\\
&\leq
\left|\sum_{k=0}^M\sum_{l=0}^\infty a_{\pi(k,l)}-\sum_{n=0}^N a_n\right|+
\sum_{n=N+1}^\infty\left|a_n\right|+
\frac\epsilon3\\
&\leq
\left|\sum_{k=0}^M\sum_{l=0}^\infty a_{\pi(k,l)}-\sum_{n=0}^N a_n\right|+
\frac\epsilon3+
\frac\epsilon3\\
&=
\left|\sum_{k=0}^M\sum_{\substack{l=0\\\pi(k,l)>N}}^\infty a_{\pi(k,l)}\right|+
\frac{2\epsilon}3\\
&\leq
\sum_{k=0}^M\sum_{\substack{l=0\\\pi(k,l)>N}}^\infty \left|a_{\pi(k,l)}\right|+
\frac{2\epsilon}3\\
&\leq
\sum_{n=N+1}^\infty\left|a_n\right|+
\frac{2\epsilon}3\\
&<
\frac{\epsilon}3+
\frac{2\epsilon}3\\
&=\epsilon
\end{align}

So for any $\epsilon>0$, we have $|L'-L|<\epsilon$, whence $L'=L$. $\square$

 

[micromass]

How do you show

$$\sum_{k=M+1}^\infty\sum_{l=0}^\infty \left|a_{\pi(k,l)}\right| \leq \sum_{n=N+1}^\infty\left|a_n\right|$$

Don't you assume something like the theorem but for positive numbers here?

 

[andrewkirk]

I'm not sure, but what's needed in the context is to show that the LHS is less than or equal to $\frac\epsilon3$. I think we can do that as follows:

But first, we might need more room, so let's replace all the $\frac\epsilon3$ in the proof by $\frac\epsilon{12}$, except for the one you quoted. I'll edit that in shortly in the attempted proof post, if this works.

We want to prove that

$$\sum_{k=M+1}^\infty\sum_{l=0}^\infty \left|a_{\pi(k,l)}\right| \leq \frac\epsilon3$$

Since the limit of the outer sum exists, we can find $K\in\mathbb N$, with $K\geq M$, such that
$$\sum_{k=K+1}^\infty\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|
<\frac\epsilon{12}$$
For each $k$ between$M+1$ and $K$ inclusive we can then find $T'(k)\in\mathbb N$ such that $\sum_{l=T'(k)+1}^\infty \left|a_{\pi(k,l)}\right|<\frac \epsilon{12(K+1)}$. Set $T\equiv\max_{k\in\{0,1,...,K\}}T_k$.

Then
\begin{align*}
\sum_{k=M+1}^K\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|-
\sum_{k=M+1}^K\sum_{l=0}^T\left|a_{\pi(k,l)}\right|
&=\sum_{k=M+1}^K\left(\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|-
\sum_{l=0}^T\left|a_{\pi(k,l)}\right|\right)\\
&=\sum_{k=M+1}^K\left(\sum_{l=T+1}^\infty\left|a_{\pi(k,l)}\right|\right)\\
&\leq\sum_{k=M+1}^K\sum_{l=T'(k)+1}^\infty\left|a_{\pi(k,l)}\right|\\
&<\sum_{k=M+1}^K\frac \epsilon{12(K+1)}\leq\frac\epsilon{12}\\
\end{align*}So
\begin{align*}
\sum_{k=M+1}^\infty\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|&=
\sum_{k=M+1}^K\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|+
\sum_{k=K+1}^\infty\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|\\
&<\sum_{k=M+1}^K\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|+
\frac\epsilon{12}\\
&\leq\left( \sum_{k=M+1}^K\sum_{l=0}^T\left|a_{\pi(k,l)}\right|+\frac\epsilon{12}\right)
+\frac\epsilon{12}\\
&=\sum_{k=M+1}^K\sum_{l=0}^T\left|a_{\pi(k,l)}\right|+\frac\epsilon{6}\\
\end{align*}

The first term is a sum of terms that form a finite subset of $a_{N+1},a_{N+2},...$ and hence cannot exceed $\sum_{n=N+1}^\infty|a_n|=\frac\epsilon{12}$.

Hence we have
$$\sum_{k=M+1}^\infty\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|<\frac\epsilon{12}+\frac\epsilon{6}=\frac\epsilon{4}<\frac\epsilon{3}$$

 

[micromass]

Neat! My only remark is that for this:

Since the limit of the outer sum exists, we can find $K\in\mathbb N$, with $K\geq M$, such that
$$\sum_{k=K+1}^\infty\sum_{l=0}^\infty\left|a_{\pi(k,l)}\right|
<\frac\epsilon{12}$$

you need a proof of convergence of the series. Can you provide that too?

 

[andrewkirk]

I think so. I've re-written the whole thing to make it a bit cleaner and integrate the last two posts. The proof of convergence of the absolute double sum is done at the start. I hope it makes sense now.

Theorem

If the sequence $\sum_{n=1}^\infty a_n$ is absolutely convergent with limit $L$, and ${\pi:\mathbb N\times\mathbb N\to\mathbb N}$ is a bijection, then $L'\equiv\sum_{k=1}^\infty\sum_{l=1}^\infty a_{\pi(k,l)}$ is a convergent sum, which is equal to $L$.

Proof

First we prove that $\sum_{k=1}^\infty\sum_{l=1}^\infty|a_{\pi(k,l)}|$ exists.
If it does not exist then either one or more of the inner sums is divergent, or the inner sums converge but the outer sum diverges.

First assume that the inner sum for $k$ diverges. Then for any $R>0$ there exists $G\in\mathbb N$ such that $\sum_{l=1}^G|a_{\pi(k,l)}|>R$. Then $\sum_{n=1}^N|a_n|>R$ where
$$N\equiv\max_{l\in\{1,...,G\}}\pi(k,l)$$
which contradicts the absolute convergence of $\sum_{n=0}^\infty a_n$. So no inner sum can diverge.

Next assume the outer sum diverges. Then for any $R>0$ we can find $G\in\mathbb N$ such that

$$\sum_{k=1}^G\sum_{l=1}^\infty|a_{\pi(k,l)}|>R+1$$

Since there is a finite number of inner sums and they all converge, we can find $F\in\mathbb N$ such that for all $l\in\{1,...,F\}$ we have $\sum_{l=F+1}^\infty|a_{\pi(k,l)}|<\frac1G$.

Then we have

$$\sum_{k=1}^G\sum_{l=1}^F|a_{\pi(k,l)}|
=\sum_{k=1}^G\sum_{l=1}^\infty|a_{\pi(k,l)}|-
\sum_{k=1}^G\sum_{l=F+1}^\infty|a_{\pi(k,l)}|
>R+1+G\cdot\frac1G=R$$

Then $\sum_{n=1}^N|a_n|>R$ where
$$N\equiv\max_{\substack{k\in\{1,...,G\}\\l\in\{1,...,F\}}}\pi(k,l)$$
which contradicts the absolute convergence of $\sum_{n=0}^\infty a_n$. So the outer sum cannot diverge either. Hence the double sum of absolute values converges.

We see then that the sum $\sum_{k=1}^\infty\sum_{l=1}^\infty a_{\pi(k,l)}$ must also converge to a limit $L'$ because sums of absolute values are no less than sums of signed numbers, so if a signed sum diverges then the sum formed by applying the same summation operators to the absolute values of the summands must also diverge.

Now we try to prove the result.

First, given $\epsilon>0$, we choose $N\in\mathbb N$ such that $\sum_{n=N+1}^\infty|a_n|<\frac\epsilon9$, which we can do by the absolute convergence of that series.

Next we set

$$H\equiv\max_{k\in\{1,2,...,N\}}\left(\pi^{-1}(k)\right)_1$$

where the 1 subscript indicates the first component of an element of $\mathbb N\times\mathbb N$.

Next we choose $G\in\mathbb N$ such that $\sum_{k=G+1}^\infty\sum_{l=1}^\infty|a_{\pi(k,l)}|<\frac\epsilon9$, which we can do by the convergence of the double sum, proven above.

Then define $M\equiv\max(G,H)$.

Next, for each $k\in\{1,...,M\}$ we choose $T'(k)$ such that ${\sum_{l=T'(k)+1}^\infty|a_{\pi(k,l)}|<\frac\epsilon{9M}}$, which again we can do by convergence of the double sum above. We then set $T\equiv\max_{k\in\{1,...,M\}}T'(k)$.

Armed with these definitions, we proceed as follows:

\begin{align}
|L'-L|&\equiv\left|\sum_{k=1}^\infty\sum_{l=1}^\infty a_{\pi(k,l)}-\sum_{n=1}^\infty a_n\right|\\
&=\left|\left(\sum_{k=1}^M\sum_{l=1}^T
+\sum_{k=1}^M\sum_{l=T+1}^\infty
+\sum_{k=M+1}^\infty\sum_{l=1}^\infty
\right)a_{\pi(k,l)}
-\left(\sum_{n=1}^N+\sum_{n=N+1}^\infty\right) a_n\right|\\
&\leq\left|\sum_{k=1}^M\sum_{l=1}^T a_{\pi(k,l)}-\sum_{n=1}^N a_n\right|
+\left|\sum_{k=1}^M\sum_{l=T+1}^\infty a_{\pi(k,l)}\right|
+\left|\sum_{k=M+1}^\infty\sum_{l=1}^\infty a_{\pi(k,l)}\right|
+\left|\sum_{n=N+1}^\infty a_n\right|\\
&<\left|\sum_{k=1}^M\sum_{\substack{l=1\\\pi(k,l)>n}}^T a_{\pi(k,l)}\right|
+\sum_{k=1}^M\sum_{l=T+1}^\infty \left|a_{\pi(k,l)}\right|
+\sum_{k=M+1}^\infty\sum_{l=1}^\infty \left|a_{\pi(k,l)}\right|
+\sum_{n=N+1}^\infty \left|a_n\right|\\
&<\sum_{k=1}^M\sum_{\substack{l=1\\\pi(k,l)>N}}^T \left|a_{\pi(k,l)}\right|
+\sum_{k=1}^M\sum_{l=T'(k)+1}^\infty \left|a_{\pi(k,l)}\right|
+\sum_{k=G+1}^\infty\sum_{l=1}^\infty \left|a_{\pi(k,l)}\right|
+\frac\epsilon9\\
&<\sum_{n=N+1}^\infty|a_n|
+\sum_{k=1}^\infty\frac\epsilon{9M}+\frac\epsilon9
+\frac\epsilon9\\
&=\frac{\epsilon}9
+\frac{\epsilon}3=\frac{4\epsilon}9<\epsilon\\
\end{align}

Since $|L'-L|<\epsilon$ for all positive $\epsilon$, it must be zero.

Phew!

 

[micromass]

I think that's ok. So only 10 remains.

I'll give another proof though that some people might find insightful. The idea is that if $(\Omega,\mathcal{B},\mu)$ is a measure space and $\Omega=\bigcup_{n} S_n$ is a partition of measurable sets, then it is not difficult to prove that for an integrable function $f:\Omega\rightarrow \mathbb{R}$ holds
$$\int_\Omega fd\mu = \sum_n \int_{S_n} fd\mu$$
Now, the result follows easily if we take $\mu$ to be the counting measure on $\mathbb{N}$. In this case, $f$ becomes a sequence which is integrable iff the series converges absolutely and whose integral is a sum.

 

[andrewkirk]

For 10, just wanted to check something else. I presume Vitali sets are ruled out, since they are not Lebesgue measurable. A given Vitali set must have a Lebesgue Outer Measure (since any subset of $\mathbb R$ does) and, for all I know, it could be zero. And I imagine it may be straightforward to show that any function whose discontinuity set is a Vitali set is not Riemann integrable. But a Vitali set is not Lebesgue measurable.

I mention this because Vitali sets are the only uncountable sets I know of, other than the Cantor set, that are not known (by me) to have positive Lebesgue Outer Measure. They also have the advantage of being dense and, as @mfb pointed, out a counterexample to 10 has to be dense somewhere. In fact, I think it will have to be dense at an infinite number of points (ie have an infinite set of limit points), and maybe even at an uncountably infinite number of points.

I think the solution to this problem, when it turns up, will be a most intriguing set.

 

[micromass]

For 10, just wanted to check something else. I presume Vitali sets are ruled out, since they are not Lebesgue measurable. A given Vitali set must have a Lebesgue Outer Measure (since any subset of $\mathbb R$ does) and, for all I know, it could be zero. And I imagine it may be straightforward to show that any function whose discontinuity set is a Vitali set is not Riemann integrable. But a Vitali set is not Lebesgue measurable.

I mention this because Vitali sets are the only uncountable sets I know of, other than the Cantor set, that are not known (by me) to have positive Lebesgue Outer Measure. They also have the advantage of being dense and, as @mfb pointed, out a counterexample to 10 has to be dense somewhere. In fact, I think it will have to be dense at an infinite number of points (ie have an infinite set of limit points), and maybe even at an uncountably infinite number of points.

I think the solution to this problem, when it turns up, will be a most intriguing set.

Right, the set in question must have an actual measure. The Vitali set does not have a measure.

Also, the Vitali sets have positive outer measure. If you construct a Vitali set inside $[0,1]$, then you can construct one which has outer measure a number inside $(0,1]$. Note that if you show something has outer measure $0$, then it actually has measure zero.

 

[micromass]

OK, let me perhaps give a series of hints to prove 10:

1) Prove that the set of discontinuity points of any function is an $F_\sigma$ set. This means that it is the countable union of closed sets.
2) Find a set of measure zero that is not an $F_\sigma$ set. This can be done in two ways (each yielding their own counterexample), by either noticing that $F_\sigma$ sets are always Borel sets, or by proving that $F_\sigma$ sets of measure zero are necessarily of first category. https://en.wikipedia.org/wiki/Meagre_set
3) So it suffices to find a measurable set that is not Borel. Or it suffices to find a set of measure zero that is not of first category.

 

[andrewkirk]

1) Prove that the set of discontinuity points of any function is an $F_\sigma$ set. This means that it is the countable union of closed sets.

What about the indicator function of the Cantor set? Its discontinuity set is the Cantor set, because the set is nowhere dense.
It can be written as a countable intersection of closed sets by applying de Morgan to the way the set is constructed.

But since the set is an uncountable union of isolated points I don't think it can be a countable union of closed sets. If any of those closed sets were non-singletons, the resulting set would be dense somewhere, which the Cantor Set is not. And if the sets are all singletons then the resulting set would be countable, which the Cantor Set isn't.

Have I missed something?

 

[micromass]

What about the indicator function of the Cantor set? Its discontinuity set is the Cantor set, because the set is nowhere dense.
It can be written as a countable intersection of closed sets by applying de Morgan to the way the set is constructed.

But since the set is an uncountable union of isolated points I don't think it can be a countable union of closed sets. If any of those closed sets were non-singletons, the resulting set would be dense somewhere, which the Cantor Set is not. And if the sets are all singletons then the resulting set would be countable, which the Cantor Set isn't.

Have I missed something?

The Cantor set is closed, because any intersection of closed sets is closed.

Any closed set is of course obviously the countable union of closed sets.

 

[andrewkirk]

For some reason my brain read 'countable union of closed intervals' where it said 'countable union of closed sets'

 

[andrewkirk]

I can't find a counterexample to 10, but I think can prove that 10 is false, using MicroMass's hint and a useful post I saw on Stack Exchange that used a cardinality argument to show that non-Borel sets must exist. Here goes.

The Cantor set is uncountable and, since it has measure zero, it is measurable and so are all subsets of it.

Let the cardinality of the Cantor set be $C$ and, because the Cantor set is uncountable, we have $C>\aleph_0$.
Hence the number of subsets of the Cantor Set is $2^C>2^{\aleph_0}$.

I will prove below that the cardinality of the Borel sets does not exceed $2^{\aleph_0}$. Since this is strictly less than $2^C$ there must be subsets of the Cantor set that are not Borel. Since they are subsets of a set of measure zero, they have Lebesgue Outer Measure zero and hence are measurable.

So there are Lebesgue-measurable sets with Lebesgue measure zero that are not Borel and hence are not $F_\sigma$ and hence cannot be the discontinuity set of any function.

Now let's derive that upper bound on the cardinality of the Borel sets.

The collection of Borel sets on $\mathbb R$ is often defined as the sigma algebra containing all real intervals. But it's easy to show that the set of all open intervals with rational endpoints (including $\pm\infty$ as possible endpoints) generates the same sigma algebra, because any interval with an irrational endpoint can be written as a countable intersection or union of intervals with rational endpoints, and a similar approach can construct an interval with a closed endpoint.The set $A'$ of intervals with rational or infinite endpoints is countable. Note that $A'$ includes the empty set as $(0,0)$ and the universal set as $(-\infty,\infty)$. The following set is also countable.

$$A\equiv A'\cup\{\mathbb R-S\ :\ S\in A\}$$

Define $B_1$ as the set of functions from $\mathbb N$ to $A$. Then for each $r\in\mathbb N$ define $B_{r+1}$ as the set of functions from $\mathbb N$ to $B_r$.

Then, for each $r\in\mathbb N$ we define a map $\psi_r$ from $B_r$ to $A$ as follows:

$$\psi_1(b)=\bigcap_{k\in\mathbb N}b(k)$$
$$\psi_{2r}(b)=\bigcup_{k\in\mathbb N}\psi_{2r-1}(b(k))$$
$$\psi_{2r+1}(b)=\bigcap_{k\in\mathbb N}\psi_{2r}(b(k))$$

Then define $\psi:\bigcup_{r\in\mathbb N} B_r\to A$ by $\psi=\bigcup_{r\in\mathbb N}\psi_r$.

It's straightforward to show that $\psi$ is surjective on the Borel sets. The cardinality of dom $\psi$ is

\begin{align*}
\left|\textrm{dom }\psi\right|&\leq\sum_{r\in\mathbb N}\left|\textrm{dom }\psi_r\right|\\
&=\sum_{r\in\mathbb N}\left|B_r\right|\\
\end{align*}

We claim that for all $r\in\mathbb N$ we have $|B_r|\leq2^{\aleph_0}$

First observe that $|B_1|=|A^{\mathbb N}|=\aleph_0{}^{\aleph_0}\leq(2^\aleph_0)^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$

Next, assume it is true for $r\in \{1,...,m\}$. Then

$|B_{m+1}|=|B_m{}^{\mathbb N}|=|B_m|^{|\mathbb N|}\leq (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$.

So by induction, the claim is proven.

It follows that $|\textrm{dom }\psi|\leq\sum_{r\in\mathbb N}|B_r|\leq \sum_{r\in\mathbb N}2^{\aleph_0}\leq 2^{\aleph_0}$.

Since $\psi$ is a surjection, we conclude that the cardinality of the Borel sets does not exceed $2^{\aleph_0}$, as required.

That's it.

It's a little dissatisfying, because we have not been able to point to a counterexample. But at least we have shown that the theorem cannot be true. And we didn't even have to use the Axiom of Choice.

 

[mfb]

Now I am confused. We established that there are functions that are discontinuous exactly at the Cantor set (e. g. the indicator function). It is trivial to construct functions that are discontinuous at a subset of the Cantor set (e. g. the indicator functions). But then it should be a Borel set, and we don't have enough Borel sets for every subset of the Cantor set?

I was thinking in the opposite direction: what if we consider {c+q} where c is in the Cantor set and q is a rational number?

 

[andrewkirk]

Very perplexing @mfb ! I took the statements 1 and 2 in post #90 as given. That is, I assumed that for $S\subset\mathbb R$:

$$(\exists f:\ S=disctyset(f))\Rightarrow (S\in F_\sigma(\mathbb R))\Rightarrow (S\in\mathscr{B}(\mathbb R))$$

where $\mathscr{B}(\mathbb R)$ is the collection of Borel sets on $\mathbb R$.

But as you point out, it seems that the indicator function of any subset $S$ of the Cantor set $C$ will have discontinuity set $S$. If the argument in post #94 is correct, that appears to mean that one or both of the above $\Rightarrow$ symbols cannot hold.

I wonder if I misinterpreted one of the statements in #90.

I like the suggestion in your last para. I think the following function could have $S=\{c+q\ :\ c\in C\wedge q\in\mathbb Q\}$ as discontinuity set:

$f(x)=0$ if $x\not\in S$

otherwise $f(x)=\frac1{n_x}$ where $n_x=\min\{d\in\mathbb N\ |\ \exists c\in C,\exists u\in\mathbb Z\ :\ c+\frac ud=x\}$

The set $S$ is uncountable and everywhere dense. I have a feeling $f$ may still be Riemann-integrable, but would like to explore that. Perhaps it isn't.

 

[micromass]

It is trivial to construct functions that are discontinuous at a subset of the Cantor set (e. g. the indicator functions).

That won't work. For example, take a countable set $S$ whose closure is the Cantor set $C$ (this exist since every closed set is the closure of a countable set by a separability argument in the newest counterexample thread).

Sure enough, if $s\in S$, then $s$ is the limit of a sequence in $S\setminus \{s\}$ and a sequence outside $S$. So the indicator function of $S$ is discontinuous at $s$. But if $x\in C\setminus S$, then by density of $S$, we have that $x$is also the limit of a sequence outside of $S$ and inside of $S$. So the points of discontinuity of the indicator function is larger than $S$.

In fact given any topological space $(X,\mathcal{T})$, we have that the indicator function of a subset $A\subseteq X$ is continuous at $x\in X$ iff $x\notin \partial A$. So the set of discontinuity of an indicator function of $A$ is $\partial A$ which is always closed.

 

[andrewkirk]

Ah, I get it. If we remove points from $C$, those points may remain discontinuity points of the indicator function of the reduced set. Since every point in $C$ is a limit point of both $C$ and not-$C$, that point will be a discontinuity point of the indicator function even if it is taken out of $C$. For instance 0 is in $C$, and the sequences, written in ternary form:

$$0.2,0.02,0.002,0.0002,...$$
and
$$0.11,0.011,0.0011,0.00011,0.000011,...$$
are in $C$ and not-$C$ respectively and both have limit 0. So the set $C-\{0\}$ is not the discontinuity set of its indicator function, because 0 remains a discontinuity point of that indicator function.

Surprising, and intriguing.

Now, I have managed to prove the second of the two $\Rightarrow$s from post #96.

We prove that any countable union of closed sets (ie $F_\sigma$ set) is a Borel set. Since $\mathscr B$ is closed under countable unions, it suffices to prove that any closed set $S$ is Borel. The complement $S^c$ is open and hence every point $x\in S_c$ is interior, meaning it is contained in an open interval that is fully within $S^c$. There is a largest path-connected component of $S^c$ containing $x$ that is the open interval $(a,b)$ where $a=\inf\{y\in\mathbb R\ |\ (y,x]\subseteq S^c\}$ and ${b=\sup\{y\in\mathbb R\ |\ [x,y)\subseteq S^c\}}$. $S^c$ is a disjoint union of such components, of which there can only be a countable number, because every interval will contain a rational number and the rational numbers are countable. So $S^c=\bigcup_{n\in\mathbb N} I_n$ where the $I_n$ are disjoint, open real intervals. Hence

$$S=(S^c)^c=\left(\bigcup_{n\in\mathbb N} I_n\right)^c$$

which, being the complement of a countable union of intervals, is Borel.

It remains to prove that any discontinuity set of a function with domain [0,1] is $F_\sigma$.

 

[micromass]

Anybody still thinking about the final part? That the discontinuity set of any function is $F_\sigma$? If nobody replies, I'll reveal the answer monday and credit andrewkirk for the problem.

 

[fresh_42]

Anybody still thinking about the final part? That the discontinuity set of any function is $F_\sigma$? If nobody replies, I'll reveal the answer monday and credit andrewkirk for the problem.

To those who may try: I suspect Riesz's representation theorem could be helpful.

 

[micromass]

Here's the proof that the set of continuity points is $G_\delta$ (meaning a countable intersection of open sets), which is of course equivalent that the set of continuity points is $F_\sigma$ by complementation.

So let $f:\mathbb{R}\rightarrow \mathbb{R}$ be any function. For $n\in \mathbb{N}$, we let
$$A_n = \left\{x\in \mathbb{R}~\vert~\exists r_{n,x} >0:~\forall x', x''\in B(x, r_{n,x}):~|f(x'') - f(x')| < 1/n\right\}$$
where $B(x,r) = \{a\in \mathbb{R}~\vert~|x-a|<r\}$.

1) First we show that each $A_n$ is open.
If $x\in A_n$, then $B(x, r_{n,x})\subseteq A_n$. And thus $A_n = \bigcup_{x\in A_n} B(x,r_{n,x})$ is the union of open sets and thus open.

2) We show that if $f$ is continuous at $x$, then $x\in A_n$ for each $n$
Indeed, if $f$ is continuous at $x$, then there is some $r_{n,x}>0$ such that for all $x' \in B(x,r_{n,x})$ holds that $|f(x) - f(x')| < \frac{1}{2n}$. And then the triangle inequality implies that for $x',x''\in B(x,r_{n,x})$ holds that
$$|f(x') - f(x'')| \leq |f(x') - f(x)| + |f(x) + f(x'')| < \frac{1}{2n} + \frac{1}{2n} = \frac{1}{n}$$

And thus $x\in A_n$.

3) We show that if $x\in A_n$ for each $n$, then $f$ is continuous at $x$.
Indeed, let $\varepsilon>0$ be arbitrary and take $n$ such that $\frac{1}{n}<\varepsilon$. Since $x\in A_n$, it follows that there is some $r_{n,x}>0$ such that for all $x' \in B(x,r_{n,x})$ holds that $|f(x) - f(x')| <\frac{1}{n}<\varepsilon$. So $f$ is continuous at $x$.

So it holds that the set of continuity points of $f$ is equal to $\bigcap_{n\in \mathbb{N}} A_n$; which is the intersection of open sets, and thus a $G_\delta$.

 

[micromass]

Here is another example of a set of measure $0$ that is not $F_\sigma$ and thus not the discontinuity set of any function.

Let $A_n$ be a Cantor set in $[0,1]$ of measure $\frac{n-1}{n}$. Let $A = \bigcup_n A_n$, then since each $A_n$ is nowhere dense, we have that $A$ is of the first category. On the other hand $\lambda(A) = \lim_{n\rightarrow +\infty}\lambda(A_n) = 1$.

Then $A' = [0,1]\setminus A$ is of the second category and of measure $0$. If it was the countable union of closed sets $F_m$, then each $F_m$ would be closed and of measure $0$, it would then be nowhere dense. This would mean that $A'$ is of the first category, which is not true.

 

[micromass]

Thank you everybody for participating to this thread! If anybody is interested in more counterexamples, get the book by Gelbaum and Olmsted "Counterexamples in analysis"

https://www.amazon.com/dp/0486428753/?tag=pfamazon01-20