BACHELOR OF BUSINESS COMPUTING

BBC 1114: COMPUTING MATHEMATICS

Topic 3: Sets and Relations
Topic objectives
i. To understand the fundamental concept of sets and their notation.
ii. To explore various operations on sets and their properties.
iii. To introduce the concept of binary relations and their applications.
iv. To study equivalence relations and their significance.
v. To learn about partial orders and their role in ordered sets.
Learning outcomes
By the end of this lecture series, students should be able to:
i. Define and represent sets using set-builder notation and roster
notation.
ii. Perform set operations, such as union, intersection, and complement,
and understand their properties.
iii. Explain binary relations, including reflexive, symmetric, and transitive
relations.
iv. Identify equivalence relations and distinguish them from other types of
relations.
v. Define partial orders and explain how they are used to create ordered
sets.
Outline.
i. Introduction to Sets
ii. Operations on Sets
iii. Binary Relations
iv. Equivalence Relations
v. Partial order
vi. Applications and Examples
Timings:

Total hours: 6 hours

i. Lectures: 4 hours
ii. Tutorials: 2 hours

Private Study: 3 hours

1
Introduction to sets
Understanding the fundamental concepts of sets and their notations is
essential for various branches of mathematics and problem-solving in
different fields. Sets provide a framework for organizing and analyzing data,
making them a crucial concept in mathematics.
Definition of Sets:
A set is a well-defined collection of distinct objects or elements. These
objects can be numbers, letters, or any other items, and they are
referred to as the members or elements of the set.
Set Notation:
Sets can be represented using two common notations:
i. Roster Notation: In roster notation, a set is listed by enumerating all its
elements within curly braces {}.
For example: The set of even numbers less than 10: {2, 4, 6, 8}
ii. Set-Builder Notation: In set-builder notation, a set is defined by
specifying a rule or condition that its elements must satisfy. The
notation typically looks like this:
- {x | x is an even number less than 10}
Universal Set:
The universal set, denoted as U, is a set that contains all the elements under
consideration in a particular context or problem. It is the largest set relevant
to a given discussion. For example, if we are working with the set of all
natural numbers, the universal set might be the set of all real numbers.
Empty Set:
The empty set, denoted as ∅ or {}, is a set that contains no elements. It is a
fundamental concept in set theory and serves as the starting point for
constructing sets. It is important to note that the empty set is a subset of
every set.
Subset:
A set A is said to be a subset of another set B, denoted as A ⊆ B, if every
element of set A is also an element of set B.

be a proper subset of B (A ⊂ B), meaning that A is a subset of B but not equal

If A is a subset of B, it is possible that A and B are equal (A = B), or A could

to B.
Power Set:

2
The power set of a set A, denoted as P(A), is the set that contains all possible
subsets of A, including A itself and the empty set.
If A has n elements, the power set P(A) will have 2^n elements.
For example, if A = {1, 2}, then P(A) = {∅, {1}, {2}, {1, 2}}.
Cardinality of Sets:
The cardinality of a set A, denoted as |A|, is the number of elements in that
set. It represents the size or count of the set.
For example, if A = {1, 2, 3}, then |A| = 3.
Operations on Sets

The union of two sets A and B, denoted as A ⋃ B, is a set that contains

 Union (⋃):

all the distinct elements that are in either set A or set B, or in both.
Mathematically, A ⋃ B = {x | x ∈ A or x ∈ B}.

The intersection of two sets A and B, denoted as A ⋂ B, is a set that

 Intersection (⋂):

contains all the distinct elements that are common to both set A and
set B.
Mathematically, A ⋂ B = {x | x ∈ A and x ∈ B}.
 Complement (¬ or '):
The complement of a set A, denoted as ¬A or A', is a set that contains
all the elements that are in the universal set U but not in set A.
Mathematically, ¬A = {x | x ∈ U and x ∉ A}.
Set Identities and Properties:
Sets follow various identities and properties, including:
Commutative Laws: A ⋃ B = B ⋃ A and A ⋂ B = B ⋂ A
Associative Laws: (A ⋃ B) ⋃ C = A ⋃ (B ⋃ C) and (A ⋂ B) ⋂ C = A ⋂
i.

(B ⋂ C)
ii.

Distributive Laws: A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C) and A ⋂ (B ⋃ C) =

