Implication of the Axiom of choice.

Question

I want to prove that, over $ZF$, the axiom of choice implies: “Any family of sets contains a maximal subfamily consisting of pairwise mutually disjoint sets”.

I think I have seen a proof of it using Zorns lemma, but I want to get used to Axiom of choice and get some feeling of how to apply it in proofs. Apart of the book I'm using, which is by Jech, I have got myself a copy of "https://www.amazon.com/Equivalents-Choice-Studies-Foundations-Mathematics/dp/0444877088", but it hasn't made me much smarter.

On page 54 they showed that “every family of sets contains a maximal subfamily consisting of mutually not disjoint sets” $\Rightarrow$ “every family of sets contains a maximal subfamily consisting of mutually disjoint sets". (I think that's what they are saying, sometimes it is pretty hard to follow along, since there are symbols everywhere, for everything!)

$\text{ }$

---

For this proof. They first let $x$ be an arbitrary set. Then they defined a set $N_s:=\{u: u=\{s\}\lor (\exists t)[t\in x, u=\{s,t\}, s\cap t=\emptyset] \}$. They concluded that $\{N_s:s\in X\}$ must have a maximal subset $w$ consisting of not disjoint sets (by assumption). Lastly they concluded that $\{s:N_s\in w\}$ is well-defined and fullfulling the properties in the statement we wanted to prove. I thought I could use this as a hint on how to prove from the axiom of choice instead.

---

Proof idea:

Let $X$ be an arbitrary set. Define the set $N_s:=\{u: u=\{s\}\lor (\exists t)[t\in x, u=\{s,t\}, s\cap t=\emptyset] \}$. Probably I could, by know, apply axiom of choice to conclude that $\{N_s:s\in X\}$ must have a maximal subset $w$ (as they did). I thought it would be easier for me to take an indirect way. That is; proving “every family of sets contains a maximal subfamily consisting of mutually not disjoint sets”. Then arguing as they did.

But I don't really know how to apply the axiom of choice. All it says is, "Every family of non-empty sets has a choice function". I have been thinking about this for 4 days now and can't really understand how to do the proof. :/

---

Zorns lemma

Using Zorns lemma, I think I could use partial ordering by $\in$ and bound it by the collection of all sets in $X$.

But I want to do it without Zorns lemma. Would be grateful for any help.

Thanks! :)

Answer 1

Let $F$ be a family of sets. If $F$ doesn't have a maximal subfamily consisting of mutually disjoint sets, then you can use the axiom of choice to pick, for each $X\subseteq F$ that consists of mutually disjoint sets, a set $g(X)\in F$ such that $g(X)\not\in X$ and $X\cup\lbrace g(X)\rbrace$ consists of mutually disjoint sets. For convenience, if $X$ does not consist of mutually disjoint sets, we'll set $g(X)=\emptyset.$

Let $\kappa$ be a cardinal number greater than the cardinality of $F.$ Define, by transfinite induction, $$X_\alpha = g(\lbrace X_\beta\mid\beta\lt\alpha\rbrace),$$ for each ordinal $\alpha\lt\kappa.$ You can prove by transfinite induction that, for each $\alpha$, $\lbrace X_\beta\mid\beta\lt\alpha\rbrace$ is a subfamily of $F$ consisting of mutually disjoint sets. It follows that each $X_\alpha\not\in\lbrace X_\beta\mid\beta\lt\alpha\rbrace;$ in other words, $\alpha\ne\beta$ implies $X_\alpha\ne X_\beta.$

But that means that we've produced $\kappa$ many distinct members of $F,$ contradicting the choice of $\kappa.$

Going back to your question, though, one could argue that all we're really doing here is re-proving Zorn's lemma.

Answer 2

