8/11/26, 11:01 AM Course Outline Generation

CHAPTER FOUR: SETS, RELATIONS AND FUNCTIONS

Programmes: Bachelor of Science in Software Engineering (BSWE) / Bachelor of Computer Science
(BCS)
Lecturer: Dr. Engr. Tuhame William
Level: Bachelor’s Degree

4.0 INTRODUCTION
Sets, relations and functions are fundamental mathematical structures used throughout computer
science and software engineering. They provide the mathematical language required to describe
collections of data, relationships between objects, mappings between inputs and outputs, and
transformations performed by computational systems.

A database table, for example, can be viewed as a collection of records. Relationships between
database entities can be represented using mathematical relations, while functions can model
transformations such as:

f (x) = 2x + 1

where each input x produces a corresponding output.

Sets, relations and functions are therefore important in:

Database management systems

Data structures
Algorithms
Programming
Artificial intelligence
Discrete mathematics
Graph theory
Software modelling
Information systems
Formal methods
This chapter develops these concepts systematically and demonstrates their applications to
computing.

4.1 CHAPTER LEARNING OBJECTIVES

By the end of this chapter, students should be able to:
1. Define a set and explain its basic properties.
2. Represent sets using different methods.
3. Perform operations on sets.
4. Apply set laws to simplify expressions.

[Link] 1/34
8/11/26, 11:01 AM Course Outline Generation

5. Explain Cartesian products.

6. Define relations and identify their properties.
7. Represent relations using matrices, tables and directed graphs.
8. Define equivalence relations and partial orders.
9. Define functions and distinguish functions from general relations.
10. Determine whether a function is injective, surjective or bijective.
11. Perform function composition.
12. Apply sets, relations and functions to computing problems.

4.2 SETS
4.2.1 Meaning of a Set
A set is a well-defined collection of distinct objects.

The objects belonging to a set are called elements or members.

For example:

A = {1, 2, 3, 4, 5}

The elements of A are:

1, 2, 3, 4, 5

We write:

2∈A
to mean:

2 is an element of A.

If an object is not a member of a set, we write:

7 ∈/ A

4.2.2 Well-Defined Sets

A collection is well-defined if it is possible to determine clearly whether an object belongs to the
collection.

Well-defined

A = {2, 4, 6, 8, 10}

It is clear whether a number belongs to A.

[Link] 2/34
8/11/26, 11:01 AM Course Outline Generation

Not well-defined

The set of beautiful computers.

The term "beautiful" is subjective and therefore does not clearly define membership.

4.2.3 Ways of Representing Sets

There are three common methods.

1. Roster or Tabular Form

Elements are listed explicitly.

A = {1, 2, 3, 4, 5}

2. Set-Builder Form
A property defining the elements is provided.

A = {x ∣ x is a positive integer less than 6}

3. Descriptive Form
The set is described using words.

A is the set of positive integers less than 6.

4.2.4 Types of Sets

Empty Set
A set containing no elements is called the empty set.

Symbol:

∅ ​

or:

{}
Example:

A = {x ∈ N : x < 0}

Then:

A=∅
[Link] 3/34
8/11/26, 11:01 AM Course Outline Generation

Singleton Set
A set containing exactly one element is called a singleton.

Example:

A = {7}

Finite Set
A set containing a finite number of elements.

Example:

A = {a, b, c, d}

Infinite Set
A set containing infinitely many elements.

Example:

N = {1, 2, 3, 4, …}

4.2.5 Cardinality of a Set

The cardinality of a set is the number of elements it contains.

It is written:

∣A∣
If:

A = {2, 4, 6, 8}
then:

∣A∣ = 4 ​

Important Point
Repeated elements are counted only once.

For:

A = {1, 2, 2, 3, 3, 3}
[Link] 4/34
8/11/26, 11:01 AM Course Outline Generation

we have:

A = {1, 2, 3}
Therefore:

∣A∣ = 3

