Intro to sets
Set theory is an important area of math which lays as a foundation of many computer science topics, such as databases and types in programming. Set theory isn’t difficult conceptually, and is generally nice to think about, especially if you like to visualize.
A set is simply a collection of things. A thing can be anything: name, object, idea. It’s a very abstract notion. For example, I can define a set of movies I have seen: American Pie, Breakfast Club, The Room. Yes, I have only seen those three movies in my entire life. I am busy writing texts about set theory.
Actually, I’ve watched The Room five times. Does this affect the set? No, because it doesn’t change the notion of “what movies I have watched”. This obvious idea is an integral property of sets: they contain only unique objects. (Nothing stops us from defining a set of movie viewings, though. In that case, each element would be a particular instance of a “movie watching event”, and, in my sad case, would contain 7 elements.)
If an object o is in set A, we say o is a member of A. To express this fact easily, mathematicians use the following notation: o \in A. So, if A = \textrm{Movies I've watched} and o = \textrm{The Room}, then o \in A. But if b = \textrm{Avengers}, then b \notin A. Now you can generate infinitely many “nerdy” T-shirts with prints like \textrm{joy} \in \textrm{mylife} or \textrm{party} \in \textrm{dahouse}. If we were to look inside set A, it might look like this:
\{s, m, o\}
Sets don’t have the notion of order, so it doesn’t matter how you mention its members as long as you mention them all. So, all these describe the same set A:
- \{s, m, o\}
- \{s, o, m\}
- \{m, s, o\}
We are lucky: set A is finite and quite small. But sets can be infinite, and it would be impossible to write down all of its members. There are ways to describe such sets nevertheless. For example, the set of all natural numbers from 1 to n can be described like so:
\{1, 2, 3, 4, ... n\}
Here we rely on reader’s common sense and assume he or she can rightfully deduce what is meant by the ellipsis (...). Notations like this are very common in math, and while it isn’t awfully strict, the idea is to be as unambiguous as possible. For example, when describing a set of odd natural numbers from 1 to n, this would be bad:
\{1, 3, ... n\}
simply because the sample isn’t long enough to make a single assumption. Another example of a set that exists in math is the set of Boolean values:
\mathcal{B} = \{T, F\}
T and F stand for True and False. Certain tests (or, in other words, questions) that can be answered with “yes” and “no”, produce values of said set. So, we can say that
(x > y) \in \mathcal{B}, \textrm{where } x \in \mathbb{N} \textrm{ and } y \in \mathbb{N}
In other words, the answer to the question “is x greater than y” is a member of set \mathcal{B}, as long as x and y are members of \mathbb{N} (i.e. natural numbers).
Math in infinitely composable. Most programming languages can only dream of the level of composability and flexibility mathematicians enjoy. While not immediately useful, we could compose the following statements about sets:
((x + y) \in \mathbb{N}) \in \mathcal{B}, \textrm{where } x, y \in \mathbb{N}
Here we said “when x and y are members of \mathbb{N}, then the answer to the question”is x + y a member of \mathbb{N}" is a member of \mathcal{B}. "
Many groups in mathematics are sets: numbers of different types (natural, irrational, complex, etc.), notions of different types (e.g. Boolean), solutions to particular problems (e.g. graphs that satisfy a certain property). But describing groups of elements is just the tip of the iceberg. Set theory, with its axioms and definitions, can play a role of a foundational area of math, from which many other areas can be derived. In this book we’re not going to talk about how set theory (and category theory) can “generate” a large portion of the whole math. But these topics are among the most fascinating frontiers of modern mathematics.