Exercise: prove statement logically equivalent to Axiom of Choice

Question

Exercise (from T.Tao's Analysis 1 textbook):

(Part I) Let $X$ be a set, and let $\Omega\subset 2^X$ be a collection of subsets of $X$. Assume that $\emptyset\notin\Omega$. Using Zorn's lemma, show that there is a subcollection $\Omega '\subseteq\Omega$ such that:

(1) All the elements of $\Omega'$ are disjoint from each other (i.e. $A\cap B=\emptyset\ \forall A,B\in \Omega', A\neq B$);

(2) All the element of $\Omega$ intersect at least one element of $\Omega '$ (i.e. $\forall C\in\Omega \exists A\in\Omega'$ such that $C\cap A\neq\emptyset$).

---

(Part II) Now let $I$ be a set, for each $\alpha\in I$ let $X_{\alpha}\neq\emptyset$ and suppose that all the sets are disjoint from each other, i.e. $X_{\alpha}\cap X_{\beta}=\emptyset$ $\forall \alpha , \beta \in I, \alpha\neq\beta$. Show that if the above claim is true then there exists a set $Y$ such that $\#(Y\cap X_{\alpha})=1\ \forall\alpha\in I$.

---

Here's my proof (which makes use of some hints given in the text):

(Part I) Let $V:=\{W\subseteq\Omega:\forall w,w'\in W, w\neq w', w\cap w'=\emptyset\}$ (i.e. V is the set of all subsets of $\Omega$ whose elements are all disjoint from each other); $(V, \subseteq)$ is a poset and $V\neq\emptyset$ since elements of $V$ are the singletons of $\Omega$). Now let $T$ be a totally ordered subset of $V$; we claim that $\bigcup T$ is an upper bound of $T$ in fact:

$-$ $x\in \bigcup T\Rightarrow x\in S, x'\in S'$ for some $S\in T\overset{T\subseteq V}\Rightarrow x\in S$ for some $S\in V \Rightarrow x\in S$ for some $S\subseteq\Omega\Rightarrow x\in\Omega$ thus $\bigcup T\subseteq\Omega$;

$-$ $x,x’\in\bigcup T, x\neq x’\Rightarrow x\in S, x’\in S’$ for some $S,S’\in T$; since $T$ is a totally ordered set, we can suppose without loss of generality that $S’\subseteq S$ thus we have that $x,x’\in S, S\in T\overset{T\subseteq V}{\Rightarrow} x,x’\in S, S\in V\Rightarrow x\cap x’=\emptyset$ thus we have that $\forall x,x’\in\bigcup T, x\neq x’ x\cap x’=\emptyset$ and so $\bigcup T\in V$;

$-$ $x\in S$ for some $S\in T\Rightarrow x\in\bigcup T$ (by Axiom of Union) so $S\subseteq \bigcup T \forall S\in T$ thus $\bigcup T$ is an upper bound for $T$. So, by Zorn’s lemma there exists a maximal element $M\in V$ and we claim that the properties (1) and (2) hold for $M$ (i.e. $M$ is the set $\Omega ‘$ which was asked to find), in fact:

(1) $x,x’\in M, x\neq x’\overset{M\in V}{\Rightarrow} x\cap x’=\emptyset$;

(2) suppose for sake of contradiction there exists a set $C\in \Omega$ such that $C\cap A=\emptyset \forall A\in M$; then if we define $M’:=M\cup \{C\}$ we have that $M’\in V$ and $M\subset M’$, a contradiction since $M$ is a maximal element of $V$; thus (2) also holds and this finishes the first part of the proof.

—

(Part II) Let $\Omega :=\{(0,\alpha),(1,x_{\alpha}):\alpha\in I, x_{\alpha}\in X_{\alpha}\}$; then by hypothesis there exists a set $\Omega ‘\subseteq\Omega $ such that the properties (1) and (2) hold. We claim that $Y:=\{y\in\bigcup_{\alpha\in I}X_{\alpha}: \{(0,\alpha),(1,y)\}\in\Omega’\ for\ some\ \alpha\in I\}$ is such that $\#(Y\cap X_{\alpha})=1\ \forall \alpha\in I$. In fact, suppose for sake of contradiction that there exists $\tilde{\alpha}\in I$ such that $\#(Y\cap X_{\alpha})\neq 1$ i.e. such that either (I.1)$\#(Y\cap X_{\alpha})=0$ or (I.2)$\#(Y\cap X_{\alpha})\geq 2$. If (I.1) holds then $\{(0,\tilde{\alpha}),(1,y)\}\notin\Omega’ \forall y\in X_{\tilde{\alpha}}$; now take an arbitrary element $x\in X_{\tilde{\alpha}}$ (which must exist since each $X_{\alpha}\neq\emptyset$ by hypothesis) and we have that $\{(0,\tilde{\alpha}),(1,x)\}\in\Omega$ thus by (2) there exists a set $A\in\Omega’$ such that $A\cap\{(0,\tilde{\alpha}),(1,x)\}\neq\emptyset$ and since $A\in\Omega$ (being $\Omega’\subseteq\Omega$) it must be of the form $A=\{(0,a),(1,b)\}$ where $a\in I, b\in X_a$ so we have that either:

$-\ $ $a=\tilde{\alpha}, b=x$ (i.e.$A\cap\{(0,\tilde{\alpha}),(1,x)\}=\{(0,\tilde{\alpha}),(1,x)\})\Rightarrow A=\{(0,\tilde{\alpha}),(1,x)\}\in\Omega’$, a contradiction;

$-\ $ $a\neq\tilde{\alpha}, b=x$ (i.e.$A\cap\{(0,\tilde{\alpha}),(1,x)\}=\{(1,x)\}$) cannot hold since if $b\in X_{\tilde{\alpha}}$ then it must be $a=\tilde{\alpha}$, since $A\in\Omega$;

$-\ $ $a=\tilde{\alpha}, b\neq x$ (i.e. $A\cap\{(0,\tilde{\alpha}),(1,x)\}=\{(0,\tilde{\alpha})\}$) then $A=\{(0,\tilde{\alpha}),(1,b)\}$ where $b\in X_{\tilde{\alpha}} -\{x\}$, a contradiction.

So if we assume that (I.1) holds we always reach a contradiction, so it must be $\#(Y\cap X_{\tilde{\alpha}})\neq 0$, i.e. $\#(Y\cap X_{\tilde{\alpha}})> 0$.

Suppose now that (I.2) holds: then there exists $y,y’\in X_{\tilde{\alpha}}$ such that $\{(0,\tilde{\alpha}),(1,y)\}, \{(0,\tilde{\alpha}),(1,y’)\}\in\Omega’$ and so $\{(0,\tilde{\alpha}),(1,y)\}\cap\{(0,\tilde{\alpha}),(1,y’)\}=\{(0,\tilde{\alpha})\}\neq\emptyset$, a contradiction (by (1)). So (I.2) also cannot hold thus it must be $\#(Y\cap X_{\tilde{\alpha}})\ngeqslant 2$, i.e. $\#(Y\cap X_{\tilde{\alpha}})<2$ thus $\#(Y\cap X_{\tilde{\alpha}})=1$ and since $\tilde{\alpha}$ was an arbitrary element of $I$ it follows that $\#(Y\cap X_{\alpha})=1\ \forall\alpha\in I$, as desired. $\square$

Is my proof correct? If it is I’d appreciate any comment or hint about how to improve it. Also, do you think this could be proved in a faster way (i.e. does anyone have a shorter proof)?

Best regards,

lorenzo.

Answer 1

Your Zorn’s lemma argument is basically correct, but it could be quite a bit easier to follow. Here’s one possibility:

Let $\mathfrak{D}$ be the family of all pairwise disjoint subsets of $\Omega$; $\langle\mathfrak{D},\subseteq\rangle$ is a poset, and $\{V\}\in\mathscr{V}$ for each $V\in\Omega$, so $\mathfrak{D}\ne\varnothing$. Now let $\mathfrak{T}$ be a totally ordered subset of $\mathfrak{D}$; we claim that $\bigcup\mathfrak{T}$ is an upper bound of $\mathfrak{T}$ in $\mathfrak{D}$.

• Clearly $\mathscr{T}\subseteq\bigcup\mathfrak{T}$ for each $\mathscr{T}\in\mathfrak{T}$, so $\bigcup\mathfrak{T}$ is an upper bound for $\mathfrak{T}$ provided that it belongs to $\mathfrak{D}$.
• $\bigcup\mathfrak{T}\in\mathfrak{D}$: Clearly $\bigcup\mathfrak{T}\subseteq\Omega$, so we need only show that $\bigcup\mathfrak{T}$ is pairwise disjoint. If $W_0,W_1\in\bigcup\mathscr{T}$, then there are $\mathscr{T}_1,\mathscr{T}_2\in\mathfrak{T}$ such that $W_0\in\mathscr{T}_0$ and $W_1\in\mathscr{T}_1$. $\mathfrak{T}$ is linearly ordered by $\subseteq$, so without loss of generality we may assume that $\mathscr{T}_0\subseteq\mathscr{T}_1$. But then $W_0,W_1\in\mathscr{T}_1$, and $\mathscr{T}_1$ is pairwise disjoint, so $W_0\cap W_1=\varnothing$, as desired.

By Zorn’s lemma there is a maximal $\mathscr{M}\in\mathfrak{D}$. Suppose that there is some $W_0\in\Omega$ such that $W\cap W_0=\varnothing$ for each $W\in\mathscr{M}$. Then $\mathscr{M}\cup\{W_0\}$ is a pairwise disjoint subset of $\Omega$, so $\mathscr{M}\cup\{W_0\}\in\mathfrak{D}$, and clearly $\mathscr{M}\subsetneqq\mathscr{M}\cup\{W_0\}$, contradicting the maximality of $\mathscr{M}$. Thus, $\mathscr{M}$ has the desired properties. $\dashv$

More words and fewer symbols make the argument easier to follow, and I’ve taken the liberty of using the convention that subsets of $X$ are represented by upper-case Latin letters, families of these subsets by upper-case script letters, and collections of such families by upper-case Fraktur letters.

The argument for Part II, however, gets off on the wrong foot right away when you set

$$\Omega=\{\langle 0,\alpha\rangle,\langle 1,x_\alpha\rangle:\alpha\in I,x_\alpha\in X_\alpha\}\;.$$

The notation implies that you’ve already selected an $x_\alpha$ in each $X_\alpha$, so that you’re assuming the desired result: $\{x_\alpha:\alpha\in I\}$ would serve for $Y$. Independent of this problem, your definition of $Y$ is flawed: you define it to be the set of $y\in\bigcup_{\alpha\in I}X_\alpha$ satisfying a property that doesn’t mention $y$ at all. I think that you had in mind something like the following argument.

Let $$X=\big(\{0\}\times I\big)\cup\left(\{1\}\times\bigcup_{\alpha\in I}X_\alpha\right)\;,$$ let $\Omega=\big\{\{\langle 0,\alpha\rangle,\langle 1,x\rangle\}:\alpha\in I\text{ and }x\in X_\alpha\big\}$, and by Part I let $\Omega'$ be a pairwise disjoint subset of $\Omega$ such that every $W\in\Omega$ meets at least one member of $\Omega'$. Let $$Y=\left\{x\in\bigcup_{\alpha\in I}X_\alpha:\{\langle 0,\alpha\rangle,\langle 1,x\rangle\}\in\Omega'\text{ for some }\alpha\in I\right\}\;.$$ We claim that $|Y\cap X_\alpha|=1$ for each $\alpha\in I$.

Let $\alpha\in I$; $X_\alpha\ne\varnothing$, so there is an $x\in X_\alpha$. Let $P=\{\langle 0,\alpha\rangle,\langle 1,x\rangle\}\in\Omega$; by hypothesis there is some $W=\{\langle 0,\beta\rangle,\langle 1,y\rangle\}\in\Omega'$ such that $W\cap P\ne\varnothing$. Let $\langle i,z\rangle\in W\cap P$.

• If $i=0$, then $\alpha=z=\beta$, so $y\in Y\cap X_\alpha$, and $Y\cap X_\alpha\ne\varnothing$.
• If $i=1$, then $y=z=x\in X_\alpha$, and again we find that $y\in Y\cap X_\alpha$ and $Y\cap X_\alpha\ne\varnothing$.

Finally, suppose that $y_0,y_1\in Y\cap X_\alpha$ for some $\alpha\in I$. Then $\{\langle 0,\alpha\rangle,\langle 1,y_0\rangle\}$ and $\{\langle 0,\alpha\rangle,\langle 1,y_1\rangle\}$ both belong to $\Omega'$. But $\Omega'$ is pairwise disjoint, and $$\langle 0,\alpha\rangle\in\{\langle 0,\alpha\rangle,\langle 1,y_0\rangle\}\cap\{\langle 0,\alpha\rangle,\langle 1,y_1\rangle\}\;,$$ so it must be that $\{\langle 0,\alpha\rangle,\langle 1,y_0\rangle\}=\{\langle 0,\alpha\rangle,\langle 1,y_1\rangle\}$ and hence that $y_0=y_1$. Thus, $|Y\cap X_\alpha|\le 1$, and since we’ve already shown that $Y\cap X_\alpha\ne\varnothing$, we must have $|Y\cap X_\alpha|=1$, as desired. $\dashv$