3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Well if the finite sets in question are disjoint, such a "minimal transversal" would clearly intersect each of them in at most one point (otherwise remove one, and since they are disjoint, you get a strictly smaller -in terms of inclusion- transversal), and so this axiom is equivalent to choice for finite sets, which is (as I recall) not equivalent to full choice $\endgroup$ – Max Apr 27 '17 at 9:11
  • $\begingroup$ @Max You have shown that a special case of OP's statement (the case where the given family consists of disjoint sets) is equivalent to a weak form of choice. $\endgroup$ – bof Apr 27 '17 at 9:45
  • $\begingroup$ @bof : I had thought for a second that the general case could be recovered from this special case $\endgroup$ – Max Apr 27 '17 at 10:48
2
$\begingroup$

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.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.