What is a Function?
In discrete mathematics, a function is a rule that assigns each element from a set called the Domain to exactly one element in a set called the Codomain. This "exactly one output" rule is the cornerstone of how functions work, ensuring predictability and reliability in mathematical and computational systems.
The Formal Definition
Mathematically, a function \( f \) from a set \( A \) (the domain) to a set \( B \) (the codomain) is a subset of the Cartesian product \( A \times B \) such that for every element \( a \in A \), there is exactly one element \( b \in B \) for which \( (a, b) \) is in the subset. We write this as \( f: A \to B \).
This means two conditions must be met:
- Total: Every element in the domain \(A\) must be mapped to some element in the codomain \(B\).
- Well-defined: No element in the domain \(A\) can be mapped to more than one element in the codomain \(B\).
Visualizing the Rule
This IS a Function
Each element in the Domain maps to exactly one element in the Codomain.
Domain
Codomain
This IS NOT a Function
Element '1' in the Domain maps to two different elements in the Codomain.
Domain
Codomain
This IS NOT a Function
Element '3' in the Domain has no mapping in the Codomain.
Domain
Codomain
Domain
The complete set of all possible inputs for the function, as shown in the visualization.
Example: {1, 2, 3}
Codomain
The set of all potential outputs. The function's outputs must belong to this set.
Example: {A, B, C}
Range
The set of actual outputs the function produces. The range is a subset of (or equal to) the codomain.
Example (for the valid function): {A, B}
Properties of Functions
Functions are classified by how their inputs map to their outputs. These properties are crucial for understanding a function's behavior and its suitability for tasks like database indexing, cryptography, and resource allocation.
Injective
(One-to-One)
Definition: A function where every distinct element of the domain maps to a distinct element of the codomain.
\( \forall a, b \in X, f(a) = f(b) \Rightarrow a = b \)
Example:
\(f: \mathbb{Z} \rightarrow \mathbb{Z}, f(x) = 2x + 1\)
(Each output has exactly one input)
Surjective
(Onto)
Definition: A function where every element in the codomain has at least one corresponding element in the domain.
\( \forall y \in Y, \exists x \in X : f(x) = y \)
Example:
\(f: \mathbb{R} \rightarrow [0, \infty), f(x) = x^2\)
(Every non-negative real number is a square of some real number)
Bijective
(Injective & Surjective)
Definition: A function that is both one-to-one and onto. Every element in the codomain is mapped by exactly one element from the domain.
\( \forall y \in Y, \exists! x \in X : f(x) = y \)
Example:
\(f: \mathbb{R} \rightarrow \mathbb{R}, f(x) = x + 3\)
(Every real number has exactly one pre-image)
Injective (but not Surjective)
One-to-One: Yes (no two inputs share an output).
Onto: No (element 'D' is not an output).
Surjective (but not Injective)
One-to-One: No (inputs '2' and '4' both map to 'B').
Onto: Yes (every codomain element is an output).
Neither Injective nor Surjective
One-to-One: No (inputs '2' and '3' both map to 'B').
Onto: No (elements 'C' and 'D' are not outputs).
Counting Number of Functions
Let \(A\) and \(B\) be two finite sets with \(|A| = m\) and \(|B| = n\). We can count the number of functions with specific properties that can be defined from \(A\) to \(B\).
Total Number of Functions
Each of the \(m\) elements in set \(A\) can be mapped to any of the \(n\) elements in set \(B\).
\( n^m \)
Example:
If \(|A| = 3\) and \(|B| = 2\), the total number of functions is \(2^3 = 8\).
Injective (One-to-One)
Possible only if \(m \le n\). The number of injective functions is given by the permutation formula.
\( P(n, m) = \frac{n!}{(n-m)!} \)
Example:
If \(|A| = 3\) and \(|B| = 4\), the number of injective functions is \(P(4,3) = \frac{4!}{1!} = 24\).
Surjective (Onto)
Possible only if \(m \ge n\). The formula uses the principle of inclusion-exclusion.
\( \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)^m \)
Example:
If \(|A| = 4\) and \(|B| = 3\), the number of surjective functions is 36.
Bijective (One-to-One & Onto)
Possible only if \(m = n\). The number of bijective functions is the number of permutations of the set.
\( n! \)
Example:
If \(|A| = 3\) and \(|B| = 3\), the number of bijective functions is \(3! = 6\).
Function Composition
Function composition is a fundamental operation that takes two functions and produces a new function by applying one function to the result of another.
Definition
Given two functions:
f: A → B
g: B → C
The composition of g with f, denoted as g∘f, is defined as:
(g∘f)(x) = g(f(x))
(First apply f to x, then apply g to the result)
Example:
Let f(x) = 2x + 3 and g(x) = x²
Then (g∘f)(x) = g(f(x)) = (2x + 3)²
And (f∘g)(x) = f(g(x)) = 2x² + 3
(Note that g∘f ≠ f∘g in general)
Properties
- • Associativity: h∘(g∘f) = (h∘g)∘f
- • Identity: f∘id = f and id∘f = f, where id is the identity function
- • Composition of injective functions is injective
- • Composition of surjective functions is surjective
Interactive Example
Given functions:
Composition: (g∘f)(x) = g(f(x)) = (2x + 3)²
Try changing the input value to see how the composition works.
Inverse Functions
An inverse function essentially reverses the effect of the original function. Only bijective functions have inverses.
Definition
For a bijective function f: X → Y, the inverse function f⁻¹: Y → X satisfies:
f⁻¹(f(x)) = x for all x ∈ X
f(f⁻¹(y)) = y for all y ∈ Y
Example:
If f(x) = 2x + 3, then f⁻¹(y) = (y - 3)/2
Let's verify with x = 4:
f(4) = 2(4) + 3 = 11
f⁻¹(11) = (11 - 3)/2 = 4
Properties
- • The inverse of a bijection is also a bijection
- • (f⁻¹)⁻¹ = f
- • (g∘f)⁻¹ = f⁻¹∘g⁻¹ (order reverses in composition)
- • The graph of f⁻¹ is the reflection of f's graph over the line y = x
Finding Inverses
To find the inverse of a function f(x):
- Replace f(x) with y
- Swap x and y in the equation
- Solve for y
- Replace y with f⁻¹(x)
Note: Not all functions have inverses. Only bijective (one-to-one and onto) functions have inverses. For non-bijective functions, we can sometimes restrict the domain to make them invertible.
Key Function Types
Discrete mathematics utilizes several specialized functions that are fundamental to computer science. Explore these functions through interactive graphs and calculators below.
Identity Function
The identity function returns the same value that was used as its argument. It's the simplest form of a function and serves as the identity element in function composition.
Graph of f(x) = x
The identity function is a straight line at 45 degrees passing through the origin.
Properties
- • Definition: f(x) = x for all x in the domain
- • Inverse: The identity function is its own inverse
- • Composition: f∘g = g∘f = g for any function g where composition is defined
- • Linear: It's a linear function with slope 1 and y-intercept 0
Try it out:
Constant Function
A constant function always returns the same output value regardless of the input. It's a horizontal line when graphed.
Graph of f(x) = c
The constant function is a horizontal line at y = c.
Properties
- • Definition: f(x) = c for some constant c and all x in the domain
- • Slope: The slope is 0 (completely flat)
- • Inverse: Not invertible (not one-to-one) unless the domain is a single point
- • Composition: f∘g is a constant function for any function g
Floor & Ceiling Functions
These functions map any real number to the nearest integer, either down (floor) or up (ceiling). They are fundamental in discrete mathematics and computer science for operations that require whole numbers.
Interactive Graph
The floor function (blue) rounds down to the nearest integer, while the ceiling function (green) rounds up.
Calculator
Floor ⌊x⌋
3
Ceiling ⌈x⌉
4
Try different values to see how floor and ceiling functions work.
Modulo Function
Calculates the remainder of a division. Essential for cyclic operations, hashing, and working with circular data structures.
Cyclic Nature
The modulo operation creates a repeating pattern, making it perfect for cycling through values.
Calculator
Remainder
2
17 ÷ 5 = 3 with a remainder of 2
Simple Hash Function
Maps data of any size to a fixed-size value. This example uses the division method, which is fundamental in hash table implementations.
Hash Distribution
A good hash function distributes values evenly across the hash space.
Try It Out
Hash Value (mod 128)
72
This is a simple hash using character codes and modulo operation.
Permutations
Calculates the number of ways to arrange 'k' items from a set of 'n' distinct items. Essential in probability and combinatorics.
Permutation Growth
Permutations grow factorially with n, making them computationally expensive for large n.
Calculator
P(5, 3) = 60
60
There are 60 ways to arrange 3 items from 5.
Applications in Computer Science
Functions are not just abstract concepts; they are the practical tools that power modern computing, from algorithm design to secure communications.
Algorithm Complexity Analysis
Functions describe how an algorithm's resource usage (like time or memory) scales with the input size ('n'). This helps us predict performance and choose efficient solutions. Toggle the lines to compare common growth rates.
Advanced Applications in AI & Computer Science
Functions are the core building blocks in many advanced fields, enabling everything from machine learning models to secure communications.
Artificial Intelligence
Activation Functions
In neural networks, functions like Sigmoid, ReLU, and Softmax introduce non-linearity. This allows models to learn from complex, real-world data that isn't separable by a straight line.
Loss Functions
Functions such as Mean Squared Error (MSE) or Cross-Entropy calculate a model's error during training. The value of this "loss" guides the optimization process, helping the model adjust its parameters to make more accurate predictions.
Core Computer Science
Hash Functions
Essential for building efficient data structures like hash tables. They map large data sets to fixed-size outputs, enabling near-instant data retrieval, which is critical for databases and caching.
Cryptography
One-way functions are the foundation of modern cryptography. They are used to create digital signatures, verify data integrity, and securely store sensitive information like passwords.