# Continuity and the Axiom of Choice

In my introductory Analysis course, we learned two definitions of continuity.

$(1)$ A function $f:E \to \mathbb{C}$ is continuous at $a$ if every sequence $(z_n) \in E$ such that $z_n \to a$ satisfies $f(z_n) \to f(a)$.

$(2)$ A function $f:E \to \mathbb{C}$ is continuous at $a$ if $\forall \varepsilon>0, \exists \delta >0:\forall z \in E, |z-a|<\delta \implies |f(z)-f(a)|<\varepsilon$.

The implication $(2)\implies(1)$ is trivial (though I will happily post a proof if there is sufficient interest). The proof of the implication $(1)\implies(2)$ is worth remarking on, though.

Proof that $(1)\implies(2)$:

Suppose on the contrary that $\exists \varepsilon>0:\forall \delta>0, \exists z \in E:\left (|z-a|<\delta \; \mathrm{and} \; |f(z)-f(a)|\ge \varepsilon\right )$. Let $A_n$ be the set $\{z\in E:|z-a|<\frac{1}{n} \; \mathrm{ and }\; |f(z)-f(a)|\ge\varepsilon\}$. Now use the Axiom of Choice to construct a sequence $(z_n)$ with $z_n \in A_n \; \forall n \in \mathbb{N}$. But now $a-\frac{1}{n}<z_n<a+\frac{1}{n}\; \forall n \in \mathbb{N}$ so $z_n \to a$. So $f(z_n) \to f(a)$. But $|f(z_n)-f(a)|\ge\varepsilon\; \forall n \in \mathbb{N}$, which is a contradiction.

You will have noticed that the above proof uses the Axiom of Choice (the lecturer didn't explicitly spell out the dependence, but it's definitely there). My question is: is it possible to prove that $(1) \implies (2)$ without using the Axiom of Choice. I strongly suspect that it isn't. In that case, can anyone prove that we have to use the Axiom of Choice? I can think of three ways to do this:

(A) Show that $\left( (1) \implies (2)\right)\implies \mathrm{AC}$. I suspect that this statement is untrue. This is definitely untrue, as Arthur points out, because I only used the axiom of countable choice, which is strictly weaker than AC.

(B) Show that $(1)\implies (2)$ is equivalent to some other statement known to require the Axiom of Choice (the obvious example being the well-ordering of the real numbers).

(C) Construct or show the existence of a model of ZF in which there exist sequences which satisfy $(1)$ but not $(2)$.

Of course, if anyone can think of another way, I would be very interested to hear about it.

One final note - I am aware that very many theorems in Analysis use the Axiom of Choice in one way or another, and that this is just one example of such a theorem. If there exists a model of ZF like the one described in (C), is the study of Analysis in that model interesting?

-
Asaf will likely be around here soon giving a complete answer, but I have an observation or two. First of all, you don't need the full power of the Axiom of Choice, but only the Axiom of Countable Choice. Even here you don't need the full power of Countable Choice, but only restricted to subsets of $\mathbb{R}$. I would posit that this is the "Choice strength" of the implication, but someone better versed will likely correct me. –  Arthur Fischer Mar 29 '12 at 18:00
consequences.emich.edu confirms that "every sequentially continuous function from a metric space to $\mathbb{R}$ is continuous" is equivalent to the axiom of countable choice. So is "any sequentially continuous function between metric spaces is continuous". –  Chris Eagle Mar 29 '12 at 18:06
In case anyone is interested, I believe Sierpinski was the first person to point out the use of the axiom of choice in proofs of this result. He published a short C. R. Academy Sci. (Paris) note about this in 1916 (JFM 46.0295.04) and a 56 page paper in French in 1918 (JFM 46.0297.01). More details are in Gregory H. Moore's book on the axiom of choice, but I don't have my copy of his book with me where I'm currently at. –  Dave L. Renfro Mar 29 '12 at 18:26
@Dave... JFM = Journal of Fluid Mechanics? –  GEdgar Mar 29 '12 at 18:35
@GEdgar: JFM is the reviewing journal Jahrbuch über die Fortschritte der Mathematik, which is on-line at emis.de/MATH/JFM/JFM.html I got the Sierpinski references by searching with author=Sierpinski and decided to use the JFM citation numbers as identifiers for the papers. –  Dave L. Renfro Mar 29 '12 at 19:43

