Sets, Relations and Functions

Introduction

Sets, relations and functions provide the mathematical vocabulary used to describe collections, associations and transformations. In computer science, a database table represents a finite relation; an access-control system composes user–role and role–permission relations; a type specification defines sets of valid values; and an algorithm can be modeled as a function from inputs to outputs.

These abstractions support precise reasoning about correctness, duplication, reachability, ordering, data integration and computational size. They are therefore foundational to database design, software specification, algorithms, programming languages and artificial intelligence.

Learning Objectives

After studying this chapter, students should be able to:

• represent collections using sets and set-builder notation;
• apply set operations and algebraic laws;
• construct Cartesian products and interpret tuples;
• identify and analyze important properties of relations;
• distinguish equivalence relations from order relations;
• represent finite partial orders correctly using strict-order graphs and Hasse diagrams;
• classify functions as injective, surjective or bijective;
• compose relations and functions in the correct order;
• calculate finite cardinalities and compare infinite cardinalities;
• determine whether common sets are countable;
• apply these concepts to databases, specifications and access-control systems.

1. Sets and Membership

A set is a well-defined collection of distinct objects. The objects are its elements or members. If object x belongs to set A, write x ∈ A; otherwise write x ∉ A.

Sets may be described extensionally by listing their elements:

A = {2, 4, 6, 8}

or intensionally by specifying a property:

A = {x ∈ ℕ | x is even and 2 ≤ x ≤ 8}.

Order and repetition do not affect a set. Thus {1,2,2,3} = {3,2,1}. The empty set, written ∅, has no elements.

1.1 Subsets and equality

A set A is a subset of B, written A ⊆ B, when every member of A belongs to B:

Set equality follows from mutual inclusion:

A proper subset, written A ⊂ B, satisfies A ⊆ B and A ≠ B. Every set is a subset of itself, and ∅ is a subset of every set.

The power set 𝒫(A) is the set of all subsets of A. If A = {a,b}, then

𝒫(A) = {∅,{a},{b},{a,b}}.

For a finite set containing n elements:

Each element has two independent possibilities—present or absent—in a subset.

2. Set Operations and Laws

For sets A and B within a universe U, the main operations are:

The universe must be stated when complements are used. Without a universe, A^c is ambiguous.

2.1 Algebra of sets

Important identities include:

• Commutativity: A ∪ B = B ∪ A and A ∩ B = B ∩ A.
• Associativity: (A ∪ B) ∪ C = A ∪ (B ∪ C), with an analogous law for intersection.
• Distributivity: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
• Identity: A ∪ ∅ = A and A ∩ U = A.
• Complement: A ∪ A^c = U and A ∩ A^c = ∅.
• Absorption: A ∪ (A ∩ B) = A.
• De Morgan’s laws:

These laws permit logical and database queries to be rewritten without changing their meaning.

Worked Example 1: Software test coverage

Let U contain 100 program requirements. Suppose test suite A covers 68 requirements, suite B covers 57, and both cover 35. The number covered by at least one suite is found using inclusion–exclusion:

Here, all cardinalities are dimensionless counts:

|A ∪ B| = 68 + 57 − 35 = 90.

Therefore, 100 − 90 = 10 requirements are uncovered. Simply adding 68 and 57 would count the 35 shared requirements twice.

For three finite sets, inclusion–exclusion becomes:

The final term restores elements subtracted too many times.

3. Cartesian Products and Tuples

The Cartesian product of sets A and B is

An ordered pair differs from a set: generally, (a,b) ≠ (b,a). Equality holds precisely when corresponding components are equal.

If |A| = m and |B| = n are finite, then

For example, three users and four resources produce 3 × 4 = 12 possible user–resource pairs.

The product may be extended to multiple sets:

A₁ × A₂ × ⋯ × A_k,

whose elements are ordered k-tuples. A database row with attributes StudentID, Course and Grade can be viewed as an element of an appropriate three-set product. A valid database table is usually a constrained subset of that product rather than the entire product.

4. Binary Relations

A binary relation R from A to B is any subset of A × B. If (a,b) ∈ R, one may write aRb. A relation on A is a subset of A × A.

The domain, range and inverse are:

Relations can be represented as sets of ordered pairs, Boolean matrices, directed graphs or database tables.

4.1 Composition of relations

