22 Sep 2017  0

In PMATH351 F17, I was (re)introduced to the Axiom of Choice. The following is my understanding and interpretation, or at least my attempt at interpreting the axiom, and other statements that are equivalent to it.

Axiom of Choice (AC)

{Ai}iI  AiiIAi\forall \{A_i\}_{i \in I} \; A_i \neq \emptyset \quad \prod_{i \in I} A_i \neq \emptyset

which says that for a family of non-empty sets, the Cartesian product of all such sets is non-empty.

An alternative definition was given with the use of the choice function:

Axiom of Choice (AC’)

Xf:P(X){}XAP(X){}f(A)AX \neq \emptyset \quad \exists f:\mathcal{P}(X) \setminus \{\emptyset\} \to X \quad \forall A \in \mathcal{P}(X) \setminus \{\emptyset\} \quad f(A) \in A

which says that given a non-empty set XX, there exists a choice function ff that maps from the power set of XX less the empty set to XX itself, such that for all such sets in the domain, their images are themselves.

What may be interesting in the alternative definition (hereafter referred to as AC’), the image set of A is an element of itself instead of being a subset or the set itself.

Without further probing on such a weird question, notice that this definition makes sense if we believe that the axiom of choice states, in layman terms, that for any number of non-empty sets, we may pick an element from each set. In this case, the choice function acts as our “way” of picking the element.

The following is a prove of the two statements.


For (AC)    (AC)(AC) \implies (AC'), since iIAi\prod_{i \in I} A_i \neq \emptyset,

(xA)AP(X){}AP(X){}A\exists (x_A)_{A \in \mathcal{P}(X)\setminus\{\emptyset\}} \in \prod_{A \in \mathcal{P}(X)\setminus\{\emptyset\}} A

Thus we can just choose f(A)=xAf(A) = x_A.

For (AC)    (AC)(AC') \implies (AC),

X=iIAif:P(X){}X    ((f(Ai))iIiIAiX = \bigsqcup_{i \in I} A_i \quad f: \mathcal{P}(X) \setminus \{\emptyset\} \to X \implies \Big( (f(A_i) \Big)_{i \in I} \in \prod_{i \in I} A_i


Before going further to the other equivalent statements, we name the following definition:

Chain: Let (X,)(X, \leq) be a partially ordered set. A chain is a set SXS \subset X such that SS has a total order, i.e. x,yS\forall x, y \in S, either xyx \leq y, or x\leq x and not both.


The Axiom of Choice is also equivalent to 3 other statements, namely:

Haussdorff’s Maximality Principle (HMP)

In any partially ordered set (S,)(S, \leq ), there is a maximal chain , i.e. a chain MM such that no M{s}M \cup \{s\} is a chain for any SMS \setminus M.

Zorn’s Lemma (ZL)

Let (X,)(X, \leq) be a partially ordered set. If every chain in (X,)(X, \leq) has an upper bound, then there is a maximal mXm \in X, i.e. sS  ms    m=s\forall s \in S \; m \leq s \implies m = s.

Well-Ordering Principle (WOP)_

Any non-empty set XX has a well order, i.e. =SX  sS  tS  st\forall \emptyset = S \subseteq X \; \exists s \in S \; \forall t \in S \; s \leq t, or in words, any subset of X has a minimal element.

This page is still incomplete

- Japorized -

Comments

There are currently no comments.
Comments have been disabled across the site.