Choice Strength in Baire, Urysohn, Stone, and Tychonoff: Examples and Counterexamples

For nonempty open $G$ and $\rho >0$, fix $y\in G$ and $r>0$ with $B(y,r)\subseteq G$. By [F2] take $m\ge 1$ with $1\mathrm{/}m<\min (r\mathrm{/}3,\rho )$ and $k$ with $s(k)\in B(y,1\mathrm{/}m)$. For $z\in \bar{B}(s(k),1\mathrm{/}m)$ the triangle inequality gives $d(z,y)\le d(z,s(k))+d(s(k),y)<2\mathrm{/}m<r$. Thus $\bar{B}(s(k),1\mathrm{/}m)\subseteq G$, proving the admissible set nonempty. This is one finite existence argument for arbitrary $G,\rho$, not a simultaneous choice of witnesses.

Density of $U_0$ makes $G_0$ nonempty, and it is open. Thus step 1.1 with bound $1\mathrm{/}4$ supplies an admissible pair.

Decode the least code to $(k_0,m_0)$ and put $x_0=s(k_0)$, $r_0=1\mathrm{/}{m}_0$. Then $\bar{B}(x_0,r_0)\subseteq G_0$. The set $G_1=B(x_0,r_0)\cap U_1$ is nonempty by density of $U_1$, because the open ball contains $x_0$; it is open by finite intersection.

Apply the same rule to $G_1$ with bound $1\mathrm{/}8$, and then to $G_2=B(x_1,r_1)\cap U_2$ with bound $1\mathrm{/}16$. At each stage density of the specified next $U_n$ keeps $G_n$ nonempty open, and step 1.1 and [F3] supply the unique next pair. Repeated values of $s$ do not affect uniqueness of the index-radius pair.

For a concrete example take $X=\{p\}$, $d(p,p)=0$, $s(k)=p$ for every $k$, and $W=U_n=X$ for every $n$. The metric axioms hold, every sequence converges to $p$, and the range of $s$ is dense, so the given hypotheses hold. All positive-radius open and closed balls equal $X$. At stages $n=0,1,2$ admissibility is exactly $m\ge 2^{n+2}$. Since $P(k,m)\ge 2m$, with equality exactly when $k=0$, the least pairs are $(0,4),(0,8),(0,16)$, with codes $8,16,32$ and radii $1\mathrm{/}4,1\mathrm{/}8,1\mathrm{/}16$. All centers are the same point $p$, as required for an enumeration with repetitions.

For the general recursion use the set of states $(n,G)$ with $G$ nonempty open, together with a default state. The unique least-code pair defines the successor state $(n+1,B(s(k),1\mathrm{/}m)\cap U_{n+1})$ on each such state; let the default state map to itself. The preceding nonemptiness argument makes this a total self-map. Apply [F4] from $(0,G_0)$ and take the uniquely defined centers and radii. This is set recursion, not a choice of points from an arbitrary family; it gives the same closed-ball inclusions and radius bounds needed in the cited theorem, though its pairs need not equal the lexicographically least pairs there.

Let $a^{(1)},\dots ,a^{(m)}$ be the nodes of the menu at level $n$, with entries $a_i^{(j)}$, and put $U_i:={\bigcap }_{1\le j\le m}{a}_i^{(j)}$ for $1\le i\le 2^n$; each $U_i$ is a finite intersection of open sets, hence open.

For each $1\le i<2^n$ the inclusion $\overline{U_i}\subseteq U_{i+1}$ holds: $\overline{U_i}$ is contained in ${\bigcap }_{1\le j\le m}\overline{a_i^{(j)}}$ by [F1], and each $\overline{a_i^{(j)}}\subseteq a_{i+1}^{(j)}$ by hypothesis, so $\overline{U_i}\subseteq {\bigcap }_{1\le j\le m}{a}_{i+1}^{(j)}=U_{i+1}$.

The boundary values are preserved: $F\subseteq U_1$ because $F$ is contained in every $a_1^{(j)}$, and $U_{2^n}=X\setminus G$ because every $a_{2^n}^{(j)}$ equals $X\setminus G$.

