10
$\begingroup$

The question is to find the cardinality of the set of all everywhere-discontinous real-valued functions of real variable.

My intuition tells me there are $2^c$ such functions, but I can't seem to find an injection from the set of all functions to the set of everywhere-discontinuous functions.

Any help would be appreciated.

$c$ here denotes the cardinality of continuum (for an example, the cardinality of set of all real numbers).

$\endgroup$
  • 4
    $\begingroup$ With nearly a 1000 points, maybe it's time to learn to make the body of the question self-contained, and not leave the question in the title. Have you ever opened a respectable article which started with "Yeah, so the issue is in the title", or just continued seamlessly from the title? No. Do you know what? Because the title is separate from the body. $\endgroup$ – Asaf Karagila Nov 14 '17 at 10:44
  • $\begingroup$ @AsafKaragila you're right, I'll change it right away $\endgroup$ – windircurse Nov 14 '17 at 15:41
  • $\begingroup$ Could you explicit what $c$ is ? I am not familiar with the notation. $\endgroup$ – Evpok Nov 15 '17 at 12:57
  • $\begingroup$ @Evpok sure, I'll edit it into the OP $\endgroup$ – windircurse Nov 15 '17 at 19:42
  • $\begingroup$ @Evpok: It's a fairly common way to denote the cardinality of the continuum. $\endgroup$ – Asaf Karagila Nov 15 '17 at 19:57
23
$\begingroup$

Your intuition is correct. Here's one way to prove it:

Write $\mathbb{Q}$ as the disjoint union of two dense sets $A, B$ (e.g. take $A$ to be the dyadic rationals and $B=\mathbb{Q}\setminus A$). Then:

Any function $f$ satisfying $f(a)=1$ for $a\in A$, $f(b)=0$ for $b\in B$ is everywhere discontinuous.

So how many functions of this type are there? Well, there's no restriction on the behavior of $f$ on irrational inputs, so we have:

The number of everywhere discontinuous functions is at least the number of functions from the irrationals to the reals.

Now using the fact that the irrationals have cardinality $c$, do you see how to finish the proof?

$\endgroup$
7
$\begingroup$

Given a subset $A$ of $\mathbb{R} \setminus \mathbb{Q}$, I can produce a unique function which is everywhere discontinuous: namely, the function which is $0$ on $\mathbb{Q}$, $1$ on $A$, and $-1$ everywhere else.

Therefore there are at least as many everywhere-discontinuous functions as there are subsets of the continuum-sized $\mathbb{R} \setminus \mathbb{Q}$.

$\endgroup$
7
$\begingroup$

Start with Conway's base 13 function $c $ (whose range on any interval is all of $\mathbb R $), which is everywhere discontinuous, and note that if $f $ only takes values $0$ and $1$, then $c+f $ is again everywhere discontinuous (since its range on any interval is unbounded). Now note that there are $2^\mathfrak c $ such functions $f $: the characteristic functions of subsets of $\mathbb R $. Since this is an upper bound (being the total number of functions from $\mathbb R $ to itself), we are done.

$\endgroup$
  • 2
    $\begingroup$ Once $c$ is given, you can choose an $f:\mathbb R\to\{0,1\}$ such that the range of $c+f$ avoids $(0,1)$, simply by choosing $f(x)=1$ when $c(x)\in(0,1)$ and $0$ otherwise. So "its range on any interval is dense in $\mathbb R$" is not necessarily true. (But $c+f$ is still everywhere discontinuous). $\endgroup$ – Henning Makholm Nov 13 '17 at 22:42
  • $\begingroup$ Ah, sure. Let me rephrase. $\endgroup$ – Andrés E. Caicedo Nov 13 '17 at 23:01
6
$\begingroup$

Here is a completely constructive mapping that is easily proven to have the desired property.

For each function $f : \mathbb{R} \to \mathbb{R}$, let $g(x) = \tanh(f(x)) + \cases{1 & if $x\in\mathbb{Q}$ \\ -1 & otherwise}$ for each $x \in \mathbb{R}$. Then $g : \mathbb{R} \to \mathbb{R}$ and $g$ is everywhere discontinuous.

$\endgroup$
  • $\begingroup$ What does $g$ have to do with $f$? $\endgroup$ – Andrés E. Caicedo Nov 14 '17 at 6:24
  • $\begingroup$ @AndrésE.Caicedo: Sorry. Blur me! See the corrected version! =) $\endgroup$ – user21820 Nov 14 '17 at 6:27
  • $\begingroup$ Is $\tanh$ somehow essential to guarantee that the function is discontinuous? Because I don't otherwise see a need for it, and yet without it there are clearly examples of $f$ that make $g$ continuous. With $\tanh$ in there, whether there are $f$ that make $g$ continuous or not is not immediately clear. $\endgroup$ – Arthur Nov 14 '17 at 12:50
  • $\begingroup$ @Arthur: Yes it is needed. The final term adds $1$ for rational points and subtracts $1$ for irrational points, and $\tanh$ has range $(-1,1)$. I'm sure you can figure it out! $\endgroup$ – user21820 Nov 14 '17 at 12:59
  • $\begingroup$ @user21820 Of course. For some reason I thought $\tanh$ looked more like $\sinh$ and $\tan$ and not like $\arctan$. Small mental lapse there. $\endgroup$ – Arthur Nov 14 '17 at 13:00
4
$\begingroup$

Here's a simple idea. Consider the set $K$ of functions $f$ such that $f=0$ on $\mathbb Q$ and $f\geq1$ on $\mathbb R\setminus \mathbb Q$.

The functions on $K$ are determined by their values on the irrationals, so the cardinality of $K$ agrees with that of the set of all functions $\mathbb R\to \mathbb R$.

$\endgroup$
2
$\begingroup$

Let's take a function $f$.

First we are going to shrink it so that its range is now $[-1,1]$

$g(x)=\dfrac{f(x)}{1+|f(x)|}\quad$ this mapping is bijective ($f=\frac g{1-|g|}$)

On every interval where it is continuous, let add $3$ to this function:

$C=\bigcup\limits_{i\in I}C_i$ where $C_i$ interval and $f$ continuous on $C_i$.

Note that $I$ is at most countably infinite.

$h(x):\begin{cases} g(x)+3 & \forall x\in C\\g(x)&\text{elsewhere}\end{cases}$

So basically, where $f$ is continuous then $h(x)\in[2,4]$ and where $f$ is everywhere discontinuous then $h(x)\in[-1,1]$.

We do not care too much about the bounds of the $C_i$, there are anyway only a countable bunch of them and this ($\mathbb N^\mathbb R$) is negligible in comparison to the cardinal of the set of functions.

Finally on $C$ we can transform continuous strictly positive functions into totally discontinuous ones by multiplying by $\psi(x)=1_{\mathbb Q}-1_{\mathbb R\setminus\mathbb Q}$.

So we keep values at rational points into $[2,4]$ and send values at irrational points to $[-4,-2]$.

For other regions where $f$ is already totally discontinuous we keep it as is with values in $[-1,1]$.

$k(x):\begin{cases} k(x)\psi(x) & \forall x\in C\\k(x)&\text{elsewhere}\end{cases}$

Now $k(x)$ is discontinuous everywhere and by construction the mapping $f\mapsto k$ is injective.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.