Sets, Relations and Mappings

Introduction

Information technology depends on precise ways of describing collections, associations, classifications and transformations. A database table contains sets of records; a network contains related nodes; a type system classifies values; and a function maps inputs to outputs. Set theory provides the common mathematical language for these activities.

This chapter develops sets, set operations, Cartesian products, relations, equivalence relations, partial orders and mappings. The emphasis is not only on formal definitions but also on their use in databases, data structures, software design and information systems.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Define sets and represent them using roster and set-builder notation.
2. Apply union, intersection, difference, complement and symmetric difference.
3. Use Venn diagrams and cardinality formulas to solve finite-set problems.
4. Construct Cartesian products and interpret ordered pairs.
5. Test whether a relation has properties such as reflexivity, symmetry, antisymmetry and transitivity.
6. Explain equivalence relations, equivalence classes and quotient structures.
7. Explain partial orders and represent them using directed graphs and Hasse diagrams.
8. Distinguish functions from general relations and classify mappings as injective, surjective or bijective.
9. Apply these ideas to databases, classification systems and software models.

1. Sets and Their Representations

A set is a well-defined collection of distinct objects. The objects are called elements or members. If an element x belongs to a set A, we write x ∈ A. If it does not belong to A, we write x ∉ A.

A set can be represented in two standard ways:

• Roster notation: list the elements between braces. For example, A = {2,4,6,8}.
• Set-builder notation: specify a property shared by the elements. For example, A = {x ∈ ℕ | x is even and 2 ≤ x ≤ 8}. The vertical bar means “such that.”

The order of elements does not matter, and repetition does not create a new element. Thus {1,2,3} = {3,1,2} and {1,1,2,3} = {1,2,3}.

Important types of sets include:

• Empty set: ∅, containing no elements.
• Singleton: a set containing exactly one element, such as {a}.
• Finite set: a set with a limited number of elements.
• Infinite set: a set with endlessly many elements, such as the natural numbers.
• Universal set: the set U containing all objects under discussion.
• Subset: A is a subset of B, written A ⊆ B, if every element of A is also in B.
• Proper subset: A ⊂ B means A is a subset of B but A and B are not equal.

Two sets are equal exactly when they contain the same elements. This is called extensional equality. The internal order in which elements are written is irrelevant.

Cardinality

The cardinality of a finite set A, written |A|, is its number of elements. For example, if A = {red, green, blue}, then |A| = 3.

For a set with n elements, the number of all subsets is:

Here, 𝒫(A) is the power set of A. The formula applies to finite sets because each element has two choices in forming a subset: it is either included or excluded. For A = {a,b}, the power set is 𝒫(A) = {∅,{a},{b},{a,b}}, which has 2² = 4 elements.

2. Set Operations

Let A and B be subsets of a universal set U.

Formally,

The words “or” in the definition of union are inclusive: an element belonging to both sets is included once.

Worked Example 1: Basic Operations

Let U = {1,2,3,4,5,6,7,8}, A = {1,2,3,4} and B = {3,4,5,6}. Then:

• A ∪ B = {1,2,3,4,5,6}
• A ∩ B = {3,4}
• A \ B = {1,2}
• B \ A = {5,6}
• A^c = {5,6,7,8}
• A △ B = {1,2,5,6}

A Venn diagram is often useful because overlapping regions represent intersection, while the entire area covered by either circle represents union.

Set Laws

Set operations obey laws analogous to familiar algebraic laws. Important examples are:

The final two identities are De Morgan’s laws. They are especially important in database query conditions and Boolean programming. For example, “not (condition A or condition B)” is equivalent to “not A and not B.”

Cardinality of Unions

For finite sets, the addition rule is:

The subtraction is necessary because elements in the intersection are counted twice when |A| and |B| are added. If A and B are disjoint, A ∩ B = ∅, so the formula reduces to |A ∪ B| = |A| + |B|.

For three finite sets:

This is the inclusion–exclusion principle.

Worked Example 2: Student Enrolment

