Relations and Functions

The One Thing

A relation is any subset of a Cartesian product, whereas a function assigns exactly one output in the codomain to every input in the domain. A function has an inverse function precisely when it is bijective between the stated domain and codomain, although restricting the domain may make a non-injective function invertible.

Definitions and Results

• Ordered Pair: An ordered pair $(a,b)$ is a pair in which order matters; generally, $(a,b)\ne (b,a)$.

• Cartesian Product: For sets $A$ and $B$, $A\times B$ is the set of all ordered pairs $(a,b)$, where $a\in A$ and $b\in B$. If $n(A)=m$ and $n(B)=n$, then $n(A\times B)=mn$.

• Relation: A relation from $A$ to $B$ is any subset of $A\times B$. A relation may connect one input to zero, one, or several outputs. The number of possible relations from $A$ to $B$ is $2^{mn}$, because every relation is a subset of $A\times B$.

• Domain of a Relation: The set of first components of the ordered pairs in the relation.

• Range of a Relation: The set of second components of the ordered pairs in the relation.

• Reflexive Relation: A relation $R$ on $A$ is reflexive if $(a,a)\in R$ for every $a\in A$. Thus, every diagonal pair must be present. In a directed graph, every vertex must have a loop.

• Symmetric Relation: A relation $R$ on $A$ is symmetric if $(a,b)\in R$ implies $(b,a)\in R$. In a directed graph, every arrow must be paired with a reverse arrow.

• Transitive Relation: A relation $R$ on $A$ is transitive if $(a,b)\in R$ and $(b,c)\in R$ imply $(a,c)\in R$. In a directed graph, all required indirect connections must be present.

• Equivalence Relation: A relation that is reflexive, symmetric, and transitive. It groups elements into equivalence classes.

• Function: A relation $f$ from $A$ to $B$ in which every element of $A$ has exactly one image in $B$. It is written $f:A\to B$. A function from $A$ to $B$ must contain exactly one ordered pair with first component $a$ for every $a\in A$. The number of functions from a set with $m$ elements to a set with $n$ elements is $n^m$.

• Image: For a function $f$, the image of $a\in A$ is $f(a)$, the unique element of $B$ associated with $a$.

• Codomain: The target set $B$ in $f:A\to B$. The range is always a subset of the codomain.

• One-One or Injective Function: A function in which distinct domain elements have distinct images. Algebraically,

$$f(a)=f(b)⟹a=b.$$

• Many-One Function: A function in which two or more distinct domain elements may have the same image.

• Onto or Surjective Function: A function for which every element of the codomain is the image of at least one element of the domain. Therefore,

$$\text{range}=\text{codomain}.$$

• Into Function: A function whose range is a proper subset of its codomain.

• Bijective Function: A function that is both one-one and onto. Each codomain element corresponds to exactly one domain element.

• Identity Function: The function $I_A:A\to A$ defined by

$$I_A(a)=a$$ for every $a\in A$.

• Constant Function: A function that assigns the same fixed value to every element of its domain.

• Composition of Functions: If $f:A\to B$ and $g:B\to C$, then

$$(g\circ f):A\to C,(g\circ f)(x)=g(f(x)).$$ The function $f$ is applied first, followed by $g$. Generally, $$g\circ f\ne f\circ g.$$

• Associativity of Composition: Whenever the compositions are defined,

$$h\circ (g\circ f)=(h\circ g)\circ f.$$

• Identity under Composition: For $f:A\to B$,

$$f\circ I_A=f,I_B\circ f=f.$$

• Inverse Function: For a bijective function $f:A\to B$, the inverse $f^{-1}:B\to A$ reverses the mapping:

$$f^{-1}(f(a))=a,f(f^{-1}(b))=b.$$ Its domain is the range of $f$, and its range is the domain of $f$.

• Invertible Function: A function is invertible precisely when it is bijective, provided its domain and codomain are fixed. If $f$ is bijective, then

$$f^{-1}\circ f=I_A,f\circ f^{-1}=I_B.$$

• Inverse Relation: The inverse relation is obtained by interchanging every ordered pair $(a,b)$ with $(b,a)$. It is a function exactly when the original function is one-one and onto between the stated sets.

• Horizontal Line Test: A graph represents a one-one function if every horizontal line intersects it at most once.

• Finite-Set Result: For finite sets, a one-one function from $A$ to $B$ is onto when $n(A)=n(B)$, and an onto function is one-one when $n(A)=n(B)$.

Worked Methods

Classifying a Relation

