Mathematical Language, Logic and Foundations

Introduction

Data science is often presented through algorithms, software libraries and visualizations. Beneath each of these lies a mathematical language for describing objects, relationships, uncertainty and computation. A model is not merely code: it is a formal mapping from inputs to outputs under specified assumptions. A dataset is not merely a table: it can be represented as a set, a function, a relation, a sequence or a point in a high-dimensional space.

This chapter develops the foundational vocabulary needed to formulate data-science problems rigorously. It introduces sets, relations, functions, mappings, sequences, summations, mathematical logic, proof methods, asymptotic notation and complex numbers. The emphasis is not on symbolic manipulation alone, but on interpretation: what a statement means, when a formula applies, and how formal reasoning prevents ambiguity in analysis and implementation.

Learning Objectives

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

1. Represent data objects using sets, subsets, Cartesian products and set operations.
2. Distinguish relations, functions, injections, surjections and bijections.
3. Use sequences, indexed notation and summations to express data-processing operations.
4. Translate between natural language and propositional or predicate logic.
5. Construct direct, contrapositive, contradiction and induction proofs.
6. Interpret Big-O, Big-Ω and Big-Θ notation and apply them to algorithmic complexity.
7. Perform basic operations with complex numbers and identify their role in Fourier and signal-based methods.
8. Communicate assumptions, domains, codomains and conclusions precisely in data-science work.

1. Mathematical Objects and Notation

A mathematical object has a name, a type and a set of permissible values. For example, a feature vector may be written as x ∈ ℝ^p, meaning that x is a vector of p real-valued components. The symbol ∈ means “is an element of.”

Common number systems are:

A statement such as x ∈ ℝ is meaningful only because a domain has been specified. In machine learning, failing to distinguish a scalar from a vector, or a categorical label from a numerical measurement, can produce invalid operations and misleading conclusions.

Variables, constants and parameters

A variable represents an object whose value may vary. A constant is fixed within a stated problem. A parameter is a quantity treated as fixed while a model is evaluated, but which may be estimated during training. In the linear model y = β₀ + β₁x, x is an input, y is the response, and β₀, β₁ are parameters.

Equality and definition

The symbol = asserts equality. A definition is often indicated by ≔, as in μ ≔ (1/n)∑_i=1ⁿ x_i. Equality should not be confused with approximation: ≈ indicates that two quantities are close under an understood criterion.

2. Sets and Set Operations

A set is a collection of distinct objects. The objects are called elements or members. Sets may be listed, such as A = {2,4,6}, or described by a rule, such as B = {x ∈ ℝ : x ≥ 0}. The colon means “such that.” The empty set is ∅, and the cardinality of a finite set A is written |A|.

A set A is a subset of B, written A ⊆ B, if every element of A is also in B. The power set 𝒫(A) is the set of all subsets of A. If |A| = n, then |𝒫(A)| = 2ⁿ.

Important operations are:

The complement of A depends on a universal set U and is A^c = U \ A. The union and intersection obey commutative, associative and distributive laws. De Morgan’s laws are especially useful in query construction:

These identities assume that all complements are taken relative to the same universal set.

Cartesian products

The Cartesian product of sets A and B is

An ordered pair preserves order, so (a,b) ≠ (b,a) in general. A data record with a customer identifier, age and purchase amount may be modeled as an element of CustomerID × ℕ × ℝ. For n feature domains X₁,…,X_n, the record space is X₁ × … × X_n.

Worked example: filtering a population

Suppose U is a population of 10,000 customers, A is the set who purchased in the last month, and B is the set who opened a promotional email. If |A|=2,400, |B|=3,000 and |A∩B|=900, then

Thus 4,500 customers satisfy at least one condition, while 5,500 satisfy neither, assuming U contains exactly these customers and the conditions are measured consistently.

3. Relations and Functions

A relation from A to B is any subset of A × B. A relation can associate one element with many elements, many elements with one element, or no element at all. For example, “customer a viewed product b” is a relation between customers and products.

A function, or mapping, f:A→B, is a relation with exactly one output in B for every input in A. The set A is the domain, B is the codomain, and the image or range is

The codomain need not equal the image. This distinction matters when a classifier is specified as mapping observations into all possible labels, even if some labels do not occur in a particular sample.

A function is injective if distinct inputs have distinct outputs:

It is surjective if every element of the codomain is attained by at least one input. It is bijective if it is both injective and surjective. A bijection has an inverse function f^-1:B→A. An inverse image, however, can be defined even when an inverse function does not exist:

This is useful for describing the observations classified into a set of labels.

Composition

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

Composition is associative, but generally not commutative: g∘f need not equal f∘g. In a data pipeline, normalization followed by dimensionality reduction is generally different from dimensionality reduction followed by normalization.

Partial functions and missing data