(A ⋂ B) ⋃ (A ⋂ C)
iii.

Identity Laws: A ⋃ ∅ = A and A ⋂ U = A

Null Laws: A ⋃ A' = U and A ⋂ A' = ∅
iv.

Domination Laws: A ⋃ U = U and A ⋂ ∅ = ∅

v.

Idempotent Laws: A ⋃ A = A and A ⋂ A = A

vi.
vii.

3
De Morgan's Laws:
De Morgan's laws describe the relationship between union and intersection
of sets with respect to complements:
First De Morgan's Law: ¬(A ⋃ B) = ¬A ⋂ ¬B
Second De Morgan's Law: ¬(A ⋂ B) = ¬A ⋃ ¬B
i.
ii.
These laws are essential for simplifying expressions involving set operations.
Cartesian Product (×):
The Cartesian product of two sets A and B, denoted as A × B, is a set that
contains all possible ordered pairs (a, b) where "a" is an element of set A,
and "b" is an element of set B.
Mathematically, A × B = {(a, b) | a ∈ A and b ∈ B}.
For example, if A = {1, 2} and B = {a, b}, then A × B = {(1, a), (1, b), (2, a),
(2, b)}.
Understanding these set operations, identities, properties, and De Morgan's
laws is crucial for solving problems involving sets and set theory, as they
provide powerful tools for manipulating and analyzing sets and their
relationships.
Binary Relations
In summary, binary relations are a fundamental concept in mathematics that
describe how elements of a set are related to each other. Understanding the
properties of reflexive, symmetric, and transitive relations, along with the
use of directed graphs, can help analyze and visualize these relationships
effectively.
Definition:
In mathematics, a binary relation on a set A is a subset of the
Cartesian product A × A. In simpler terms, it is a set of ordered pairs
(a, b) where both "a" and "b" belong to set A. Binary relations are used
to describe relationships or connections between elements of a set.
Examples of Relations:
 Equality Relation (=): On the set of real numbers, the equality relation
is a binary relation where (a, b) is in the relation if and only if a = b. It
relates elements that are equal.
 Less Than Relation (<): On the set of natural numbers, the less than
relation is a binary relation where (a, b) is in the relation if and only if a
< b. It relates elements where one is less than the other.

4
 Parent-Child Relation: On the set of all humans, the parent-child
relation is a binary relation where (a, b) is in the relation if and only if
"a" is the parent of "b."
 Divisibility Relation: On the set of positive integers, the divisibility
relation is a binary relation where (a, b) is in the relation if and only if
"a" divides "b" without a remainder.

Reflexive, Symmetric, and Transitive Relations:

These are important properties of binary relations that describe how
elements in the set are related within the relation.
Reflexive Relation:
A relation R on a set A is reflexive if, for every element "a" in set A, the
ordered pair (a, a) is in the relation R.
In other words, every element is related to itself.
Example: The equality relation (=) is reflexive because a = a for all a in
the set.
Symmetric Relation:
A relation R on a set A is symmetric if, for every pair (a, b) in the
relation R, the pair (b, a) is also in the relation R.
In other words, if "a" is related to "b," then "b" is related to "a."
Example: The "is-sibling-of" relation is symmetric because if person A
is a sibling of person B, then person B is also a sibling of person A.
Transitive Relation:
A relation R on a set A is transitive if, for every pair of ordered pairs (a,
b) and (b, c) in the relation R, the ordered pair (a, c) is also in the
relation R.
In other words, if "a" is related to "b," and "b" is related to "c," then "a"
is related to "c."
Example: The "is-ancestor-of" relation is transitive because if person A
is an ancestor of person B, and person B is an ancestor of person C,
then person A is also an ancestor of person C.
Directed Graphs to Represent Relations:

5
Binary relations can be visually represented using directed graphs, where the
elements of the set are nodes (vertices), and the ordered pairs in the relation
are represented as directed edges (arcs).
Nodes represent elements of the set.
Directed edges represent the ordered pairs in the relation, with arrows
indicating the direction of the relation.
The directed graph of relation R = {(a,a),(a,b),(b,b),(b,c),(c,c),(c,b),(c,a)} is
represented as :

