Building the vocabulary of mathematical structures used in ZK proofs
Agenda
Sets: definitions, subsets, cardinality
Ordered pairs & Cartesian products
Functions as subsets of Cartesian products
Binary operators
The algebraic hierarchy: Magma → Semigroup → Monoid → Group
Why this vocabulary matters for ZK
What is a Set?
A well-defined collection of objects
Examples
{1, 2, 3, 4, 5}
{0, 1, 2, ..., p-1} ← a finite field!
All integers ℤ
All real numbers ℝ
All 3×3 matrices
All polynomials of degree ≤ 5
Rules
No duplicates: {a, a, b} = {a, b}
Order doesn't matter: {1,2,3} = {3,1,2}
Can be empty: { } = ∅
Membership is well-defined
Subsets & Number Systems
The classic number systems form a chain of subsets:
ℂ Complex Numbers
ℝ Real Numbers
ℚ Rational Numbers
ℤ Integers
ℤ ⊂ ℚ ⊂ ℝ ⊂ ℂ — Every integer is a rational number, but not every rational is an integer.
Cardinality
The number of elements in a set
|{5, 9, 10}| = 3
|{0, 1, 2, ..., 10}| = 11
|𝔽₇| = 7 (finite field of order 7)
|ℤ| = ∞ (countably infinite)
|ℝ| = ∞ (uncountably infinite — a "bigger" infinity!)
In ZK proofs, we always work with finite sets, so cardinality = a specific number.
Ordered Pairs
Sets have no order, but we can create ordered pairs (tuples):
Set: {a, b} = {b, a} (order doesn't matter)
Ordered pair: (a, b) ≠ (b, a) (order matters!)
Two ordered pairs are equal iff both components match
Programmer translation: An ordered pair is a tuple.
(a, b) == (c, d) ⇔ a == c and b == d
Elliptic curve points are ordered pairs (x, y). The order matters!
Cartesian Products
A × B = all possible ordered pairs (a, b) where a ∈ A, b ∈ B
A = {1, 2, 3}
B = {'x', 'y', 'z'}
# A × B
cartesian = [(a, b) for a in A for b in B]
# [(1,'x'), (1,'y'), (1,'z'),
# (2,'x'), (2,'y'), (2,'z'),
# (3,'x'), (3,'y'), (3,'z')]
print(f"|A × B| = {len(cartesian)}") # 9 = |A| × |B|
A × B
x
y
z
1
(1,x)
(1,y)
(1,z)
2
(2,x)
(2,y)
(2,z)
3
(3,x)
(3,y)
(3,z)
Functions as Subsets of Cartesian Products
A function f: A → B is a subset of A × B where each element of A maps to exactly one element of B
✓ Valid function
# f(1) = y, f(2) = z, f(3) = x
f = {(1,'y'), (2,'z'), (3,'x')}
# Each input maps to exactly
# one output ✓
✗ Not a function
# 1 maps to BOTH p and q
bad = {(1,'p'), (1,'q'), (2,'q'),
(3,'r')}
# Same input, different outputs ✗
Key insight: functions don't have to be "computable." A function is just a relation — a mapping — between sets. In ZK, we deal with functions between very exotic sets (like elliptic curve points).
Binary Operators
A binary operator takes two elements from a set and returns one element.
A closed binary operator always produces a result in the same set.
Division on integers is NOT closed: 1 ÷ 3 = 0.333... (not an integer!)
Constructing a Binary Operator
Addition mod 3 on the set {0, 1, 2}:
+
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
# Build the operation table
S = {0, 1, 2}
print(" | " + " ".join(str(b) for b in sorted(S)))
print("--+------")
for a in sorted(S):
row = " ".join(str((a + b) % 3) for b in sorted(S))
print(f"{a} | {row}")
# Verify closure: every entry is in {0, 1, 2} ✓
The Algebraic Hierarchy
Magma — closed binary operator
Semigroup — + associative
Monoid — + identity element
Group — + every element has an inverse
Each level adds one more requirement. Groups are the star of the show for ZK.
Magma
A set with a closed binary operator. That's all!
# Example: positive integers under exponentiation
# a^b is always a positive integer ✓ (closed)
# But NOT associative:
a, b, c = 2, 3, 2
assert (a ** b) ** c != a ** (b ** c)
# (2³)² = 64 but 2^(3²) = 512
# And NOT commutative:
assert a ** b != b ** a
# 2³ = 8 but 3² = 9
A Magma is the least restrictive algebraic structure.
Only requirement: the operation stays in the set.
Semigroup
A Magma where the binary operator is associative
(a □ b) □ c = a □ (b □ c)
# Example: non-empty strings under concatenation
# Closed: concat of two strings is a string ✓
# Associative: ("foo" + "bar") + "baz" == "foo" + ("bar" + "baz") ✓
a, b, c = "foo", "bar", "baz"
assert (a + b) + c == a + (b + c) # "foobarbaz"
# But NOT commutative:
assert a + b != b + a # "foobar" ≠ "barfoo"
# (That's OK — commutativity isn't required)
# No identity element (if no empty string allowed)
# No inverses: can't "un-concatenate"
Monoid
A Semigroup with an identity element
a □ e = e □ a = a for all a in the set
Examples
Set + Op
Identity
ℤ under +
0
ℤ under ×
1
Strings + concat
"" (empty)
Matrices + multiply
I (identity matrix)
# Positive integers under ×
# is a Monoid (identity = 1)
# but NOT a Group (no inverses!)
# 5 × 1 = 5 ✓ (identity)
# 5 × ? = 1 → ? = 1/5
# but 1/5 is not an integer!
# So no inverse exists
Group — The Star of the Show
A Monoid where every element has an inverse
For every a, there exists a' such that a □ a' = e
Set + Operation
Identity
Inverse of a
Group?
Positive ℤ under +
0 (not positive!)
—
✗ Semigroup
ℤ≥0 under +
0
No (-5 not in set)
✗ Monoid
All ℤ under +
0
-a
✓ Group!
𝔽ₚ under +
0
p - a
✓ Group!
𝔽ₚ\{0} under ×
1
ap-2
✓ Group!
Abelian Groups
An abelian group is a group where the binary operator is commutative:
a □ b = b □ a for all a, b
Integers under addition: abelian (3 + 5 = 5 + 3)
Matrices under multiplication: NOT abelian (AB ≠ BA in general)
Finite field under addition: abelian
Elliptic curve points under point addition: abelian ← important!
"Abelian" is just a fancy word for commutative. Say abelian — you'll sound smarter.
Why This Vocabulary Matters
Consider this statement:
"Elliptic curve points in a finite field under addition are a finite cyclic abelian group."
You now know this means:
✓ Adding two points gives another point (closed)
✓ Addition is associative
✓ There's an identity element ("point at infinity")
✓ Every point has an inverse
✓ Addition is commutative (abelian)
✓ The group has finite size
✓ Every element can be generated from a single generator (cyclic)
You know 7 things about elliptic curves without knowing what they are!
The Programmer's Analogy
# Abstract algebra is like interfaces/traits in programming!
class Group:
"""Any Group implementation must satisfy:
- closed: combine(a, b) always returns an element in the group
- associative: combine(combine(a,b), c) == combine(a, combine(b,c))
- identity: combine(a, identity) == a
- inverse: combine(a, inverse(a)) == identity
"""
def combine(self, a, b): ...
def identity(self): ...
def inverse(self, a): ...
# Integers under + is a Group
# Finite fields under + is a Group
# EC points under point-add is a Group
# All use the SAME interface, different implementations!
Groups hide implementation details like interfaces hide implementations.
You can reason about behavior without knowing internals.
Summary: The Full Hierarchy
Structure
Closed
Assoc.
Identity
Inverse
Magma
✓
Semigroup
✓
✓
Monoid
✓
✓
✓
Group
✓
✓
✓
✓
For ZK, you primarily need Groups.
Everything we'll encounter — finite fields, elliptic curves — forms a Group.
Practice Problems
Is the set {0, 1, 2, 3, 4} under multiplication mod 5 a Group? (Careful about 0!)
Build the operation table for XOR on the set {0, 1}. What algebraic structure is it?
Why can't strings under concatenation be a Group? Which property fails?
Define the Cartesian product of {triangle, square} × {3, 4, 5}. Which subset defines the "number of sides" function?
Is min(a, b) over all integers a Magma? A Semigroup? A Monoid? What about over positive integers?
Consider 3-bit binary numbers under bitwise AND. Is this a Magma, Semigroup, Monoid, or Group?
Next Workshop
Group Theory Deep Dive
Examples of groups in detail
Finite groups & group order
Cyclic groups & generators
Why cyclic groups are essential for ZK
Groups are the mathematical backbone of elliptic curve cryptography.