In a class of 80 students, 45 study programming, thirty study databases, and 18 study both. The number studying at least one of the two subjects is:

|P ∪ D| = 45 + 30 − 18 = 57.

Therefore, 80 − 57 = 23 students study neither subject.

3. Cartesian Products

The Cartesian product of sets A and B is the set of all ordered pairs whose first component comes from A and second component comes from B:

An ordered pair differs from an unordered set: (a,b) = (c,d) exactly when a = c and b = d. Generally, (a,b) ≠ (b,a).

If A and B are finite, then:

For example, if A = {1,2} and B = {x,y,z}, then A × B = {(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)}, containing six pairs. In general, A × B ≠ B × A, although the two products have equal cardinality when A and B are finite.

A product of three sets is written A × B × C and contains ordered triples. Relational database records can be understood as tuples, and tables can be viewed mathematically as subsets of Cartesian products.

4. Relations

A binary relation R from A to B is any subset of A × B. If (a,b) ∈ R, we write aRb and say that a is related to b.

A relation on A is a subset of A × A. Relations can be represented by:

1. A set of ordered pairs.
2. A directed graph, with an arrow from a to b when aRb.
3. A zero–one matrix, where entry m_ij = 1 when the relation holds and 0 otherwise.
4. A database table containing pairs that satisfy a condition.

For example, let A = {1,2,3} and define R by “less than.” Then:

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

The relation is not symmetric because 1R2 but not 2R1.

Properties of Relations

For a relation R on A:

• Reflexive: aRa for every a ∈ A.
• Irreflexive: aRa is false for every a ∈ A.
• Symmetric: If aRb, then bRa.
• Antisymmetric: If aRb and bRa, then a = b. Antisymmetry does not mean that reverse pairs never occur; it means that reverse pairs can occur only when the elements are equal.
• Transitive: If aRb and bRc, then aRc.

These properties are logically independent in many combinations. For instance, “is a sibling of” is commonly symmetric but need not be transitive if half-siblings are included. “Is less than or equal to” is reflexive, antisymmetric and transitive.

5. Equivalence Relations and Classification

An equivalence relation is a relation that is reflexive, symmetric and transitive. Equivalence relations formalize the idea that objects are “the same” with respect to a chosen criterion, even if they are not literally identical.

Example: Congruence Modulo n

For a positive integer n, integers a and b are congruent modulo n if n divides their difference:

The symbol n | (a − b) means that there is an integer k such that a − b = kn. Congruence modulo n is an equivalence relation:

• Reflexive: a − a = 0, and n divides 0.
• Symmetric: if n divides a − b, it also divides b − a.
• Transitive: if n divides a − b and b − c, it divides a − c.

For modulo 3, the equivalence classes are represented by:

[0] = {...,−6,−3,0,3,6,...},

[1] = {...,−5,−2,1,4,7,...}, and

[2] = {...,−4,−1,2,5,8,...}.

Equivalence Classes and Partitions

The equivalence class of a under R is:

Equivalence classes partition A: every element belongs to exactly one class, and distinct classes do not overlap. Conversely, every partition of a set defines an equivalence relation by declaring two elements equivalent when they belong to the same block.

This result is important in computing. If records are grouped by a key, records with the same key form an equivalence class. Deduplication, canonical representations, clustering and user classification all depend on an explicitly chosen notion of equivalence.

6. Partial Orders

A partial order is a relation that is reflexive, antisymmetric and transitive. A set together with a partial order is called a partially ordered set, or poset.

Examples include:

• The relation ≤ on numbers.
• Set inclusion ⊆ on a collection of sets.
• Divisibility on positive integers: aRb when a divides b.
• Dependency relations among software tasks.
• The “is a prerequisite of” relation in a curriculum, after reflexive pairs are included for formal ordering.

Unlike a total order, a partial order permits incomparable elements. For example, under subset inclusion, {1} and {2} are incomparable because neither set contains the other.

Hasse Diagrams

