1. Mathematical Foundations, Logic and Notation

Introduction and Context

Machine learning is often presented through algorithms, software libraries, and data. Beneath these visible components lies a mathematical language that makes models precise. Sets describe collections of data and possible outcomes; functions describe transformations; sequences describe iterative procedures and observations; limits explain convergence; logarithms and summations support objectives, probabilities, and complexity analysis; logic and proof establish whether claims are valid; and asymptotic notation describes how computational demands grow.

These ideas are not merely formal prerequisites. A machine-learning practitioner uses them when defining a feature space, specifying a hypothesis class, interpreting a loss function, proving a property of an algorithm, analysing convergence, or deciding whether a proposed computation is feasible at scale. Mathematical notation also reduces ambiguity. The statement “the model maps inputs to predictions” becomes a precise mapping f: X -> Y, while “training improves performance” can be expressed through an optimization sequence and an objective function.

This chapter develops a working foundation rather than treating mathematics as symbolic manipulation alone. The emphasis is on meaning, structure, reasoning, and modelling conventions. Examples are drawn from machine learning, data analysis, and computing so that abstract concepts can be connected to professional practice.

Learning Objectives

After studying this chapter, a student should be able to:

1. distinguish sets, subsets, Cartesian products, relations, functions, and mappings;

2. describe sequences, limits, logarithms, products, and summations using correct notation;

3. formulate statements using propositions, predicates, quantifiers, and logical connectives;

4. select and apply direct, contradiction, contrapositive, induction, and counterexample-based reasoning;

5. interpret Big-O, Big-Omega, and Big-Theta notation in algorithmic and statistical contexts;

6. translate an informal machine-learning situation into a mathematically coherent model;

7. identify common errors involving domains, quantifiers, dimensions, limits, and asymptotic claims.

The Mathematical Language of Machine Learning

A mathematical model begins by specifying objects and relationships. Let X denote an input space, Y an output space, and f a function. A supervised-learning model is commonly written as

f: X -> Y.

For a dataset of n observations, one may write

D = {(x_i, y_i) | i in {1, 2, ..., n}},

where x_i is an input and y_i is its target. If each input has d numerical features, then x_i belongs to R^d. The notation R^d represents the Cartesian product of d copies of the real numbers and is therefore a d-dimensional vector space.

A parameterized model is written f_theta, where theta belongs to a parameter space Theta. Training attempts to select a parameter value, often by minimizing an empirical loss:

J(theta) = (1/n) sum from i=1 to n of L(f_theta(x_i), y_i).

This single expression illustrates several conventions: subscripts identify observations, a function receives arguments, a summation aggregates contributions, and equality defines a quantity. Mathematical literacy requires understanding not only what symbols mean individually but also how their scope and relationships are determined.

Sets, Membership, and Operations

A set is a well-defined collection of distinct objects. We write x ∈ A when x is an element of A and x ∉ A otherwise. A set may be described by listing elements, such as A = {1, 2, 3}, or by a rule, such as B = {x ∈ R | x > 0}. The second form is called set-builder notation.

The empty set, written ∅, contains no elements. The universal set depends on context. In a classification task, the label set might be Y = {cat, dog, horse}; in a binary task it might be {0,1}. A set A is a subset of B, written A ⊆ B, if every element of A is also an element of B. Proper inclusion, A ⊂ B, usually indicates that A is a subset but not equal to B, although conventions vary and should be stated when precision matters.

Important operations include:

• Union: A ∪ B contains elements in A, in B, or in both.
• Intersection: A ∩ B contains elements common to A and B.
• Difference: A \ B contains elements in A but not B.
• Complement: A^c contains elements in the relevant universal set that are not in A.
• Cardinality: |A| is the number of elements in a finite set.

Two sets are equal precisely when they have the same elements. The order in which elements are listed is irrelevant, and repetition does not create new elements. Thus {1,2,3} = {3,2,1}.

