A colleague is refereeing a paper in which the following lemma appears implicitly:

For any family $\mathcal G$ of nonempty sets let us call a set $B$ a "selector" if $B$ meets all $F\in\mathcal G$.

Lemma: For every family $\mathcal G$ of nonempty finite sets there is a minimal selector $B$. (That is, for all $x$ in $B$ there is at least one $F$ in $G$ such that $x$ is the unique element of $B\cap F$.)

A proof is quite easy: The family of selectors is closed under intersections of chains, so there must be a minimal element (using Zorn's lemma in a version that is dual to the common one).

I would like to know

  1. if the lemma is well known, and/or has a name;
  2. if the concepts used (selector, minimal selector) have some other (established) name.

(This is a request for references. I will post a mathematical question separately, once I know the terminology.)

I could not find this property in Howard-Rubin's "Consequences of the axiom of choice" but I admit I am not very experienced in using this book, so I may have overlooked something.

  • 1
    $\begingroup$ I'm sure that you already know that, but to make it clear to others reading this: the need of the axiom of choice is essential. Consider a set pairs that has no choice function (e.g. a partition of a Russell set). This set does not have a minimal selector (as that would constitute of a choice function). $\endgroup$ – Asaf Karagila Jul 4 '12 at 19:52
  • $\begingroup$ Yes, it certainly implies choice for finite sets. See mathoverflow.net/questions/101348/… for 2 questions on this topic. $\endgroup$ – Goldstern Jul 4 '12 at 22:42

I think "selector" usually refers to choosing just one element from each set in a family. For the concept you described here, I've seen names like "blocker" or "blocking set", but I haven't seen them so often that I'd call them standard.

The blockers of a family of finite sets (all included in some big set $X$) obviously constitute an upward-closed family of subsets of $X$, and this family is closed in the usual product topology of the power set of $X$. Conversely (and not quite so obviously), every upward-closed, topologically-closed family of subsets of $X$ is the family of blockers of some family of finite subsets of $X$. Unfortunately, I don't recall ever having seen these facts explicitly written down in the literature.

Note that the existence of a minimal blocker for a family of finite sets is a consequence of the fact that any topologically-closed subfamily of the power set of $X$ has a minimal element.


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.