Since, there is loop at every node, it is reflexive but it is neither symmetric

nor antisymmetric as there is an edge from a to b but no opposite edge from
b to a and also directed edge from b to c in both directions. R is not transitive
as there is an edge from a to b and b to c but no edge from a to c.
Equivalence Relations:
Equivalence relations are fundamental in mathematics and are used to
classify objects into classes of equivalence. They provide a way to
understand and organize relationships between elements of a set, ensuring
that these relationships are reflexive, symmetric, and transitive.
Definition:
An equivalence relation on a set A is a binary relation that satisfies three
key properties:
 Reflexivity: For all elements a in set A, (a, a) is in the relation.
 Symmetry: If (a, b) is in the relation, then (b, a) must also be in the
relation.

6
 Transitivity: If (a, b) and (b, c) are in the relation, then (a, c) must
also be in the relation.
In simpler terms, an equivalence relation is a relation that is reflexive,
symmetric, and transitive.
Properties of Equivalence Relations:
Equivalence relations have some important properties:
 Equivalence Class: For any element a in set A, the equivalence class
[a] is the set of all elements that are related to a. It can be defined as
[a] = {x | (a, x) is in the equivalence relation}.
 Partition: An equivalence relation on a set A divides A into disjoint
subsets called equivalence classes. These equivalence classes
together form a partition of the set A.
 Uniqueness: Each element belongs to exactly one equivalence class.
 Completeness: The union of all equivalence classes covers the entire
set A.
Examples of Equivalence Relations:
Equality ( = ):
On the set of real numbers, the equality relation is an equivalence
relation. It satisfies reflexivity, symmetry, and transitivity.
Equivalence class for any element 'a' is [a] = {a}, as each element is
equivalent only to itself.
Modular Congruence (≡):
On the set of integers, the modular congruence relation is an
equivalence relation. For a fixed positive integer 'm', (a, b) is in the
relation if and only if (a - b) is divisible by 'm'.
Equivalence class for an integer 'a' is [a] = {b | a ≡ b (mod m)}.
Partition of Integers (≈):
On the set of integers, the relation ≈ is defined such that a ≈ b if and
only if a and b have the same parity (both even or both odd).
Equivalence class for an integer 'a' is [a] = {b | a and b have the same
parity}.
This relation partitions the integers into two equivalence classes: even
and odd.
Equivalence in Set Theory:

7
In set theory, an equivalence relation can be defined based on the cardinality
of sets. Two sets A and B are considered equivalent if they have the same
cardinality, denoted as |A| = |B|.
Equivalence class for a set A is the set of all sets that have the same
cardinality as A.
Partial Orders:
Partial orders and their representations in Hasse diagrams are important in
various areas of mathematics, computer science, and other fields for
organizing and studying relationships among elements in a set.
Definition:
A partial order is a relation on a set that possesses three key properties:
 Reflexivity: For all elements a in the set, (a, a) is in the relation. In
other words, every element is related to itself.
 Antisymmetry: If (a, b) and (b, a) are both in the relation, then a must
be equal to b. In other words, there are no distinct elements that are
related in both directions.
 Transitivity: If (a, b) and (b, c) are in the relation, then (a, c) must also
be in the relation. In other words, the relation is transitive.
Posets (Partially Ordered Sets):
A partially ordered set, often abbreviated as "poset," is a set together with a
partial order relation. It is a mathematical structure consisting of:
A non-empty set, denoted as A.
A partial order relation, denoted as ≤ (or another symbol), that satisfies the
three properties of reflexivity, antisymmetry, and transitivity.
Hasse Diagrams to Represent Partial Orders:
A Hasse diagram is a graphical representation of a poset that simplifies the
visualization of the partial order relation. It is a directed acyclic graph (DAG)
where:
Each element of the set corresponds to a node (vertex).
If (a, b) is in the partial order relation and there is no other element 'c' such
that (a, c) and (c, b) are in the relation, then a directed edge (arrow) is drawn
from node 'a' to node 'b.'
Example.
Draw Hasse diagram for ({3, 4, 12, 24, 48, 72}, /)

8
Explanation – According to above given question first, we have to find
the poset for the divisibility.
Let the set is A.
A = {(3 12), (3 24), (3 48), (3 72), (4 12), (4 24), (4 48),
(4 72), (12 24), (12 48), (12 72), (24 48), (24 72)}
So, now the Hasse diagram will be:

