Section 3: Relations

Properties

1. Comparability (C): for every $x$ and $y$ , either $x=y$ or $xCy$ or $yCx$ .
2. Reflexivity (R): $xCx$ for every $x$ .
3. Nonreflexivity (nR): $xCx$ never holds.
4. Symmetry (S): if $xCy$ then $yCx$ .
5. Antisymmetry (aS): if $xCy$ then not $yCx$ .
6. Transitivity (T): if $xCy$ and $yCz$ then $xCz$ .
7. Negative Transitivity (nT): if not $xCy$ and not $yCz$ then not $xCz$ .

Definitions

• An equivalence relation ($\sim$ ) satisfies RST. It is equivalent to partitioning of the set to the equivalence classes.
• An order relation (or a simple order, or a linear order; $<$ ) satisfies CnRT.
  • A strict partial order satisfies nRT.
  • An open interval $(a,b)$ is the set $\{x:a<x<b\}$ . If it is empty $a$ is the immediate predecessor of $b$ , and $b$ is the immediate successor of $a$ .
  • Two order relations have same order types if there is a bijection between them that preserves the order.
  • The dictionary order relation on $A\times B$ is defined as $a\times b<c\times d$ iff $a<c$ , or $a=c$ and $b<d$ .
  • Other terms defined for orders: a set bounded above/below, upper/lower bounds, the largest/smallest elements, the supremum and infimum, the least upper/greatest lower bound property.

Some facts

• Restriction of an equivalence/order relation is an equivalence/order relation.
• An ordered set has the least upper bound property iff it has the greatest lower bound property.