Minimal transversal for family of finite sets

226 Views Asked by At

Consider the statement: Every family of non-empty finite sets has a minimal transversal - a set that intersects every element of the family and no strict subset of it has this property.

Is it true that this statement is equivalent with the axiom of choice? Clearly Zorn's lemma implies it. But what about vice verse... or something else?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, even the statement "every family of $2$-element sets has a minimal transversal" is equivalent to the axiom of choice. Let's use it to prove that every partially ordered set has a maximal chain.

Let $P$ be any partially ordered set. Let $\mathcal A$ be the set of all $2$-element antichains in $P,$ i.e., all sets $\{x,y\}\subseteq P$ such that $x\not\le y$ and $y\not\le x.$ If $T$ is a minimal transversal for $\mathcal A,$ then $P\setminus T$ is a maximal chain in $P.$

Alternatively, let's use your statement to prove that every family $\mathcal F$ of disjoint nonempty sets has a selector. Let $$\mathcal A=\bigcup_{X\in\mathcal F}\binom X2,$$ the collection of all $2$-element sets that are contained in some member of $\mathcal F.$ If $T$ is a minimal transversal for $\mathcal A,$ then $T$ contains all but one element of each member of $\mathcal F,$ so the complement $\bigcup\mathcal F\setminus T$ contains exactly one element of each member of $\mathcal F.$