Does every partial order admit a maximal chain? Let $<$ be a strict partial order on a set $S$. Is there necessarily a set $C\subseteq S$ such that $C$ is totally ordered by $<$ and no proper superset of $C$ is totally ordered by $<$?
My intuition is that we can build $C$ by starting with the empty set and considering each element of $S$ in turn, adding it to $C$ if the result is still a chain. Since $S$ can be large, I guess formally we need to define $C$ (and simultaneously prove things about it) by transfinite induction, so that "considering each element of $S$ in turn" actually does what we want.
Is that the right idea? I'm not familiar with arguments of this kind and would like to see what a clean/conventional proof looks like (at a level that assumes familiarity with whatever induction principle is used). Is it helpful to explicitly operate with ordinals, or is there a clean solution that's just based on a well-ordering of $S$? Or some other approach?
 A: You need the Axiom of Choice to carry out your construction; either to make the choices, or to ensure that you can actually do an induction that will terminate. In fact, your statement is equivalent to Zorn’s Lemma (and hence to the Axiom of Choice).
If $S$ is empty, then the empty chain is clearly maximal. Assume $S$ is not empty. Let $\mathcal{P}$ be the set of all chains in $S$, ordered by inclusion. This is a partially ordered set; it is nonempty since given $s\in S$, $\{s\}$ is a chain.
Now let $\mathcal{C}$ be a nonempty totally ordered subset of $\mathcal{P}$. I claim that $\cup\mathcal{C}$ is a chain in $S$. Indeed, it is a subset of $S$ since each element of $\mathcal{C}$ is a subset of $S$. And if $a,b\in\cup\mathcal{C}$, then there exist $A,B\in\mathcal{C}$ such that $a\in A$ and $b\in B$. As $\mathcal{C}$ is totally ordered, either $A\subseteq B$ or $B\subseteq A$. Without loss of generality, say $A\subseteq B$. Then $a,b\in B$, and since $B\in\mathcal{P}$, $B$ is totally ordered, hence either $a\leq b$ or $b\leq a$. Thus, $\cup\mathcal{C}$ is totally ordered. Hence $\cup\mathcal{C}\in\mathcal{P}$ is an upper bound for $\mathcal{C}$. 
By Zorn’s Lemma, $\mathcal{P}$ has maximal elements. A maximal element $M$ of $\mathcal{P}$ is a chain in $S$ that is not properly contained in any chain in $S$, i.e., a maximal chain in $S$.
(One can prove Zorn’s Lemma, assuming the Axiom of Choice, using an transfinite inductive argument as the one you try to use; but nailing it down properly takes some work. You can see a proof of Zorn’s Lemma in George Bergman’s handout that does not use this process, but which has a reference to a proof that does. Warning: it is a postscript file). 
On the other hand, if the Axiom of Choice is false, then Zorn’s Lemma is false, and so there exists a partially ordered set $P$ in which every chain has an upper bound, but that contains no maximal elements. Using that as your $S$, if $C$ is any chain in $P$, then $C$ has an upper bound $b$. But $b$ cannot be maximal in $P$, hence there exists $x$ such that $b\lt x$. In particular, we cannot have $x\in C$. Then $C\cup\{x\}$ is strictly larger than $C$, and a chain, since $c\leq b\lt x$ for any $c\in C$. Thus, $C$ is not a maximal chain, so this witness to the failure of Zorn’s Lemma is also a witness to the failure of the proposition you are trying to establish. 
