1

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.

Bartek
  • 6,265
Celeritas
  • 2,743

1 Answers1

1

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.

Community
  • 1
Git Gud
  • 31,356
  • Oh right because (1,2) and (2,3) is in R but (1,3) is not. Is that why transitivity fails? – Celeritas Nov 24 '13 at 11:54
  • @Celeritas Exactly. It also fails because $(2,3), (3,1)\in R$, but $(2,1)\not \in R$. – Git Gud Nov 24 '13 at 11:55
  • I don't get the algorithm because 1)what's Euclidian plane 2)I don't know what it means for x to cover y? – Celeritas Nov 24 '13 at 12:31
  • @Celeritas Just think of the euclidean place as $\Bbb R^2$. Intuitively, $x$ covers $y$ if there aren't any elements between $x$ and $y$. For instance here, ${x,y}$ and ${x,z}$ both cover ${x}$, but ${x,y,z}$ and ${y,z}$ don't (for different reasons). – Git Gud Nov 24 '13 at 12:34
  • Ok but I don't see how an algorithm for drawing Hasse diagram explains why there can't be any loops in a partially ordered set. – Celeritas Nov 24 '13 at 12:48
  • If there is a loop, it means you're able to go from a vertice to another vertice and back (perhaps going through some more vertices in between), but in a diagram you can only "go up". If you're coming down too you're getting something like $\color{blue}x<y<z<\color{blue}x$. – Git Gud Nov 24 '13 at 12:51
  • Right. I really don't see such a violation x<y<z<x what is wrong with that? Seriously what rule does that violate? – Celeritas Nov 24 '13 at 12:52
  • @Celeritas You get $x<x$ and that can't happen. – Git Gud Nov 24 '13 at 12:53
  • :( why not? Sorry but that's not apparent to me. < isn't the actual less than operator, right, it's the precedes operator? – Celeritas Nov 24 '13 at 12:53
  • 1
    @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? – Git Gud Nov 24 '13 at 12:55
  • Yes that's clear but are we talking about the less than operator, or something different? My understanding is in the context of partial orders the operator $\prec$ is used which isn't actually the same as <. I think that's what my confusion is. – Celeritas Nov 24 '13 at 12:59
  • 1
    @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? – Git Gud Nov 24 '13 at 13:36
  • You say you can't have $x<x$ and I agree with that but isn't the irrelevant in this conversation since we're actually concerned with $x \prec x$ and I know of no reason why this is an invalid statement. – Celeritas Nov 24 '13 at 13:45
  • @Celeritas The very definition of $\prec$ implies that $a\prec b\implies a<b$. – Git Gud Nov 24 '13 at 13:56
  • What is the definition of $\prec$? My textbook doesn't have it and I can't Google search it because it doesn't have a name. – Celeritas Nov 24 '13 at 14:36
  • 1
    @Celeritas It's what denoted here as '$<\cdot$', $a\prec b$ means '$b$ covers $a$'. – Git Gud Nov 24 '13 at 14:37