55
8/22/2019 Math 103 - 10 Relations http://slidepdf.com/reader/full/math-103-10-relations 1/55 7/1/2013 Relations 1 Chapter 10 Relations

Math 103 - 10 Relations

Embed Size (px)

Citation preview

Page 1: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 1/55

7/1/2013 Relations 1

Chapter 10

Relations

Page 2: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 2/55

7/1/2013 Relations 2

Section 10.1

Relations on Sets

Page 3: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 3/55

7/1/2013 Relations 3

Relations on a Set

A relation from a set A to a set B is a subsetof  A × B.

A relation on a set A is a relation from A to

 A, i.e., a subset of  A × A.

Page 4: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 4/55

7/1/2013 Relations 4

Examples: Relations on a Set

Define the relation on the integers asa b if a divides b.

Define the relation < on the real numbers as

 x < y if  x is less than y.

Define the relation ≤ on a Boolean algebra

as a ≤ b if a ⋅ b = a.

Page 5: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 5/55

7/1/2013 Relations 5

Inverse Relations

Let R be a relation from A to B.

The inverse relation, denoted R–1, is defined

by (a, b) ∈ R–1 if and only if (b, a) ∈ R.

Page 6: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 6/55

7/1/2013 Relations 6

Examples: Inverse Relations

The inverse of the “divides” relation onthe integers is the “is a multiple of” relation.

The inverse of the “less-than” relation < on

the real numbers is the “greater-than”relation >.

The inverse of the relation ≤ on a Boolean

algebra (defined by a ⋅ b = a) is the relation≥ (defined by a + b = a).

Page 7: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 7/55

7/1/2013 Relations 7

Section 10.2

Reflexivity, Symmetry, and

Transitivity

Page 8: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 8/55

7/1/2013 Relations 8

Reflexivity, Symmetry, andTransitivity

Let R be a relation on a set A.

R is reflexive if ( x, x) ∈ R for all x ∈ A.

R is symmetric if for all x, y ∈ A( x, y) ∈ R → ( y, x) ∈ R.

R is transitive if for all x, y, z ∈ A

( x, y) ∈ R and ( y, z) ∈ R → ( x, z) ∈ R.

Page 9: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 9/55

7/1/2013 Relations 9

Examples

Which of the following relations arereflexive? symmetric? transitive?

a ⋅ b = a, on a Boolean algebra B.

R × R, on R.

∅, on R.

Page 10: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 10/55

7/1/2013 Relations 10

Section 10.3

Equivalence Relations

Page 11: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 11/55

7/1/2013 Relations 11

Equivalence Relations

An equivalence relation on a set A is arelation on A that is reflexive, symmetric,

and transitive.

We use the symbol ~ as a generic symbol

for an equivalence relation.

Page 12: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 12/55

7/1/2013 Relations 12

Examples of EquivalenceRelations

Which of the following are equivalencerelations?

a ⋅ b = a, on a Boolean algebra B.

gcd(a, b) = 1, on Z+.

gcd(a, b) = a, on Z+.

A ∩ B = ∅, on℘(U ).  A =  B, on℘(U ).

Page 13: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 13/55

7/1/2013 Relations 13

Examples of EquivalenceRelations

Which of the following are equivalencerelations?

R × R, on R.

∅, on R.

Page 14: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 14/55

7/1/2013 Relations 14

Equivalence Classes

Let ~ be an equivalence relation on a set Aand let a ∈ A.

The equivalence class of a is

[a] = { x ∈ A  x ~ a}.

Page 15: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 15/55

7/1/2013 Relations 15

Examples: Equivalence Classes

Describe the equivalence classes of each of the following equivalence relations.

a ≡ b (mod 10), on Z.

 A =  B, on℘(U ).

p ↔ q, on a set of statements.

R

×R

, onR

.

Page 16: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 16/55

7/1/2013 Relations 16

Equivalence Classes andPartitions

Theorem: Let ~ be an equivalence relationon a set A. The equivalence classes of ~

form a partition of  A.

Proof:

We must show that

The equivalence classes are pairwise disjoint, The union of the equivalence classes equals A.

Page 17: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 17/55

7/1/2013 Relations 17

Proof, continued

Proof that the equivalence classes arepairwise disjoint.

Let [a] and [b] be two distinct equivalence

classes.

Suppose [a] ∩ [b] ≠ ∅.

Let x ∈ [a] ∩ [b].

Then x ~ a and x ~ b.

Therefore, a ~ x and x ~ b.

Page 18: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 18/55

7/1/2013 Relations 18

Proof, continued

By transitivity, a ~ b. Now let y ∈ [a].

Then y ~ a.

By transitivity, y ~ b.

So y ∈ [b].

Therefore, [a] ⊆ [b].

By a similar argument, [b] ⊆ [a].

Page 19: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 19/55

7/1/2013 Relations 19

Proof, continued

Thus, [a] = [b], which is a contradiction Therefore, [a] ∩ [b] = ∅.

Thus, the equivalence classes are pairwise

disjoint.

Page 20: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 20/55

7/1/2013 Relations 20

Proof, continued

Proof that the union of the equivalenceclasses is A.

Let a ∈ A.

Then a ∈ [a] since a ~ a.

Therefore, a is in the union of the equivalence

classes.

So, A is a subset of that union.

Page 21: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 21/55

7/1/2013 Relations 21

Proof, concluded

On the other hand, every equivalence class is asubset of  A.

Therefore, the union of the equivalence classes

is a subset of  A. Therefore, the union of the equivalence classes

equals A.

Therefore, the equivalence classes form apartition of  A.

Page 22: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 22/55

7/1/2013 Relations 22

Example: A Partition Induced byan Equivalence Relation

Let F be the set of all functions f : R→ R. For f , g ∈ F , define f ~ g to mean that f is

O(g) and g is O( f ).

Page 23: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 23/55

7/1/2013 Relations 23

Example: A Partition Induced byan Equivalence Relation

Theorem: ~ is an equivalence relation on F . Proof:

Reflexivity Obviously, f ~ f for all f ∈ F .

Symmetry

By the symmetry of the definition of ~, it isclear that f ~ g implies that g ~ f .

Page 24: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 24/55

7/1/2013 Relations 24

Example: A Partition Induced byan Equivalence Relation

Transitivity Let f , g, h ∈ F and suppose that f ~ g and g ~ h.

Then there exist M 1 and x1 and M 2 and x2 such

that

 f ( x) ≤ M 1g( x)for all x ≥ x

1

and

g( x) ≤ M 2h( x)for all x ≥ x2.

Page 25: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 25/55

7/1/2013 Relations 25

Example: A Partition Induced byan Equivalence Relation

Let M = M 1 ⋅ M 2 and let x0 = max( x1, x2). Then for all x ≥ x0,

 f ( x)≤ M 1g( x)

≤ M 1 ⋅ M 2h( x)= M h( x).

Therefore, f is O(h).

Similarly, we can show that h is O( f ).

Therefore, f ~ h.

Page 26: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 26/55

7/1/2013 Relations 26

Example: A Partition Induced byan Equivalence Relation

Therefore, ~ is an equivalence relation on F . The equivalence class of  f is the set [ f ] of all

functions with the same growth rate as f .

The most important equivalence classes are

[ xa], a ∈ R.

[b x], b ∈ R. [ xa log x], a ∈ R.

Page 27: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 27/55

7/1/2013 Relations 27

The Equivalence RelationInduced by a Partition

Let A be a set and let { Ai}i∈ I be a partitionof  A.

Define a relation ~ on A as

 x ~ y ↔ x, y ∈ Ai for some i ∈ I .

Page 28: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 28/55

7/1/2013 Relations 28

The Equivalence RelationInduced by a Partition

Theorem: The relation ~ defined above isan equivalence relation on A.