The Cartesian product A × B is the set of ordered pairs (a,b) with a ∈ A and b ∈ B. If A has m elements and B has n elements, then A × B has mn elements. Feature vectors, input-output pairs, and combinations of hyperparameter choices can all be represented through Cartesian products.

Relations and Functions

A relation R from A to B is a subset of A × B. If (a,b) ∈ R, we may write aRb. Relations can express similarity, preference, connectivity, or correspondence. A relation on A is often examined for properties such as reflexivity, symmetry, antisymmetry, and transitivity.

A function is a special relation in which every element of the domain is associated with exactly one element of the codomain. We write f: A -> B. The set A is the domain, B is the codomain, and the set of actual outputs is the range or image, f(A). The range need not equal the codomain.

For example, f: R -> R defined by f(x)=x^2 has range [0,∞), although its codomain is R. This distinction matters in classification: a model may be declared as f: X -> R, while a thresholding rule later converts real-valued scores into labels.

A function is injective if distinct inputs have distinct outputs. It is surjective if every element of the codomain is achieved by at least one input. It is bijective if it is both injective and surjective. A bijection has an inverse function f^(-1), but a general function does not necessarily have one. If f: A -> B and g: B -> C, their composition is (g ∘ f)(a)=g(f(a)). Composition is central to neural networks, where layers are composed transformations.

A mapping may be many-to-one, as with a classifier assigning several inputs to the same class. It cannot be one-to-many if it is to remain a function. Confusing a function with a general relation is a frequent modelling error.

Sequences, Indexing, and Limits

A sequence is an ordered list, usually represented as (a_n) or {a_n}_{n=1}^∞. Formally, a sequence is a function from the positive integers to another set. In iterative optimization, theta_0, theta_1, theta_2, ... is a sequence of parameter values generated by an algorithm.

A sequence (a_n) converges to L if its terms become arbitrarily close to L as n increases. The formal definition is:

For every epsilon > 0, there exists N such that n ≥ N implies |a_n − L| < epsilon.

We write lim as n approaches infinity of a_n = L. The definition emphasizes that convergence concerns eventual behaviour, not whether early terms are close. For example, a_n = 1/n converges to 0, while a_n = (-1)^n does not converge because it continues to alternate between -1 and 1.

A function limit is defined similarly. The statement lim as x approaches a of f(x)=L means that f(x) can be made arbitrarily close to L by taking x sufficiently close to a, without requiring x=a. This distinction is important when a function is undefined at a point but has stable nearby behaviour.

Continuity at a requires f(a) to be defined and equal to the limit as x approaches a of f(x). Many optimization results rely on continuity, differentiability, or weaker regularity conditions. These assumptions should not be silently transferred from one model to another.

A sequence may be bounded if there is a constant M such that |a_n| ≤ M for all n. Monotonicity and boundedness can help establish convergence, but boundedness alone does not guarantee convergence: (-1)^n is bounded but divergent.

Logarithms, Exponents, and Summation Notation

The logarithm log_b(x) is the inverse of exponentiation: log_b(x)=y exactly when b^y=x, where b>0 and b≠1. Important identities include

log_b(xy)=log_b(x)+log_b(y),

log_b(x/y)=log_b(x)−log_b(y),

and log_b(x^r)=r log_b(x).

In machine learning, natural logarithms, written ln or log, occur in likelihoods, entropy, cross-entropy, and numerical transformations. The base changes scale but not the essential ordering: log_a(x)=log_b(x)/log_b(a). Since logarithm is increasing for bases greater than one, maximizing log likelihood is equivalent to maximizing likelihood, while the logarithm often converts products into sums and improves numerical stability.

A summation is written

sum from i=1 to n of a_i.

The index i is a dummy variable; changing it to j does not alter the value. Linearity gives sum of (a_i+b_i) = sum of a_i + sum of b_i and sum of c a_i = c sum of a_i. Common formulas include sum from i=1 to n of 1 = n and sum from i=1 to n of i = n(n+1)/2.

