How to extend a partial order on a finite set

94 Views Asked by At

Let $A$ be a finite set and let $\le$ be a partial order order on the set $A$.

Suppose that $a,b \in A$ are two elements of $A$ such that $a \not \le b$ and $b \not \le a$.

I define a new binary relation $T$ on the set $A$ setting $T := \{(x,y) \in A \times A \mid x \le a \text{ and } b \le y\}$.

I define another new binary relation $\le^*$ on the set $A$ setting $\le^*=\le \cup T$.

I claim that $\le^*$ is a partial order on the set $A$, that $\le^*$ extends $\le$ and that $a \le^* b$.

I have that $(a,b) \in T \subseteq \le^*$, that is, $a \le^* b$.

I have that $\le \subseteq \le^*$.

I have that $\le \subseteq \le^*$ and that $\le$ is reflexive, so $\le^*$ is reflexive.

But how can I prove that $\le^*$ is antisymmetric and transitive?

1

There are 1 best solutions below

1
On

I try to prove that $\le^*$ is antisymmetric.

I have to prove that if $p \le^* q$ and $q \le^* p$ then $p=q$.

There are four cases: ($p \le q$ and $q \le p$) or ($p \le q$ and $qTp$) or ($pTq$ and $q \le p$) or ($pTq$ and $qTp$).

Case 1: $p \le q$ and $q \le p$. If $p \le q$ and $q \le p$ then $p=q$ because $\le$ is a partial order (in particular $\le$ is antisymmetric).

Case 2: $p \le q$ and $qTp$. If $p \le q$ and $qTp$ then $p \le q$, $q \le a$ and $b \le p$, then $b \le a$ because $\le$ is a partial order (in particular $\le$ is transitive), this is a contraddiction because $b \not \le a$ by hypothesis. So case 2 is impossible.

Case 3: $pTq$ and $q \le p$. If $pTq$ and $q \le p$ then $p \le a$, $b \le q$ and $q \le p$, then $b \le a$ because $\le$ is a partial order (in particular $\le$ is transitive), this is a contraddiction because $b \not \le a$ by hypothesis. So case 3 is impossible.

Case 4: $pTq$ and $qTp$. If $pTq$ and $qTp$ then $p \le a$, $b \le q$, $q \le a$ and $b \le p$, then $b \le a$ because $\le$ is a partial order (in particular $\le$ is transitive), this is a contraddiction because $b \not \le a$ by hypothesis. So case 4 is impossible.

Is my proof correct?