Binary Relations

Page Contents

Binary Relation

A #~{binary relation} on a set ~A is a subset _ ~S &subset. ~A # ~A , _ where ~x , ~y &in. ~A are related if _ ( ~x , ~y ) &in. ~S. _ Write _ ~x @R ~y .

 

Equivalence Relation

An #~{equivalence relation} is a binary relation ~ , such that

  1. ~x ~ ~x , _ &forall. ~x &in. ~X. _ (~#{reflexive})
  2. ~x ~ ~y _ => _ ~y ~ ~x. _ (#~{symmetric})
  3. ~x ~ ~y _ and _ ~y ~ ~z _ => _ ~x ~ ~z. _ (#~{transitive})

 

Equivalence Class

If ~ is an equivalence relation on the set ~A, then for any ~x &in. ~A , define the #~{eqivalence class} ( of ~x ) as _ [ ~x ] _ #:= _ \{ ~y &in. ~A | ~y ~ ~x\}.

Note that

  • ~x &in. [ ~x ] _ &forall. ~x &in. ~A
  • ~x ~ ~y _ => _ [ ~x ] = [ ~y ]

Either _ [ ~x ] = [ ~y ] _ ( if ~x ~ ~y ) , _ or _ [ ~x ] &intersect. [ ~y ] = &empty..

So an equivalence relation induces a partition of the set ~A , _ ~A = &union._{~x &in. ~A} [ ~x ] . _ The set of equivalence classes of ~A is denoted _ ~A / ~ _ = _ \{ [ ~x ] | ~x &in. ~A \} .

The map _ ~p #: ~A -> ~A / ~ _ given by _ ~p ( ~x ) = [ ~x ] _ is called the #~{canonical mapping} from ~A to the set of its equivalence classes.

Partial Ordering

An #~{partial ordering} is a binary relation =< , such that

  1. ~x =< ~x _ &forall. ~x &in. ~X
  2. ~x =< ~y _ and _ ~y != ~x _ _ => _ _ ~y not =< ~x , _ _ (#~{antisymmetric})
  3. ~x =< ~y _ and _ ~y =< ~z _ => _ ~x =< ~z

 

 

Total Ordering

A partially ordered set ~X is #~{totally ordered} if , for any ~x, ~y &in. ~X , either _ ~x =< ~y _ or _ ~y =< ~x .

A totally ordered subset of a partially ordered set ~X is called a #~{chain}.

An #~{upper bound} for a chain , \{ ~x_1 =< ~x_2 =< ... \} , is an element ~x &in. ~X such that _ ~x_~i =< ~x , _ &forall. ~x_~i in the chain. (~x is not necessarily in the chain).
[ ~y &in. ~X is a #~{lower bound} _ if _ ~y =< ~x_~i , _ &forall. ~x_~i in the chain.]

An element of a set is #~{maximal} if there is no element _ ~y _ ( ~y != ~x ) _ such that ~x =< ~y .
An element of a set is #~{minimal} if there is no element _ ~y _ ( ~y != ~x ) _ such that ~y =< ~x .

Zorn's Lemma

In a partially ordered set ~X, in which every chain has an upperbound, there exists a maximal element.

Example
~X = &naturals. , _ ~x =< ~y _ if _ ~n~x = ~y , _ some ~n &in. &naturals. _ ( i.e. by definition _ ~x =< ~y _ if ~x divides ~y exactly ).
This is not a total ordering, 3 does not divide 4 for example. _ A chain will be of the form:

  • ~x _ =< _ ~n_1~x _ =< _ ~n_2~n_1~x _ =< ... =< _ ( &prod. ~n_~i ) ~x

In this example, not every chain has an upperbound, and there is no maximal element. However, every chain does have a lower bound, as _ 1 =< ~x , _ &forall. ~x &in. &naturals. _ ( ~x # 1 = ~x ). So the set does have a minimal element, which is in fact 1.