Skip to content Skip to navigation

Connexions

You are here: Home » Content » Relation types

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the author

Recently Viewed

This feature requires Javascript to be enabled.

Relation types

Module by: Sunil Kumar Singh

Relations among elements of a set have wide possibilities. A systematic approach to study them is facilitated by recognizing different relation types. It should be noted that all relation types described here are relation on one set.

We describe a relation on set itself as :

Definition 1: Relation on A
A relation “R” from set “A” to “A” is called a “relation on A”.

In this module, we shall be using a symbol, “xRy” to denote an instance of relation (ordered pair). The symbol conveys that the instance of relation denoted by the symbol is an ordered pair (x,y), which follows relation “R”.

Void relation

Relation is a subset of Cartesian product of two sets. We have seen that power set of Cartesian product “ A × B A × B ” is a set of all possible relations among the elements of sets “A” and “B”. In the case of “relation on A”, the power set of Cartesian product “ A × A A × A ” is a set of all possible relations among the elements of set “A”.

One of the subsets of the power set is empty set or void set. This subset without any element is called the void relation.

R = φ = { } R = φ = { }

Universal relation

Universal relation is the widest possible relation. This relation consists of all ordered pairs of the Cartesian product “ A × A A × A ”.

R = A × A R = A × A

Consider a set A = { 1,2,3 } A = { 1,2,3 } . Then, universal relation set is :

R = { 1,1 , 1,2 , 1,3 , 2,1 , R = { 1,1 , 1,2 , 1,3 , 2,1 ,

2,2 , 2,3 , 3,1 , 3,2 , 3,3 } 2,2 , 2,3 , 3,1 , 3,2 , 3,3 }

Identity relation

An identity relation is defined as :

Definition 2: Identity relation
In an identity relation "R", every element of the set “A” is related to itself only.

Note the conditions conveyed through words “every” and “only”. The word “every” conveys that identity relation consists of ordered pairs of element with itself - all of them. The word “only” conveys that this relation does not consist of any other combination.

Consider a set A = { 1,2,3 } A = { 1,2,3 } . Then, its identity relation is :

R = { 1,1 , 2,2 , 3,3 } R = { 1,1 , 2,2 , 3,3 }

It is evident that a set has only one such relation. This relation, as we can see, identifies the set - as it identifies each elements of the set, which are related to itself. By looking at the relation, we can identify the set itself. For this reason, the name of this relation is identity relation. In set builder form, we express an identity relation as

R = { x , x : for all x ∈ A } R = { x , x : for all x ∈ A }

The qualification of the relation is that first and second element of the ordered pair is same element, which belongs to set A.

The followings are not an identity relation :

R 1 = { 1,1 , 2,2 } R 1 = { 1,1 , 2,2 }

R 2 = { 1,1 , 2,2 , 3,3 , 1,2 , 1,3 } R 2 = { 1,1 , 2,2 , 3,3 , 1,2 , 1,3 }

First one is not an identity relation as it does not include the pairing of remaining element “3”. Second is not an identity relation, because there are other combinations of pairs in the relation.

Reflexive relation

Reflexive relation is an expansion of identity relation. In the simple word, reflexive relation is plus identity relation.

Definition 3: Reflexive relation
In reflexive relation, "R", every element of the set “A” is related to itself.

The definition of reflexive relation is exactly same as that of identity relation except that it misses the word “only” in the end of the sentence. The implication is that this relation includes identity relation and permits other combination of paired elements as well.

Consider a set A = { 1,2,3 } A = { 1,2,3 } . Then, one of the possible reflexive relations can be :

R = { 1,1 , 2,2 , 3,3 , 1,2 , 1,3 } R = { 1,1 , 2,2 , 3,3 , 1,2 , 1,3 }

However, following is not a reflexive relation :

R 1 = { 1,1 , 2,2 , 1,2 , 1,3 } R 1 = { 1,1 , 2,2 , 1,2 , 1,3 }

It is not a reflexive relation as one instance of identity relation (3,3) is absent and violates the condition that every element of the set is related to itself.

We state the condition for reflexive relation as :

