Relations, Functions and Discrete Models

Introduction

Relations and functions provide the mathematical language for describing connections, transformations, dependencies, and classifications. In computer science and artificial intelligence, they are used to represent database associations, model input-output behavior, define state transitions, describe similarity between objects, and formalize mappings between data spaces. A relation may associate one object with many others, while a function imposes the stronger condition that each input has exactly one output.

This chapter develops the theory of relations and functions from basic definitions to closures, equivalence relations, partitions, composition, inverse mappings, growth, and discrete models. Particular attention is given to representations useful in databases and AI systems.

Learning Objectives

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

1. Define relations, functions, domains, codomains, ranges, and graphs.

2. Represent relations using matrices, directed graphs, and ordered pairs.

3. Test relations for reflexivity, symmetry, antisymmetry, and transitivity.

4. Compute reflexive, symmetric, and transitive closures.

5. Explain equivalence relations and construct their associated partitions.

6. Distinguish injective, surjective, and bijective functions.

7. Calculate compositions and determine when inverse functions exist.

8. Analyze common discrete growth models.

9. Apply relations and functions to databases, classification, and AI systems.

10. Evaluate limitations and governance issues in relational modeling.

1. Relations as Models of Association

Let A and B be sets. A relation R from A to B is a subset of the Cartesian product A × B. Thus, each element of R is an ordered pair (a,b), where a ∈ A and b ∈ B. We write aRb when (a,b) ∈ R.

If A = B, R is called a relation on A. For example, let A = {1,2,3,4} and define R by

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

This relation records selected connections among elements of A. It does not need to contain every possible ordered pair. Since A × A contains 16 ordered pairs, R is a relatively sparse relation.

The domain of a relation R from A to B is

dom(R) = {a ∈ A : (a,b) ∈ R for at least one b ∈ B}.

The range is

ran(R) = {b ∈ B : (a,b) ∈ R for at least one a ∈ A}.

The codomain is the target set B, which may be larger than the range. Confusing codomain and range can lead to incorrect conclusions about whether a function is surjective.

Representations of Relations

A relation can be represented in several equivalent ways.

Ordered-pair representation. The relation is listed explicitly as a set of ordered pairs. This is useful for small finite sets.

Matrix representation. If A = {a1,...,am} and B = {b1,...,bn}, the relation matrix M_R is an m × n matrix defined by

M_R[i,j] = 1 if (ai,bj) ∈ R, and 0 otherwise.

For example, if A = {1,2,3} and R = {(1,1),(1,3),(2,2),(3,3)}, then, using the order 1,2,3,

M_R = [[1,0,1],[0,1,0],[0,0,1]].

The matrix is a Boolean representation: entries indicate membership rather than numerical magnitude.

Directed-graph representation. A relation on A can be represented by a directed graph whose vertices are elements of A and whose directed edge a → b exists exactly when aRb. A pair (a,a) appears as a self-loop.

Database representation. A relation is also the theoretical basis of a relational database table. Rows correspond to tuples, and columns correspond to attributes. In database terminology, the word relation has a specialized meaning: a set of tuples with a defined schema.

2. Properties of Relations

For a relation R on a set A, several properties are especially important.

Reflexivity

R is reflexive if every element is related to itself:

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

In a matrix representation, every diagonal entry must be 1. In a directed graph, every vertex must have a self-loop.

Irreflexivity

R is irreflexive if no element is related to itself:

∀a ∈ A, (a,a) ∉ R.

A relation cannot be both reflexive and irreflexive on a nonempty set.

Symmetry

R is symmetric if

∀a,b ∈ A, aRb implies bRa.

For example, the relation “has the same birth month as” is symmetric. In a matrix, symmetry means M_R = M_R^T.

Antisymmetry

R is antisymmetric if

∀a,b ∈ A, (aRb and bRa) implies a = b.

Antisymmetry does not mean that aRb prevents bRa in every case. Both may occur when a = b. The relation ≤ on numbers is antisymmetric because if a ≤ b and b ≤ a, then a = b.

