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

## Section1.1Sets 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{.}$$

### Checkpoint1.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{.}$$
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.

### Checkpoint1.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.
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.

### Checkpoint1.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{.}$$
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.

### Checkpoint1.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{.}$$
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{.}$$

### Checkpoint1.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?

### ExercisesExercises

#### 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{.}$$

#### 2.

Let $$f\colon S\to T$$ be a function, and let $$V,W$$ be subsets of $$T\text{.}$$ Show that $$f^{-1}(V\cap W)=f^{-1}(V)\cap f^{-1}(W)\text{.}$$ Do not assume that $$f$$ is invertible!
Hint.
To show that two sets $$A,B$$ are equal, the standard method is to show that if $$x$$ is an element of $$A\text{,}$$ then $$x$$ is also an element of $$B\text{,}$$ and vice-versa. If you can do this, it then follows that $$A=B\text{.}$$ Try starting this proof with: "Let $$x$$ be an element of $$f^{-1}(V\cap W)$$". What can you do next? In this case, just follow the definitions. The next line is: "This means $$f(x)$$ is an element of $$V\cap W$$". Now keep going!