4.3 SUBSETS
Set A is a subset of set B if every element of A is also an element of B .

We write:

A⊆B ​

Example
Let:

A = {1, 2}
and:

B = {1, 2, 3, 4}
Then:

A⊆B

because every element of A belongs to B .

4.3.1 Proper Subset

If:

A⊆B
and:

A=B

then A is a proper subset of B .

It is commonly represented as:

A⊂B

[Link] 5/34
8/11/26, 11:01 AM Course Outline Generation

4.3.2 Power Set

The power set of A, denoted:

P(A)

is the set containing all subsets of A.

Suppose:

A = {1, 2}
The subsets are:

∅, {1}, {2}, {1, 2}

Therefore:

P(A) = {∅, {1}, {2}, {1, 2}} ​

If:

∣A∣ = n
then:

∣P(A)∣ = 2n ​

For A = {1, 2}:

22 = 4
subsets exist.

4.4 SET OPERATIONS

The main set operations are:
1. Union
2. Intersection
3. Difference
4. Complement
5. Symmetric difference

4.4.1 Union
The union of A and B contains all elements that belong to A, B , or both.

[Link] 6/34
8/11/26, 11:01 AM Course Outline Generation

Symbol:

A∪B ​

Example
Let:

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}
Then:

A ∪ B = {1, 2, 3, 4, 5, 6}

4.4.2 Intersection
The intersection contains elements common to both sets.

Symbol:

A∩B ​

Using the same sets:

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}
Therefore:

A ∩ B = {3, 4} ​

4.4.3 Set Difference

The difference:

A−B

contains elements belonging to A but not to B .

Using the previous example:

A − B = {1, 2}
while:

B − A = {5, 6}
[Link] 7/34
8/11/26, 11:01 AM Course Outline Generation

Therefore, in general:

A−B =B−A

4.4.4 Complement
Suppose U is the universal set.

The complement of A contains all elements in U that are not in A.

It is represented as:

Ac
or:

A
Example
Let:

U = {1, 2, 3, 4, 5, 6}
and:

A = {1, 3, 5}
Then:

Ac = {2, 4, 6} ​

4.4.5 Symmetric Difference

The symmetric difference contains elements belonging to either A or B , but not both.

It can be written:

A△B
and:

A△B = (A − B) ∪ (B − A)

For:

A = {1, 2, 3}

B = {3, 4, 5}

[Link] 8/34
8/11/26, 11:01 AM Course Outline Generation

we obtain:

A△B = {1, 2, 4, 5}

4.5 WORKED EXAMPLE 1: SET OPERATIONS

Let:

A = {1, 2, 3, 4, 5}

B = {4, 5, 6, 7, 8}

Find:

a) A ∪ B

{1, 2, 3, 4, 5, 6, 7, 8} ​

b) A ∩ B

{4, 5} ​

c) A − B

{1, 2, 3} ​

d) B −A

{6, 7, 8} ​

4.6 SET LAWS

Set operations obey mathematical laws similar to logical operations.

4.6.1 Commutative Laws

A∪B = B∪A

A∩B =B∩A

4.6.2 Associative Laws

(A ∪ B) ∪ C = A ∪ (B ∪ C)

[Link] 9/34
8/11/26, 11:01 AM Course Outline Generation

(A ∩ B) ∩ C = A ∩ (B ∩ C)

4.6.3 Distributive Laws

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
and:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

4.6.4 De Morgan's Laws for Sets

The first law is:

(A ∪ B)c = Ac ∩ B c ​

The second is:

(A ∩ B)c = Ac ∪ B c ​

These laws are closely related to De Morgan's laws in propositional logic.

4.7 INCLUSION-EXCLUSION PRINCIPLE

For two finite sets:

∣A ∪ B∣ = ∣A∣ + ∣B∣ − ∣A ∩ B∣ ​

The intersection is subtracted because its elements are initially counted twice.

