2
$\begingroup$

Let $F$ be a set of nonempty sets. A set $R\subseteq\cup F$ is said to be a system of distinct representatives (SDR) of for every $B\in F$ there exists unique $x\in R$ such that $x\in B$ and $\forall C \in F[C\not =B\rightarrow x\not\in C]$

Using Hall's theorem one can show that every finite set of finite sets $F=\{B_1,B_2,...,B_k\}$ has a system of distinct representatives iff $\forall G\subseteq F[|G|\leq|\cup G|]$.

Does this hold if $F$ is infinite ?

Thanks

  • 0
    You are right I should add this2012-12-16

1 Answers 1

2

Assuming the axiom of choice the answer is yes. However there are models in which the axiom of choice fails and Hall's theorem fails as well.

The full theorem would be:

Let $F=\{S_i\mid i\in I\}$ be a collection of (non-empty) finite subsets of some $X$. Then there exists an injective choice function from $F$ if and only if there is an injective choice function for every finite $A\subseteq F$.

Interestingly enough, a different mathematician named Hall proved that the condition on "finite injectivity" is equivalent to the following: $|F|\leq\left|\bigcup_{i\in I} S_i\right|$

The equivalence holds without the axiom of choice.

It is not hard to use the compactness theorem in order to prove the statement in the full theorem. Let $T$ be a certain theory which asserts the injectivity of the choice function, and by compactness it would be consistent that every finite fragment is consistent and therefore we can "glue" it together.


Also relevant: Hall's theorem vs Axiom of Choice?