Page 29: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 29/55

7/1/2013 Relations 29

Proof 

Proof: We must prove that ~ is reflexive,

symmetric, and transitive.

Proof that ~ is reflexive.

Let a ∈ A.

Then a is in Ai for some i ∈ I . So a ~ a.

Page 30: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 30/55

7/1/2013 Relations 30

Proof, continued

Proof that ~ is symmetric. Let a, b ∈ A and suppose that a ~ b.

Then a, b ∈ Ai for some i ∈ I .

So b, a ∈ Ai for some i ∈ I .

Therefore b ~ a.

Page 31: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 31/55

7/1/2013 Relations 31

Proof, concluded

Proof that ~ is transitive. Let a, b, c ∈ A and suppose a ~ b and b ~ c.

Then a, b ∈ Ai for some i ∈ I and b, c ∈ A j for

some j ∈ I .

That means that b ∈ Ai ∩ A j.

This is possible only if  Ai = A j.

Therefore, a, c ∈ Ai.

So, a ~ c.

Page 32: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 32/55

7/1/2013 Relations 32

Section 10.4

Partial Order Relations

Page 33: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 33/55

7/1/2013 Relations 33

Antisymmetry

A relation R on a set A is antisymmetric if for all a, b ∈ A,

[(a, b) ∈ R and (b, a) ∈ R] → a = b.

Page 34: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 34/55

7/1/2013 Relations 34

Examples: Antisymmetry

The following relations are antisymmetric. a b, on Z+.

A ⊆ B, on ℘(U ).

p → q, on the set of all statements (= means ≡).

x ≤ y, on R.

a ⋅ b = a, on a Boolean algebra B.

Page 35: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 35/55

7/1/2013 Relations 35

Partial Order Relations

A relation R on a set A is a partial order relation if 

R is reflexive.

R is antisymmetric.

R is transitive.

We use ≤ as the generic symbol for a partialorder relation.

Page 36: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 36/55

7/1/2013 Relations 36

Examples: Partial OrderRelations

The following relations are partial orderrelations.

a b, on Z+.

A ⊆ B, on ℘(U ).

p → q, on the set of all statements (= means ≡).

x ≤ y, on R.

a ⋅ b = a, on a Boolean algebra B.

Page 37: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 37/55

7/1/2013 Relations 37

Total Order Relations

A relation < on a set A is a total order relation if it has the following properties.

< is transitive.

Trichotomy – For all a, b ∈ A, exactly one of the following holds:

a < b.

b < a.

a = b.

Page 38: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 38/55

7/1/2013 Relations 38

Partial Orders and Total Orders

It is important to realize that not everypartial order is a total order.

Example

Let ≤ be the subset relation ⊆ and let A = ℘({a, b, c}).

Then {a, b}, {a, c} ∈℘( A),

But {a, b} ⊄ {a, c}, {a, c} ⊄ {a, b}, and{a, b} ≠ {a, c}.

Page 39: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 39/55

7/1/2013 Relations 39

Partial Orders and Total Orders

Theorem: If < is a total ordering of a set Aand we define a ≤ b to mean that a < b or

a = b, then ≤ is a partial ordering of  A.

Proof:

Reflexivity.

a ≤ a because a = a.

Page 40: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 40/55

7/1/2013 Relations 40

Proof, continued

Antisymmetry. Suppose a ≤ b and b ≤ a.

Then

a < b or a = b, and

b < a or b = a.

Suppose a < b.

Then a ≠ b, and b < a is false.

This contradicts b ≤ a.

Page 41: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 41/55

7/1/2013 Relations 41

Proof, continued

Therefore, a < b is false. So, a = b, since a ≤ b.

Page 42: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 42/55

7/1/2013 Relations 42

Proof, continued

Transitivity. Suppose a ≤ b and b ≤ c.

Then

a < b or a = b, and

b < c or b = c.

Case 1: a < b and b < c.

Then a < c.

Therefore, a ≤ c.

