Equivalent to the Axiom of Choice

116 Views Asked by At

I'm trying to prove that the following statements are equivalent:

  1. Axiom of Choice: For all family of non-empty sets, $\mathcal{F}$, there exists a choice function $f$ such that $f(X)\in X$, for all $X\in\mathcal{F}$.

  2. If $\mathcal{F}$ is a family of pairwise disjoint sets, then there exists $M$ such that $M\cap X$ is a singleton, for all $X\in \mathcal{F}$.

I have proved 1) implies 2), but with the other implication I'm having some problems.

If $\mathcal{F}$ is a family of non-empty sets, I construct the family $\mathcal{F}'=\{\{X\}\times X : X\in\mathcal{F} \}$, whose elements are pairwise disjoints. Now, I can apply 2) to this new family $\mathcal{F}'$, so there exists $M$ such that $M\cap(\{X\}\times X)$ is a singleton, for all $X\in\mathcal{F}$, but now I don't know how to continue and pick a choice function for $\mathcal{F}$.

1

There are 1 best solutions below

1
On BEST ANSWER

To show 2 implies 1, consider the set $\sum\limits_{x \in F} x$, which is defined as $\{(x, y) | x \in F, y \in x\}$ (this set exists, since it is a subset of $F \times \cup F$). For each $x \in F$, define $x'$ to be $\{(x, y) | y \in x\}$. Then the set $\{x' | x \in F\}$ exists (either using powerset + separation or replacement) and is a disjoint family of sets.

Then take a set $M$ such that for all $x \in F$, $M \cap x'$ is a singleton. Then define a function $f$ with domain $F$ and codomain $\cup \{x' | x \in F\}$ by $f(x) = $ the unique element of $M \cap x'$.

Now clearly, for all $x$, $f(x)$ is a pair of the form $(x, y)$. So define a function $g$ with domain $F$ and codomain $\cup F$ by $g(x) = $ the unique $y$ such that $(x, y) = f(x)$.

Then $g$ is a choice function.