I am trying to understand posets and if I have understood correctly – a poset is a set with a binary relation "≤" which is reflexive, transitive, and antisymmetrical.
I am having trouble understanding Hasse Diagrams and the way to denote a poset.
My current understanding for coming up with an example goes something like this:
1) Form a set: A = {1, 2, 3, 4}
2) Form a relation: ?
3) Draw a diagram based on the relation.
I'm not sure what the notation is supposed to be like in step 2). R = a set of pairs that fulfills reflexivity, transitivity, and asymmetry? What is the easiest way to come up with that and how do I write it out?
For drawing the diagram, I would usually draw an arrow for each relation – but from the examples I have seen not each relation has been directly joined and arrows are not necessarily used. How are they drawn?
I am just learning about this so it's still quite confusing as a whole and a simple and clear example would be helpful.
Also, if the relation is defined to be "≤" then why are there diagrams depicting other kinds of relations? What does it mean to be ordered by inclusion?
Would this be an example of a poset?
A = {1, 2, 3, 4}
and its Hasse diagram
4
|
3
|
2
|
1
?
Do I need to write out R, the relation?
I found this example of a Hasse diagram:
But it had no numbers or anything. How am I supposed to interpret it? How would a poset for this be written out?
Best Answer
The whole idea of a Hasse diagram is just an efficient representation of your poset. If you think about the set of subsets of $\{1,2,3\}$ ordered by inclusion (that is, $\subseteq$), we have ordered pairs like $(\varnothing, \{1\}),\, (\varnothing \{1,2\}),\, (\{1\}, \{1,2\})$, and so on, reflecting the fact that $\varnothing \subseteq \{1\}$, etc.
But since we know that $\subseteq$ is transitive, then knowing $\varnothing \subseteq \{1\}$ and $\{1\} \subseteq \{1,2\}$ tells us that $\varnothing \subseteq \{1,2\}$; it would be silly for our efficient representation to waste time representing this, as long as we make sure to represent $\varnothing \subseteq \{1\}$ and $\{1\} \subseteq \{1,2\}$:
So for example, the fact that we can trace a path from $\{1\}$ up to $\{1, 2, 3\}$ using edges in the Hasse diagram means that $\{1\} \subseteq \{1,2,3\}$, or equivalently, that the ordered pair $(\{1\}, \{1,2,3\})$ is in our relation.
We only draw edges in the Hasse diagram to depict so-called covering relations: So, we drew a line from $\{1\}$ to $\{1,2\}$ because if we have an inequality like
$$\{1\} \subseteq \Delta \subseteq \{1,2\},$$ then we're forced to use $\Delta = \{1\}$ or $\Delta = \{1,2\}$; nothing "fits" between them properly. Thus, we say that $\{1\}$ is covered by $\{1, 2\}$, and draw a line in the Hasse diagram.
We generally use the symbol $\le$ any time we have a poset, even if the relation has nothing to do with the normal definition of $\le$ to compare numbers. So we could write $\varnothing \le \{1\}$ in the example above, if we wanted to. Some people, to prevent this confusion, use the symbol $\preceq$ for a generic poset, to help you realize that the relation might have nothing to do with the usual way to order real numbers.
When you're given an unlabeled Hasse Diagram as in your last example, just call all of the nodes by some name; $\{1, 2, 3,4\}$ or $\{a, b, c, d\}$, it doesn't really matter. Just that we can see the comparisons between them.
So we could pick
and start getting ordered pairs $(a, c),\, (a, d),$ etc, since we can see that $a \le c$, $a \le d$, and so on. In this example, the only relations are covering relations, so we'll have as many ordered pairs as there are lines in the graph.
In your linear example with $1 \le 2 \le 3 \le 4$, we would have $4 + 3 + 2 + 1$ ordered pairs: $\{(i, j): i \le j\}$ even though there are only $3$ edges in the Hasse Diagram.