Predecessor coherence is preserved: the Given predecessor property and the definition of $S$ show that every $2i$-th entry occurring in the level-$(n+1)$ menu is an $i$-th entry occurring in the level-$n$ menu. Conversely, the successor property in the Given data makes every level-$n$ node occur as the predecessor of some level-$(n+1)$ node, so every level-$n$ $i$-th entry occurs among those $2i$-th entries. The two indexed families of sets therefore have the same range, and their intersections are equal.

At level $0$ the only possible node is $⟨X\setminus G⟩$, so its intersection is $X\setminus G$. A finite menu at level $1$ consists of nodes $⟨V_j,X\setminus G⟩$, $1\le j\le m$, with $F\subseteq V_j$ and $\overline{V_j}\subseteq X\setminus G$. Its two intersections are $V={\bigcap }_{1\le j\le m}{V}_j$ and $X\setminus G$. Steps 2.1 and 2.2 give $F\subseteq V\subseteq \bar{V}\subseteq X\setminus G$; the second intersection equals the level-$0$ value as in step 2.3. When $m=1$ these are just the original entries. All finite enumerations here concern one fixed menu; no sequence of enumerations is selected.

$E$ is infinite: the map $k\mapsto 2k$ is injective from $\mathbb{N}$ onto $E$, so $E$ is countably infinite.

$\mathbb{N}\setminus E$, the set of odd naturals, is infinite: $k\mapsto 2k+1$ is injective from $\mathbb{N}$ into it, so it is not finite.

In the cofinite space $Y$, the coordinate set $A=\mathbb{N}$ is not closed. Indeed, its complement is the singleton $\{\mathrm{\infty }\}$; this set is nonempty but is not open because its complement $A$ is infinite.

$E$ is not closed: if $E$ were closed then its complement $\mathbb{N}\setminus E$ would be open. It is nonempty because $1$ is odd, and it is not cofinite because its complement $E$ is infinite by step 1.1. Thus $\mathbb{N}\setminus E$ is neither empty nor cofinite, contrary to [F1].

Step 2.1 refutes the first claim using an infinite subset whose complement is infinite, whereas step 1.3 separately refutes the coordinate claim using a subset whose complement is finite. The isolated-point repair of [F2] meets the latter closedness obligation by making $\{\mathrm{\infty }\}$ open.

The three cylinders $C_0,C_1,C_2$ are closed in $X$ by [F1] and [F2].

Each single cylinder is nonempty: the point with one coordinate $0$ (or any other element of $A_j$) and the artificial values $\mathrm{\infty }$ at the other two coordinates lies in it; the artificial values are available because ${\mathrm{\infty }}_k\in X_{A_k}$ for every $k$.

For the pair $\{j,k\}$ the point with prescribed values in $A_j$ and $A_k$ and $\mathrm{\infty }$ in the remaining coordinate lies in $C_j\cap C_k$, so the family has the finite intersection property; for the triple the point $(0,0,0)$ lies in $C_0\cap C_1\cap C_2$.

By [F3] the product $X$ is compact, so by [F2] the intersection $C_0\cap C_1\cap C_2$ is nonempty. Choose $x$ in this intersection. Then $x_j\in A_j$ for all three indices, and the function $g$ defined in [L1] has domain $\mathcal{A}=\{A_0,A_1,A_2\}$ and satisfies $g(S)\in S$ for every $S\in \mathcal{A}$. Thus $g$ is the required choice function.

For a finite list of $n$ sets, the same least-index construction converts a point in the $n$ closed cylinders into a choice function on the underlying set-family. In the general AC argument the factors are instead indexed by the family $\mathcal{A}$ itself, so a product point $x$ with $x_A\in A$ directly defines the choice function $A\mapsto x_A$; compactness supplies such a point after finite choice verifies the cylinders' finite-intersection property. [step 3.1, F2, L1, Every natural-number-indexed list of nonempty sets has a choice function on its family of values] ∎