Chapter - 4, Relations

Section - 4.4 - Ordering Relations


Summary

  • Antisymmetric Relation:
    • Suppose is a relation on a set . Then is said to be antisymmetric if .
    • For example:
      1. , where .
      2. , where .
    • It can be seen from the above examples, that is atleast as . Thus antisymmetric relation gives a sense of ordering.
  • Partial Order: Consider a relation defined on set . will be called partial order on , if is reflexive, transitive and antisymmetric.
  • Total Order: Consider a relation defined on set . will be called total order, if is partial order and . As it can be seen from the definition, every two elements of the set are in . Also, since is antisymmetric, everyone of these elements/objects have a sense of ordering with respect to every other element/object.
  • If is a partial order on a set . Suppose :
    • Smallest and Minimal element(s):
      • Suppose . If , then is called -smallest element of . Also, if is called an -minimal element of .
      • If has a smallest element then this element is unique.
      • If is the smallest element of B, then is also a minimal element of , and it is the only minimal element.
      • If is a total order and is a minimal element of , then is the smallest element of .
    • Largest and Maximal element(s):
      • If , then is called -largest element of . Also, if is called an -maximal element of .
      • Other properties of largest and maximal are similar to smallest and minimal as above.
  • Lower Bound and Upper Bound:
    • Suppose is a partial order on , , and . Then is called a lower bound for if . Similarly, it is an upper bound for if .
    • Thus there can be multiple lower bounds or upper bounds for a set.
    • Note that lower/upper bound need not be part of the set . However, smallest/largest element of must be the part of set .
  • Least Upper Bound and Greatest Lower Bound:
    Suppose is a partial order on and . Let be the set of all upper bounds for , and let be the set of all lower bounds. If has a smallest element, then this smallest element is called the least upper bound of . If has a largest element, then this largest element is called the greatest lower bound of . The phrases least upper bound and greatest lower bound are sometimes abbreviated l.u.b. and g.l.b.
  • Suppose is a set, , and . Then the least upper bound of (in the subset partial order) is and the greatest lower bound of is .

Soln1

(a)

Reflexive: True Transitive: True Antisymmetric: True

Thus it is partial order. It is not total order since .

(b)

Reflexive: True Transitive: True Antisymmetric: False, Because but .

Thus it is not partial order.

(c)

Reflexive: True Transitive: True Antisymmetric: True

Thus it is partial order. It is not total order because .


Soln2

(a)

Reflexive: True Transitive: True Antisymmetric: True

Thus it is partial order. It is also total order because every two english words, say and , then either or .

(b)

Reflexive: True Transitive: True Antisymmetric: False. For example but .

(c)

Reflexive: True Transitive: True Antisymmetric: False. Suppose and are two different countries with same population. Then but .


Soln3

(a)

.

Minimal elements = .
Smallest element =
Greatest Lower Bound = 2.

Maximal elements = .
Largest = N.A.
Least Upper Bound = N.A.

(b)

.

Minimal elements = .
Smallest element =
Greatest Lower Bound = 1.

Maximal elements = N.A.
Largest = N.A.
Least Upper Bound = 2

(c)

Minimal elements = .
Smallest element =
Greatest Lower Bound = .

Maximal elements =
Largest = N.A.
Least Upper Bound = N.A.


Soln4

()Suppose is symmetric and antisymmetric. Suppose in . Since is symmetric . Since and is antisymmetric, it follows that . Thus . Since is arbitrary, it follows that .

()Suppose . Suppose , thus . Since , it follows . Thus is symmetric. Now to prove antisymmetric, suppose . Since , it follows . since , it follows that . Thus is antisymmetric.


Soln5

Suppose is a partial order on and .

Reflexive:

Suppose is arbitrary element of . Since , . Since is reflexive, if follows that . Since , it follows . Thus if , then . Since is arbitrary, we can conclude that is reflexive.

Transitive:

Suppose are arbitrary elements of such that . Thus . Since is transitive, it follows . Since , thus . Thus if , then . Since , are arbitrary, we can conclude that is transitive.

Antisymmetric:

Suppose are arbitrary elements of such that . Thus . Since is antisymmetric, it follows . Thus if , then . Since , is arbitrary, we can conclude that is antisymmetric.

Since is reflexive, transitive, antisymmetric, it follows that is partial order on .


Soln6