A partial function may be undefined for some domain elements. A preprocessing rule that divides by a feature’s standard deviation is undefined when that standard deviation is zero. Rather than silently treating this as a valid function, the analyst should specify an exception, a fallback rule or a restricted domain. Missing values also require an explicit policy; they are not automatically equal to zero or to the mean.

4. Sequences, Indexing and Summation

A sequence is an ordered list, commonly represented as (a_n)_n=1^∞. It can be viewed as a function from the positive integers to a target set. In a dataset, x₁,…,x_n may represent observations ordered by acquisition time, while x_t denotes the observation at time t.

A finite sum is written

The index i is a dummy variable; it may be renamed without changing the result. A weighted mean is

where weights satisfy w_i ≥ 0 and at least one weight is positive. If all weights are equal, this reduces to the arithmetic mean. The units of x̄_w are the same as those of x_i, because the weights cancel dimensionally.

A finite geometric sum, for r ≠ 1, is

For r=1, the sum is n. This condition must be stated because the displayed fraction becomes 0/0 when r=1.

Double sums appear in matrices, grids and pairwise calculations:

When the sum is finite, the order of summation can be exchanged. This permits alternative implementations, although computational cost and memory access patterns may differ.

Recurrences

A recurrence defines a term using earlier terms. For example,

where a and b are constants. If b ≠ 1, its closed form is

for integer t ≥ 0. The expression follows by repeated substitution and is useful for analyzing iterative algorithms and time-series dynamics. If |b|<1, then b^t→0 and the sequence approaches the fixed point a/(1-b).

5. Logic and Quantifiers

Logic provides rules for combining statements. A proposition is a declarative statement that is either true or false. Let P and Q be propositions.

The implication P⇒Q is false only when P is true and Q is false. It does not assert that P causes Q. Causal claims require additional assumptions and evidence.

A predicate is a statement containing a variable, such as P(x): x>0. Quantifiers express scope:

means that P(x) holds for every element of A, while

means that at least one element satisfies it. The order of quantifiers matters. In general, ∀x∃y P(x,y) does not imply ∃y∀x P(x,y). The first permits a different y for each x; the second requires one common y.

Negating quantified statements

Negation reverses quantifiers:

Thus, the negation of “every model passes validation” is “at least one model fails validation,” not “no model passes validation.”

6. Proof Methods and Mathematical Communication

Proof is a reasoned argument establishing that a conclusion follows from definitions, assumptions and previously justified results. In professional data science, proof-like reasoning supports validation of transformations, correctness of algorithms and interpretation of guarantees.

Direct proof

To prove P⇒Q directly, assume P and derive Q. For example, if m and n are even integers, write m=2r and n=2s for integers r,s. Then m+n=2(r+s), so their sum is even.

Contrapositive

An implication is logically equivalent to its contrapositive:

To prove that a nonzero real number has a nonzero square, one may prove the contrapositive: if x²=0, then x=0. This method is often effective when the conclusion is difficult to establish directly.

Proof by contradiction

Assume the claim is false and derive an impossibility. The contradiction must arise from the assumption together with accepted premises, not from an informal appeal to intuition.

Mathematical induction

For a statement P(n) over integers n≥n₀, induction requires:

1. Base case: prove P(n₀).
2. Inductive hypothesis: assume P(k) for an arbitrary k≥n₀.
3. Inductive step: prove P(k+1).

Induction is appropriate for recursive algorithms and finite-sum identities. It does not prove statements over arbitrary real values unless an additional argument is supplied.

Counterexamples

A universal claim can be disproved by one valid counterexample. The assertion “all functions are invertible” is false because f(x)=x² on ℝ maps both 1 and −1 to 1 and is therefore not injective. A counterexample must satisfy the stated domain and assumptions.

7. Asymptotic Notation and Algorithmic Growth

Asymptotic notation describes growth as an input-size variable n becomes large. It abstracts away machine-dependent constants and lower-order terms, but it does not automatically describe actual execution time for small inputs.

A function f(n) is O(g(n)) if there exist constants c>0 and n₀ such that

assuming g(n) is eventually nonnegative. Big-O is an upper bound, not necessarily a tight bound.

It is Ω(g(n)) if there exist c>0 and n₀ such that

It is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)). Equivalently, there are positive constants c₁,c₂ and n₀ such that

For example, 3n²+7n+2 = Θ(n²). The quadratic term eventually dominates, but the exact operation count may still matter in deployment.

Typical growth classes satisfy, for sufficiently large n,

The symbol ≺ informally means “grows strictly more slowly than.” The comparison depends on the computational model and on whether arithmetic operations are treated as constant-time. Multiplying very large integers, for example, may not have constant cost.

