- 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*}
- 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*}
- Are any of the following things the same? Discuss.\begin{align*} \{0\}\amp \amp \{\emptyset\} \amp \amp \emptyset \amp \amp \{ \} \end{align*}
- Write out all of the subsets of \(\{x,y,z\}\text{.}\)
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.
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{.}\)
- Give an example for which \(R,S,T,U\) are four different sets.
- Give an example for which \(R,S,T,U\) are exactly two different sets.
- 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.
Checkpoint 1.1.3.
- Write the graphs of all possible functions from \(\{x,y,z\}\) to \(\{A,B\}\text{.}\)
- Write the graphs of all possible functions from \(\{A,B\}\) to \(\{x,y,z\}\text{.}\)
- Write the graphs of all possible functions from \(\{x,y,z\}\) to \(\{x,y,z\}\text{.}\)
- 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.
Proposition 1.1.4.
Let \(f\colon
S\to T\) be a function, and suppose that the inverse relation \(f^{-1}\subseteq T\times S\) is a function \(f^{-1}\colon T\to S\text{.}\) Then we have \(f^{-1}\of f=\One_S\) and \(f\of f^{-1}=\One_T\text{.}\)
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{.}\)
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\). The preimage of \(V\) under \(f\), denoted \(f^{-1}(V)\), is defined to be
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.
\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.
- 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{.}\)
- 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{.}\)
- Of the collection of functions from \(\{x,y,z\}\) to \(\{x,y,z\}\text{.}\) Which are invertible?
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{.}\)
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!