R is reflexive ⇔ x , x ∈ R , for all x ∈ A R is reflexive ⇔ x , x ∈ R , for all x ∈ A

It is clear that identity relation is a reflexive relation. Further, universal relation consists of all combinations of ordered pairs in the Cartesian product. It means it consists of all elements of the identity relation apart from other ordered pairs. Hence, universal relation is also a reflexive relation.

Interpretation of reflexive relation

Reflexivity of a relation (meaning that a relation is reflexive) is used to characterize important algebraic relations. Following relations are reflexive :

  • “is equal to”
  • “is less than or equal to”
  • “is greater than or equal to”
  • “divides”
  • “is subset of”

The relation “is less than” or “greater than”, however, are not reflexive.

Examples

Problem 1 : Determine whether “greater than or equal to” is a reflexive relation for natural number.

Solution : A relation, “R”, representing “greater than or equal to” is defined as relation on natural number (N) as :

x , y ∈ R ⇔ x ≥ y where x , y ∈ N x , y ∈ R ⇔ x ≥ y where x , y ∈ N

We construct data for “x” and “y” in accordance with the given relation for few initial natural numbers, say 1, 2 and 3, as under :

For x = 1, y = 1,2,3 For x = 1, y = 1,2,3

F o r x = 2, y = 2,3 F o r x = 2, y = 2,3

F o r x = 3, y = 3 F o r x = 3, y = 3

Thus, the relation set is :

R = { 1,1 , 1,2 , 1,3 , 2,2 , 2,3 , 3,3 } R = { 1,1 , 1,2 , 1,3 , 2,2 , 2,3 , 3,3 }

Evidently, this set consists of relation of all elements of the set, which are related to itself ie. (1,1), (2,2) and (3,3). Thus, we conclude that “is greater than or equal to” is a reflexive relation.

Problem 2 : Determine whether “is not equal to” is a reflexive relation for natural number?

Solution : A relation, “R”, representing “is not equal to” is defined as relation on natural number (N) as :

x , y ∈ R ⇔ x ≠ y w h e r e x , y ∈ N x , y ∈ R ⇔ x ≠ y w h e r e x , y ∈ N

We construct data for “x” and “y” in accordance with the given relation for few initial natural numbers, say 1,2 and 3, as under :

F o r x = 1, y = 2,3 F o r x = 1, y = 2,3

F o r x = 2, y = 1,3 F o r x = 2, y = 1,3

F o r x = 3, y = 1,2 F o r x = 3, y = 1,2

Thus, the relation set is :

R = { 1,2 , 1,3 , 2,1 , 2,3 , 3,1 , 3,2 } R = { 1,2 , 1,3 , 2,1 , 2,3 , 3,1 , 3,2 }

Evidently, this set does consists of all ordered pair representing relation of an element with itself. The instances (1,1), (2,2) and (3,3) are missing. Thus, we conclude that “is not equal to" is a irreflexive relation.

Symmetric relation

In symmetric relation, the instance of relation has a mirror image. It means that if (1,3) is an instance, then (3,1) is also an instance in the relation. Clearly, an ordered pair of element with itself like (1,1) or (2,2) are themselves their mirror images. Consider some of the examples of the symmetric relation,

R 1 = { 1,2 , 2,1 , 1,3 , 3,1 } R 1 = { 1,2 , 2,1 , 1,3 , 3,1 }

R 2 = { 1,2 , 1,3 , 2,1 , 3,1 , 3,3 } R 2 = { 1,2 , 1,3 , 2,1 , 3,1 , 3,3 }

We have purposely jumbled up ordered pairs to emphasize that order of elements in relation is not important. In order to decide symmetry of a relation, we need to identify mirror pairs. We state the condition of symmetric relation as :

I f f x , y ∈ R ⇒ y , x ∈ R for all x , y ∈ A I f f x , y ∈ R ⇒ y , x ∈ R for all x , y ∈ A

The symbol “Iff” means “If and only if”. Here one directional arrow means “implies”. Alternatively, the condition of symmetric relation can be stated as :

x R y ⇒ y R x for all x , y ∈ A x R y ⇒ y R x for all x , y ∈ A

