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

Example: programmers' lists

- Array
*(dynamic?)* - Linked list
*(doubled?)*

Trade-offs; depends on use-case

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

What trade-offs will we need to consider?

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!

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 ✗

- 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?*

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\} \}.$$

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

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

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

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

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

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?$

Specify how sets should behave. Some highlights:

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

All together there are eight **ZF axioms**.

- 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

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.

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.

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

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"

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?

- 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