Lesson 4: Relations

Introduction to Discrete Math 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.

Example:

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

graph

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)

graph

Previous Lesson

Back to Course