Cowen-Engeler Lemma

From ProofWiki
Jump to: navigation, search


Let $X$ and $Y$ be sets.

Let $M$ be a set of mappings from subsets of $X$ to $Y$.

Thus each element of $M$ is a partial mapping from $X$ to $Y$.

Define a mapping $\Phi: X \to \mathcal P \left({Y}\right)$ thus:

$\Phi \left({x}\right) = \left\{{f \left({x}\right): f \in M \text{ and } x \in \operatorname{Dom} \left({f}\right) }\right\}$

That is:

$\Phi \left({x}\right) = \left\{{y \in Y: \exists f \in M: \left({x, y}\right) \in f}\right\}$

Suppose that the following hold:

\((1)\)   $:$   $\Phi \left({x}\right)$ is finite for each $x \in X$.             
\((2)\)   $:$   For each finite subset $F$ of $X$, there exists an element $f \in M$ such that the domain of $f$ is $F$.             
\((3)\)   $:$   $M$ has finite character.             
That is, a mapping $f$ from some subset of $X$ to $Y$ is an element of $M$ if and only if its restriction to each finite subset of $\operatorname{Dom} \left({f}\right)$ is in $M$.             

Then there exists an element of $M$ with domain $X$.


Let $\operatorname{Fin} \left({X}\right)$ be the set of finite subsets of $X$.

For each $S \in \operatorname{Fin} \left({X}\right)$, let $\Gamma_S = \left\{{f \in M: S \subseteq \operatorname{Dom} \left({f}\right)}\right\}$.

By $(2)$, $\Gamma_S$ is non-empty for each $S \in \operatorname{Fin} \left({X}\right)$.

For each $S \in \operatorname{Fin} \left({X}\right)$, $\Gamma_S \cap \Gamma_T = \Gamma_{S \cup T}$:

If $f \in \Gamma_{S \cup T}$, then $S \cup T \subseteq \operatorname{Dom} \left({f}\right)$.

Then $S \subseteq \operatorname{Dom} \left({f}\right)$ and $T \subseteq \operatorname{Dom} \left({f}\right)$, so $f \in \Gamma_S$ and $f \in \Gamma_T$.

Thus $f \in \Gamma_S \cap \Gamma_T$.

If $f \in \Gamma_S \cap \Gamma_T$, then $f \in \Gamma_S$ and $f \in \Gamma_T$.

Thus $S \subseteq \operatorname{Dom} \left({f}\right)$ and $T \subseteq \operatorname{Dom} \left({f}\right)$.

Thus $S \cup T \subseteq \operatorname{Dom} \left({f}\right)$.

So $f \in \Gamma_{S \cup T}$.

Thus $\left\{ {\Gamma_S: S \in \operatorname{Fin} \left({X}\right)}\right\}$ has the finite intersection property.

Then by the corollary to the Ultrafilter Lemma, there is an ultrafilter $\mathcal U$ on on $M$ which includes $\left\{ {\Gamma_S: S \in \operatorname{Fin} \left({X}\right) }\right\}$ as a subset.

We will now construct a mapping $\phi: X \to Y$.

Fix $x \in X$.

Note that by the definitions of $\Phi$ and $\Gamma$:

$\Phi \left({x}\right) = \left\{ {f \left({x}\right): f \in \Gamma_{\left\{{x}\right\} } }\right\}$

For each $y \in \Phi \left({x}\right)$, let $K_y = \left\{ {f \in \Gamma_{\left\{{x}\right\} } : f \left({x}\right) = y }\right\}$.

Then $\left\{ {K_y : y \in \Phi \left({x}\right) }\right\}$ is a partition of $\Gamma_{\left\{{x}\right\} }$.

Since $\left\{{x}\right\} \in \operatorname{Fin} \left({X}\right)$:

$\Gamma_{\left\{{x}\right\} } \in \mathcal U$

By $(1)$, $\Phi \left({x}\right)$ is finite.

Thus by Component of Finite Union in Ultrafilter, there is exactly one $y \in \Phi \left({x}\right)$ such that $K_y \in \mathcal U$.

We define $\phi \left({x}\right)$ to be that $y$.

By the definition of $K_y$, for each $x \in X$ we have:

$\left\{ {f \in \Gamma_{\left\{{x}\right\} } : f \left({x}\right) = \phi \left({x}\right) }\right\} \in \mathcal U$

We must show that $\phi \in \mathcal M$.

Let $S$ be a finite subset of $X$.

Let $\displaystyle \Psi = \bigcap_{x \mathop \in S} \left\{ {f \in \Gamma_{\left\{{x}\right\} } : f \left({x}\right) = \phi \left({x}\right) }\right\}$.


$\left\{ {f \in \Gamma_{\left\{{x}\right\} } : f \left({x}\right) = \phi \left({x}\right) }\right\} \in \mathcal U$ for each $x \in X$
$S$ is finite
$\mathcal U$ is a filter

it follows that:

$\Psi \in \mathcal U$

Thus $\Psi \ne \varnothing$.

Choose any $f \in \Psi$.

Then $f \left({x}\right) \in \Gamma_{\left\{{x}\right\} }$ for each $x \in S$.

So $f \in M$ and $S$ is a finite subset of the domain of $f$.

Since $M$ has finite character, $f \restriction S \in M$.

Furthermore, by the definition of $\Psi$:

$f \left({x}\right) = \phi \left({x}\right)$

for each $x \in S$.


$\phi \restriction S = f \restriction S \in \phi$

So we see that $\phi \restriction S \in M$ for each finite subset $S$ of $X$.

Since $M$ has finite character, $\phi \in M$.


Boolean Prime Ideal Theorem

This theorem depends on the Boolean Prime Ideal Theorem (BPI), by way of Ultrafilter Lemma.

Although not as strong as the Axiom of Choice, the BPI is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.

Source of Name

This entry was named for Robert H. Cowen and Erwin Engeler.