Part of your observation is indeed correct. The axiom of choice is needed, although not in its entire power.

The first model of ZF without the axiom of choice, known as Cohen's first model, is one where there exists an infinite Dedekind-finite set of reals.

We say that a set is Dedekind-finite if it has no infinitely-countable subset, indeed it is consistent without the axiom of choice that such infinite sets exist, and Cohen's model is an example of a model in which such set exists within the real numbers, let us call it $D$.

First we observe that if $a_n$ is a sequence of elements from $D$ then as a set $\{a_n\mid n\in\mathbb N\}$ is finite, otherwise we would have a countably infinite subset of $D$. If so every weakly decreasing/increasing sequence in $D$ is eventually constant. It also holds that there is at least one accumulation point of $D$ (within $D$, that is). Otherwise we could have separated all the points by disjoint intervals and would then reach the conclusion that $D$ is at most countable.

Let $S=D\setminus\{a\}$ for some accumulation point $a$ in $D$. Now consider $f\colon D\to\mathbb R$ define as: $$f(x)=\begin{cases}1 & x=a\\ 0 &x\neq 0\end{cases}$$ This function is not continuous at $a$ for obvious reasons, for $\varepsilon=\frac12$ we have that for $\delta>0$ we have some $d\in S$ such that $|d-a|<\delta$ we still have $|f(d)-f(a)|=1>\varepsilon$.

However, given a sequence $a_n$ whose limit is $a$ then the sequence is eventually constantly $a$, therefore $f(a_n)=f(a)=1$ for almost all $n$.

Note that if we assume that $f\colon\mathbb R\to\mathbb R$ is continuous at $x$, and $x_n$ is a sequence approaching $x$ then indeed $f(x_n)$ approaches $f(x)$.

Suppose not, then there is some $\varepsilon>0$ that for large enough $n$ we have $|f(x)-f(x_n)|>\varepsilon$, then for every $\delta>0$ we can find $n$ such that $|x-x_n|<\delta$, which contradicts the $\varepsilon$-$\delta$ continuity at $x$.

On the other hand, assuming that for a given point $x$ continuity at $x$ equals sequential continuity there is far from the axiom of choice. Why? Note that we really just need countable choice to assert the equivalence, and it is quite simple to construct models in which the axiom of choice does not hold but the axiom of countable choice holds.

Indeed we know that the assertion:

$f\colon\mathbb R\to\mathbb R$ is continuous at a point $x$ if and only if it is sequentially continuous at that point.

Is equivalent to the axiom of countable choice for subsets of the real line; and I suppose we can use that to deduce the same for complex valued functions quite easily.

I should also add the following:

If the equivalence between the two forms of continuity does not hold it means that the axiom of countable choice does not hold. In turn we cannot ensure that countable unions of countable sets are still countable; this allows great difficulties in ensuring that real analysis works as we are familiar with it.

However, there are interesting models for analysis where the axiom of choice does not hold. Solovay's model in which every set is Lebesgue measurable (and much much more) is such model. Just today I ran into a relatively old paper speaking excitingly about "Solovayan functional analysis" which will be a new and exciting field.

With gratitude to Brian pointing out that continuity everywhere is still equivalent to sequential continuity everywhere; but not when we require a function to be continuous at a certain point (the counterexample in the Dedekind-finite set would be a function which is not continuous everywhere).

