Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.