Relation

Binary

Here we are going to define relation formally, first binary relation, then general n-ary relation. A relation in everyday life shows an association of objects of a set with objects of other sets (or the same set) such as John owns a red Mustang, Jim has a green Miata etc. The essence of relation is these associations. A collection of these individual associations is a relation, such as the ownership relation between peoples and automobiles. To represent these individual associations, a set of "related" objects, such as John and a red Mustang, can be used. However, simple sets such as {John, a red Mustang} are not sufficient here. The order of the objects must also be taken into account, because John owns a red Mustang but the red Mustang does not own John, and simple sets do not deal with orders. Thus sets with an order on its members are needed to describe a relation. Here the concept of ordered pair and, more generally, that of ordered n-tuple are going to be defined first. A relation is then defined as a set of ordered pairs or ordered n-tuples.

Definition (ordered pair):

An ordered pair is a set of a pair of objects with an order associated with them. If objects are represented by x and y, then we write an ordered pair as <x, y> or <y, x>. In general <x, y> is different from <y, x>.

Definition (equality of ordered pairs):

Two ordered pairs <a, b> and <c, d> are equal if and only if a = c and b = d. For example, if the ordered pair <a, b> is equal to <1, 2>, then a = 1, and b = 2. <1, 2> is not equal to the ordered pair <2, 1>.

Definition (binary relation):

A binary relation from a set A to a set B is a set of ordered pairs <a, b> where a is an element of A and b is an element of B.

When an ordered pair <a, b> is in a relation R, we write a R b, or <a, b> ∈R. It means that element a is related to element b in relation R. When A = B, we call a relation from A to B a (binary) relation on A.

Definition (Cartesian product):

The set of all ordered pairs <a, b>, where a is an element of A and b is an element of B, is called the Cartesian product of A and B and is denoted by A × B.

Thus a binary relation from A to B is a subset of Cartesian product A × B.

Examples:

If A = {1, 2, 3} and B = {4, 5}, then {<1, 4>, <2, 5>, <3, 5>}, for example, is a binary relation from A to B.

However, {<1, 1>, <1, 4>, <3, 5>} is not a binary relation from A to B because 1 is not in B.

The parent-child relation is a binary relation on the set of people. <John, John Jr.>, for example, is an element of the parent-child relation if John is the father of John Jr.

Definition of n-ary

Here we are going to formally define general n-ary relation using the concept of ordered n-tuple.

Definition (ordered n-tuple): An ordered n-tuple is a set of n objects with an order associated with them. If n objects are represented by x1, x2, ..., xn, then we write the ordered n-tuple as <x1, x2, ..., xn> .

Definition (Cartesian product): Let A1, ..., An be n sets. Then the set of all ordered n-tuples <x1, ..., xn> , where xi ∈Ai for all i, 1 ≤i ≤n , is called the Cartesian product of A1, ..., An, and is denoted by A1 ×... ×An .

Definition (equality of n-tuples): Two ordered n-tuples <x1, ..., xn> and <y1, ..., yn> are equal if and only if xi = yi for all i, 1 ≤i ≤n.

For example the ordered 3-tuple <1, 2, 3> can be equal to only <1, 2, 3> and nothing else. It is not equal to the ordered n-tuple <2, 3, 1> for example.

Definition (n-ary relation): An n-ary relation on sets A1, ..., An is a set of ordered n-tuples <a1, ..., an> where ai is an element of Ai for all i, 1 ≤i ≤n . Thus an n-ary relation on sets A1, ..., An is a subset of Cartesian product A1 ×... ×An .

Example 1: Let A1 be a set of names, A2 a set of addresses, and A3 a set of telephone numbers. Then a set of 3-tuples < name, address, telephone number > such as { < Amy Angels, 35 Mediterranean Ave, 224-1357 >, < Barbara Braves, 221 Atlantic Ave, 301-1734 >, < Charles Cubs, 312 Baltic Ave, 223-9876 > }, is a 3-ary (ternary) relation over A1, A2 and A3.

Example 2: Let A1 be a set of names. Then a set of 1-tuples such as {< Amy >, < Barbara >, < Charles >}, is a 1-ary (unary) relation over A1.

A unary relation represents a property/characteristic, such as tall, rich etc., shared by the members of A1 listed in the relation.

Equality of s