A Hasse diagram represents a finite poset without drawing reflexive loops or edges implied by transitivity. If b covers a, b is placed above a and connected by a line. The diagram is read upward: lower elements precede higher elements.

For the divisors of 12 ordered by divisibility, the elements are 1, 2, 3, 4, 6 and 12. The cover relationships are 1–2, 1–3, 2–4, 2–6, 3–6, 4–12 and 6–12. The relation captures dependency-like structure: a divisor may be reached from another through successive cover steps.

A partial order supports scheduling and dependency analysis. If task A must precede task B, then a topological ordering can produce a valid execution sequence, provided the dependency graph has no cycle. A topological ordering is not necessarily unique because incomparable tasks may be performed in different orders.

7. Mappings and Functions

A mapping or function f from A to B, written f:A→B, assigns each element of A exactly one element of B. A is the domain, B is the codomain, and the set of actual outputs is the range or image of f.

The defining condition is:

A relation can assign several outputs to one input, or no output to an input; such a relation is not a function. A function may assign the same output to several inputs.

Types of Functions

• Injective (one-to-one): distinct inputs have distinct outputs. Formally, f(a₁)=f(a₂) ⇒ a₁=a₂.
• Surjective (onto): every element of the codomain is produced by at least one domain element. Thus range(f)=B.
• Bijective: both injective and surjective.

A function has an inverse function precisely when it is bijective. If f is bijective, f^-1:B→A reverses the mapping and satisfies f^-1(f(a))=a for all a in A and f(f^-1(b))=b for all b in B.

Composition

If f:A→B and g:B→C, their composition is:

The output of f must lie in the domain of g. Composition is associative, meaning h ∘ (g ∘ f) = (h ∘ g) ∘ f, but it is generally not commutative: g ∘ f need not equal f ∘ g.

Worked Example 3: A Finite Mapping

Let A={1,2,3}, B={p,q,r,s}, and define f(1)=p, f(2)=q, f(3)=r. The function is injective because no two inputs share an output. It is not surjective because s is not in the range. Therefore it is not bijective.

If instead the codomain were {p,q,r}, the same rule would be bijective. This illustrates why the codomain matters: surjectivity is determined relative to the stated codomain, not merely by the output values observed in isolation.

8. Applications in Information Technology

Databases

A relation in relational database theory is mathematically a subset of a Cartesian product of domains. A table with attributes StudentID and CourseID can be represented as a set of ordered pairs. A primary key behaves like a function from a row identifier to the remaining attributes, while a foreign key expresses a link between relations.

Relational operations also reflect set operations. A union combines compatible tables, intersection identifies common tuples, and difference identifies tuples in one table but not another. In practice, database systems impose additional requirements, such as schemas, data types, integrity constraints and duplicate-handling conventions.

Data Structures and Graphs

A directed graph is a pair (V,E), where V is a set of vertices and E ⊆ V × V is a relation representing edges. Adjacency lists store related pairs efficiently when the graph is sparse; adjacency matrices store relation membership in a two-dimensional array.

Tree structures often represent partial orders, hierarchical classification or containment. A directed acyclic graph can represent task dependencies, package dependencies or data-processing pipelines.

Classification and Machine Learning

Classification defines a mapping from an object space to a set of labels. If each object receives one label, the classifier is a function. If several labels are allowed, the output is more accurately modeled as a mapping to a power set of labels, such as f:X→𝒫(L). Equivalence classes can describe groups treated identically by a rule, while partitions support segmentation and clustering.

In machine learning, the practical mapping learned from data may be uncertain or probabilistic rather than a strict deterministic function. Therefore, the mathematical model should not hide uncertainty: a probability distribution over labels is different from a single-valued classification mapping.

9. Illustrative Case: Access Control in a University System

Background

Consider an illustrative university information system containing users, roles and permissions. Users may be students, instructors, administrators or technical staff.

Problem

The institution must determine which users may perform actions such as viewing grades, submitting marks, modifying course records or managing accounts. The system must avoid granting permissions accidentally and must support auditing.

Analysis

