502 – Equivalents of the axiom of choice

November 11, 2009

The goal of this note is to show the following result:

Theorem 1 The following statements are equivalent in {{\sf ZF}:}

  1. The axiom of choice: Every set can be well-ordered.
  2. Every collection of nonempty set admits a choice function, i.e., if {x\ne\emptyset} for all {x\in I,} then there is {f:I\rightarrow\bigcup I} such that {f(x)\in x} for all {x\in I.}
  3. Zorn’s lemma: If {(P,\le)} is a partially ordered set with the property that every chain has an upper bound, then {P} has maximal elements.
  4. Any family of pairwise disjoint nonempty sets admits a selector, i.e., a set {S} such that {|S\cap x|=1} for all {x} in the family.
  5. Any set is a well-ordered union of finite sets of bounded size, i.e., for every set {x} there is a natural {m,} an ordinal {\alpha,} and a function {f:\alpha\rightarrow{\mathcal P}(x)} such that {|f(\beta)|\le m} for all {\beta<\alpha,} and {\bigcup_{\beta<\alpha}f(\beta)=x.}
  6. Tychonoff’s theorem: The topological product of compact spaces is compact.
  7. Every vector space (over any field) admits a basis.

Read the rest of this entry »

Advertisement

2 Comments | 502: Logic and set theory | Tagged: , , , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Some choiceless results (4)

January 29, 2009

Let me begin with a remark related to the question of whether \aleph(X)\preceq {\mathcal P}^2(X). We showed that this is the case if X\sim Y^2 for some Y, or if X is Dedekind-finite.

Theorem. The axiom of choice is equivalent to the statement that any Dedekind-infinite cardinal is a square.

Proof. Let X be a set. Assuming that every D-infinite cardinal is a square, we need to show that X is well-orderable. We may assume that \omega\preceq X. Otherwise, replace X with X\cup\omega. Let \kappa=\aleph(X). Assume that X\sqcup\kappa is a square, say X\sqcup\kappa\sim Y^2. Then \kappa\preceq Y^2. By Homework problem 2, \kappa\preceq Y, so Y\sim \kappa\sqcup Z for some Z, and X\sqcup \kappa\sim Y^2\sim\kappa^2\sqcup 2\times\kappa\times Z\sqcup Z^2\succeq\kappa\times Z.

Lemma. Suppose A,B,C are D-infinite sets and \lambda is an (infinite) initial ordinal. If \lambda\times A\preceq B\cup C then either \lambda\preceq B or A\preceq C.

Proof. Let f:\lambda\times A\to B\sqcup C be an injection. If there is some a\in A such that f(\cdot,a):\lambda\to B we are done, so we may assume that for all a\in A there is some \alpha\in\lambda such that f(\alpha,a)\in C. Letting \alpha_a be the least such \alpha, the map a\mapsto f(\alpha_a,a) is an injection of A into C. {\sf QED}

By the lemma, it must be that either \kappa\preceq X or else Z\preceq\kappa. The former is impossible since \kappa=\aleph(X), so Z is well-orderable, and thus so is Y, and since Y\sim Y^2\succeq X, then X is well-orderable as well. {\sf QED}

Read the rest of this entry »

2 Comments | 580: Topics in set theory | Tagged: , , , | Permalink
Posted by andrescaicedo