4
$\begingroup$

I am trying to understand the relationship between two forms of the axiom of choice:

  1. If $T=\{X_0,X_1\cdots \}$ is a family of non-empty mutually disjoint finite sets, then $\cup T$ contains at least one subset having exactly one element in common with each element of $T$.

  2. Let $X\ne\emptyset$ be countable and $\mathcal{F}(X)$ be the collection of all finite subsets of it. Then there is a function $f:\mathcal{F}(X)-\emptyset\to X$ such that $f(x)\in x\forall x\in \mathcal{F}(X)-\emptyset$.

Which one implies the other? What will be the formulation of 1. in terms of the choice function?

Thanks.

Follow up question: If in (2) the condition $X\ne\emptyset$ is countable is removed, i.e. $X$ is an arbitrary nonempty set then will it imply (1)?

2 Answers 2

7

First note that $\mathcal F(X)$ can be transformed to a disjoint family, $\{\{x\}\times x\mid x\in\mathcal F(X)\}$. Now assuming the first principle is true a transversal set (meeting each set at one point) is in fact a function choosing from each $x\in\mathcal F(X)$.

Therefore the first implies the second.

On the other hand, note that if $X$ is countable then $\mathcal F(X)$ has a definable choice function: fix a bijection of $X$ with $\omega$ and choose from $x\in\mathcal F(X)$ the least element in this enumeration. However the first cannot be proved without some axiom of choice. In fact it is possible to have a countable set of disjoint pairs which has no choice function.

To your final question, the set meeting each set is exactly $\operatorname{rng}(f)$ of a choice function $f$ from the family of your sets.


Addressing your edit, yes. If we remove the requirement that $X$ is countable then the two propositions are equivalent. To see this, let $X=\bigcup T$, then $T\subseteq\mathcal F(X)$. A choice function on $\mathcal F(X)$ will give us a choice function on $T$ in return.

6

The second statement is true in ZF: it requires no choice at all. If $X$ is countable, there is a bijection $\varphi:X\to\alpha$ for some $\alpha\le\omega$, and of course if $X\ne\varnothing$, then $\alpha>0$. Then

$f:\mathcal{F}\setminus\{\varnothing\}\to X:x\mapsto\min\varphi[x]$

has the desired property.