1
$\begingroup$

I'm doing a section on directed graphs and Hasse diagrams right now on partially ordered sets, and I'm trying to understand what it means for two elements in a Hasse diagram to be comparable.

For example, on Wikipedia it states in the set of all subsets of a three element set, {x,y,z}, that the set {x} and {x,y,z} are comparable. And that for two elements to be comparable, it must satisfy the condition that $x \preceq y$ and $y \preceq x$

I'm having trouble understanding how the set {x} and the set {x,y,z} are anti-symmetric (because how does {x} = {x,y,z}?) first off, and how $\{x,y,z\} \preceq \{x\}$? Besides that how can I understand what is a partially ordered set of what in a Hasse diagram, or how to tell if elements are comparable within a Hasse diagram?

$\endgroup$
  • $\begingroup$ Sets aren't anti-symmetric (well some are, but ignore this), binary relations can be anti-symmetric. In a Hasse diagram two elements are comparable if you can go from one to another by going either straight up or straight down. $\endgroup$ – Git Gud Mar 4 '15 at 9:32
  • $\begingroup$ @GitGud So for the binary relation, where xRy is x is a subset of y, and anti-symmetric means xRy and yRx then x = y, I get how {x} is a subset of {x,y,z} but how is {x,y,z} a subset of {x}? and what defines the = then? I'm confused :( $\endgroup$ – Alex Mar 4 '15 at 9:36
2
$\begingroup$

A partially ordered set is any set $S$ with a relation $\preceq$ which is antisymmetric, transitive and reflexive.

Wikipedia correctly states that two elements are comparable if $x\preceq y$ or $y\preceq x$ so in your example everything is fine $\{x\}\preceq\{x,y,z\}$ but not the other way around.

As to how to understand a Hasse diagram this is fairly straightforward. The lines in a Hasse diagram are oriented (usually top down) and if there is a line from $y$ (above) to $x$ (below), this indicates that $x\preceq y$, $x\neq y$ and $\forall z (x\preceq z\preceq y)\implies (x=z)\vee(y=z)$. In words that just says a line from $y$ to $x$ when $x$ is below $y$, means that $x\prec y$ and there are no elements between them.

You can really think of a Hasse diagram of $\preceq$, as the diagram of the minimal relation $R$ such that it's transitive closure is $\preceq$.

When you are reading the relation off the diagram you can just follow the lines as pointed out in comments. If you can get from $x$ to $y$ along only upward sloping lines then $x\preceq y$.

$\endgroup$

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.