Let R ⊆ A × B and S ⊆ B × C. Their composition is

The rightmost relation is applied first. Composition is associative when the domains and codomains are compatible, but it is generally not commutative.

For role-based access control, let:

• assigns ⊆ U × ℛ associate users in U with roles in ℛ;
• grants ⊆ ℛ × P associate roles with permissions in P.

Then the effective user–permission relation is correctly given by

A pair (u,p) belongs to effective exactly when some role r satisfies (u,r) ∈ assigns and (r,p) ∈ grants.

4.2 Properties of relations

For a relation R on set A:

Symmetry and antisymmetry are not opposites. Equality is both symmetric and antisymmetric. Asymmetry, however, implies irreflexivity and antisymmetry.

4.3 Closures

A closure minimally adds pairs needed to obtain a desired property:

• reflexive closure: R ∪ I_A, where I_A = {(a,a) | a ∈ A};
• symmetric closure: R ∪ R⁻¹;
• transitive closure: R^+, containing pairs connected by paths of one or more edges;
• reflexive–transitive closure: R^* = I_A ∪ R^+.

In program analysis, if R represents one execution step, then R^* represents execution in zero or more steps. Algorithms such as Warshall’s algorithm compute transitive closure for finite relations represented by Boolean matrices.

5. Equivalence Relations and Partitions

An equivalence relation is reflexive, symmetric and transitive. It formalizes when objects are considered identical under a chosen criterion.

For a ∈ A, the equivalence class of a is

Example: Congruence modulo 3

Define a ≡ b (mod 3) when 3 divides a−b. This is an equivalence relation on ℤ. It creates three classes:

• [0] for integers with remainder 0;
• [1] for integers with remainder 1;
• [2] for integers with remainder 2.

A partition of a set is a collection of nonempty, pairwise disjoint subsets whose union is the original set. Every equivalence relation induces a partition into equivalence classes. Conversely, every partition induces an equivalence relation: two elements are related exactly when they occupy the same block.

This correspondence supports data deduplication. Records judged equivalent under a carefully designed matching rule can be grouped into candidate entity clusters. In practice, approximate matching may fail transitivity, so it should not automatically be treated as an equivalence relation.

6. Order Relations

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

Examples include:

• (𝒫(A), ⊆);
• positive integers ordered by divisibility;
• tasks ordered by prerequisite dependency after reflexive closure.

Elements a and b are comparable if aRb or bRa. If every pair is comparable, the partial order is a total order.

For subset S of a poset, a least element is below every member of S, while a minimal element merely has no distinct smaller member in S. A least element, when it exists, is unique; a set may have several minimal elements.

6.1 Strict orders and Hasse diagrams

From a partial order ≤, define its strict counterpart by a < b when a ≤ b and a ≠ b. On a finite poset, the directed graph of this strict order is acyclic. The reflexive relation ≤ itself is not a directed acyclic graph because it contains a loop (a,a) at every vertex.

A Hasse diagram is a compact representation that removes reflexive loops and edges implied by transitivity. An upward edge connects a to b only when b covers a—that is, a < b with no intermediate element c satisfying a < c < b.

Figure: Hasse diagram for divisibility on {1,2,3,6}. Reflexive and transitive edges are omitted.

The diagram omits the relation 1 | 6 because it follows transitively through 2 or 3. It also omits all reflexive pairs.

Topological sorting applies to a finite DAG representing strict precedence, not directly to a reflexive partial-order relation containing loops. It produces a total order consistent with the original constraints; several valid outputs may exist.

7. Functions and Mappings

A function f:A → B assigns every element of domain A exactly one element of codomain B. The value assigned to a is f(a). Its image is

f(A) = {f(a) | a ∈ A},

which may be a proper subset of B.

A relation F ⊆ A × B represents a function from A to B precisely when:

1. Existence: every a ∈ A occurs as a first component;
2. Uniqueness: no a is paired with two different values.

A partial function may be undefined for some elements of its declared input set. Database lookup and division are often naturally partial: x ↦ 1/x is undefined at zero unless an error or extended value is specified.

7.1 Function classifications

A function f:A → B is:

• injective if f(a₁)=f(a₂) → a₁=a₂;
• surjective if ∀b∈B, ∃a∈A, f(a)=b;
• bijective if it is both injective and surjective.

