This work is licensed under a
Creative Commons

Attribution-ShareAlike 4.0 International License

Source: codeberg.org/andybalaam

Attribution-ShareAlike 4.0 International License

Source: codeberg.org/andybalaam

Andy Balaam

element.io

element.io

Maths is:

- Trying to think clearly
- Developing a language that helps

Maths is:

- Trying to think clearly
- Developing a language that helps

- This is quite like programming

Sets are groups of things

- Fundamental to almost all of Maths
- The easy bits are quite boring
- The hard bits are just weird

Throw out what you know from programming

- Nothing to do with ordering
- Not really about uniqueness

Is x a member of A?

```
interface Set {
```*contains*(element: any): boolean;
}

x is a member of A:

`expect(A.`*contains*(x)).toBe(true);

x is not a member of A:

`expect(A.`*contains*(x)).toBe(false);

x is a member of A:

x is not a member of A:

```
class Set123 extends Set {
```*contains*(element: any): boolean {
return (
element === 1 ||
element === 2 ||
element === 3
);
}
}

`const s = new `*Set123*();
expect(s.contains(*1*)).toBe(true);
expect(s.contains(*3*)).toBe(true);
expect(s.contains(*0*)).toBe(false);
expect(s.contains(*4*)).toBe(false);

`const s = new ArrSet([`*"X"*, *"Y"*, *"Z"*]);
expect(s.contains(*"X"*)).toBe(true);
expect(s.contains(*"A"*)).toBe(false);
expect(s.contains(*3*)).toBe(false);
expect(s.contains(*new EmptySet()*)).toBe(false);

`class `*Intersection* implements Set {
constructor(
private set1: Set,
private set2: Set,
) {}
contains(element: any): boolean {
return (
*this.set1.contains(element) &&
this.set2.contains(element)*
);
}
}

Intersection of A and B:

Intersection of A and B:

Intersection of A and B:

Intersection of A and B:

`class `*Union* implements Set {
constructor(
private set1: Set,
private set2: Set,
) {}
contains(element: any): boolean {
return (
*this.set1.contains(element) ||
this.set2.contains(element)*
);
}
}

Union of A and B:

Union of A and B:

Subsets

```
is_subset_of(other: Set): boolean {
for (const element of this) {
if (
```*!*other.contains(element)) {
return *false*;
}
}
return *true*;
}

Subsets

```
is_subset_of(other: Set): boolean {
```*for (const element of this)* {
if (!other.contains(element)) {
return false;
}
}
return true;
}

Subsets

`abstract class `*IterableSet* implements Set, Iterable {
abstract contains(element: any): boolean;
*abstract [Symbol.iterator](): Iterator*;
is_subset_of(other: Set): boolean {
// ...

For all

A is a subset of B

Infinite sets

`class `*Evens* implements Set {
contains(element: any): boolean {
return (
typeof element === "number" &&
*element % 2 === 0*
);
}
}

All elements of this set?

```
class Evens implements Set {
*[Symbol.iterator](): Iterator
``` {
*yield 0;*
let i = 1;
while (true) {
*yield i * 2;*
*yield -i * 2;*
i++;
}
}
}

Sets can contain sets

```
export class AllSets implements Set {
```*contains*(element: any): boolean {
// We consider anything with a
// contains property to be a set!
return *!!element.contains*;
}
}

Sets can contain sets

```
const s = new AllSets();
expect(s.contains(
```*new EmptySet()*)).toBe(true);
expect(s.contains(*new Set123()*)).toBe(true);
expect(s.contains(*3*)).toBe(false);

AllSets is a member of itself

```
const s = new AllSets();
expect(
```*s.contains(s)*).toBe(true);

Algebra replaces numbers with variables

Algebra replaces numbers with variables

But what about the "+"?

We can replace that with a variable too

`interface `*Group* {
*set*(): Set;
*op*(left: any, right: any): any;
*identity*(): any;
}

A Group is:

Binary operation

```
class PlusMod5 extends Group {
...
```*op*(left: any, right: any): any {
return *(left + right) % 5*;
}
...
}

Binary operation

```
const g = new PlusMod5();
expect(g.
```*op*(1, 2)).toBe(3);
expect(g.*op*(4, 3)).toBe(2);

Binary operation

PlusMod5

0, 1, 2, 3, 4

+_{(mod 5)}

Rule 1: Closed

Rule 1: Closed

`class PlusMod5 extends Group {`

Rule 1: Closed

`class PlusMod5 extends `*Iterable*Group {
...
}
*for* (const x *of* g) {

Rule 1: Closed

```
for (const x of g) {
for (const y of g) {
const z =
```*g.op(x, y)*;
expect(*g.set().contains(**z*)).toBe(true);
}
}

PlusMod5 is closed

3 +_{(mod 5)} 4 = 2

Rule 2: Identity

```
const idt = g.identity();
for (const x of g) {
expect(
```*g.op(idt, x)*).toEqual(*x*);
expect(*g.op(x, idt)*).toEqual(*x*);
}

