we can obtain R by adding ( , ) to R to get the desired relation. However, we can not add two pairs ( , ), ( , ) or single pair ( , ) to R at a time, as by doing so, we will be forced to add the remaining pair in order to maintain transitivity and in the process, the relation will become symmetric also which is not required. Thus, the total number of desired relations is three. Example Show that the number of equivalence relation in the set { , , } containing ( , ) and ( , ) is two.
Solution The smallest equivalence relation R containing ( , ) and ( , ) is {( , ), ( , ), ( , ), ( , ), ( , )}. Now we are left with only pairs namely ( , ), ( , ), ( , ) and ( , ). If we add any one, say ( , ) to R , then for symmetry we must add ( , ) also and now for transitivity we are forced to add ( , ) and ( , ). Thus, the only equivalence relation bigger than R is the universal relation.
This shows that the total number of equivalence relations containing ( , ) and ( , ) is two. Example Consider the identity function I N : N → N defined as I N ( x ) = x ∀ x ∈ N . Show that although I N is onto but I N + I N : N → N defined as (I N + I N ) ( x ) = I N ( x ) + I N ( x ) = x + x = x is not onto. Solution Clearly I N is onto.
But I N + I N is not onto, as we can find an element in the co-domain N such that there does not exist any x in the domain N with (I N + I N ) ( x ) = x = . Example Consider a function f : ,