0
$\begingroup$

Let $R$ be a partial order (reflexive, transitive, and anti-symmetric) on a set $X$.

Recall that $\text{Id}_X = \{\langle x, x\rangle : x \in X\}$.

Let $R^\ast = R \setminus \text{Id}_X$. Prove that $R^\ast$ is a strict order (irreflexive, asymmetric, transitive).

So we are given that R is a partial order of X thus,

  1. for all x in R, x <= x for all x in X. (reflexive)
  2. for all x in R, x = x for all x in X. (anti-symmetry)
  3. based on (1) and (2) x is transitive or an anti-symmetric pre-order

Now we are also Given $R^\ast = R \setminus \text{Id}_X$

I am not sure how to begin this proof..

Can I first assume that for all x in R*, it is reflexive and show that there is a contradiction?

Then assume that for all x in R*, it is anti-symmetric and show that it is not the case

which finally leads to the fact that it is not an anti-symmetric pre-order thus, R* is a strict order?

$\endgroup$
1
  • $\begingroup$ antisymmetry means $x \le y$ and $y \le x$ implies $x=y$ always. $\endgroup$ – Henno Brandsma Jan 20 at 22:31
1
$\begingroup$

There is hardly anything to do here: irreflexive is obvious because of the set $\text{Id}_X$ we take away. Asymmetric: Suppose that $xR^\ast y$ and $yR^\ast x$ would both hold. As then also $xRy,yRx$ hold as well, the fact that $R$ is a partial order (so antisymmetric) tells us that $x=y$ which is a contradiction as we know that not $xR^\ast x$ holds. So $R^\ast$ is a-symmetric. The transivity is clear: $xR^\ast y$ and $y R^\ast z$ then $xRy$ and $yRz$ so $xRz$, and $x=z$ would have contradicted a-symmetry, so $x \neq z$ so $xR^\ast z$ and we're done.

$\endgroup$
2
  • $\begingroup$ Ah i get it. its very straight forward $\endgroup$ – swordlordswamplord Jan 20 at 23:03
  • $\begingroup$ i was over thinking it $\endgroup$ – swordlordswamplord Jan 20 at 23:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.