[Math] Proving that restrictions of partial orders are partial orders

discrete mathematicsorder-theoryrelations

Prove: A set has a partial-order relation $R$ on it. $P$ is a subset of this set. Prove that the restriction of $R$ to $P$ is itself a partial-order relation.

Assume that this relation, $T$, resulting from the restriction of $R$ on $P$ is defined as such:

$T = \{(x,y) \mid x \in P, y \in P, (x, y) \in R\}$.

It seems to be obvious that if $R$ works on a set $S$, and $P$ contains some subset of $S$, then $T(R\text{ on }P)$ is also a partial-order relation; that, or $P$ is the non-orderable units of $S$.

Anyhow, I have no examples of how to do this proof with a very general description of a relation/the sets it acts upon. How do I prove that that $T$ is a partial-order relation?

Best Answer

Here's an example.

Suppose we get our partial order by considering divisibility; let's say we've got the poset of all divisors of $12$, with $mRn$ if $m$ divides $n$. Then we can "restrict" this order to consider only divisors of, say, $6$ (or any other divisor of $12$, really). Or we could just pick our favorite handful of divisors of $12$, and keep the same strategy for ordering them; say we throw away $3$ and $12$. You can just draw the Hasse diagrams to "see" what's happening.

Divisors of 12Induced poset: Divisors of 6Induced poset: Throw away 3 and 12

Anyway, you're right, the result is obvious, and its proof is trivial. But this brings about its own difficulties: How do you even prove something when it's trivial?

By resorting to the definitions and doing some bookkeeping! Specifically, you need to show that

  • $T$ is reflexive: for all $x \in P$, we have $(x, x) \in T$.

  • $T$ is transitive: whenever $(x, y) \in T$ and $(y, z) \in T$, we have $(x, z) \in T$, and

  • $T$ is antisymmetric: whenever $x \neq y$ and $(x, y) \in T$, we have $(y, x) \not\in T$.

But since you're focusing only on $x, y \in P \subseteq S$ then $T$ "inherits" these properties from $R$, truly!

Let's look at the transitive one.

We'd like to show that $T$ is transitive: whenever $(x, y) \in T$ and $(y, z) \in T$, we have $(x, z) \in T$. To do that, we just assume we have some arbitrary $(x, y)$ and $(y, z)$ in $T$, and we'll be done once we've shown that $(x, z)$ is necessarily in $T$ as well.

Suppose $x, y, z \in P$, and $(x, y), (y, z) \in T$. By the definition of $$T = \{(a,b) \mid a \in P, b \in P, (a, b) \in R\},$$ we have that $(x, y)$ and $(y, z)$ are in $R$ as well, hence $(x, z) \in R$ since $R$ is transitive. But since $x, z \in P$ and $(x, z) \in R$, then again by the definition of $T$, we have $(x, z) \in T$, as desired.

Blech. But, it's completely mundane and is just a matter of crossing i's and dotting t's.

(By the way, $T$ is usually called an induced (sub)poset; you pick elements to include from a given poset, and are forced to included any relations that exist between them. I can't seem to find a Wikipedia-like reference for this, but I'm fairly sure it's at least somewhat standard.)

Related Question