Page 43: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 43/55

7/1/2013 Relations 43

Proof, concluded

Case 2: a < b and b = c. Then a < c.

Therefore, a ≤ c.

Cases 3 and 4 are similar.

Page 44: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 44/55

7/1/2013 Relations 44

Hasse Diagrams

A Hasse diagram is a drawing thatrepresents a partial order relation.

Draw a diagram in which

a ≤ b is represented by a  b.

a is drawn below b.

If there exists c such that a ≤ c and c ≤ b, thenwe represent only a ≤ c and c ≤ b; a ≤ b is

implied by transitivity.

Page 45: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 45/55

7/1/2013 Relations 45

Example: Hasse Diagram

Let the relation be ⊆ on ℘({a, b, c}).

{a , b , c  }

{a , c  } {b , c  }{a , b }

{a } {b } {c  }

{}

Page 46: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 46/55

7/1/2013 Relations 46

Example: Hasse Diagram

Let the relation be on {1, 2, 3, 4, 6, 12}12

6

3

4

2

1

Page 47: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 47/55

7/1/2013 Relations 47

Example: Partial Order Relation

Let F be the set of all functions f : R→ R. Define a relation ≤ on the equivalence

classes [ f ] of F , under the equivalence

relation f ~ g if  f is O(g) and g is O( f ), by

[ f ] ≤ [g] if  f is O(g).

Page 48: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 48/55

7/1/2013 Relations 48

[ f ] ≤ [g] is Well Defined

First, we must show that ≤ is well defined on F . Suppose that f is O(g) and let f ′  in [ f ] and g′  in [g].

Then f ′  ~ f and g′  ~ g.

Then f ′  is O( f ) and f is O(g), so f ′  is O(g).

Furthermore, f ′  is O(g) and g is O(g′  ), so f ′  is

O(g′  ).

Therefore, [ f ′  ] <= [g′  ].

Page 49: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 49/55

7/1/2013 Relations 49

Example: Partial Order Relation

Theorem: ≤ is a partial order relation on F . Proof:

Reflexivity

It is clear that [ f ] ≤ [ f ] . (Let M = 1, x0 = 0.)

Page 50: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 50/55

7/1/2013 Relations 50

Example: Partial Order Relation

Antisymmetry Suppose that [ f ] ≤ [g] and [g] ≤ [ f ] .

Then f is O(g) and g is O( f ).

This is the definition of  f ~ g.

Therefore, [ f ] = [g].

Page 51: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 51/55

7/1/2013 Relations 51

Example: Partial Order Relation

Transitivity Suppose that [ f ] ≤ [g] and [g] ≤ [h].

Then f is O(g) and g is O(h).

We have already shown that this implies that f is O(h).

Therefore, [ f ] ≤ [h].

Thus, ≤ is a partial order relation.

Page 52: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 52/55

7/1/2013 Relations 52

Total Orderings and Sorting

In C++, if we define an order relation < on aclass, then we may sort the class, provided <

is a total ordering of the members of the

class.

E l T l O d i d

Page 53: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 53/55

7/1/2013 Relations 53

Example: Total Ordering and

Sorting

Define a Point object to consist of twodoubles.

class Point

{

double x;

double y;

};

E l T l O d i d

Page 54: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 54/55

7/1/2013 Relations 54

Example: Total Ordering and

Sorting

Define operator<() on the Point class asfollows.

bool operator<(const Point& p, const Point& q)

{

if (p.x != q.x)

return p.x < q.x;

else

return p.y < q.y;}

E l T l O d i d

Page 55: Math 103 - 10 Relations

8/22/2019 Math 103 - 10 Relations

http://slidepdf.com/reader/full/math-103-10-relations 55/55

7/1/2013 Relations 55

Example: Total Ordering and

Sorting

Sort the list{(2, 3), (3, 3), (3, 2), (2, 2)}.

The problem is that < is not a total ordering

of the Point class.

Is < a partial ordering?