To what extent does the usual Stone-Weierstrass Theorem depend on some form of the Axiom of Choice? There seems to be a lot of literature on constructive versions in toposes, but I have been unable to find a clear statement about the dependence of the usual theorem on the AC, or a counterexample without AC. And what about the metrizable or second countable case?



Stone-Weierstrass Theorem without AC
Caveat - I am not well versed in working with mathematics without the axiom of choice, so this answer should be taken with a grain of salt.


This question seems to be sensitive to the precise definition of compactness, continuity, and separation of points. Here I use the following definitions:


* A space $X$ is compact if and only if for all open covers ${\mathcal U}$ there exists a finite subcover $U\_1,\dots,U\_n$ of ${\mathcal U}$. [We do *not* require that there is a choice function from ${\mathcal U}$ to $(U\_1,\dots,U\_n)$. We also do *not* require that the open cover come with a choice function $x \mapsto U\_x$ from each point $x \in X$ to an open set $U\_x$ in the cover that contains it.]
* A function $f: X \to Y$ is continuous if and only if the inverse image of every open set is open.
* An algebra ${\mathcal A} \subset C(X) = C(X \to {\bf R})$ separates points if and only if, for every distinct $x,y \in X$, there exists a function $f \in {\mathcal A}$ such that $f(x) \neq f(y)$. [We do *not* require that there is a choice function from $(x,y)$ to $f$.]


(I will leave it to the experts to work out what happens if we use net-based, sequence-based, or ultrafilter-based definitions of compactness and/or continuity instead.)


Then:



> 
> **Stone--Weierstrass Theorem** Let $X$ be a compact space, and let ${\mathcal A} \subset C(X)$ be a unital algebra that separates points. Then for any $f \in C(X)$ and $\varepsilon > 0$ there exists $g \in {\mathcal A}$ such that $d(f,g) \leq \varepsilon$ (where $d$ denotes the uniform metric).
> 
> 
> 


[Strictly speaking, this is only one direction of the Stone--Weierstrass theorem; the converse direction, which is essentially Urysohn's lemma for compact Hausdorff spaces, asserts that if $X$ is additionally assumed to be Hausdorff, then any dense subset of $C(X)$ must necessarily separate points. This direction appears to be more reliant on the axiom of choice, but I will not pursue this question further here, as the direction stated above is the one which is most commonly invoked in applications.]


**Proof** This is going to be the textbook proof of Stone--Weierstrass, with all unnecessary references to choice functions removed (and also by refusing to pass to the uniform closure of the algebra, though this seems less critical to me).


First observe from the Weierstrass approximation theorem (which as noted in comments is completely constructive) that for any $f,g \in {\mathcal A}$ and $\varepsilon > 0$ there exists $h \in {\mathcal A}$ such that $d(\max(f,g),h) \leq \varepsilon$. Similarly with $\max$ replaced by $\min$. By induction, this implies that ${\mathcal A}$ is closed under arbitrary finite lattice operations to arbitrary error in the uniform topology. [Here we are using the fact that continuous functions on a compact set are bounded, which is still true without AC with our definitions, as one can easily check by inspecting the standard proof (the collection of open sets on which the function is bounded is an open cover).]


We have the following key subclaim: if $f \in C(X)$, $x \in X$ and $\varepsilon>0$, then there exists $g \in {\mathcal A}$ such that $|f(x)-g(x)| \leq \varepsilon$ and $g(y) \leq f(y)+\varepsilon$ for all $y \in X$.


To prove the subclaim, consider the collection ${\mathcal U}$ of open sets $U$ for which there exists a function $g \in {\mathcal A}$ such that $|f(x)-g(x)| \leq \varepsilon$ and $g(y) \leq f(y)+\varepsilon$ for all $y \in U$. By continuity of $f$, there is a neighbourhood of $x$ that lies in ${\mathcal U}$. Because ${\mathcal A}$ is a unital algebra that separates points and $f$ is continuous, every $y$ not equal to $x$ has a neighborhood that lies in ${\mathcal U}$. Hence ${\mathcal U}$ is an open cover of $X$, hence by compactness there is a finite subcover $U\_1,\dots,U\_n$. By finite choice, for each $i=1,\dots,n$ one can find $g\_i \in {\mathcal A}$ such that $|f(x)-g\_i(x)| \leq \varepsilon$ and $g\_i(y) \leq f(y)+\varepsilon$ for $y \in U\_i$. By preceding remarks, we can find $g \in {\mathcal A}$ which lies within $\varepsilon$ in the uniform metric of $\min(g\_1,\dots,g\_n)$, then $|f(x)-g(x)| \leq 2\varepsilon$ and $g(y) \leq f(y)+2\varepsilon$ for all $y \in X$. The claim now follows after replacing $\varepsilon$ with $\varepsilon/2$.


Now for a given $f \in C(X)$, let ${\mathcal V}$ denote the open sets $V$ for which there exists $g \in {\mathcal A}$ such that $|f(x)-g(x)| \leq \varepsilon$ for $x \in V$ and $g(y) \leq f(y)+\varepsilon$ for all $y \in X$. By the preceding claim and continuity (replacing $\varepsilon$ with $\varepsilon/2$) we see that every $x \in X$ has a neighbourhood in ${\mathcal V}$, thus ${\mathcal V}$ is an open cover of $X$. By compactness it has a finite subcover $V^1,\dots,V^m$. By finite choice, for each $i=1,\dots,m$ we can find $g^i \in {\mathcal A}$ such that $|f(x)-g^i(x)| \leq \varepsilon$ for $x \in V^i$ and $g^i(y) \leq f(y) + \varepsilon$ for $y \in X$. By the previous discussion, we can find $g \in {\mathcal A}$ that lies within $\varepsilon$ of $\max(g^1,\dots,g^m)$. Then $|f(x)-g(x)| \leq 2\varepsilon$ for all $x \in X$, giving the claim after replacing $\varepsilon$ with $\varepsilon/2$ one final time. $\Box$


I think what is going on here is that compactness becomes a strong hypothesis in the absence of choice - so strong, in fact, that while the Stone--Weierstrass theorem is technically provable without AC, it is somewhat useless since there are so few provably compact spaces one can apply it to.


