Functions

Understanding Functions

A function is a rule that assigns exactly one output to every input from a given domain. Discrete mathematics focuses heavily on classifying functions by their behavior — whether they hit every possible output, whether two different inputs can ever share an output, and whether they can be reliably reversed. These classifications aren't just theoretical: they determine whether a piece of code can be safely inverted, whether a hash function is prone to collisions, and whether an encoding scheme loses information.

Key Definitions & Formulas

• Injective (one-to-one): no two distinct inputs map to the same output.
• Surjective (onto): every element of the codomain is hit by at least one input.
• Bijective: both injective and surjective — a function that pairs up domain and codomain perfectly and therefore has an inverse.
• Composition (f ∘ g)(x): apply g first, then feed the result into f.
• Inverse (f⁻¹): exists only for bijective functions; swaps every input/output pair.

Worked Example

Let f = {1→a, 2→b, 3→c} from {1,2,3} to {a,b,c}. Since every input maps to a different output (injective) and every codomain element is used (surjective), f is bijective, so its inverse exists: f⁻¹ = {a→1, b→2, c→3}, found simply by reversing every arrow.

Where This Is Used

• Cryptography, where encoding/decoding functions must be bijective to be reversible.
• Hash tables and hashing algorithms, where injectivity minimizes collisions.
• Database keys and lookups, which rely on functions being well-defined and often one-to-one.
• Compiler theory, where type-checking relies on precisely defined mappings.