Duality (order theory)
Encyclopedia
In the mathematical
area of order theory
, every partially ordered set
P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if
y ≤ x holds in P. It is easy to see that this construction, which can be depicted by flipping the Hasse diagram
for P upside down, will indeed yield a partially ordered set. In a broader sense, two posets are also said to be duals if they are dually isomorphic, i.e. if one poset is order isomorphic
to the dual of the other.
The importance of this simple definition stems from the fact that each and every definition and theorem of order theory can readily be transferred to the dual order. Formally, this is captured by the Duality Principle for ordered sets:
If a statement or definition is equivalent to its dual then it is said to be self-dual. Note that the consideration of dual orders is so fundamental that it often occurs implicitly when writing ≥ for the dual order of ≤ without giving any prior definition of this "new" symbol.
Examples of notions which are self-dual include:
Since partial orders are antisymmetric
, the only ones that are self-dual are the equivalence relations.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
area of order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, every partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
y ≤ x holds in P. It is easy to see that this construction, which can be depicted by flipping the Hasse diagram
Hasse diagram
In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...
for P upside down, will indeed yield a partially ordered set. In a broader sense, two posets are also said to be duals if they are dually isomorphic, i.e. if one poset is order isomorphic
Order isomorphism
In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets . Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of...
to the dual of the other.
The importance of this simple definition stems from the fact that each and every definition and theorem of order theory can readily be transferred to the dual order. Formally, this is captured by the Duality Principle for ordered sets:
- If a given statement is valid for all partially ordered sets, then its dual statement, obtained by inverting the direction of all order relations and by dualizing all order theoretic definitions involved, is also valid for all partially ordered sets.
If a statement or definition is equivalent to its dual then it is said to be self-dual. Note that the consideration of dual orders is so fundamental that it often occurs implicitly when writing ≥ for the dual order of ≤ without giving any prior definition of this "new" symbol.
Examples
Naturally, there are a great number of examples for concepts that are dual:- Greatest elements and least elementsGreatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
- Maximal elements and minimal elementsMaximal elementIn 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...
- Least upper bounds (suprema, v) and greatest lower bounds (infima, ^)
- Upper sets and lower setsUpper setIn mathematics, an upper set of a partially ordered set is a subset U with the property that x is in U and x≤y imply y is in U....
- IdealsIdeal (order theory)In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
and filtersFilter (mathematics)In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in... - Closure operatorClosure operatorIn mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
s and kernel operators.
Examples of notions which are self-dual include:
- Being a (complete) latticeLattice (order)In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
- MonotonicityMonotonic functionIn mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....
of functions - Distributivity of lattices, i.e. the lattices for which x ^ (y v z) = (x ^ y) v (x ^ z) holds are exactly those for which the dual statement x v (y ^ z) = (x v y) ^ (x v z) holds
- Being a Boolean algebra
- Being an order isomorphismOrder isomorphismIn the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets . Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of...
.
Since partial orders are antisymmetric
Antisymmetric
The word antisymmetric refers to a change to an opposite quantity when another quantity is symmetrically changed. This concept is related to that of Symmetry and Asymmetry. The difference between these three concepts can be simply illustrated with Latin letters. The character "A" is symmetric about...
, the only ones that are self-dual are the equivalence relations.