Lemma: sia $S$ un insieme qualsiasi, sia $\le$ una relazione d'ordine parziale sull'insieme $S$ e siano $a,b \in S$ due elementi non confrontabili tramite la relazione $\le$ (cioè tali che non valga nè $a \le b$ nè $b \le a$). Allora la relazione d'ordine parziale $\le$ si può estendere ad una relazione d'ordine parziale $\le'$ tale che $a \le' b$.
Teorema: sia $S$ un insieme finito e sia $\le$ una relazione d'ordine parziale sull'insieme $S$. Allora la relazione d'ordine parziale $\le$ si può estendere ad una relazione d'ordine totale $\bar \le$.
Supponiamo di aver già dimostrato il lemma e di volerlo utilizzare per dimostrare il teorema.
L'idea è abbastanza ovvia: partiamo dalla relazione d'ordine parziale $\le$, se questa relazione non è totale allora esistono due elementi $a,b \in S$ non confrontabili tramite la relazione $\le$, allora utilizziamo il lemma per estendere la relazione $\le$ ad una relazione $\le'$ tale che $a \le' b$, ripetiamo questo argomento finchè non otteniamo un ordine totale.
Ma come posso formalizzare questa semplice idea? In particolare, come posso mostrare che questo procedimento porta ad ottenere una relazione totale in un numero finito di passi?