Skip to main content

Not Just Calculus: First-Year Introduction to Upper-Level Mathematics

David W. Lyons

Section 1.1 Sets and Functions

A set is a collection of objects called the elements or members of the set. Given an object \(x\) and a set \(A\text{,}\) exactly one of two things is true: either \(x\) is an element of \(A\text{,}\) denoted \(x\in A\), or \(x\) is not an element of \(A\text{,}\) denoted \(x\not \in A\). Two sets are equal if they contain exactly the same elements.
To denote a set that contains a small number of elements, we list the elements, separated by commas, and enclosed in curly brackets "\(\{\ldots\}\)". For example, the set \(A=\{x,y,z\}\) contains elements \(x,y,z\text{,}\) and contains no other objects. In this notation, the order in which the objects are listed does not matter. Redundancy also does not matter: the same object may be listed more than once. For example, we may write
\begin{equation*} A=\{x,y,z\}=\{y,z,x\}=\{y,x,y,z\}. \end{equation*}
Another way to denote a set is the notation \(\{x\colon x \text{ satisfies condition } C\}\text{,}\) where the colon ":" is pronounced "such that". For example, the closed unit interval of the real numbers \(\R\) is the set \(\{x\in \R \colon 0\leq x\leq 1\}\text{.}\)
The set that contains no elements is called the empty set, denoted \(\emptyset\).
We say that \(A\) is a subset of \(B\text{,}\) denoted \(A\subseteq B\), if every element in the set \(A\) is also in the set \(B\text{,}\) and we write \(A\not\subseteq B\) to indicate that there is at least one element in \(A\) that is not an element in \(B\text{.}\) A consequence of these definitions is that if \(A=B\text{,}\) then \(A\subseteq B\) and \(B\subseteq A\text{.}\) Conversely, if \(A\subseteq B\) and \(B\subseteq A\text{,}\) then \(A=B\text{.}\) Another consequence is that the empty set is a subset of any given set \(A\) because there is no element in \(\emptyset\) that is not in \(A\text{.}\)

Checkpoint 1.1.1.

  1. Which of these are correct (one, both, or neither)? Discuss.
    \begin{align*} 2\subseteq \{1,2,3\}\amp \amp 2\in \{1,2,3\} \end{align*}
  2. Which of these are correct (one, both, or neither)? Discuss.
    \begin{align*} \emptyset\subseteq \{1,2,3\} \amp \amp \emptyset \in \{1,2,3\} \end{align*}
  3. Are any of the following things the same? Discuss.
    \begin{align*} \{0\}\amp \amp \{\emptyset\} \amp \amp \emptyset \amp \amp \{ \} \end{align*}
  4. Write out all of the subsets of \(\{x,y,z\}\text{.}\)

Instructor’s solution for Checkpoint 1.1.1.

  1. The expression on the right is correct. It says the object \(2\) is an element of the set consisting of objects \(1,2,3\text{.}\) The expression on the left is incorrect. The object \(2\) is not a subset of the set consisting of objects \(1,2,3\text{.}\) Instead it would be correct to say
    \begin{equation*} \{2\}\subseteq \{1,2,3\}. \end{equation*}
  2. The expression on the left is correct. Since every element in the empty set is also an element of \(\{1,2,3\}\) (we say this is "vacuously true"), the empty set is a subset of \(\{1,2,3\}\text{.}\) The expression on the right is not correct. The set \(\{1,2,3\}\) has exactly three members, and the empty set is not one of them.
  3. The last two things on the right are the same. Both symbols \(\emptyset\) and \(\{\}\) denote a set with no members. The two sets on the left are not empty: they each contain one member. But the number 0 and the empty set are not the same thing, so two sets on the left are different.
  4. \begin{equation*} \emptyset,\{x\},\{y\},\{z\},\{x,y\},\{x,z\},\{y,z\},\{x,y,z\} \end{equation*}
