2

I understand that why a partially ordered set needs to be antisymmetric and transitive. I just can't see the logic behind why it has to be reflexive?

William
  • 4,893
  • @SaucyO'Path Can't it be greater than or equal to? – William Aug 26 '18 at 16:15
  • I read $a\le b$ as "$a$ smaller or equal than $b$", so I say that one. Of course, $\ge$ is itself a partial order, and in general if $R$ is a partial order then $R^{-1}$ defined by $aR^{-1}b\stackrel{\text{def}}\iff bRa$ is a partial order as well. –  Aug 26 '18 at 16:17

1 Answers1

4

Because it mimics the usual meaning of "smaller-or-equal-than". In fact, there is a "dual" notion of "strict partial order":

A binary relation $R$ on a set $X$ is a strict partial order if and only if:

  1. $\forall x\in X,\ \neg xR x$
  2. $\forall x,y\in X,\ (xRy\land yRx)\to x=y$
  3. $\forall x,y,z\in X,\ (xR y\land yR z)\to xR z$

Notice that $[(1)\land (2)]$ could have been restated equivalently as $[\forall x,y\in X,\ (\neg xRy\lor \neg yRx)]$.

An instance of these is the usual "$<$" on $\Bbb R$. Just as the names and examples suggest:

  • for any partial order $P$ on a set $X$ the relation $x\Bbb S_Py\stackrel{\text{def}}\iff (x Py\land x\ne y)$ is a strict partial order;

  • for any strict partial order $S$ on a set $X$ the relation $x\Bbb P_Sy\stackrel{\text{def}}\iff (x Sy\lor x= y)$ is a partial order;

  • for any partial order $P$ and for any strict partial order $S$, $\Bbb S_{\Bbb P_S}=S$ and $\Bbb P_{\Bbb S_P}=P$.

Community
  • 1
  • +1. Although I have a doubt. Does the binary relation involved in ordered set always has to be either $≤ $ or $≥$ , or it can be anything else too? – William Aug 26 '18 at 19:07
  • 1
    @William A commonly used partial order is inclusion of sets, which is inherently different from the usual total order of $\Bbb R$. –  Aug 26 '18 at 19:42
  • Yes but then if I'm not mistaken, if you use that, the set will only ever be a partially ordered and can never be a totally ordered set as law of trichotomy wouldn't apply. Correct me if I'm wrong. – William Aug 26 '18 at 19:53
  • 1
    It is indeed the case that the power set of a set with at least two elements is not totally ordered by $\subseteq$. –  Aug 26 '18 at 19:56
  • Thanks a lot for your time man. You been a big help. :) – William Aug 26 '18 at 19:58
  • @SaucyO'Path I actually had the same question as the original OP, and found this question and your answer. But, I still don't understand it. Why would a partial order mirror something like $\leq$? As you say yourself, a strict partial order would behave something like $<$ ... but by its name would still be considered a type of partial order. And that's exactly how I got to this question as well: why do we have to assume anything about its reflexive properties when it comes to partial orders? I am with William: it seems like only Antisymmetry and Transivitity are the real important ones. – Bram28 Mar 19 '21 at 19:28
  • Strict partial orders aren't partial orders. They are relations that may be writen as $\text{partial order}\land x\ne y$ @bram28 –  Mar 20 '21 at 20:17
  • But from $\text{partial order} \land x \neq y$ I can logically infer $\text{partial order}$ @SaucyO'Path – Bram28 Mar 20 '21 at 20:32
  • @Bram28 I don't see how you would. –  Mar 20 '21 at 21:04
  • @SaucyO'Path I was just going by your earlier comment.... from $P \land Q$ I can infer $P$. But yeah, I was being facetious there. :P But look, my serious question is this: Yes, I know how partial orders are defined. ... my question is why mathematicians defined them that way. That is, it seems that for any kind of 'order', all you need is anti-symmetry and transitivity: that alone will allow me to either line up all objects (in case of a total order), or at least create a lattice (and as such I would have a partial order). Reflexivity seems irrelevant to the basic idea of an order. – Bram28 Mar 20 '21 at 21:41
  • @Bram28 I don't know why exactly. I can see concepts of maximality and least upper bound being stated more naturally with $\le$, other than the fact that a number of proofs boil down to showing $a=b$ by showing $a\le b\land b\le a$. Anyways, the spirit of my answer is that the two notions are equally powerful and therefore you could choose one or the other (although I don't necessarily agree with your choice). –  Mar 21 '21 at 10:58
  • @Bram28 Notice however that the point I'm making is about chosing a transitive and asymmetric relation over a transitive, reflexive and antisymmetric relation. A statement on the truth value of all the $aRa$ must be made either way. –  Mar 21 '21 at 11:15