Relations

A relation R on A is defined to be R A x A

Partial order:

A partial order is a binary relation R over a set P which is reflexive, antisymmetric, and transitive

Examples:

• The set of natural numbers equipped with the lesser than or equal to relation, or with the divisibility relation is a partial order. Under divisibility there is a lower (lcm) and upperbound (gcd)

• If (A, <_A) and (B,<_B) are partially ordered sets, then the product order is

  (a₁ <_A a₂) ^ (b₁ <_A b₂) <-> (a₁, b₁) < (a₂, b₂)

  ie Its just the Cartesian (normal multiplication) product of the two orders.

You can prove AxB is a partial order as follows:

• reflexive as (a,b) < (a,b)

• A and B are antisymmetric, so a₁< a₂ and a₂< a₁ so a₁=a₂ (same with b's) so

  (a₁,b₁)=(a₂,b₂)

• a1<_Aa2<_Aa3 so a1<_Aa3 because <_A is transitive, same with b's

  (a1,b1)

Divisibility is a partial order:

• reflexive a|a

• antisymmetric a|b => b|a

• transitive a|b and b|c => a|c

To prove something is a least upper bound, assume there is a lower upper bound, then it divides the elements and either divides the LUB or is the LUB: contradiction. Simliar argument for greatest lower bound.

is a partial order:

• reflexive AA

• anti symmetric A B B A=> B=A

• transitive A B B C => A C

Given A,B X the greatest lower bound is A B and the lowest upper bound is A n B.

This is proved by letting C be g|b, C X and by entailment show either CAB or A n BC

The greatest lower bound of AxB = ( glb(a1,a2) ,glb(b1,b2) )

Subsets including of 0 dont have an upper bound, as 0 doesn't divide natural numbers (when using the divide operator as the PO).

N has no least upper bound (as there is no number bigger than the largest in N), but a greatest lower bound. Its subsets have both.

Lattices:

A lattice is a partially ordered set where every pair of elements has both a least upper bound and a greatest lower bound.

Well founded relation

• A well founded relation on a set A is a relation A x A such that there are no infinitely descending chains.

• Any non-empty subset S of a well-founded (relation) set A has a minimal element: Pick an element a0, if it is minimal then stop. Otherwise pick a1 a0. If minimal stop, if not then pick a2 a1. This can't continue for ever as is well founded, therefore there must be a minimal element.

• If two relations <_A on A and <_B on B are well founded show that the relation and product relation on AxB are both well founded:

  Consider projection of product order into A -> find minimum.

  Consider proection into B-> find minimum.

  Show minimal

  Observe <_L <_P

Total order

A total order on a set X is any binary relation on X that is antisymmetric, transitive, and total. This means that if we denote one such relation by = then the following statements hold for all a, b and c in X:

• if a = b and b = a then a = b (antisymmetry)

• if a = b and b = c then a = c (transitivity)

• a = b or b = a (totality)

A relation's property of "totality" can be described this way: that any pair of elements in the set are mutually comparable under the relation.

Notice that the totality condition implies reflexivity, that is a = a. Thus a total order is also a partial order, that is, a binary relation which is reflexive, antisymmetric and transitive.

• The lexicographical order on the product of a set of totally ordered sets indexed by an ordinal (indexing number, eg first, second etc.) is itself a total order.

• For example, any set of words ordered alphabetically is a total order, viewed as a subset of a product of a countable number of copies of a set formed by adding the space symbol to the alphabet (and defining a space to be less than any letter).

• A totally ordered set is said to be complete if every subset that has an upper bound, has a least upper bound.

Equivalence relation

An equivalence relation on a set X is a binary relation on X that is reflexive, symmetric, and transitive. That is, if the relation is denoted by the symbol "~", it holds for all a, b, and c in X that

1. (Reflexivity) a ~ a

2. (Symmetry) if a ~ b then b ~ a

3. (Transitivity) if a ~ b and b ~ c then a ~ c

• If two equivalence relations over the set X are given, then their intersection (viewed as subsets of X×X) is also an equivalence relation.