Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In this question I asked for a reference for the following lemma:

Lemma X: For every family $\mathcal G$ of nonempty finite sets there is a minimal "blocking set" $B$. By a "blocking set" $B$ I mean a set which meets each $F\in\mathcal G$, and "minimal" refers to the subset relation.

Questions:

  1. What is the exact strength (or approximate strength) of this lemma in the hierarchy of consequences of AC? Clearly it implies that for every family of finite sets there is a choice function (as the finite sets can easily be made disjoint, and for a disjoint family a minimal blocking set is the same as a choice function.)
    In particular, is lemma X equivalent to AC for families of finite sets? Or does it at least follow from the (stronger) ordering principle? Or at least from the (even stronger) Prime Ideal Theorem?

  2. Is there a natural condition on $\mathcal G$ which is weaker than "all elements of $\mathcal G$ are finite", but still implies the conclusion of the lemma above?

share|improve this question
    
Is "all elements of G are disjoint" weaker than "all elements of G are finite"? –  Gerry Myerson Jul 4 '12 at 23:02
add comment

2 Answers

up vote 6 down vote accepted

This is only a partial answer: If you assume (with notation as in the question) that every point is in only finitely many sets from $\mathcal G$, then the existence of a minimal blocking set follows from the Boolean prime ideal theorem (BPI). One way to see this is via the compactness theorem for propositional logic (which is equivalent to BPI), applied to the following situation. Let there be a propositional variable $\hat p$ for each point $p$ in the union of the family $\mathcal G$, and let $S$ be the set of the following sentences. First, for each $F\in\mathcal G$, the disjunction of the $\hat p$'s for $p\in F$ is in $S$. Second, $S$ contains, for each $p$, the implication $$ \hat p\implies\bigvee_{F:p\in F\in\mathcal G} \bigwedge_{q\in F-\{p\}}\neg\hat q$$ A truth assignment satisfying $S$ yields a minimal blocking set, namely the set of those $p$ whose $\hat p$ is assigned the value true. (The displayed implication serves to ensure that, for each such $p$, there is a set in $\mathcal G$ containing it and no other element of the blocking set, so we get minimality.) Every finite subset of $S$ is satisfiable, essentially because finite families have minimal blocking sets. So compactness gives a satisfying assignment for $S$ and thus a minimal blocking set for the whole $\mathcal G$.

Unfortunately, if we drop the hypothesis that each $p$ is in only finitely many sets from $\mathcal G$, then this argument breaks down, because the disjunction in the displayed implication becomes an infinite disjunction, and there is no compactness theorem for such infinitary sentences.

EDIT: Here's a better partial answer, in the opposite direction. In set theory with atoms, BPI does not imply that every family of nonempty finite sets has a minimal blocking set. Specifically, in Mostowski's linearly ordered model, which is known to satisfy BPI (a theorem of Dan Halpern), the following family of finite, nonempty sets has no minimal blocker. Start with the disjoint union of countably many copies of the set $A$ of atoms, i.e., start with $\omega\times A$. Let $\mathcal G$ consist of all the $(n+1)$-element subsets of the $n$-th copy $\{n\}\times A$ for all $n\in\omega$. A minimal blocking set for this $\mathcal G$ would have to consist of (exactly) all but $n$ elements of the $n$-th copy, for all $n$. But no such set has finite support and therefore no such set is in the model.

share|improve this answer
add comment

Dear Martin: I think you can easily extend the result for systems of infinite sets, where there is a set $A$ intersecting all sets in finitely many but at least 1 point. The latter property was investigated by Erdos and Hajnal in On a property of families of sets, Acta Math. Acad. Sci. Hungar. 12 (1961), 87--123, see http://www.renyi.hu/~p_erdos/1961-11.pdf Perhaps I also had some papers on this. Does this make any sense?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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