Recursive Definition of

Certain relations can be defined recursively. Note that a relation is a set. Therefore a recursive definition of a relation follows the same format as that of sets. Here only examples are given.

Example 1: Let us define recursively the relation "less than" denoted by R< on the set of natural numbers N.

Note that R< = { <a, b> | a ∈N ⋀ b ∈N ⋀ a < b } = { <0, 1>, <0, 2> , ..., <1, 2>, .... }.

Basis Clause: <0, 1> ∈R< (or 0 R< 1), meaning 0 is less than 1.

Inductive Clause: For all x and y in N, if <x, y> ∈R< , then <x, y + 1> ∈R< , and <x + 1, y + 1> ∈R< .

Extremal Clause: Nothing is in R< , unless it is obtained from the Basis and Inductive Clauses.

Informally one can see that this definition is correct as follows:

First, <0, 1> is the "simplest" element in R< .

Next by arranging the ordered pairs in R< as follows, one can see that the two operations in the Inductive Clause generate them all:

<0, 1>, <0, 2>, <0, 3>, ............................. , <0, n>, .....

<1, 2>, <1, 3>, <1, 4>, ................. , <1, n>, .....

<2, 3>, <2, 4>, <2, 5>, ..... , <2, n>, .....

............................................

............................................

In each row, the first (leftmost) ordered pair gives the "smallest" ordered pair with the first number. For example <2, 3> is the smallest with 2 as the first component. It is obtained from the first ordered pair of the row immediately above it by using <x + 1, y + 1> of the Inductive Clause, apply that to <1, 2> to get <2, 3> , for example.

Within each row, the ordered pairs are obtained from the first one by using <x, y + 1> of the Inductive Clause successively.

Thus all the ordered pairs of R< are generated from <0, 1> by following the Inductive Clause.

Example 2: Let Ra + b = c be the set of triples of natural numbers <a, b, c> which satisfy a + b = c . Then Ra + b = c on the set of natural numbers N can be defined recursively as follows.

Basis Clause: <0, 0, 0> ∈Ra + b = c.

Inductive Clause: For all x, y and z in N, if <x, y, z> ∈Ra + b = c , then <x + 1, y, z + 1> and <x, y + 1, z + 1> ∈Ra + b = c.

Extremal Clause: Nothing is in Ra + b = c unless it is obtained from the Basis and Inductive Clauses.

Digraph

A digraph is short for directed graph, and it is a diagram composed of points called vertices (nodes) and arrows called arcs going from a vertex to a vertex.

For example Figure 1 is a digraph with 3 vertices and 4 arcs.

In this figure the vertices are labeled with numbers 1, 2, and 3.

Mathematically a digraph is defined as follows.

Definition (digraph): A digraph is an ordered pair of sets G = (V, A), where V is a set of vertices and A is a set of ordered pairs (called arcs) of vertices of V.

In the example, G1 , given above, V = { 1, 2, 3 } , and A = { <1, 1>, <1, 2>, <1, 3>, <2, 3> } .

Digraph representation of binary relations

A binary relation on a set can be represented by a digraph.

Let R be a binary relation on a set A, that is R is a subset of A×A. Then the digraph, call it G, representing R can be constructed as follows:

1. The vertices of the digraph G are the elements of A, and

2. <x, y> is an arc of G from vertex x to vertex y if and only if <x, y> is in R.

Example: The less than relation R on the set of integers A = {1, 2, 3, 4} is the set {<1, 2>, <1, 3>, <1, 4>, <2, 3> , <2, 4> , <3, 4> } and it can be represented by the digraph in Figure 2.

Let us now define some of the basic concepts on digraphs.

Definition (loop): An arc from a vertex to itself such as <1, 1>, is called a loop (or self-loop)

Definition (degree of vertex): The in-degree of a vertex is the number of arcs coming to the vertex, and the out-degree is the number of arcs going out of the vertex.

For example, the in-degree of vertex 2 in the digraph G2 shown above is 1, and the out-degree is 2.

Definition (path): A path from a vertex x0 to a vertex xn in a digraph G = (V, A) is a sequence of vertices x0, x1, ....., xn that satisfies the following:

for each i, 0 ≤i ≤ n - 1 , <xi , xi + 1> ∈A , or <xi + 1 , xi> ∈A , that is, between any pair of vertices there is an arc connecting them. x0 is the initial vertex and xn is the terminal vertex of the path.

