Functions Summary

Discrete Math · Axiom Academy

SUMMARY Functions and Relations Let's review how relations capture connections between elements and functions provide deterministic mappings—fundamental concepts in databases, programming, and abstract algebra. Definition: A relation R from set A to set B is a subset of the Cartesian product A × B. Notation: R ⊆ A × B Ordered Pairs: If (a, b) ∈ R, we say "a is related to b" and write aRb Three Representations: Relations can be shown as sets of ordered pairs, matrices, or directed graphs—each captures the same information Real-World Examples: Social networks (friendships), databases (foreign keys), family trees (parent-child), divisibility (number theory) Reflexive: Every element relates to itself. For all a ∈ A, aRa . Example: "equals" (=) Symmetric: If a relates to b, then b relates to a. If aRb , then bRa . Example: "is married to" Antisymmetric: If a relates to b and b relates to a, then a = b. Example: "less than or equal to" (≤) Transitive: If a relates to b and b relates to c, then a relates to c. Example: "is an ancestor of" Equivalence Relation: Reflexive, symmetric, and transitive. Divides set into disjoint equivalence classes. Example: modular arithmetic (≡ₙ) Partial Order: Reflexive, antisymmetric, and transitive. Provides a way to compare elements. Example: divisibility (|), subset relation (⊆) Total Order: A partial order where every pair of elements is comparable. Example: ≤ on real numbers

This is the written version of the interactive lesson above. See the full Discrete Math course.