show/hide this revision's text 3 +addendum

Addendum (Adam Bjorndahl):

This construction can be viewed as a generalization of the quantifier duality$$\forall \equiv \lnot \exists \lnot.$$

As above, fix a set $X$. For $F \subseteq 2^{X}$, define the formula $(\text{F}x) \ \phi(x)$ to mean that$$\{x \in X : \phi(x)\} \in F.$$So $(\text{F}x) \ \phi(x)$ might be read "for $F$-many $x$, property $\phi$ holds". Three special cases deserve some attention.

  • When $F = \{X\}$, we recover the usual "for all" quantifier. Succinctly, $\forall = \{X\}$.

  • Dualizing, we obtain$$\lnot (\text{F}x) \lnot \phi(x) \iff \{x \in X : \lnot \phi(x)\} \notin F;$$thus if $A = \{x \in X : \phi(x)\}$, we have$$\lnot (\text{F}x) \lnot \phi(x) \iff A \in F^{*} \iff (\text{F}^{*}x) \phi(x),$$where $F^{*}$ is the blocker of $F$.

  • Finally, if $U \subset 2^{X}$ is an ultrafilter on $X$, then$$\lnot (\text{U}x) \lnot \phi(x) \iff (\text{U}x)\phi(x),$$which exhibits ultrafilters as self-dual quantifiers, a perspective I find appealing.

    		•
    show/hide this revision's text 2 fixed typo

    A very simple and important notion of duality is the following.

    Start with a collection $F$ of subsets of a ground set $X$.

    Now, define the blocker $F^*$ of $F$ as follows:

    $F^*=${$ X \backslash A: A \notin F $}.

    In words, we take the complements of all sets not in $F$.

    This notion is very important in combinatorial optimization and polyhedral combinatorics. It is also a simple manifestation of Alexabder Alexander duality from algebraic topology.
    show/hide this revision's text 1 [made Community Wiki]

    A very simple and important notion of duality is the following.

    Start with a collection $F$ of subsets of a ground set $X$.

    Now, define the blocker $F^*$ of $F$ as follows:

    $F^*=${$ X \backslash A: A \notin F $}.

    In words, we take the complements of all sets not in $F$.

    This notion is very important in combinatorial optimization and polyhedral combinatorics. It is also a simple manifestation of Alexabder duality from algebraic topology.