“Code golf” is the practice of trying to solve a specific problem or implement a specific algorithm in the smallest possible number of characters of a given programming language. A related concept is exploring what can be accomplished with a tweet-length program (for example see here), though “tweet-length” can be a moving target. In the spirit of code golf, I propose the following “function golf” challenge.
What is the simplest function (defined on the real numbers) that is continuous everywhere except on a given subset of the reals? It is not always possible to find such a function - there are subsets of the reals which cannot be represented as the set of discontinuities of a function. So I will restrict to subsets of the reals that are open or closed.
Here “simplest” is not defined in any formal way - feel free to define it as you wish. In general, I consider a function expressed in fewer characters to be simpler than a function expressed in more characters, but I don’t want to unnecessarily sacrifice clarity on the altar of brevity.
More formally, the desired function is \(f: \mathbb{R} \to \mathbb{R}\) such that when given any open or closed set \(A \subseteq \mathbb{R}\), \(f(x)\) is continuous if \(x\notin A\) and discontinuous if \(x \in A\).
I’ll use the notation invented by Iverson and popularized by Knuth: a statement in square brackets is equal to 1 if the statement is true, and 0 if the statement is false. Like Knuth, I will make this “very strongly zero,” so that if a statement \(S\) is false, \([S] \times (\text{expression})\) is 0, even if \((\text{expression})\) is undefined when \(S\) is false. A brief explanation of other notation used is included at the end of this post.
Here is my proposal for the desired function (which I’m certain is far from optimal):
\[ \boxed{ f(x) = [x \in A] \big( [A \text{ is open}]\, [x \in \mathbb{Q}]\, d(x, A^c) + [A \text{ is closed}]\, (1 + [x \in \mathbb{Q}]) \big)} \]
It fits on one line, but does it work? Before I give a proof, I’ll note that it
seems as if there should be a version of \(f\) that is written in similar
notation but is much shorter - like there
is some duality that I am not quite exploiting properly. Please let me know if
you find a shorter and/or simpler version and I’ll post it on my blog (with
credit to you of course). My email is ab@gmail.com, where a is
my first name in lowercase, and b is my last name in lowercase.
Here is a proof, split into three cases: \(A\) is open and not closed, \(A\) is closed and not open, and \(A\) is both open and closed. The only two subsets of \(\mathbb{R}\) that satisfy the last condition are the empty set (\(\emptyset\)) and \(\mathbb{R}\) itself, which implies that in the first two cases \(A\) is nonempty.
Case 1: \(A\) is open and not closed, so \([A \text{ is open}] = 1\) and \([A \text{ is closed}] = 0\). The function then reduces to \[ f(x) = [x \in A]\, [x \in \mathbb{Q}]\, d(x, A^c). \] If \(x \in A\), \(d(x, A^c) \geq \epsilon\) for some \(\epsilon > 0\), since \(A\) is open. Again since \(A\) is open, we can construct a sequence of rationals and a sequence of irrationals, both in \(A\) and converging to \(x\). Applying the function to one of the two sequences will result in a sequence that does not converge to \(f(x)\), so \(f(x)\) is discontinuous at all \(x \in A\).
For \(x \in A^c\), \(f(x) = 0\), and applying the function \(f\) to any sequence converging to \(x\) results in a sequence that converges to 0 (if the sequence is in \(A\) and irrational, it is driven to zero by the \(d(x, A^c)\) term). So \(f(x)\) is continuous for all \(x \in A^c\).
Thus \(D_f = A\) as desired.
Case 2: \(A\) is closed and not open, so \([A \text{ is open}] = 0\) and \([A \text{ is closed}] = 1\). The function then reduces to \[ f(x) = [x \in A] (1 + [x \in \mathbb{Q}]). \] If \(x \in A^c\), \(f(x) = 0\), and since \(A^c\) is open, there exists an \(\epsilon\)-neighborhood \(V_\epsilon(x) \subseteq A^c\). Since \(f(x) = 0\) everywhere in this \(\epsilon\)-neighborhood, \(f(x)\) is continuous at all points \(x \in A^c\).
If \(x \in A\), \(x\) is either in \(A^\circ\) (the interior of \(A\)) or in \(A\setminus A^\circ\) (the boundary of \(A\)). If \(x \in A^\circ\), \(f(x)\) is discontinuous by a similar argument to the one given in Case 1 (since \(A^\circ\) is open). If \(x \in \partial A\), every \(\epsilon\)-neighborhood of \(x\) intersects \(A^c\), so we can construct a sequence \((x_n)\) in \(A^c\) converging to \(x\). Then \(f (x_n) \to 0 \neq f(x) = (1 \text{ or } 2)\). So \(f(x)\) is discontinuous for \(x \in \partial A\).
Since \(A = \partial A \cup A^\circ\), we have \(D_f = A\) as desired.
Case 3: \(A\) is both open and closed. This case can be split into two subcases: \(A = \emptyset\) and \(A = \mathbb{R}\). For both subcases, \([A \text{ is open}] = 1\) and \([A \text{ is closed}] = 1\). If \(A = \emptyset\), \([x \in A] = 0\), so \(f(x) = 0\) everywhere, which is continuous everywhere, so \(D_f = \emptyset = A\).
If \(A = \mathbb{R}\), \([x \in A] = 1\), and \(A^c = \emptyset\), so \(f(x) = 1 + [x \in \mathbb{Q}] (1 + d(x, \emptyset))\). Here is a point where I must engage in a bit of notational overload. The distance \(d(x, \emptyset)\) is technically undefined, and while an argument can be made that it should be \(+\infty\) (which is not a real number), I will arbitrarily define it to be 0. Or, using the Iversonian notation, \(d(x, A) = [A \neq \emptyset] \inf\{|x - a| : a \in A\}\). Then \(f(x) = 1 + [x \in \mathbb{Q}]\), which is 2 on the rationals and 1 on the irrationals, so is discontinuous everywhere. So \(D_f = \mathbb{R} = A\) as desired.
Notation (all pretty standard):
\(\mathbb{Q}\) denotes the rationals. The complement of a set is defined as \(A^c = \{x \in \mathbb{R} : x \notin A\}\). \(D_f \subseteq \mathbb{R}\) is the set of points where a function \(f: \mathbb{R} \to \mathbb{R}\) is discontinuous. The distance between a real number \(x\) and a subset of the reals \(A\) is defined as \(d(x, A) = \inf\{ |x - a| : a \in A\}\). The interior of a set \(A\) is defined as \(A^\circ = \{x \in A : \text{ there exists } V_\epsilon(x) \subseteq A\}\). The boundary of a set \(A\) is defined as the closure of \(A\) minus the interior of \(A\): \(\partial A = \overline{A}\setminus A^\circ\). The \(\epsilon\)-neighborhood of a point \(a\) is defined as \(V_\epsilon (a) = \{ x \in \mathbb{R} : |x - a| < \epsilon \}\).