Worked Example 2
Suppose a class has:
40 students studying Java;
30 studying Python;
15 studying both.
How many students study at least one of the two languages?

Let:

∣J∣ = 40

∣P ∣ = 30

∣J ∩ P ∣ = 15
[Link] 10/34
8/11/26, 11:01 AM Course Outline Generation

Then:

∣J ∪ P ∣ = 40 + 30 − 15

= 55
Therefore:

55 students

study at least one of the two languages.

4.8 CARTESIAN PRODUCTS

The Cartesian product of sets A and B is the set of all ordered pairs where the first element comes
from A and the second from B .

It is written:

A×B ​

Example
Let:

A = {1, 2}

B = {a, b}
Then:

A × B = {(1, a), (1, b), (2, a), (2, b)}

Notice that:

(1, a) = (a, 1)
because ordered pairs consider position.

4.8.1 Cardinality of Cartesian Product

If:

∣A∣ = m

and:

∣B∣ = n
then:
[Link] 11/34
8/11/26, 11:01 AM Course Outline Generation

∣A × B∣ = mn ​

For the previous example:

∣A∣ = 2, ∣B∣ = 2
Therefore:

∣A × B∣ = 2(2) = 4

4.9 APPLICATION OF CARTESIAN PRODUCTS IN COMPUTING

Suppose:

U sers = {U1 , U2 , U3 }
​ ​ ​

and:

Resources = {R1 , R2 } ​ ​

Then:

U sers × Resources

represents all possible user-resource pairs.

This can be used to model:

Access-control relationships
User permissions
Database relationships
Network connections
Assignment problems
For example:

(U1 , R1 )
​ ​

may mean:

User U1 has access to resource R1 .

​ ​

4.10 RELATIONS
4.10.1 Meaning of a Relation
A relation describes a relationship between elements of sets.

[Link] 12/34
8/11/26, 11:01 AM Course Outline Generation

A relation R from A to B is a subset of:

A×B
Therefore:

R⊆A×B ​

4.10.2 Worked Example 3

Let:

A = {1, 2, 3}

and:

B = {2, 4, 6}
Define:

R = {(1, 2), (2, 4), (3, 6)}

Then:

R⊆A×B

because every ordered pair in R belongs to A × B .

The relation could represent:

y = 2x

4.11 REPRESENTING RELATIONS

Relations can be represented in several ways:
1. Ordered pairs
2. Tables
3. Matrices
4. Directed graphs
5. Arrow diagrams

4.11.1 Relation as Ordered Pairs

Example:

R = {(1, 2), (2, 3), (3, 4)}

[Link] 13/34
8/11/26, 11:01 AM Course Outline Generation

4.11.2 Relation as a Table

Student Course

John Mathematics

Mary Programming

Peter Databases

This represents a relationship:

Student → Course

4.11.3 Relation as a Matrix

Suppose:

A = {1, 2, 3}
and:

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

The relation matrix is:

1 2 3

1 1 1 0

2 0 0 1

3 0 0 1

A value of 1 indicates that the corresponding ordered pair belongs to R.

A value of 0 means it does not.

4.12 PROPERTIES OF RELATIONS

For a relation R defined on a set A, important properties include:
1. Reflexivity
2. Symmetry
3. Antisymmetry
4. Transitivity

[Link] 14/34
8/11/26, 11:01 AM Course Outline Generation

4.12.1 Reflexive Relation

A relation R on A is reflexive if:

∀a ∈ A, (a, a) ∈ R ​

Every element must be related to itself.

Example
The equality relation:

R = {(a, a) : a ∈ A}
is reflexive.

4.12.2 Symmetric Relation

A relation is symmetric if:

aRb ⇒ bRa ​

If a is related to b, then b must be related to a.

Example

Is a classmate of

If:

John is a classmate of Mary,

then:

Mary is a classmate of John.

Therefore, the relation is symmetric.

4.12.3 Antisymmetric Relation

