Implication of the Axiom of choice. 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! :)
 A: 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.
A: 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.
A: 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.
A: 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)\}.$ 