In above diagram, 3 and 4 are at same level because they are not
related to each other and they are smaller than other elements in the
set. The next succeeding element for 3 and 4 is 12 i.e, 12 is divisible
by both 3 and 4. Then 24 is divisible by 3, 4 and 12. Hence, it is placed
above 12. 24 divides both 48 and 72 but 48 does not divide 72. Hence
48 and 72 are not joined. We can see transitivity in our diagram as the
level is increasing

Comparability and Upper/Lower Bounds:

In a poset, two elements 'a' and 'b' are said to be comparable if either (a, b)
or (b, a) is in the relation. In other words, they can be compared in terms of
the partial order.
An element 'x' is an upper bound for elements 'a' and 'b' if 'x' is greater than
or equal to both 'a' and 'b' in the partial order, denoted as x ≥ a and x ≥ b.
Similarly, an element 'y' is a lower bound for elements 'a' and 'b' if 'y' is less
than or equal to both 'a' and 'b' in the partial order, denoted as y ≤ a and y
≤ b.
The greatest element in a poset is called the maximal element, and the least
element is called the minimal element.
Example:
Consider the set of positive integers under the relation of divisibility (where
'a' divides 'b'). This forms a partial order, and its Hasse diagram would
represent elements as nodes and directed edges to show divisibility
relationships between numbers.

9
Comparability: In this poset, not all numbers are comparable. For example, 2
and 3 are not comparable because neither divides the other.
Upper Bounds: In this poset, for any two numbers 'a' and 'b,' an upper bound
would be the least common multiple (LCM) of 'a' and 'b.'
Lower Bounds: Similarly, for any two numbers 'a' and 'b,' a lower bound
would be the greatest common divisor (GCD) of 'a' and 'b.'

Real-world examples illustrating sets, relations, equivalence

relations, and partial orders in computer science:
These real-world examples showcase how fundamental mathematical
concepts like sets, relations, equivalence relations, and partial orders are
applied in computer science to model and solve various problems related to
data management, algorithms, and system design.
Sets in Computer Science:
Example: Data Structures

In computer science, sets are used to implement data structures like

arrays and hash tables. An array can be seen as a set of elements with
indices as their positions. A hash table uses sets to store keys and
values, allowing efficient data retrieval.
Relations in Computer Science:
Example: Database Management Systems
In a relational database, tables are used to store data. The
relationships between tables are established using keys and foreign
keys. For instance, in an e-commerce application, there can be a
relation between the "Orders" table and the "Customers" table based
on customer IDs.
Equivalence Relations in Computer Science:
Example: User Authentication
In user authentication systems, equivalence relations are used to
establish user identity. Users are considered equivalent (i.e.,
authenticated) if their provided credentials (e.g., username and
password) match those stored in a database.

10
Partial Orders in Computer Science:
Example: Task Scheduling
In task scheduling algorithms, tasks can be partially ordered based on
dependencies. For example, in a project management software, tasks
may need to be completed in a certain order. This creates a partial
order of tasks, ensuring that dependent tasks are scheduled
accordingly.
Example: CPU Scheduling
In operating systems, processes can be partially ordered based on their
priorities. Higher priority processes are scheduled before lower priority
ones. This partial order helps manage the allocation of CPU time.
Combination of Concepts:
Example: Version Control Systems (VCS)
VCS systems like Git use a combination of sets, relations, equivalence
relations, and partial orders.
 Sets: The set of files or source code changes in a repository.
 Relations: Relations between commits, such as parent-child
relationships.
 Equivalence Relations: Branches and tags in Git can be seen as
equivalence classes of commits, as they represent snapshots of the
repository at specific points in time.
 Partial Orders: Commits can be partially ordered based on their
chronological order, forming a history of changes.
References:
1. Rosen, K. H. (2019). Discrete Mathematics and its Applications.
McGraw-Hill Education. Chapter 1: The Foundations: Logic and Proofs
2. Epp, S. S. (2010). Discrete Mathematics with Applications. Cengage
Learning. Chapter 2: The Fundamentals: Algorithms, the Integers, and
Matrices and Chapter 7: Relations

11