A path is called a directed path if <xi, xi + 1> ∈A , for every i, 0 ≤i ≤n -1.

If the initial and the terminal vertices of a path are the same, that is, x0 = xn, then the path is called a cycle.

If no arcs appear more than once in a path, the path is called a simple path. A path is called elementary if no vertices appear more than once in it except for the initial and terminal vertices of a cycle. In a simple cycle one vertex appears twice in the sequence: once as the initial vertex and once as the terminal vertex.

Note: There are two different definitions for "simple path". Here we follow the definition of Berge[1], Liu[2], Rosen[3] and others. A "simple path" according to another group (Cormen et al[4], Stanat and McAllister[5] and others) is a path in which no vertices appear more than once.

Definition(connected graph): A digraph is said to be connected if there is a path between every pair of its vertices.

Example: In the digraph G3 given in Figure 3,

1, 2, 5 is a simple and elementary path but not directed,

1, 2, 2, 5 is a simple path but neither directed nor elementary.

1, 2, 4, 5 is a simple elementary directed path,

1, 2, 4, 5, 2, 4, 5 is a directed path but not simple (hence not elementary),

1, 3, 5, 2, 1 is a simple elementary cycle but not directed, and

2, 4, 5, 2 is a simple elementary directed cycle.

This digraph is connected.

Sometimes we need to refer to part of a given digraph. A partial digraph of a digraph is a digraph consisting of arbitrary numbers of vertices and arcs of the given digraph, while a subdigraph is a digraph consisting of an arbitrary number of vertices and all the arcs between them of the given digraph. Formally they are defined as follows: Definition (subdigraph, partial digraph): Let G = (V, A ) be a digraph. Then a digraph ( V', A' ) is a partial digraph of G , if V' ⊆V , and A' ⊆A ∩( V' ×V' ) . It is a subdigraph of G , if V' ⊆V , and A' = A ∩ ( V'×V' )

A partial digraph and a subdigraph of G3 given above are shown in Figure 4.

Properties of Binary

Certain important types of binary relation can be characterized by properties they have. Here we are going to learn some of those properties binary relations may have. The relations we are interested in here are binary relations on a set.

Definition(reflexive relation): A relation R on a set A is called reflexive if and only if < a, a > ∈R for every element a of A.

Example 1: The relation ≤ on the set of integers {1, 2, 3} is {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3>} and it is reflexive because <1, 1>, <2, 2>, <3, 3> are in this relation. As a matter of fact ≤ on any set of numbers is also reflexive. Similarly ≥ and = on any set of numbers are reflexive. However, < (or >) on any set of numbers is not reflexive.

Example 2: The relation ⊆on the set of subsets of {1, 2} is { < ∅, ∅> , < ∅, {1} > , < ∅, {2} > , < ∅, {1, 2} > , < {1} , {1} > , < {1} , {1, 2} > , < {2} , {2} > , < {2} , {1, 2} > , < {1, 2} , {1, 2} > } and it is reflexive. In fact relation ⊆ on any collection of sets is reflexive.

Definition(irreflexive relation): A relation R on a set A is called irreflexive if and only if <a, a> ∉ R for every element a of A.

Example 3: The relation > (or <) on the set of integers {1, 2, 3} is irreflexive. In fact it is irreflexive for any set of numbers.

Example 4: The relation {< 1, 1 >, < 1, 2 >, < 1, 3 >, < 2, 3>, < 3, 3 >} on the set of integers {1, 2, 3} is neither reflexive nor irreflexive.

Definition(symmetric relation): A relation R on a set A is called symmetric if and only if for any a, and b in A, whenever <a, b> ∈R , <b, a> ∈R .

