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 GraphSearch.
Concept
Szpilrajn extension theorem
Summary
In order theory, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930, states that every partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable. The theorem is one of many examples of the use of the axiom of choice in the form of Zorn's lemma to find a maximal set with certain properties.
A binary relation on a set is formally defined as a set of ordered pairs of elements of and is often abbreviated as
A relation is reflexive if holds for every element it is transitive if imply for all it is antisymmetric if imply for all and it is a connex relation if holds for all A partial order is, by definition, a reflexive, transitive and antisymmetric relation. A total order is a partial order that is connex.
A relation is contained in another relation when all ordered pairs in also appear in that is, implies for all The extension theorem states that every relation that is reflexive, transitive and antisymmetric (that is, a partial order) is contained in another relation which is reflexive, transitive, antisymmetric and connex (that is, a total order).
The theorem is proved in two steps. First, if a partial order does not compare and it can be extended by first adding the pair and then performing the transitive closure, and second, since this operation generates an ordering that strictly contains the original one and can be applied to all pairs of incomparable elements, there exists a relation in which all pairs of elements have been made comparable.
The first step is proved as a preliminary lemma, in which a partial order where a pair of elements and are incomparable is changed to make them comparable. This is done by first adding the pair to the relation, which may result in a non-transitive relation, and then restoring transitivity by adding all pairs such that This is done on a single pair of incomparable elements and and produces a relation that is still reflexive, antisymmetric and transitive and that strictly contains the original one.
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.