Hall's theorem vs Axiom of Choice?

Question

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?

1. 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?
2. What does "selecting a (not necessarily distinct) element" mean?
3. I was wondering if the correctness of Hall's theorem assumes Axiom of Choice?
4. What is the difference between transversal and a choice function? Are they the same concept?

Thanks!

Answer 1

In the dictionary of choice principles you can find Hall's marriage theorem as Form 107. It can be checked quickly that there are models in which this theorem does not hold. Therefore the theorem is not provable without the axiom of choice, and it may fail.

However the theorem follows from the Boolean Prime Ideal Theorem (Form 14) which is an equivalent to many useful theorems, e.g. Ultrafilter Theorem/Stone Representation Theorem/etc., note that these principles are weaker than the axiom of choice.

Interestingly (albeit expectedly), Hall's theorem proves the axiom of choice for families of finite sets (Form 62). It is not know whether the implication can be reversed, or if the previous implication can be reversed (however it is impossible for both to be reversed, Boolean prime ideal theorem is strictly stronger than the axiom of choice for families of finite sets).

The above shows that Hall's theorem is quite weak compared to the axiom of choice. Hall's theorem allows us to choose one element from every set, and it tells us when we can make a choice which is distinct, namely if two sets are different then their chosen element is different as well. The axiom of choice, however, permits the case where the choice function is constant (although this usually don't require the axiom of choice).

This is also the difference between selecting an element from every non-empty set, and selecting distinct elements from distinct sets.

Lastly, for your last question a transversal set (as described above) meets every set exactly once and different sets are met with different elements; whereas a choice function may choose the same elements from different sets. Of course if we require the family of have disjoint elements then a transversal set is exactly the range of a choice function, and vice versa. However if $\{A_i\mid i\in A\}$ is a family of sets, $\{\{i\}\times A_i\mid i\in I\}$ is a family of disjoint sets, and a transversal set is exactly a choice function.

Answer 2

I’ll leave (1) and (3) for Asaf, who will doubtless be along shortly.

(2) Suppose that $S=\big\{\{0,1\},\{1,2\}\big\}$; then the function $f:T_0=\{0,1\}\to S$ defined by $f(0)=\{0,1\},f(1)=\{1,2\}$ is a transversal for $S$. So are the functions $g:T_1=\{0,2\}\to S$ defined by $g(0)=\{0,1\},g(2)=\{1,2\}$ and $h:T_2=\{1,2\}\to S$ defined by $h(1)=\{0,1\}$, $h(2)=\{1,2\}$. Each of these functions is a bijection, and the inverse of each is a choice function that selects one element from each of the sets $\{0,1\}$ and $\{1,2\}$. For example, $f^{-1}\big(\{0,1\}\big)=0\in\{0,1\}$ and $f^{-1}\big(\{1,2\}\big)=1\in\{1,2\}$.

But each of these inverse functions does more than select one representative from each of the sets in $S$: they select different representatives from different sets. The function $c:S\to\{0,1,2\}$ defined by $c\big\{0,1\}\big)=c\big\{1,2\}\big)=1$ is a choice function for $S$, but it does not select distinct representative from the sets $\{0,1\}$ and $\{1,2\}$; rather, it selects the same object, $1$, as the representative for each of the sets.

(4) The differences between a transversal and a choice function are illustrated by the example above. The first difference is purely formal: a choice function for a family $\mathscr{S}$ of non-empty sets is a function $c$ from $\mathscr{S}$ to $\bigcup\mathscr{S}$ such that $c(S)\in S$ for each $S\in\mathscr{S}$, while a transversal (as defined in the Wikipedia article) is a function $f$ from a subset $T$ of $\bigcup\mathscr{S}$ to $\mathscr{S}$ such that $t\in f(t)$ for each $t\in T$. That is, the functions go in opposite directions. The important difference, though, is that a choice function can pick out the same object from many different sets, while a transversal must pick different elements from different sets.