Min-Max Math, ep. 07: Sets, relations, and functions
Dots and arrows rule the world of mathematics
For many of us, this is a function:
def square(x):
return x*x
For others, this is:
For some, this is:
In truth, these are all only representations of functions, a concept that lies at the core of mathematics.
At their essence, all of the above examples are instances of this:
What are these dots and arrows, and most importantly, how do they relate to square and f(x) = x²? Let’s find out.
Sets
One recurring notion throughout this series is that sets are not what we think they are. Let’s recap what we know about them. If we naively define sets as collections of things, things break down quickly.
Thus, we define sets through their properties called the set axioms. Any mathematical model that satisfies the set axioms works. For more detail, check out one of the earlier episodes in this series:
Instead of tackling a complete axiomatic treatment of sets, we’ll take a more scenic route: I’ll show some examples of sets, and we’ll see what we can do with them.
Sets…
Let’s dive in. We denote sets by curly braces { }, and either
list their elements in between, like {♠, ♥, ♣, ♦},
or describe them using the set builder notation, like {n ∈ ℕ: n is even}.
The set builder notation is always composed of a parent set and a property, which can be evaluated as true or false for each element. In the above example, the set is the set of natural numbers ℕ, and the property is “n is even”.
Visually, we can represent sets via planar blobs. Like this:
Sets are like Lego blocks. They are not that interesting in themselves, but we can build wonderful things by combining the blocks together.
The most important building blocks are composed of numbers. There are five of them that we need to know about:
the natural numbers ℕ = {1, 2, 3, …},
the integers ℤ = {…, -2, -1, 0, 1, 2, …},
the rational numbers ℚ = {a/b: a, b ∈ ℤ, b ≠ 0},
the mysterious real numbers ℝ (which you can imagine as a line),
and the even more mysterious complex numbers ℂ = {a + bi: a, b ∈ ℝ}, where i is the square root of -1. (One of its square roots, to be more precise.)
Chances are, you are familiar with most of them on the user level. We’ll have an entire episode about each of them, but for now, this is enough.
Speaking about Lego blocks: let’s talk about putting them together.
…and their operations
Defining and describing sets are not the exciting parts; it’s the things that we can do with sets. Most importantly, we can take their union, intersection, and difference.
Definition. (Union of sets.) Let A and B be two sets. Their union A ∪ B is the set that contains precisely those elements that are elements of A or B.
Simple enough: for instance, {1, 2} ∪ {2, 3} = {1, 2, 3}. (Sets cannot contain the same element more than once.)
Let’s draw it!
The above method of visualization is called a Venn diagram, representing the relation between sets. Although they do not possess enough power for proofs, they are pretty damn useful for understanding what’s going on. (Some mathematicians often frown upon the usage of Venn diagrams, but don’t listen to such elitist snobbery.)
We can define the intersection similarly to the union.
Definition. (Intersection of sets.) Let A and B be two sets. Their intersection A ∩ B is the set that contains precisely those elements that are elements of both A and B.
We might even define A ∩ B in terms of the set builder notation: A ∩ B = {a ∈ A: a ∈ B}.
Here’s the Venn diagram.
If you sense a connection to mathematical logic, it’s not an accident. The “corresponding” logical connective is OR (∨) to union (∪) and AND (∧) to intersection (∩). Even their symbols are analogous: a wedge or a cup, oriented similarly.
We’ll talk about this connection later. Before that, there is one more operation that I want to show you: set difference.
Definition. (Difference of sets.) Let A and B be two sets. Their difference A ∖ B is the set that contains precisely those elements that are elements of A, but not B.
These mathematically precise definitions are not that clear, so here’s the Venn diagram one more time.
As you can see, the word “difference“ precisely explains what’s going on: we remove the elements of one set from another.
These set operations behave as we would expect. For instance, the union and intersection are
commutative: A ∪ B = B ∪ A and A ∩ B = B ∩ A,
associative: (A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C),
and distributive: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
(On the other hand, A ∖ B is not the same as B ∖ A.)
I will not prove this to you, but you should whip out those Venn diagrams to check your understanding.
The Cartesian product
The Cartesian product is one of the principal ways of constructing sets from others (you know, Lego blocks and whatnot).
Think about the Euclidean plane, often modeled by
The elements of ℝ² are simply tuples of real numbers, and nothing stops us from forming tuples from any two sets.
Definition. (The Cartesian product.) Let A and B be two sets. Their Cartesian product A × B is defined by
that is, A × B is the set of all possible tuples formed from the elements of A and B.
(For brevity, we write A² = A × A.)
Here’s an example for the finite sets A = {1, 2, 3} and B = {1, 2, 3, 4}.
Similar to the above case, the Cartesian product A × B can represent an image. Say, if we’re talking about an image of a resolution 28 × 28, its pixel coordinates are represented by {0, 1, …, 27} × {0, 1, …, 27}.
We can even iterate the Cartesian product by
thus obtaining n-tuples.
Here’s another example. We’ve mentioned the set of rational numbers briefly:
We’ve gotten used to writing things such as the ratio a/b without questioning its meaning. However, when constructing ℚ from ℤ for the first time, the expression “a/b” doesn’t make any sense.
Think about it: we only know
the set of integers ℤ = {…, -2, -1, 0, 1, 2, …},
and how to add, subtract, and multiply two integers together.
We don’t have anything like “a/b” in our vocabulary. However, we have the Cartesian product! Thus, we can define ℚ by
and define addition and multiplication by
Building upon the mathematical structure (ℚ, +, ·), we can give meaning to a/b by identifying it with the tuple (a, b):
Mathematics is like particle physics: you can’t define a proton in terms of an atom, as protons come first.
Now that we know what tuples are, it’s time to think about what they represent. Tuples are the fundamental data structure of mathematics. In the example of the Euclidean plane, they express coordinates such as (13.2, -43.6).
Is there a deeper meaning to tuples than simply finite-length sequences?
Yes. Meet the relations.
Relations
Let’s talk about the symbol “<“.
Fun fact. We semi-officially call < and > “duck beak” in Hungarian because it looks like exactly that. An open duck beak.
Mathematically speaking, what is the relation <? We understand this intuitively, but at this point, we don’t have an exact mathematical structure that is <. Or >. Or ≤. Or ≥. Or any relation.
This situation is exactly like the one we had with rational numbers, and the solution will be the same: Cartesian products.
Let’s shoot first, ask questions later define first, explain later.
Definition. (Relations.) Let A and B be two sets. Any subset ρ ⊆ A × B is called a relation over A and B.
If (a, b) ∈ ρ, we write a ρ b.
It seems simple, but it’s a rather deep concept. Here are a few examples.
Example 1. (Ordering on ℕ.) Intuitively, we all understand the meaning of <. Here’s the mathematical definition.
Yes, it’s not pretty. But hey, at least it’s precise. The visual version is much prettier.
There’s much more to relations than orderings. Here’s one more example.
Example 2. (Divisibility.) We are all familiar with the divisibility property: for any two integers m, n, we say that m | n if n = m · k for some integer k. Divisibility is a relation as well!
Example 3. Let’s consider a bit more abstract example, a relation f on the set
{1, 2, …, 10} × {1, 2, 3}, defined by
Just like before, let’s illustrate this!
Is this familiar? Yes, it looks eerily similar to a function graph, whatever functions might be.
In addition to the above, there is another way to illustrate the relation f. Let’s use dots and arrows this time! For each tuple (a, b), we can indicate the relation by directing an arrow from a to b.
This illustration is not just familiar—we’ve seen the very same image! That’s right: f is a function indeed.
It’s time to finally unwrap what functions really are!
Functions
Don’t ask me why, but I prefer to jump straight into the definitions nowadays. Here it is.
Definition. (Functions.) Let A and B be two sets and f ⊆ A × B be a relation. We say that f is a function if for every a ∈ A, there is at most one b ∈ B such that (a, b) ∈ f.
In this case, A is called the domain, and B is called the image of f.
Let’s draw a picture to see what’s going on. We’ll use the dots-and-arrows representation.
In (other) words, a relation is a function if every dot has at most one arrow starting from it. For any given input, the output is uniquely determined.
Notice that this is not the case in programming languages! Even though we call the object
from random import random
def random_addition(x):
return x + random()
a function in Python, it is not a function in the mathematical sense.
In practice, we define functions with expressions such as f(x) = eˣ or
Expressions like f(x) = eˣ are short for the relation
We also often write f: x ↦ eˣ, which indicates that f maps any x to eˣ.
In essence, mathematics is the never-ending process of expansion and compression. We make things complicated and then simple again through abstractions and abbreviations.
It's a matter of personal preference, but for me, functions are mathematics's most important building blocks. A neural network is a function, mapping a data point to a prediction. An image is a function, mapping a pixel to an intensity value. A voice recording is a function, mapping an instance of time to the value of air pressure.
Now that we are familiar with the notion of functions, we can start with the cool stuff. For instance, we can start counting the elements of sets. This is more exciting, than you think: we'll discover the infinite type of infinities this way.
See you next time!
Brilliant simplification. An interesting "Turing test" for an LLM would be: what percent of a Tivadar Danka tutorial can it reproduce? As of April 2024 it's around 5%.