Functions

Definition of Functions

Basic Concept

Function: relation associating each element of a set (domain) with exactly one element of another set (codomain). Notation: f: A → B, where f assigns each a ∈ A a unique f(a) ∈ B.

Formal Definition

Formally, f is a function if ∀a ∈ A, ∃! b ∈ B such that (a, b) ∈ f. The uniqueness condition ensures no element in A maps to multiple elements in B.

Graphical Representation

Graph: set of ordered pairs {(a, f(a)) | a ∈ A} in Cartesian product A × B. Visualizes input-output pairing.

"Functions are the fundamental building blocks of mathematics, encoding dependence and transformation." -- Herbert B. Enderton

Domain, Codomain, and Range

Domain

Domain: set of all inputs on which function is defined. Must be specified or inferred from context.

Codomain

Codomain: set containing all possible outputs. Function maps domain elements into codomain elements.

Range (Image)

Range: subset of codomain consisting of actual outputs. Range ⊆ codomain. May be equal or proper subset.

Types of Functions

Total and Partial Functions

Total: defined for every element in domain. Partial: defined for some subset of domain.

Constant Functions

Constant: all inputs map to same output. Example: f(x) = c for fixed c ∈ B.

Identity Function

Identity: f: A → A where f(a) = a for all a ∈ A. Acts as neutral element under composition.

Function Notation and Representation

Standard Notation

f: A → B, f(a) = b. Uses arrow to indicate mapping direction.

Arrow Diagrams

Visual: domain and codomain sets drawn with arrows showing pairings.

Tabular and Set-Builder

Tabular: list pairs (a, f(a)). Set-builder: f = {(a, b) | condition}.

f: ℕ → ℕf(n) = 2n + 1

Injective Functions (One-to-One)

Definition

Injective: distinct inputs map to distinct outputs. ∀a1, a2 ∈ A, f(a1) = f(a2) ⇒ a1 = a2.

Properties

No two domain elements share same image. Allows "reversing" on image subset.

Examples

f(x) = 2x on ℤ is injective. f(x) = x² on ℝ is not injective (since f(-1) = f(1)).

Surjective Functions (Onto)

Definition

Surjective: every element of codomain is image of at least one domain element. ∀b ∈ B, ∃a ∈ A such that f(a) = b.

Properties

Range equals codomain. Function "covers" entire codomain.

Examples

f(x) = x³ on ℝ is surjective. f(x) = x² on ℝ is not surjective onto ℝ.

Bijective Functions

Definition

Bijective: both injective and surjective. One-to-one correspondence between domain and codomain.

Consequences

Invertible: inverse function exists. Domain and codomain have equal cardinality.

Examples

f(x) = x + 1 on ℝ is bijective. Identity function is bijective.

Composition of Functions

Definition

Composition: combining two functions f: A → B and g: B → C to produce g ∘ f: A → C defined by (g ∘ f)(a) = g(f(a)).

Associativity

(h ∘ g) ∘ f = h ∘ (g ∘ f) for functions f, g, h with matching domains/codomains.

Non-commutativity

Generally, g ∘ f ≠ f ∘ g.

Given:f: A → B, f(a) = a + 2g: B → C, g(b) = 3bThen:(g ∘ f)(a) = g(f(a)) = 3(a + 2) = 3a + 6

Inverse Functions

Definition

Inverse f⁻¹ of bijection f: A → B satisfies f⁻¹ ∘ f = id_A and f ∘ f⁻¹ = id_B.

Existence

Only bijections have inverses. Inverse reverses mapping.

Computation

Construct inverse by swapping roles of domain and codomain; solve f(a) = b for a.

Example:f(x) = 2x + 3, f: ℝ → ℝ (bijective)To find f⁻¹(y):y = 2x + 3x = (y - 3)/2Thus,f⁻¹(y) = (y - 3)/2

Functions in Discrete Mathematics

Role in Relations

Functions are special relations with uniqueness property. Basis for equivalence relations, orderings.

Counting Functions

Number of functions from finite set A (|A|=m) to B (|B|=n) is n^m.

Characteristic Functions

Indicator functions χ_A: U → {0,1} represent membership in subsets. χ_A(x) = 1 if x ∈ A, else 0.

Properties and Theorems

Function Equality

Two functions f, g: A → B are equal if ∀a ∈ A, f(a) = g(a).

Cancellation Laws

If f is injective and f ∘ g₁ = f ∘ g₂, then g₁ = g₂. If f is surjective and h₁ ∘ f = h₂ ∘ f, then h₁ = h₂.

Pigeonhole Principle

Injective function from larger to smaller finite set impossible. Implies cardinality constraints.

Applications

Computer Science

Functions model deterministic computations, hash functions, data mappings.

Logic and Set Theory

Functions encode transformations, equivalence classes, cardinality comparisons.

Cryptography

Bijective and invertible functions form basis of encryption/decryption algorithms.

References

• Rosen, K. H. "Discrete Mathematics and Its Applications," McGraw-Hill, 7th ed., 2012, pp. 45-78.
• Epp, S. S. "Discrete Mathematics with Applications," Cengage Learning, 4th ed., 2011, pp. 102-130.
• Enderton, H. B. "A Mathematical Introduction to Logic," Academic Press, 2nd ed., 2001, pp. 50-60.
• Rudin, W. "Principles of Mathematical Analysis," McGraw-Hill, 3rd ed., 1976, pp. 15-25.
• Knuth, D. E. "The Art of Computer Programming, Volume 1: Fundamental Algorithms," Addison-Wesley, 3rd ed., 1997, pp. 85-95.