**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# Preorder

Summary

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cases of a preorder: an antisymmetric (or ) preorder is a partial order, and a symmetric preorder is an equivalence relation.
The name comes from the idea that preorders (that are not partial orders) are 'almost' (partial) orders, but not quite; they are neither necessarily antisymmetric nor asymmetric. Because a preorder is a binary relation, the symbol can be used as the notational device for the relation. However, because they are not necessarily antisymmetric, some of the ordinary intuition associated to the symbol may not apply. On the other hand, a preorder can be used, in a straightforward fashion, to define a partial order and an equivalence relation. Doing so, however, is not always useful or worthwhile, depending on the problem domain being studied.
In words, when one may say that b a or that a b, or that b to a. Occasionally, the notation ← or → or is used instead of
To every preorder, there corresponds a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. The converse is not true: most directed graphs are neither reflexive nor transitive. In general, the corresponding graphs may contain cycles. A preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a directed acyclic graph. A preorder that is symmetric is an equivalence relation; it can be thought of as having lost the direction markers on the edges of the graph. In general, a preorder's corresponding directed graph may have many disconnected components.
Consider a homogeneous relation on some given set so that by definition, is some subset of and the notation is used in place of Then is called a or if it is reflexive and transitive; that is, if it satisfies:
Reflexivity: for all and
Transitivity: if for all
A set that is equipped with a preorder is called a preordered set (or proset).

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 courses (4)

Related publications (9)

Related lectures (12)

Related concepts (29)

Ontological neighbourhood

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

HUM-228: Musical studies B

Ce cursus particulier - dont l'admission est sujette à l'acceptation d'un dossier de candidature - offre à l'étudiant engagé dans des études en musique de haut niveau en parallèle à ses études EPFL la

HUM-415: Musical studies II

Ce cursus particulier - dont l'admission est sujette à l'acceptation d'un dossier de candidature - offre à l'étudiant engagé dans des études en musique de haut niveau en parallèle à ses études EPFL la

Relations in Computer Science

Explores the properties of relations in computer science, including equivalence relations and the partition of a set.

Physics 1: Normal Acceleration and Spatial Rotations

Explores normal acceleration, spatial rotations, vector rotation, and angular speed concepts in physics.

Relations: Reflexive, Symmetric, Antisymmetric, Transitive

Explains binary relations on a set and their properties with illustrative examples.

Order theory

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary. Orders are everywhere in mathematics and related fields like computer science. The first order often discussed in primary school is the standard order on the natural numbers e.

Homogeneous relation

In mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations.

Category (mathematics)

In mathematics, a category (sometimes called an abstract category to distinguish it from a ) is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the , whose objects are sets and whose arrows are functions. is a branch of mathematics that seeks to generalize all of mathematics in terms of categories, independent of what their objects and arrows represent.

The baseplate of phage T4 is an important model system in viral supramolecular assembly. The baseplate consists of six wedges surrounding the central hub. We report the first successful attempt at complete wedge assembly using an in vitro approach based on ...

2010Gábor Tardos, Abhishek Methuku

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...

Jean-Philippe Thiran, Alessandra Griffa, Patric Hagmann, Olaf Sporns

6 The complex relationship between structural and functional connectivity, as measured by noninvasive imaging of the human brain, poses many unresolved challenges and open questions. Here, we apply analytic measures of network communication to the structur ...