Hasse diagram


Hasse diagram

In the mathematical discipline known as order theory, a Hasse diagram (pronEng|ˈhɑːsə "HAHS uh"), named after Helmut Hasse (1898–1979)) is a simple picture of a finite partially ordered set, forming a drawing of the transitive reduction of the partial order. Concretely, one represents each element of "S" as a vertex on the page and draws a line segment or curve that goes "upward" from "x" to "y" if "x" < "y", and there is no "z" such that "x" < "z" < "y". In this case, we say "y" covers "x", or "y" is an immediate successor of "x". Furthermore it is required that the vertices are positioned in such a way that each curve meets exactly two vertices: its two endpoints. Any such diagram (given that the vertices are labeled) uniquely determines a partial order, and any partial order has a unique transitive reduction, but there are many possible placements of elements in the plane, resulting in different Hasse diagrams for a given order that may have widely varying appearances.

Sometimes, the phrase "Hasse diagram" is used to refer to the transitive reduction as an abstract directed acyclic graph, independently of any drawing of that graph, but we eschew that usage here.

Examples

* The power set of { "x", "y", "z" } partially ordered by inclusion, has the Hasse diagram:

* The set "A" = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 } of all divisors of 60, partially ordered by divisibility, has the Hasse diagram:

* The set of all 15 partitions of the set { 1, 2, 3, 4 }, partially ordered by "refinement", i.e. a finer partition is "less than" a coarser partition, has the Hasse diagram:

Motivation

If we were to try to create some visual representation of a partially ordered set ("S", ≤), how would we proceed? We could begin by first creating a graph, where every node on the graph is an element in S, and every edge ("u", "v") in that graph would represent the relation "u" ≤ v.

Doing this, and trying to draw the graph, would result in a graph that would be very "busy". In fact, we carry a lot of redundant information in such a graph. Recall the requirements on a partial order:
*"a" ≤ "a" (reflexivity)
* if "a" ≤ "b" and "b" ≤ "c" then "a" ≤ "c" (transitivity)
* if "a" ≤ "b" and "b" ≤ "a" then "a" = "b" (antisymmetry)

Now, in our original graph, we have a number of edges — loops, on each node in the graph — in the form ("u", "u"), because reflexivity means that "u" ≤ "u". This must be true for every element in "S" (otherwise it would not be a partial order).

Say we were now to create a diagram, as above now, without loops, of the partially ordered set ({1,2,3,4}, ≤), where a finer partition of that set is "less than" a coarser partition. We would obtain the following graph:

However, in this graph, we still carry redundant information. Referring back to the requirements of a partial order, we see the requirement of transitivity. In the above graph, we are including edges ("a","c"), ("a","b"), and ("b","c"). We do not need to carry the extra edge ("a","c") because the other two edges imply the third exists.

This means we need only include an edge between a member of the set, and its immediate predecessor. We do not need the edges to the other predecessors because we have transitivity, nor do we need to draw loops at each edge because we have reflexivity.

If we were to stop here and draw the diagram again according to these new requirements, we obtain the third image above, in the Example section. We can stop here, but it may be useful to define the Hasse diagram in terms of another relation which automatically excludes these cases.

Cover relation

Symbolically, all edges in the Hasse diagram should be of the form ("x", "y") where "x" < "y" (this stricter relation means we exclude cases of loops as before), and that there exists no element "z" in the set such that "x" < "z" < "y" (this is another way of excluding drawing extra edges because of transitivity).

This relation is known as the "cover relation", and the Hasse diagram is often defined in terms of this relation. An element "y" is said to "cover" "x" if "y" is an immediate successor of "x". The (strict) partial ordering is then just the transitive closure of this cover relation.

The Hasse diagram of "S" may then be defined abstractly as the set of all ordered pairs ("x", "y") such that "y" covers "x", i.e., the Hasse diagram may be identified with the inverse of the cover relation.

Finding a "good" Hasse diagram

Although Hasse diagrams are simple as well as intuitive tools for dealing with finite posets, it turns out to be rather difficult to draw "good" diagrams. The reason is that there are in general many (in fact: infinitely many) possible ways to draw a Hasse diagram for a given poset. Yet, the simple technique of just starting with the minimal elements of an order and then adding greater elements incrementally often produces quite poor results: symmetries and internal structure of the order are easily lost.

The following example demonstrates the problem. Consider the powerset of the set "S" = {"a", "b", "c", "d"}, i.e. the set of all subsets of "S", written as mathcal{P}(S). This powerset can easily be ordered via subset inclusion subseteq. Below there are three different principal ways to draw a Hasse diagram for this order:

