In mathematics, two elements x and y of a set P are said to be comparable with respect to a binary relation ≤ if at least one of x ≤ y or y ≤ x is true. They are called incomparable if they are not comparable. A binary relation on a set is by definition any subset of Given is written if and only if in which case is said to be to by An element is said to be , or (), to an element if or Often, a symbol indicating comparison, such as (or and many others) is used instead of in which case is written in place of which is why the term "comparable" is used. Comparability with respect to induces a canonical binary relation on ; specifically, the induced by is defined to be the set of all pairs such that is comparable to ; that is, such that at least one of and is true. Similarly, the on induced by is defined to be the set of all pairs such that is incomparable to that is, such that neither nor is true. If the symbol is used in place of then comparability with respect to is sometimes denoted by the symbol , and incomparability by the symbol . Thus, for any two elements and of a partially ordered set, exactly one of and is true. A totally ordered set is a partially ordered set in which any two elements are comparable. The Szpilrajn extension theorem 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. Both of the relations and are symmetric, that is is comparable to if and only if is comparable to and likewise for incomparability. Comparability graph The comparability graph of a partially ordered set has as vertices the elements of and has as edges precisely those pairs of elements for which . When classifying mathematical objects (e.g., topological spaces), two are said to be comparable when the objects that obey one criterion constitute a subset of the objects that obey the other, which is to say when they are comparable under the partial order ⊂.

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.
Related lectures (3)
Partial Ordering: Relations, Sequences, Summation
Explores partial orderings, divisibility relations, lattices, lexicographic ordering, comparability, and total orderings.
Equivalence Relations and Partial Orderings
Introduces equivalence relations, partitions, partial orderings, and total ordering concepts with examples and definitions.
Relations and Sequences
Covers relations, sequences, and posets, emphasizing properties like anti-symmetry and transitivity, and introduces arithmetic and geometric progressions.
Related publications (9)

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...
CAMBRIDGE UNIV PRESS2020

String graphs and incomparability graphs

János Pach

Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,
2012

High b-value diffusion-weighted imaging: a sensitive method to reveal white matter differences in schizophrenia

Jean-Philippe Thiran, Reto Meuli, Pierre Marquet, Patric Hagmann, Djalel Eddine Meskaldji, Leila Cammoun, Philipp Baumann

Over the last ten years, Diffusion-weighted Imaging (DWI) has become an important tool to investigate white matter (WM) anomalies in schizophrenia. Despite technological improvement and the exponential use of this technique, discrepancies remain and little ...
Elsevier2012
Show more
Related concepts (4)
Weak ordering
In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered sets (rankings without ties) and are in turn generalized by (strictly) partially ordered sets and preorders.
Transitive relation
In mathematics, a relation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c. Each partial order as well as each equivalence relation needs to be transitive. A homogeneous relation R on the set X is a transitive relation if, for all a, b, c ∈ X, if a R b and b R c, then a R c. Or in terms of first-order logic: where a R b is the infix notation for (a, b) ∈ R. As a non-mathematical example, the relation "is an ancestor of" is transitive.
Binary relation
In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain. A binary relation over sets X and Y is a new set of ordered pairs (x, y) consisting of elements x in X and y in Y. It is a generalization of the more widely understood idea of a unary function. It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.