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
Total order
Summary
In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation on some set , which satisfies the following for all and in :
(reflexive).
If and then (transitive).
If and then (antisymmetric).
or (strongly connected, formerly called total).
Reflexivity (1.) already follows from connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders.
Total orders are sometimes also called simple, connex, or full orders.
A set equipped with a total order is a totally ordered set; the terms simply ordered set, linearly ordered set, and loset are also used. The term chain is sometimes defined as a synonym of totally ordered set, but refers generally to some sort of totally ordered subsets of a given partially ordered set.
An extension of a given partial order to a total order is called a linear extension of that partial order.
A on a set is a strict partial order on in which any two distinct elements are comparable. That is, a strict total order is a binary relation on some set , which satisfies the following for all and in :
Not (irreflexive).
If then not (asymmetric).
If and then (transitive).
If , then or (connected).
Asymmetry follows from transitivity and irreflexivity; moreover, irreflexivity follows from asymmetry.
For delimitation purposes, a total order as defined in the lead is sometimes called non-strict order.
For each (non-strict) total order there is an associated relation , called the strict total order associated with that can be defined in two equivalent ways:
if and (reflexive reduction).
if not (i.e., is the complement of the converse of ).
Conversely, the reflexive closure of a strict total order is a (non-strict) total order.
Any subset of a totally ordered set X is totally ordered for the restriction of the order on X.
The unique order on the empty set, ∅, is a total order.
Any set of cardinal numbers or ordinal numbers (more strongly, these are well-orders).
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.