Let U be the set of users, R the set of roles and P the set of permissions. A role-assignment relation A ⊆ U × R records which users hold which roles. A permission relation G ⊆ R × P records which permissions belong to each role. The effective permission relation can be obtained through composition:

Thus a user receives a permission when the user has a role that grants it. Role inheritance may be modeled as a partial order: an advanced administrative role can dominate a less privileged role, but two specialist roles may be incomparable.

Equivalence relations can support auditing by grouping events with the same transaction identifier. Set difference can identify permissions granted to a user that are not permitted by current policy.

Approach and Solution

The system should define:

1. Explicit sets of users, roles and permissions.
2. A relation for user–role assignment.
3. A relation for role–permission assignment.
4. Constraints preventing unauthorized combinations of roles.
5. A mapping from each audit event to its unique event identifier.
6. Tests for conflicting permissions using set intersection and difference.

For example, if an instructor’s permission set is {viewGrades,submitMarks} and the policy-approved set is {viewGrades,submitMarks,viewRoster}, the missing permission is the set difference {viewRoster}. If a user has both approveMarks and modifyMarks, the intersection of the user’s permissions with a conflict set can trigger review.

Outcome and Learning Points

The model makes authorization rules explicit, testable and auditable. Relations represent assignments, composition propagates permissions, partial orders express role hierarchy, and set operations detect missing or conflicting privileges. The case also demonstrates that formal modeling is valuable before implementation: unclear definitions of roles or permissions lead to ambiguous software behavior.

10. Limitations, Governance and Best Practices

Set-based models are precise, but they do not automatically solve practical issues. Real data may be incomplete, duplicated, inconsistent or time-dependent. A relation describing access today may be invalid tomorrow if a user changes role. Systems therefore need timestamps, versioning and lifecycle rules.

A mathematical relation also does not establish whether a policy is ethical or lawful. In access-control and classification applications, designers should apply least privilege, transparency, auditability, data minimization and appropriate privacy safeguards. Classification systems should be tested for discriminatory effects, especially when labels influence access to education, employment or public services.

Best practices include:

• Define the universal set and the meaning of membership explicitly.
• Distinguish a relation from a function before selecting a data structure.
• State the codomain when claiming that a function is surjective.
• Check relation properties systematically rather than by a few examples.
• Use constraints to preserve keys, referential integrity and valid mappings.
• Use partial orders for dependencies and avoid forcing unrelated items into an artificial total order.
• Document whether data sets permit duplicates, since mathematical sets do not.
• Treat equivalence as criterion-dependent; two records can be equivalent for one purpose and different for another.

Chapter Summary

Sets provide a formal language for collections of objects. Roster and set-builder notation describe membership, while subsets, power sets and cardinality describe structure and size. Union, intersection, difference, complement and symmetric difference support data selection and logical reasoning. Inclusion–exclusion prevents double counting.

Cartesian products create ordered combinations and provide the foundation for relations. A relation is a subset of a Cartesian product and may be represented as pairs, graphs, matrices or database tables. Reflexivity, symmetry, antisymmetry and transitivity characterize important relation types. Equivalence relations partition a set into non-overlapping classes, supporting classification and grouping. Partial orders model hierarchy and dependency without requiring every pair of elements to be comparable.

A mapping assigns each domain element exactly one codomain element. Injective, surjective and bijective mappings describe different forms of correspondence; bijections possess inverse functions. Composition models multi-stage transformations. In IT, these concepts support database design, graph structures, authorization, classification, scheduling and software modeling. Correct applications require clear definitions, suitable constraints, attention to changing data and responsible governance.

Key Terms

Set: A well-defined collection of distinct objects.

Element: An object belonging to a set.

Subset: A set whose every element belongs to another set.

Power set: The set of all subsets of a given set.

Cardinality: The number of elements in a finite set.

Union: The set of elements belonging to at least one of two sets.

Intersection: The set of elements common to two sets.

Complement: Elements in the universal set but not in the specified set.

Cartesian product: The set of ordered pairs formed from two sets.

