In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
area of
order theory
Order theory is a branch of mathematics that investigates the 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 intr ...
, every
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
''P'' gives rise to a dual (or opposite) partially ordered set which is often denoted by ''P''
op or ''P''
''d''. This dual order ''P''
op is defined to be the same set, but with the inverse order, i.e. ''x'' ≤ ''y'' holds in ''P''
op if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
''y'' ≤ ''x'' holds in ''P''. It is easy to see that this construction, which can be depicted by flipping the
Hasse diagram
In order theory, 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. Concretely, for a partially ordered set ''(S, ≤)'' one represents ea ...
for ''P'' upside down, will indeed yield a partially ordered set. In a broader sense, two partially ordered sets 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 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 elements
*
Maximal elements and minimal elements
*
Least upper bound
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest low ...
s (suprema, ∨) and
greatest lower bound
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
s (infima, ∧)
*
Upper sets and lower sets
*
Ideals and
filters
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
*
Closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S
:
Closure operators are dete ...
s and
kernel operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S
:
Closure operators are de ...
s.
Examples of notions which are self-dual include:
* Being a (
complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
)
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an ornam ...
*
Monotonicity
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of orde ...
of functions
*
Distributivity of lattices, i.e. the lattices for which ∀''x'',''y'',''z'': ''x'' ∧ (''y'' ∨ ''z'') = (''x'' ∧ ''y'') ∨ (''x'' ∧ ''z'') holds are exactly those for which the dual statement ∀''x'',''y'',''z'': ''x'' ∨ (''y'' ∧ ''z'') = (''x'' ∨ ''y'') ∧ (''x'' ∨ ''z'') holds
[The quantifiers are essential: for individual elements ''x'', ''y'', ''z'', e.g. the first equation may be violated, but the second may hold; see the N5 lattice for an example.]
* Being a
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
* Being an
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 (posets). Whenever two posets are order isomorphic, they can be cons ...
.
Since partial orders are
antisymmetric, the only ones that are self-dual are the
equivalence relations
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relati ...
(but the notion of partial order is self-dual).
See also
*
Converse relation
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent& ...
*
List of Boolean algebra topics
This is a list of topics around Boolean algebra and propositional logic.
Articles with a wide scope and introductions
* Algebra of sets
* Boolean algebra (structure)
* Boolean algebra
* Field of sets
* Logical connective
* Pro ...
*
Transpose graph
In the mathematical and algorithmic study of graph theory, the converse, transpose or reverse, entry 2.24 of a directed graph is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of th ...
*
Duality in category theory, of which duality in order theory is a special case
References
*
{{Order theory
Order theory
Order theory
Order theory is a branch of mathematics that investigates the 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 intr ...