Space complexity measures memory consumption, while time complexity measures computational work. A streaming algorithm may reduce space from O(n) to O(1) while making multiple passes over data. Complexity analysis should therefore state the resource being measured and the relevant input dimensions, such as number of records, features and nonzero entries.

8. Complex Numbers

A complex number has the form

where a,b∈ℝ and i²=-1. The real part is Re(z)=a, and the imaginary part is Im(z)=b. Two complex numbers are equal exactly when their real and imaginary parts are equal.

For z₁=a+bi and z₂=c+di,

The complex conjugate is z^*=a−bi, and the modulus is

The modulus is a nonnegative real number and obeys |z₁z₂|=|z₁||z₂|. For z≠0,

For example, if z=3+4i, then |z|=5 and 1/z=(3−4i)/25.

Every nonzero complex number can be expressed in polar form:

where r=|z| and θ is an argument of z. Euler’s identity gives e^iθ=cos θ+i sin θ, so z=re^iθ. The angle is not unique: adding any integer multiple of 2π gives the same complex number.

Complex numbers are central to the discrete Fourier transform (DFT), which represents a finite sequence in terms of frequencies:

Here x_n is the input sequence, N is its length, k indexes frequency components, and i is the imaginary unit. The DFT assumes a finite sequence and a chosen convention for sign and scaling; alternative conventions place a factor such as 1/N in the forward or inverse transform. Complex arithmetic therefore does not imply that the original measurements are complex; it is a representation tool for periodic and frequency-domain structure.

9. An Integrated Applied Case

Illustrative case: validating a customer-risk pipeline

Background. A financial-services team builds a binary classifier that assigns each application either “review” or “standard processing.” The data contain numerical features, categorical fields and missing values.

Problem. Analysts report that the pipeline is “accurate for every applicant,” while engineers state that its running time is linear. These claims are insufficiently specified.

Analysis. Let U be the set of applications, X the feature-record space and Y={0,1} the label set. The prediction rule is a function f:D→Y, where D⊆X is the subset of records for which all required preprocessing operations are defined. If missing-value handling is not specified, the rule may be partial rather than total.

The statement “accurate for every applicant” could mean ∀x∈U, f(x)=y(x), which is an exceptionally strong claim and is usually impossible to establish from a finite test sample. A defensible empirical statement instead defines a test set T and a metric, such as accuracy

where 𝟙[condition] equals 1 when the condition is true and 0 otherwise. The metric must be accompanied by sampling, class-balance and uncertainty information.

For complexity, suppose each of n records has p features and the algorithm examines every feature once. Its work is O(np), not simply O(n), unless p is treated as fixed. If the model uses a tree whose depth is d, prediction cost may instead depend on d per record. Complexity claims must identify input dimensions and the computational operation being counted.

Approach and solution. The team defines the domain, documents missing-value rules, separates training and test sets, and reports performance using a clearly defined evaluation set. It also records time and memory complexity in terms of n, p and model size. Logical requirements are written explicitly: every production record must either satisfy the validation predicate or be routed to an exception queue.

Outcome. The revised documentation distinguishes a mathematical guarantee from a sample estimate, a total function from a partial function, and an asymptotic bound from observed latency.

Learning points. Formal domains prevent undefined behavior; quantifiers expose overstrong claims; indexed sums define metrics precisely; and asymptotic notation becomes meaningful only when input dimensions and assumptions are stated.

10. Limitations, Governance and Best Practices

Mathematical formalism improves clarity but does not guarantee that a model is fair, causal or useful. A perfectly consistent function may encode biased data. A proof may establish correctness relative to an unrealistic assumption. Big-O notation may hide constants, hardware effects and data-access costs. Complex transformations may improve computation while reducing interpretability.

Good practice includes:

• Specify the domain, codomain, units and missing-value policy.
• Distinguish definitions, assumptions, empirical observations and conclusions.
• State quantifiers explicitly when making universal or probabilistic claims.
• Preserve index meaning in sequences and summations; avoid accidental leakage across time.
• Report all relevant input dimensions in complexity analysis.
• Use reproducible notation and define every symbol before relying on it.
• Validate formulas with limiting cases, dimensional checks and independent calculations.
• Treat mathematical guarantees as conditional on their assumptions.
• Document ethical constraints, especially when sets and functions represent people, eligibility or risk.

Contemporary data-science systems increasingly combine symbolic specifications with automated learning. This makes foundational reasoning more important, not less: formal constraints can support verification, monitoring and governance, while statistical evaluation is still required to assess behavior on real populations.

Chapter Summary

