|
In the mathematical discipline known as order theory, a Hasse diagram (pronounced 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. For other meanings of mathematics or math, see mathematics (disambiguation). ...
Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ...
Helmut Hasse (pronounced HAHS uh) (25 August 1898- 26 December 1979) was a German mathematician working in algebraic number theory, known for fundamental contributions to class field theory, the application of p-adic numbers to local classfield theory and diophantine geometry (Hasse principle), and to local zeta functions. ...
In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. ...
As a branch of Graph theory, Graph drawing applies topology and geometry to derive visual and haptic representations of graphs. ...
In mathematics, the transitive reduction of a binary relation R on a set X is the smallest relation on X such that that the transitive closure of is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then is unique. ...
The geometric definition of a line segment In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. ...
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. A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ...
Examples
- 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:
In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ...
Image File history File links Lattice_of_the_divisibility_of_60. ...
A partition of U into 6 blocks: a Venn diagram representation. ...
Image File history File links Lattice_of_partitions_of_an_order_4_set. ...
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: A partition of U into 6 blocks: a Venn diagram representation. ...
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. Image File history File links Lattice_of_partitions_of_an_order_4_set_redundant. ...
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. In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ...
In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ...
If we were to stop here and draw the diagram again according to these new requirements, we obtain the first 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. In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ...
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. In mathematics, especially order theory, a partially ordered set (or poset) is a set equipped with a partial order relation. ...
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually. ...
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  . This powerset can easily be ordered via subset inclusion  . Below there are three different principal ways to draw a Hasse diagram for this order: In mathematics, given a set S, the power set of S, written P(S) or 2S, is the set of all subsets of S. In formal language, the existence of power set of any set is presupposed by the axiom of power set. ...
A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...
 Hasse diagram of a four-elements-sets power set. | | | 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 4D-hypercube, layered according to distance from one corner. ...
Image File history File links Hypercube_star. ...
Image File history File links Hypercube_cubes. ...
Image File history File links Download high-resolution version (1817x2571, 629 KB) The sixteen logic functions or junctors and thus the subsets of a set containing four elements form the rhombic-dodecahedral shadow of a tesseract when represented as a Hasse-diagram. ...
Image File history File links Download high-resolution version (1817x2571, 629 KB) The sixteen logic functions or junctors and thus the subsets of a set containing four elements form the rhombic-dodecahedral shadow of a tesseract when represented as a Hasse-diagram. ...
Image File history File links Download high-resolution version (1485x2112, 368 KB) The vertex-first-shadow of a 4-dimensional cube (called octahedroid or tesseract) is a rhombic dodecahedron. ...
Image File history File links Download high-resolution version (1485x2112, 368 KB) The vertex-first-shadow of a 4-dimensional cube (called octahedroid or tesseract) is a rhombic dodecahedron. ...
The rhombic dodecahedron is a convex polyhedron with 12 rhombic faces. ...
Stereographic projection In geometry, the tesseract is the four-dimensional analog of the (three-dimensional) cube, where motion along the fourth dimension is often a representation for bounded transformations of the cube through time. ...
In the mathematical area of order theory, given a partially ordered set (S, ≤) an order automorphism of (S, ≤) is an order isomorphism from (S, ≤) to itself. ...
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 first diagram relates the number of elements to the level of each vertex. The second drawing strongly emphasizes the internal symmetry of the structure. Finally, the third one constructs the picture from two cubes such that the relationship between the powerset 2S and the product order 2 × 2{a, b, c} is emphasized. In mathematics, given two ordered sets A and B, one can induce an ordering on the Cartesian product A × B. Given two pairs (a1,b1) and (a2,b2) in A × B, one sets (a1,b1) ≤ (a2,b2) if and only if a1 ≤ a2 and b1 ≤ b2. ...
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. In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
See also The name lattice is suggested by the form of the Hasse diagram depicting it. ...
External links |
Feeds |
Contact