 This work is licensed under a Creative Commons

Source: codeberg.org/andybalaam

# Maths: the fun parts

Andy Balaam
element.io

## Isn't Maths hard?

Maths is:

• Trying to think clearly
• Developing a language that helps

## Isn't Maths hard?

Maths is:

• Trying to think clearly
• Developing a language that helps
• This is quite like programming

## Sets

Sets are groups of things

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

## Sets

Throw out what you know from programming

• Nothing to do with ordering

## Sets

Is x a member of A?

## Sets

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

## Sets

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);`

## Sets

x is a member of A: x is not a member of A: ## Sets

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

## Sets

```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);```

## Sets

```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);```

## Sets

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

## Sets

Intersection of A and B: ## Sets

Intersection of A and B: ## Sets

Intersection of A and B: ## Sets

Intersection of A and B: ## Sets

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

## Sets

Union of A and B: ## Sets

Union of A and B: ## Sets

Subsets

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

## Sets

Subsets

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

## Sets

Subsets

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

## Sets

For all ## Sets

A is a subset of B ## Sets ## Sets

Infinite sets

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

## Sets ## Sets ## Sets

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

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

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);```

## Sets ## Sets

AllSets is a member of itself

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

## Sets ## Groups

Algebra replaces numbers with variables ## Groups

Algebra replaces numbers with variables ## Groups ## Groups

We can replace that with a variable too ## Groups

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

## Groups

A Group is: ## Groups

Binary operation

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

## Groups

Binary operation

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

## Groups

Binary operation PlusMod5

0, 1, 2, 3, 4

+(mod 5)

## Groups

Rule 1: Closed ## Groups

Rule 1: Closed

`class PlusMod5 extends Group {`

## Groups

Rule 1: Closed

```class PlusMod5 extends IterableGroup { ... } for (const x of g) {```

## Groups

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); } }```

## Groups

PlusMod5 is closed

3 +(mod 5) 4 = 2

## Groups

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); }```

## Groups

Rule 2: Identity ## Groups

Rule 2: Identity ## Groups

PlusMod5 has an identity

2 +(mod 5) 0 = 2

0 +(mod 5) 2 = 2

## Groups

Rule 3: Inverses

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

## Groups

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; }```

## Groups

Rule 3: Inverses ## Groups

PlusMod5 has inverses

2 +(mod 5) 3 = 0

4 +(mod 5) 1 = 0

## Groups

Rule 4: Associative ## Groups

PlusMod5 is associative

2 +5 (3 +5 1) = 1

(2 +5 3) +5 1 = 1

## Groups

Optional: Commutative ## Groups

PlusMod5 is commutative

1 +5 3 = 3 +5 1

## Groups

A non-commutative group: D6

Things you can do to a triangle ## Groups

A non-commutative group: D6 ## Groups

A non-commutative group: D6

rot120 + hflip = tlflip ## Groups

A non-commutative group: D6

hflip + rot120 = trflip ## Groups

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

## Groups

A non-commutative group: Rubik's Cube Group

Number of members:

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

## Groups

Infinite groups:

The real numbers under multiplication ## Groups

Famous groups:

Elliptic Curve group Image created by GYassineMrabetTalk✉, CC BY-SA 3.0, via Wikimedia Commons

## Groups

Famous groups:

Elliptic Curve group Adapted from an image by SuperManu, CC BY-SA 3.0, via Wikimedia Commons

## Graphs

Dots and lines ## Graphs

Vertices and edges ## Graphs

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

## Graphs

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

## Graphs

Connected ## Graphs

Disconnected ## Graphs

```function is_connected<T>(g: FiniteGraph<T>): boolean { const found = [g.vertices()]; for (const path of all_paths_from(g, g.vertices())) { 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; } ```

## Graphs

Degree of a vertex deg(v) = 4

## Graphs

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; }```

## Graphs

Eulerian circuit

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

## Graphs

Eulerian circuit ## Graphs

Eulerian circuit ## Graphs

Eulerian circuit ## Graphs

Eulerian circuit ## Graphs

Eulerian circuit ## Graphs

Eulerian circuit ## Graphs

Eulerian circuit ## Graphs

Eulerian circuit ## Graphs

Eulerian trail ## Graphs (Obviously?)

## Graphs

Every time you enter, you leave again ## Graphs (Obviously.)

## Graphs Euler's Theorem (Carl Heirholzer)

## Graphs

Directed graphs ## Graphs

Secret Santa

• Everyone gives one present

## Graphs

Secret Santa

• Everyone gives one present
• No-one gives to the same person they receive from

## Graphs

Secret Santa

• Everyone gives one present
• No-one gives to the same person they receive from
• Don't want to buy for my partner

## Graphs

Secret Santa

• Everyone gives 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

## Graphs

Secret Santa ## Graphs

Secret Santa Directed graph of who can give to whom

## Graphs

Secret Santa Directed graph of who can give to whom

## Graphs

Secret Santa

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

## Graphs

Secret Santa This is called a Hamiltonian circuit

## Graphs

Santa Circles! santacircles.artificialworlds.net

## Graphs

Finding Hamiltonian circuits in Rust

See my PR in petgraph

Implementation is based on Frank Rubin's github.com/petgraph/petgraph/pull/494
 Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits", Journal of the ACM, 21 (4): 576–80

## Graphs

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

## Graphs

Rubin's algorithm to find Hamiltonian circuits If one edge definitely leaves a vertex, no others do.

## Graphs

Rubin's algorithm to find Hamiltonian circuits If two definite edges go to the same place, stop.

## Things we didn't talk about

• Uncountable infinity