Namespaces
Variants
Actions

Difference between revisions of "Order (on a set)"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Category:Order, lattices, ordered algebraic structures)
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
''order relation''
 
''order relation''
  
A [[Binary relation|binary relation]] on some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700501.png" />, usually denoted by the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700502.png" /> and having the following properties: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700503.png" /> (reflexivity); 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700504.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700505.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700506.png" /> (transitivity); 3) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700507.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700508.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o0700509.png" /> (anti-symmetry). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005010.png" /> is an order, then the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005011.png" /> defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005012.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005014.png" /> is called a strict order. A strict order can be defined as a relation having the properties 2) and 3'): <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005016.png" /> cannot occur simultaneously. The expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005017.png" /> is usually read as "a is less than or equal to b" or "b is greater than or equal to a" , and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005018.png" /> is read as "a is less than b" or "b is greater than a" . The order is called total if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005019.png" /> either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005020.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005021.png" />. A relation which has the properties 1) and 2) is called a pre-order or a quasi-order. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005022.png" /> is a quasi-order, then the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005023.png" /> defined by the conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005025.png" /> is an [[Equivalence|equivalence]]. On the quotient set by this equivalence one can define an order by setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005026.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005027.png" /> is the class containing the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005028.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005029.png" />. For examples and references see [[Partially ordered set|Partially ordered set]].
+
A [[Binary relation|binary relation]] on some set $A$, usually denoted by the symbol $\leq$ and having the following properties: 1) $a\leq a$ (reflexivity); 2) if $a\leq b$ and $b\leq c$, then $a\leq c$ (transitivity); 3) if $a\leq b$ and $b\leq a$, then $a=b$ (anti-symmetry). If $\leq$ is an order, then the relation $<$ defined by $a<b$ when $a\leq b$ and $a\neq b$ is called a strict order. A strict order can be defined as a relation having the properties 2) and 3'): $a<b$ and $b<a$ cannot occur simultaneously. The expression $a\leq b$ is usually read as "a is less than or equal to b" or "b is greater than or equal to a", and $a<b$ is read as "a is less than b" or "b is greater than a". The order is called total if for any $a,b\in A$ either $a\leq b$ or $b\leq a$. A relation which has the properties 1) and 2) is called a pre-order or a quasi-order. If $\triangleleft$ is a quasi-order, then the relation $a\approx b$ defined by the conditions $a\triangleleft b$ and $b\triangleleft a$ is an [[Equivalence|equivalence]]. On the quotient set by this equivalence one can define an order by setting $[a]\leq[b]$, where $[a]$ is the class containing the element $a$, if $a\triangleleft b$. For examples and references see [[Partially ordered set|Partially ordered set]].
  
  
  
 
====Comments====
 
====Comments====
A total order is also called a linear order, and a set equipped with a total order is sometimes called a chain or [[Totally ordered set|totally ordered set]]. For emphasis, an order which is not (necessarily) total is often called a partial order; some writers use the notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005030.png" /> to indicate that neither <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005031.png" /> nor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070050/o07005032.png" /> holds.
+
A total order is also called a linear order, and a set equipped with a total order is sometimes called a chain or [[Totally ordered set|totally ordered set]]. For emphasis, an order which is not (necessarily) total is often called a partial order; some writers use the notation $a||b$ to indicate that neither $a\leq b$ nor $b\leq a$ holds.
  
 
[[Category:Order, lattices, ordered algebraic structures]]
 
[[Category:Order, lattices, ordered algebraic structures]]

Revision as of 21:26, 8 November 2014

order relation

A binary relation on some set $A$, usually denoted by the symbol $\leq$ and having the following properties: 1) $a\leq a$ (reflexivity); 2) if $a\leq b$ and $b\leq c$, then $a\leq c$ (transitivity); 3) if $a\leq b$ and $b\leq a$, then $a=b$ (anti-symmetry). If $\leq$ is an order, then the relation $<$ defined by $a<b$ when $a\leq b$ and $a\neq b$ is called a strict order. A strict order can be defined as a relation having the properties 2) and 3'): $a<b$ and $b<a$ cannot occur simultaneously. The expression $a\leq b$ is usually read as "a is less than or equal to b" or "b is greater than or equal to a", and $a<b$ is read as "a is less than b" or "b is greater than a". The order is called total if for any $a,b\in A$ either $a\leq b$ or $b\leq a$. A relation which has the properties 1) and 2) is called a pre-order or a quasi-order. If $\triangleleft$ is a quasi-order, then the relation $a\approx b$ defined by the conditions $a\triangleleft b$ and $b\triangleleft a$ is an equivalence. On the quotient set by this equivalence one can define an order by setting $[a]\leq[b]$, where $[a]$ is the class containing the element $a$, if $a\triangleleft b$. For examples and references see Partially ordered set.


Comments

A total order is also called a linear order, and a set equipped with a total order is sometimes called a chain or totally ordered set. For emphasis, an order which is not (necessarily) total is often called a partial order; some writers use the notation $a||b$ to indicate that neither $a\leq b$ nor $b\leq a$ holds.

How to Cite This Entry:
Order (on a set). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Order_(on_a_set)&oldid=34380
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article