Almost always, the way you prove things like this directly using the axiom of choice is by transfinite induction, using a choice function to make a choice at each step of the induction. Let $X$ be the family of sets you are interested in, and fix some set $*$ that is not an element of $X$ (you could take $*=X$, for instance). We may assume $\emptyset\not\in X$ (otherwise, we could solve the problem for $X\setminus\{\emptyset\}$, and then throw $\emptyset$ in as an extra element of our subfamily at the end). Let $c$ be a choice function on the set of all nonempty subsets of $X$.

Now recursively define a function $F:Ord\to X$ as follows. Having defined $F(\beta)$ for all $\beta<\alpha$, let $Y$ be the set of elements of $X$ that are disjoint from $F(\beta)$ for all $\beta<\alpha$. If $Y=\emptyset$, define $F(\alpha)=*$. Otherwise, define $F(\alpha)=c(Y)$.

By induction, it is clear that if $\alpha,\beta\in Ord$ are distinct and $F(\alpha), F(\beta)\neq *$, then $F(\alpha)$ and $F(\beta)$ are disjoint elements of $X$. In particular, $F(\alpha)\neq F(\beta)$ (since they cannot be $\emptyset$). If $F(\alpha)\neq *$ for all $\alpha$, then $F$ would be an injection from $Ord$ to $X$, which is impossible since $Ord$ is a proper class. Thus there exists $\alpha$ such that $F(\alpha)=*$; choose the least such $\alpha$.

By definition of $F$, we know that there cannot exist any element of $X$ that is disjoint from $F(\beta)$ for all $\beta<\alpha$. Let $Z=\{F(\beta):\beta<\alpha\}$. Then $Z$ is a subset of $X$ and all the elements of $Z$ are disjoint. Furthermore, $Z$ is maximal with this property, since no element of $X$ is disjoint from every element of $Z$. This is exactly what we want.

Answer 3

Let me add an answer, explaining why you cannot possibly avoid Zorn's lemma altogether.

We say that $A$ is an amorphous set if every subset of $A$ is finite or its complement is finite. We say that $A$ is strongly amorphous if whenever $S$ is a partition of $A$, then except finitely many cells, $S$ is made out of singletons.

Theorem. It is consistent that there is a[n infinite] strongly amorphous set.

Suppose that $A$ is a strongly amorphous set, then $[A]^2=\{\{a,b\}\subseteq A\mid a\neq b\}$ does not have a maximal family of pairwise disjoint sets. To see why, simply note that any family of pairwise disjoint sets inside $[A]^2$ has to be finite, otherwise we could have partitioned $A$ into "mostly pairs", but $A$ is strongly amorphous. But because $A$ is infinite, any finite family of pairwise disjoint pairs is not maximal.

Answer 4

This is a modification of Eric Wofsey's answer. Suppose $F$ has no maximal pair-wise disjoint subset. Let $F^*$ be the set of pair-wise disjoint subsets of $F.$ For $x\in F^*$ let $g(x)\in F$ \ $x$ such that $\forall y\in x\;(g(x)\cap y=\emptyset).$ And let $h(x)=x\cup \{g(x)\}.$

Now for ordinal $A$ let $$G(A)=h(\cup_{B< A}G(B)).$$ By transfinite induction we have $\forall B<A\;(\;G(A)\supsetneqq G(B)\in F^*)$ and $G(A)\in F^*.$ So by Replacement there is a bijection from $\{z\in F^*: \exists A\;(\;z=G(A)\;)\}$ to the class of all ordinals, an impossibility.

Remark: $G(0)=h(0)=\{g(0)\}$ where $g(0)\in F$. And $G(1)=h(G(0))= G(0)\cup \{g(G(0)\}.$ Etc. (When I first saw formulas like the def'n of $G(A)$ they seemed strange.)

Remark: If $F^*$ has no maximal element then $F^*\ne \emptyset$ and $g$ is a choice-function on $\{ S(x)\}_{x\in F^*}$ where $S(x)$ is an abbreviation for $\{z\in F$ \ $x: \forall y\in x\;(z\cap y = \emptyset)\}.$