Skip to content
AI.info

Mathematical foundations

Sets, Functions, Relations, and Notation

Build the notation discipline needed to distinguish sets, elements, functions, relations, random variables, and approximations in machine learning.

By the end you can

Example

Domain mistakes that survive compilation

Many mathematical errors are legal software operations. They fail because the meaning, not the syntax, is wrong. Each of the five below has been counted, standardised or shipped somewhere a reader can go and check.

  • Label leakage: A timestamped feature is joined from after the prediction cutoff, so the function receives information outside its intended domain. This happens often enough to have a census. A 2023 survey in Patterns by Sayash Kapoor and Arvind Narayanan reports: “Through a survey of literature in research communities that adopted ML methods, we find 22 papers across 17 fields where leakage has been found, collectively affecting 294 papers”. Their 2022 preprint put the count at 329 affected papers across the same 17 fields. Both versions sort the failure into a taxonomy of eight distinct types of leakage. This is not one team's bad join. It is a documented mode of scientific error with a census attached.
  • Undefined transformation: A logarithm is applied to zero or negative values without specifying a shifted domain. The standard is explicit about what those inputs are. The 2011 committee draft of the C standard, N1570, states: “The log functions compute the base-e (natural) logarithm of x. A domain error occurs if the argument is negative. A pole error may occur if the argument is zero.” Now watch the error survive. NumPy's reference documentation for numpy.log records that “For each value that cannot be expressed as a real number or infinity, it yields nan and sets the invalid floating point error flag”, and its worked example returns array([ 0., 1., 2., -inf]) for the input [1, e, e**2, 0]. The illegal domain is signalled. The program keeps running, carrying -inf and nan into whatever comes next.
  • Wrong codomain: A model output is treated as a calibrated probability even though the training objective only produced an unconstrained score. The size of that gap has been measured. In 2017 Chuan Guo and three co-authors ran a 110-layer ResNet on CIFAR-100: 16.53% expected calibration error before calibration, 1.26% after single-parameter temperature scaling. A ResNet-152 on ImageNet went from 5.48% to 1.86%. The number that looked like a probability was off by roughly thirteen points of calibration error on CIFAR-100. A single fitted parameter recovered most of it.
  • Ambiguous inverse: A many-to-one encoder is described as invertible because a decoder can produce a plausible reconstruction. In August 2013 David Kriesel showed what a plausible reconstruction costs. Xerox WorkCentre scanners using JBIG2 symbol-coding compression silently substituted digits in scanned documents: a 65 in a cost table came out as 85. Kriesel is precise about why that is worse than a misread character: “This is not an OCR problem (as we switched off OCR on purpose), it is a lot worse – patches of the pixel data are randomly replaced in a very subtle and dangerous way: The scanned images look correct at first glance, even though numbers may actually be incorrect.” The mechanism is the many-to-one map itself: “Images are cut into small segments, which are grouped by similarity. For every group only a representative segment is is saved that gets reused instead of other group members, which may cause character substitution.” The decoder returned a page. It was not the page.
  • Set–element confusion: A metric reported for one sample is discussed as though it described the entire population. An audit of ten widely used test sets, by Curtis Northcutt and two colleagues, gives the pair of numbers that makes the distinction concrete: at least 3.3% label errors on average across the ten, and at least 6% of the ImageNet validation set alone. The 6% belongs to one member of that collection. The 3.3% belongs to the collection. Quoting either where the other is meant is a category error with a factor of nearly two inside it.

Notation is a type system for reasoning

A mathematical expression does more than abbreviate prose. It declares what kind of object each symbol represents and which operations are legal. Confusing a set with one of its elements is therefore like passing the wrong data type into a program. Machine learning mixes examples, labels, parameters, functions, distributions, and datasets. The same letter can play different roles in different papers. Good notation prevents those roles from drifting silently. The goal is not to decorate an argument with symbols. It is to read an equation and ask whether the objects, domains, and quantifiers match the claim being made.

Every symbol should have an object type, a domain, and a role.

Case

One ill-typed object broke a finished system in 1902

Type discipline has a famous origin story. In June 1902 Bertrand Russell wrote to Gottlob Frege about the set of all sets that are not members of themselves. Frege’s second volume was already at the printers. He answered in an appendix with a modified axiom. One ill-typed object had broken the system.

Analogy

Notation is a carefully labeled laboratory bench

Mathematical notation is a laboratory bench. Every container carries a substance name, a concentration, a unit, and a hazard label. That matters because two clear liquids can look identical and need completely different handling. Sets are the shelves. Elements are individual samples. Functions are procedures that turn one labeled object into another, so composition works only when the output label of one procedure matches the required input label of the next.