A relation is antisymmetric if:

aRb ∧ bRa ⇒ a = b

Example
The relation:
[Link] 15/34
8/11/26, 11:01 AM Course Outline Generation

≤
is antisymmetric.

If:

a≤b
and:

b≤a

then:

a=b

4.12.4 Transitive Relation

A relation is transitive if:

aRb ∧ bRc ⇒ aRc

Example
The relation ≤ is transitive.

If:

a≤b

and:

b≤c
then:

a≤c

4.13 EQUIVALENCE RELATIONS

A relation is an equivalence relation if it is:
1. Reflexive
2. Symmetric
3. Transitive

Example
Consider the relation:

[Link] 16/34
8/11/26, 11:01 AM Course Outline Generation

Has the same birthday as.

It is:
Reflexive: everyone has the same birthday as themselves.
Symmetric: if A has the same birthday as B, B has the same birthday as A.
Transitive: if A has the same birthday as B and B has the same birthday as C, A has the same
birthday as C.
Therefore, it is an equivalence relation.

4.14 PARTIAL ORDER RELATIONS

A relation is a partial order if it is:
1. Reflexive
2. Antisymmetric
3. Transitive
A set together with a partial order is called a partially ordered set, or poset.

A common example is:

⊆
on a collection of sets.

For example:

{1} ⊆ {1, 2}
and:

{1, 2} ⊆ {1, 2, 3}

therefore:

{1} ⊆ {1, 2, 3}

4.15 FUNCTIONS
4.15.1 Meaning of a Function
A function is a special type of relation in which every input has exactly one output.

A function from A to B is written:

f :A→B ​

This means that f maps elements of A to elements of B .

[Link] 17/34
8/11/26, 11:01 AM Course Outline Generation

4.15.2 Function Terminology

Consider:

f :A→B
where:
A = domain
B = codomain
f (A) = range or image

Example

f (x) = 2x
If:

A = {1, 2, 3}
then:

f (1) = 2

f (2) = 4

f (3) = 6
Therefore:

Range = {2, 4, 6}

4.15.3 Function versus Relation

Every function is a relation, but not every relation is a function.

Function

{(1, a), (2, b), (3, c)}

Each input has exactly one output.

Not a Function

{(1, a), (1, b), (2, c)}

Input 1 has two outputs:

a, b
[Link] 18/34
8/11/26, 11:01 AM Course Outline Generation

Therefore, this is not a function.

4.16 TYPES OF FUNCTIONS

Three important types are:
1. Injective
2. Surjective
3. Bijective

4.16.1 Injective Function

A function is injective or one-to-one if different inputs produce different outputs.

Formally:

f (a) = f (b) ⇒ a = b

Example

f (x) = 2x
is injective over the real numbers.

If:

2a = 2b

then:

a=b

4.16.2 Surjective Function

A function is surjective or onto if every element of the codomain has at least one corresponding
input.

Example
Suppose:

A = {1, 2, 3}

B = {a, b, c}
and:

f (1) = a, f (2) = b, f (3) = c

[Link] 19/34
8/11/26, 11:01 AM Course Outline Generation

Every element of B is reached.

Therefore, f is surjective.

4.16.3 Bijective Function

A function is bijective if it is both:
Injective
Surjective
Therefore:

Bijective = Injective + Surjective ​

A bijective function establishes a one-to-one correspondence between two sets.

4.17 WORKED EXAMPLE 4: CLASSIFYING A FUNCTION

Let:

A = {1, 2, 3}

B = {a, b, c}
and:

f = {(1, a), (2, b), (3, c)}

Is it a function?
Yes. Every input has exactly one output.

Is it injective?
Yes. No two inputs have the same output.

Is it surjective?
Yes. Every element of B is used.

Therefore:

f is bijective ​

4.18 FUNCTION COMPOSITION

If:

[Link] 20/34
8/11/26, 11:01 AM Course Outline Generation