The intersection of sets \(A,B\text{,}\) denoted \(A\cap B\), is the set
\begin{equation*} A\cap B =\{x\colon x\in A \text{ and } x\in B\}. \end{equation*}
The union of sets \(A,B\text{,}\) denoted \(A\cup B\), is the set
\begin{equation*} A\cup B =\{x\colon x\in A \text{ or } x\in B\} \end{equation*}
where the word "or" means "one or the other or both". The set
\begin{equation*} A\setminus B =\{x\colon x\in A \text{ and } x\not \in B\} \end{equation*}
(also sometimes denoted \(A-B\)) is called the difference of set \(A\) minus set \(B\), or just "\(A\) minus \(B\)" for short.

Checkpoint 1.1.2.

Let \(A,B\) be sets, and let \(R=A\cap B\text{,}\) \(S=A\cup B\text{,}\) \(T=A\setminus B\text{,}\) and \(U=B\setminus A\text{.}\)
  1. Give an example for which \(R,S,T,U\) are four different sets.
  2. Give an example for which \(R,S,T,U\) are exactly two different sets.
  3. Give an example for which \(R,S,T,U\) are all the same set.

Instructor’s solution for Checkpoint 1.1.2.

(There are many correct answers. These are just a sample.)
  1. Let \(A=\{x,y\}\) and let \(B=\{y,z\}\text{.}\) Then \(R=\{y\}\text{,}\) \(S=\{x,y,z\}\text{,}\) \(T=\{x\}\text{,}\) and \(U=\{z\}\) are all different.
  2. Let \(A=\{x,y\}\) and let \(B=\{x,y\}\text{.}\) Then \(R=S=\{x,y\}\) and \(T=U=\emptyset\) are exactly two different sets.
  3. Let \(A\) and let \(B\) be empty. Then \(R\text{,}\) \(S\text{,}\) \(T\text{,}\) and \(U=\) are all the same set (the empty set).
