Learn the fundamentals of set theory, from finite and infinite sets to set operations and functions, crucial for understanding cryptographic structures in ZK proofs.
Table of Contents
Set theory is the branch of mathematics that studies collections of objects called sets. It provides the language and structure needed to work with collections of mathematical objects (integers, rational numbers, etc). While initially abstract, these concepts will be essential as we later explore groups, rings, and fields used in cryptographic systems.
This article is the second in the series of math articles teaching the concepts and terminology that are a prerequisite to understanding the math of zero-knowledge proofs.
This article series is not meant as a stand-alone, conclusive resource for studying the math topics outlined. Instead, it is an overview to share the high-level concepts required for understanding zero-knowledge proofs and cryptography. For a more detailed breakdown, links can be found in the references section at the end of each article.
Also note that mathematical proofs of the theorems and definitions have been omitted for simplicity. If you are interested, please use the linked resources or your favorite AI assistant to understand how to derive the concepts from first principles.
With that said, let’s get into it!
Set theory
A set is a collection of distinct elements, meaning it cannot contain duplicate elements. Elements can be of any type, e.g., numbers, letters, objects, etc, as long as each element in the set is unique. That’s set theory's beauty (and weirdness): it’s incredibly general by design.
Element: An object that belongs to a set. For example, $1$ is an element of the infinite set of integers, denoted with the symbol $\mathbb{Z}$. Each element must be distinct from all other elements in the set: elements cannot be repeated.
Sets: Denoted using curly brackets: ${}$$\{\}$, for example, $\{1, 2, 3\}$.
Cardinality: The number of elements the set contains. For example, the cardinality of the set $\{1 , 2, 3\}$ is $3$. This is also referred to as the order of the set.
Finite and infinite sets
An infinite set contains an unlimited number of elements and is not finite (woooah bet you didn’t know that - sorry the British sarcasm couldn’t resist). For example, consider the number line: it goes on forever in one or both directions. No single natural number can represent the total number of elements in an infinite set—it is, by definition, infinite.
There are two types of infinite sets: countably infinite sets and uncountable infinite sets.
Countably infinite sets can be placed into a one-to-one correspondence with the natural numbers (positive integers used for counting and ordering). In other words, the elements of the set can be listed in a sequence $\{1,2,3,…\}$ where each element is paired with a unique natural number.
Formally, this means a bijective function (we will introduce this shortly) exists between the set and the set of natural numbers. The cardinality of any countably infinite set is the same as the cardinality of the set of natural numbers.
This implies that even though the set is infinite, it can still be ordered, and its elements can be systematically listed without any gaps.
Examples of countably infinite sets:
Integers ($\mathbb{Z}$): Integers can be listed in a sequence such as $\{0, 1, -1, 2, -2, 3, -3, \ldots\}$.
Positive integers ($\mathbb{N}^+$): The set of positive integers can be listed as $\{1, 2, 3, \ldots\}$.
Natural numbers ($\mathbb{N}$): The set of natural numbers can be listed as $\{0, 1, 2, \ldots\}$.
Rational Numbers ($\mathbb{Q}$): The set of all rational numbers, denoted by $\left\{\frac{p}{q} \mid p \text{ and } q \text{ are integers, } q \neq 0\right\}$. They can still be enumerated despite being densely packed on the number line. If you want to see a proof explaining why the rational numbers are countably infinite, you should read about Cantor's Diagonalization Argument.
Uncountably infinite sets cannot be put into a one-to-one correspondence with the natural numbers. This means that there’s no way to list all of their elements in a sequence like you can with countably infinite sets.
A classic example is the set of real numbers between $0$ and $1$. Although there are infinitely many rational numbers in this interval (which can be listed), the set also contains irrational numbers. Irrational numbers are numbers with non-repeating, non-terminating decimal expansions that cannot be expressed as a ratio of integers $\frac{p}{q}$ (e.g. $e$, or $\pi$), and they cannot be captured in any list. Even though rationals are countable, when you combine them with the uncountably many irrationals, the whole set becomes uncountable.
This was proven by Cantor’s diagonal argument, which shows that even if you tried to list all real numbers between $0$ and $1$, you could always construct a new number that is not on the list, meaning the list is incomplete. So, no matter how clever your method, you can’t assign every real number between $0$ and $1$ a unique natural number label.
This is what makes the set of real numbers uncountably infinite: its size (or cardinality) is strictly larger than that of the natural numbers or the rational numbers, both of which are countably infinite. “Some infinities are larger than others” really is true after all.
Examples of uncountably infinite sets:
Real numbers ($\mathbb{R}$): The set of real numbers between any two distinct real numbers (e.g., between 0 and 1) is uncountably infinite. There are infinitely many real numbers in this interval, and they cannot all be listed in a sequence.
Complex numbers ($\mathbb{C}$): The set of complex numbers is uncountably infinite because it includes all possible combinations of real and imaginary parts.
A finite set has a specific, countable number of elements. Its cardinality is a whole number and can be determined exactly.
$\{\text{Monday}, \ldots, \text{Sunday}\}$ — days of the week.
$\{0, 1, 2, \ldots, 23\}$ — hours in a day.
Set of remainders of integers modulo $n$ (where $n$ is some integer). For example,$\{0, 1, 2, 3, 4\}$ is the set of integers modulo $5$ and denoted by $\mathbb{Z}_5$. What's important to understand now is that this type of set is the most commonly used in cryptography, and its critical importance for zero-knowledge proofs will become clearer as we progress through these topics.
Subsets
If every element of set $A$ is also an element of set $B$, then $A$ is a subset of $B$, denoted as $A \subseteq B$.
Proper subset: If $A \subseteq B$ and $A \neq B$ (meaning $B$ has at least one element that $A$ doesn't have), then $A$ is a proper subset of $B$, denoted as $A \subset B$.
Empty set: The empty set, denoted as $\emptyset$ or $\{\}$, is a subset of every set.
Power set: The power set of a set $S$, denoted as $\mathcal{P}(S)$ or $2^S$, is the set of all possible subsets of $S$, including the empty set and $S$ itself.
Cardinality: For a finite set with cardinality $n$, the power set has cardinality $2^n$. This means that the set has $2^n$ possible subsets.
Example: If $S = {a, b, c}$, then $\mathcal{P}(S) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$
Properties of subsets:
Transitivity: If $A$ is a subset of $B$, and $B$ is a subset of $C$, $A$ must also be a subset of $C$. In math notation, this is equivalent to saying:
if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.
Reflexivity: Every set is a subset of itself, i.e., $A \subseteq A$.
Antisymmetry: If $A$ is a subset of $B$ and $B$ is a subset of $A$ then $A$ must be equal to $B$. Or, in math notation, this is equivalent to saying: if $A \subseteq B$ and $B \subseteq A$, then $A = B$.
Supersets
If set $B$ contains all elements of set $A$ (and possibly more), then $B$ is a superset of $A$, denoted as $B \supseteq A$.
Equivalence: $B \supseteq A$ is equivalent to $A \subseteq B$ (they express the same relationship from different perspectives).
Proper Superset: If $B \supseteq A$ and $B \neq A$ (meaning $B$ has at least one element that $A$ doesn't have), then $B$ is a proper superset of $A$, denoted as $B \supset A$.
Universal Set: In a given context, the universal set (often denoted as $U$) is a superset of all sets under consideration.
Properties of supersets:
Transitivity: If $C \supseteq B$ and $B \supseteq A$, then $C \supseteq A$.
Reflexivity: Every set is a superset of itself, i.e., $A \supseteq A$
Antisymmetry: If $B \supseteq A$ and $A \supseteq B$, then $A=B$.
Set operations, relations, and functions
The following sections on set operations, relations, and functions provide mathematical terminology you may occasionally encounter when reading ZKP literature. This will give you basic familiarity to help navigate broader mathematical contexts in papers. Consider this purely a reference guide:
Basic set operations
Set operations allow us to combine and manipulate sets to create new sets.
Union ($\cup$): The union of sets $A$ and $B$, denoted as $A \cup B$, is the set of all elements that belong to either $A$ or $B$ or both.
Formally: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$
Where $\mid$ means “such that” and $\in$ means “is part of” in math notation. So this notation says we're defining a set containing all elements $x$ such that $x$ is a member of $A$ OR $x$ is a member of $B$.
Intersection ($\cap$): The intersection of sets $A$ and $B$, denoted as $A \cap B$, is the set of all elements that belong to both $A$ AND $B$.
Formally: $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$.
This notation says we're defining a set containing all elements $x$ such that $x$ is a member of $A$ AND $x$ is a member of $B$.
Example: $\{1, 2, 3\} \cap \{3, 4, 5\} = \{3\}$
Difference ($\setminus$): The difference of sets $A$ and $B$, denoted as $A \setminus B$, is the set of all elements that belong to $A$ but NOT to $B$.
Formally: $A \setminus B = \{x \mid x \in A \text{ and } x \notin B\}$
Where $\notin$ means ”not a part of”.
This notation says we're defining a set containing all elements $x$ such that $x$ is a member of $A$ but NOT a member of $B$.
Complement ($A^c$ or $\overline{A}$): The complement of a set $A$ with respect to a universal set $U$ is the set of all elements in $U$ that are NOT in $A$. The universal set $U$ is the set of all possible elements (depending on the system you are working in, e.g., integers).
Formally: $A^c = \{x \mid x \in U \text{ and } x \notin A\}$
Example: If $U = \{1, 2, 3, 4, 5\}$ and $A = \{1, 3, 5\}$, then $A^c = \{2, 4\}$
The complement set of $A$ is a special case of the difference set operation where $B$ is specific - the universal set $U$.
Symmetric difference ($\triangle$ or $\oplus$): The symmetric difference of sets $A$ and $B$, denoted as $A \triangle B$, is the set of elements that belong to either $A$ OR $B$ but not to their intersection.
Formally: $A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$
This notion says we are defining a set containing all elements in $A$ OR $B$ but excluding any elements which are in both $A$ and $B$.
The Cartesian product of two sets $A$ and $B$, denoted as $A \times B$, is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.
Formally: $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$
Example: If $A = \{1, 2\}$ and $B = \{x, y\}$, then $A \times B = \{(1, x), (1, y), (2, x), (2, y)\}$
Relations
A relation between sets $A$ and $B$ is a subset of the Cartesian product $A \times B$. It's a collection of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.
Types of relations
Reflexive relation: A relation $R$ on a set $A$ is reflexive if for every element $a \in A$, $(a, a) \in R$.
Example: "Equal to" relation on integers: every integer equals itself.
Symmetric relation: A relation $R$ on a set $A$ is symmetric if for all $a, b \in A$, if $(a, b) \in R$, then $(b, a) \in R$.
Example: "Sibling" relation among people: if Sarah is Alice’s sibling then Alice is Sarah’s sibling.
Transitive relation: A relation $R$ on a set $A$ is transitive if for all $a, b, c \in A$, if $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.
This means relationships chain together. If A relates to B and B relates to C, then A must relate to C.
Example: "Greater than" relation on real numbers. If $a > b$ and $b > c$ then $a > c$
Equivalence relation: A relation that is reflexive, symmetric, and transitive.
This creates groupings where all elements in a group are considered "the same" according to the relation.
Example: "Congruence modulo $n$" is an equivalence relation on integers.
Equivalence relations partition a set into equivalence classes: disjoint subsets (the subsets have no elements in common) where all elements in a class are related to each other. For example, modulo $3$ creates three classes: $\{0, 3, 6, ...\}$, $\{1, 4, 7, ...\}$, and $\{2, 5, 8, ...\}$.
Functions
A function from set $A$ to set $B$ is a special type of relation where each element in $A$ is related to exactly one element in $B$.
Formally: $f: A \rightarrow B$ is a function if for each $a \in A$, there exists exactly one $b \in B$ such that $f(a) = b$.
The set $A$ is called the function's domain, and the set $B$ is called the codomain.
Types of functions
Injective (one-to-one): A function $f: A \rightarrow B$ is injective if different elements in $A$ map to different elements in $B$.
Formally: For all $a_1, a_2 \in A$, if $a_1 \neq a_2$, then $f(a_1) \neq f(a_2)$.
Equivalently: For all $a_1, a_2 \in A$, if $f(a_1) = f(a_2)$, then $a_1 = a_2$.
Surjective (onto): A function $f: A \rightarrow B$ is surjective if every element in $B$ is mapped to by at least one element in $A$.
Formally: For all $b \in B$, there exists an $a \in A$ such that $f(a) = b$.
Bijective (one-to-one and onto): A function that is both injective and surjective.
A bijective function ensures that each element in the codomain is mapped to by exactly one element in the domain and vice versa.
All bijective functions have inverses.
What’s next?
In the next part of the series, we'll explore group theory and how groups are defined using sets. This will help us understand the properties of these mathematical structures, so we can later see how they're used in zero-knowledge proof protocols like Groth16 and PLONK.
Summary
Set theory is the branch of mathematics that studies collections of objects called sets
A set is a collection of distinct elements with no duplicates
Elements can be any objects (numbers, letters, etc.) as long as each is unique
Cardinality refers to the number of elements in a set
Types of sets:
Finite sets have a specific, countable number of elements
Countably infinite sets can be put in one-to-one correspondence with natural numbers
Uncountably infinite sets cannot be enumerated (e.g., real numbers)
Key set relationships:
Subset: If every element of A is also in B, then A ⊆ B
Proper subset: A ⊂ B when A ⊆ B and A ≠ B
Empty set (∅) is a subset of every set
Power set contains all possible subsets of a set
Set operations:
Union (∪): Elements in either set or both
Intersection (∩): Elements common to both sets
Difference (\): Elements in the first set but not the second
Complement: Elements of a universal set but not in the given set
Symmetric difference (△): Elements in either set but not both
Relations and functions:
The Cartesian product creates ordered pairs from two sets
Relations are subsets of the Cartesian product
Functions map each element of a domain to exactly one element in a codomain
Function types: injective (one-to-one), surjective (onto), bijective (both)
Set theory provides the foundation for understanding and describing the mathematical structures used in cryptography and zero-knowledge proofs.
In the next article, we will be using this knowledge to understand group theory–what does it mean if we describe something as a group?
References
Prefer to learn via video? Check out this YouTube video instead!