Nested sums require attention to scope. The expression sum over i of sum over j of a_ij may represent an aggregate over a matrix, whereas a normalized average includes a factor such as 1/n. Omitting normalization can change the scale of a loss and affect optimization behaviour.

Products are denoted by the capital Greek letter Pi: product from i=1 to n of a_i. Likelihoods for independent observations are products of individual probabilities; taking logarithms turns them into sums of log probabilities.

Mathematical Logic and Quantifiers

A proposition is a declarative statement that is either true or false. “The dataset contains 500 records” is a proposition; “train the model” is not. If P and Q are propositions, the principal logical connectives are:

• not P, written ¬P;
• P and Q, written P ∧ Q;
• P or Q, written P ∨ Q, usually inclusive;
• if P then Q, written P -> Q;
• P if and only if Q, written P ↔ Q.

The implication P -> Q is false only when P is true and Q is false. It does not assert that P causes Q, nor that Q implies P. The converse of P -> Q is Q -> P and may have a different truth value. The contrapositive is ¬Q -> ¬P and is logically equivalent to the original implication.

Predicates are statements containing variables, such as P(x): x is an even integer. Quantifiers express scope. The universal quantifier ∀ means “for every,” while the existential quantifier ∃ means “there exists.” The statements ∀x ∃y P(x,y) and ∃y ∀x P(x,y) are generally not equivalent. In machine learning, this distinction separates “for every input there exists a suitable parameter” from “there exists one parameter suitable for every input.”

Negation changes quantifiers: ¬(∀x P(x)) is equivalent to ∃x ¬P(x), and ¬(∃x P(x)) is equivalent to ∀x ¬P(x). This principle is useful when testing universal claims about model performance. One counterexample is enough to refute a universal statement.

Proof Techniques for Machine-Learning Reasoning

A direct proof starts with the assumptions and derives the conclusion through valid steps. To prove that the sum of two even integers is even, write them as 2m and 2n; their sum is 2(m+n), which is even.

A proof by contrapositive proves P -> Q by proving ¬Q -> ¬P. This is useful when the conclusion is difficult to handle directly. A proof by contradiction assumes the claim is false and derives an impossibility. Contradiction must be used carefully: an apparent computational failure is not automatically a logical contradiction.

Mathematical induction proves a statement for all positive integers. It has a base case and an inductive step: assuming the statement for k, prove it for k+1. Induction is relevant to recursive algorithms, cumulative sums, and properties of tree-structured models.

A counterexample disproves a universal claim. The claim “every bounded sequence converges” is disproved by the bounded sequence (-1)^n. In applied work, a counterexample may reveal that a model guarantee requires an omitted assumption, such as convexity, boundedness, independence, or differentiability.

Proof is different from empirical testing. Experiments can provide evidence that a claim may hold on sampled data; they do not establish a universal theorem unless the relevant mathematical conditions are satisfied.

Asymptotic Notation and Computational Growth

Asymptotic notation describes how a quantity behaves as an input size n becomes large. It abstracts away constants and lower-order terms, allowing algorithms to be compared by growth rate.

We say f(n) is O(g(n)) if there exist constants c>0 and n_0 such that 0 ≤ f(n) ≤ c g(n) for every n ≥ n_0. Big-O is an asymptotic upper bound. We say f(n) is Ω(g(n)) if f(n) ≥ c g(n) for sufficiently large n, for some positive c. Big-Theta, Θ(g(n)), means both O(g(n)) and Ω(g(n)); it characterizes a tight asymptotic bound.

For example, 3n^2+7n+4 is Θ(n^2), because the quadratic term dominates for large n. A linear scan is O(n), binary search is O(log n) when its assumptions hold, and comparing every pair of n objects is typically Θ(n^2). The base of a logarithm is irrelevant in Big-O notation because different constant bases differ only by a multiplicative constant.