• Identify the set $A$ on which the relation is defined.
• For reflexivity, check that every diagonal pair $(a,a)$ is present.
• For symmetry, check that whenever $(a,b)$ is present, $(b,a)$ is also present.
• For transitivity, check that whenever $(a,b)$ and $(b,c)$ are present, $(a,c)$ is also present.
• Conclude that the relation is an equivalence relation only if all three properties hold: reflexivity, symmetry, and transitivity.
• If the relation is represented by a directed graph, use the corresponding tests: loops at every vertex, reverse arrows for every arrow, and all required indirect connections.

Determining Whether a Relation Is a Function

• List the elements of the domain.
• Check the ordered pairs with each possible first component.
• Every domain element must occur as a first component exactly once.
• If an input has no output, or has more than one output, the relation is not a function.
• A function may be many-one, because different inputs may share the same image; the defining requirement is uniqueness of output for each input.

Testing Injectivity, Surjectivity, and Bijectivity

• To test whether $f$ is one-one, use

$$f(a)=f(b)⟹a=b.$$ Equivalently, check that distinct domain elements have distinct images.

• To test whether $f$ is onto, verify that for every $b$ in the codomain $B$, there exists at least one $a\in A$ such that

$$f(a)=b.$$

• If the range is a proper subset of the codomain, the function is into rather than onto.
• Conclude that $f$ is bijective only if it is both one-one and onto.
• For finite sets with $n(A)=n(B)$, one-one implies onto and onto implies one-one.

Finding a Composite Function

Given $f:A\to B$ and $g:B\to C$:

• Apply $f$ to the input $x$.
• Apply $g$ to the resulting value $f(x)$.
• Write the result as

$$(g\circ f)(x)=g(f(x)).$$

• Check that the codomain of $f$ is compatible with the domain of $g$.
• Do not reverse the order: $g\circ f$ generally differs from $f\circ g$.
• Use associativity when three functions are composed:

$$h\circ (g\circ f)=(h\circ g)\circ f.$$

Finding an Inverse Function

For $y=f(x)$:

• Check whether the function is bijective between the stated domain and codomain. If it is not one-one, its inverse relation will not be a function; if it is not onto, the inverse will not be defined on the entire codomain.
• Interchange $x$ and $y$.
• Solve the resulting equation for $y$.
• Write the result as $y=f^{-1}(x)$.
• Check the domain and range: the domain of $f^{-1}$ is the range of $f$, and the range of $f^{-1}$ is the domain of $f$.
• Verify, where appropriate, that

$$f^{-1}(f(a))=a,f(f^{-1}(b))=b.$$

• If the original function is not one-one on its full domain, restrict the domain so that it becomes one-one before finding an inverse.

Using the Horizontal Line Test

• Consider the graph of the function.
• Draw or visualise horizontal lines across the graph.
• If every horizontal line intersects the graph at most once, the function is one-one.
• If a horizontal line intersects the graph more than once, the function is not one-one and therefore cannot have an inverse function on that domain and codomain.

Where It Goes Wrong

• Treating a relation as a function when one input is paired with several outputs; a function requires exactly one output for every domain element.
• Checking symmetry only in one direction; $(a,b)$ requires $(b,a)$ to be present as well.
• Forgetting that reflexivity requires every diagonal pair $(a,a)$, or every loop in a directed graph, to be present.
• Claiming that a function is onto without checking the entire codomain; onto requires every codomain element to be reached.
• Reversing the order of composition; in $(g\circ f)(x)=g(f(x))$, $f$ is applied first.
• Finding an inverse without checking bijectivity, or without checking the domain restriction, range, and codomain.

What Gets Asked

• Define an ordered pair, Cartesian product, relation, domain, and range.
• Calculate $n(A\times B)=mn$ and the number of possible relations, $2^{mn}$.
• Calculate the number of functions from a set with $m$ elements to a set with $n$ elements, $n^m$.
• Determine whether a relation is reflexive, symmetric, transitive, or an equivalence relation.
• Interpret reflexivity, symmetry, and transitivity from a directed graph.
• Decide whether a relation is a function.
• Classify a function as one-one, many-one, onto, into, or bijective.
• Use $f(a)=f(b)⟹a=b$ to test injectivity.
• Determine whether a finite one-one or onto function is bijective when $n(A)=n(B)$.
• Evaluate and compare composite functions, including the order in $g\circ f$, associativity, and identity functions.
• Find an inverse by interchanging $x$ and $y$, solving for $y$, and checking domain and range.
• Determine whether a function is invertible using bijectivity or the Horizontal Line Test.
• Explain why injectivity and surjectivity are both required for a well-defined inverse.
• Restrict the domain of a function that is not one-one on its full domain so that an inverse can be defined.