f :A→B
and:

g:B→C
then their composition is:

g ∘f ​

and:

(g ∘ f )(x) = g(f (x))

The function f is applied first, followed by g .

4.18.1 Worked Example 5

Let:

f (x) = 2x + 1
and:

g(x) = x2

Find:

(g ∘ f )(x)

Step 1

f (x) = 2x + 1

Step 2
Substitute into g :

g(f (x)) = (2x + 1)2

Therefore:

(g ∘ f )(x) = (2x + 1)2 ​

Expanding:

= 4x2 + 4x + 1

[Link] 21/34
8/11/26, 11:01 AM Course Outline Generation

4.19 INVERSE FUNCTIONS

A function f has an inverse f −1 if the mapping can be reversed.

For a bijective function:

f −1 : B → A

Example
Let:

f (x) = 2x + 3

Set:

y = 2x + 3

Solve for x:

y − 3 = 2x
y−3
x=
2
​

Therefore:

x−3
f −1 (x) =
2
​ ​

4.20 APPLICATIONS IN COMPUTING

4.20.1 Databases
A database can be viewed as a collection of sets.

For example:

Students
may be a set of student records.

A relationship can connect:

Students × Courses

This mathematical model underlies relational database concepts.

4.20.2 Data Structures

[Link] 22/34
8/11/26, 11:01 AM Course Outline Generation

Sets are useful when modelling:

Unique values
Membership
Search spaces
Collections of objects
For example, a programming language may provide a set data structure that automatically prevents
duplicate values.

4.20.3 Access Control

Let:

U sers = {U1 , U2 , U3 }
​ ​ ​

and:

Resources = {R1 , R2 , R3 } ​ ​

Then a relation:

Access ⊆ U sers × Resources

can specify which users can access which resources.

4.20.4 Programming Functions

A programming function can be viewed mathematically as:

f : Input → Output
For example:

calculateArea(radius)

can be modelled as:

f (r) = πr2
Each valid radius produces one corresponding area.

4.20.5 Algorithms
Functions can represent transformations performed by algorithms.

For example:

f (x) = x2
[Link] 23/34
8/11/26, 11:01 AM Course Outline Generation

maps an input number to its square.

An algorithm can therefore be analysed as a mapping from:

Input → Output

4.21 INTEGRATED COMPUTING EXAMPLE

Student-Course Registration System
Suppose:

S = {John, M ary, P eter}

and:

C = {P rogramming, Databases, N etworks}

A registration relation can be:

R = {(John, P rogramming), (John, Databases), (M ary, N etworks), (P eter, P rogramming)

 

This means:
John registered for Programming.
John registered for Databases.
Mary registered for Networks.
Peter registered for Programming.
Notice that this is a relation, not necessarily a function, because one student can register for
multiple courses.

For example:

(John, P rogramming)
and:

(John, Databases)
both exist.

Thus, one input has multiple outputs.

4.22 CLASSROOM EXERCISES

Exercise 1
Given:

[Link] 24/34
8/11/26, 11:01 AM Course Outline Generation

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}
Find:
1. A∪B
2. A ∩ B
3. A − B
4. B − A

Answers

A ∪ B = {1, 2, 3, 4, 5, 6}

A ∩ B = {3, 4}

A − B = {1, 2}

B − A = {5, 6}

Exercise 2
Let:

A = {a, b, c}
Find:

P(A)

Answer

P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} ​

There are:

23 = 8
subsets.

Exercise 3
Let:

A = {1, 2}

B = {x, y, z}
[Link] 25/34
8/11/26, 11:01 AM Course Outline Generation

Find:

A×B

Answer

{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)} ​

Exercise 4: Relations
Let:

A = {1, 2, 3}
and:

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

Determine whether R is:

1. Reflexive
2. Symmetric
3. Antisymmetric
4. Transitive
Students should justify each answer.

Exercise 5: Functions
Determine whether each relation is a function.