Given objects \(x,y\text{,}\) an ordered list of the form \((x,y)\) is called an ordered pair. To say that the pair is ordered means that the pairs \((x,y)\) and \((y,x)\) are different if \(x\neq y\text{.}\) The object \(x\) is called the first entry (or the left entry) of the ordered pair \((x,y)\text{,}\) and the object \(y\) is called the second entry (or the right entry). The (Cartesian) product of the set \(A\) with the set \(B\text{,}\) denoted \(A\times B\) is the set
\begin{equation*} A\times B = \{(a,b)\colon a\in A \text{ and } b\in B\} \end{equation*}
of all ordered pairs of the form \((a,b)\text{,}\) where \(a\) is an element of set \(A\) and \(b\) is an element of set \(B\text{.}\)
A subset \(R\subseteq S\times T\) of the product of sets \(S,T\) is called a relation from \(S\) to \(T\). A relation \(f\subseteq S\times T\) is called a function from \(S\) to \(T\) if every element \(s\) in \(S\) is the left entry of exactly one element in \(f\text{.}\) We write \(f\colon S\to T\) to indicate that the relation \(f\subseteq S\times T\) is a function. The set \(S\) is called the domain, the set \(T\) is called the codomain, and the set \(f\subseteq S\times T\) is called the graph of the function \(f\colon S\to T\text{.}\) We write \(f(s)=t\) to indicate that \((s,t)\) is an element of \(f\text{.}\) If \(f(s)=t\text{,}\) we say that \(t\) is the image of \(s\) under \(f\) and that \(s\) is a preimage of \(t\) under \(f\). Informally, we may refer to a function a process that transforms inputs (elements of the domain set) to outputs in the codomain set. When the sets \(S,T\) are understood or implied by context, it is common usage to refer to the function \(f\colon S\to T\) simply as "the function \(f\)".
To express that a relation \(R\subseteq S\times T\) consists of three parts, namely, the set \(S\text{,}\) the set \(T\text{,}\) and the subset \(R\subseteq S\times T\text{,}\) we say that a relation is a triple \((S,T,R)\text{.}\) To say that relations \((S,T,R)\) and \((S',T',R')\) are equal means that \(S=S'\text{,}\) \(T=T'\text{,}\) and \(R=R'\text{.}\) In particular, to say that two functions are equal means that they have the same domain, the same codomain, and the same graph.

Checkpoint 1.1.3.

  1. Write the graphs of all possible functions from \(\{x,y,z\}\) to \(\{A,B\}\text{.}\)
  2. Write the graphs of all possible functions from \(\{A,B\}\) to \(\{x,y,z\}\text{.}\)
  3. Write the graphs of all possible functions from \(\{x,y,z\}\) to \(\{x,y,z\}\text{.}\)
  4. Suppose that the graph of \(f\colon S\to T\) is given by
    \begin{equation*} f=\{(u,1), (v,3), (w,1)\} \end{equation*}
    Is it possible to identify the set \(S\text{?}\) Is it possible to identify the set \(T\text{?}\)
Hint.
Consider using this shortcut for writing a graph: For part 1, write \((f(x),f(y),f(z))\) to represent the graph \(\{(x,f(x)),(y,f(y)),(z,f(x))\}\text{.}\) For example, \((A,A,B)\) represents the function \(\{(x,A),(y,A),(z,B)\}\text{.}\)

Instructor’s solution for Checkpoint 1.1.3.

  1. We will write functions in the following list form.
    \begin{equation*} (f(x),f(y),f(z)) \end{equation*}
    The collection of all 8 possible functions is
    \begin{equation*} (A,A,A),(A,A,B),(A,B,A),(A,B,B),(B,A,A),(B,A,B),(B,B,A),(B,B,B). \end{equation*}
  2. We will write functions in list form \((f(A),f(B))\text{,}\) as for the previous problem. The 9 possible functions are
    \begin{equation*} (x,x),(x,y), (x,z), (y,x), (y,y), (y,z),(z,x),(z,y),(z,z). \end{equation*}
  3. Using list form, as in the previous two problems, there are 27 functions.
  4. It must be that \(S=\{u,v,w\}\text{,}\) because every element in \(S\) must appear as the left entry in exactly one element of \(f\text{.}\) It is not possible to say what \(T\) is, except to say that \(T\) must contain the set \(\{1,3\}\text{.}\)
Given functions \(f\colon S\to T\) and \(g\colon T\to U\text{,}\) the function \(g\of f\colon S\to U\), called the composition of \(g\) with \(f\text{,}\) is defined by \((g\of f)(s) = g(f(s))\) for all \(s\in S\text{.}\) This means that if \((s,t)\) is an element of \(f\) and \((t,u)\) is an element of \(g\text{,}\) then \((s,u)\) is an element of \(g\of f\text{.}\)
Given a set \(S\text{,}\) the function \(f\colon S\to S\) defined by \(f(s)=s\) for every \(s\in S\) is called the identity function on \(S\). The identity function on \(S\) is sometimes denoted \(I_S\) , \(\Id_S\), or \(\One_S\), and the subscript \(S\) may be omitted when the context is clear.
Given a relation \(R\subseteq S\times T\text{,}\) the inverse relation to \(R\), denoted \(R^{-1}\text{,}\) is the relation from \(T\) to \(S\) given by
\begin{equation*} R^{-1}=\{(t,s)\colon (s,t)\in R\}\subseteq T\times S. \end{equation*}
In general, the inverse relation \(f^{-1}\subseteq T\times S\) of a function \(f\colon S\to T\) is not a function. To say that the inverse relation \(f^{-1}\subseteq T\times S\) is a function, it must be true that every \(t\) in \(T\) is the left entry of exactly one element in \(f^{-1}\text{.}\) This is the same as saying that every \(t\) in \(T\) is the right entry of exactly one element in \(f\text{,}\) or, to say in another way, every element in the codomain of \(f\colon S\to T\) has exactly one preimage under \(f\text{.}\) In this case, \(f\colon S\to T\) is said to be invertible with inverse function \(f^{-1}\colon T\to S\text{.}\) Proposition 1.1.4 records an important basic property of the relationship between an invertible function and its inverse function.

Checkpoint 1.1.5.

Fill in the blanks in the following proof of Proposition 1.1.4. Let \(s\in S\text{,}\) and let \(t=f(s)\) so that we have \(\fillinmath{XXX}\in f\text{.}\) By the definition of \(\fillinmath{XXX}\text{,}\) we have that \((t,s)\in \fillinmath{XXX} \text{.}\) By the definition of \(\fillinmath{XXX}\text{,}\) we have \((s,s) \in f^{-1}\of f\text{.}\) This holds for all \(s\in S\text{,}\) so we conclude that \(\fillinmath{XXX}\text{.}\) Similarly, let \(t\in T\text{,}\) and let \(s=f^{-1}(t)\text{,}\) so that we have \(\fillinmath{XXX}\in f^{-1}\text{.}\) It follows that \(\fillinmath{XXX} \in f\text{.}\) By the definition of composition, we have \((t,t)\in \fillinmath{XXX} \text{.}\) This holds for all \(t\in T\text{,}\) so we conclude that \(f\of f^{-1}=\One_T\text{.}\)

Instructor’s solution for Checkpoint 1.1.5.

  1. \(\displaystyle (s,t)\)
  2. inverse relation
  3. \(\displaystyle f^{-1}\)
  4. composition
  5. \(\displaystyle f^{-1}\of f=\One_S\)
  6. \(\displaystyle (t,s)\)
  7. \(\displaystyle (s,t)\)
  8. \(\displaystyle f\circ f^{-1}\)
Image sets and preimage sets. Let \(f\colon S\to T\) be a function, let \(U\subseteq S\) be a subset of the domain \(S\) and let \(V\subseteq T\) be a subset of the codomain \(T\text{.}\) The image of \(U\) under \(f\), denoted \(f(U)\), is defined to be
\begin{equation*} f(U)=\{f(s)\colon s\in U\}. \end{equation*}
The set \(f(S)\) is called the image of the function \(f\).
 1 
The term "range" is used in many texts, sometimes to refer to the image of a function, and sometimes to refer to the codomain. Because the ambiguity, we do not use the term "range" in these notes.
The preimage of \(V\) under \(f\), denoted \(f^{-1}(V)\), is defined to be
\begin{equation*} f^{-1}(V)=\{s\in S\colon f(s)\in V\}. \end{equation*}
Note that we do not assume that \(f^{-1}\) is a function to make this definition. If \(V\) contains only one point, say \(V=\{t_0\}\text{,}\) it is customary to omit the set brackets and write \(f^{-1}(t_0)\) instead of \(f^{-1}(\{t_0\})\text{.}\)

Checkpoint 1.1.6.

This exercise refers to the collections of function in Checkpoint 1.1.3.
  1. Of the collection of functions from \(\{x,y,z\}\) to \(\{A,B\}\text{,}\) which ones are invertible? For each function, give the preimage of \(A\text{.}\)
  2. Of the collection of functions from \(\{A,B\}\) to \(\{x,y,z\}\text{.}\) Which are invertible? For each function, give the preimage of the set \(\{x,y\}\text{.}\)
  3. Of the collection of functions from \(\{x,y,z\}\) to \(\{x,y,z\}\text{.}\) Which are invertible?

Instructor’s solution for Checkpoint 1.1.6.

  1. None of the 8 functions
    \begin{equation*} (A,A,A),(A,A,B),(A,B,A),(A,B,B),(B,A,A),(B,A,B),(B,B,A),(B,B,B) \end{equation*}
    is invertible. The preimages of \(A\) for the 8 functions are, in order:
    \begin{equation*} \{x,y,z\},\{x,y\},\{x,z\},\{x\},\{y,z\},\{y\},\{z\},\emptyset. \end{equation*}
  2. None of the 9 functions
    \begin{equation*} (x,x),(x,y), (x,z), (y,x), (y,y), (y,z),(z,x),(z,y),(z,z) \end{equation*}
    The preimages of the set \(\{x,y\}\) for the 9 functions are, in order:
    \begin{equation*} \{A,B\},\{A,B\},\{A\},\{A,B\},\{A,B\},\{A\},\{B\},\{B\},\emptyset. \end{equation*}
  3. Of the 27 functions, 6 are invertible. Here are those 6.
    \begin{equation*} (x,y,z),(x,z,y), (y,x,z), (y,z,x), (z,x,y), (z,y,x) \end{equation*}

Exercises Exercises

1.

A hypergraph is a pair of sets \((V,E)\text{,}\) where \(V\) is a set and \(E\) is a set of nonempty subsets of \(V\text{.}\) Write out all of the hypergraphs \((V,E)\) for \(V=\{a,b\}\text{.}\)

Instructor’s solution for Exercise 1.1.1.

Here are the 8 hypergraphs of the form \((\{a,b\},E)\text{.}\)
\begin{align*} E\amp = \emptyset\\ E\amp = \{\{a\}\}\\ E\amp = \{\{b\}\}\\ E\amp = \{\{a,b\}\}\\ E\amp = \{\{a\},\{b\}\}\\ E\amp = \{\{a\},\{a,b\}\}\\ E\amp = \{\{b\},\{a,b\}\}\\ E\amp = \{\{a\},\{b\},\{a,b\}\} \end{align*}

2.

Let \(f\colon S\to T\) be a function that is not invertible. One of the following statements is always true, and the other statement is sometimes true, and sometimes false. Determine which is which. Demonstrate the "sometimes true" statement by giving two specific examples — one example for which the statement is true, and one example for which the statement is false. "Specific" means that you will write all of the sets \(S,T,A,B\) or \(S,T,V,W\) as lists of elements inside curly brackets, and write your functions as lists of ordered pairs in curly brackets.
  1. For any subsets \(A,B\) of \(S\text{,}\) we have \(f(A \cap B) = f(A) \cap f(B)\text{.}\)
  2. For any subsets \(V,W\) of \(T\text{,}\) we have \(f^{-1}(V\cap W) = f^{-1}(V)\cap f^{-1}(W)\text{.}\)

Instructor’s solution for Exercise 1.1.2.

Statement a is sometimes true and sometimes false. To see that statement a is sometimes true, consider the example \(S=T=A=B=\{\ast\}\text{,}\) with \(f\) given by \(f=\{(\ast,\ast)\}\text{.}\) It is clear that \(f(A\cap B)=f(A)\cap f(B) = \{\ast\}\text{.}\) To see that statement a is sometimes false, consider the example \(S=\{a,b\}\text{,}\) \(T=\{\ast\}\text{,}\) \(A=\{a\}\text{,}\) \(B=\{b\}\text{,}\) and \(f=\{(a,\ast),(b,\ast)\}\text{.}\) Then we have \(f(A\cap B)=f(\emptyset)=\emptyset\text{,}\) but \(f(A)\cap f(B) = \{\ast\}\neq \emptyset\text{.}\)
A direct proof that statement b is always true is not required; proof technique for equality of sets is not expected at this point. Nonetheless, here is a sample proof, in case there is interest, that attempts to rely only on the intuitive notion of "equivalent statements".
To say that \(x\) is an element in the set \(f^{-1}(V\cap W)\) means that \(f(x)\) is in the set \(V\cap W\text{.}\) This is the same as saying that \(f(x)\in V\) and \(f(x)\in W\text{.}\) This, in turn, is the same as saying that \(x\in f^{-1}(V)\) and \(x\in f^{-1}(W)\text{,}\) which is the same as saying \(x\in f^{-1}(V)\cap f^{-1}(W)\text{.}\) This chain of equivalent statements shows that
\begin{equation*} f^{-1}(V\cap W)=f^{-1}(V)\cap f^{-1}(W), \end{equation*}
as desired.
PrevTopNext