Is a subset of a relation that is a partial order also a partial order?

Question

I've sat on this question for a while now:

Question:

Suppose that $R$ is a partial order. If we take some subset $S$ of $R$, will it also be a partial order? Prove or disprove this.

Now I know the following. For a partial order, the set must follow these criteria.

1. reflective

2. anti-symmetric

3. transitive

So if the relation on a set is a partial order. If we collected any values from that set $R$ and put in set $S$ will that be a partial order?

I believe that the subset is always reflective because a set is always a subset of itself. However I am struggling to prove the other $2$ criteria.

Example:

$R = \{(1,1),(1,2),(2,2),(1,3),(2,3),(3,3)\}$

$S = \{(1,1),(2,3)\}$

Subset $S$ is not a partial order from the set of relation $R$? I could use multiple counter examples and proof by cases?

Is this the right way of looking at the question?

Thanks.

Answer 1

Well, if $R\subset A\times A$ is a partial order and $B$ is a subset of $A$, then $$S = R\cap B\times B = \{(a,b)\mid (a,b)\in R,a,b\in B\}$$ is a partial order. This is the best general result you can get.

In your example, let $R= \{(1,1),(1,2),(2,2),(1,3),(2,3),(3,3)\}$, where $A=\{1,2,3\}$. If $B=\{1,2\}$, then $S=\{(1,1),(1,2),(2,2)\}$.

---

Transitivity: Let $aRb$ and $bRc$. We know that $aRc$.

If $a,b,c\in B$, then fine.

If $a,b\in B$ but not $c$, then $aSb$ but not $bSc$. Fine.

Similar if $b,c\in B$ but not $a$.

If $a,c\in B$ but not $b$, then $aSc$. Fine.

Answer 2

A subset of a partial order need not always be one. For a simple example, take

$$R = \{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\}$$

This relation is a partial order. However, take

$$S = R \setminus \{(1,1)\}$$

The relation is no longer reflexive, and thus not a partial order. In general, if $R$ is a partial order over a nonempty set $A$, then $S_a = R\setminus \{(a,a)\}$ for any fixed $a \in A$ is a subset of $R$ which is not a partial order. (And we know such an $(a,a) \in R$ exists since $A \ne \varnothing$ and $R$ is reflexive.)

---

...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.