Tychonoff's Theorem Without Choice

From ProofWiki
Jump to: navigation, search


Theorem without Axiom of Choice

Preliminaries

Let $\displaystyle X = \prod_{i \mathop \in I} X_i$ be a topological product space.

From the definition of the Tychonoff topology, a basic open set of the natural basis of $X$ is a set of the form:

$\displaystyle \prod_{i \mathop \in I} U_i$

where:

each $U_i$ is a nonempty open subset of $X_i$

and:

$U_i = X_i$ for all but finitely many $i \in I$.


Statement that holds in Zermelo–Fraenkel set theory (without Axiom of Choice)

Let $\left({I, <}\right)$ be a well-ordered set.

The Well-Ordering Theorem, equivalent to the Axiom of Choice over Zermelo–Fraenkel set theory, states that every set is well-orderable.

Let $\left \langle {X_i} \right \rangle_{i \mathop \in I}$ be an indexed family of compact topological spaces.

Denote $\displaystyle X := \prod_{i \mathop \in I} X_i$.


Let $\left({F, \subset}\right)$ be the set-theoretic tree:

$\displaystyle \left({\bigcup_{i \mathop \in I} \prod_{j \mathop < i} X_j}\right) \cup X$

of mappings defined on initial intervals of $I$, where the ordering is that of set inclusion.

Consider the set of all subtrees $T \subseteq F$ with the following property:

For every $i \in I$ and every $\displaystyle f \in T \cap \prod_{j \mathop < i} X_j$, the set $\left\{{g \left({i}\right): g \in T, f \subsetneq g}\right\}$ is closed in $X_i$.

Suppose that every such subtree $T$ of $F$ has a branch.

The Hausdorff Maximal Principle, equivalent to the Axiom of Choice over Zermelo–Fraenkel set theory, states that in an ordered set, every chain is contained in a maximal chain, which implies that every tree has a branch.


Then $\displaystyle \prod_{i \mathop \in I} X_i$ is compact.


Proof of the version without Axiom of Choice

To prove that every open cover of $X$ has a finite subcover, it is enough to prove that every open cover by basic open set of the natural basis has a finite subcover.

(If the Axiom of Choice was assumed, it would be even enough to prove that every open cover by subbasic open sets of the natural subbasis has a finite subcover, according to Alexander Subbase Theorem.)

Let $\mathcal O$ be a collection of basic open subsets of $X$ such that no finite subcollection of $\mathcal O$ covers $X$.

It is enough to prove that $\mathcal O$ does not cover $X$.

Let $T_\mathcal O$ be the set of all elements $f \in F$ such that the set $\left\{{x \in X : f \subseteq x}\right\}$ is not covered by any finite subcollection of $\mathcal O$.

Then $T_\mathcal O$ is a subtree of $F$.

For every $i \in I$ and $\displaystyle f \in T_\mathcal O \cap \prod_{j \mathop < i} X_j$, denote:

$C_\mathcal O \left({f}\right) = \left\{{g \left({i}\right): f \subsetneq g \in T_\mathcal O}\right\}$


Step 1

For every $i \in I$ and every $\displaystyle f \in T_\mathcal O \cap \prod_{j \mathop < i} X_j$:

$C_\mathcal O \left({f}\right)$ is closed in $X_i$ and nonempty.

Here the compactness of $X_i$ is used similarly to the usual proof: Topological Product of Compact Spaces.

To prove this, let $\mathcal W$ be the set of all open subsets $U$ of $X_i$ such that:

there exist a finite subset $\mathcal P \subseteq \mathcal O$ such that:
$\displaystyle \left\{ {x \in X: f \subseteq x, x \left({i}\right) \in U}\right\} \subseteq \bigcup \mathcal P$

Then:

$\displaystyle X_i \setminus C_\mathcal O \left({f}\right) = \bigcup \mathcal W$

and hence $C_\mathcal O \left({f}\right)$ is closed.

