# 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 (weights, labels?)
• Extendable lists (programmer's array)
• Database?

## Then choose an implementation

Example: programmers' lists

• Array (dynamic?)

## 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".

### 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

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?

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