-
I’m afraid that this is wrong: the assertion in question is not equivalent to $\mathbf{CC}(\Bbb R)$. See my answer. –  Brian M. Scott Mar 29 '12 at 19:08
@Brian: Glossing over Herrlich's chapter on the topic I'm not seeing any mention of complex valued functions. –  Asaf Karagila Mar 29 '12 at 19:12
That claim is false, and I’m not making it. The statement on the lefthand side of the $\iff$ is true in ZF; it’s only when you localize it to continuity at a point that it becomes equivalent to $\mathbf{CC}(\Bbb R)$. –  Brian M. Scott Mar 29 '12 at 19:40
@Brian: Wouldn't it be easier to just point me at Theorem 4.52 in Herrlich's book and them to compare and contrast it with 4.54? :-) I see your point now! Thanks for the correction, it's a subtle one! –  Asaf Karagila Mar 29 '12 at 19:44
@Donkey: I am not sure how you have accepted this answer, but since you have I will revise it. I'm reading it now and it is completely without clarity. I will change some things and work with the books to ensure correctness as well. To your comment I will address within the edit. To the second part, first $D$ is dense everywhere (by the generic properties of its construction) and secondly $\mathbf{CC}(D)$ means choice function from countably many finite subset of real numbers. There is always a finite choice function like that, those are real numbers in the sets, every finite set has a minimum –  Asaf Karagila Mar 30 '12 at 13:05

The implication $(1)\to (2)$ can be proved in ZF alone, though this requires major revision of the argument.

Assume that $f:\Bbb R\to\Bbb R$ is sequentially continuous (i.e., satisfies (1)). Let $x\in\Bbb R$ be arbitrary.

Claim: $f\upharpoonright(\Bbb Q\cup\{x\})$ is continuous at $x$.

Proof: Enumerate $\Bbb Q=\{q_n:n\in\omega\}$. If $f\upharpoonright(\Bbb Q\cup\{x\})$ is not continuous at $x$, there is an $\epsilon>0$ such that for each $k\in\omega$, $$A_k\triangleq\{q\in\Bbb Q:|q-x|<2^{-k}\text{ and }|f(q)-f(x)|\ge\epsilon\}\ne\varnothing\;.$$ Let $$n(0)=\min\{k\in\omega:q_k\in A_0\}\;.$$ Given $n(m)$, let $$n(m+1)=\min\{k\in\omega:k>n(m)\text{ and }q_k\in A_{m+1}\}\;.$$ Then $\langle q_{n(k)}:k\in\omega\rangle\to x$, but $|f(q_{n(k)})-f(x)|\ge\epsilon$ for all $k\in\omega$, which is a contradiction. Note that no choice was used in this construction. $\dashv$

Now let $\epsilon>0$. It follows from the Claim that there is a $\delta>0$ such that $|f(x)-f(q)|\le\epsilon$ whenever $q\in\Bbb Q$ and $|x-q|\le\delta$. Now suppose that $y\in\Bbb R$ with $|x-y|\le\delta$. Let $I$ be the closed interval whose endpoints are $x$ and $y$. For each $k\in\omega$ let $$n(k)=\min\{m\in\omega:q_m\in I\text{ and }|q_m-y|<2^{-k}\}\;.$$ Then $\langle q_{n(k)}:k\in\omega\rangle\to y$, so $\langle f(q_{n(k)}):k\in\omega\rangle\to f(y)$. However, each $q_{n(k)}\in I$, so $|q_{n(k)}-x|\le\delta$ for each $k\in\omega$, and therefore $|f(q_{n(k)})-f(x)|\le\epsilon$ for each $k\in\omega$. Clearly this implies that $|f(y)-f(x)|\le\epsilon$ as well.

Thus, we’ve shown that for each $\epsilon>0$ there is a $\delta>0$ such that $|f(y)-f(x)|\le\epsilon$ whenever $|y-x|<\delta$, which is sufficient.

