Let $X\neq\emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ be a collection of non-empty subset. We say that a map $f: {\cal E}\to X$ is an injective choice function if it is injective and
$f(e) \in e$ for all $e\in {\cal E}$.
I want to prove the following maximality statement:
(S) If $X$ is a set and ${\cal E}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ has an injective choice function, then there is ${\cal E}_1 \subseteq {\cal P}(X)\setminus\{\emptyset\}$ with ${\cal E}_1\supseteq {\cal E}$ such that
-
${\cal E}_1$ has an injective choice function, and
-
if $u \in {\cal P}(X)\setminus ({\cal E}_1\cup\{\emptyset\})$ then ${\cal E}_1\cup \{u\}$ has no injective choice function.
My gut feeling is that this is a pretty straightforward application of Zorn's Lemma – but I can't make the self-map work on the union of a chain of ${\cal E}$'s…! Any help appreciated!
Best Answer
It’s false. Let $X=\omega$, for $n\in\omega$ let $e_n=\omega\setminus n$, and let $\mathscr{E}=\{e_n:n\in\omega\}$. Suppose that $\mathscr{E}_1\supseteq\mathscr{E}$ has an injective choice function $f$, and let $a=\{f(e_n):n\in\omega\}$. Let $\{a_0,a_1\}$ be a partition of $a$ such that $|a_0|=|a_1|=\omega$; clearly $a_0\notin\mathscr{E}_1$, so let $\mathscr{E}_2=\mathscr{E}_1\cup\{a_0\}\supsetneqq\mathscr{E}_1$.
Recursively define $\varphi:\omega\to a_1$ as follows: if $\varphi\upharpoonright n$ has been defined for some $n\in\omega$, let
$$\varphi(n)=\min\{k\in a_1:k\in e_n\setminus\varphi[n]\}\;;$$
then $\varphi$ is an injective choice function for $\mathscr{E}$, and $\operatorname{ran}\varphi\subseteq a_1$.
Let
$$g:\mathscr{E}_2\to\omega:e\mapsto\begin{cases} f(e),&\text{if }e\in\mathscr{E}_1\setminus\mathscr{E}\\ \min a_0,&\text{if }e=a_0\\ \varphi(n),&\text{if }n\in\omega\text{ and }e=e_n\;; \end{cases}$$
then $g$ is an injective choice function for $\mathscr{E}_2$. Thus, there is no $\mathscr{E}_1$ extending $\mathscr{E}$ that is maximal with respect to having an injective choice function.