A function has an inverse function f⁻¹:B → A exactly when it is bijective. For a non-bijective function, the inverse relation may exist but is not an inverse function on the stated sets.

If finite sets satisfy |A|>|B|, no function A→B can be injective. This is the pigeonhole principle. If |A|=|B| is finite, injectivity, surjectivity and bijectivity are equivalent.

7.2 Composition

For f:A→B and g:B→C,

Again, the rightmost mapping acts first. Function composition is associative:

h ∘ (g ∘ f) = (h ∘ g) ∘ f,

but generally not commutative.

Worked Example 2: Composition and inverse

Let f:ℝ→ℝ be f(x)=2x+3 and g:ℝ→ℝ be g(x)=x². Then

(g∘f)(x)=(2x+3)², whereas (f∘g)(x)=2x²+3.

They are not equal in general. The function f is bijective on ℝ, and solving y=2x+3 for x gives

The domain and codomain assumptions matter: g(x)=x² is not injective on ℝ, but its restriction g:[0,∞)→[0,∞) is bijective.

8. Cardinality and Countability

The cardinality |A| measures the size of a set. Two sets have the same cardinality when a bijection exists between them.

For finite sets, cardinality is the ordinary number of elements. Infinite sets require a structural comparison rather than subtraction or physical measurement.

8.1 Countably infinite sets

A set is countably infinite if it is in bijection with ℕ={0,1,2,…}. A set is countable if it is finite or countably infinite.

The integers are countably infinite. One enumeration is

0,1,−1,2,−2,3,−3,….

A corresponding bijection e:ℕ→ℤ is

Every integer appears exactly once, including zero.

The rational numbers are also countable. Positive fractions can be arranged by increasing numerator-plus-denominator and duplicates such as 2/2=1/1 removed. Including zero and negatives still gives a countable set.

Useful results include:

• every subset of a countable set is countable;
• a finite Cartesian product of countable sets is countable;
• a countable union of countable sets is countable, assuming the standard set-theoretic framework including countable choice where required.

8.2 Uncountability

The real numbers are uncountable. Cantor’s diagonal argument shows that no proposed sequence can list every real number in (0,1). Given a list of decimal expansions, construct a new real whose nth digit differs from the nth digit of the nth listed number. Choosing digits such as 1 and 2 avoids ambiguous trailing-9 expansions. The constructed number differs from every listed number in at least one position, contradicting completeness.

Cantor’s theorem states that for every set A, its power set has strictly greater cardinality:

No function from A onto 𝒫(A) exists. The diagonal set D={a∈A | a∉f(a)} provides the contradiction for any proposed surjection f:A→𝒫(A).

In computation, the set of all finite strings over a finite alphabet is countable. Programs are finite strings, so there are countably many programs. By contrast, the set of all functions from ℕ to {0,1} is uncountable. Consequently, not every such function can be computed by a program.

9. Applications in Databases and Specifications

9.1 Relational databases

In the mathematical relational model, a relation is a set of tuples. Consequently, duplicate tuples are absent at the conceptual level, although SQL implementations may use bag semantics unless DISTINCT or constraints are applied.

Relational operations correspond closely to set concepts:

A Cartesian product of tables with m and n rows has mn candidate row pairs before a join condition is applied. Poorly specified joins may therefore produce unexpectedly large results.

Keys have a functional interpretation. If EmployeeID is a key, the relation satisfies a functional dependency such as

EmployeeID → Department,

meaning equal EmployeeID values must imply equal Department values. This arrow denotes a database dependency rather than an ordinary function declaration, although the underlying uniqueness idea is closely related.

9.2 Formal specifications

A specification may define:

• a state space as a Cartesian product of component sets;
• valid states as a constrained subset;
• transitions as a relation between states;
• deterministic operations as functions;
• nondeterministic operations as general relations;
• invariants as predicates that must hold in all reachable states.

If T⊆S×S is a transition relation and I⊆S is an invariant set, preservation requires every transition from an invariant state to remain within it:

This condition underpins model checking and safety verification.

10. Applied Case: Role-Based Access Control

This is an illustrative case.

Background

A software organization uses users U, roles ℛ and permissions P. It must calculate effective permissions and enforce separation of duties.

Problem

Let

