Functions & Relations
The problem
Once we can describe collections, we need to describe how elements of one collection correspond to elements of another — deterministically (functions) or loosely (relations). Without this, 'mapping', 'lookup', and 'transformation' have no precise meaning.
Why now
Sets alone are static — they say what exists, not how things connect. Logic alone judges truth, not correspondence. Describing 'every user has exactly one email' or 'orders reference products' requires a formal notion of mapping between sets.
Mental model
A function is a machine with a guarantee: same input, same output, always exactly one. A relation drops the guarantee — it is just a set of pairs, any connection you can write down. Hash maps, database foreign keys, and pure functions in code are all this one idea wearing different clothes.
Requires
- Sets & LogicMathematical Thinking
A function is defined as a special set of ordered pairs between two sets (domain and codomain); without set vocabulary the definition cannot even be stated.
Unlocks
- Computability & the Halting ProblemComputer Science Fundamentals
- The Relational Model & SQLDatabase Engineering
- Normalization & Schema DesignDatabase Engineering
- Proof TechniquesMathematical Thinking
- Combinatorics & CountingMathematical Thinking
- Graph Theory BasicsMathematical Thinking
- Modular ArithmeticMathematical Thinking
- Logarithms & ExponentsMathematical Thinking
- Algebraic StructuresMathematical Thinking
- Functions & ScopeProgramming Fundamentals
- Arrays & ListsProgramming Fundamentals
- Mutability & ReferencesProgramming Fundamentals
Parallel
Used in
- Pure functions and referential transparency in functional programming
- Hash maps / dictionaries (finite functions from keys to values)
- Database foreign keys and one-to-many / many-to-many relations
- React: UI = f(state) — the view as a function of data
Projects
- Model a small e-commerce schema purely as relations between sets, then identify which relations are functions
- Take three impure functions from your own code and refactor each into a pure function plus an effect
Examples
- Map<UserId, Email> is a function; the 'follows' table on a social network is a relation that is not a function
- Injective = no collisions (perfect hashing); surjective = every output reachable (full test coverage of states)
Resources
Mastery checklist
- I can state what makes a relation a function and give a code example of each
- I can explain injective, surjective, and bijective with one data-modeling example each
- I can explain why function composition order matters and connect it to pipeline design
- I can decide whether a real-world correspondence (e.g. user→sessions) is a function or a relation and say why it matters for the schema