Relation: A subset of a Cartesian product.

Reflexive: A relation containing every pair (a,a) on its domain.

Symmetric: A relation in which aRb implies bRa.

Antisymmetric: A relation in which mutual relatedness implies equality.

Transitive: A relation in which aRb and bRc imply aRc.

Equivalence relation: A reflexive, symmetric and transitive relation.

Equivalence class: The set of elements equivalent to a specified element.

Partial order: A reflexive, antisymmetric and transitive relation.

Function: A relation assigning exactly one output to every input.

Bijection: A function that is both injective and surjective.

Composition: The function formed by applying one function after another.

Review Questions

5 Short Answer Questions

1. What is the difference between a subset and a proper subset?
2. Define the Cartesian product A × B.
3. State the four defining properties of an equivalence relation and a partial order.
4. What is the difference between the range and codomain of a function?
5. Why is the subtraction term needed in the formula for |A ∪ B|?

5 Long Answer Questions

1. Explain the principal set operations and illustrate each with a suitable example.
2. Describe three representations of a relation and discuss when each representation is useful in IT.
3. Explain equivalence classes and show how they produce a partition of a set.
4. Compare equivalence relations, partial orders and total orders, giving one computing example of each.
5. Explain injective, surjective and bijective functions, including the relationship between bijections and inverse functions.

3 Analytical / Application Questions

1. A university records students enrolled in programming and databases. Design sets and use inclusion–exclusion to determine how many students study at least one subject and neither subject, using your own realistic data.
2. Model a software build system as a directed relation on tasks. Identify conditions under which the relation represents a partial order, and explain how a valid execution sequence could be obtained.
3. Design a role-based access-control model using sets and relations. Explain how composition, difference and intersection could detect inherited permissions, missing permissions and conflicting permissions.

Multiple Choice Questions with Answers

Question 1

If A = {1,2,3} and B = {3,4,5}, what is A ∩ B?

A. {1,2}

B. {3}

C. {1,2,3,4,5}

D. {4,5}

Correct Answer: B. {3}

Question 2

If |A| = 4 and |B| = 3, what is |A × B|?

A. 7

B. 12

C. 64

D. 1

Correct Answer: B. 12

Question 3

Which properties define an equivalence relation?

A. Reflexive, symmetric and transitive

B. Reflexive, antisymmetric and transitive

C. Symmetric, antisymmetric and irreflexive

D. Injective, surjective and transitive

Correct Answer: A. Reflexive, symmetric and transitive

Question 4

A relation R is antisymmetric when:

A. aRb always implies bRa

B. aRb and bRa imply a = b

C. aRb and bRc imply aRc

D. aRa is false for every a

Correct Answer: B. aRb and bRa imply a = b

Question 5

If |A| = 20, |B| = 15 and |A ∩ B| = 5, what is |A ∪ B|?

A. 30

B. 35

C. 40

D. 300

Correct Answer: A. 30

Question 6

A function is surjective when:

A. Every input has exactly two outputs

B. Different inputs always have different outputs

C. Every element of the codomain is the image of at least one input

D. Its domain and codomain are empty

Correct Answer: C. Every element of the codomain is the image of at least one input

Question 7

Which relation is a partial order?

A. “Is a sibling of”

B. “Is less than or equal to” on numbers

C. “Is not equal to”

D. “Has the same age as”

Correct Answer: B. “Is less than or equal to” on numbers

Question 8

How many subsets does a finite set with five elements have?

A. 5

B. 10

C. 25

D. 32

Correct Answer: D. 32

Question 9

A bijective function is:

A. Only injective

B. Only surjective

C. Both injective and surjective

D. Neither injective nor surjective

Correct Answer: C. Both injective and surjective

Question 10

In a role-based access-control model, composing user–role and role–permission relations identifies:

A. Users who have permissions through assigned roles

B. Only roles with no permissions

C. The complement of every user set

D. Users who have no role assignment

Correct Answer: A. Users who have permissions through assigned roles