{ The joy | of sets }

Woah, your set is on fire
Let's talk about sets, baby
Set Bomb
The Kamasetra

Everyone needs a data structure

Choose the right structure for the job

  • Vectors $(x, y, z)$, matrices $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$, $n$-dim. arrays
  • Functions $A \to B$ (hashmaps/dictionaries)
  • Graphs A drawing of the Petersen graph in the plane (weights, labels?)
  • Extendable lists (programmer's array)
  • Database?

Then choose an implementation

Example: programmers' lists

  • Array (dynamic?)
  • Sketch of an array
  • Linked list (doubled?)
  • Sketch of a singly-linked list

Trade-offs; depends on use-case

A data structure for mathematics?

  • Simple
  • Expressive
  • Consistent
  • Explicit (no hand-waving)
  • Handles infinity (infinities?)

What trade-offs will we need to consider?

What is a set, anyway?

Easy to write down examples:

  • $\{1, 2, 3\}$, $\{ \text{red}, \text{white}, \text{blue} \}$
  • $\mathbb{N} = \{1, 2, 3, 4, \dotsc\}$ (naughty)
  • $\{ \text{humans}\ h \mid h\ \text{was born in 1992} \} \ni \text{me}$
  • $\{ \text{continuous functions}\ f \colon \mathbb{R} \to \mathbb{R} \}$

Hard to define a set precisely!

Cantor's definition

By an ‘aggregate’ (Menge) we are to understand any collection into a whole $M$ of definite and separate objects $m$ of our intuition or thought. These objects are called the ‘elements’ of $M$.

  • Simple ✔, Explicit ✗

Another definition

  • A set $S$ is something for which we can decide if any object $s$ belongs to $S$. "S has decidable membership"
  • Simple ✔, Explicit ✗ Decide? Object?

Simple bricks build complex houses

Can we describe everything using sets?

Sets are unordered: $\{x, y\} = \{y, x\}$.

What if we want tuples, where $(x, y) \neq (y, x)$?

  • Kurtowski defined $(x, y)$ to be the set $\{ \{x \}, \{x, y\} \}$.
  • Check that $(a, b) = (c, d)$ iff $a = c$ and $b = d$.
  • Extends recursively to $$(x_1, \dotsc, x_n) = \{ (x_1, \dotsc, x_{n-1}), \{x_1, \dotsc, x_n\} \}.$$

How can we use sets to count?

  • Define $0 = \{ \, \} = \emptyset$.
  • Define $1 = \{ 0 \} = \{ \{ \} \} = \{\emptyset\}$. (note $1 \neq 0$, a good sign!)
  • Define $2 = \{ 0, 1 \} = \{ \emptyset, \{ \emptyset \} \}$.
  • Recursively define $n = \{0, \dotsc, n-1 \}$.

This generalises to ordinal numbers, which classify "well-ordered sets".

  • A set with order type omega + omega

Why even bother?

  • Fewer assumptions and primitives to worry about.
  • If sets are logically consistent, so is anything built out of them.

On the other hand:

  • Would never implement a list or number like this on a computer!
  • Theoretical, for reassurance

Forget about the bricks

Constructing things using sets is mostly academic.

  • Nobody literally thinks of $4$ as $\{ \emptyset, \{ \emptyset \}, \{\emptyset, \{\emptyset\}\}, \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\} \}$!
  • What matters are the properties of $4$

  • C.f. object-oriented programming: classes versus interfaces

  • Punchline: any foundation of maths is fine, as long as it's expressive and consistent.

What could possibly go wrong?

Russell's paradox

A simple (naive) definition of a set causes problems.

  1. Let $V$ be the set $V = \{ \text{sets}\ x \mid x \notin x\}$.
  2. If $V \in V$, then $V \notin V$.
  3. Else $V \notin V$, and then $\neg(V \notin V)$, i.e. $V \in V$.
  4. Thus $V \in V \iff V \notin V$.
  5. 😕

Uh-oh!

A statement can't be true and false at the same time.

What could be wrong with our logic? Options:

  • Maybe $V = \{ \text{sets}\ x \mid x \notin x \}$ isn't a set?
  • Maybe $x \in x$ doesn't make logical sense?
  • Maybe logic is wrong: $\neg(V \notin V) ⇏ V \in V?$

Solution: axioms (paranoia)

Specify how sets should behave. Some highlights:

  1. If $S$ is a set, so too is $\{ s \in S \mid s\ \text{has property}\ P\}$.
  2. Power sets $\mathcal{P}(X) = \{ \text{sets}\ U \mid U \subseteq X \}$ exist.
  3. Infinite sets exist; unions exist.

All together there are eight ZF axioms.

Consequence: there is no set of all sets

  • Suppose there were such a set $U$.
  • $V = \{ x \in U \mid x \notin x \}$ is a set, by axiom 1 above.
  • $\to$ Russell's Paradox $\to$ 😞 $\to$ contradiction.

Workaround: use a different word.

  • e.g. the class, family or collection of all sets

The axiom of choice

A scary 9th axiom on top of ZF.

Let $\{S_i\}_{i \in I}$ be nonempty sets indexed by $I$. Then we can choose an element $x_i \in S_i$ for each $i \in I$.

What does "choose" mean when $I$ or $S_i$ is infinite?

  • If you give me sets $N_i \subseteq \mathbb{N}$ of natural numbers,
  • I can specify $x_i \in N_i$ by saying $x_i = \min N_i$.

The axiom of choice (AC) is powerful, but gives nonconstructive proofs.

  • If I give you sets $R_i \subseteq \mathbb{R}$ of real numbers,
  • Can you give a recipe for selecting an $x_i \in R_i$?
  • Can't say min/max, e.g. $R_i = \{ x \in \mathbb{R} \mid x > 0 \}$.

AC tells us something exists, but not how to find it.

What's the problem?

AC implies or is equivalent to many reasonable, and many unreasonable statements.

  • Every vector space has a basis.
  • A sphere can be broken down into two spheres of the same volume. (Banach-Tarski paradox)
  • Any product (even infinite) of compact spaces is compact. (Tychonoff's Theorem)

AC is used begrudgingly and with suspicion.

Are there any alternatives?

  • Categories: "functions are more important than sets"
  • [Homotopy] type theory (programming languages)
  • Constructive mathematics:
    • "there must exist an $x$ because..."
    • "we can build such an $x$ by..."
  • Metamathematics: model theory, proof theory, reverse mathematics (philosophy?)
  • Formal methods; automated theorem proving?

Fuzzy set theory

Any object $x$ either does or does not belong to a set $V.$

Membership is binary: true or false.

  • A fuzzy set $U$ assigns a number $0 \leq \mu_A(x) \leq 1$ to each object $x$. ("how much" is $x$ contained in $A$?)
  • Clasically: $x \in A \leftrightarrow \mu_A(x) = 1$ and $x \notin A \leftrightarrow \mu_A(x) = 0$.
  • True/false replaced with a "degree of belief"

Hot fuzz

Can define unions, intersections and complements of fuzzy sets which take into account the fuzziness described by $\mu_A$.

  • Fuzzy control systems, for automation that needs more than just ON/OFF outputs
  • Sendai railway in Japan; other industrial applications to improve efficiency
  • Useful in AI?

tl;dr: Sets

  • data structure for mathematics
  • more complicated than you might think
  • naive definition has problems (Russell's paradox)
  • formal axiomatisation—with controversy (AC)
  • sets work well, but there are alternatives

Danke schön!