A symbol can also name an object no bench could hold — a function space, an equivalence class, a measure. The discipline of labeling matters more there, not less.

A symbol without a declared role is an invitation to a category error.

Composition, inverse images, and why arrows matter

If f maps inputs to representations and g maps representations to decisions, the composed system is g ∘ f. The order matters: g ∘ f means apply f first, then g. Reversing the arrows may not even be defined. An inverse function exists only when the mapping is one-to-one and onto the relevant codomain. Machine-learning encoders are often many-to-one. A decoder is therefore usually not a true inverse. The preimage f⁻¹(B) is a different object. It asks which inputs land inside a set B of outputs, and it stays meaningful even when no inverse function exists.

The cleanest published demonstration of that distinction is a hash collision. On 23 February 2017 CWI Amsterdam and Google announced the first practical SHA-1 collision: “As a proof of the attack, we are releasing two PDFs that have identical SHA-1 hashes but different content.” The attack took roughly 9,223,372,036,854,775,808 SHA-1 computations, 6,500 CPU-years and 110 GPU-years. Read it as a statement about types. Two distinct files sit inside the preimage of one digest. So that preimage is a set with at least two elements, and the map has no inverse function. NIST announced on 15 December 2022 that SHA-1 is retired and will be removed from its remaining protocols by 31 December 2030, and it states the other direction flatly — “It is impossible to reconstruct the original message from the hash alone”. The preimage is a perfectly good object. The inverse does not exist.

Where identity between input and output has to be provable, a many-to-one encoding is not merely inadvisable. It can be prohibited. Legally substitutive scanning in Germany is governed by Technical Guideline TR-03138, RESISCAN, issued by the Federal Office for Information Security (BSI). The rule is one sentence: “Verfahren, die zur Bildkompression das sog. „Symbol Coding“ verwenden, DÜRFEN NICHT eingesetzt werden.” It took effect on 16 March 2015. A footnote gives the reasoning in the vocabulary of this lesson: “Bei ungenauem oder fehlerhaft implementiertem „Symbol Coding“ besteht die Gefahr, dass sich das Scanergebnis semantisch (z. B. durch Vertauschung von Zeichen) vom Original unterscheidet.” The guideline adds that even a correct implementation cannot guarantee the required legal certainty. A regulator reached the conclusion this section argues for. The existence of a decoder is not invertibility.

Key idea

Three symbols that should not be interchangeable

The equality sign states that two expressions denote the same value. The symbol “:=” declares a definition, while “≈” signals approximation.

Replacing one with another can hide a modeling assumption. A finite Monte Carlo estimate is not equal to an expectation. A learned score is not equal to a probability merely because both lie between zero and one. That second substitution has a measured price. A 2017 paper on the calibration of modern neural networks opens with the finding: “We discover that modern neural networks, unlike those from a decade ago, are poorly calibrated.” Chuan Guo and three co-authors then put numbers on it. A 110-layer ResNet on CIFAR-100 sits at 16.53% expected calibration error, falling to 1.26% after temperature scaling — a single fitted parameter. A ResNet-152 on ImageNet sits at 5.48%, falling to 1.86%. An equals sign written between a softmax output and P(Y=1|x) asserts that the 16.53% is zero. When reading technical work, mark every approximation and every definition before manipulating the expression.

Notation should reveal where exact identity ends and approximation begins.

Visual

The objects behind common ML notation

A small hierarchy helps separate containers, elements, mappings, and statements about them. Each level answers a different question. What collection is this drawn from? Which particular member is it? What rule carries it somewhere else? What claim is being asserted about the result? Most of the failures in this lesson are a symbol that has quietly moved one level while nobody rewrote the sentence around it.

FigureHierarchy · 5 levels

  • Set or space

    A collection such as the input space X, label set Y, or parameter space Θ.

    • Element or tuple

      A particular example x, label y, parameter θ, or paired observation (x, y).

      • Function

        A rule such as f: X → Y that assigns one output to each input in its domain.

        • Relation

          A rule that may associate one input with several outputs, such as a graph edge relation.

          • Predicate

            A statement that evaluates to true or false, such as x ∈ A or loss(θ) ≤ ε.

Comparison

Function, relation, lookup table, and random variable

These objects can look similar in code while supporting different mathematical claims. The one most often mistaken for the underlying rule is the lookup table, because a label file is exactly that: a finite record of pairs somebody wrote down.

