Properties and Special Relations

Given a relation \( R \) we have that

  • \( R \) is reflexive if for all \( a \) we have that \( a\ R\ a \). That is \( a \) is related to itself. This is typical for the equal relation: we have that \( a = a \). However for the relation "is less then" this does not hold.
  • \( R \) is symmetric if we have that $$ a\ R\ b \Rightarrow b\ R\ a $$ That is if \( a \) is related to \( b \), then \( b \) is related to \( a \). This is again typical for the equal relation. However for the relation "is less than" this does not hold.
  • \( R \) is irreflexive, or anti-reflexive, if for no \( a \) we have that \( a\ R\ a \). A typical example is the relation "less than". No \( a \) is less than itself.
  • \( R \) is anti-symmetrical if $$ a\ R\ b \land b\ R\ a \Rightarrow a = b $$ A typical example is the "less than or equal to". If we have that \( a \leq b \) and \( b \leq a \), then we have that \( a = b \).
  • \( R \) is asymmetrical if and only if \( R \) is both irreflexive and anti-symmetrical.
  • \( R \) is transitive if we have that $$ a\ R\ b \land b\ R\ c \Rightarrow a\ R\ c $$ This holds true for both "less than", "less then or equal to" and "equal to". If \( a \lt b \) and \( b \lt c \), then sure \( a \lt c \).
  • \( R \) is a connex relation (or has the property of connexity) if for all \( a,b \) we have $$ a\ R\ b \lor b\ R\ a $$
  • \( R \) is a semiconnex relation if for all \( a,b \) we have $$ a \neq b \Rightarrow a\ R\ b \lor b\ R\ a $$

Now we can define special kind of relations.

Equivalence Relation

An equivalence relation is a relation that is:

  • Reflexive
  • Symmetric
  • Transitive

Partial Order

A partial order is a relation that is

  • Reflexive
  • Antisymmetric
  • Transitive

A set with a partial order is called a partially ordered set or a poset.

Preorder

A preorder relation is a relation that is

  • Reflexive
  • Transitive

Total Preorder

A total preorder is a relation that is

  • Transitive
  • Connexitive
  • Reflexive

A set that is equipped with a preorder is called a preordered set.

Total Order

A partial order is a relation that is

  • Antisymmetric
  • Transitive
  • Connexitive
Share