A partial order $P$ on a set $X$ is a binary relation, so a subset $P\subset X^2$. Subsets of $P$ might or might not be partial orders themselves, depending on whether transitivity is preserved.

  • Does this type of question; "is this subset of $P$ a partial order", appear in some paper? How are they usually called, how would I be able to look up for them?

Usually looking for "subsets of partial orders" gives results about the "partial order of subsets" instead.

The only clue I've been able to find so far is in the Wikipedia entry of binary relations, where it says

A relation $R$ over two sets $X$ and $Y$ is said to be contained in a relation $S$ over $X$ and $Y$ if $R$ is a subset of $S$, that is, for all $x$ in $X$ and $y$ in $Y$, if $xRy$ then $xSy$. In this case, if $R$ and $S$ disagree, $R$ is also said to be smaller than $S$. For example, $>$ is contained in $≥$.

However I was not able to find further sources for this, and again looking for "containment of binary relations" instead results in "the containment binary relation".

  • $\begingroup$ A subset of $P$ may also not be reflexive or anti-symmetric over $X$; so it doesn't depend only on whether or not the subset is transitive. For example, if $X=\{0,1\}$, and $P=\{(0,0),(0,1),(1,1)\}$, then $P$ is an order relation over $X$. But $P_1=\{(0,1)\}$ is not, because it's not reflexive. $\endgroup$ – amrsa Aug 17 '19 at 9:24

A (ordered) subset of a partial order is a subset that inherits the order.
A suborder is a subset of the order that is also an order.
The smallest suborder is equality, an antichain.
The antichain {1,2,3} is a subordered subset of the usually ordered integers.
Though { (1,2), (2,3), (2,2) } is a subset of the usual order for {1,2,3}, it is not a suborder. { (1,1), (2,2), (3,3), (1,2), (1,3) } is.
When an order is extended to a linear order, that order is a suborder of the linear order.
Though occasionally extensions may be considered, I never seen suborders used.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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