(a) Suppose and are partial orders on .

Suppose . Since is reflexive, . Similarly since is reflexive, . Thus . Since is arbitrary, is reflexive.

Suppose are arbitrary elements of such that . It follows that . Since is transitive, it follows . Similarly since and is transitive, it follows that . Thus we have . Since are arbitrary, it follows that is transitive.

Suppose are arbitrary elements of such that . Thus . Since is antisymmetric, it follows . Thus if , then . Since , is arbitrary, we can conclude that is antisymmetric.

Thus is partial order on .

(b) False. Counter example:

.

.

As we can see and are partial order. But is not partial order because it is not transitive.


Soln7

Suppose is partial order on and is partial order on .

(a)

Reflexive:

Suppose . Two possible cases:

  • Case 1:
    Since is partial order, . Or we can also say .

  • Case 2:
    Since is partial order, . Or we can also say .

Thus from all cases, is reflexive on .

Transitive:

Suppose are arbitrary elements of such that . We have following possible cases:

  • Case 1: :
    Since is transitive, it follows . We can also say .

  • Case 2: :
    Since is transitive, it follows . We can also say .

  • Case 3: :
  • Case 4: :
    Both cases(3 & 4) are not possible, since both of them require . But , so these cases do not exist.

Thus from all cases, is transitive on .

Antisymmetric:

Suppose are arbitrary elements of such that . we have following possible cases:

  • Case 1: :
    Since is antisymmetric, it follows .

  • Case 2: :
    Since is antisymmetric, it follows .

  • Case 3: :
  • Case 4: :
    Both cases(3 & 4) are not possible, since both of them require . But , so these cases do not exist.

Thus from both cases, is antisymmetric on .

As we can see now, is reflexive, transitive and antisymmetric, it follows that is partial order on .

(b)

Reflexive:

Suppose . Two possible cases:

  • Case 1:
    Since is partial order, . Or we can also say .

  • Case 2:
    Since is partial order, . Or we can also say .

Thus from all cases, is reflexive on .

Transitive:

Suppose are arbitrary elements of such that . We have following possible cases:

  • Case 1: :
    Since is transitive(proved in part (a)), it follows . We can also say .

  • Case 2: :
    Thus . This is not possible since .

  • Case 3: :
    Here two further cases are possible:
    • Case a: :
      Thus . Clearly . Or we can also say .

    • Case b: :
      Thus . Clearly . This is not possible since .

  • Case 4: :
    Here two further cases are possible:
    • Case a: :
      Thus . This is not possible since .

    • Case b: :
      Thus . Clearly . Or we can also say .

Thus from all cases, is transitive on .

Antisymmetric:

Suppose are arbitrary elements of such that . we have following possible cases:

  • Case 1: :
    Since we know from last part that x = y $$.

  • Case 2: :
    Thus . This is not possible since .

  • Case 3: :
    Here two further cases are possible:
    • Case a: :
      Thus . This is not possible since .

    • Case b: :
      Thus . This is not possible since .

  • Case 4: :
    Here two further cases are possible:
    • Case a: :
      Thus . This is not possible since .

    • Case b: :
      Thus . This is not possible since .

Thus from all cases, is antisymmetric on .

Thus from is partial order.

(c)

Suppose and are total order on and respectively.

is not total order on . Counter example: Suppose , then but , and also because .

Now suppose , then we have following possible cases:

  • Case 1: :
    Since is total order on , or . Thus we can also say or .

  • Case 2: :
    Since is total order on , or . Thus we can also say or .

  • Case 3: :
    Thus . Thus we can also say or .

  • Case 4: :
    Thus . Thus we can also say or .

Thus from all the cases, we can conclude that is total order.


Soln8

Reflexive: Suppose . Since is reflexive, it follows . Similarly since is reflexive, it follows that . Thus . Since is arbitrary, it follows that is reflexive.

Transitive:

Suppose such that . Since , it follows . Since is transitive, . Similarly, since is transitive, and , follows that . Now since , it follows that . Since is arbitrary, we can conclude that is transitive.

Antisymmetric:

Suppose such that . Thus . Since is antisymmetric, it follows that . Similarly since and is transitive, it follows that . Thus . Since are arbitrary, it follows that is partial order.

Thus is partial order.

Total Order:

is not total order even if and are full order. Suppose and . Then neither and nor is true.


Soln9

