2. Sets, Relations, Functions and Order Structures

Introduction and Context

Sets, relations, and functions provide the language through which much of computer science is specified. A database schema describes collections of records and relationships among them; a compiler maps source programs to target representations; an operating system orders events and resources; a formal semantic model assigns meanings to programs; and an algorithm often manipulates finite or infinite collections according to precisely defined rules. These activities rely on mathematical structures that make membership, association, transformation, comparison, and dependency explicit.

This chapter develops the principal structures used for these purposes. It begins with set theory and proceeds to relations, equivalence relations, functions, closures, cardinality, countability, and order structures. The emphasis is not merely on symbolic manipulation. A postgraduate student should be able to select an appropriate structure for a problem, prove its properties, recognize limitations in a model, and translate between mathematical notation and computational practice.

Learning Objectives

After completing this chapter, the reader should be able to:

• represent finite and infinite collections using set notation and perform set operations;
• distinguish relations, equivalence relations, partial orders, and total orders;
• determine whether a relation has properties such as reflexivity, symmetry, antisymmetry, and transitivity;
• construct equivalence classes, quotient sets, closures, and Hasse diagrams;
• analyze functions according to injectivity, surjectivity, bijectivity, and compositional behavior;
• compare finite and infinite cardinalities and explain countability;
• interpret lattices and order structures in data models, semantics, verification, and computing systems;
• evaluate modeling choices, assumptions, and common errors in applied situations.

Sets as Mathematical Models of Collections

A set is a well-defined collection of distinct objects, called elements or members. If an object x belongs to a set A, we write x ∈ A; otherwise x ∉ A. The phrase “well-defined” means that membership is unambiguous. For example, the set of valid IP addresses under a specified address scheme is well-defined, whereas “the set of interesting programs” requires a criterion before it can be used mathematically.

Sets may be specified by roster notation, such as A = {1, 2, 3}, or by set-builder notation, such as A = {x ∈ Z | x is even}. The empty set, written ∅, contains no elements. The universal set U is the domain under consideration, and the complement of A is Aᶜ = U − A. Two sets are equal exactly when they contain the same elements; ordering and repetition in a roster do not matter.

A set A is a subset of B, written A ⊆ B, when every element of A is also an element of B. If A ⊆ B and A ≠ B, then A is a proper subset, written A ⊂ B. The power set P(A) is the set of all subsets of A. If A has n elements, P(A) has 2ⁿ elements. This result is important in state-space analysis: even a modest set of variables can generate a substantially larger set of possible configurations.

The principal operations are union, intersection, difference, and Cartesian product:

• A ∪ B contains elements in A or B, or both.
• A ∩ B contains elements common to A and B.
• A − B contains elements in A but not in B.
• A × B is the set of ordered pairs (a,b) with a ∈ A and b ∈ B.

Union and intersection are commutative, associative, and distributive over one another. De Morgan’s laws state that (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. These identities occur directly in query optimization, Boolean conditions, and digital circuit simplification.

A partition of a set S is a collection of nonempty, pairwise disjoint subsets whose union is S. Partitions are especially significant because equivalence relations generate them, allowing a complex domain to be divided into meaningful categories without overlap.

Relations: Representing Association and Dependency

A binary relation R from A to B is a subset of A × B. We write aRb when (a,b) ∈ R. When A = B, R is a relation on A. Relations can be represented by a set of ordered pairs, a Boolean matrix, a directed graph, or a logical predicate. The representation should be chosen according to the intended operation: matrices support algebraic computation, graphs support visualization, and predicates support specification.

For a relation R on A, several properties are fundamental:

• Reflexive: for every a ∈ A, (a,a) ∈ R.
• Irreflexive: for every a ∈ A, (a,a) ∉ R.
• Symmetric: if (a,b) ∈ R, then (b,a) ∈ R.
• Antisymmetric: if (a,b) and (b,a) belong to R, then a = b.
• Asymmetric: if (a,b) ∈ R, then (b,a) ∉ R.
• Transitive: if (a,b) and (b,c) belong to R, then (a,c) ∈ R.

Symmetry and antisymmetry are not opposites. The relation “is married to” is commonly modeled as symmetric, while “is a subset of” is antisymmetric. A relation can be both symmetric and antisymmetric, as happens with the equality relation.

The inverse relation R⁻¹ reverses each ordered pair: (b,a) ∈ R⁻¹ exactly when (a,b) ∈ R. Relations can be composed. If R ⊆ A × B and S ⊆ B × C, then S ○ R contains (a,c) whenever there is some b ∈ B such that aRb and bSc. Relational composition models multi-stage reachability, database joins, and successive program transformations.

The transitive closure R⁺ is the smallest transitive relation containing R. It records reachability through one or more relation steps. The reflexive-transitive closure R = R⁺ ∪ I, where I is the identity relation, records reachability through zero or more steps. In a directed graph, R can be computed by methods such as Warshall’s algorithm. For a transition system, R* answers whether one state can eventually reach another.

A closure operator on a set of objects maps each object to a closed object and normally satisfies extensivity, monotonicity, and idempotence. For example, taking the transitive closure of a relation gives a relation that contains the original, preserves inclusion order, and does not change when closure is applied again. Closure operators are useful because they complete partial information according to a specified rule.

Equivalence and the Logic of Classification

An equivalence relation is reflexive, symmetric, and transitive. It expresses sameness relative to a chosen criterion rather than absolute identity. Congruence modulo n provides a standard example: a ≡ b (mod n) when n divides a − b. In computing, two strings may be equivalent under case-insensitive comparison, two programs may be equivalent under an observational criterion, or two database records may be equivalent under a deduplication policy.

For a ∈ A, the equivalence class of a is [a] = {x ∈ A | xRa}. Equivalence classes are either identical or disjoint. Consequently, the set of all equivalence classes, denoted A/R, forms a partition of A and is called the quotient set. This construction replaces many individual objects with representative categories. In automata theory, state minimization uses an equivalence notion to identify states with indistinguishable future behavior.

A crucial modeling caution is that an informal similarity relation may fail transitivity. If records are considered similar whenever their names differ by at most one character, similarity need not be transitive. Treating such a relation as an equivalence relation can produce overlapping and inconsistent classes. A system must either refine the criterion or use a different clustering model.

Functions as Deterministic Mappings

A function f from A to B, written f: A → B, assigns exactly one element of B to every element of A. A is the domain and B is the codomain. The image or range is f(A) = {f(a) | a ∈ A}, which may be a proper subset of B. Confusing codomain with image is a common source of error: a function can be surjective only relative to its stated codomain.

A function is injective if distinct domain elements have distinct images. It is surjective if every element of the codomain is the image of at least one domain element. It is bijective if it is both injective and surjective. A bijection establishes a one-to-one correspondence and therefore equality of cardinality. A function has an inverse function precisely when it is bijective, although a non-injective function may have an inverse relation rather than an inverse function.

Functions can be composed. If f: A → B and g: B → C, then (g ○ f)(a) = g(f(a)). Composition is associative but generally not commutative. The identity function id_A maps each element to itself. A function has a left inverse if it is injective and a right inverse if it is surjective, under the usual set-theoretic conditions.

In computer science, a function may be total or partial. A total function produces an output for every permitted input; a partial function is undefined for some inputs. Division by zero and a parser that rejects malformed input are examples of partial behavior when their domains are not restricted appropriately. Making the domain explicit often converts an apparently partial operation into a total function, improving formal specifications.

Cardinality and Countability

The cardinality of a finite set is its number of elements. For arbitrary sets A and B, |A| = |B| when there exists a bijection between them. This definition produces a surprising result: the natural numbers N and the even natural numbers have the same cardinality, because n ↦ 2n is a bijection.

A set is countably infinite if it can be put into bijection with N, or equivalently if its elements can be listed in a sequence without omission. The integers and rational numbers are countable, although the latter may initially appear more numerous. The real numbers are uncountable. Cantor’s diagonal argument proves that no list of all real numbers in an interval can be complete.

For every set A, its power set P(A) has strictly greater cardinality than A. This is Cantor’s theorem and implies an infinite hierarchy of increasingly large infinities. In computing, the set of all finite strings over a finite alphabet is countable, whereas the set of all infinite binary sequences is uncountable. Therefore, most mathematically possible infinite behaviors cannot be represented by finite programs or finite strings. This observation informs computability theory and the limits of formal verification.

Cardinality also constrains data structures and encodings. A lossless encoding from A into B requires an injective function A → B. A reversible representation requires a bijection between the represented objects and their codes, or a precisely specified subset of codes. Claims about compression, identifiers, and finite address spaces should therefore be checked against cardinality rather than intuition.

Order Structures and Lattices

A partial order is a relation ≤ on a set P that is reflexive, antisymmetric, and transitive. The pair (P, ≤) is a partially ordered set, or poset. Unlike ordinary numerical order, a partial order need not compare every pair. In the power set P(S), inclusion ⊆ is a partial order: two subsets may be incomparable.

If every pair of elements in a poset is comparable, the order is total or linear. A total order is useful for sorting, while a partial order more accurately models dependency, containment, refinement, and precedence. A topological sorting of a finite directed acyclic graph produces a linear ordering consistent with its partial order, but several valid orderings may exist.

An element y covers x when x < y and there is no z such that x < z < y. A Hasse diagram represents a finite poset using only cover relations; reflexive loops and transitive edges are omitted. Elements at the bottom and top, when they exist, are called least and greatest elements. These differ from minimal and maximal elements: a poset may have several minimal elements but at most one least element.

For a subset A of a poset, a least upper bound, when it exists, is called the join of A and is written ∨A. A greatest lower bound is the meet, written ∧A. A lattice is a poset in which every pair of elements has both a join and a meet. The power set ordered by inclusion is a lattice: join is union and meet is intersection. A bounded lattice has a least element 0 and greatest element 1. A complemented lattice gives, for each element, a complement satisfying appropriate meet and join conditions; Boolean algebras are complemented distributive lattices and underpin propositional logic and digital design.

In program analysis, abstract interpretation often uses lattices of properties. For example, an element may represent “definitely constant,” “possibly constant,” or “unknown.” Moving upward in the lattice can represent loss of precision, while a fixed point represents a stable result of iterative analysis. The mathematical properties of the lattice help establish termination and soundness under suitable conditions.

An Applied Case: Access Control and Information Flow

Background

Consider an illustrative university research platform containing projects, datasets, users, and permission levels. The platform must answer questions such as whether a user may access a dataset, whether two users have equivalent effective permissions, and whether a request inherits permissions through a project hierarchy.

Situation and Problem

Projects are organized by containment: a laboratory contains projects, and projects contain datasets. Permissions include read, write, and administer. A user may receive permissions directly, through membership in a group, or through a parent project. The organization needs a model that prevents accidental privilege escalation while allowing automated authorization decisions.

Analysis

Let D be the set of datasets and U the set of users. The access relation A ⊆ U × D records direct access. Group membership is another relation M ⊆ U × G. Project containment is represented by C ⊆ P × P, where (p,q) means that p contains q. The reflexive-transitive closure C* captures inherited containment, including a project’s relation to itself. Authorization can then be defined as a predicate over user, dataset, and permission type rather than as an informal rule.

Permission levels form a partial order: administer implies write, and write implies read, but read does not imply write. Thus the permission order is not merely a list if several permissions are incomparable. Its join can represent the least permission set combining grants from multiple sources. A denial policy must be specified separately because simply taking joins may produce an unsafe result when explicit denial is intended to override inheritance.

Users can be classified by an equivalence relation if they have identical effective permission sets. However, this equivalence must be recomputed when membership or project structure changes. A relation such as “users share at least one permission” is not an equivalence relation because it may fail transitivity.

Approach and Outcome

The platform stores primitive relations, computes transitive closure for containment, and derives effective permissions through well-defined compositions. It uses a lattice-like representation for permission sets and logs every derivation so that an authorization decision can be audited. Formal tests check reflexivity, antisymmetry, and transitivity of hierarchy data, while cycle detection prevents an invalid containment structure from creating ambiguous inheritance.

Learning Points

The case illustrates that different questions require different structures. Relations represent raw associations, closures represent indirect reachability, functions are appropriate for deterministic mappings such as a dataset’s owner, equivalence classes support classification, and partial orders represent permission implication without forcing incomparable privileges into an artificial sequence. It also shows that mathematical correctness does not by itself determine policy: governance rules, conflict resolution, and audit requirements must be made explicit.

Applications, Risks, and Professional Practice

Set and relation models appear in relational databases, graph databases, compiler symbol tables, type systems, formal languages, workflow scheduling, knowledge graphs, version-control histories, and distributed-system state models. Database normalization relies on dependencies and keys; graph algorithms rely on reachability relations; type checking often computes ordered approximations of program properties; and query languages use set or bag semantics depending on whether duplicates matter.

Several errors recur in practice. Treating a relation as a function when one input may have multiple outputs loses information. Assuming that a relation is transitive because it “sounds hierarchical” can introduce false reachability. Confusing antisymmetry with asymmetry leads to incorrect order tests. Omitting the codomain makes claims about surjectivity ambiguous. Ignoring empty sets and boundary cases causes incorrect proofs and faulty software. Finally, applying a closure without considering cycles, computational cost, or semantic meaning may produce results that are mathematically valid but operationally inappropriate.

In data governance, equivalence criteria affect deduplication, identity management, and fairness. A mistaken equivalence rule may merge distinct individuals or keep duplicate records. In access control, closure computations can create privilege escalation if inheritance is not constrained. In AI and analytics, clustering or similarity should not be presented as equivalence unless the required properties have been verified. Professional practice therefore requires documenting domains, codomains, assumptions, conflict rules, and the meaning of derived relations.

Modern software tools automate relation reasoning through graph databases, constraint solvers, model checkers, theorem provers, and symbolic algebra systems. Automation is valuable for large finite structures, but it does not replace semantic judgment. A tool can verify that a supplied relation is transitive; it cannot decide whether transitivity is an appropriate requirement for a social, organizational, or security concept. Emerging work in formal methods increasingly combines machine-checkable proofs with automated invariant discovery and abstract interpretation, while the underlying set-theoretic definitions remain the foundation.

Best Practices for Modeling

Begin by declaring the universe of discourse and distinguishing elements from sets of elements. State the domain and codomain of every function. Represent primitive facts separately from derived facts, and identify whether a derived relation is a reflexive, symmetric, or transitive closure. Use equivalence relations only when the criterion genuinely satisfies all three defining properties. Use partial orders when comparison is meaningful but incomparability must be preserved. For finite posets, Hasse diagrams and topological sorts provide useful validation views. Finally, test definitions against empty inputs, duplicate data, cycles, boundary values, and changes in policy.

Chapter Summary

Sets model collections and support union, intersection, difference, Cartesian products, complements, and power sets. Relations generalize association and can be analyzed through reflexivity, symmetry, antisymmetry, transitivity, inverse, composition, and closure. Equivalence relations partition domains into disjoint classes and generate quotient sets. Functions provide deterministic mappings and are distinguished by injectivity, surjectivity, and bijectivity. Cardinality uses bijections to compare finite and infinite sets; countability separates natural-number-sized infinities from uncountable structures. Partial orders model dependency and refinement without requiring universal comparability, while lattices provide joins and meets that support logic, permission systems, and program analysis. Effective application requires precise domains, explicit assumptions, careful closure rules, and attention to governance and security consequences.

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.

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

Relation: A subset of a Cartesian product.

Reflexive relation: A relation containing (a,a) for every domain element.

Symmetric relation: A relation in which aRb implies bRa.

Antisymmetric relation: A relation in which aRb and bRa imply a=b.

Transitive relation: 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 selected element.

Quotient set: The set of equivalence classes induced by an equivalence relation.

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

Injective function: A function mapping distinct inputs to distinct outputs.

Surjective function: A function whose image equals its codomain.

Bijection: A function that is both injective and surjective.

Closure: The smallest structure containing an object and satisfying a specified property.

Partial order: A reflexive, antisymmetric, and transitive relation.

Lattice: A poset in which every pair has a join and a meet.

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

Review Questions

Short Answer Questions

1. Distinguish a subset from a proper subset and provide an example.

2. Define reflexivity, antisymmetry, and transitivity for a relation.

3. What is the difference between the image and codomain of a function?

4. Why do equivalence classes form a partition?

5. Define a lattice in terms of joins and meets.

Long Answer Questions

1. Explain the principal set operations and prove both of De Morgan’s laws using element-wise reasoning.

2. Discuss equivalence relations, equivalence classes, quotient sets, and their use in state minimization.

3. Compare injective, surjective, and bijective functions, including the relationship between bijections and inverse functions.

4. Explain partial orders, cover relations, Hasse diagrams, minimal elements, least elements, and topological sorting.

5. Describe countability, Cantor’s diagonal argument, and the significance of uncountable sets for computation.

Analytical / Application Questions

1. A workflow relation records that task x must precede task y. Determine which closure is needed to answer whether a task can indirectly precede another, and explain how cycles affect the model.

2. A data-cleaning system declares two records equivalent when their names differ by at most one character. Test whether this criterion is an equivalence relation and propose a safer alternative if it is not.

3. Model inherited permissions in a project hierarchy using sets, relations, closures, and a partial order. Explain how your model would prevent an unintended privilege escalation.

22. Multiple Choice Questions with Answers

Question 1

Which condition is necessary for a relation on A to be an equivalence relation?

A. It must be reflexive, symmetric, and transitive.

B. It must be reflexive, antisymmetric, and asymmetric.

C. It must be irreflexive, symmetric, and transitive.

D. It must compare every pair of elements.

Correct Answer: A. It must be reflexive, symmetric, and transitive.

Question 2

If f:A→B is injective but not surjective, which statement is correct?

A. Every element of B has exactly one preimage.

B. Distinct elements of A have distinct images, but some elements of B may have none.

C. f has an inverse function from B to A.

D. A and B necessarily have equal finite cardinality.

Correct Answer: B. Distinct elements of A have distinct images, but some elements of B may have none.

Question 3

What does the reflexive-transitive closure R* represent in a directed graph?

A. Reachability by exactly one edge.

B. Reachability only between distinct vertices.

C. Reachability by zero or more relation steps.

D. Pairs connected by a symmetric path only.

Correct Answer: C. Reachability by zero or more relation steps.

Question 4

Which structure is induced by the equivalence classes of an equivalence relation on A?

A. A partition of A.

B. A total order on A.

C. A power set with 2|A| elements in every case.

D. A bijection from A to the empty set.

Correct Answer: A. A partition of A.

Question 5

In the poset of subsets of S ordered by inclusion, what is the join of X and Y?

A. X∩Y

B. X−Y

C. X∪Y

D. S−(X∪Y)

Correct Answer: C. X∪Y

Question 6

A relation is antisymmetric when:

A. aRb always implies bRa.

B. aRb and bRa together imply a=b.

C. aRb implies that a is not equal to b.

D. aRb and bRc imply cRa.

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

Question 7

Which statement about cardinality is correct?

A. The even natural numbers have smaller cardinality than the natural numbers.

B. Every infinite set is uncountable.

C. A bijection between two sets establishes that they have equal cardinality.

D. The power set of a finite set has the same cardinality as the original set.

Correct Answer: C. A bijection between two sets establishes that they have equal cardinality.

Question 8

A function has an inverse function precisely when it is:

A. Only injective.

B. Only surjective.

C. Bijective.

D. A relation but not a function.

Correct Answer: C. Bijective.

Question 9

Why is “shares at least one permission with” generally unsuitable as an equivalence relation?

A. It cannot be reflexive.

B. It may fail transitivity.

C. It is always antisymmetric.

D. It necessarily defines a total order.

Correct Answer: B. It may fail transitivity.

Question 10

In access-control modeling, why might a closure operation be dangerous if used without policy constraints?

A. Closure always removes all original facts.

B. It can create unintended inherited reachability or privileges.

C. Closure converts every relation into a function.

D. Closure makes every set uncountable.

Correct Answer: B. It can create unintended inherited reachability or privileges.