Lesson 4: Relations

In this lesson

Set Relations

In real life, relationships between elements exist in many contexts. for example:

  • A relationship between an employee and their salary
  • A relationship between a student and their grades

In discrete math, a relationship between elements of sets is represented using the terminology relation, which is the subset of the Cartesian product of the set.

Binary Relation

A binary relation R is the relation from set A to set B, which is the subset R ⊆ A × B. For Example:

Given the sets A = {0,1,2} and B = {3,4}:

{(0, 3), (0, 4), (1,3) , (2, 4)} is a relation from A to B, which is a subset of A X B

A × B = {(0,3), (0,4), (1,3), (1,4), (2,3), (2,4)}

A relation from set A to set B can be illustrated below

table slide 31

Relations notation

  • If (a,b) ∈ R, then we can write aRb.
  • If (a,b) ∈ R, then a is said to be related to b by R.
  • If (a,b) ∉ R, then we can write aRb.

Are relations and functions the same?

They are not the same. Many people get confused with the two terms.

  • Relations are more general than functions.
  • In functions, all elements in set A must be related to an element in B. In contrast, in a relation, it is possible to have elements from A that are unrelated to any elements in B.
  • In relation, it is possible to have both (a,b) ∈ R and (a,c) ∈ R, where b≠c.

Example of relations

Example I:

Given the two sets:

Set A, contains all cities in the US

Set B, contains all States in the US

The relation R (a,b) is where a city a in Set A belongs to a state b in Set B.


(Detroit, MI),(Los Angeles, CA),(Newyork City, NY)



Example II:

Set S, contains all students at Harvard University.

Set C, contains all courses offered at Harvard.

The relation R from S to C is defined only if s(student) is enrolled in c (course)