Relations and Functions

The One Thing

A relation is any subset of a Cartesian product, whereas a function is a relation in which every input has exactly one output. Functions may be classified by their mapping behaviour, combined by composition, and inverted precisely when they are bijective.

Definitions and Results

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

• Cartesian Product: For sets $A$ and $B$,

$$A\times B=\{(a,b):a\in A,b\in B\}.$$ If $n(A)=m$ and $n(B)=n$, then $$n(A\times B)=mn,$$ and the number of possible relations from $A$ to $B$ is $$2^{mn}.$$

• Relation: A relation from $A$ to $B$ is any subset of $A\times B$. The first components form its domain, and the second components form its range.

• Domain: The domain is the set of all first components of the ordered pairs in a relation, or the set of permitted input values of a function.

• Codomain: The codomain is the set into which a function maps its inputs. It may contain elements that are not actual outputs.

• Range: The range is the set of actual output values of a function. It is always a subset of the codomain.

• Function: A function $f$ from $A$ to $B$ is a relation in which every element of $A$ has exactly one image in $B$. Equivalently, every element of $A$ occurs as the first component exactly once in the relation.

• Reflexive Relation: A relation $R$ on $A$ is reflexive if

$$(a,a)\in R$$ for every $a\in A$. Thus, all pairs $(a,a)$ must be present.

• Symmetric Relation: A relation $R$ on $A$ is symmetric if

$$(a,b)\in R⟹(b,a)\in R.$$

• Transitive Relation: A relation $R$ on $A$ is transitive if

$$(a,b)\in R\text{ and }(b,c)\in R⟹(a,c)\in R.$$

• Equivalence Relation: An equivalence relation is reflexive, symmetric, and transitive. It divides a set into disjoint equivalence classes.

• One-One Function: A function is one-one if distinct elements of the domain have distinct images:

$$f(a)=f(b)⟹a=b.$$ Equivalently, $$f(x_1)=f(x_2)⟹x_1=x_2.$$

• Many-One Function: A function is many-one if two or more distinct elements of the domain may have the same image.

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

• Onto Function: A function is onto if its range equals its codomain. Equivalently, for every $y$ in the codomain, there exists at least one $x$ in the domain such that

$$f(x)=y.$$

• Bijective Function: A function is bijective if it is both one-one and onto.

• Composition of Functions: If

$$f:A\to B,g:B\to C,$$ then $g$ composed with $f$ maps $A$ to $C$ and is defined by $$(g\circ f)(x)=g(f(x)).$$ Its domain consists of those $x$ in the domain of $f$ for which $f(x)$ lies in the domain of $g$. In general, $$g\circ f\ne f\circ g.$$ Composition is associative: $$h\circ (g\circ f)=(h\circ g)\circ f.$$

• Inverse Function: A function $f:A\to B$ has an inverse function if and only if it is bijective. For a bijective $f$, the inverse $f^{-1}:B\to A$ satisfies

$$f^{-1}(f(x))=x$$ and $$f(f^{-1}(y))=y.$$ When the inverses exist, $$(g\circ f{)}^{-1}=f^{-1}\circ g^{-1}.$$

• Identity Function: The identity function

$$I_A:A\to A$$ is defined by $$I_A(x)=x$$ for every $x\in A$. Identity relations and identity functions leave every element unchanged.

Worked Methods

1. Determining a Cartesian Product and the Number of Relations

• Identify the cardinalities of the sets:

$$n(A)=m,n(B)=n.$$

• Calculate the number of ordered pairs:

$$n(A\times B)=mn.$$

• Since every subset of $A\times B$ is a relation from $A$ to $B$, calculate the number of possible relations:

$$2^{mn}.$$

2. Checking Whether a Relation Is a Function

• List the elements of the proposed relation as ordered pairs.
• Check that every element of the domain $A$ occurs as a first component.
• Check that every element of $A$ occurs as the first component exactly once.
• If an input is missing, or if one input is paired with more than one output, the relation is not a function.

A relation from $A$ to $B$ is therefore a function precisely when every element of $A$ has exactly one image in $B$.

3. Testing Relation Properties

For a relation $R$ on $A$:

• Reflexivity: Check that $(a,a)\in R$ for every $a\in A$.
• Symmetry: For every $(a,b)\in R$, check that $(b,a)\in R$.
• Transitivity: Whenever $(a,b)\in R$ and $(b,c)\in R$, check that $(a,c)\in R$.
• Equivalence: Conclude that $R$ is an equivalence relation only if all three properties—reflexivity, symmetry, and transitivity—hold.
• If $R$ is an equivalence relation, identify its disjoint equivalence classes.

4. Classifying a Function by Its Mapping Behaviour

• Check whether distinct domain elements can have the same image.

- If not, the function is one-one. - If two or more distinct domain elements have the same image, it is many-one.

• Compare the range with the codomain.

- If the range is a proper subset of the codomain, the function is into. - If the range equals the codomain, the function is onto.

• If the function is both one-one and onto, classify it as bijective.

The distinction between range and codomain is essential: the range consists of actual outputs, whereas the codomain is the specified target set.

5. Evaluating a Composition of Functions

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

• Apply the inner function $f$ to $x$.
• Apply the outer function $g$ to the result:

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

• Ensure that $f(x)$ lies in the domain of $g$.
• Do not interchange the order without checking, since generally

$$g\circ f\ne f\circ g.$$

• For three functions, use associativity:

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

6. Finding or Verifying an Inverse Function

• Determine whether the original function is one-one.
• Determine whether it is onto.
• Conclude that an inverse function exists exactly when both conditions hold, that is, when the function is bijective.
• Verify the inverse using

$$f^{-1}(f(x))=x$$ and $$f(f^{-1}(y))=y.$$

• For a composition, reverse the order:

$$(g\circ f{)}^{-1}=f^{-1}\circ g^{-1},$$ provided the inverses exist.

Where It Goes Wrong

• Treating a general relation as a function without checking that every element of the domain has exactly one image.
• Confusing the range with the codomain; the range contains actual outputs, while the codomain may contain elements that are never reached.
• Checking only some diagonal pairs when testing reflexivity; every pair $(a,a)$ for $a\in A$ must be present.
• Forgetting one of the three requirements for an equivalence relation: reflexivity, symmetry, and transitivity.
• Reversing the order in composition; $g\circ f$ means apply $f$ first and then $g$, and in general $g\circ f\ne f\circ g$.
• Assuming that every function has an inverse; an inverse function exists if and only if the function is bijective.

What Gets Asked

• Find $A\times B$, calculate $n(A\times B)=mn$, or determine the number of possible relations $2^{mn}$.
• Decide whether a set of ordered pairs is a relation or a function from $A$ to $B$.
• Identify the domain, codomain, and range of a relation or function.
• Test whether a relation is reflexive, symmetric, transitive, or an equivalence relation.
• Determine the equivalence classes produced by an equivalence relation.
• Classify a function as one-one, many-one, into, onto, or bijective.
• Use the condition $f(x_1)=f(x_2)⟹x_1=x_2$ to test whether a function is one-one.
• Use the condition that every codomain element has at least one preimage to test whether a function is onto.
• Evaluate $g\circ f$, determine its domain, and compare it with $f\circ g$.
• Apply the associativity of composition.
• Determine whether an inverse function exists and verify it using the two inverse identities.
• Find the inverse of a composition using

$$(g\circ f{)}^{-1}=f^{-1}\circ g^{-1}.$$

• Identify or use the identity relation and the identity function $I_A(x)=x$.