Note: Proof of transitivity can be done in a shorter way as suggested in the comment below.

Reflexive: Suppose . Since is reflexive, it follows . Similarly since is reflexive, it follows that . Thus . Since is arbitrary, it follows that is reflexive.

Transitive:

Suppose such that . Since , it follows . Since is transitive, . Now we have following cases:

Case 1: Since , it follows . Similarly since , it follows . Now since and and , it follows .

Case 2: Since , it follows . Since , it follows .

Case 3: Since , it follows . Since , it follows .

Case 4: Since , it may be either , or . Suppose , then since , it follows . Thus and is antisymmetric, it follows . But we have . Thus our assumption is not correct. Or . Now since , it follows .

Thus from all cases is transitive.

Antisymmetric:

Suppose such that . Since , it follows . Similarly since , it follows . Since and is antisymmetric, it follows . Since and , it follows . Also, since and , it follows . Since is antisymmetric, it follows . Thus , or we can say . Thus is antisymmetric.

Thus is partial order.

Total Order:

Suppose and are total orders.

Now suppose are in . Thus and are in and and are in . Since is total order on and is total order on . Thus we have and . Thus we have following cases:

  • Case 1: .
    • Case a:
      Thus . We can also say .
    • Case b:
      Thus . We can also say .
  • Case 2: .
    • Case a:
      Since , if follows . Thus . We can also say .

    • Case b:
      Thus . We can also say .

  • Case 3: .
    • Case a:
      Since , if follows . Thus . We can also say .

    • Case b:
      Thus . We can also say .

  • Case 4: .
    • Case a:
      Thus . We can also say .

    • Case b:
      Thus . We can also say .

Thus from all the cases, . Since are arbitrary, we can conclude that is total order.


Soln10

Suppose are arbitrary elements of .

() Suppose . Suppose . Since , it follows . Since and and is partial order, it follows . Thus . Since is arbitrary, it follows that .

()Suppose . Since is partial order, xRx. Thus . Since , it follows , thus .

Since and are arbitrary elements, we can conclude that .


Soln11

Minimal elements: . Smallest element: N.A.


Soln12

We shall prove this by contradiction. Suppose has a minimal element, say . Thus . Also since is minimal, it follows . Since , suppose is an element in . Then contains all elements of set . Now consider the set . Clearly . Also all the elements that exist in are greater than , thus . Also, since , . Thus . But it contradicts our assumption that . Thus we can conclude that there does not exist any minimal element in .


Soln13

Suppose is partial order on .

Reflexive:

Suppose . Since is partial order, . Thus . Since is arbitrary, we can conclude that is reflexive.

Transitive:

Suppose are arbitrary elements of such that . It follows that . Since is transitive, it follows that . Thus . Since are arbitrary, we can conclude the is transitive.

Antisymmetric:

Suppose are arbitrary elements of such that . It follows that . Since is antisymmetric, it follows that . Since are arbitrary, we can conclude the is antisymmetric.

Thus is reflexive, transitive and antisymmetric, we can conclude that is partial order.

Total Order:

Suppose is total order. Suppose are arbitrary elements of . Since is total order we have two possible cases:

  • Case 1: .
    Thus . We can also say that .

  • Case 2: .
    Thus . We can also say that .

Since are arbitrary, we can conclude that is total order.


Soln14

(a)

Suppose is the -largest element of , iff
iff
iff
iff
iff
is the -smallest element of .

(b)

Suppose is the -maximal element of . iff
. iff
. iff
is the -minimal element of .


Soln15

(a)

Suppose is the -smallest element of . Suppose is arbitrary element in . Since is -smallest element in , it follows that . Since , it follows . Since is arbitrary, it follows . Thus is also the -smallest element of .

(b)

Suppose is an -minimal element of . Suppose is arbitrary element in such that . Then . Since , it follows that such element must also not exist in . Thus . It follows that is the -minimal element of .


Soln16

Suppose is the -largest element of . Suppose is not a maximal element of . Thus there exist an element such that . But it contradicts with the given that is the largest element of . Thus assumption is not a maximal element is not correct. Hence, is a maximal element of .

Suppose is also a maximal element of . Thus , or . Also since is largest element of , . Thus . Thus we can conclude that is the only maximal element.


Soln17 (Using the hint from book as not able to do it myself).

False. Counter example:

Suppose , and let .

