Did I solve exercise 4.5.4 (b) of 'How to Prove it' by velleman correctly and concisely?

Question

4.5.4 Suppose R is a strict partial order on A. Let S be the reflexive closure of R.

(b) Show that if R is a strict total order, then S is a total order.

Suppose R is a strict total order. Then, R is transitive and irreflexive.

Let S be the reflexive closure of R. Let T be R ∪ Ia. Let U be a relation on A. Suppose R ⊆ U and U is reflexive.

Let x ∈ T. Since T=R ∪ Ia, x ∈ R or x ∈ Ia. If x ∈ R, then x ⊆ U. If x ∈ Ia, then since U is reflexive, x ∈ U.

Thus, T ⊆ U. Since U was arbitrary, R ⊆ T, and T is reflexive, T is the reflexive closure of R.

It follows that S=T=R ∪ Ia. Let (a, b) ∈ S and (b, c) ∈ S. Then, (a, b) ∈ R ∪ Ia and (b, c) ∈ R ∪ Ia.

If (a, b) ∈ R and (b, c) ∈ R, then since R is transitive, (a, c) ∈ R.

If (a, b) ∈ R and (b, c) ∈ Ia, then since b=c, (a, c) ∈ R.

If (a, b) ∈ Ia and (b, c) ∈ R, then since a=b, (a, c) ∈ R.

If (a, b) ∈ Ia and (b, c) ∈ Ia, then since a=b=c, (a, c) ∈ Ia.

Since a, b, and c were arbitrary, S is transitive.

Let (x, y) ∈ R and (y, x) ∈ R. Since R is transitive, (x, x) ∈ R.

Since, R is irreflexive, this leads to a contradiction. Hence, R is asymmetric.

Now, suppose (d, e) ∈ S and (e, d) ∈ S. Then, (d, e) ∈ R ∪ Ia and (e, d) ∈ R ∪ Ia.

Since R is asymmetric, (d, e) ∈ R ∧ (e, d) ∈ R is false.

Since R is irreflexive, (d, e) ∈ R ∧ (e, d) ∈ Ia and (d, e) ∈ Ia ∧ (e, d) ∈ R are both false.

However, (d, e) ∈ Ia and (e, d) ∈ Ia is true. Thus, if (d, e) ∈ S and (e, d) ∈ S, then d=e.

Therefore, S is antisymmetric.

Since R is a strict total order, ∀x ∈ A∀y ∈ A(xRy ∨ yRx ∨ x = y). Let x and y be arbitrary elements in A.

Since S = R ∪ Ia, (x, y) ∈ S or (y, x) ∈ S if y ≠ x. If x=y, since S is reflexive, (x, y) ∈ S and (y, x) ∈ S.

Since x and y were arbitrary, ∀x ∈ A∀y ∈ A(xSy ∨ ySx).

Since S is reflexive, transitive, antisymmetric, and ∀x ∈ A∀y ∈ A(xSy ∨ ySx), S is a total order.

---

While I think the proof is probably correct, it seems verbose.

Can anyone help make it more concise?

Answer 1

To prove that $S$ is a total order, we need to show antisymmetry, transitivity and totality.

Lemma: Take $a,b \in A$. Then $aSb$ and (not $aRb$) implies that $a = b$. This is because the reflexive closure only adds pairs of the form $(x,x)$ to the relation. In fact, $S \setminus R = \{(x,x) | x \in A\}$.

Antisymmetry

Suppose there exist $a \neq b \in A$ such that $aSb$ and $bSa$. As $a \neq b$, we know only one of $aRb$ or $bRa$ is true. As the other is false, and we have both $aSb$ and $bSa$, the lemma imples $a = b$, a contradiction. Therefore, $a=b$.

Transitivity Take $a,b,c \in A$ such that $aSb, bSc$. There are four cases:

1. $aRb, bRc$. $R$ is transitive, so it follows that $aRc$ and thus $aSc$.
2. $aSb, bRc$ and (not $aRb$). By lemma, $a = b$, and we substitute $aRc$ and so $aSc$.
3. $aRb, bSc$ and (not $bRc$). As above, $b = c$, and we substitute $aRc$ implying $aSc$.
4. $aSb, bSc$ and (not $aRb$),(not $bRc$). From the lemma, $a=b=c$. $S$ is reflexive, so $aSc$.

Totality

Take $a = b \in A$. Because $S$ is a reflexive closure, we know that $aSb$. Now suppose that $a \neq b \in A$. Then we have $(a,b) \in R$, and therefore $(a,b) \in S$.

---

Your proof is probably similar to this, but it's difficult to read. I think the formatting is more important than the verbosity. Brief cases look better as a list, and you don't need to put each sentence on a new line.