• Overview
• Details
• Exercises

Relations generalize pairings between elements of sets, while functions are relations with a single, well-defined output for each input. Properties like reflexivity, symmetry, and transitivity structure relations; injective/surjective/bijective properties characterize functions.

• Relations on a set A: subsets of A×A; properties: reflexive, symmetric, antisymmetric, transitive
• Equivalence relations and partitions; equivalence classes
• Partial orders (posets), Hasse diagrams; total orders
• Functions: domain, codomain, image; injective, surjective, bijective; inverses and composition
• Function restrictions, extensions, characteristic functions; indicator notation

1. Prove that a given relation is an equivalence relation and describe its classes.
2. Give an example of an injective but not surjective function from N→N, and vice versa.
3. Show that the composition of bijections is a bijection and derive the inverse.