Ten of the label files the field trusts most have been audited. Curtis Northcutt and two colleagues report: “Errors in test sets are numerous and widespread: we estimate an average of at least 3.3% errors across the 10 datasets, where for example label errors comprise at least 6% of the ImageNet validation set.” Crowdworkers confirmed 51% of the algorithmically flagged candidates as genuinely mislabelled. A separate re-annotation of the ImageNet validation set, by five researchers at Google Brain and DeepMind, reaches the same place from another direction. It finds “the original ImageNet labels to no longer be the best predictors of this independently-collected set”.

So the table is a recorded relation between images and strings, and at least one row in twenty of the ImageNet validation file disagrees with the rule it is standing in for. A function, a relation, a table and a random variable can carry the same values in memory while licensing entirely different claims about them.

FigureComparison · 4 columns

Function

One output for every input in its domain.

  • Has a declared domain and codomain
  • May be deterministic without being invertible
  • Composition requires compatible domains
  • Example: a trained classifier

Relation

Connects inputs and outputs without requiring uniqueness.

  • Can be one-to-many or many-to-many
  • Useful for graphs and constraints
  • Does not automatically define an inverse function
  • Example: user-to-purchased-item links

Lookup table

A finite representation of recorded pairs.

  • May omit valid inputs
  • Can contain duplicates or contradictions
  • Is data, not necessarily the underlying rule
  • Example: a label file

Random variable

A measurable function from outcomes to values.

  • Its uncertainty comes from the probability model
  • A realized value is not the variable itself
  • May be vector-valued
  • Example: future demand

Steps

Read an equation before solving it

Unfamiliar notation in an ML paper or design document yields to a fixed reading order: inventory the symbols, state the domains, read the quantifiers, trace the compositions, mark the approximations. The order is not arbitrary. The domain check catches log applied to zero before NumPy returns -inf. The composition check catches an encoder whose decoder is being sold as an inverse. The approximation check catches an equals sign standing where 16.53% of calibration error actually stands.

FigureProcess · 5 steps

  1. 1. Inventory symbols

    Write the object type and dimensions of every symbol.

  2. 2. State domains

    Identify where each function is defined and what values are excluded.

  3. 3. Read quantifiers

    Find words such as every, exists, with high probability, or on average.

  4. 4. Trace compositions

    Follow the arrows and verify that output spaces match the next input spaces.

  5. 5. Mark approximations

    Separate definitions, exact equalities, estimates, and numerical approximations.

Position

The notation worth worrying about is the notation that reads easily

The difficulty a beginner expects from notation is the difficulty of reading it. Unfamiliar letters, stacked subscripts, an integral where a sum would have done. That difficulty is real, and it is temporary. The failures collected in this lesson are of the opposite kind, and not one of them is hard to read.

A timestamped feature joined from after the prediction cutoff: 22 papers across 17 fields, collectively affecting 294 papers, sorted into eight types of leakage. A logarithm applied to zero: the C standard calls a negative argument a domain error and a zero argument a possible pole error, and NumPy hands back -inf and continues. A many-to-one encoder called invertible because a decoder returns something plausible: a Xerox WorkCentre returned a page that looked right and said 85 where the original said 65, and Xerox's own support article KB0230451 records the resolution in the flattest possible words — “A Scanning Software Patch (Firmware Update File) is Available to Resolve This Behavior.” A metric from one sample discussed as though it described the population: 6% of the ImageNet validation set is not the 3.3% average across the ten test sets. Every one of these is syntactically legal.

That contrast is where compact notation earns its density. Writing f: X → Y is shorter than the sentence it replaces, and it commits to a domain and a codomain, so g ∘ f can be checked before it is computed. The preimage f⁻¹(B) stays meaningful when no inverse function exists — two published PDF files sit in the preimage of a single SHA-1 digest — which the phrase “run the model backwards” quietly does not. Three symbols carry three strengths of claim, and swapping them hides the difference: equality, definition, approximation. The lesson's example is score(x) = P(Y=1|x) written over an uncalibrated logit. Nothing in that line is difficult. An equals sign is doing the work a calibration step was supposed to do, and the 2017 measurements say what that work is worth: 16.53% expected calibration error on CIFAR-100, 1.26% once the step is actually taken.

The case from 1902 is the sharp version. Frege’s system was a formal one, axioms and all, and the second volume was already at the printers when Russell’s letter arrived that June. What broke it was one object of the wrong type, not a page anyone found unreadable. So the habit worth building is not parsing denser expressions. It is the reflex to ask of every symbol what kind of thing it names and where it is defined. That reflex turns each of the errors above into a question asked before any code runs — and, where the answer has to hold up in law, into the rule the BSI wrote down: symbol coding must not be used.

A symbol you read fluently can still be the one whose type was never declared.

Key takeaways