Discrete Mathematics for Machine Learning

Why Does This Exist?

Machine learning runs on two kinds of mathematics. Calculus handles the smooth stuff: gradients, curves, things that flow. But the data itself is almost always discrete: a vocabulary of 50,000 distinct tokens, a graph of users and friendships, a true-or-false label, a remainder when you shard rows across machines.

Discrete mathematics is the toolkit for that world. It collects five ideas that look unrelated until you need them together: sets (collections and what belongs to them), logic (combining true-or-false claims), counting (how many possibilities exist), graphs (things plus connections), and modular arithmetic (remainders). Hashing a feature, masking attention, counting label combinations, walking a knowledge graph: each is one of these five wearing work clothes.

This page maps the territory and shows how the pieces connect. Each piece gets its full treatment on its own page: counting lives in combinatorics and counting, graphs in graph fundamentals.

The one idea you need first

A set is a collection of distinct things, written with braces: $A = \\{1, 2, 3\\}$. Order does not matter and repeats collapse, so $\\{1, 2, 2, 3\\}$ is the same set as $A$. The power set of $A$ is the set of all its subsets. That one construction already explains binary features, as the diagram shows.

Think of It Like This

How It Actually Works

The five branches, each in one paragraph:

• Sets answer membership questions. Union, intersection and complement describe "either", "both" and "not". Inclusion-exclusion keeps the counting honest when groups overlap: $|A \cup B| = |A| + |B| - |A \cap B|$.
• Logic combines claims with and, or and not, governed by propositional logic and checked row by row in truth tables. Every if in your pipeline is logic.
• Counting says how many outcomes exist before you assign them probabilities. Permutations order things, combinations choose them, and the binomial coefficient $\binom{n}{k}$ counts the choices.
• Graphs model connections: nodes for things, edges for relationships. A social network, a dependency tree, a neural network's wiring diagram.
• Modular arithmetic works with remainders: $a \equiv b \pmod m$ means $m$ divides their difference. Sharding, hashing and cyclic schedules all live here.

Worked example

Take $A = \\{1, 2, 3\\}$ and list every subset by deciding yes or no for each element:

Count them: 8. In general an $n$-element set has $2^n$ subsets, because each of the $n$ elements contributes an independent yes-or-no choice and $2 \times 2 \times \cdots \times 2 = 2^n$. For $n = 10$ binary features that is already 1,024 patterns; for $n = 100$ it is about $10^{30}$, more than any dataset will ever cover. That gap between possible and observed patterns is why generalisation is hard and why structure (graphs, hierarchies, sparsity) matters.

Code

The point is the check: enumerate the power set and confirm the count is exactly $2^n$, no more and no fewer.

1import itertools2
3
4def power_set(items: list[int]) -> list[tuple[int, ...]]:5    out: list[tuple[int, ...]] = []6    for r in range(len(items) + 1):7        out.extend(itertools.combinations(items, r))  # all subsets of size r8    return out9
10
11subs = power_set([1, 2, 3])12print(len(subs))       # -> 813print(2 ** 3 == len(subs))  # -> True

Watch Out For

The Quick Version

• Discrete mathematics covers countable things: sets, logic, counting, graphs and remainders.
• An $n$-element set has exactly $2^n$ subsets, so $n$ binary features span $2^n$ patterns.
• Inclusion-exclusion corrects double counting when groups overlap.
• Remainders (modular arithmetic) sit behind hashing, sharding and cyclic schedules.
• Possible patterns dwarf observed data, which is why models need structure to generalise.

What to Read Next

• Combinatorics and Counting
• Graph Fundamentals
• Sets, Logic and Proofs
• Boolean Algebra in Machine Learning