Relations (8.1, 8.2, 8.3)

Practice Problems

8.1 .- 5bc, 14, 20, 23.

8.2 .- 5, 10, 14, 35, 44, 53.

8.3 .- 10, 22, 37.

Concepts

Relation

A binary relation   on sets    is a subset of .  

When   we may also write  .

Relation on a Set

A binary relation   “on ”   is a subset of .  

Inverse

The inverse of a relation   on sets  , written    is defined as:

Types of Relations

Let   be a relation on set  .  

Reflexive Relation

  is Reflexive iff  .

Symmetric Relation

  is Symmetric iff  .

Transitive Relation

  is Transitive iff  .

Transitive Closure

Let   be a relation on set  .  

The transitive closure of , written  , is the relation on  that satisfies:

1.   is transitive
2. 
3.   is minimal. No subset of   is transitive and contains

Equivalence Relation

Let   be a relation on set  .  

  is an Equivalence relation when  is Reflexive and Symmetric and Transitive. 

Equivalence Class

Let   be a relation on set   and  an element of  .

The equivalent class of ,  written   is the set of all elements related to  .

i.e.: