Part 1 · 1 chapters · ~8 min

Sets and Functions

Sets, membership, subsets, union, intersection, difference and complement, power sets and Cartesian products, types as sets (union and product types), functions, domains and codomains, injective, surjective and bijective functions, composition and inverses, and cardinality including countable and uncountable sets.

Sets are types; functions are mappings

code

const a = new Set(['NGN', 'USD', 'GHS']), b = new Set(['USD', 'KES']);
const union = new Set([...a, ...b]);                         // A ∪ B
const inter = new Set([...a].filter(x => b.has(x)));        // A ∩ B = {USD}
const diff  = new Set([...a].filter(x => !b.has(x)));       // A \ B = {NGN, GHS}

// types as sets: a union type is a set union, an object type is a Cartesian product
type Currency = 'NGN' | 'USD' | 'GHS';                       // |Currency| = 3
type State = 'pending' | 'settled';                          // |State| = 2
type Payout = { currency: Currency; state: State };          // |Payout| = 3 × 2 = 6 combinations
// the power set of n flags has 2^n members: 10 feature flags = 1,024 configurations to test

Cardinality: two sets have the same size if a bijection exists between them. The integers and rationals are countable (listable), but the real numbers are not (Cantor's diagonal argument), the same argument used to prove the halting problem undecidable (Theory of Computation P4).

FUNCTIONS AS MAPPINGS

injective, surjective, bijective

swipe the figure sideways, or tap expand for full screen

1/4

a function

A function maps each input in its domain to exactly one output in its codomain. A TypeScript signature (x: A) => B states exactly that: domain A, codomain B.

each input → one outputtypes are domains