# Partial and Strict order proof of binary relations [closed]

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?

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

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.