This can be proved directly using excercise - 8 that it is partial order.

Now, suppose .

Thus, contains elements like …. , , , , , , , , , ,…..

Thus it can be noticed here, how might this example is developed. got created in such a way that looks like it will contain two minimals but because other minimal moves towards infinity, we only get one defined minimal. There is no element such that is defined, so is the only minimal.

Now since elements like …. are not present in (which can be seen that it is because of the particular choice of B), is not the smallest element as an element is smallest iff . Thus in our example, this is not the case that for all values, say , of , .


Soln18

Note: There are errors in this solution. Refer to the below comment for correct solution.

(a)

()Suppose is upper bound on . Suppose is arbitrary element of . Since it is given that , if suppose for , we have . Since , it follows . But since is upper bound for and , it follows . Since is partial order on and , it follows . Since is arbitrary element of , it follows that is upper bound for .

()Suppose is upper bound on . Suppose is arbitrary element of . Since it is given that , if suppose for , we have . Since , it follows . But since is upper bound for and , it follows . Since is partial order on and , it follows . Since is arbitrary element of , it follows that is upper bound for .

(b)

We will prove this by contra-positive. Suppose is a maximal element of . Similarly, suppose is a maximal element of .

Since it is given that , suppose for the value , we have . Similarly, since it is given that , suppose for the value , we have . Now since and , it follows that . Similarly, since and , it follows that . Thus and since is partial order, it follows that .

Since is a maximal element of , it follows . Also since , it follows, . Since , it follows . But is a maximal element of , thus .

Since is a maximal element of , it follows . Also since , it follows, . Since , it follows . But is a maximal element of , thus .

Thus . Thus and are not disjoint. Thus by contra-positive, if and are disjoint, then there is no element and such that . And if there is no such element, then and does not have a maximal element.

Note: I am not confident of this proof. As from the givens it can be easily seen that and are not disjoint. Or the other cases might be that and are empty.


Soln19

(a) The proof is not correct. The problem with the proof is conclusion in both cases are wrong i.e.:

  • Case 1: . Since was arbitrary, we can conclude that , so is the smallest element of .

Here the conclusion is wrong, because is not true for all values of . it does not consider the other case, . Similarly, in the other case , we can not conclude that is true for all because it does not consider the case when .

(b) Theorem is not correct. Counter example:

. Clearly and is partial order on . Note that but is niether -largest element of nor the -smallest element of .


Soln20

(a) Suppose is smallest element of . Thus . Thus the set of all lower bound elements of is Since , , and clearly in the set , is the greatest element. Thus is the greatest lower bound element of .

(b) Suppose is largest element of . Thus . Thus the set of all upper bound elements of is Since , , and clearly in the set , is the least element. Thus is the least upper bound element of .


Soln21

(a) Suppose is the set of upper bound elements of . Suppose and suppose such that . Since , it follows that . Thus for any arbitrary element , . Since , and is partial order, it follows . Since is arbitrary, it follows . Thus is upper bound of , or .

(b) Suppose is an arbitrary element of . Suppose . Since is the set of upper bound of , it follows that . Since is arbitrary, it follows . Since (because ) and , it follows is a lower bound of . Since is arbitrary, it follows every element of is lower bound element of .

(c) Suppose is the greatest lower bound of . Suppose is an arbitrary element of . Then from part (b), is lower bound for . Since is greatest lower bound of , it follows . Since is arbitrary, it follows that . Thus is upper bound of . Thus . Since is lower bound of , it follows . Thus is the lowest element in . Since is the set of all upper bounds of , it follows that is least upper bound of .


Soln22

Suppose . Since , is also the upper bound of . But since is the least upper bound of , it must be smaller than all other upper bounds of . Thus .


Soln23

  • Proof of is l.u.b. of :

Suppose . Suppose . Since , it follows that . Since is arbitrary, it follows . Since is arbitrary, it follows that , or is the largest subset element of . Thus all the upper bounds of must be larger than . Thus is the smallest element in all the uppper bounds of . Thus is the least upper bound of .

  • Proof of is g.l.b. of :

Suppose . Suppose . Then . Thus if , then . Since is arbitrary . Since is arbitrary, it follows that . Thus is the smallest element(wrt subset relation) in . Thus all the lower bounds of must be lesser than . Thus is the largest element in all the lower bounds of . Thus is the greatest lower bound of .