a)

{(1, a), (2, b), (3, c)}

b)

{(1, a), (1, b), (2, c)}

Answers
a) Function.

b) Not a function because input 1 has two outputs.

Exercise 6: Function Composition

[Link] 26/34
8/11/26, 11:01 AM Course Outline Generation

Given:

f (x) = x + 2
and:

g(x) = 3x
Find:
1. g ∘f
2. f ∘ g

Solution

(g ∘ f )(x) = g(x + 2)

= 3(x + 2)

3x + 6 ​

For:

(f ∘ g)(x) = f (3x)

= 3x + 2
Therefore:

f ∘ g = 3x + 2 ​

Notice that:

g ∘f = f ∘g

in general.

4.23 CLASS ACTIVITIES

Activity 1: University Database
Create the following sets:

Students

Courses

Lecturers
Then create relations representing:
Student-course registration
[Link] 27/34
8/11/26, 11:01 AM Course Outline Generation

Lecturer-course teaching
Student-examination participation
Students should identify whether each relationship is a function or a general relation and explain
why.

Activity 2: Access-Control Modelling

Let:

U sers = {U1 , U2 , U3 , U4 }
​ ​ ​ ​

and:

Resources = {R1 , R2 , R3 }
​ ​

Create a relation:

Access ⊆ U sers × Resources

representing an access-control system.

Students should:

1. List the ordered pairs.

2. Draw an arrow diagram.
3. Construct a relation matrix.
4. Determine whether the relation is a function.
5. Explain why or why not.

4.24 ASSIGNMENT TASKS — CHAPTER FOUR

Assignment 1: Set Theory
Answer the following:
1. Define a set.
2. Explain what is meant by a well-defined set.
3. Explain roster notation.
4. Explain set-builder notation.
5. Define an empty set.
6. Define a singleton set.
7. Define a finite set.
8. Define an infinite set.
9. Explain cardinality.
10. Explain the difference between a subset and a proper subset.

[Link] 28/34
8/11/26, 11:01 AM Course Outline Generation

Assignment 2: Set Operations

Given:

A = {1, 2, 3, 4, 5, 6}

B = {4, 5, 6, 7, 8}
Find:
1. A∪B
2. A∩B
3. A−B
4. B−A
5. A△B

Assignment 3: Power Sets

Find the power set of:

a)

A = {1, 2}

b)

B = {a, b, c}

c)

C = {x, y, z, w}
Also determine the number of subsets using:

2n

Assignment 4: Cartesian Products

Let:

A = {1, 2, 3}

B = {a, b}

Tasks
1. Find A × B .

[Link] 29/34
8/11/26, 11:01 AM Course Outline Generation

2. Find B
× A.
3. Compare A × B and B × A.
4. Determine their cardinalities.
5. Explain why ordered pairs are important in computing.

Assignment 5: Relations
Let:

A = {1, 2, 3}

and:

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

Determine whether R is:

1. Reflexive
2. Symmetric
3. Antisymmetric
4. Transitive
5. An equivalence relation
Give reasons for every answer.

Assignment 6: Functions
Consider:

f (x) = 3x + 2

Tasks
1. Find f (0).
2. Find f (1).
3. Find f (5).
4. Find f (−2).
5. Determine whether f is injective over the real numbers.
6. Determine whether f has an inverse.
7. Find f −1 (x).

Assignment 7: Computing Application

A university has the following sets:

[Link] 30/34
8/11/26, 11:01 AM Course Outline Generation

Students = {S1 , S2 , S3 , S4 } ​ ​ ​ ​

Courses = {C1 , C2 , C3 } ​ ​ ​

The registration information is:

R = {(S1 , C1 ), (S1 , C2 ), (S2 , C1 ), (S3 , C3 ), (S4 , C2 )}

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Tasks
1. Explain what each ordered pair means.
2. Determine the students registered for C1 . ​

3. Determine the courses registered for by S1 . ​