Rule 2: Identity

Rule 2: Identity

PlusMod5 has an identity

2 +_{(mod 5)} 0 = 2

0 +_{(mod 5)} 2 = 2

Rule 3: Inverses

```
for (const x of g) {
expect(
```*has_inverse*(x, g).toBe(true);
}

Rule 3: Inverses

`function `*has_inverse*(e: any, g: Group): boolean {
for (const y of g) {
if (
*g.op(e, y) === g.identity()* &&
*g.op(y, e) === g.identity()*
) {
return true;
}
}
return false;
}

Rule 3: Inverses

PlusMod5 has inverses

2 +_{(mod 5)} 3 = 0

4 +_{(mod 5)} 1 = 0

Rule 4: Associative

PlusMod5 is associative

2 +_{5} (3 +_{5} 1) = 1

(2 +_{5} 3) +_{5} 1 = 1

Optional: Commutative

PlusMod5 is commutative

1 +_{5} 3 = 3 +_{5} 1

A non-commutative group: D6

Things you can do to a triangle

A non-commutative group: D6

A non-commutative group: D6

rot120 + hflip = tlflip

A non-commutative group: D6

hflip + rot120 = trflip

A non-commutative group: Rubik's Cube Group

Image created by Booyabazooka, CC BY-SA 3.0, via Wikimedia CommonsA non-commutative group: Rubik's Cube Group

Number of members:

43,252,003,274,489,856,000

Infinite groups:

The real numbers under multiplication

Famous groups:

Elliptic Curve group

Image created by GYassineMrabetTalk✉, CC BY-SA 3.0, via Wikimedia CommonsFamous groups:

Elliptic Curve group

Adapted from an image by SuperManu, CC BY-SA 3.0, via Wikimedia CommonsDots and lines

Vertices and edges

`interface Finite`*Graph*<V> {
*vertices*(): Array<V>;
*edges*(): Array<[V, V]>;
}

```
class K3 implements FiniteGraph<string> {
vertices(): Array<string> {
return
```*["a", "b", "c"]*;
}
edges(): Array<[string, string]> {
return *[
["a", "b"],
["b", "c"],
["a", "c"],
]*;
}
}

Connected

Disconnected

`function `*is_connected*<T>(g: FiniteGraph<T>): boolean {
const *found* = [g.vertices()[0]];
for (const path of *all_paths_from*(g, g.vertices()[0])) {
for (const n of path) {
if (*!found.includes(n)*) {
*found.push(n)*;
if (found.length === g.vertices().length) {
return true;
} } } }
return found.length === g.vertices().length;
}

Degree of a vertex

deg(v) = 4

Degree of a vertex

`function `*degree*<V>(v: V, g: FiniteGraph<V>): number {
let ret = 0;
for (const [from, to] of *g.edges()*) {
if (*from === v || to === v*) {
ret++;
}
}
return ret;
}

Eulerian circuit

- visit every edge exactly once
- get back where we started

Eulerian circuit

Eulerian circuit

Eulerian circuit

Eulerian circuit

Eulerian circuit

Eulerian circuit

Eulerian circuit

Eulerian circuit

Eulerian trail

(Obviously?)

Every time you enter, you leave again

(Obviously.)

Euler's Theorem (Carl Heirholzer)

Directed graphs

Secret Santa

- Everyone gives one present
- Everyone receives one present
- No-one gives to the same person they receive from
- Don't want to buy for my partner
- Make sure X doesn't buy for Y because that was a disaster last year

Secret Santa

- Everyone gives one present
- Everyone receives one present
- No-one gives to the same person they receive from
- Don't want to buy for my partner
- Make sure X doesn't buy for Y because that was a disaster last year

Secret Santa

- Everyone gives one present
- Everyone receives one present
- No-one gives to the same person they receive from
- Don't want to buy for my partner
- Make sure X doesn't buy for Y because that was a disaster last year

Secret Santa

- Everyone gives one present
- Everyone receives one present
- No-one gives to the same person they receive from
- Don't want to buy for my partner
- Make sure X doesn't buy for Y because that was a disaster last year

Secret Santa

Secret Santa

Directed graph of who can give to whom

Secret Santa

Directed graph of who can give to whom

Secret Santa

- Find a circuit in a directed graph
- That visits all vertices

Secret Santa

This is called a Hamiltonian circuit

Santa Circles!

Finding Hamiltonian circuits in Rust

See my PR in petgraph^{[1]}

Implementation is based on Frank Rubin's^{[2]}

[2] Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits",

Rubin's algorithm to find Hamiltonian circuits

- Basic idea: walk all paths until you find one
- But, at each step, eliminate lots of useless edges and impossible paths

Rubin's algorithm to find Hamiltonian circuits

If one edge definitely leaves a vertex, no others do.

Rubin's algorithm to find Hamiltonian circuits

If two definite edges go to the same place, stop.

- Uncountable infinity
- Russell's Paradox
- Directed acyclic graphs (DAGs)
- The Monster group
- The Four Colour Theorem