Check my understanding of proof that Partial order can be extended to total order

83 Views Asked by At

Induction step : let n be arbitrary natural number, and suppose that every partial order on a set with n elements can be extended to total order. Suppose A has n+1 elements and R is a partial order on A. So there must be $a \in A$ such that a is R-minimum element of A. Let $A'=A-{a}$ and let $R = R \cap (A' \times A')$. R ' is a partial order on A'. By inductive hypothesis, we can let T' be total order on A' such that $R' \subseteq T'$. Now let $T= T' \cup ({a} \times A)$. So T is a total order on A and R is a subset of T

Now

  1. Firstly i thought about why R' is defined in such a way. So i think it is so because they wanted to exclude all " trace of minimal element and its pairs " from R with disturbing partial ordering.

  2. I thought on about why they define T as it is. Since T' is total order on A' and we need total order on A. But $A = A' + {a}$, where a is minimal element. So its defined in such a way so as to squeeze minimal element pairs without disturbing total order. But i took example to see whats happening here. I think if we take $T = T' \cup {(a,a)} $ will also do as we need to satisfy reflexive property. But i am not sure why they have taken T to be otherwise.

Please comment on my points 1,2

Thanks