HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are two elements always in a relation within a partially ordered set?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
elementsaresetalwayswithinpartiallytworelationordered

Problem

In a partially ordered set, am I always able to order two arbitrary elements out of the set? Or is it possible that two elements within the set have no order relation to each other?

For example if there are three elements $\{a, b, c\}$ and $a \leq b$ and $a \leq c$, does either $b \leq c$ or $c \leq b$ have to hold?

I need this to understand the fixed point theory for semantics of programming languages (denotation of while loops).

Solution

In a partially ordered set, there may be members which are not comparable. A partial order where all elements are comparable is called a total order.

We say $a$ and $b$ are comparable when at least one of the following holds:

  • $a\leq b$,



  • $b \leq a$.

Context

StackExchange Computer Science Q#764, answer score: 8

Revisions (0)

No revisions yet.