Neugebauer’s theorem

December 30, 2014

The problem of characterizing when a given function is a derivative has been studied at least since 1911 when Young published a paper recognizing its relevance:

W. H. Young. A note on the property of being a differential coefficient, Proc. Lond. Math. Soc., 9 (2), (1911), 360–368.

The paper opens with the following comment (Young refers to derivatives as “differential coefficients”):

Recent research has provided us with a set of necessary and sufficient conditions that a function may be an indefinite integral, in the generalised sense, of another function, and the way has thus been opened to important developments. The corresponding, much more difficult, problem of determining necessary and sufficient conditions that a function may be a differential coefficient, has barely been mooted; indeed, though we know a number of necessary conditions, no set even of sufficient conditions has to my knowledge ever been formulated, except that involved in the obvious statement that a continuous function is a differential coefficient.

It is more or less understood nowadays that no completely satisfactory characterization is possible. We know that derivatives are Darboux continuous (that is, they satisfy the intermediate value property), and are Baire one functions (that is, they are the pointwise limit of a sequence of continuous functions). But this is not enough: For instance, any function $f$ such that $f(x)=\sin(1/x)$ for $x\ne 0$, and $f(0)\in[-1,1]$ is Darboux continuous and Baire one, but only the function with $f(0)=0$ is a derivative.

Andrew Bruckner has written excellent surveys on derivatives and the characterization problem. See for instance:

Andrew M. Bruckner and John L. Leonard. Derivatives. Amer. Math. Monthly, 73 (4, part II), (1966), 24–56. MR0197632 (33 #5797).

Andrew M. Bruckner. Differentiation of real functions. Second edition. CRM Monograph Series, 5. American Mathematical Society, Providence, RI, 1994. xii+195 pp. ISBN: 0-8218-6990-6. MR1274044 (94m:26001).

Andrew M. Bruckner. The problem of characterizing derivatives revisited. Real Anal. Exchange, 21 (1),  (1995/96), 112–133. MR1377522 (97g:26004).

Here I want to discuss briefly a characterization obtained by Neugebauer, see

Christoph Johannes Neugebauer. Darboux functions of Baire class one and derivatives. Proc. Amer. Math. Soc., 13 (6), (1962), 838–843. MR0143850 (26 #1400).

For concreteness, I will restrict discussion to functions $f:[0,1]\to\mathbb R$, although this makes no real difference. Whenever an interval is mentioned, it is understood to be nondegenerate. For any closed subinterval $I\subseteq [0,1]$, we write $I^\circ$ for its interior, and $\mathrm{lh}(I)$ for its length. Given a point $x\in[0,1]$, we write $I\to x$ to indicate that $\mathrm{lh}(I)\to 0$ and $x\in I$.

Theorem (Neugebauer). A function $f:[0,1]\to\mathbb R$ is a derivative iff to each closed subinterval $I$ of ${}[0,1]$ we can associate a point $x_I\in I^\circ$ in such a way that the following hold:

1. For all $x\in[0,1]$, if $I\to x$, then $f(x_I)\to f(x)$, and

2. For all  closed subintervals $I,I_1,I_2$ of ${}[0,1]$, if $I=I_1\cup I_2$ and ${I_1}^\circ\cap {I_2}^\circ=\emptyset$, then $\mathrm{lh}(I)f(x_I)=\mathrm{lh}(I_1)f(x_{I_1})+\mathrm{lh}(I_2)f(x_{I_2})$.

Comparability of cardinals from Zorn’s lemma

September 26, 2014

One of the basic consequences of the axiom of choice is that any two sets are comparable, that is, there is an injection from one into the other. The standard argument for this uses that choice is equivalent to the well-ordering theorem: One can prove (without choice) that any two well-ordered sets are comparable, and the well-ordering theorem states that any set is well-orderable.

If for some (foolhardy) reason (say, one is teaching an analysis or algebra course) one is interested in the result, but wants to avoid discussing the theory or well-orders, it seems desirable to have a proof based directly on Zorn’s lemma.

A few weeks ago, Sam Coskey and I found ourselves discussing such a proof. It turns out the argument, though not as well-known as may be expected, dates back at least to Chaim Samuel Hönig, and his short note Proof of the well-ordering of cardinal numbers, Proc. Amer. Math. Soc., 5, (1954), 312. MR0060558 (15,690a). It goes as follows: Let the sets $A$ and $B$ be given. Consider the collection of all partial injections $f$ from $A$ into $B$. That $f$ is partial means that there is a $C\subseteq A$ such that $f:C\to B$. Order this collection by extension: $f\le f'$ iff $f\subseteq f'$. This poset satisfies the conditions of Zorn’s lemma, so it admits maximal elements. One easily verifies that, if $f$ is maximal, then $A$ is the domain of $f$, or $B$ is its range. In either case, this gives us an injection from one of the sets into the other.

A natural extension of the idea allows us to recover that the class of cardinals is not just linearly ordered, but in fact well-ordered, but an additional use of the axiom of choice is needed now (namely, in the form: The product of non-empty sets is non-empty). Suppose first that $\mathcal C$ is a set. We argue that one of the members of $\mathcal C$ injects into all others. The proof is essentially the same as before: Let $A\in \mathcal C$, and consider the family of all sequences $(f_B\mid B\in\mathcal C)$ such that for some $A'\subset A$ and all $B$, we have that $f_B:A'\to B$ is injective. This is a partial order under coordinatewise inclusion. Again, Zorn’s lemma applies, so there is a maximal element $\vec f=(f_B\mid B\in \mathcal C)$; call $A'$ the common domain of all the $f_B$. If $A'=A$, we are done. Else (and this is where the additional use of choice comes in), for some $B$, the range of $f_B$ is $B$: Otherwise, we can pick $a'\in A\setminus A'$ and a sequence $(b_B\mid B\in\mathcal C)$ such that, for all $B$, $b_B\in B\setminus f_B[A']$. But then, setting $f'_B=f_B\cup\{(a',b_B)\}$, we see that $(f'_B\mid B\in\mathcal C)$ contradicts the maximality of $\vec f$. The result follows: Letting $B$ be such that $f_B$ is onto, we see that $B$ injects into $A'$, and $A'$ injects into all sets in $\mathcal C$.

Finally, consider a (proper) class $\mathcal C$. Again, fix $A\in\mathcal C$. Let $\mathcal C'$ be the collection of subsets of $A$ equipotent to sets in $\mathcal C$. Since $\mathcal C'$ is a set, the previous analysis applies, and we can find a $C\in \mathcal C$ that injects into all members of $\mathcal C$ that inject into $A$. It follows that $C$ actually injects into all members of $\mathcal C$. Otherwise, there is a $B\in\mathcal C$ that $C$ does not inject into. But then $B$ itself injects into $C$, and therefore into $A$. But this means that $C$ injects into $B$ after all.

305 – The Futurama theorem

February 24, 2012

Here is a link to Dana Ernst talk on the Futurama theorem of Ken Keeler. In this version, products are just as we treat them (left to right). Also, in this version, there is the “try it yourself” exercise we did not do, but you may want to practice a few examples on your own anyway to make sure you understand the argument.

Another discussion of the Futurama theorem, by Samuel Coskey (who will be joining our math department starting this Fall) can be found here.

Finally, the questions mentioned at the end of Ernst’s talk (see here) are all interesting, and if you figure one or several of them out, please turn them in for extra credit.

(By the way, the same applies to all problems we have been discussing. For example, if through the term you figure a way of producing a really long sequence giving us a better bound for $n(3)$ than what you obtained when the homework was due, please turn it in as well.)