A partial ordering $\preceq'$ on $S$ is said to be compatible with another partial ordering $\preceq$ if for all $a,b,\in S$,
$$ a \preceq b \Rightarrow a \preceq' b$$
Given a poset $(S, \preceq)$, a toplogical sorting on $S$ is a total order $\preceq'$ that is compatible with $\preceq$. There is a simple constructive proof that every finite poset can be toplogically sorted. Is the same true for infinite sets? Can every poset be toplogically sorted?
On
Choice is indeed necessary - for one thing, even the statement "Every set can be linearly ordered" is not provable in ZF alone! See https://mathoverflow.net/questions/37272/are-all-sets-totally-ordered.
This is the Szpilrajn extension theorem; it’s a result that follows from the axiom of choice. In fact, it follows from but does not imply the weaker compactness theorem for first-order logic or the equivalent Boolean prime ideal theorem. Its proof from the result for finite partial orders and either the compactness theorem or the equivalent ultrafilter lemma is a straightforward application of either.