Are the theorems of P. Hall and M. Hall equivalent?

Question

Let $A$ be a set together with and indexed collection $\{A_{i}:i\in I\}$ of (not necessarily distinct) subsets of $A$.

A system of distinct representatives of $\{A_{i}:i\in I\}$ is a collection of elements $a_{i}\in A_{i}$ for each $i\in I$ such that, $a_{i}\neq a_{j}$ whenever $i\neq j$.

Phillip Hall's theorem (PH) - [P. Hall, On representatives of subsets, J.London Math. Soc. vol. 10, pp. 26-30 (1935)] is the following statement:

Let $A$ be any set (possibly infinite) together with a finite collection $\mathcal{A} = \{A_{1},\ldots,A_{n}\}$, $n\in\mathbb{N}$, of subsets of $A$. Then a necessary and sufficient condition for the existence of a system of distinct representatives is:

• (Condition H) For each $1\leq k\leq n$, any choice of $k$ of the sets in $\mathcal{A}$ contains between them at least $k$ elements of $A$. That is, for every choice of $k$ distinct indices $1\leq i_{1},\ldots,i_{k}\leq n$, $|A_{i_{1}}\cup\ldots\cup A_{i_{k}}|\ge k$.

The folklore statement goes as follows: If there are $n$ women $\{1,\ldots,n\}$, each with a set $A_{i}$ of men they like (i.e. $A_{i}$ is the set of possible matches of woman $i$), there is a way to give all of them distinct husbands they like if and only if condition H holds. That is, if and only if any $k$ women like at least $k$ different men.

Marshall Hall's theorem (MH) - [M. Hall, Distinct representatives of subsets, Bull. Amer. Math. Soc. 54(10), pp. 922-926 (1948). Also Chapter 5 of M. Hall's book "Combinatorial Theory", 2nd. ed. John Wiley & Sons, 1986 has both theorems. They are Theorem 5.1.1 (P. Hall) and Theorem 5.1.2 (M. Hall), respectively.] is the following statement:

Let $A$ be any set (possibly infinite) together with a (possibly infinite) collection $\mathcal{C} = \{A_{i}:i\in I\}$ of finite subsets of $A$. Then a necessary and sufficient condition for the existence of a system of distinct representatives is:

• (Condition H*) For each $k\ge 1$, any choice of $k$ of the sets in $\mathcal{C}$ contains between them at least $k$ elements of $A$. That is, for every choice of $k$ distinct indices $i_{1},\ldots,i_{k}\in I$, $|A_{i_{1}}\cup\ldots\cup A_{i_{k}}|\ge k$.

The folklore statement goes as follows: If there is a (possibly infinitely) set of women $I$, each with a finite set $A_{i}$ of men they like (i.e. $A_{i}$ is the finite set of possible matches of woman $i$), there is a way to give all of them distinct husbands they like if and only if condition H* holds. That is, if and only if any $k$ women like at least $k$ different men.

Note: These theorems have widespread graph theoretic formulations. See R. Diestel's book "Graph Theory", for example.

Are PH and MH equivalent statements over $\mathsf{ZF}+\mathsf{BPI}$? (where $\mathsf{BPI}$ denotes the Boolean Prime Ideal Theorem, which is equivalent over $\mathsf{ZF}$ to propositional compactness)

Answer 1

In order to remove the question from the unanswered list I will post what I found out.

They are not equivalent over $\mathsf{ZF}$ since PH does not require any choice principle, while MH requires some form of choice. For example, MH implies $\mathsf{AC}_{\text{fin}}$, the axiom of choice for families of finite sets (see Theorem 2.3 in E. Tachtsis, Dilworth's decomposition theorem for posets in $\mathsf{ZF}$, Acta Math. Hungar. 159, p.603–617, 2019)

1. MH is equivalent (via the compactness theorem for propositional logic or Tychonoff's product theorem for compact Hausdorff spaces, for example - all equivalent to the Boolean prime ideal theorem $\mathsf{BPI}$ over $\mathsf{ZF}$) to the statement of MH with $I$ finite. That is, when the collection $\mathcal{C}$ in the statement of MH is finite (in which case condition H* is simply condition H). Let us call the modified statement MHF [See Paul R. Halmos and Herbert E. Vaughan, The marriage problem, American Journal of Mathematics, Vol. 72, No. 1, pp. 214-215 (1950) for a proof of MH. They use induction on the size of $I$ when the index set is finite, and Tychonoff's theorem when $I$ is infinite].
2. PH is equivalent to the statement of PH when each of the sets in the collection $\mathcal{A}$ is finite (which would be the case, when the set $A$ in the statement of PH is finite). Let us call the modified statement PHF.
3. PHF is clearly equivalent to MHF.

Therefore, it is enough to prove PHF, in fact, enough to prove PH for the case of $A$ finite, which can be done by induction on the cardinality of $A$. (Although this does not seem to be any simpler than proving PH directly by induction of size $n$ of the collection $\mathcal{A}$, or via Dilworth's theorem).

Perhaps there is a better way to express the equivalence of PH and MH.

Note: This has a nice exposition on the relationship between MH and the axiom of choice.