Transitivity

R is transitive if

∀a,b,c ∈ A, (aRb and bRc) implies aRc.

The relation “is an ancestor of” is transitive. If x is an ancestor of y and y is an ancestor of z, then x is an ancestor of z.

Worked Example: Testing Properties

Let A = {1,2,3} and

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

The relation is reflexive because all three diagonal pairs are present. It is not symmetric because (2,3) ∈ R but (3,2) ∉ R. It is not antisymmetric because (1,2) and (2,1) are both present while 1 ≠ 2. It is not transitive because (1,2) and (2,3) are present but (1,3) is absent.

3. Closures of Relations

A closure adds the minimum necessary pairs to make a relation satisfy a desired property. “Minimum” means that no unnecessary pairs are added.

Reflexive Closure

The reflexive closure of R on A is

R_ref = R ∪ {(a,a) : a ∈ A}.

It adds missing self-pairs.

Symmetric Closure

The symmetric closure is

R_sym = R ∪ R^{-1},

where

R^{-1} = {(b,a) : (a,b) ∈ R}.

It adds the reverse of every ordered pair.

Transitive Closure

The transitive closure contains a pair (a,b) whenever there is a path of length at least one from a to b in the directed graph of R. It is often denoted R^+.

For a finite relation, the transitive closure can be computed by repeatedly applying the rule

if (a,b) ∈ R and (b,c) ∈ R, add (a,c),

until no new pairs are produced. A standard matrix-based method is Warshall’s algorithm, which operates in O(n^3) time for an n × n Boolean matrix.

Example of Transitive Closure

Let R = {(1,2),(2,3)}. The pair (1,3) must be added because 1R2 and 2R3. Therefore,

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

If reflexive-transitive closure is required, self-pairs are added as well. This closure is commonly used to represent reachability in graphs, prerequisite dependencies, and hierarchical data.

4. Equivalence Relations and Partitions

An equivalence relation is a relation that is reflexive, symmetric, and transitive. Equivalence relations formalize the idea that two objects should be treated as equivalent under a specified criterion.

Examples include:

• Having the same remainder when divided by n.
• Having the same student identification year.
• Producing identical output under a specified measurement or coding rule.
• Belonging to the same connected component of an appropriately defined structure.

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

[a] = {x ∈ A : xRa}.

The equivalence classes form a partition of A. A partition is a collection of nonempty, pairwise disjoint subsets whose union is A. Every element belongs to exactly one block.

Example: Congruence Modulo 3

On the integers, define aRb if a and b have the same remainder when divided by 3. Equivalently,

a ≡ b (mod 3) if and only if 3 divides a − b.

There are three equivalence classes:

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

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

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

Although the integers are infinite, the number of distinct classes is three. This illustrates how equivalence relations reduce a large set to representative categories.

Equivalence Relations in AI and Data Management

Clustering and deduplication often require an equivalence-like criterion. For instance, records may be grouped when their normalized customer identifiers are identical. However, approximate similarity is not automatically an equivalence relation. Similarity may fail transitivity: record A may be similar to B, and B to C, while A is not sufficiently similar to C. Treating a nontransitive similarity relation as an equivalence relation can produce unstable or misleading clusters.

5. Functions and Mappings

A function f from A to B, written f: A → B, is a relation that assigns to every element of A exactly one element of B. The set A is the domain, B is the codomain, and the set

f(A) = {f(a) : a ∈ A}

is the image or range.

The phrase “exactly one” contains two conditions:

1. Every input in the domain has an output.

2. No input has two different outputs.

Different inputs may have the same output. Therefore, a function need not be one-to-one.

Types of Functions

A function f: A → B is injective or one-to-one if

f(a1) = f(a2) implies a1 = a2.

No two distinct inputs share an output.

It is surjective or onto if every element of B is attained:

∀b ∈ B, ∃a ∈ A such that f(a) = b.

