relations

An ordering is any relation R that satisfies:

(a) Reflexive property: (a,a) ε R

(b) Transitive property : (a,b) ε R and (b,c) ε R implies (a,c) ε R

(c) Anti-symmetric: (a,b) ε R and (b,a) ε R iff a = b

A set S on which such an ordering exists, is in general a partially ordered set (as against a bare set, on which no order is defined)

If (a,b) ε R or (b,a) ε R we say that a and b are comparable

A set S is said to be totally ordered if given a,b ε S either (a,b)ε R or (b,a) ε R. In other words any two elements of S are comparable.

Familiar examples of ordering are:

(1) 'greater than or equal to' : this induces a total ordering if S consists of real numbers

(2) ' is divisible by ': S = {1,3,4,6,8,9}

The ordered pairs will be {(1,1) (3,1), (4,1), (6,1), (8,1), (9,1), (3,3), (6,3), (9,3), (8,4)}

You can easily see that 'is divisible by' is an ordering and the set S is partially ordered by this relation

(3)' is a subset of ' is also an ordering

Anti-Symmetric:

You must first understand symmetry:

If you consider the set of lines L, then consider the relation R defined by R ={(l₁,l₂): l, l₂ ε L and l_1 \left| \right| l_2

Obviously if (l_1, l_2) \in R then we must have (l_2, l_1) \in R

It is not necessary that if (l_1, l_2) \in R and (l_2, l_1) \in R then l₁ and l₂ are identical.

But in anti-symmetric, (a, b) \in R and (b,a) \in R \Rightarrow a=b

e.g. "is a subset of" . As you know A \subseteq B \ \text{and} \ B\subseteq A \Rightarrow A = B. This is hence an anti-symmetric relation ( and its an example of an ordering as mentioned before)