Challenge Yet another counterexample challenge

[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 \Rightarrows 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&#039;) - f(x&#039;&#039;)| \leq |f(x&#039;) - f(x)| + |f(x) + f(x&#039;&#039;)| &lt; \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