It is bijective if it is both injective and surjective. A bijection establishes a one-to-one correspondence between A and B. For finite sets, a bijection can exist only when the sets have equal cardinality.

Example: Classifying Functions

Let A = {1,2,3}, B = {a,b,c,d}.

Define f(1)=a, f(2)=b, f(3)=c. The function is injective because outputs are distinct, but it is not surjective because d is not used. It is therefore not bijective.

If instead B = {a,b,c}, the same assignment is bijective.

6. Composition and Inverse Functions

If f: A → B and g: B → C, the composition g ∘ f: A → C is defined by

(g ∘ f)(a) = g(f(a)).

The function f is applied first, followed by g. Composition is associative:

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

whenever the functions have compatible domains and codomains. Composition is generally not commutative; usually g ∘ f differs from f ∘ g, and one of these may not even be defined.

Worked Example: Composition

Let f: {1,2,3} → {2,4,6} be f(x)=2x, and let g: {2,4,6} → {1,2,3} be g(y)=y/2. Then

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

In this case, f and g undo one another on the specified sets.

Inverse Functions

A function f: A → B has an inverse function f^{-1}: B → A if and only if f is bijective. The inverse satisfies

f^{-1}(f(a)) = a for every a ∈ A,

and

f(f^{-1}(b)) = b for every b ∈ B.

The inverse relation of any function can be formed by reversing ordered pairs, but it is a function only when the original function is injective and its codomain is restricted to its range. A common error is to assume that every function has an inverse function.

7. Discrete Growth Models

Functions are useful for modeling quantities that change over discrete time periods. The correct model depends on the mechanism producing change.

Arithmetic Growth

If a quantity increases by a constant amount d each period, its value after n periods is

x_n = x_0 + nd,

where x_0 is the initial value, n is a nonnegative integer, and d is the constant increment. This is a linear or arithmetic model.

Geometric Growth

If a quantity is multiplied by a constant factor r each period, then

x_n = x_0r^n.

Here x_0 is the initial value, r is the multiplicative factor, and n is a nonnegative integer. If r > 1, the model represents growth; if 0 < r < 1, it represents decay.

For a percentage growth rate p expressed as a decimal, r = 1+p. For example, 5% growth uses r=1.05, not r=5.

Recurrence Models

Many discrete systems are more naturally defined recursively:

x_{n+1} = F(x_n).

For example, a population with a fixed number of new members added at every step has x_{n+1}=x_n+d. A population multiplied by a fixed factor has x_{n+1}=rx_n.

A recurrence can include several previous values. The Fibonacci sequence is defined by

F_0=0, F_1=1, and F_n=F_{n-1}+F_{n-2} for n≥2.

Recurrence relations are important in algorithm analysis, dynamic programming, digital circuits, and discrete-time simulations.

Comparing Growth Rates

For sufficiently large n, exponential functions such as 2^n grow faster than polynomial functions such as n^2, while polynomial functions grow faster than logarithmic functions such as log n. This hierarchy is central to computational complexity. The comparison assumes fixed positive bases and asymptotic behavior as n tends to infinity; behavior for small n may differ.

8. Relations in Databases and AI Systems

Relational Databases

A database schema defines tables and their attributes. A primary key identifies a tuple uniquely, while a foreign key references a key in another table. These constraints can be interpreted through functions and relations.

For example, each employee may be assigned exactly one department. This is a function from employees to departments. A department, however, may contain many employees, so the reverse association is generally a relation rather than a function. A many-to-many association, such as students enrolling in courses, is represented by a separate junction table containing pairs (student, course).

Functional dependencies have the form X → Y: whenever two tuples agree on attributes X, they must agree on attributes Y. Such dependencies support normalization and help reduce update anomalies.

Classification and Labeling

A classifier can be modeled as a function f: X → Y from an input space X to a set of labels Y. A deterministic classifier assigns one label to each input. If multiple labels are allowed, the output is better modeled as a subset of Y or as a relation between inputs and labels.

