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.
Definitions and statement
A binary relation R on a set X is formally defined as a set of ordered pairs (x, y) of elements of X, and (x, y) \in R is often abbreviated as xRy.
A relation is reflexive if xRx holds for every element x \in X; it is transitive if xRy \text{ and } yRz imply xRz for all x, y, z \in X; it is antisymmetric if

Official source

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.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications

Related people

No results

No results

Related concepts

No results

Related units

Related courses

Related lectures

No results

No results

No results