Example 5: The relation = on the set of integers {1, 2, 3} is {<1, 1> , <2, 2> <3, 3> } and it is symmetric. Similarly = on any set of numbers is symmetric. However, < (or >), ≤ (or ≥ on any set of numbers is not symmetric.

Example 6: The relation "being acquainted with" on a set of people is symmetric.

Definition (antisymmetric relation): A relation R on a set A is called antisymmetric if and only if for any a, and b in A, whenever <a, b> ∈R , and <b, a> ∈R , a = b must hold. Equivalently, R is antisymmetric if and only if whenever <a, b> ∈R , and a ≠ b , <b, a> ∉ R . Thus in an antisymmetric relation no pair of elements are related to each other.

Example 7: The relation < (or >) on any set of numbers is antisymmetric. So is the equality relation on any set of numbers.

Definition (transitive relation): A relation R on a set A is called transitive if and only if for any a, b, and c in A, whenever <a, b> ∈R , and <b, c> ∈R , <a, c> ∈R .

Example 8: The relation ≤ on the set of integers {1, 2, 3} is transitive, because for <1, 2> and <2, 3> in ≤, <1, 3> is also in ≤, for <1, 1> and <1, 2> in ≤, <1, 2> is also in ≤, and similarly for the others. As a matter of fact ≤ on any set of numbers is also transitive. Similarly ≥ and = on any set of numbers are transitive.

Figure 5 show the digraph of relations with different properties.

(a) is reflexive, antisymmetric, symmetric and transitive, but not irreflexive.

(b) is neither reflexive nor irreflexive, and it is antisymmetric, symmetric and transitive.

(c) is irreflexive but has none of the other four properties.

(d) is irreflexive, and symmetric, but none of the other three.

(e) is irreflexive, antisymmetric and transitive but neither reflexive nor symmetric.

Operations on Binary s

Composite s

If the elements of a set A are related to those of a set B, and those of B are in turn related to the elements of a set C, then one can expect a relation between A and C. For example, if Tom is my father (parent-child relation) and Sarah is a sister of Tom (sister relation), then Sarah is my aunt (aunt-nephew/niece relation). Composite relations give that kind of relations.

Definition(composite relation): Let R1 be a binary relation from a set A to a set B, R2 a binary relation from B to a set C. Then the composite relation from A to C denoted by R1R2 (also denoted by R1 ∘ R2 is defined as

R1R2 = {<a, c> | a ∈A ⋀c ∈C ⋀∃b [b ∈B ⋀<a, b> ∈R1 ⋀<b, c> ∈R2 ] } .

In English, this means that an element a in A is related to an element c in C if there is an element b in B such that a is related to b by R1 and b is related to c by R2. Thus R1R2 is a relation from A to C via B in a sense. If R1 is a parent-child relation and R2 is a sister relation, then R1R2 is an aunt-nephew/niece relation.

Example 1: Let A = {a1 , a2} , B = {b1 , b2 , b3} , and C = {c1 , c2} . Also let R1 = {<a1 , b1> , <a1 , b2> , <a2 , b3> } , and R2 = {<b1 , c1> , <b2 , c1> , <b2 , c2> , <b3 , c1> } . Then R1R2 = {<a1 , c1> , <a1 , c2> , <a2 , c1> } .

This is illustrated in Figure 6. The dashed lines in the figure of R1R2 indicate the ordered pairs in R1R2, and dotted lines show ordered pairs that produce the dashed lines. (The lines in the left figure are all supposed to be solid lines.)

Example 2: If R is the parent-child relation on a set of people A, then RR, also denoted by R2, is the grandparent-grandchild relation on A.

More examples:

The digraphs of R2 for several simple relations R are shown in Figure 7:

The digraphs of R2

Closure of Binary

In our everyday life we often talk about parent-child relationship. This is a binary relation on the set of people in the world, dead or alive. Also we are often interested in ancestor-descendant relations. Although the latter relation can be obtained from the former, hence it is redundant in that sense, we do use ancestor-descendant relations which give us necessary information more directly. This ancestor-descendant relation relates two people if there is a sequence of parent-child relations from one to the other. It includes the parent-child relation as a subset. The ancestor-descendant relation is an example of the closure of a relation, in particular the transitive closure of the parent-child relation. In general, the closure of a relation is the smallest extension of the relation that has a certain specific property such as the reflexivity, symmetry or transitivity. Formally they are defined as follows:

Definition (reflexive closure): A relation R' is the reflexive closure of a relation R if and only if

(1) R' is reflexive,

(2) R ⊆R', and

(3) for any relation R', if R ⊆R' and R' is reflexive, then R' ⊆R' , that is, R' is the smallest relation that satisfies (1) and (2).

Example: Let R be the less-than relation on the set of integers I, that is R = { < a, b> | a ∈I ⋀b ∈I ⋀a < b }.

Then the reflexive closure r(R) of R is the union of R and the equality relation on I, that is r(R) = {<a, b> | a ∈I ⋀b ∈I ⋀a ≤b }

The digraph of the reflexive closure of a relation is obtained from the digraph of the relation by adding a self-loop at each vertex if one is already not there.

Symmetric and transitive closures can be defined similarly.

Definition (symmetric closure): A relation R' is the symmetric closure of a relation R if and only if

(1) R' is symmetric,

(2) R ⊆R', and

(3) for any relation R', if R ⊆R', and R' is symmetric, then R' ⊆R' , that is, R' is the smallest relation that satisfies (1) and (2).

Example: Let R be the less-than relation on the set of integers I. Then the symmetric closure of R, denoted by s(R) is s(R) = { <a, b> | a ∈I ⋀ b ∈I ⋀[ a < b ∨ a > b ] } that is { <a, b> | a ∈I ⋀b ∈I ⋀a ≠b }

The digraph of the symmetric closure of a relation is obtained from the digraph of the relation by adding for each arc the arc in the reverse direction if one is already not there.

Definition (transitive closure): A relation R' is the transitive closure of a relation R if and only if

(1) R' is transitive,

(2) R ⊆R', and

(3) for any relation R', if R ⊆R' and R' is transitive, then R' ⊆R' , that is, R' is the smallest relation that satisfies (1) and (2).

Examples: The transitive closure of a parent-child relation is the ancestor-descendant relation as mentioned above, and that of the less-than relation on I is the less-than relation itself.

The digraph of the transitive closure of a relation is obtained from the digraph of the relation by adding for each directed path the arc that shunts the path if one is already not there.

Two more examples of closures are given in Figure 8 in terms of digraphs.

The arrows with two heads represent arrows going in opposite directions.

Properties of Closure

The closures

The closures have the following properties. They are stated here as theorems without proof.

Theorem: Let E denote the equality relation, and Rc the inverse relation of binary relation R, all on a set A, where Rc = {< a, b > | < b, a > ∈R}. Then

1. r(R) = R ∪ E

2. s(R) = R ∪Rc

3. t(R) = i=1∞ size 12{ union rSub { size 8{i=1} } rSup { size 8{ infinity } } } {}Ri = i=1n size 12{ union rSub { size 8{i=1} } rSup { size 8{n} } } {} Ri, if |A| = n.

4. R is reflexive if and only if r(R) = R.

5. R is symmetric if and only if s(R) = R.

6. R is transitive if and only if t(R) = R.

Equivalence

On the face of most clocks, hours are represented by integers between 1 and 12. However, since a day has 24 hours after 12 hours, a clock goes back to hour 1, and starts all over again from there. Thus each pair of hours such as 1 and 13, 2 and 14, etc. share one number 1, 2, ...etc., respectively. The same applies when we are interested in more than 24 hours. 25th hour is 1, so are 37th, 49th etc. What we are doing here essentially is that we consider the numbers in each group such as 1, 13, 25, ..., equivalent in the sense that they all are represented by one number (they are congruent modulo 12). Being representable by one number such as we see on clocks is a binary relation on the set of natural numbers and it is an example of equivalence relation we are going to study here.

The concept of equivalence relation is characterized by three properties as follows:

Definition (equivalence relation): A binary relation R on a set A is an equivalence relation if and only if

(1) R is reflexive

(2) R is symmetric, and

(3) R is transitive.

Example 1: The equality relation (=) on a set of numbers such as {1, 2, 3} is an equivalence relation.

Example 2: The congruent modulo m relation on the set of integers i.e. {<a, b>| a ≡ b (mod m)}, where m is a positive integer greater than 1, is an equivalence relation.

Note that the equivalence relation on hours on a clock is the congruent mod 12, and that when m = 2, i.e. the congruent mod 2, all even numbers are equivalent and all odd numbers are equivalent. Thus the set of integers are divided into two subsets: evens and odds.

Example 3: Taking this discrete structures course together this semester is another equivalence relation.

Equivalence relations can also be represented by a digraph since they are a binary relation on a set. For example the digraph of the equivalence relation congruent mod 3 on {0, 1, 2, 3, 4, 5 , 6} is as shown in Figure 9. It consists of three connected components.

The set of even numbers and that of odd numbers in the equivalence relation of congruent mod 2, and the set of integers equivalent to a number between 1 and 12 in the equivalence relation on hours in the clock example are called an equivalence class. Formally it is defined as follows:

Definition (equivalence class): For an equivalence relation R on a set A, the set of the elements of A that are related to an element, say a, of A is called the equivalence class of element a and it is denoted by [a].

Example 4: For the equivalence relation of hours on a clock, equivalence classes are

[1] = {1, 13, 25, ... } = {1+ 12n: n ∈N} ,

[2] = {2, 14, 26, ... } = {2+ 12n: n ∈N} ,

........,

where N is the set of natural numbers. There are altogether twelve of them.

For an equivalence relation R on a set A, every element of A is in an equivalence class. For if an element, say b, does not belong to the equivalence class of any other element in A, then the set consisting of the element b itself is an equivalence class. Thus the set A is in a sense covered by the equivalence classes. Another property of equivalence class is that equivalence classes of two elements of a set A are either disjoint or identical, that is either [a] = [b] or [a] ∩ [b] = ∅ for arbitrary elements a and b of A. Thus the set A is partitioned into equivalence classes by an equivalence relation on A. This is formally stated as a theorem below after the definition of partition.

Definition (partition): Let A be a set and let A1, A2, ..., An be subsets of A. Then {A1, A2, ..., An} is a partition of A, if and only if

(1) i=1n size 12{ union rSub { size 8{i=1} } rSup { size 8{n} } } {}Ai = A, and

(2) Ai ∩Aj = ∅, if Ai ≠ Aj , 1 ≤ i, j ≤ n .

(3) Example 5: Let A = {1, 2, 3, 4, 5}, A1 = {1, 5}, A2 = {3}, and A3 = {2, 4}. Then {A1, A2, A3} is a partition of A. However, B1 = {1, 2, 5}, B2 = {2, 3}, and B3 = {4} do not form a partition for A because B1 ∩B2 ≠∅, though B1 ≠B2.

Theorem 1: The set of equivalence classes of an equivalence relation on a set A is a partition of A.

Conversely, a partition of a set A determines an equivalence relation on A.

Theorem 2: Let {A1, ..., An} be a partition of a set A. Define a binary relation R on A as follows: <a, b> ∈R if and only if a ∈Ai and b ∈Ai for some i, 1 ≤i ≤n . Then R is an equivalence relation.

Theorem 3: Let R1 and R2 be equivalence relations. Then R1 ∩R2 is an equivalence relation, but R1 ∪R2 is not necessarily an equivalence relation.

Order

Shoppers in a grocery store are served at a cashier on the first-come-first-served basis. When there are many people at cashiers, lines are formed. People in these lines are ordered for service: Those at the head of a line are served sooner than those at the end. Cars waiting for the signal to change at an intersection are also ordered similarly. Natural numbers can also be ordered in the increasing order of their magnitude. Those are just a few examples of order we encounter in our daily lives. The order relations we are going to study here are an abstraction of those relations. The properties common to orders we see in our daily lives have been extracted and are used to characterize the concepts of order. Here we are going to learn three types of order: partial order, total order, and quasi order.

Definition(partial order): A binary relation R on a set A is a partial order if and only if it is

(1) reflexive,

(2) antisymmetric, and

(3) transitive.

The ordered pair <A, R> is called a poset (partially ordered set) when R is a partial order.

Example 1: The less-than-or-equal-to relation on the set of integers I is a partial order, and the set I with this relation is a poset.

Example 2: The subset relation on the power set of a set, say {1, 2}, is also a partial order, and the set {1, 2} with the subset relation is a poset.

Definition(total order): A binary relation R on a set A is a total order if and only if it is

(1) a partial order, and

(2) for any pair of elements a and b of A, < a, b > ∈R or < b, a > ∈R.

That is, every element is related with every element one way or the other. A total order is also called a linear order.

Example 3: The less-than-or-equal-to relation on the set of integers I is a total order.

The strictly-less-than and proper-subset relations are not partial order because they are not reflexive. They are examples of some relation called quasi order.

Definition(quasi order): A binary relation R on a set A is a quasi order if and only if it is

(1) irreflexive, and

(2) transitive.

A quasi order is necessarily antisymmetric as one can easily verify.

Caution Like many other definitions there is another fairly widely used definition of quasi order in the literature. According to that definition a quasi order is a relation that is reflexive and transitive. That is something quite different from "quasi order" we have defined here.

Example 4: The less-than relation on the set of integers I is a quasi order.

Example 5: The proper subset relation on the power set of a set, say {1, 2}, is also a quasi order.

The concept of least/greatest number in a set of integers can be generalized for a general poset. We start with the concepts of minimal/maximal elements.

Definition(minimal/maximal element): Let < A, ≾> be a poset, where ≾ represents an arbitrary partial order. Then an element b ∈A is a minimal element of A if there is no element a ∈A that satisfies a ≾b. Similarly an element b ∈A is a maximal element of A if there is no element a ∈A that satisfies b ≾a.

Example 6: The set of {{1}, {2}, {1, 2}} with ⊆ has two minimal elements {1} and {2}. Note that {1}, and {2} are not related to each other in ⊆. Hence we can not say which is "smaller than" which, that is, they are not comparable.

Definition(least/greatest element): Let < A, ≾> be a poset. Then an element b∈A is the least element of A if for every element a ∈A, b ≾a.

Note that the least element of a poset is unique if one exists because of the antisymmetry of ≾.

Example 7: The poset of the set of natural numbers with the less-than-or-equal-to relation has the least element 0.

Example 8: The poset of the powerset of {1, 2} with ⊆ has the least element ∅.

Definition(well order): A total order R on a set A is a well order if every non-empty subset of A has the least element.

Example 9: The poset of the set of natural numbers with the less-than-or-equal-to relation is a well order, because every set of natural numbers has the least element.

The poset of the set of positive real numbers with the less-than-or-equal-to relation is not a well order, because the set itself does not have any least element (0 is not in the set).

A digraph of a binary relation on a set can be simplified if the relation is a partial order. Hasse diagrams defined as follows are such graphs.

Definition(Hasse diagram): A Hasse diagram is a graph for a poset which does not have loops and arcs implied by the transitivity. Further, it is drawn so that all arcs point upward eliminating arrowheads.

To obtain the Hassse diagram of a poset, first remove the loops, then remove arcs < a, b > if and only if there is an element c that < a, c > and < c, b > exist in the given relation.

Example 10: For the relation {< a, a >, < a, b >, < a, c >, < b, b >, < b, c >, < c, c >} on set {a, b,c}, the Hasse diagram has the arcs {< a, b >, < b, c >} as shown in Figure 10.

Topological Sorting

The elements in a finite poset can be ordered linearly in a number of ways while preserving the partial order. For example {∅, {1}, {2}, {1, 2}} with the partial order ⊆, can be ordered linearly as ∅, {1}, {2}, {1, 2}, or ∅, {2}, {1}, {1, 2}. In these orders a set appears before (to the left of) another set if it is a subset of the other. In real life, tasks for manufacturing goods in general can be partially ordered based on the prerequisite relation, that is certain tasks must be completed before certain other tasks can be started. For example the arms of a chair must be carved before the chair is assembled. Scheduling those tasks is essentially the same as arranging them with a linear order (ignoring here some possible concurrent processing for simplicity's sake).

The topological sorting is a procedure to find from a partial order on a finite set a linear order that does not violate the partial order. It is based on the fact that a finite poset has at least one minimal element. The basic idea of the topological sorting is to first remove a minimal element from the given poset, and then repeat that for the resulting set until no more elements are left. The order of removal of the minimal elements gives a linear order. The following algorithm formally describes the topological sorting.

Algorithm Topological Sort

Input: A finite poset <A, R>.

Output: A sequence of the elements of A preserving the order R.

integer i;

i := 1;

while ( A ≠∅) {

pick a minimal element b from A;

A := A - {b};

i := i + 1;

output b

} Example: Let A = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} with the partial order ⊆. This given A has three minimal elements {1}, {2}, and {3}.

Select {2} and remove it from A. Let A denote the resultant set i.e. A := A - {2}. The new A has two minimal elements {1}, and {3}.

Select {1} and remove it from A. Denote by A the resultant set, that is A = {{3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

This new A has two minimal elements {3} and {1, 2}.

Select {1, 2} and remove it from A.

Proceeding in like manner, we can obtain the following linear order: {{2}, {1}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}.