In words, we say that if (x,y) be an instance of relation, then (y,x) will also be the instance of a symmetric relation "R".

It is clear that identity relation is a symmetric relation. Also, universal set consists of the Cartesian product of a set with itself. It means that the relation consists of instances with mirror instances. Therefore, universal relation is also symmetric relation.

Symmetric and inverse relation

An inverse relation ( R − 1 R − 1 ) consists of ordered pairs with exchange of positions of the elements in a given relation (R). Now let us consider a symmetric relation,

R = { 1,2 , 1,3 , 2,1 , 3,1 , 3,3 } R = { 1,2 , 1,3 , 2,1 , 3,1 , 3,3 }

By definition, its inverse relation is :

⇒ R - 1 = { 2,1 , 3,1 , 1,2 , 1,3 , 3,3 } ⇒ R - 1 = { 2,1 , 3,1 , 1,2 , 1,3 , 3,3 }

Using the fact that order does not change a set, we conclude that :

⇒ R = R - 1 ⇒ R = R - 1

We use this fact to identify symmetric relation. The given set is a symmetric relation, if it equals its inverse set.

Analytical proof

Let “R” be a symmetric relation on set “A”. In order to prove that R = R - 1 R = R - 1 , we consider an arbitrary instance of relation “R” :

x , y ∈ R x , y ∈ R

According to definition of symmetric relation,

y , x ∈ R y , x ∈ R

According to definition of inverse relation,

x , y ∈ R - 1 x , y ∈ R - 1

But, we had started with “R” and used definitions to show that “(x,y)” belongs to another set “ R − 1 R − 1 ”. It means that the “ R − 1 R − 1 ”set consists of the elements of set “R” – at the least. Thus,

R ⊂ R - 1 R ⊂ R - 1

Similarly, we can start with “ R - 1 R - 1 ”set and reach the conclusion that :

R - 1 ⊂ R R - 1 ⊂ R

If sets are subsets of each other, then they are equal. Hence,

⇒ R = R - 1 ⇒ R = R - 1

Asymmetric relation

A relation “R” on a set “A” is asymmetric for the following condition :

I f f x , y ∈ R and y , x ⇒ a = b for all x , y ∈ A I f f x , y ∈ R and y , x ⇒ a = b for all x , y ∈ A

It means that possibility of symmetry in asymmetric relation exists only if elements are equal.

Transitive relation

If “R” be the relation on set A, then we state the condition of transitive relation as :

I f f x , y ∈ R and y , z ∈ R ⇒ x , z ∈ R for all a , b , c ∈ A I f f x , y ∈ R and y , z ∈ R ⇒ x , z ∈ R for all a , b , c ∈ A

Alternatively,

x R y a n d y R z ⇒ x R z for all x , y , z ∈ A x R y a n d y R z ⇒ x R z for all x , y , z ∈ A

In words, we say that if (x,y) and (y,z) be the instances of a relation R such that (a,z) is also the instance of the relation, then that relation is transitive.

The identity and universal relations are transitive. Some other important transitive relations are :

  • “is equal to”
  • “is greater than”
  • “is at least as great as”
  • “is a subset of”
  • "divides"

Example

Problem 3 : Determine whether “divides” is a transitive relation for natural number?

Solution : Let us consider three elements “x”,”y” and “z” of set “N” of natural numbers such that a relation “R” on “N” is :

x , y ∈ R , y , z ∈ R , “ divides ” , x , y , z ∈ N x , y ∈ R , y , z ∈ R , “ divides ” , x , y , z ∈ N

This means that :

“ x divides y ” and “ y divides z ” “ x divides y ” and “ y divides z ”

Let us now consider two natural numbers “a” and “b” such that :

y = a x and z = b y y = a x and z = b y

z = a b x z = a b x

This means that “x divides z”. Hence, we conclude that the relation "divides" is transitive relation.

Equivalence relation

A relation is equivalence relation if it is reflexive, symmetric and transitive at the same time. In order to check whether a relation is equivalent or not, we need to check all three characterizations.

Comments, questions, feedback, criticisms?

Send feedback