Do you know if the following statement is an equivalent form of the axiom of choice or not?

If $X$ is a compact metric space, then every continuous function $f: X \longrightarrow \mathbb{R}$ is uniformly continuous.

If you know any references, please let me know.

  • 1
    $\begingroup$ What notion of compactness do you use? I ask specifically since with the definition that seems most standard to me: every open cover contains finite subcover, it is not clear to me where the usual proof even appears to make use of AC. I might be missing something though. If so could you please say where AC is/seems to be needed. $\endgroup$ – user9072 Feb 17 '13 at 15:46
  • 4
    $\begingroup$ Quid, one might think that one has to use AC when choosing the ball around each point $x$, but in a metric space there is a canonical choice, so AC is not needed. The argument does not work, however, in a general topological space as opposed to a metric space. $\endgroup$ – Joel David Hamkins Feb 17 '13 at 15:52
  • $\begingroup$ @Joel David Hamkins: ah, yes, thank you! The usual 'for each $x$ esists $\delta_x$ such that...' does not really "give" a $\delta_x$ but so to say only the option to choose one (this is what I overlooked). $\endgroup$ – user9072 Feb 17 '13 at 16:05
  • 2
    $\begingroup$ Of course "uniformly continuous" is not defined in general topological space. $\endgroup$ – Gerald Edgar Feb 17 '13 at 17:41
  • 1
    $\begingroup$ Uniform continuity is, however, defined in uniform spaces, namely those spaces $X$ whose topology is defined by a choice of a neighborhood basis for the diagonal in $X \times X$. So this question would make sense in that context. $\endgroup$ – Lee Mosher Feb 17 '13 at 23:28

It seems to me that this is provable without using the axiom of choice.

Suppose that $X$ is a compact metric space and $f:X\to\mathbb{R}$ is continuous. Let's show it is uniformly continuous. Fix any $\epsilon\gt 0$. For each point $x\in X$, there is a small ball $B$ centered at $x$ such that $f(y)$ is within $\epsilon/2$ of $f(x)$ for all $y\in B$, and we may choose $B$ to have radius $1/{n_x}$, where we choose $n_x$ to the smallest positive natural number for which this radius has the desired property. Thus, we have a canonical choice of radius here, and so we do not need the axiom of choice to define the map $x\mapsto n_x$.

Consider now the family $\{ B_{1/{2n_x}}(x) \mid x\in X \}$, consisting of the inner core of each of those balls, with the radius of each of them shrunk to half. This is an open cover of $X$, and so by compactness there is a finite subcover, which consists of finitely many balls, having some minimal radius $1/{2n}$. Now, if $y$ and $z$ are within $1/{2n}$ of each other, then they are both within $1/{n_x}$ of the center $x$ of the ball in which $y$ sits in the subcover, and so $f(y)$ and $f(z)$ are within $\epsilon/2$ of $f(x)$, and hence within $\epsilon$ of each other, showing that $f$ is uniformly continuous.

  • $\begingroup$ General case being a function to an arbitrary (locally compact?) metric space? $\endgroup$ – Asaf Karagila Feb 17 '13 at 17:28
  • 2
    $\begingroup$ I see, there is even no need to choose a particular $n_x$; just include all the balls! $\endgroup$ – Joel David Hamkins Feb 17 '13 at 23:39
  • 3
    $\begingroup$ Right, in fact if I wrote a book titled "How to avoid the axiom of choice", that would be trick number one: don't choose! $\endgroup$ – Andrej Bauer Feb 17 '13 at 23:43
  • 3
    $\begingroup$ Because every compact metric space is separable, the theorem can be formalized in second-order arithmetic, where it is provable in $\mathsf{WKL}_0$. $\endgroup$ – Carl Mummert Feb 18 '13 at 0:24
  • 2
    $\begingroup$ As far as I can see, the obvious argument for separability of compact metric spaces uses the countable axiom of choice, and further instances of choice may be hidden in the representation of compact metric spaces as quotients of $2^\omega$, which is what you need to translate the theorem into the language of $\mathrm{WKL}_0$. $\endgroup$ – Emil Jeřábek Feb 18 '13 at 19:37

Let us improve slightly on Joel's answer by avoiding not only choice but also excluded middle (which is used in assuming that the minima $n_x$ exist). In passing we also generalize to an arbitrary metric codomain. Since the various notions of compactness are not equivalent intuitionistically, we have to specify which one we mean. We mean by "compact" the Heine-Borel finite subcover property.

Theorem: If a map $f : X \to Y$ from a compact metric space to a metric space is continuous then it is uniformly continuous.

Proof. (No excluded middle, no choice.) Let $\epsilon > 0$ be given. Consider the family of open balls $$\mathcal{F} = \lbrace B(x,r) \mid x \in X, r > 0, \forall x', x'' \in B(x,2r) . d(f(x'), f(x'')) < \epsilon \rbrace.$$ Beware, we put $B(x,r)$ in $\mathcal{F}$ if the larger ball $B(x,2 r)$ is mapped by $f$ to a sufficiently small set.