Aiming for a contradiction, suppose $C_\mathcal O \left({f}\right)$ is empty.

Then $\mathcal W$ would be a cover for $X_i$ and, by compactness of $X_i$, it would have a finite subcover.

This would yield a finite subset of $\mathcal O$ that covers $\left\{{x \in X: f \subseteq x}\right\}$ in contradiction with the fact that $f \in T_\mathcal O$.

So $C_\mathcal O \left({f}\right)$ is nonempty.


It remains to be shown that indeed:

$\displaystyle X_i \setminus C_{\mathcal O} \left({f}\right) = \bigcup \mathcal W$

Consider an arbitrary $a \in X_i \setminus C_\mathcal O \left({f}\right)$.

Define $\displaystyle g \in \prod_{j \mathop \le i} X_j$ by:

$f \subseteq g$

and:

$g \left({i}\right) = a$

Then:

$g \notin T_\mathcal O$

and therefore there is a finite set $\mathcal P \subseteq \mathcal O$ such that:

$\displaystyle \left\{{x \in X: f \subseteq x, x \left({i}\right) = a}\right\} = \left\{{x \in X: g \subseteq x}\right\} \subseteq \bigcup \mathcal P$

and:

$\forall V \in \mathcal P: \left\{{x \in X: f \subseteq x, x \left({i}\right) = a}\right\} \cap V \ne \varnothing$


Let $\displaystyle U = \bigcap \left\{{\operatorname{pr}_i \left({V}\right): V \in \mathcal P}\right\}$.

Then $U$ is an open subset of $X_i$, $a\in U$, and:

$\displaystyle \left\{{x \in X: f \subseteq x, x \left({i}\right) \in U}\right\} \subseteq \bigcup \mathcal P$

Therefore:

$U \cap C_{\mathcal O} \left({f}\right) = \varnothing$

and $a \in U \in \mathcal W$.

$\Box$


Step 2

Every branch of $T_\mathcal O$ has the greatest element.

Aiming for a contradiction, suppose $B$ is a branch of $T_\mathcal O$ without such a greatest element.

Let $f = \bigcup B$.

Let $i$ be the least element of $I$ that is not in the domain of any element of $B$.

Then:

$\displaystyle f \in \prod_{j \mathop < i} X_j$

Since $B$ has no greatest element, $f \notin B$.

Since $B$ is a maximal chain in $T_\mathcal O$:

$f \notin T_\mathcal O$.

Let $\mathcal P \subseteq \mathcal O$ be a finite collection such that:

$\displaystyle \left\{{x \in X: f \subseteq x}\right\} \subseteq \bigcup \mathcal P$

Let $m$ be the greatest element of the finite set:

$\left\{ {j \in I: j < i \text{ and } \exists V \in \mathcal P: \left({\operatorname{pr}_j \left({V}\right) \ne X_j}\right)}\right\}$

Let $g$ be any element of $B$ that is defined on $m$.

Consider an arbitrary $x \in X$ such that $g \subseteq x$.

Let $y \in X$ be defined by $f \subseteq y$ and $y \left({j}\right) = x \left({j}\right)$ for every $j \ge i$, and choose $V \in \mathcal P$ such that $y \in V$.

Because $V$ does not "take into account" the values of $x \left({j}\right)$ for $m < j < i$:

$x \in V$

Thus:

$\left\{{x \in X: g \subseteq x}\right\} \subseteq \bigcup \mathcal P$

in contradiction of the fact that $g \in T_\mathcal O$.

$\Box$


Step 3

Every maximal element of $T_\mathcal O$ is an element of $X$:

Because $C_\mathcal O \left({f}\right) \ne \varnothing$:

an element $f \in T_\mathcal O \setminus X$ cannot be maximal in $T_\mathcal O$.

$\Box$


Conclusion

Now it can be shown that there is $f \in X$ such that $f \notin \bigcup \mathcal O$.

By hypothesis, $T_\mathcal O$ has a branch $B$.