A probabilistic classifier does not directly produce a single deterministic mapping. It may produce a probability distribution P(Y|X). The final predicted label may be obtained by a decision rule such as selecting the label with maximum estimated probability. This distinction matters when representing uncertainty.

Knowledge Graphs

Knowledge graphs use entities as vertices and typed relationships as edges. Relations such as “works for,” “located in,” and “is a subclass of” may have different logical properties. A subclass relation is often transitive, whereas “works for” is not necessarily symmetric. Explicitly identifying these properties supports valid inference.

9. Illustrative Case: Student-Course Data Integration

Background. A university integrates admissions, enrollment, and learning-platform data. Student records are stored in one system, while course registrations are stored in another.

Problem. The university must identify which students are enrolled in which courses, ensure that each course has a valid department, and group duplicate student records created by inconsistent formatting.

Analysis. Let S be the set of students and C the set of courses. Enrollment is a relation E ⊆ S × C because one student may enroll in many courses and one course may contain many students. A mapping d: C → D assigns each course to exactly one department, assuming the institutional policy requires a single owning department. The relation “records have the same normalized university identifier” should be tested for reflexivity, symmetry, and transitivity before it is used to form duplicate groups.

Approach. The university creates an enrollment junction table with student and course keys. Referential integrity ensures that every referenced student and course exists. The department mapping is represented by a foreign key. A normalization function converts identifiers to a standard form. Equivalence classes of identical normalized identifiers are reviewed before merging records, because an automated merge may incorrectly combine different individuals.

Outcome. The relational design represents many-to-many enrollment accurately, preserves department ownership, and makes duplicate detection auditable. Ambiguous matches are sent for human review rather than merged automatically.

Learning Points. The case illustrates that relation type determines data structure, function properties determine permissible mappings, and equivalence classes are useful only when the underlying criterion genuinely defines an equivalence relation. It also demonstrates that mathematical correctness does not remove the need for operational review and governance.

10. Challenges, Limitations, and Best Practices

A mathematical relation is only as meaningful as its definition. Ambiguous labels, incomplete data, changing schemas, and inconsistent identifiers can make a formally correct model operationally unreliable.

Important limitations include:

• A binary relation may be too simple for relationships involving time, uncertainty, or multiple roles.
• A deterministic function can conceal uncertainty or multiple valid outcomes.
• Equivalence-based grouping may be inappropriate when similarity is not transitive.
• Closure operations can add inferred relationships that are logically valid under the model but undesirable in practice.
• Large transitive-closure computations may require substantial storage or specialized graph algorithms.

Best practices include defining domains and codomains explicitly, documenting assumptions, distinguishing range from codomain, validating relation properties, preserving provenance for inferred links, and testing data constraints before deployment. In AI systems, uncertainty should be represented rather than silently converted into a deterministic label.

Ethical and Governance Considerations

Relations used in classification and record linkage can affect access to education, employment, credit, or public services. Incorrect equivalence decisions may merge individuals or exclude legitimate records. A relation that encodes social categories may reproduce historical bias. Therefore, systems should provide traceable definitions, access controls, correction mechanisms, privacy protection, and human review for high-impact decisions. Data minimization is important: storing a relation does not justify collecting information unrelated to its purpose.

Chapter Summary

Relations are subsets of Cartesian products and provide a general framework for representing associations. They can be expressed as ordered pairs, Boolean matrices, directed graphs, or database tables. Reflexivity, symmetry, antisymmetry, and transitivity are fundamental properties used to classify relations and reason about them.

Closures extend relations minimally to satisfy selected properties. Equivalence relations are reflexive, symmetric, and transitive; their equivalence classes form partitions. Functions are relations assigning exactly one output to every input. Injective, surjective, and bijective functions describe increasingly strong mapping properties. Composition combines compatible functions, and inverse functions exist precisely for bijections between the stated domain and codomain.

