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! :)

  • 2
    $\begingroup$ When you write "mutually disjoint" do you mean "pairwise disjoint"? $\endgroup$ – Carl Mummert Oct 8 '16 at 22:20
  • $\begingroup$ yes, sorry. That is exactly what I mean. I can modify it. :) $\endgroup$ – user376380 Oct 8 '16 at 23:25

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.

  • $\begingroup$ @EricWofsey I've modified the internal proof by transfinite induction slightly to make this clearer, but the definitions don't have to be changed. At most one of the $X_\alpha\text{'s}$ can be empty, since any later $X_\beta$ does not belong to the set of all preceding sets, and the empty set is one of those sets. $\endgroup$ – Mitchell Spector Oct 8 '16 at 21:51
  • $\begingroup$ Yes, I realized that right after I wrote my comment (and that's why I deleted it). $\endgroup$ – Eric Wofsey Oct 8 '16 at 21:57
  • $\begingroup$ @EricWofsey -- Well, I appreciate your having mentioned it, because the statement that I was proving by transfinite induction, after the definition, really needed to be strengthened slightly (which I've done). $\endgroup$ – Mitchell Spector Oct 8 '16 at 21:59
  • $\begingroup$ I don't think your edit is necessary: $g(X)$ is defined even if $X=\emptyset$. Note that $g$ isn't technically a choice function itself; rather, given a choice function $c$ on the nonempty subsets of $X$, you could define $g(X)=c(F\setminus X)$. In particular, $F\setminus X$ is never going to be empty (if it were, $X=F$ would trivially be a maximal disjoint subfamily). $\endgroup$ – Eric Wofsey Oct 8 '16 at 22:02
  • $\begingroup$ Yes, I set $g(X)=\emptyset$ if $X$ doesn't consist of mutually disjoint sets precisely to make sure that $X_\alpha$ was defined properly, since the definition has to come before the transfinite induction where you prove that that part of the definition of $g$ never comes into play. The issue with the first version was that $\emptyset$ is itself a set of mutually disjoint sets so what I was proving by induction wasn't quite sufficient. The edit solves that slight issue. Alternatively, we could choose a different default value for $g(X),$ one that's not itself a set of mutually disjoint sets. $\endgroup$ – Mitchell Spector Oct 8 '16 at 22:11

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.

  • $\begingroup$ Some of the technicality with Ord and $*$ can be finessed by making a map just from (a well ordering of) $X$. For example we could make a map from $X$ to $\{0,1\}$ so that $f(v) = 1$ if and only if $v$ is disjoint from every $u$ which comes before $v$ in the order and has $f(u) =1$. Then $\{v \in X : f(v) = 1\}$ is a maximal pairwise disjoint family. $\endgroup$ – Carl Mummert Oct 8 '16 at 22:19
  • $\begingroup$ Well, I was trying to write a proof that just uses choice directly, not any consequence of choice like the well-ordering theorem. $\endgroup$ – Eric Wofsey Oct 8 '16 at 22:44
  • $\begingroup$ Thanks Eric, For telling me that you usually prove such things by transfinite induction. It might seem obvious for others but it really helps me. I will try to have this in mind next time im confronted with the axiom of choice :) $\endgroup$ – user376380 Oct 8 '16 at 23:36

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.


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)\}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy