From Wikipedia
Let $S$ be a family of finite sets, where the family may contain an infinite number of sets and the individual sets may be repeated multiple times.
A transversal for $S$ is a set $T$ and a bijection $f$ from $T$ to $S$ such that for all $t$ in $T$, $t$ is a member of $f(t)$. An alternative term for transversal is system of distinct representatives or "SDR".
The collection $S$ satisfies the marriage condition (MC) if and only if for each subcollection $W \subseteq S$, we have $$ |W| \le \Bigl|\bigcup_{A \in W} A\Bigr|. $$ In other words, the number of sets in each subcollection W is less than or equal to the number of distinct elements in the union over the subcollection W.
Hall's theorem states that $S$ has a transversal (SDR) if and only if $S$ satisfies the marriage condition.
The more general problem of selecting a (not necessarily distinct) element from each of a collection of sets (without restriction as to the number of sets or the size of the sets) is permitted in general only if the axiom of choice is accepted.
What relations and differences are between Hall's thoerem and Axiom of Choice?
- Is their only difference that hall's theorem require $S$ to be a family of finite sets, while Axiom of Choice allows $S$ to be a family of arbitrary sets?
- What does "selecting a (not necessarily distinct) element" mean?
- I was wondering if the correctness of Hall's theorem assumes Axiom of Choice?
- What is the difference between transversal and a choice function? Are they the same concept?
Thanks!