Sets provide a language for populations, features, labels and filtering conditions. Relations describe associations, whereas functions assign exactly one output to every input in a stated domain. Injectivity, surjectivity, bijectivity and composition clarify information loss and pipeline behavior. Sequences and summations express ordered observations, weighted statistics, recurrences and evaluation metrics. Logic and quantifiers make claims precise and expose the difference between universal and existential statements. Direct proofs, contrapositives, contradiction, induction and counterexamples are practical tools for validating algorithms and mathematical claims. Asymptotic notation describes resource growth, provided the input dimensions and computational assumptions are explicit. Complex numbers support algebraic representation and frequency-domain methods such as the DFT. Across all topics, rigorous data science requires definitions, assumptions, valid domains and careful interpretation.

Key Terms

Set: A collection of distinct objects.

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

Cardinality: The number of elements in a finite set.

Cartesian product: The set of ordered tuples formed from specified sets.

Relation: A subset of a Cartesian product.

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

Domain: The set of permitted inputs to a function.

Codomain: The declared set in which function outputs lie.

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

Injective: A function that maps distinct inputs to distinct outputs.

Surjective: A function whose image equals its codomain.

Bijection: A function that is both injective and surjective.

Sequence: An ordered list represented as a function of an index.

Summation: Compact notation for adding indexed terms.

Predicate: A statement whose truth depends on one or more variables.

Quantifier: A symbol or phrase specifying how broadly a predicate applies.

Contrapositive: The logically equivalent form ¬Q⇒¬P of P⇒Q.

Big-Θ: A tight asymptotic growth bound.

Complex number: A number of the form a+bi, with i²=-1.

Conjugate: For a+bi, the complex number a−bi.

Review Questions

Short Answer Questions

1. Distinguish a relation from a function.
2. What is the difference between a codomain and an image?
3. State De Morgan’s laws for sets.
4. What does the quantifier ∀ mean?
5. Define Big-Θ notation.

Long Answer Questions

1. Explain injective, surjective and bijective functions, and discuss their relevance to data transformations.
2. Describe direct proof, proof by contradiction, contrapositive proof and mathematical induction. Give a suitable data-science-related use for each.
3. Explain how domains and partial functions arise in preprocessing pipelines involving missing values or zero variance.
4. Derive the closed form of the recurrence x_t+1=a+bx_t for b≠1, stating the assumptions.
5. Explain the role of complex numbers in the discrete Fourier transform and distinguish representation from measurement.

Analytical / Application Questions

1. A dataset has 12,000 records. Set A contains 4,800 records satisfying a quality rule, set B contains 3,500 records satisfying a privacy rule, and |A∩B|=1,200. Calculate |A∪B| and interpret the result.
2. A preprocessing algorithm scans n records and p features, examining every feature exactly once. State its time complexity in terms of n and p, and explain when it may be described as linear in n.
3. Critique the statement “the classifier is correct for every future observation because it achieved 98% accuracy on the test set.” Rewrite it as a logically and statistically more defensible claim.

Multiple Choice Questions with Answers

Question 1

If |A|=20, |B|=15 and |A∩B|=6, what is |A∪B|?

A. 29

B. 35

C. 41

D. 26

Correct Answer: A. 29

Question 2

Which condition defines an injective function f?

A. Every codomain element has an input

B. Distinct inputs have distinct outputs

C. Every input has at least two outputs

D. The domain and codomain have equal cardinality

Correct Answer: B. Distinct inputs have distinct outputs

Question 3

What is the correct negation of ∀x∈A, P(x)?

A. ∀x∈A, ¬P(x)

B. ∃x∈A such that P(x)

C. ∃x∈A such that ¬P(x)

D. ¬P(x) for no element of A

Correct Answer: C. ∃x∈A such that ¬P(x)

Question 4

Which statement about Big-O notation is correct?

A. It always gives an exact operation count

B. It is a lower bound only

C. It describes an eventual upper bound up to a constant factor

D. It applies only to numerical algorithms

Correct Answer: C. It describes an eventual upper bound up to a constant factor

Question 5

For z=3+4i, what is |z|?

A. 1

B. 5

C. 7

D. 25

Correct Answer: B. 5

Question 6

Which expression is the composition of f:A→B and g:B→C evaluated at a?

A. f(g(a))

B. g(a)+f(a)

C. g(f(a))

D. f(a)g(a)

Correct Answer: C. g(f(a))

Question 7

If w₁=1, w₂=3, x₁=2 and x₂=6, what is the weighted mean?

A. 4

B. 5

C. 4.5

D. 6

Correct Answer: B. 5

Question 8

Which proof method establishes a statement by proving its logically equivalent form ¬Q⇒¬P?

A. Direct proof

B. Contrapositive proof

C. Induction

D. Counterexample

Correct Answer: B. Contrapositive proof

Question 9

Which growth class is asymptotically larger than n log n for positive integer n?

A. 1

B. log n

C. n

D. n²

Correct Answer: D. n²

Question 10

In z=a+bi, what is the complex conjugate?

A. −a+bi

B. a−bi

C. −a−bi

D. b+ai

Correct Answer: B. a−bi