Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Partially ordered set
Summary
In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.
Formally, a partial order is a homogeneous binary relation that is reflexive, transitive and antisymmetric. A partially ordered set (poset for short) is a set on which a partial order is defined.
The term partial order usually refers to the reflexive partial order relations, referred to in this article as non-strict partial orders. However some authors use the term for the other common type of partial order relations, the irreflexive partial order relations, also called strict partial orders. Strict and non-strict partial orders can be put into a one-to-one correspondence, so for every strict partial order there is a unique corresponding non-strict partial order, and vice versa.
A reflexive, weak, or , commonly referred to simply as a partial order, is a homogeneous relation ≤ on a set that is reflexive, antisymmetric, and transitive. That is, for all it must satisfy:
Reflexivity: , i.e. every element is related to itself.
Antisymmetry: if and then , i.e. no two distinct elements precede each other.
Transitivity: if and then .
A non-strict partial order is also known as an antisymmetric preorder.
An irreflexive, strong, or is a homogeneous relation < on a set that is irreflexive, asymmetric, and transitive; that is, it satisfies the following conditions for all
Irreflexivity: not , i.e. no element is related to itself (also called anti-reflexive).
Asymmetry: if then not .
Transitivity: if and then .
Irreflexivity and transitivity together imply asymmetry. Also, asymmetry implies irreflexivity. In other words, a transitive relation is asymmetric if and only if it is irreflexive. So the definition is the same if it omits either irreflexivity or asymmetry (but not both).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.