Suppose $A$ is a finite set and $R$ is a partial order on $A$. Prove that $R$ can be extended to a total order on $A$.

Question

Suppose $A$ is a finite set and $R$ is a partial order on $A$. Prove that $R$ can be extended to a total order on $A$. In other words, prove that there is a total order $T$ on $A$ such that $R ⊆ T$.

My attempt:

Notation and abbreviations:

1. Cardinality of the set, say $A$, is denoted as $|A|$.

2. Partial order will be abbreviated as PO, and total order will be abbreviated as TO.

---

By induction.

Base case

Take $A = \{x\}$. The only possible PO on $A$ is $\{(x,x)\}$. Clearly, it is also a TO on $A$.

Induction step

Suppose for any set with $n$ elements, any PO on the set can be extended to TO.

Now take $A = |n+1|$.

Take arbitrary PO on $A$, say $R$. Need to prove that $R$ can be extended to TO.

---

Take $a \in A$, such that $a$ is the R-minimal element of $A$.

Let $A' = A \setminus \{a\}$.

Let $R' = \{(x,y) \mid xRy \land x ≠ a\}$

It can be shown that $R'$ is a PO on $A'$, and by inductive hypothesis we conclude that there exists some $T'$, such that $R' \subseteq T'$ and $T'$ is a TO on $A'$.

Now let $T = T' \cup \{(a,x) \mid x \in A \}$.

It can be shown that $R \subseteq T$. Now we need to show that $T$ is TO on $A$.

In other words, we need to prove that

1. $T$ is reflexive

2. $T$ is transitive

3. $T$ is antisymmetric

4. For all $x \in A$ and for all $y \in A$, either $xTy$ or $yTx$.

---

1. Reflexive: take $x \in A$. Clearly if $x = a$ then $(x,x) \in T$. Now suppose $x ≠ a$. Then $x \in A'$ and $(x,x) \in T'$. Since $T' \subseteq T$, $(x,x) \in T$.

2. Transitive: take $(x,y),(y,z) \in T$ and suppose $x ≠ a$. We know that $y ≠ a$. And since $y ≠ a$, both elemetns are in $T'$. $T'$ is TO on $A'$, hence $xT'z$, and therefore $xTz$

3. Antisymmetric: Take $(x,y) \in T$ and suppose $x ≠ a$. We know that $xT'y$ and $T'$ is antisymmetric, hence $\lnot yT'x$ and $\lnot yTx$. Now suppose $aTy$. By definition of $T$, we conclude that $\lnot yTa$

4. • Take $x,y \in A$, such that $x ≠ a$ and $y ≠ a$. $x \in A'$ and $y \in A'$, hence either $xT'y$ and $yT'x$. And since $T' \subseteq T$, we conclude that either $xTy$ or $yTx$.
   • Take $a, y \in A$. Since $(a,y) \in \{(a,x) \mid x \in A \}$, we have $aTy$.

Hence $T$ is a TO. $\Box$

Is it correct?