Discrete growth models include arithmetic, geometric, and recursive forms. These models support algorithm analysis, simulation, databases, knowledge graphs, and AI classification. Effective professional practice requires clear definitions, valid assumptions, careful representation of uncertainty, data governance, and awareness of ethical 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 first components associated by a relation or function.

Codomain: The declared target set of a function.

Range: The set of outputs actually attained by a function.

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

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.

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

Equivalence relation: A reflexive, symmetric, and transitive relation.

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

Partition: A collection of nonempty, disjoint blocks whose union is the whole set.

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

Injective function: A function with no shared output among distinct inputs.

Surjective function: A function whose range equals its codomain.

Bijective function: A function that is both injective and surjective.

Composition: The application of one function after another.

Inverse function: A function that reverses a bijective mapping.

Recurrence relation: A rule defining sequence values from earlier values.

Review Questions

Short Answer Questions

1. What is the difference between a function’s codomain and its range?

2. State the four principal properties used to classify relations.

3. Define an equivalence relation.

4. When does a function have an inverse function?

5. What is the difference between arithmetic and geometric growth?

Long Answer Questions

1. Explain ordered-pair, matrix, directed-graph, and database representations of relations.

2. Describe reflexive, symmetric, and transitive closures and explain one application of each.

3. Explain how equivalence classes produce a partition, using congruence modulo n as an example.

4. Compare injective, surjective, and bijective functions, including their implications for inverses.

5. Discuss the use of relations and functions in relational database design.

Analytical / Application Questions

1. Let A={1,2,3,4} and R={(1,2),(2,3),(3,4)}. Determine the transitive closure R+ and explain the paths that justify each added pair.

2. A university stores student-course enrollment data. Decide which associations should be modeled as functions and which should be modeled as relations, and justify your decisions.

3. A record-linkage system defines two records as equivalent when their names differ by at most one character. Analyze whether this criterion necessarily defines an equivalence relation and explain the consequences for automated grouping.

Multiple Choice Questions with Answers

Question 1

Which condition defines a function from A to B?

A. Every element of B has exactly one preimage

B. Every element of A has exactly one image in B

C. Every element of A has at least two images in B

D. The relation must be symmetric

Correct Answer: B. Every element of A has exactly one image in B

Question 2

A relation on A is reflexive when it contains:

A. (a,b) for every distinct a and b

B. (b,a) whenever it contains (a,b)

C. (a,a) for every a in A

D. No ordered pairs with equal components

Correct Answer: C. (a,a) for every a in A

Question 3

Which property requires that aRb and bRa imply a=b?

A. Symmetry

B. Transitivity

C. Reflexivity

D. Antisymmetry

Correct Answer: D. Antisymmetry

Question 4

If R={(1,2),(2,3)}, which pair must be added to its transitive closure?

A. (2,1)

B. (3,2)

C. (1,3)

D. (1,1)

Correct Answer: C. (1,3)

Question 5

An equivalence relation must be:

A. Reflexive, symmetric, and transitive

B. Irreflexive, symmetric, and transitive

C. Reflexive, antisymmetric, and nontransitive

D. Only symmetric

Correct Answer: A. Reflexive, symmetric, and transitive

Question 6

A function is bijective if it 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 7

If f(x)=2x and g(x)=x+1, what is (g∘f)(3)?

A. 6

B. 7

C. 8

D. 9

Correct Answer: B. 7

Question 8

For x0=5 and multiplicative factor r=2, the geometric model x_n=x0r^n gives x3 equal to:

A. 15

B. 20

C. 30

D. 40

Correct Answer: D. 40

Question 9

Which database association is naturally many-to-many?

A. Each course has one course code

B. Each course belongs to one department

C. Students enrolling in courses

D. Each person having one date of birth

Correct Answer: C. Students enrolling in courses

Question 10

Why may approximate similarity fail to define an equivalence relation?

A. It is always reflexive but never symmetric

B. It may fail transitivity

C. It cannot be represented by ordered pairs

D. It always produces a bijection

Correct Answer: B. It may fail transitivity