Relations and Functions

• Relation: A relation from a set A to a set B is a subset of the Cartesian product A × B.

  • Think of a relation as a mapping between two sets.
  • The elements of the relation are ordered pairs.

• Domain and range: The domain of a relation R from A to B is the set of all first components of ordered pairs in R. The range of R is the set of all second components of ordered pairs in R.

  • The domain tells you which set the relation starts with, and the range tells you which set it ends with.
  • The Cartesian product A × B is the set of all ordered pairs (a, b) where a is in A and b is in B.

• Function: A function from A to B is a relation from A to B that assigns to each element of A exactly one element of B.

  • A function is a special type of relation where each input corresponds to a single output.
  • Functions are also called mappings.

• Injective function: A function f from A to B is injective (or one-to-one) if, for all a1, a2 ∈ A, f(a1) = f(a2) implies a1 = a2.

  • An injective function preserves distinct elements.
  • In other words, if the outputs of an injective function are equal, then the inputs must also be equal.

• Surjective function: A function f from A to B is surjective (or onto) if, for every b ∈ B, there exists an a ∈ A such that f(a) = b.

  • A surjective function covers the entire range.
  • In other words, every element in the range is the output of at least one input in the domain.

• Bijective function: A function f from A to B is bijective if it is both injective and surjective.

  • A bijective function is both one-to-one and onto.
  • Bijective functions are also called invertible.

• Inverse function: If f is a bijective function from A to B, then there exists a unique function g from B to A such that f(g(b)) = b and g(f(a)) = a for all a ∈ A and b ∈ B. The function g is called the inverse of f and is denoted by f^-1.

  • The inverse of a function undoes the original function.
  • Inverse functions only exist for bijective functions.

• Composition of functions: If f is a function from A to B and g is a function from B to C, then the composition of f and g, denoted by g o f, is the function from A to C defined by (g o f)(a) = g(f(a)) for all a ∈ A.

• Composition of functions allows you to combine multiple functions to create new functions.
• The order of functions in composition matters.