Because $f$ is continuous, $\mathcal{F}$ covers $X$. By the Heine-Borel property it has a finite subcover $$B(x_1, r_1), \ldots, B(x_n, r_n).$$ Let $\delta = \min (r_1, \ldots, r_n)$. Suppose $d(y,z) < \delta$ for some $y, z \in X$. There is $i$ such that $d(x_i, y) < r_i$, hence $d(x_i, z) \leq d(x_i, y) + d(y, z) < r_i + \delta \leq 2 r_i$. Thus, since both $y$ and $z$ are contained in $B(x_i, 2 r_i)$ we conclude $d(f(y), f(z)) < \epsilon$. QED.

As usual, the constructive proof is also the most elegant one. The above proof is an easy adaptation that avoids unecessary use of choice of 4.3.31 and 4.3.32 of Engelking's famous General Topology. Further reading: Hajime Ishihara and Peter Schuster, Compactness under constructive scrutiny. Math. Log. Quart. 50, No. 6, 540 – 550 (2004).

  • $\begingroup$ That's a nice proof! $\endgroup$ – user9072 Feb 18 '13 at 0:01
  • 6
    $\begingroup$ The constructive skeleton in the closet is this: one cannot exhibit existence of interesting spaces with the Heine-Borel property, constructively. $\endgroup$ – Andrej Bauer Feb 18 '13 at 0:15

Look Ma, no axiom of choice!

THEOREM 0   Let   $X$   be a compact space. Let   $\Phi$   be a non-empty family of closed subsets of   $X$,   $F := \bigcap \Phi$,   and   $G\supseteq F$   an open subset of   $X$.   Then there exists a finite   $\Phi_0\subseteq \Phi$   such that   $\bigcap\Phi_0\subseteq G$.

PROOF   Family   $\Gamma\ :=\ G\cup\{X\setminus A : A \in \Phi\}$   is an open covering of   $X$. Etc.   END of PROOF

As an instant corollary we get:

THEOREM 1   Let   $X$   be a compact space. Let   $\Phi$   be a non-empty family of closed subsets of   $X$,   $F := \bigcap \Phi$,   and   $G\supseteq F$   an open subset of   $X$.   Assume also that   $\Phi$   is linearly ordered by   $\subseteq$.   Then there exists   $A\in \Phi$   such that   $A \subseteq G$.

THEOREM 2   Let   $(X\ d)$   be a compact metric space. Let   $W$   be an open subset of   $X^2$,   such that   $\Delta_X\subset W$,   where   $\Delta_X := \{(x\ x):x\in X\}$.   Then there exists   $\delta > 0$   such that   $V_X(\delta)\subseteq W$,   where   $V_X(\delta) := \{(x\ y)\in X^2 : d(x\ y)\le\delta\}$.

PROOF   Apply Theorem 1 to   $X^2$ as a replacement of   $X$   of Theorem 1; etc.   END of PROOF

THEOREM 3   Let   $f : X\rightarrow Y$   be an arbitrary continuous function of a metric compact space   $(X\ d_X)$   into an arbitrary metric space   $(Y\ d_Y)$.   Then function   $f$   is uniformly continuous.

PROOF   Let   $\epsilon > 0$.   Let   $W\subseteq X^2$   be the inverse image of   $V_Y(\epsilon)$   under function   $f\times f$.   There exists, by Theorem 2,   $\delta > 0$   such that   $V_X(\delta)\subseteq W$.   Then   $d_Y(f(x')\ f(x''))\le\epsilon$   for every   $x'\ x''\in X$   such that   $d_X(x'\ x'')\le\delta$.   END of PROOF

  • $\begingroup$ This proof has no balls. Is it a drawback? $\endgroup$ – Włodzimierz Holsztyński Feb 18 '13 at 19:24
  • $\begingroup$ I assume you require $F = \bigcap_{\phi \in \Phi}\phi$ instead of $F = \bigcap\Phi$. $\endgroup$ – Vidit Nanda Feb 18 '13 at 19:32
  • 2
    $\begingroup$ @Vel Nias: en.wikipedia.org/wiki/… $\endgroup$ – Emil Jeřábek Feb 18 '13 at 19:49
  • $\begingroup$ In the context of my writing (of my notation) the two are the same. I use pairs of related big operations: direct and indexed. Whenever the direct operation is suitable, it is simpler (less clutter) hence preferable. It works for Cup, Sum, Max, Sup, Cap, Product, Min, Inf, ... (I also avoid coma whenever possible...; there was around here a thread devoted to notation, and I enjoy notation and terminology, but ... oh, well). $\endgroup$ – Włodzimierz Holsztyński Feb 18 '13 at 20:02
  • $\begingroup$ I miss the missing commas. You have excluded middle all over the place, but it might be avoidable: use closed sets instead of open to formulate topology and compactness, and in Theorem 1 replace linearity with directedness, or intuitionstic linearity $x < y \Rightarow x < z \lor z < y$, I am not sure. Anyhow, your proof seems to generalize to uniform spaces, so it is nice to have it. $\endgroup$ – Andrej Bauer Feb 18 '13 at 22:44

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.