Composition $R \circ R$ of a partial ordering $R$ with itself is again a partial ordering

Question

If $R$ is a partial ordering then $R\circ R$ is a partial ordering.

I cannot seem to prove this can anyone help ?

Answer 1

Denote $R$ with $\le$, and $R \circ R$ with $\mathrel{\underline\ll}$. Expanding what reflexivity, transitivity, and antisymmetry of $R \circ R$ mean:

• Reflexivity: $x \mathrel{\underline\ll} x$ iff there is a $y$ with $x \le y$ and $y \le x$.
• Transitivity: $x \mathrel{\underline\ll} y$ and $y \mathrel{\underline\ll} z$ should imply $x \mathrel{\underline\ll} z$. The premises imply there exist $v,w$ with $x \le v \le y \le w \le z$.
• Antisymmetry: $x \mathrel{\underline\ll} y$ and $y \mathrel{\underline\ll} x$ should imply $x = y$. The premises imply there exist $v,w$ with $x \le v \le y \le w \le x$.

I leave it to you to conclude by using that $\le$ is a partial ordering.

Answer 2

Using the definition of composition of orders from Wikipedia, we have

Suppose $x \in X$ (suppose $X$ is the set where you have defined the order $R$).

Then $(x,x) \in R\circ R$ as $(x,x) \in R$. This proves reflexivity.

If $(x,y) \in R\circ R$ and $(y,z) \in R\circ R$ then $ \exists\, p,q \in X \text{ s.t. } (x,p) \in R,\, (p,y) \in X, \; (y,q) \in R, (q,z) \in R$ (by definition of composition). Now, by transitivity of $R$, this implies $(x,q) \in R$ and $(q,z) \in R$ whence $(x,z) \in R\circ R$. This proves transitivity.

If $(x,y) \in R\circ R$ then $ \exists z \in X$ such that $(x,z) \in R$ and $(z,y) \in R$; as $R$ is transitive, this implies $(x,y) \in R$. Thus, $(x,y) \in R\circ R$ and $(y,x) \in R\circ R$ implies $(x,y) \in R$ and $(y,x) \in R$ and hence $x=y$. This proves antisymmetry.

Answer 3

If a binary relation $R$ is reflexive and transitive, then $R\circ R=R$. In particular, if $R$ is a reflexive partial ordering, then $R\circ R$, being equal to $R$, is also a reflexive partial ordering.

Suppose $(x,y)\in R\circ R$. Then there is some $u$ such that $(x,u)\in R$ and $(u,y)\in R$. Since $R$ is transitive, it follows that $(x,y)\in R$. This shows that $R\circ R\subseteq R$.

Suppose $(x,y)\in R$. Since $R$ is reflexive, we have $(x,x)\in R$. Since $(x,x)\in R$ and $(x,y)\in R$, it follows that $(x,y)\in R\circ R$. This shows that $R\subseteq R\circ R$.

The question would be slightly more interesting (but not much) if you were talking about irreflexive partial orderings.