PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] Tychonoff's theorem implies AC (Proof)

In this entry, we prove that Tychonoff's theorem implies that product of non-empty set of non-empty sets is non-empty, which is equivalent to the axiom of choice (AC). This fact, together with the fact that AC implies Tychonoff's theorem, shows that Tychonoff's theorem is equivalent to AC (under ZF). The proof was first discovered by John Kelley in 1950, and is now an exercise in axiomatic set theory.

Proof. Let $C$ be a non-empty collection of non-empty sets. Let $Y$ be the generalized cartesian product of all the elements in $C$ Our objective is show that $Y$ is non-empty.

First, some notations: for each $A\in C$ set $X_A:=A\cup \lbrace A\rbrace$ $D:=\lbrace X_A\mid A\in C\rbrace$ $X$ the generalized cartesian product of all the $X_A$ s, and $p_A$ the projection from $X$ onto $X_A$

We break down the proof into several steps:

  1. $Y$ is equipollent to $Z:=\bigcap \lbrace p_A^{-1}(A)\mid A\in C\rbrace$

    An element of $X$ is a function $f: D\to \bigcup D$ such that $f(X_A)\in X_A$ for each $A\in C$ In other words, either $f(X_A)\in A$ or $f(X_A)=A$ An element of $Y$ is a function $g:C\to \bigcup C$ such that $g(A)\in A$ for each $A\in C$ Finally, $h\in p_A^{-1}(A)$ iff $h(X_A)\in A$

    Given $g\in Y$ define $g^*\in X$ by $g^*(X_A):=g(A)\in A$ Since $A$ is arbitrary, $g^*\in Z$ Conversely, given $h\in Z$ define $h'\in Y$ by $h'(A):=h(X_A)$ which is well-defined, since $h(X_A)\in A$ Now, it is easy to see that the function $\phi:Y\to Z$ given by $\phi(g)=g^*$ is a bijection, whose inverse $\phi^{-1}:Z\to Y$ is given by $\phi^{-1}(h)=h'$ This shows that $Y$ and $Z$ are equipollent.

  2. Next, we topologize each $X_A$ in such a way that $X_A$ is compact.

    Let $\mathcal{T}_A$ be the coarsest topology containing the cofinite topology on $X_A$ and the singleton $\lbrace A\rbrace$ A typical open set of $X_A$ is either the empty set, or has the form $S\cup \lbrace A\rbrace$ where $S$ is cofinite in $A$

    To show that $X_A$ is compact under $\mathcal{T}_A$ let $\mathcal{D}$ be an open cover for $X_A$ We want to show that there is a finite subset of $\mathcal{D}$ covering $X_A$ If $X_A\in \mathcal{D}$ then we are done. Otherwise, pick a non-empty element $S\cup \lbrace A\rbrace$ in $\mathcal{D}$ so that $A-S\ne \varnothing$ and is finite. By assumption, each element in $A-S$ belongs to some open set in $\mathcal{D}$ So to cover $A-S$ only a finite number of open sets in $\mathcal{D}$ are needed. These open sets, together with $S\cup\lbrace A\rbrace$ cover $X_A$ Hence $X_A$ is compact.

  3. Finally, we prove that $Z$ and therefore $Y$ is non-empty.

    Apply Tychonoff's theorem, $X$ is compact under the product topology. Furthermore, $\pi_A$ is continuous for each $A\in C$ Since $\lbrace A\rbrace$ is open in $X_A$ and $A=X_A-\lbrace A\rbrace$ $A$ is closed in $X_A$ and thus so is $p_A^{-1}(A)$ closed in $X$

    To show that $Z$ is non-empty, we employ a characterization of compact space: $X$ is compact iff every collection of closed sets in $X$ having FIP has non-empty intersection. Let us look at the collection $\mathcal{S}:=\lbrace p_A^{-1}(A)\mid A\in C\rbrace$ Given $A_1,\ldots, A_n\in C$ pick an element $a_i\in A_i$ since $A_i\ne \varnothing$ by assumption. Note that this is possible, since there are only a finite number of sets. Define $f:D\to \bigcup D$ as follows:

    \begin{displaymath} % latex2html id marker 266f(X_A):= \left\{ \begin{array}{l... ... }i=1,\ldots, n,\ A & \textrm{otherwise.} \end{array}\right. \end{displaymath}
    Since $f(X_{A_i})=a_i \in A_i$ $f\in p_{A_i}^{-1}(A_i)$ for each $i=1,\ldots, n$ Therefore, $$f\in p_{A_1}^{-1}(A_1) \cap \cdots \cap p_{A_n}^{-1}(A_n).$$ Since $p_{A_1}^{-1}(A_1), \ldots, p_{A_n}^{-1}(A_n)$ are arbitrarily picked from $\mathcal{S}$ the collection $\mathcal{S}$ has finite intersection property, and since $X$ is compact, $Z=\bigcap S$ must be non-empty.
This completes the proof. $ \qedsymbol$

Remark. In the proof, we see that the trick is to adjoin the set $\lbrace A\rbrace$ to each set $A\in C$ Instead of $\lbrace A\rbrace$ we could have picked some arbitrary, but fixed singleton $\lbrace B\rbrace$ as long as $B\notin A$ for each $A\in C$ and the proof follows essentially the same way.

Bibliography

1
T. J. Jech, The Axiom of Choice. North-Holland Pub. Co., Amsterdam, 1973.
2
J. L. Kelley, The Tychonoff's product theorem implies the axiom of choice. Fund. Math. 37, pp. 75-76, 1950.




"Tychonoff's theorem implies AC" is owned by CWoo.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: fixed, completes, finite intersection property, characterization, closed, open, continuous, product topology, number, cover, covering, subset, finite, open cover, cofinite, empty set, open set, singleton, cofinite topology, topology, compact, inverse, bijection, easy to see, well-defined, conversely, iff, function, equipollent, onto, projection, generalized Cartesian product, collection, set theory, axiomatic, proof, ZF, axiom of choice, equivalent, product of non-empty set of non-empty sets is non-empty, implies, Tychonoff's theorem
There is 1 reference to this entry.

This is version 4 of Tychonoff's theorem implies AC, born on 2009-01-23, modified 2009-01-23.
Object id is 11540, canonical name is TychonoffsTheoremImpliesAC.
Accessed 626 times total.

Classification:
AMS MSC54D30 (General topology :: Fairly general properties :: Compactness)
 03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)