This argument is expanded from the ZF proof of Theorem 3.15 in Horst Herrlich, Axiom of Choice, Lecture Notes in Mathematics 1876. Note that it is not true in ZF that a function $f:\Bbb R\to\Bbb R$ is continuous at a point $x$ iff it is sequentially continuous at $x$: in Theorem 4.54 he proves that this assertion is equivalent to $\mathbf{CC}(\Bbb R)$, the assertion that every countable family of non-empty subsets of $\Bbb R$ has a choice function.

Added: I failed to notice that the functions in the original question are complex-valued, not real-valued. However, the argument can easily be adapted to $\Bbb R^2$, replacing $\Bbb Q$ by $\Bbb Q^2$ and using the $\max$ norm.

Added2: The only slightly tricky bit is figuring out what to use for $I$. Suppose that $x=\langle x_1,x_2\rangle,y=\langle y_1,y_2\rangle\in\Bbb R^2$ with $0<\|x-y\|\le\delta$. If $x_1\ne y_1$ and $x_2\ne y_2$, let $$I=\big[\min\{x_1,y_1\},\max\{x_1,y_1\}\big]\times\big[\min\{x_2,y_2\},\max\{x_2,y_2\}\big]\;.$$ If $x_1\ne y_1$ and $x_2=y_2$, let $$I=\big[\min\{x_1,y_1\},\max\{x_1,y_1\}\big]\times\big[x_2,x_2+\delta\big]\;,$$ and if $x_1=y_1$ and $x_2\ne y_2$ let $$I=\big[x_1,x_1+\delta\big]\times\big[\min\{x_2,y_2\},\max\{x_2,y_2\}\big]\;.$$

Let $\Bbb Q^2=\{q_n:n\in\omega\}$ be an enumeration of $\Bbb Q^2$, and for $k\in\omega$ let $$n(k)=\min\{m\in\omega:q_m\in I\text{ and }\|q_m-y\|<2^{-k}\}\;.$$ Everything else is the same as before, except that $|\cdot|$ must be replaced throughout by $\|\cdot\|$, where $$\|\langle x,y\rangle\|=\max\{|x|,|y|\}\;.$$

With very minor modification this works for $\Bbb R^n$ for any $n\in\Bbb Z^+$.

-
I have to admit that I am very amused by the fact that all three posters in this thread had subtle inaccuracies in their posts; myself and the OP disregarded the pointed continuity while you neglected the complex numbers. I guess that now all is well and we can move on! :-) –  Asaf Karagila Mar 29 '12 at 20:20
Ah, yes - I should have been clearer that I was talking about continuity at a point. But then I might have missed out on this delightful proof! –  Donkey_2009 Mar 30 '12 at 8:32
@Brian Your argument shows that "$\forall (x\in \mathbb{R} \bigwedge \epsilon >0), \exists \delta >0$ such that $\forall y\in \mathbb{R}, d(x,y)≦\delta \Rightarrow d(f(x),f(y))≦\epsilon$". I don't understand why it is sufficient to show that $f$ is continuous. Help! –  Katlus Oct 17 '12 at 6:05
@Katlus: That should be ‘$d(x,y)<\delta\Rightarrow d(f(x),f(y))\le\epsilon$’. What don’t you understand? That’s essentially the definition of continuity at $x$. Is it the $\le\epsilon$ instead of $<\epsilon$? If you want me to get $d(f(x),f(y))<\epsilon$, I’ll just choose $\delta$ small enough to guarantee that $d(f(x),f(y))\le\epsilon/2$. –  Brian M. Scott Oct 17 '12 at 6:22
@Brian I'm not talking about the inequality. I mean, in my comment, "$\forall x\in \mathbb{R}$" is at the first of the statement. I don't know how to locate it after $"\exists \delta>0$". The statement in my comment and the definition of continuity doesn't seem trivially equivalent to me.. –  Katlus Oct 17 '12 at 6:35