• U={Asha,Ben,Chen,Dana};
• ℛ={Developer,Auditor,Administrator};
• P={readCode,deploy,readLogs,approve,manageUsers}.

The assignment relation is

assigns={(Asha,Developer),(Ben,Auditor),(Chen,Developer),(Chen,Auditor),(Dana,Administrator)}.

The grant relation is

grants={(Developer,readCode),(Developer,deploy),(Auditor,readLogs),(Auditor,approve),(Administrator,readLogs),(Administrator,manageUsers)}.

Policy forbids one user from holding both deploy and approve.

Analysis and solution

Using right-to-left relational composition:

The resulting permissions are:

Chen violates the separation-of-duties policy because Chen has both conflicting permissions. There are ten effective user–permission pairs: 2 for Asha, 2 for Ben, 4 for Chen and 2 for Dana.

A straightforward remediation is to remove either Chen’s Developer assignment or Auditor assignment, provided organizational responsibilities permit it. Removing (Chen,Auditor) leaves Chen with readCode and deploy and reduces the effective relation to eight pairs.

Outcome

The relational model reveals both inherited permissions and the precise source of the policy violation. It also supports automated audits: compute effective, group permissions by user and test each group against a conflict relation.

Learning points

• Composition order must respect the types of the relations.
• Effective access is derived data and should be recomputed after changes.
• Set semantics prevent duplicate grants from changing authorization meaning.
• Least privilege and separation of duties can be stated as checkable set constraints.
• Audit records should document who changed assignments, when and under what authority.

11. Challenges, Governance and Best Practices

Mathematical models simplify reality. Several practical limitations require attention:

1. Ambiguous universes: complements and quantifiers are meaningful only relative to declared domains.
2. Data quality: a formally valid relation may still contain outdated or incorrect facts.
3. Identity matching: approximate similarity is not necessarily transitive and may not define equivalence classes.
4. Scale: explicit Cartesian products and transitive closures can be expensive; database indexes and graph algorithms avoid unnecessary materialization.
5. Partiality and failure: software functions may time out, throw exceptions or fail to terminate. A mathematical total function models such behavior only if outcomes are represented explicitly.
6. Privacy and fairness: joining datasets may reveal sensitive information or enable harmful profiling. Legal authority, purpose limitation and access controls remain necessary even when an operation is mathematically valid.
7. AI-generated mappings: entity-resolution and classification systems may produce uncertain or biased associations. Confidence scores are not equivalence proofs, and human review may be required.

Recommended practice is to declare domains and codomains, type-check compositions, distinguish sets from bags, document relation properties, test boundary cases, preserve provenance and verify that implemented constraints match organizational policy.

Chapter Summary

Sets describe collections, while set operations support combination, filtering and comparison. Cartesian products form spaces of ordered tuples and provide the basis for relations and database schemas. A binary relation is a subset of a Cartesian product; relation properties determine whether it behaves as an equivalence, an order or neither.

Equivalence relations correspond exactly to partitions. Partial orders support dependency and hierarchy modeling, but the reflexive relation itself contains loops; finite acyclic representations use strict-order graphs or Hasse diagrams. Functions are single-valued, total mappings and may be injective, surjective or bijective. Both relation and function composition apply the rightmost mapping first.

Cardinality compares set sizes through bijections. The integers and rationals are countable, whereas the real numbers and the power set of any countably infinite set are uncountable. These concepts have direct applications to databases, specifications, program transitions, access control and computability.

Key Terms

Set: A well-defined collection of distinct objects.

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

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

Cardinality: A measure of the size of a set.

Cartesian product: The set of all ordered pairs or tuples drawn from specified sets.

Binary relation: A subset of a Cartesian product of two sets.

Composition: Chaining compatible relations or functions, with the rightmost applied first.

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

Symmetric relation: A relation in which aRb implies bRa.

Antisymmetric relation: A relation in which mutual relatedness implies equality.

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

Equivalence relation: A reflexive, symmetric and transitive relation.

Partition: Nonempty, disjoint blocks whose union is the original set.

Partial order: A reflexive, antisymmetric and transitive relation.

Hasse diagram: A reduced representation of a finite partial order omitting loops and transitive edges.

Function: A mapping assigning each domain element exactly one codomain element.

Bijection: A function that is both injective and surjective.

Countable set: A finite set or one that can be placed in bijection with a subset of the natural numbers.

Transitive closure: The relation connecting elements linked by paths of one or more steps.

Invariant: A property that remains true throughout permitted state transitions.

Review Questions

Short Answer Questions

1. What is the difference between a subset and a proper subset?
2. Why must a universe be specified when taking a complement?
3. State the three properties of an equivalence relation.
4. Distinguish a minimal element from a least element.
5. Under what condition does a function possess an inverse function?

Long Answer Questions

1. Explain the main set operations and derive both of De Morgan’s laws using membership reasoning.
2. Describe binary relations, their major properties and the significance of reflexive, symmetric and transitive closures.
3. Prove that equivalence relations induce partitions and that partitions induce equivalence relations.
4. Compare partial orders, strict orders and total orders. Explain the construction and interpretation of a Hasse diagram.
5. Explain finite, countably infinite and uncountable cardinalities, including the main idea of Cantor’s diagonal argument.

Analytical / Application Questions

1. Let R⊆A×B and S⊆B×C be specified as finite pair sets. Design an algorithm to compute S∘R, and analyze its behavior with and without indexing by the shared component.
2. Model a university prerequisite system as a relation. Explain how cycle detection, transitive closure and topological sorting support curriculum governance.
3. Extend the access-control case with a temporary Contractor role. Specify assignment, grant and conflict relations, then formulate tests for least privilege and separation of duties.

Multiple Choice Questions with Answers

Question 1

If |A|=18, |B|=15 and |A∩B|=7, what is |A∪B|?

A. 26

B. 33

C. 40

D. 10

Correct Answer: A. 26

Question 2

How many subsets does a set with five elements have?

A. 10

B. 25

C. 32

D. 64

Correct Answer: C. 32

Question 3

Given assigns⊆U×ℛ and grants⊆ℛ×P, which expression gives the effective user–permission relation using right-to-left composition?

A. assigns∘grants⊆U×P

B. grants∘assigns⊆U×P

C. assigns∪grants⊆U×P

D. grants×assigns⊆U×P

Correct Answer: B. grants∘assigns⊆U×P

Question 4

Which combination of properties defines an equivalence relation?

A. Reflexive, antisymmetric and transitive

B. Irreflexive, symmetric and transitive

C. Reflexive, symmetric and transitive

D. Reflexive, asymmetric and total

Correct Answer: C. Reflexive, symmetric and transitive

Question 5

Which statement correctly describes a finite partial order and its graph representations?

A. Its reflexive relation is a DAG because all loops are ignored by definition.

B. Its strict-order graph is acyclic, and its Hasse diagram omits reflexive and transitive edges.

C. Its Hasse diagram must contain one loop at every vertex.

D. Its strict-order graph must contain a directed cycle whenever incomparable elements exist.

Correct Answer: B. Its strict-order graph is acyclic, and its Hasse diagram omits reflexive and transitive edges.

Question 6

Which condition states that f:A→B is injective?

A. Every element of B has at least one preimage.

B. f(a₁)=f(a₂)→a₁=a₂

C. Every element of A has two images.

D. f(A) is a proper subset of B.

Correct Answer: B. f(a₁)=f(a₂)→a₁=a₂

Question 7

Which set is uncountable?

A. The integers

B. The rational numbers

C. All finite binary strings

D. The real numbers in (0,1)

Correct Answer: D. The real numbers in (0,1)

Question 8

Assuming ℕ={0,1,2,…}, which sequence begins a bijective enumeration of all integers?

A. 0,1,−1,2,−2,3,−3,…

B. 1,−1,2,−2,3,−3,…

C. 0,1,2,3,4,5,…

D. 0,2,−2,4,−4,6,−6,…

Correct Answer: A. 0,1,−1,2,−2,3,−3,…

Question 9

A database table has 12 rows and another has 8 rows. How many candidate row pairs are in their Cartesian product before filtering?

A. 20

B. 48

C. 96

D. 144

Correct Answer: C. 96

Question 10

Which properties define a partial order?

A. Reflexive, symmetric and transitive

B. Irreflexive, asymmetric and transitive

C. Reflexive, antisymmetric and transitive

D. Symmetric, antisymmetric and total

Correct Answer: C. Reflexive, antisymmetric and transitive