Asymptotic complexity may refer to time, memory, communication, or sample size. A training procedure with cost Θ(nd) may be practical for moderate n and d but problematic when both grow. Complexity notation does not provide exact runtime, hardware-independent performance, or quality guarantees. It also does not justify claiming O(n) when a nested loop performs n^2 operations.

The distinction between worst-case, average-case, amortized, and expected complexity should be stated. A randomized algorithm may have expected complexity O(n), even if particular runs take longer. Similarly, an algorithm can be asymptotically efficient yet slow for realistic small inputs because of large constants.

Mathematical Modelling Conventions

A sound model begins with explicit assumptions. Identify the objects, their spaces, the indices, and the relationships among them. For example, in a binary classifier, x_i ∈ R^d, y_i ∈ {0,1}, and f_theta: R^d -> [0,1] may represent a predicted probability. The loss L must have a compatible domain, such as L: [0,1] × {0,1} -> R.

Dimensions must be checked. If X is an n × d data matrix, its rows may represent observations and columns features; alternatively, a convention may use columns as observations. Both are valid, but mixing them produces incorrect matrix products and misleading interpretations.

Indices should have clear ranges. Writing x_i without stating 1 ≤ i ≤ n leaves scope ambiguous. Random variables should be distinguished from observed values, often by using uppercase letters for variables and lowercase letters for realizations. Parameters, estimators, and estimates should not be treated as interchangeable: theta may denote an unknown parameter, theta-hat an estimator, and theta-hat observed after training.

A model is not only an equation. It includes assumptions, an objective, constraints, data-generating interpretation, and a decision rule. Good notation exposes these components and makes it possible to examine whether a conclusion follows from the assumptions.

An Illustrative Case: Verifying a Scalable Classification Pipeline

Background

A fictional online service receives customer requests represented by d numerical features and assigns one of K categories. The engineering team proposes a nearest-centroid classifier for rapid prediction.

Situation and Problem

The proposed training procedure computes one centroid per category. Prediction compares a new vector with all K centroids using Euclidean distance. The team claims that the system has linear complexity in both the number of training records n and the number of features d.

Analysis

Let D={(x_i,y_i)} with x_i ∈ R^d and y_i ∈ {1,...,K}. For class k, the centroid is

mu_k = (1/n_k) sum over i such that y_i=k of x_i.

Computing all centroids requires examining each feature of each observation, giving Θ(nd) arithmetic operations. Prediction requires computing K distances, each involving d coordinates, so the prediction cost is Θ(Kd), not simply Θ(d) unless K is treated as a fixed constant. The team’s claim is therefore incomplete.

The model is a function f: R^d -> {1,...,K}, but ties between centroids must be resolved by a specified rule. The training data and labels also define the domain of the centroid calculation: a class with n_k=0 makes the formula undefined.

Approach and Solution

The team documents the assumptions that K is fixed, every class in the training set has at least one observation, and all features have been placed on a justified scale. It reports training complexity as Θ(nd), prediction complexity as Θ(Kd), and memory complexity as Θ(Kd) for storing centroids. If K is large, an indexing or approximate nearest-centroid method may be considered, but its accuracy and complexity must be analysed separately.

Outcome

The revised specification is mathematically precise and avoids overstating scalability. It also identifies a governance concern: a compact model is not automatically fair or reliable. Feature construction, class imbalance, and systematic errors require empirical evaluation.

Learning Points

The case demonstrates that notation clarifies domains, edge conditions, dimensionality, and complexity. It also shows why asymptotic statements must identify which quantities grow and which are treated as fixed.

Common Errors, Limitations, and Professional Considerations

Several mistakes recur in mathematical machine learning. Treating the codomain as the range can lead to incorrect claims about outputs. Reversing quantifiers can change a theorem completely. Assuming a sequence converges because it is bounded ignores oscillation. Applying logarithms to zero or negative values violates the real-valued domain. Omitting an index or normalization factor can alter an objective. Calling every upper bound a tight bound confuses O with Θ.

