1
$\begingroup$

I was wondering if partially ordered sets could have loops in their diagrams. For example isn't the $S=\{1,2,3\}$ and relation $R=\{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\}$ a partially ordered set that has a cycle? $R$ is reflexive, antisymmetric and transitive.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Transitivy fails for your relation $R$.

As for loops on the diagram, that is not possible due to transitivy, that should become apparent from the algorithm to draw diagrams I describe in this answer.

$\endgroup$
16
  • $\begingroup$ Oh right because (1,2) and (2,3) is in R but (1,3) is not. Is that why transitivity fails? $\endgroup$
    – Celeritas
    Nov 24, 2013 at 11:54
  • $\begingroup$ @Celeritas Exactly. It also fails because $(2,3), (3,1)\in R$, but $(2,1)\not \in R$. $\endgroup$
    – Git Gud
    Nov 24, 2013 at 11:55
  • 1
    $\begingroup$ @Celeritas In a partial order, $a<b\iff a\leq b \land a\neq b$, replacing $a$ and $b$ with $x$ yields $x<x\iff x\leq x \land \color{red}{x\neq x}$. Is this clear? $\endgroup$
    – Git Gud
    Nov 24, 2013 at 12:55
  • 1
    $\begingroup$ @Celeritas $\prec$ is used for covering. Notice the name of the command \prec, it comes from preciding which is the same as covering. In my comment above $<$ intuitively is 'less than', yes and it is different from $\prec$. What exactly aren't you understanding at the moment? $\endgroup$
    – Git Gud
    Nov 24, 2013 at 13:36
  • 1
    $\begingroup$ @Celeritas It's what denoted here as '$<\cdot$', $a\prec b$ means '$b$ covers $a$'. $\endgroup$
    – Git Gud
    Nov 24, 2013 at 14:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .