Relations, Functions and Orders

Introduction

Relations and functions provide a mathematical language for describing connections, dependencies, classifications and transformations. In computing, a relation can represent links between database records, compatibility between devices, prerequisites among courses, or transitions in a software system. A function models a deterministic mapping such as an input-to-output computation, a memory address translation, or a program that transforms data.

Orders add structure to relations by expressing ideas such as precedence, containment and dependency. They support scheduling, version control, type hierarchies, formal verification and query optimization. Equivalence relations classify objects into meaningful groups, while lattices provide a framework for combining and comparing information.

This chapter develops these ideas from set-theoretic foundations to practical applications.

Learning Objectives

After studying this chapter, you should be able to:

1. Define and represent relations between sets.
2. Test reflexivity, symmetry, antisymmetry and transitivity.
3. Construct equivalence classes and partitions.
4. Compute reflexive, symmetric and transitive closures.
5. Explain partial orders, total orders, Hasse diagrams and lattices.
6. Define functions, distinguish injective, surjective and bijective functions, and determine inverses.
7. Perform function composition and analyze growth using asymptotic notation.
8. Apply these concepts to databases, classifications, dependencies and computational mappings.

1. Relations as Mathematical Models

Let A and B be sets. A binary relation R from A to B is a subset of the Cartesian product A × B. Thus, R ⊆ A × B. If (a, b) ∈ R, we write a R b and say that a is related to b.

When A = B, R is called a relation on A. A relation may be represented by:

• an ordered-pair list;
• a directed graph, with one vertex for each element and an arrow a → b when a R b;
• a Boolean matrix, where entry 1 indicates that the relation holds;
• a rule or predicate.

For example, let A = {1, 2, 3} and define R = {(1, 1), (1, 2), (2, 3)}. The relation states that 1 is related to 1 and 2, and 2 is related to 3. It does not state that 3 is related to any element.

The inverse relation R⁻¹ reverses every ordered pair:

The domain of R is the set of first components that occur in R, and its range is the set of second components that occur in R.

Properties of Relations

For a relation R on A:

• Reflexive: a R a for every a ∈ A.
• Irreflexive: a R a for no a ∈ A.
• Symmetric: if a R b, then b R a.
• Antisymmetric: if a R b and b R a, then a = b.
• Asymmetric: if a R b, then b R a is impossible.
• Transitive: if a R b and b R c, then a R c.

Symmetry and antisymmetry are different. The relation “is a sibling of” is usually symmetric but not antisymmetric. The relation “is less than or equal to” is antisymmetric but not symmetric.

Worked Example 1: Testing Relation Properties

Let A = {1, 2, 3} and R = {(1,1), (2,2), (3,3), (1,2), (2,1)}.

The relation is reflexive because all three pairs (a,a) are present. It is symmetric because (1,2) and (2,1) both occur, and the diagonal pairs are automatically symmetric. It is not antisymmetric because 1 R 2 and 2 R 1, but 1 ≠ 2. It is transitive: the only nontrivial two-step paths are 1 → 2 → 1 and 2 → 1 → 2, and the required diagonal pairs are present. Therefore R is an equivalence relation, but not a partial order.

2. Equivalence Relations, Classes and Partitions

An equivalence relation is a relation that is reflexive, symmetric and transitive. Equivalence relations express “having the same relevant property,” even when objects are not identical.

If R is an equivalence relation on A, the equivalence class of a ∈ A is

All members of [a] are equivalent to a. Two fundamental results are:

1. Every element belongs to exactly one equivalence class.
2. Two equivalence classes are either identical or disjoint.

A partition of A is a collection of nonempty, pairwise disjoint subsets whose union is A. Every equivalence relation produces a partition, and every partition defines an equivalence relation: two elements are related precisely when they belong to the same block.

Example: Congruence Modulo 3

On the integers, define a R b when a − b is divisible by 3. This is an equivalence relation. Its three classes are:

• [0] = {..., −6, −3, 0, 3, 6, ...}
• [1] = {..., −5, −2, 1, 4, 7, ...}
• [2] = {..., −4, −1, 2, 5, 8, ...}

These classes partition the integers according to their remainder after division by 3.

Equivalence classes are important in data deduplication, user classification, canonical representations and quotient structures. For example, two strings may be considered equivalent if they differ only in capitalization; a system can store one representative per class, provided that the equivalence rule is carefully defined.

3. Closures of Relations

A closure adds the smallest number of ordered pairs needed to give a relation a desired property. “Smallest” means that the original relation is retained and no unnecessary pairs are added.

For a relation R on A:

• Reflexive closure: R ∪ {(a,a) : a ∈ A}.
• Symmetric closure: R ∪ R⁻¹.
• Transitive closure: the smallest transitive relation containing R.

The transitive closure is often denoted R⁺. It contains (a,b) whenever there is a path of one or more edges from a to b in the directed graph of R. The reflexive-transitive closure, commonly denoted R*, also includes (a,a) for every a.

Worked Example 2: Closures

Let A = {a, b, c} and R = {(a,b), (b,c)}.

The reflexive closure adds (a,a), (b,b) and (c,c). The symmetric closure adds (b,a) and (c,b). The transitive closure adds (a,c), because a R b and b R c. Thus R⁺ = {(a,b), (b,c), (a,c)}.

In computing, reachability algorithms calculate transitive closure. If R represents “direct prerequisite,” R⁺ represents “prerequisite directly or indirectly.” Warshall’s algorithm computes reachability for a finite relation represented by an n × n Boolean matrix. Its standard time complexity is O(n³), where n is the number of vertices.

4. Partial Orders and Hasse Diagrams

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, and is written (A, ≤).

Examples include:

• ordinary ≤ on numbers;
• set inclusion ⊆;
• divisibility on positive integers;
• the relation “is an ancestor of,” when reflexivity is included;
• task precedence in project scheduling.

In a poset, two elements may be incomparable. For example, under set inclusion, {a} and {b} are incomparable because neither contains the other.

A total, or linear, order is a partial order in which every pair of elements is comparable. For all a, b ∈ A, either a ≤ b or b ≤ a.

Minimal, Maximal, Least and Greatest Elements

An element m is minimal if no distinct element is below m. An element M is maximal if no distinct element is above M. A least element is below every element, while a greatest element is above every element. A poset can have several minimal or maximal elements, but it can have at most one least element and at most one greatest element.

Hasse Diagrams

A Hasse diagram represents a finite poset without drawing reflexive edges or transitive edges. If x is immediately below y, y is drawn above x and connected by a line. The diagram must be interpreted with upward movement representing the order.

For the divisibility relation on {1, 2, 3, 6}, the order is 1 ≤ 2, 1 ≤ 3, 2 ≤ 6 and 3 ≤ 6, where “≤” means “divides.” The Hasse diagram is a diamond: 1 at the bottom, 6 at the top, and 2 and 3 between them.

5. Lattices

A lattice is a poset in which every pair of elements a and b has:

• a greatest lower bound, called the meet and written a ∧ b;
• a least upper bound, called the join and written a ∨ b.

For subsets ordered by inclusion, the meet is intersection and the join is union:

The applicability here is the power set of a fixed universal set, ordered by ⊆. For example, if a = {1,2} and b = {2,3}, then a ∧ b = {2} and a ∨ b = {1,2,3}.

A bounded lattice has a least element 0 and a greatest element 1. A Boolean algebra is a complemented distributive lattice and is fundamental to digital logic and circuit design. In Boolean algebra, meet corresponds to AND, join to OR and complement to NOT.

Lattices also appear in access-control policies. If permissions are ordered by inclusion, the join of two permission sets is the least permission set containing both, while the meet is the common permission set.

6. Functions and 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

Every function is a relation, but not every relation is a function. A relation from A to B is a function precisely when each element of A appears as the first component of exactly one ordered pair.

Important types include:

• Injective (one-to-one): f(a₁) = f(a₂) implies a₁ = a₂.
• Surjective (onto): for every b ∈ B, there exists a ∈ A such that f(a) = b.
• Bijective: both injective and surjective.

A finite function f: A → B can be injective only if |A| ≤ |B| and surjective only if |A| ≥ |B|. It is bijective when the finite sets have equal cardinality and both properties hold.

Composition

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

The rightmost function is applied first. Composition is associative, so h ○ (g ○ f) = (h ○ g) ○ f whenever the mappings are compatible. It is generally not commutative: g ○ f usually differs from f ○ g, and one of these compositions may not even be defined.

Inverse Functions

A function has an inverse function f⁻¹: B → A exactly when it is bijective. The inverse satisfies

for all a ∈ A and b ∈ B. A non-injective function cannot have a function inverse because two inputs would require the same output to map back to two different inputs. A non-surjective function cannot have an inverse with the stated codomain because some codomain elements have no preimage.

Worked Example 3: Composition and Inverse

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

(g ○ f)(x) = (2x + 3)²,

whereas

(f ○ g)(x) = 2x² + 3.

These are not equal in general. The function f is bijective on R. To find its inverse, let y = 2x + 3. Solving for x gives x = (y − 3)/2, so f⁻¹(y) = (y − 3)/2. The function g is not injective on R because g(2) = g(−2), and therefore it has no inverse function from R to R.

7. Relations and Functions in Databases

A relational database represents data using tables. A table can be viewed as a relation whose tuples are rows and whose attributes are columns. Keys impose functional dependencies. If attribute set X determines attribute set Y, we write X → Y. This means that whenever two rows agree on X, they must also agree on Y.

For example, StudentID → StudentName expresses that each student identifier determines one student name. If a table stores StudentID, StudentName and CourseID, repeating names across course registrations can cause update anomalies. Functional-dependency analysis supports normalization, which decomposes tables to reduce redundancy while preserving important information.

Database foreign keys represent links between relations. A primary key functionally identifies a row, while a foreign key creates a relation between rows in different tables. Integrity constraints ensure that these relations remain meaningful.

8. Growth of Functions and Computational Complexity

Functions also describe resource growth. Big-O notation gives an asymptotic upper bound. We write f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that

Here n is typically input size, while c and n₀ are constants independent of n. Big-Ω gives an asymptotic lower bound, and Big-Θ gives a tight bound when both O and Ω conditions hold.

For example, f(n) = 3n² + 5n + 7 is Θ(n²), because the quadratic term dominates as n becomes large. Constants and lower-order terms matter for actual performance, but asymptotic notation focuses on growth.

Common growth classes, from generally slower to faster, are O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and O(n!). These classifications help compare algorithms independently of hardware, although they do not replace empirical testing.

9. Illustrative Case: Course-Prerequisite Management

Background

A university wants to build a registration system that prevents students from enrolling in a course before completing its prerequisites.

Problem

The database stores direct prerequisite links, but a course may require another course indirectly. For example, Programming II requires Programming I, and Data Structures requires Programming II. The system must recognize that Programming I is also an indirect prerequisite for Data Structures.

Analysis

Let C be the set of courses and define R ⊆ C × C by (x,y) ∈ R when x is a direct prerequisite of y. The transitive closure R⁺ identifies all direct and indirect prerequisite relationships. Since a course cannot be its own prerequisite, the relation should be checked for cycles. A cycle would indicate an impossible curriculum, such as Course A requiring B while B requires A.

Approach and Solution

The curriculum service stores R as an adjacency matrix or adjacency list. A transitive-closure procedure computes reachability. Before approving a new edge (x,y), the system checks whether y already reaches x. If so, adding (x,y) would create a cycle and should be rejected. A topological ordering can then produce a valid sequence for courses in an acyclic prerequisite graph.

Outcome

Students receive accurate prerequisite decisions, curriculum designers can detect circular dependencies, and administrators can identify courses with no prerequisites or courses that unlock many later courses.

Learning Points

This case combines relations, transitive closure, directed graphs, partial-order ideas and functions. It also illustrates that mathematical correctness affects real system reliability: an incorrectly defined prerequisite relation can deny valid enrollment or permit academically unsafe enrollment.

10. Limitations, Governance and Best Practices

Relations and functions simplify reality, but the chosen rule determines the quality of the model. A classification relation may encode cultural or organizational assumptions. Database dependencies may become invalid when business rules change. A function is appropriate only when each input has one well-defined output; uncertain or many-valued processes require a different model, such as a relation, probability distribution or set-valued mapping.

Best practices include:

• state the domain and codomain explicitly;
• distinguish direct relationships from their closures;
• test relation properties rather than assuming them;
• validate uniqueness and completeness of functions;
• check for cycles in dependency systems;
• document assumptions behind classifications;
• protect sensitive identifiers and relationship data;
• test algorithms on boundary cases, empty sets and duplicate values;
• use asymptotic analysis together with practical performance measurements.

In AI and data systems, relations may be learned from data rather than specified directly. This creates additional concerns about bias, explainability, data quality and governance. A mathematically valid relation can still be socially inappropriate if its underlying data or interpretation is discriminatory.

Chapter Summary

A relation is a set of ordered pairs and can model links between objects. Relations are characterized by properties such as reflexivity, symmetry, antisymmetry and transitivity. An equivalence relation creates equivalence classes, and these classes form a partition of the underlying set. Closures extend relations minimally to achieve reflexivity, symmetry or transitivity.

Partial orders express structured precedence while allowing incomparable elements. Hasse diagrams provide compact representations of finite posets. Lattices strengthen partial orders by guaranteeing a meet and join for every pair. Functions are special relations assigning exactly one output to each input; injective, surjective and bijective functions support classification, data transformation and reversible computation. Composition combines functions, and bijections possess inverses.

These concepts support database dependencies, prerequisite systems, access control, algorithm design and computational complexity. Correct modeling requires explicit domains, validated assumptions and attention to ethical and operational consequences.

Key Terms

Relation: A subset of a Cartesian product.

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

Domain: The set of possible inputs or first components of a relation.

Range: The set of actual outputs or second components.

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

Symmetric relation: A relation in which a R b implies b R a.

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

Transitive relation: A relation in which a R b and b R c imply a R c.

Equivalence relation: A reflexive, symmetric and transitive relation.

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

Partition: Disjoint nonempty blocks whose union is the whole set.

Closure: The smallest extension of a relation having a specified property.

Partial order: A reflexive, antisymmetric and transitive relation.

Total order: A partial order in which every pair is comparable.

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

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

Injective: A function mapping distinct inputs to distinct outputs.

Surjective: A function whose range equals its codomain.

Bijection: A function that is both injective and surjective.

Composition: The application of one function after another.

Review Questions

Short Answer Questions

1. Define a binary relation from A to B.
2. State the three properties required for an equivalence relation.
3. What is the difference between a partial order and a total order?
4. When does a function have an inverse function?
5. Define the transitive closure of a relation.

Long Answer Questions

1. Explain equivalence classes and partitions, and prove why equivalence classes are either identical or disjoint.
2. Describe reflexive, symmetric and transitive closures with a suitable example.
3. Explain partial orders, minimal and maximal elements, and Hasse diagrams.
4. Discuss injective, surjective and bijective functions with examples.
5. Explain how relations and functional dependencies are used in relational databases.

Analytical / Application Questions

1. A university records direct course prerequisites. Design a relation-based method for detecting indirect prerequisites and circular dependencies.
2. Let f(x) = 3x − 4 and g(x) = x². Compute g ○ f and f ○ g, and explain why they differ.
3. A permission system orders permission sets by inclusion. Explain the meet and join of two permission sets and discuss one governance risk of this model.

Multiple Choice Questions with Answers

Question 1

Which property, together with symmetry and transitivity, defines an equivalence relation?

A. Reflexivity

B. Antisymmetry

C. Asymmetry

D. Totality

Correct Answer: A. Reflexivity

Question 2

If R = {(a,b),(b,c)}, which pair must be added to obtain the relevant transitive consequence?

A. (b,a)

B. (c,b)

C. (a,c)

D. (a,a)

Correct Answer: C. (a,c)

Question 3

Under set inclusion, what is the meet of {1,2} and {2,3}?

A. {1,2,3}

B. {2}

C. {1,3}

D. ∅

Correct Answer: B. {2}

Question 4

A function f: A → B is injective when:

A. Every element of B has a preimage

B. Every input has at least two outputs

C. Equal outputs imply equal inputs

D. A and B have equal cardinality

Correct Answer: C. Equal outputs imply equal inputs

Question 5

Which condition is necessary and sufficient for a function to have a function inverse with the stated domain and codomain?

A. It is reflexive

B. It is bijective

C. It is symmetric

D. It is constant

Correct Answer: B. It is bijective

Question 6

If f(x) = 2x + 3 and g(x) = x², what is (g ○ f)(x)?

A. 2x² + 3

B. (2x + 3)²

C. x² + 5

D. 4x + 9

Correct Answer: B. (2x + 3)²

Question 7

Which relation is a partial order?

A. Siblinghood

B. Strict inequality <

C. Set inclusion ⊆

D. Being unrelated

Correct Answer: C. Set inclusion ⊆

Question 8

For a finite poset, a least element is an element that:

A. Has no element below it

B. Is below every element

C. Is above every element

D. Has no comparable elements

Correct Answer: B. Is below every element

Question 9

The asymptotic classification of 3n² + 5n + 7 is:

A. Θ(1)

B. Θ(n)

C. Θ(n²)

D. Θ(2ⁿ)

Correct Answer: C. Θ(n²)

Question 10

In a prerequisite relation, the transitive closure represents:

A. Only courses with no prerequisites

B. Direct and indirect prerequisite links

C. Only symmetric links

D. Random course pairs

Correct Answer: B. Direct and indirect prerequisite links