Skip to main content

Discrete Mathematical Structures

Subsection 2.3.2 Graphs of functions

We can represent a function \(f:A\to B\) as a subset of \(A\times B\text{.}\)

Definition 2.3.2.1.

Let \(f:A\to B\) be a function. The graph of \(f\) is
\begin{equation*} \set{(a,f(a))\given a \in A}\subset A\times B. \end{equation*}

Example 2.3.2.2. Function given by its graph.

Let \(g:A\to B\) where \(A=\set{1,2,3,4}\) and \(B=\set{1,2,3}\) be given by its graph
\begin{equation*} \set{(1,1),(2,3),(3,1),(4,2)}\subset \set{1,2,3,4}\times \set{1,2,3}\text{.} \end{equation*}
Then \(g(1)=1\text{,}\) \(g(2)=3\text{,}\) \(g(3)=1\text{,}\) and \(g(4)=2\text{.}\)
Two sets A and B are represented each by an oval.  The ovals do not overlap. Inside A are the numbers 1, 2, 3, and 4. Inside B are the numbers 1, 2, and 3. An arrow labeled g goes from 1 in A to to 1 in B. An arrow labeled g goes from 2 in A to to 3 in B. An arrow labeled g goes from 3 in A to to 1 in B. An arrow labeled g goes from 4 in A to to 2 in B.
Figure 2.3.2.3. Graphical representation of the function \(g:A\to B\) where \(A=\set{1,2,3,4}\) and \(B=\set{1,2,3}\) with graph \(\set{(1,1),(2,3),(3,1),(4,2)}\) from Example 2.3.2.2.
Note that in both Figure 2.3.1.11 and Figure 2.3.2.3 each element of \(A\) is assigned to a unique element of \(B\text{.}\) An element of \(B\) may be the image of \(1\text{,}\) none, or several elements of \(A\text{.}\)
We plot a function \(f:A\to B\) by representing the elements of its graph \(G\subset A\times B\) by black pixels and the elements of \((A\times B)-G\) by white pixels on the \(A\times B\) plane. In Example 2.3.2.4 observe how changing the plot of the graph of a function changes its graph.

Example 2.3.2.4. Interactive plot of a function and its graph.

Functions need to assign exactly one element of the codomain to each element in the domain. Relations are generalizations of functions that do not have this restriction. Just like the graph of a functions relations can be represented as a subset of a Cartesian product.
We cover relations in more detail in Chapter 6.

Definition 2.3.2.5.

Let \(A\) and \(B\) be sets. A subset \(R\) of a \(A \times B\) is called a relation from \(A\) to \(B\text{.}\)
In Figure 2.3.2.6 and Figure 2.3.2.7 we give examples of relations that are not functions.
Two sets A and B are represented each by an oval.  The ovals do not overlap. Inside A are the numbers 1, 2, and 3. Inside B are the numbers 1, 2, 3 and 4. An arrow goes from 1 in A to to 1 in B. An arrow goes from 1 in A to to 4 in B. An arrow goes from 3 in A to to 3 in B. An arrow goes from 3 in A to to 1 in B.
Figure 2.3.2.6. The graphical representations of the relation \(\set{(1,1),(1,4),(2,3),(3,1)}\subseteq A\times B\) where \(A=\set{1,2,3}\) and \(B=\set{1,2,3,4}\text{.}\) This relation is not a function, because the element \(1\in A\) is assigned to \(1\in B\) and \(4\in B\text{.}\)
Two sets A and B are represented each by an oval.  The ovals do not overlap. Inside A are the numbers 1, 2, 3, and 4. Inside B are the numbers 1, 2, and 3. An arrow goes from 1 in A to to 1 in B. An arrow goes from 2 in A to to 3 in B. An arrow goes from 3 in A to to 2 in B.
Figure 2.3.2.7. The graphical representations of the relation \(\set{(1,1),(2,3),(3,2)}\subseteq A\times B\) where \(A=\set{1,2,3,4}\) and \(B=\set{1,2,3}\text{.}\) This relation is not a function, because the element \(4\in A\) is not assigned to any element in \(B\) and functions need to assign exactly one element of the codomain to each element in the domain.

Remark 2.3.2.8.

A function is a special kind of relation from \(A\) to \(B\text{.}\) Specifically, each element \(a\) in \(A\) is related to the element \(f(a)\) in \(B\text{.}\) We discuss relations in detail in Section 6.1.