4. Represent R as a table.
5. Represent R using a matrix.
6. Determine whether R is a function from Students to Courses.
7. Explain your answer.

Assignment 8: Software Engineering Application

Develop a mathematical model for a simple user-role-permission system.

Define:

U sers

Roles

P ermissions
Then:
1. Define the three sets.
2. Define a relation between users and roles.
3. Define a relation between roles and permissions.
4. Give at least five sample ordered pairs.
5. Explain whether either relation is a function.
6. Explain how the model could be implemented in a relational database.
7. Discuss how the mathematical model could support access-control software.

4.25 CHAPTER REVISION QUESTIONS

1. What is a set?
2. What is an element?
3. Explain set notation.
4. Define an empty set.
[Link] 31/34
8/11/26, 11:01 AM Course Outline Generation

5. Define a finite set.

6. Define an infinite set.
7. What is cardinality?
8. Define a subset.
9. Define a power set.
10. What is union?
11. What is intersection?
12. What is set difference?
13. What is complement?
14. Explain symmetric difference.
15. State the inclusion-exclusion principle.
16. Define Cartesian product.
17. What is a relation?
18. How is a relation different from a function?
19. Explain reflexivity.
20. Explain symmetry.
21. Explain antisymmetry.
22. Explain transitivity.
23. What is an equivalence relation?
24. What is a partial order?
25. Define a function.
26. What is the domain of a function?
27. What is the codomain?
28. What is the range?
29. Define an injective function.
30. Define a surjective function.
31. Define a bijective function.
32. Explain function composition.
33. Explain inverse functions.
34. Explain the application of sets in databases.
35. Explain the application of relations in access-control systems.
36. Explain the importance of functions in programming.
37. Explain how Cartesian products can model database relationships.
38. Determine whether a given relation is a function.
39. Determine whether a given function is injective or surjective.
40. Explain why sets, relations and functions are important in computer science.

4.26 KEY FORMULAS TO REMEMBER

Cardinality

[Link] 32/34
8/11/26, 11:01 AM Course Outline Generation

∣A∣ ​

Power Set

∣P(A)∣ = 2∣A∣ ​

Union

A∪B ​

Intersection

A∩B ​

Difference

A−B ​

Complement

Ac ​

Cartesian Product

A×B ​

Cardinality of Cartesian Product

∣A × B∣ = ∣A∣∣B∣ ​

Inclusion-Exclusion

∣A ∪ B∣ = ∣A∣ + ∣B∣ − ∣A ∩ B∣ ​

Relation

R⊆A×B ​

Function

f :A→B ​

Function Composition

(g ∘ f )(x) = g(f (x)) ​

[Link] 33/34
8/11/26, 11:01 AM Course Outline Generation

Bijective Function

Bijective = Injective + Surjective ​

4.27 CHAPTER SUMMARY

This chapter introduced sets, relations and functions, three fundamental mathematical structures
in computer science.

A set represents a collection of objects, while operations such as union, intersection, difference and
complement allow collections to be manipulated mathematically.

A relation describes an association between elements of sets:

R⊆A×B
Relations can be represented using ordered pairs, tables, matrices and directed graphs. Important
properties include:

Reflexive, Symmetric, Antisymmetric, Transitive ​

A relation that is reflexive, symmetric and transitive is an equivalence relation, while one that is
reflexive, antisymmetric and transitive is a partial order.

A function is a special relation where each input has exactly one output:

f :A→B
Functions can be classified as injective, surjective or bijective, and functions can be combined
through composition:

(g ∘ f )(x) = g(f (x))

These concepts provide an essential mathematical foundation for databases, data structures,
algorithms, programming, access-control systems and software modelling.

The next chapter can build on these ideas through Chapter Five: Combinatorics, Counting and
Discrete Structures, introducing permutations, combinations, counting principles, recurrence
relations and their applications to algorithmic problem solving.

[Link] 34/34