There are also modelling limitations. A formal expression may be internally consistent while representing the wrong real-world process. Statistical assumptions such as independence, identical distribution, or stationarity may be unrealistic. An asymptotic guarantee may not describe finite-sample behaviour. A proof may establish optimization convergence without establishing predictive accuracy or fairness.

Professional practice requires transparent assumptions, reproducible notation, dimensional checks, and explicit treatment of edge cases. When mathematical models influence lending, healthcare, employment, or public services, governance requires more than computational correctness. Stakeholders need interpretable definitions, documented limitations, auditability, and evidence that performance is not being reported selectively.

Emerging Relevance in AI and ML

Modern machine-learning systems increasingly use symbolic and mathematical tools together. Automatic differentiation manipulates compositions of functions; probabilistic programming relies on distributions, products, and logarithms; formal verification attempts to prove properties of neural networks; and complexity analysis informs the deployment of large models. Automated theorem provers and proof assistants can check formal arguments, while program-analysis tools can detect dimension and type inconsistencies.

These technologies do not remove the need for mathematical understanding. They make precise specification more important because an automated system can verify only the statement that has actually been formalized. The direction of current practice is therefore toward models that combine numerical performance with explicit assumptions, verifiable properties, and resource-aware design.

Best Practices for Mathematical Work in Machine Learning

1. Define every symbol, its domain, and its index range before using it.

2. Distinguish a set, a vector, a random variable, a parameter, and an observed value.

3. Check dimensions and function compatibility at every composition.

4. State assumptions such as nonzero denominators, differentiability, independence, or fixed K.

5. Use quantifiers carefully and test universal claims with counterexamples.

6. Separate empirical evidence from mathematical proof.

7. Report whether complexity is worst-case, expected, amortized, time, or memory complexity.

8. Use logarithms and normalization consistently in objectives.

9. Treat edge cases—empty classes, zero probabilities, ties, and undefined limits—explicitly.

10. Interpret formal results in relation to data quality, deployment conditions, ethics, and governance.

Chapter Summary

Mathematical foundations provide the language through which machine-learning problems are specified and analysed. Sets and Cartesian products define data spaces; relations describe associations; functions and compositions represent models and pipelines. Sequences and limits support the analysis of iterative algorithms and convergence. Logarithms transform products into sums and underpin likelihood-based objectives, while summations express aggregation and empirical risk. Logic and quantifiers make claims precise, and proof techniques establish or refute them. Big-O, Big-Omega, and Big-Theta describe asymptotic growth but must be interpreted with respect to the variable that grows and the type of complexity being measured. Finally, modelling conventions—explicit domains, indices, dimensions, assumptions, and edge cases—connect formal mathematics with responsible professional practice in AI and ML.

Key Terms

Set: A well-defined collection of distinct objects.

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

Cartesian product: The set of ordered combinations formed from two or more sets.

Relation: A subset of a Cartesian product that specifies associations between elements.

Function: A relation assigning exactly one output to each domain element.

Domain: The set of valid inputs of a function.

Codomain: The declared set in which function outputs lie.

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

Bijection: A function that is both injective and surjective.

Composition: The application of one function to the output of another.

Sequence: An ordered function or list indexed, commonly, by positive integers.

Limit: The value a function or sequence approaches under a specified limiting process.

Logarithm: The inverse operation of exponentiation.

Summation: An indexed addition of terms.

Proposition: A declarative statement with a truth value.

Quantifier: A logical symbol indicating how broadly a predicate applies.

Contrapositive: The logically equivalent form ¬Q -> ¬P of P -> Q.

Counterexample: An instance that disproves a universal claim.

Big-O notation: An asymptotic upper bound on growth.

Big-Theta notation: A tight asymptotic bound describing matching upper and lower growth rates.