The labels in these diagrams have been left out to save space, but it should be an easy exercise to assign the subsets of "S" to the given vertices. The leftmost version is probably closest to the naive way of constructing diagrams: the five layers of the graph represent the numbers of elements that the subsets at each level contain. Note that there are many different ways to assign concrete one-element sets to the second layer, but that this assignment will determine the labels of all other elements. The circumstance that more than one labeling of each of the diagrams is possible reflects the fact that the poset in this example is automorphic — even in many different ways.

The above example demonstrates how different Hasse diagrams for the same order can be, and how each representation can reflect different aspects of the underlying mathematical structure. The leftmost diagram relates the number of elements to the level of each vertex. The rightmost drawing strongly emphasizes the internal symmetry of the structure. Finally, the middle one constructs the picture from two cubes such that the relationship between the powerset 2"S" and the product order 2 × 2{"a", "b", "c"} is emphasized.

Various algorithms for drawing better diagrams have been proposed, but today good diagrams still heavily rely on human assistance. However, even humans need quite some practice to draw instructive diagrams.

ee also

* Lattice (order)
* Mathematical diagram

References

Further reading

* Patrick Suppes 1957, Dover reprint 1999, "Introduction to Logic", Dover Publications Inc., Mineola NY. ISBN 0-486-40687-3 (pbk.). cf a short discussion in §10.5 Ordering Relations pp.220–225.

External links

* [http://www.win.tue.nl/ida/demo/c1s1ja.html Hasse diagrams of divisors]
* [http://www.math.northwestern.edu/~mlerma/courses/cs310-04w/notes/dm-relations.pdf How to draw hasse diagrams of binary relations]
* [http://mathworld.wolfram.com/HasseDiagram.html "Hasse Diagram" on MathWorld]
* [http://www.flickr.com/photos/hexadecimal_time/2418492457/ Detailed Hasse diagram of all sixteen logical connectives (four element set´s power set)]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Hasse diagram — noun A diagram which represents a finite poset, in which nodes are elements of the poset and arrows represent the order relation between elements. Transitivity of the order relation is tacit, in other words, if and then no arrow is drawn from x… …   Wiktionary

  • Hasse — may refer to:People with the surname Hasse: * Peter Hasse (c. 1585–1640), German organist and composer * Johann Adolph Hasse (1699–1783), German composer * Henry Hasse (1913–1977), US writer of science fiction * Helmut Hasse (1898–1979), German… …   Wikipedia

  • Hasse-Diagramm — In der Mathematik ist ein Hasse Diagramm eine bestimmte graphische Darstellung endlicher halbgeordneter Mengen. Solche Diagramme wurden 1967 von dem Mathematiker Helmut Hasse eingeführt. Das Hasse Diagramm für eine Halbordnung ist ein gerichteter …   Deutsch Wikipedia

  • Diagram — Further information: Chart Sample flowchart representing the decision process to add a new article to Wikipedia. A diagram is a two dimensional geometric symbolic representation of information according to some visualization technique. Sometimes …   Wikipedia

  • Mathematical diagram — This article is about general diagrams in mathematics. For diagrams in the category theoretical sense, see Diagram (category theory). Euclid s Elements, ms. from Lüneburg, A.D. 1200 Mathematical diagrams are diagrams in the field of mathematics,… …   Wikipedia

  • Helmut Hasse — Infobox Scientist name=Helmut Hasse birth date = August 25 1898 death date = December 26 1979 field = MathematicsHelmut Hasse (IPA2|ˈhasə) (25 August 1898 – 26 December 1979) was a German mathematician working in algebraic number theory, known… …   Wikipedia

  • Frattini subgroup — Hasse diagram of the lattice of subgroups of the dihedral group Dih4 In the 3 element layer are the maximal subgroups; their intersection (the F. s.) is the central element in the 5 element layer. So Dih4 has only one non generating element… …   Wikipedia

  • Complemented lattice — Hasse diagram of a complemented lattice A point and a line of the Fano plane are complements, when In the mathematical discipline of order theory, a complemented lattice is a bounded lattice in which every element a …   Wikipedia

  • Modular lattice — Hasse diagram of N5, the smallest non modular lattice. In the branch of mathematics called order theory, a modular lattice is a lattice that satisfies the following self dual condition: Modular law x ≤ b implies… …   Wikipedia

  • Hassediagramm — In der Mathematik ist ein Hasse Diagramm eine bestimmte graphische Darstellung halbgeordneter Mengen. Solche Diagramme wurden 1967 von dem Mathematiker Helmut Hasse eingeführt. Das Hasse Diagramm für eine Halbordnung ist ein gerichteter Graph,… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.