Let $f$ be the greatest element of $B$.

Then $f$ is a maximal element of $T_\mathcal O$.

Therefore $f \in X$.

Therefore the set $\left\{{f}\right\} = \left\{{x \in X: f \subseteq x}\right\}$ is not covered by any finite subcollection of $\mathcal O$.

Hence $f \notin \bigcup \mathcal O$.

$\blacksquare$


Corollaries without Axiom of Choice

Corollary 1

The Cartesian product of a finite indexed family of compact topological spaces is compact.

$\blacksquare$


Corollary 2

Let $I$ be a well-orderable set.

Let $\left \langle {X_i}\right \rangle_{i \mathop \in I}$ be an indexed family of compact topological spaces.

Let the Cartesian product of all nonempty closed subsets of all $X_i$ be nonempty:

$\displaystyle \prod \left\{ {C: C \ne \varnothing \text { and } C \text{ is closed in } X_i \text { for some } i \in I}\right\} \ne \varnothing$

Then $\displaystyle \prod_{i \mathop \in I} X_i$ is compact.


Proof

Let $<$ be a well-order relation on $I$.

Denote $\displaystyle X = \prod_{i \mathop \in I} X_i$.

Let $F$ be the tree:

$\displaystyle \left({\bigcup_{i \mathop \in I} \prod_{j \mathop < i} X_j}\right) \cup X$

ordered by set inclusion.

To apply the theorem, it is enough to verify that:

If $T$ is a subtree of $F$ such that:
for every $i \in I$ and every $\displaystyle f \in T \cap \prod_{j \mathop < i} X_j$, the set $\left\{{g \left({i}\right): g \in T,\ f \subsetneq g}\right\}$ is closed in $X_i$
then $T$ has a branch.


Let:

$\displaystyle e \in \prod \left\{{C: C \ne \varnothing \text { and } C \text{ is closed in } X_i \text { for some } i \in I}\right\}$

be a choice function.

That is:

$e \left({C}\right) \in C$ for every nonempty $C$ which is closed in some $X_i$.

Let $B_e$ be the minimal tree among all subtrees $S$ of $T$ with the property that:

for every $i \in I$ and every $\displaystyle f \in S \cap \prod_{j \mathop < i} X_j$:
$e \left({\left\{{g \left({i}\right): g \in T, f \subsetneq g}\right\}}\right) \in \left\{{g \left({i}\right): g \in S, f \subsetneq g}\right\}$
unless:
$\left\{{g \left({i}\right): g \in T, f \subsetneq g}\right\} = \varnothing$

Such subtrees of $T$ exist because $T$ itself is one such.

The minimal such subtree is the intersection of all such subtrees.

It can be shown that $B_e$ is a branch by assuming that it is not, considering the minimal $i\in I$ where it "branches", and arriving at a contradiction with its minimality.



$\blacksquare$


Applications


The proof that $\left[{0 \,.\,.\, 1}\right]^\Z$ is compact does not require the Axiom of Choice, because the product of all nonempty closed subsets of $\left[{0 \,.\,.\, 1}\right]$ contains, for example, the greatest lower bound function $\inf$ (restricted to the collection of closed subsets of $\left[{0 \,.\,.\, 1}\right]$):

$\displaystyle \left\{{(C,\inf C) : C \ne \varnothing \text { and } C \text{ is closed in } \left[{0 \,.\,.\, 1}\right]}\right\} \in\prod \left\{{C: C \ne \varnothing \text { and } C \text{ is closed in } \left[{0 \,.\,.\, 1}\right]}\right\}$

(Here $\displaystyle \left\{ { \left({C, \inf C}\right): C \ne \varnothing \text { and } C \text{ is closed in } \left[{0 \,.\,.\, 1}\right]}\right\}$ is a way to write a function $f$ defined on the collection of all nonempty closed subsets of $[0 \,.\,.\, 1]$ by $f \left({C}\right) = \inf C$.)



Also see