Review Questions

Short Answer Questions

1. Distinguish the codomain of a function from its range.

2. What is the difference between a relation and a function?

3. State the formal idea behind convergence of a sequence.

4. Why are logarithms useful in likelihood-based machine-learning objectives?

5. What does Big-Theta notation communicate?

Long Answer Questions

1. Explain set operations, Cartesian products, and their relevance to feature and label spaces.

2. Compare injective, surjective, and bijective functions with suitable machine-learning examples.

3. Explain universal and existential quantifiers and show why changing their order can change a statement.

4. Describe direct proof, proof by contradiction, contrapositive proof, induction, and counterexample-based reasoning.

5. Develop a mathematically precise specification for a supervised-learning dataset, model, loss, and training objective.

Analytical / Application Questions

1. A model is written f: R^d -> R but is used as a probability predictor. What additional range restriction and interpretation should be specified?

2. An algorithm processes every pair of n observations and performs d-dimensional comparisons. Derive a suitable asymptotic time complexity and explain which variables affect it.

3. A colleague claims that every bounded sequence converges. Construct a counterexample and explain what additional conditions might be needed for convergence.

22. Multiple Choice Questions with Answers

Question 1

Which statement correctly distinguishes the range from the codomain of a function?

A. The range is always larger than the codomain.

B. The range contains the outputs actually attained, while the codomain is the declared output set.

C. The codomain contains only outputs that are actually attained.

D. Range and codomain are different names for the domain.

Correct Answer: B. The range contains the outputs actually attained, while the codomain is the declared output set.

Question 2

If f: A -> B and g: B -> C, which expression correctly defines their composition?

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

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

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

D. (g ∘ f)(a)=a for every a

Correct Answer: B. (g ∘ f)(a)=g(f(a))

Question 3

Which sequence is bounded but does not converge?

A. a_n=1/n

B. a_n=1−1/n

C. a_n=(-1)^n

D. a_n=1/n^2

Correct Answer: C. a_n=(-1)^n

Question 4

Why is the logarithm of a likelihood commonly used in machine learning?

A. It changes sums into products and reverses order.

B. It converts products of probabilities into sums and preserves maximizers.

C. It permits logarithms of negative probabilities.

D. It guarantees that every model is convex.

Correct Answer: B. It converts products of probabilities into sums and preserves maximizers.

Question 5

What is the logical contrapositive of P -> Q?

A. Q -> P

B. ¬P -> ¬Q

C. ¬Q -> ¬P

D. P ↔ Q

Correct Answer: C. ¬Q -> ¬P

Question 6

Which statement is sufficient to disprove a claim of the form “for every x, P(x)”?

A. Showing P(x) for one value of x

B. Finding one x for which P(x) is false

C. Showing that x belongs to a large set

D. Replacing the universal quantifier with an existential one

Correct Answer: B. Finding one x for which P(x) is false

Question 7

The expression 3n^2+7n+4 belongs to which asymptotic class?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n^2)

Correct Answer: D. Θ(n^2)

Question 8

A classifier compares a d-dimensional input with K centroids. What is the usual prediction complexity?

A. Θ(K+d)

B. Θ(Kd)

C. Θ(nK) regardless of d

D. Θ(log K) regardless of d

Correct Answer: B. Θ(Kd)

Question 9

Which statement about implication is correct?

A. P -> Q and Q -> P always have the same truth value.

B. P -> Q is false whenever P is false.

C. P -> Q is false only when P is true and Q is false.

D. P -> Q asserts that P causes Q.

Correct Answer: C. P -> Q is false only when P is true and Q is false.

Question 10

Why must a mathematical machine-learning model specify index ranges and dimensions?

A. To make notation decorative and longer

B. To prevent ambiguity and detect incompatible operations

C. To ensure every algorithm has constant complexity

D. To replace empirical evaluation

Correct Answer: B. To prevent ambiguity and detect incompatible operations