%!TEX root = proofs+concepts.tex


\chapter{Sets}
\label{SetsChap}

\begin{quote}
\it In mathematics these days, essentially everything is a set. Some knowledge of set theory is a necessary part of the background everyone needs for further study of mathematics.
\par\raggedleft \small\rm\sf
Herbert B.\ Enderton (1936--2010), American mathematician
\\ \emph{Elements of Set Theory}
\end{quote}


\section{{\SL} is not enough}
Consider the following deduction:
\begin{quote}
\label{willard1}
Merlin is a wizard. 
All wizards wear funny hats.\\
Therefore, Merlin wears a funny hat.
\end{quote}
To symbolize it in {\SL}, we define a symbolization key:
\begin{ekey}
\item[W] Merlin is a wizard.
\item[A] All wizards are wearing funny hats.
\item[H] Merlin is wearing a funny hat.
\end{ekey}

Now we symbolize the deduction:
\begin{earg}
\item[]$W$
\item[]$A$
\conclusion $H$
\end{earg}

This is \emph{not} valid in {\SL}. (If $W$ and~$A$ are true, but $H$~is false, then it is obvious that both hypotheses are true, but the conclusion is false.) There is something very wrong here, because the deduction that was written in English is clearly valid. 

 The problem is that symbolizing this deduction in {\SL} leaves out some of the important structure: The assertion ``All wizards are wearing funny hats'' is about both wizards and hat-wearing, but {\SL} is not able to capture this information: it loses the connection between Merlin's being a wizard and Merlin's wearing a hat.
 However, the problem is not that we have made a mistake while symbolizing the deduction; it is the best symbolization we can give for this deduction \emph{in {\SL}}.
 
 In order to symbolize this deduction properly, we need to use a more powerful logical language. This language is called \define{\QL}, and its assertions are built from ``predicates'' and ``quantifiers\rlap.''

A predicate is an expression like ``\blank~is wearing a funny hat\rlap.'' This is not an assertion on its own, because it is neither true nor false until we fill in the blank, to specify who it is that we claim is wearing a funny hat.

The details of this will be explained in \cref{sec.predicates}, but here is the basic idea: In {\QL}, we will represent predicates with capital letters. For instance, we could let $H$ stand for ``\blank\ is wearing a funny hat\rlap.'' However, we will use variables instead of blanks; so ``$x$~is wearing a funny hat'' is a predicate, and we could represent it as $H(x)$.

%Lower-case letters will be used as the names of specific things. For instance, we might let $m$ stand for Merlin. Then the expression $H(w)$ is a translation of the assertion ``Merlin is wearing a funny hat'' into the notation of {\QL}.

The words ``all'' and ``some'' are \emph{quantifiers}, and we will have symbols that represent them. For instance, ``$\exists$'' will mean ``There exists some\blank, such that\rlap.'' Thus, to say that someone is wearing a funny hat, we can write $\exists x ,H(x)$; that is: There exists some~$x$, such that $x$~is wearing a funny hat.  Quantifiers will be dealt with in \cref{ch.firstorder}, when {\QL} is fully explained.

With predicates and quantifiers, we will be talking about many people (or other things) all at once, instead of one at a time. For example, we may wish to talk about ``the people who are wearing hats\rlap,'' or ``the mammals that lay eggs\rlap.'' These are examples of \emph{sets}.





\section{Sets, subsets, and predicates} \label{SetSect}


\subsection{Sets and their elements}
In mathematics, a \define{set} is a collection of objects. The objects in the collection are called ``\define[element]{elements}'' (or ``\define[members of a set]{members}'') of the set. If someone has a particular set in mind, they may wish to tell other people which set it is. One good way to do this is to list its elements. The list needs to be surrounded with curly braces~(``$\{\ \ \}$'')%
\nindex{$\{\ \ \}$}
to indicate that it represents a set, rather than some other type of object.

\begin{otherterm}
In mathematics, the term \define{collection} is a synonym for ``set\rlap.''
\end{otherterm}

\begin{eg} \ 
\noprelistbreak
\begin{enumerate}
\item $\{1, 2, 3, 4, 5\}$ is the set of natural numbers from $1$ to~$5$.
\item $\{1,2,3,\ldots,100\}$ is the set of natural numbers from $1$ to~$100$.
\item $\{\clubsuit, \diamondsuit, \heartsuit, \spadesuit \}$ is the set of suits in a standard deck of cards.
\item The set of provinces in Canada is
$$\left\{ \begin{matrix} 
\text{British Columbia, Alberta, Saskatchewan, Manitoba,} \\
\text{Ontario, Quebec, Newfoundland and Labrador,} \\
\text{New Brunswick, Prince Edward Island, Nova Scotia} 
\end{matrix} \right\} .$$
\end{enumerate}
\end{eg}

\begin{rem}
 In everyday life, when you have a bunch of things that you want to keep together, you might look for a box to put them in. (The box itself probably has no value --- you are interested only in the stuff that is in the box.) In mathematics, you should put the things into a set, not a box. If you think of a set as being a box of stuff, then the elements of the set are the things you see when you open the box.
 \end{rem}

\begin{eg} \ 
\begin{enumerate}
\item If $A = \{1,2,3\}$, then the elements of~$A$ are the numbers $1$, $2$, and~$3$.
\item If $B = \bigl\{ 1, \{2,3\} \bigr\}$, then the elements of~$B$ are the number~$1$ and the set $\{2,3\}$. It is important to note that the numbers $2$ and~$3$ are \emph{not} elements of~$B$. 
 \begin{enumerate}
\item To understand this, it may help to consider the analogy with boxes: if we open the box~$B$, we will see the number~$1$ and a box, but we will not see the number~$2$ or the number~$3$. 

\smallskip
\hfil 
\hbox{\boxit{
%\vskip\smallskipamount
\qquad \begin{minipage}{2.6in}
\medskip
Contents of Box~$B$ (2 items):
\begin{itemize}
\item the number~``$1$''
\item a box of assorted numbers
\end{itemize}
\medskip
\end{minipage}
}}
%MAYBE WOULD BE GOOD TO HAVE A PICTURE HERE, TOO !!!

\smallskip\noindent
We would need to open up the box that is inside of~$B$ in order to see those extra numbers. So $2$ and $3$ are not elements of the set~$B$ --- they are elements of a set that is an element of~$B$.

\item As another illustration of this same phenomenon, suppose we make a list of the teams in a chess tournament. The list might be:
\smallskip
	\begin{multicols}{3}
	\begin{enumerate}
	\item U of Lethbridge,
	\item U of Alberta,
	\item U of Calgary.
	\end{enumerate}
	\end{multicols}
And maybe the members of the Lethbridge team are Alice, Bob, and Cindy. Then Alice is \emph{not} on the list of teams; she is a \emph{member} of one of the teams on the list.
\end{enumerate}
\end{enumerate}
\end{eg}

\begin{notation}
 We use 
 \begin{itemize}
 \item ``$\in$''%
 \nindex{$\in$}
 as an abbreviation for ``is an element of\rlap,''
 and
 \item ``$\notin$''%
 \nindex{$\notin$}
 as an abbreviation for ``is \emph{not} an element of\rlap.''
 \end{itemize}
 For example, if $A = \{1,2,3,4,5\}$, then we have $3 \in A$ and $7 \notin A$, because $3$ is an element of~$A$, but $7$~is not an element of~$A$.
 \end{notation}

\begin{defn}
The set with no elements can be denoted $\{\ \}$. (It is like an empty box.) It is called the \define{empty set}, and it comes up so often that is named by a special symbol: 
	\factoidbox{$\emptyset$%
	\nindex{$\emptyset$}
	denotes the empty set.}
\end{defn}

\begin{rem}
 Because the empty set has no elements,
 \factoidbox{for all~$x$, we have $x \notin \emptyset$.}
\end{rem}
 
 \begin{exer} \label{MemberEx}
 Fill in each blank with $\in$ or $\notin$.
\begin{tasks}(3)
\task\fixtask \label{MemberEx-tintime}%
$\var{t} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-iintime}%
$\var{i} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-mintime}%
$\var{m} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-Tintime}%
$\{\var{t}\} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-Iintime}%
$\{\var{i}\} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-Mintime}%
$\{\var{m}\} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-TIintime}%
$\{\var{t},\var{i}\} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-MEintime}%
$\{\var{m},\var{e}\} \blank \bigl\{ \var{t}, \var{i}, \var{m}, \var{e} \bigr\} $
\task\fixtask \label{MemberEx-tintI(ME)}%
$\var{t} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-iintI(ME)}%
$\var{i} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-mintI(ME)}%
$\var{m} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-TintI(ME)}%
$\{\var{t}\} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-IintI(ME)}%
$\{\var{i}\} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-MintI(ME)}%
$\{\var{m}\} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-TIintI(ME)}%
$\{\var{t}, \var{i}\} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-MEintI(ME)}%
$\{\var{m}, \var{e}\} \blank \bigl\{ \var{t}, \{\var{i}\}, \{\var{m}, \var{e} \} \bigr\} $
\task\fixtask \label{MemberEx-0in0}%
$\emptyset \blank \emptyset$
\task\fixtask \label{MemberEx-0in(0)}%
$\emptyset \blank \{\emptyset\}$
\task\fixtask \label{MemberEx-(0)in0}%
$\{\emptyset\} \blank \emptyset$
\task\fixtask \label{MemberEx-(0)in(0)}%
$\{\emptyset\} \blank \{\emptyset\}$
\task\fixtask \label{MemberEx-(0)in((0))}%
$\{\emptyset\} \blank \bigl\{ \{\emptyset\} \bigr\}$
\end{tasks}
  \end{exer}

We said that a set is a collection of objects, but this needs a bit of elaboration:
\begin{enumerate}
\item \emph{A set is \textbf{determined by its elements}.} This means that there cannot be two different sets that have exactly the same elements. (Or, in other words, if two sets have the same elements, then the two sets are equal.) For example, suppose: 
\begin{enumerate}
\item $H$ is the set of students who had a perfect score on last week's history quiz,
\item $M$ is the set of students who had a perfect score on last week's math quiz.
 \item  \var{Alice} and \var{Bob} are the only two students who had a perfect score on last week's history quiz,
 and
 \item \var{Alice} and \var{Bob} are also the only two students who had a perfect score on last week's math quiz.
 \end{enumerate}
 Then $H$ and~$M$ have exactly the same elements, so $H$ and~$M$ are just different names for the same set: namely, both represent $\{\var{Alice}, \var{Bob}\}$. So the sets are equal: we have $H = M$.
 \factoidbox{Suppose $A$ and $B$ are two sets. \\
 We have $A = B$ if and only if \\ for every $x, \bigl( (x \in A) \Leftrightarrow (x \in B) \bigr)$. }
\item \emph{A set is an \textbf{unordered} collection.} This means that listing the elements of a set in a different order does not give a different set. For example, $\{1,2,3\}$ and $\{1,3,2\}$ are the same set. We write $\{1,2,3\}=\{1,3,2\}$.  Both of them are the set whose elements are $1$, $2$, and~$3$.
\item \emph{A set is a collection \textbf{without repetition}.} This means that repeating something in the list of elements does not change the set. For example, $\{1,2,2,3,3\}$ is the same set as $\{1,2,3\}$.  We write $\{1,2,2,3,3\}=\{1,2,3\}$.
\end{enumerate}

\begin{exers} \label{EqualSetEx}
Fill in the blank with $=$ or~$\neq$.
\begin{tasks}(3)
\task\fixtask \label{EqualSetEx-time_tmie}
$\{\var{t}, \var{i}, \var{m}, \var{e} \} \blank \{\var{t}, \var{m}, \var{i}, \var{e} \}$
\task\fixtask \label{EqualSetEx-tim_tmie}
$\{\var{t}, \var{i}, \var{m} \} \blank \{\var{t}, \var{m}, \var{i}, \var{e} \}$
\task\fixtask \label{EqualSetEx-tim_tmim}
$\{\var{t}, \var{i}, \var{m} \} \blank \{\var{t}, \var{m}, \var{i}, \var{m} \}$
\task\fixtask \label{EqualSetEx-tim_tmi}
$\{\var{t}, \var{i}, \var{m} \} \blank \{\var{t}, \var{m}, \var{i} \}$
\task\fixtask \label{EqualSetEx-tim_timi}
$\{\var{t}, \var{i}, \var{m} \} \blank \{\var{t}, \var{i}, \var{m}, \var{i} \}$
\task\fixtask \label{EqualSetEx-tim_tttiim}
$\{\var{t}, \var{i}, \var{m} \} \blank \{\var{t}, \var{t}, \var{t}, \var{i}, \var{i}, \var{m} \}$
\task\fixtask \label{EqualSetEx-ti_t}
$\{\var{t}, \var{t}\} \blank \{\var{t}\}$
\task\fixtask \label{EqualSetEx-ti_ii}
$\{\var{t}, \var{t}\} \blank \{\var{i},\var{i}\}$
\task\fixtask \label{EqualSetEx-tt_ti}
$\{\var{t}, \var{t}\} \blank \{\var{t},\var{i}\}$
%\item $\{x\} \blank \{x,x\}$
%\item $\{x,y\} \blank \{y,x\}$
\end{tasks}
\end{exers}


\begin{exers} \label{NotinPfEx}
Provide a 2-column proof of each deduction.
\begin{problist}
\item  \label{NotinPfEx-notinA}
$(a \in A) \eif (a \notin B)$, \  $(b \in B) \eif (a \in B)$, \  \therefore\ $(b \in B) \eif (a \notin A)$
\item  \label{NotinPfEx-Yempty}
$(p \in X) \eand (q \in X)$, \ $(p \in X) \eif \bigl( (q \notin X) \eor (Y = \emptyset) \bigr)$, \ \therefore $Y = \emptyset$.
\end{problist}
\end{exers}

\begin{exers}  \label{EngNotinPfEx}
Write your proofs in English.
%Provide a proof of each deduction. (Write your proof in English.)
\columnsep=-30pt % !!!
\begin{multicols}{2}
\begin{problist} 
\makeatletter\renewcommand{\p@enumii}{}\makeatother % want hypotheses to have single-letter labels !!!
\item  \label{EngNotinPfEx-H}
Assume:
	\begin{enumerate}
	\item \label{EngNotinPfEx-H-rinH}
	If $p \in H$ and $q \in H$, then $r \in H$.
	\item \label{EngNotinPfEx-H-qinH}
	$q \in H$.
	\end{enumerate}
Show that if $p \in H$, then $r \in H$.
\columnbreak % !!!
\item  \label{EngNotinPfEx-Y}
Assume:
	\begin{enumerate}
	\item \label{EngNotinPfEx-Y-ainY}
	If $X \neq \emptyset$, then $a \in Y$.
	\item \label{EngNotinPfEx-Y-binY}
	If $X = \emptyset$, then $b \in Y$.
	\item \label{EngNotinPfEx-Y-Ynot0}
	If either $a \in Y$ or $b \in Y$, then $Y \neq \emptyset$.
	\end{enumerate}
Show $Y \neq \emptyset$.
\end{problist}
\end{multicols}
\end{exers}

\begin{notation} 
It is traditional to use:
                \begin{itemize}
                \item capital letters (such as $A,B,C, X,Y,Z$) to represent sets, 
                and 
                \item lower-case letters (such as $a,b,c,x,y,z$) to represent numbers and other objects that are individual elements (or ``atoms''), rather than sets.
                \end{itemize}
                Furthermore, it is a good idea to maintain a correspondence between the upper-case letters and lower-case letters: when feasible, use $a$ to represent an element of~$A$ and $b$~to represent an element of~$B$, for example.
                %\item In proofs, it will sometimes be useful to know that 
                %$$\{1,2,3,\ldots,n\} = \{\, i \in \natural \mid 1 \le i \le n\,\} .$$
                %You may assume this fact without proving it.
\end{notation}

\begin{notation} 
A few particularly important sets of numbers have been given names that every mathematician needs to know:
\begin{itemize}
\item   $\natural = \{0, 1, 2, ... \}$%
\nindex{$\natural$}
is the set of \emph{natural numbers}.
\\ (\emph{Warning:} Some textbooks do not consider~$0$ to be a natural number.)
\item   $\natural^+ = \{1, 2, ... \}$%
\nindex{$\natural^+$}
is the set of \emph{positive natural numbers}.
\item   $\integer = \{\ldots, -3,-2,-1, 0, 1, 2,3,\ldots \}$%
\nindex{$\integer$}
is the set of \emph{integers}. A number is an integer if and only if it is either a natural number or the negative of a natural number.
\item  $\displaystyle 
\rational = \bigset{ 
\frac{p}{q} }{ \begin{matrix} p,q \in \integer \\ q \neq 0 \end{matrix} }$%
\nindex{$\rational$}
is the set of \emph{rational numbers}.\index{rational number}
(This notation means that a number~$x$ is an element of~$\rational$ if and only if there exist integers $p$ and~$q$, with $q \neq 0$, such that $x = p/q$ \cfSect{PredicateMakeSubsetSect}.)
%This is the set of all fractions $p/q$, where $p$~and~$q$ are integers and $q \neq 0$. 
For example, $1/2$, $7/5$, and $-32/9$ are elements of~$\rational$.
\item $\real$%
\nindex{$\real$} is the set of all \emph{real numbers}. (That is, the set of all numbers that are either positive or negative or~$0$. Unless you have learned about ``complex numbers'' or ``imaginary numbers\rlap,'' it is probably the case that all the numbers you know are real numbers.) For example, $\root 3 \of n$ is a real number whenever $n \in \integer$; and $\sqrt{n}$ is a real number whenever $n \in \natural$. (``You can't take the square root of a negative number\rlap.'')
\end{itemize}
\end{notation}

\begin{rem}
Sets are the most fundamental objects in mathematics. Indeed, modern mathematicians consider every object everywhere to be a set, but we will not be quite this extreme. Namely, in addition to sets, we will consider two additional types of objects: numbers and ordered pairs. (It is assumed that you already have a lot of experience with numbers, and know how to deal with them. You have probably also seen ordered pairs $(x,y)$, but their basic properties will be reviewed in \cref{OrderedPairDefn}.)
Functions are another very important class of mathematical objects, but, as will be seen in \cref{introfunctionsSect}, we can think of them as being a particular type of set.
\end{rem}


\subsection{Cardinality} \label{NaiveCardSect}

\begin{notation} \label{InformalCardinalityDefn}
We use $\#A$%
\nindex{$\#$ (\emph{informal})}
to denote the number of elements in the set~$A$. 
(Thus, for example, 
	$\#\{\var{a}, \var{e}, \var{i}, \var{o}, \var{u} \} = 5$.)
Mathematicians call $\#A$ the \define{cardinality} of~$A$. This seemingly simple notion actually has some complicated implications, and will be discussed in more detail in \cref{CardinalityChap}.
\end{notation}

 \begin{othernot}
 Many mathematicians use the notation $|A|$ instead of $\# A$.
 \end{othernot}

\begin{rem}
You probably already know that some sets are finite and some (such as~$\natural$) are infinite. We will discuss this in more detail in \cref{CardinalityChap}. For now, we remind you that a set~$A$ is \define[finite set]{finite} iff the elements of~$A$ can be counted (and the answer is some number~$n$); that is, if $\#A = n$, for some $n \in \natural$.
\end{rem}

\begin{exers} \label{EasyCardEx}
What is the cardinality of each set?
\noneed
\begin{tasks}(3)
\task\fixtask \label{EasyCardEx-abcd}
$\#\{\var{a}, \var{b}, \var{c}, \var{d} \} = $
\task\fixtask \label{EasyCardEx-aabccd}
$\#\{\var{a}, \var{a}, \var{b}, \var{c}, \var{c}, \var{d} \} = $ %(recall that repetitions do not count!),
\task\fixtask \label{EasyCardEx-a(bc)}
$\#\bigl\{\var{a}, \{\var{b}, \var{c} \}  \bigr\} = $ %(the only elements are $\var{a}$ and $\{\var{b}, \var{c} \}$).
\task\fixtask \label{EasyCardEx-aa(bc)(bcd)}
$\#\bigl\{\var{a}, \var{a}, \{\var{b}, \var{c}\}, \{\var{b}, \var{c}, \var{d} \} \bigr\} = $
\task\fixtask \label{EasyCardEx-0}
$\#\emptyset =$
\task\fixtask \label{EasyCardEx-(0)}
$\#\{\emptyset\} =$ 
\end{tasks}
\end{exers}






\subsection{Subsets} \label{SubsetsSect}

%\subsection{Definition and basic properties}

Geometry students are taught that  every square is a rectangle. Translating this into the terms of set theory, we can say that if
\begin{itemize}
\item $S$ is the set of all squares, 
and
\item $R$ is the set of all rectangles,
\end{itemize}
then every element of the set~$S$ is also an element of~$R$. For short, we say that $S$ is a \emph{subset} of~$R$, and we may write $S \subset R$.%
\nindex{$\subset$}

\begin{defn}
Suppose $A$ and~$B$ are two sets. We say that $B$ is a \define{subset} of~$A$ iff every element of~$B$ is an element of~$A$.
\end{defn}

When $B$ is a subset of~$A$:
\begin{itemize}
\item In symbols, we write $B \subset A$. 
\item We may say that $B$ is \define{contained in}~$A$ or that $A$ \define{contains}~$B$.
\item We may also write $A \supset B$%
\nindex{$\supset$}
(and call $A$ a \define{superset} of~$B$). 
\end{itemize}

\begin{eg} \ 
\begin{enumerate}
\item $\{1,2,3\}$ is a subset of $\{1,2,3,4\}$, because the elements of~$\{1,2,3\}$ are $1$, $2$, and~$3$, and every one of those numbers is an element of $\{1,2,3,4\}$.
\item $\{1,3,5\}$ is \emph{not} a subset of $\{1,2,3,4\}$, because there is an element of~$\{1,3,5\}$ (namely,~$5$) that is not an element of $\{1,2,3,4\}$.
%\item $\emptyset$ is a subset of $\{1,2,3,4\}$. 
\item We have $\natural^+ \subset \natural \subset \integer \subset \rational \subset \real$.
\end{enumerate}
\end{eg}


\begin{rem} \ 
\begin{enumerate}
\item We write $B \notsubset A$%
\nindex{$\notsubset$}
to denote that $B$ is \emph{not} a subset of~$A$.
\item We have $B \notsubset A$ iff there is at least one element of~$B$ that is \emph{not} an element of~$A$.
\end{enumerate}
\end{rem}
 
\begin{rem} \label{SubsetFacts} \ 
\begin{enumerate}
\item In the language of everyday life, suppose someone gives you a box~$A$ that has some stuff in it. You are allowed to take some of the things from the box and put them into a new box~$B$. But you are not allowed to put anything into~$B$ if it was not in box~$A$. Then $B$ will be a subset of~$A$.
\item If you decide to take all of the things that were in box~$A$, then box $B$ will end up being exactly the same as~$A$; that is $B = A$. This illustrates the fact that every set is a subset of itself.
\factoidbox{For every set~$A$, we have $A \subset A$.}
\item If you decide not to take anything at all from box~$A$, then box $B$ will be empty. This illustrates the important fact that the empty set is a subset of every set.
\factoidbox{For every set~$A$, we have $\emptyset \subset A$.}
\end{enumerate}
\end{rem}

\begin{defn}
Suppose $A$ and~$B$ are sets. We say $B$ is a \define[subset!proper]{proper subset} of~$A$ iff 
$B \subset A$ \emph{and} $B \neq A$.
\end{defn}

\begin{othernot}
Many mathematicians use a slightly different notation: they define $A \subset B$ to mean that $A$ is a \emph{proper} subset of~$B$. Then, to say that $A$ is a subset of~$B$, they write $A \subseteq B$.
\end{othernot}
 
 \begin{exer} \label{SubsetOrNotEx}
 Fill each blank with $\subset$ or $\notsubset$, as appropriate.
\begin{tasks}(2)
 \task\fixtask \label{SubsetOrNotEx-s_horns}
$\{\var{s}\} \blank  \{\var{h},\var{o},\var{r},\var{n},\var{s}\}$
 \task\fixtask \label{SubsetOrNotEx-or_horns}
$\{\var{o},\var{r}\} \blank \{\var{h},\var{o},\var{r},\var{n},\var{s}\}$
 \task\fixtask \label{SubsetOrNotEx-nor_horns}
$\{\var{n},\var{o},\var{r}\} \blank \{\var{h},\var{o},\var{r},\var{n},\var{s}\}$
 \task\fixtask \label{SubsetOrNotEx-prong_horns}
$\{\var{p},\var{r},\var{o},\var{n},\var{g}\} \blank \{\var{h},\var{o},\var{r},\var{n},\var{s}\}$
 \task\fixtask \label{SubsetOrNotEx-shorn_horns}
$\{\var{s},\var{h},\var{o},\var{r},\var{n}\} \blank \{\var{h},\var{o},\var{r},\var{n},\var{s}\}$
 \task\fixtask \label{SubsetOrNotEx-0_horns}
$\emptyset \blank \{\var{h},\var{o},\var{r},\var{n},\var{s}\}$
 \task\fixtask \label{SubsetOrNotEx-(0)_horns}
$\{\emptyset\} \blank \{\var{h},\var{o},\var{r},\var{n},\var{s}\}$
  \task\fixtask \label{SubsetOrNotEx-horns_0}
$\{\var{h},\var{o},\var{r},\var{n},\var{s}\} \blank \emptyset$
 \end{tasks}
 \end{exer}

%\begin{prop} \label{SubsetIsTransitive}
%The relation $\subset$ is \emph{transitive:} that is, if $A \subset B$ and $B \subset C$, then $A \subset C$.
%\end{prop}

%\begin{proof} 
%Assume $A \subset B$ and $B \subset C$. We wish to show, for every $a \in A$, that $a \in C$.

%Given $a \in A$. Because $A \subset B$, we have $a \in B$. 
%Then, because $B \subset C$, we have $a \in C$, as desired.
%\end{proof}

It is intuitively clear that a subset of a set cannot have more elements than the original set. That is:
\factoidbox{If $B \subset A$, then $\#B \le \#A$.}
We will prove this fact in \fullcref{CardinalitySubsetExers}{subset}.

%Let us state this as an official result:

%\begin{prop}
%Suppose $A \subset B$, and $B$ is finite. Then:
%\begin{enumerate}
%\item $A$ is finite,
%and
%\item $\#A \le \#B$.
%\end{enumerate}
%\end{prop}

%\begin{proof}
%Since $A \subset B$, we may define $f \colon A \to B$ by $f(a) = a$. It is clear that $f$ is one-to-one, so we conclude from Thm.~\fullref{Cardinality:OneToOneVsOntoThm}{11} that $\#A \le \#B$, as desired.
%\end{proof}



%\section{How to show two sets are equal}

In \cref{EqualIffSubsets}, we will prove that two sets are equal if and only if they are subsets of each other.
This is a basic principle that will be very important in later chapters when we are doing proofs with sets:
\factoidbox{To show two sets $A$ and $B$ are equal, prove $A \subset B$ and $B \subset A$.%
\label{Mention2SetsEqual}}



\begin{exers} \label{Subset2ColPfEx}
Write a two-column proof to justify each assertion.

\begin{problist}
\item \label{Subset2ColPfEx-XnotY}
$X \subset Y \eif X \subset Z$, $X \subset Z \eif x \in Z$, $x \notin Z$, \ \therefore $X \notsubset Y$.
\item  \label{Subset2ColPfEx-XYorYX}
$(x \in Y) \eif (X \subset Y)$, $(x \in Y) \eor (Y \subset X)$, \ \therefore $(X \subset Y) \eor (Y \subset X)$.
\end{problist}
\end{exers}











\subsection{Predicates} \label{sec.predicates}

The simplest predicates are things you can say about a single object; they are properties of individuals. For example, ``$x$~is a dog'' and ``$x$~is a \emph{Harry Potter} fan'' are both predicates. 
In {\QL}, we symbolize predicates with capital letters $A$ through $Z$ (with or without subscripts). Thus, our symbolization key might include:
\smallskip % !!!
	\begin{multicols}{2}
	\begin{ekey}
	\item[D(x)] $x$~is a dog. 
	\nindex{$P(x)$, $Q(x)$, etc.}
	\item[H(x)] $x$~is a \emph{Harry Potter} fan.
	\end{ekey}
	\end{multicols}
Predicates like these are called \define[predicate!one-place]{one-place} or \define[predicate!unary]{unary}, because there is only one variable. Assigning a value to this variable yields an assertion. For example, letting $x$ = ``Lassie'' in the first predicate yields the assertion ``Lassie is a dog\rlap.'' Note that in translating English assertions, the variable will not always come at the beginning of the assertion: 
``the Louvre owns at least one watercolour painted by~$x$'' is also a predicate.

Other predicates are about the \emph{relation} between two things. For instance, in algebra, we have the relations ``$x$ is equal to~$y$\rlap,'' symbolized as $x = y$, and ``$x$~is greater than~$y$\rlap,'' symbolized as $x > y$. These are \define[predicate!two-place]{two-place} or \define[predicate!binary]{binary} predicates, because values need to be assigned to two variables in order to make an assertion. Our symbolization key might include:
	\begin{ekey}
	\item[x \mathrel{F} y] $x$~is a friend of~$y$.
	\nindex{$x \mathrel{R} y$, $x \mathrel{L} y$, etc.}
	\item[x \mathrel{L} y] $x$~is to the left of~$y$.
	\item[x \mathrel{M} y] $x$~owes money to~$y$.
	\end{ekey}

In general, we can have predicates with as many variables as we need. Predicates with $n$~variables, for some number~$n$, are called \define[predicate!n-place@$n$-place]{$n$-place} or \define[predicate!n-ary@$n$-ary]{$n$-ary}.  However, in practice, predicates almost always have only one or two variables.

A symbolization key may also include \define{constants} (that is, the names of specific objects). For example, we might have a symbolization key that looks like this:
\smallskip % !!!
\begin{multicols}{4} % have to manually reorder to use multicols instead of tasks !!!
\begin{ekey}
\item[H(x)] $x$ \hbox to 0pt{is happy.\hss}% !!!
\item[g] Greg
\item[S(x)] $x$ \hbox to 0pt{is singing.\hss}% !!!
\item[m] Mary
\item[x \mathrel{T} y] $x$ is \hbox to 0pt{teaching $y$.\hss} % !!!
\item[v] Vikki
\end{ekey}
\end{multicols}

 This allows us to symbolize assertions that use any combination of these predicates and terms. For example:
%\begin{assertlist}
%\nix{I am inclined to change these to Cordelia, Hamlet, and Macbeth}
%\item[\ex{terms1}] Donald is angry.
%\item[\ex{terms2}] If Donald is angry, then so are Greg and Mary.
%\item[\ex{terms3}] Mary is at least as tall and as friendly as Greg.
%\item[\ex{terms4}] Donald is shorter than Greg.
%\item[\ex{terms5}] Donald is married to Mary.
%%\item[\ex{terms5}] Greg is between Donald and Mary.
%\item[\ex{terms6}] Greg is at least as tall as both Donald and Mary.
%\end{assertlist}
%
%\assert{terms1} is straightforward: $A(d)$. 
%
%\assert{terms2} can be paraphrased as, ``If $A(d)$, then $A(g)$ and $A(m)$\rlap.'' {\QL} has all the logical connectives of {\SL}, so we translate this as $A(d) \eif \bigl( A(g) \eand A(m) \bigr)$.
%
%\assert{terms3} can be translated as $(m \mathrel{T} g) \eand (m \mathrel{F} g)$.  
%
%\assert{terms4} might seem as if it requires a new predicate. If we only needed to symbolize this assertion, we could define a predicate like $x \mathrel{S} y$ to mean ``$x$ is shorter than $y$\rlap.'' However, this would ignore the logical connection between ``shorter'' and ``taller\rlap.'' Considered only as symbols of {\QL}, there is no connection between $S$ and~$T$. They might mean anything at all. Instead of introducing a new predicate, we paraphrase \assert{terms4} using predicates already in our key: ``It is not the case that Donald is at least as tall as Greg\rlap.'' We can translate it as $\enot (d \mathrel{T} g)$.%, or $d \not\mathrel{T} g$.
%
%Notice that, as mentioned previously, the order of the variables (or here, the constants) is important: saying $\enot (d \mathrel{T} g)$ (that Donald is shorter than Greg) is very different from saying $\enot (g \mathrel{T} d))$ (that Greg is shorter than Donald)!
%
%\assert{terms5} can be translated as $d \mathrel{M} m$.  Even though in English, if Donald is married to Mary, then it is also true that Mary is married to Donald, we should \emph{not} translate this as $m \mathrel{M} d$.  Getting sloppy with the order of variables (or constants) can lead you to making mistakes in cases where the order really is important.
%
%%\assert{terms5} requires that we pay careful attention to the order of terms in the key. It becomes $B(d,g,m)$.
%
%\assert{terms6} says two things: that Greg is at least as tall as Donald, and that Greg is at least as tall as Mary. Thus, we can translate it as $(g \mathrel{T} d) \eand (g \mathrel{T} m)$.
\begin{center} \renewcommand{\arraystretch}{1.25}
\begin{tabular}{|c|c|}
\hline
\it assertion & \it symbolization \\
\hline
Greg is happy. 
	& $H(g)$ \\
If Mary is singing, then Vikki is happy. 
	& $S(m) \eif H(v)$ \\
Greg and Mary are singing.
	& $S(g) \eand S(m)$ \\
If either Greg or Mary is singing, then Vikki is not happy. 
	& $\bigl( S(g) \eor S(m) \bigr) \eif \enot H(v)$ \\ 
Mary is teaching Greg. 
	& $m \mathrel{T} g$ \\
Mary is not teaching Vikki. 
	& $\enot( m \mathrel{T} v)$ \\
Vikki is teaching either Mary or Greg. 
	& $(v \mathrel{T} m) \eor (v \mathrel{T} g)$ \\
If Mary is teaching Greg, then Mary and Vikki are happy. 
	& $(m \mathrel{T} g) \eif \bigl( H(m) \eand H(v) \bigr)$ \\ 
Either Vikki is not singing, or she is not teaching Mary.
	& $\bigl( \enot S(v) \bigr) \eor \enot (v \mathrel{T} m)$ \\
If Mary is singing, then Greg is not teaching Vikki. 
	& $S(m) \eif \enot (g \mathrel{T} v )$ \\
%If Mary is not happy, then she is teaching Greg and Vikki.
%	& $\bigl( \enot H(m) \bigr) \eif\bigl( (m \mathrel{T} g) \eand (m \mathrel{T} v ) \bigr)$ \\
\hline
\end{tabular}
\end{center}

\begin{warn}
Whenever you  have a predicate with two (or more) variables, it is important to be careful about the order in which the variables occur.  (For example, saying $x < y$ is certainly not the same as saying $y < x$.)  Some special choices of predicates are ``symmetric\rlap,'' which means that if the predicate is true with variables in one order, then it is true for the same variables in a different order, but this should \emph{never} be assumed.  The order of the variables should always represent exactly what we know.  %We will give an example of this shortly.
\end{warn}

\vbox{% don't allow page break !!!
\begin{exers} \label{WriteEnglishExer}
Using the symbolization key given below, give an English version of each assertion.
\begin{multicols}{2} %% !!!
\begin{ekey}
\item[x \mathrel{O} y] $x$ is older than $y$.
\item[x \mathrel{F} y] $x$ is a friend of $y$.
\item[S] the set of all students.
\item[r]Roger
\item[s]Sam
\item[t]Tess
\end{ekey}
\end{multicols}
\begin{tasks}(2)
\task\fixtask \label{WriteEnglishExer-ros}
$r \mathrel{O} s$
\task\fixtask \label{WriteEnglishExer-tos}
$t \mathrel{O} s$
\task\fixtask \label{WriteEnglishExer-rft}
$(r \mathrel{F}  t) \eif (t \in S)$
\task\fixtask \label{WriteEnglishExer-ssrs}
$\bigl( (s \in S) \eand (r \in S) \bigr) \eif (s \mathrel{F} r)$
\task\fixtask \label{WriteEnglishExer-tsrot}
$(t \in S) \eor (r \mathrel{O} t)$
\task\fixtask \label{WriteEnglishExer-rfsts}
$(r \mathrel{F} s) \eiff (t \notin S)$
\end{tasks}
\end{exers}%
}

\begin{exers} \label{EnglishFromPreds}
Using the same symbolization key, write these English assertions using predicates and logical connectives.
\begin{problist}
\item \label{EnglishFromPreds-tor}
Tess is older than Roger.
\item \label{EnglishFromPreds-rfs}
Roger is a friend of Sam.
\item \label{EnglishFromPreds-tstfs}
If Tess is a student then Tess is a friend of Sam.
\item \label{EnglishFromPreds-ssrns}
Either Sam is a student, or Roger is not a student.
\item \label{EnglishFromPreds-rfsss}
If Roger is a friend of Sam, then Sam is a student.
\item \label{EnglishFromPreds-sorrs}
Sam is older than Roger if and only if Roger is a student.
\item \label{EnglishFromPreds-srssfr}
If Sam and Roger both are students, then Sam is not a friend of Roger.
\end{problist}
\end{exers}


\begin{exers} \label{Write3ColPfRogerSamExer}
Using the same symbolization key, write a two-column proof to justify each of the following deductions.
\begin{problist}
\item \label{Write3ColPfRogerSamExer-symbol}
 $(r \in S) \eif \bigl( (r \mathrel{O} s) \eor (r \notin S) \bigr)$,
\quad \therefore~$\bigl( (t \in S) \eand \enot  (r \mathrel{O} s)  \bigr) \eif (r \notin S)$

\item \label{Write3ColPfRogerSamExer-English}
 If either Roger is a student, or Tess is \emph{not} a student, then Sam is older than Tess.
\\ If Tess is a student, then Roger is also a student.
\\ \therefore~Sam is older than Tess.
\end{problist}
\end{exers}






\subsection{Using predicates to specify subsets} \label{PredicateMakeSubsetSect}

Subsets arise in everyday life whenever you want only \emph{part} of something. For example, suppose you are in a kitchen with a lot of plates. If you are washing dishes, then you do not want to be given \emph{all} of the plates, but only the ones that are dirty. In mathematical terms, you do not want the set of all plates, but only want a subset, those that are dirty. That is, if $P$ represents the set of all plates, and $D$ represents the set of all dirty plates, then $D \subset P$. 

This type of situation is handled by the following useful notation:
\factoidbox{Suppose $A$ is a set and $P(x)$ is a predicate.
% (that is, for each $a \in A$, $P(a)$ is an assertion that is either true or false). 
\\ Then
$ \{\, a \in A \mid P(a) \,\}$
 denotes
\\  the set of 
  all elements~$a$ of~$A$, 
  such that $P(a)$ is true.\nindex{$ \{\, a \in A \mid P(a) \,\}$}
 \\ It is a subset of~$A$.}
%Usually, a subset of a set is described by giving a \emph{condition} that determines whether or not each element of the set belongs to the subset. For example, suppose $B = \{1,2,3,\ldots, 10\}$. Then:
%\begin{enumerate}
%\item $\{1,3,5,7,9\}$ is the set consisting of all the elements of~$B$ that are odd. It is a subset of~$B$.
%\item $\{2,4,6,8,10\}$ is the set consisting of all the elements of~$B$ that are even. It is a subset of~$B$.
%\item $\{2,3,5,7\}$ is the set consisting of all the elements of~$B$ that are prime. It is a subset of~$B$.
%\end{enumerate}
%Mathematicians have a notation for defining subsets in this way. If ``$P(b)$'' is some condition that depends on~$b$, then:
%	\factoidbox{$\{\, b \in B \mid P(b) \,\}$
%		is the set of all elements of~$B$ such that $P(b)$ is true.}
%It is a subset of~$B$.
In the example above, you are interested in the subset 
	$$\{\, p \in P \mid \mbox{$p$ is dirty}\,\} ,$$
because this is the set of plates that are dirty. 
The notation tells us to look through all of the plates in~$P$, and check each one to see whether it is dirty. If it is, we put it in the subset. If it is not dirty, then we do not put it in the subset.


\begin{eg} \ 
\begin{enumerate}
\item Suppose $B = \{1,2,3,\ldots, 10\}$. Then:
\begin{enumerate}
\item $\{\, b \in B \mid \mbox{$b$ is odd}\,\} = \{1,3,5,7,9\}$. 
\item $\{\, b \in B \mid \mbox{$b$ is even}\,\} = \{2,4,6,8,10\}$.
\item $\{\, b \in B \mid \mbox{$b$ is prime}\,\} = \{2,3,5,7\}$.
\item $\{\, b \in B \mid \mbox{$b^2 - 1$ is divisible by~$3$}\,\} = \{1,2,4,5,7,8,10\}$.
\item $\{\, b \in B \mid (b-5)^2 > 4 \,\} = \{1,2,8,9,10\}$.
\item $\{\, b \in B \mid \mbox{$3 \le b \le 8$ and $b$ is even} \,\} = \{4,6,8\}$.
\end{enumerate}
\item For any $n \in \natural$, we have $\{\, i \in \natural \mid 1 \le i \le n \,\} = \{1,2,3,\ldots,n\}$.
\end{enumerate}
\end{eg}

\begin{exer} \label{ListEltsExer}
Let $A = \{1,2,3,4,5\}$ and $B = \{1,3,5,7,9\}$. Specify each set by listing its elements.
\begin{tasks}(2)
\task\fixtask \label{ListEltsExer-Aeven}
$\{\, a \in A \mid \mbox{$a$ is even} \,\} = $
\task\fixtask \label{ListEltsExer-Beven}
$\{\, b \in B \mid \mbox{$b$ is even} \,\} = $
\task\fixtask \label{ListEltsExer-Aodd}
$\{\, a \in A \mid \mbox{$a$ is odd} \,\} = $
\task\fixtask \label{ListEltsExer-Bodd}
$\{\, b \in B \mid \mbox{$b$ is odd} \,\} = $
\task\fixtask \label{ListEltsExer-A<4}
$\{\, a \in A \mid a < 4\,\} = $
\task\fixtask \label{ListEltsExer-B<4}
$\{\, b \in B \mid b < 4\,\} =$
\task\fixtask \label{ListEltsExer-A=9}
$\{\, a \in A \mid (a-3)^2 = 9\,\} = $
\task\fixtask \label{ListEltsExer-B=9}
$\{\, b \in B \mid (b-3)^2 = 9\,\} =$
\task\fixtask \label{ListEltsExer-AB}
$\{\, a \in A \mid a \in B \,\} =$
\task\fixtask \label{ListEltsExer-BA}
$\{\, b \in B \mid b \in A \,\} =$
\task\fixtask \label{ListEltsExer-AnB}
$\{\, a \in A \mid a \notin B \,\} =$
\task\fixtask \label{ListEltsExer-BnA}
$\{\, b \in B \mid b \notin A \,\} =$
\task\fixtask \label{ListEltsExer-A2B}
$\{\, a \in A \mid 2a \in B \,\} =$
\task\fixtask \label{ListEltsExer-B2A}
$\{\, b \in B \mid 2b \in A \,\} =$
\task\fixtask \label{ListEltsExer-a2B}
$\{\, a \in A \mid a^2 \in B \,\}= $
\task\fixtask \label{ListEltsExer-a2<0}
$\{\, a \in A \mid a^2 < 0 \,\}= $
\end{tasks}
\end{exer}


Students of mathematics are expected to be able to \emph{prove} assertions about sets and their subsets. Before giving an example of this, let us point out that if $A$ is a set, $P(x)$ is a predicate, and 
	$$ B = \{\, a \in A \mid P(a) \,\} ,$$
then the assertion ``$b \in B$'' is logically equivalent to the assertion ``$(b \in A) \eand P(b)$\rlap.'' Thus, in a proof:
 	\begin{itemize}
	\item if the assertion $b \in B$ is known to be true, then we also know that $b \in A$ and $P(b)$ are also true;
	and
	\item if the assertions $b \in A$ and $P(b)$ are both known to be true, then we also know that $b \in B$ is true.
	\end{itemize}
In a $2$-column proof, the justification for these assertions is ``definition of~$B$'' or ``because $B = \{\, a \in A \mid P(a) \,\}$\rlap.''

Of course, not all sets are called $A$ and~$B$, but the same principles hold for sets named with other letters.

\begin{eg}
Suppose $X$ and~$Y$ are sets, and let $Z = \{\, y \in Y \mid y \notin X \,\}$. Show that if $z \in Z$, then $z \notin X$.
\end{eg}

\begin{solution}
Assume $z \in Z$. Then, from the definition of~$Z$, we know $z \in Y$ and $z \notin X$. In particular, $z \notin X$, as desired.
\end{solution}

\begin{exers} \label{SetBuilder} \ 
	\begin{enumerate}
	\item \label{SetBuilder-A}
	Assume $A = \{\, d \in D \mid \text{$d$ is hungry} \,\}$.
		\begin{enumerate}
		\item \label{SetBuilder-A-know}
		If we \emph{know} that $p \in A$, then what do we know about~$p$?
		\item \label{SetBuilder-A-prove}
		If we want to \emph{prove} that $q \in A$, then what do we need to show?
		\end{enumerate}
	
	\item \label{SetBuilder-K}
	Assume $f(x) = x^2$ and $K = \{\, y \in \real \mid f(y) > 2 \,\}$.
		\begin{enumerate}
		\item \label{SetBuilder-K-know}
		If we \emph{know} that $s \in K$, then what do we know about~$s$?
		\item \label{SetBuilder-K-prove}
		If we want to \emph{prove} that $t \in K$, then what do we need to show?
		\end{enumerate}
	
	\item \label{SetBuilder-G}
	Assume $G = \{\, i \in I \mid M(i) \,\}$, where $M(x)$ is a predicate.
		\begin{enumerate}
		\item \label{SetBuilder-G-know}
		If we \emph{know} that $v \in G$, then what do we know about~$v$?
		\item \label{SetBuilder-G-prove}
		If we want to \emph{prove} that $w \in G$, then what do we need to show?
		\end{enumerate}
	\end{enumerate}
\end{exers}

\begin{exers} \label{EngSetPfsEx}
Write your proofs in English.
\begin{enumerate}
\item  \label{EngSetPfsEx-cinB}
Assume $A$ and~$B$ are sets, and let $C = \{\, a \in A \mid a \in B\,\}$. Show that if $c \in C$, then $c \in B$.
\item  \label{EngSetPfsEx-a<10}
Let $A = \{\, x \in \real \mid x^2 - 5x = 14\,\}$. Show that if $a \in A$, then $a < 10$.
\end{enumerate}
\end{exers}

\begin{notation}
%Listing the elements is often a good way to specify a particular set, but it is not convenient when there are a lot of elements. For this situation, we have a useful notation: % \defit{set-builder notation}: 
%\begin{enumerate}
%\item Suppose $A$ is a set and $P(x)$ is a predicate (that is, for each $a \in A$, $P(a)$ is an assertion that is either true or false). Then
%$$ \{\, a \in A \mid P(a) \,\}$$
% denotes the set of all elements~$a$ of~$A$, such that $P(a)$ is true. For example, if $A = \{-3,-2,-1,0,1,2,3\}$, then 
% $$ \{\, a \in A \mid \mbox{$a$ is odd} \,\} = \{ -3,-1,1,3\}$$
% and
% $$\{\, a \in A \mid a \ge 0 \} = \{0,1,2,3\} .$$
% (In the first example, the predicate $P(x)$ is ``$x$~is odd''; in the second example, $P(x)$ is ``$x \ge 0$\rlap.'')
%\item 
When talking about sets or using predicates, we usually assume that a ``\define{universe of discourse}''~$\univ$%
\nindex{$\univ$}
 has been agreed on. This means that all the elements of all of the sets under discussion are assumed to be members of~$\univ$. Then
$$ \{\, x \mid P(x) \,\} 
\nindex{$\{\, x \mid P(x) \,\}$} $$
can be used as an abbreviation for $\{\, x \in \univ \mid P(x) \,\}$.
\end{notation}


The universe of discourse is sometimes assumed to be understood from the context, but it is an important concept, and it is best to specify it so that there is no room for confusion.  For example, if we say ``Everyone is happy\rlap,'' who is included in this \emph{everyone}? We usually do not mean everyone now alive on the Earth. We certainly do not mean everyone who was ever alive or who will ever live. We mean something more modest: perhaps we mean everyone in the building, or everyone in the class, or maybe we mean everyone in the room.

Specifying a universe of discourse eliminates this ambiguity. The \univ{} is the set of things that we are talking about. So if we want to talk about people in Lethbridge, we define \univ{} to be the set of all people in Lethbridge. We write this at the beginning of our symbolization key, like this:
\begin{ekey}
\item[\univ ] the set of all people in Lethbridge
\end{ekey}
Everything that follows \emph{ranges over} the universe of discourse. Given this \univ, ``everyone'' means ``everyone in Lethbridge'' and ``someone'' means ``someone in Lethbridge\rlap.'' 

Each constant names some member of \univ, so, if \univ{} is the set of people in Lethbridge, then constants Donald, Greg, and Mary can only be used if these three people are all in Lethbridge. If we want to talk about people in places besides Lethbridge, then we need to specify a different universe of discourse.

\begin{eg} 
%\begin{enumerate}
%\item 
If $\univ$ is the set of all Canadian provinces, then
	$$\{\, x \mid \mbox{the English name of~$x$ has three syllables} \,\}
	= \{ \var{Alberta}, \var{New Brunswick} \}  % , \var{Newfoundland}
	. $$
%\end{enumerate}
\end{eg}


\begin{rem}
There is a very close relationship between sets and unary predicates. 
In general:
\begin{itemize}
\item From any unary predicate $P(x)$, we can define the set 
	$$\{x \mid P(x)\} .$$
\item Conversely, from any set~$A$, we can define a unary predicate $P(x)$ to be ``$x$ is a member of~$A$\rlap.''  
\end{itemize}
Because of this, sets are more-or-less interchangeable with unary predicates.
For example, the predicate ``$x$~is a dog'' can be symbolized in two quite different ways:
\begin{itemize}
\item Our symbolization key could state that $D(x)$ means ``$x$~is a dog\rlap.''
\item Alternatively, our symbolization key could let $D$ be the set of all dogs. Then ``$x$~is a dog'' would be translated as ``$x \in D$\rlap.''
\end{itemize}
Mathematicians use sets much more often than unary predicates. We will see in \cref{DimeSetBetter} that this tends to make it easier to translate statements from English into {\QL} when quantifiers are involved.
\end{rem}




\section{Operations on sets} \label{SetOperationsSect}

%\begin{quote}
%\it While I am interested both in economics and in philosophy, the union of my interests in the two fields far exceeds their intersection.
%\par\raggedleft \small\rm\sf
%Amartya Sen (b.\,1933), Nobel prize-winning economist
%\\ 
%Autobiography on nobelprize.org
%\end{quote}

There are several important ways that a new set can be made from sets that you already have. 
Any method of doing this is called a \define[set!operation]{set operation}. 

\subsection{Union and intersection}

Two of the most basic operations are \emph{union} and \emph{intersection}. Let us first discuss them in informal terms.
 Suppose:
 \begin{itemize}
 \item Alice and Bob are going to have a party, and need to decide who should be invited, 
\item Alice made a list of all the people that she would like to invite, 
and 
\item Bob made a list of all the people that he would like to invite. 
\end{itemize}
Here are two of the many possible decisions they could make.
\begin{enumerate}
\item One solution would be to invite everyone that is on either of the lists. That is, they could begin their invitation list by writing down all of the names on Alice's list, and then add all of the names from Bob's list (or, more precisely, the names from Bob's list that are not already included in Alice's list). This is the \emph{union} of the lists.
\item A much more conservative solution would be to invite only the people that appear on both of the lists. That is, they could go through Alice's list, and cross off everyone that does not appear on Bob's list. (They would get the same result by going through Bob's list, and crossing off everyone that does not appear on Alice's list.) This is the \emph{intersection} of the lists. 
\end{enumerate}

\begin{defn}
Suppose $A$ and~$B$ are sets.
\begin{enumerate}
\item The \define{union} of~$A$ and~$B$ is the set
	$$A \cup B = \{\, x \mid \mbox{$x \in A$ \textbf{or} $x \in B$} \,\} 
	\nindex{$\cup$}
	.$$
\item The \define{intersection} of~$A$ and~$B$ is the set
	$$A \cap B = \{\, x \mid \mbox{$x \in A$ \textbf{and} $x \in B$} \,\} 
	\nindex{$\cap$}
	.$$
\end{enumerate}
\end{defn}

\begin{rem}
By drawing the sets~$A$ and~$B$ as overlapping circles, the union and intersection can be represented as follows: 
\begin{center}
\centerline{\includegraphics[scale=0.4]{PDF/UnionAndIntersection.pdf}}
 $A \cup B$ is shaded \hskip 0.5in $A \cap B$ is shaded
\end{center}
Pictures like these are called \define{Venn diagrams}. 
\end{rem}

\begin{rem} \ 
\begin{enumerate}
\item In ordinary English, the word ``intersection'' refers to where two things meet. For example, the intersection of two streets is where the two streets come together. We can think of this area as being part of both streets, so this is consistent with the way the term is used in mathematics.
\item In ordinary English,  the word ``union'' refers to joining things together. For example, a marriage is the union of two people --- it joins the two people into a single married couple. This is consistent with the way the term is used in mathematics --- we could form the union of Alice's list and Bob's list by gluing Bob's list to the end of Alice's list.
\end{enumerate}
\end{rem}

\begin{eg} \ 
\begin{enumerate}
\item $\{1,3,5,7,9\} \cup \{1,4,7,10\} = \{1,3,4,5,7,9,10\}$
\item $\{1,3,5,7,9\} \cap \{1,4,7,10\} = \{1,7\}$
\end{enumerate}
\end{eg}

\begin{exers} \label{SetOpListEltsEx}
Specify each set by listing its elements. \noneed
\begin{enumerate}
\item \label{SetOpListEltsEx-1234+34567}
$\{1,2,3,4\} \cup \{3,4,5,6,7\} =$
\item \label{SetOpListEltsEx-1234*34567}
$\{1,2,3,4\} \cap \{3,4,5,6,7\} =$
\item \label{SetOpListEltsEx-prong*horns}
$\{\var{p},\var{r},\var{o},\var{n},\var{g}\} \cap \{\var{h},\var{o},\var{r}, \var{n}, \var{s}\} =$
\item \label{SetOpListEltsEx-prong+horns}
$\{\var{p},\var{r},\var{o},\var{n},\var{g}\} \cup \{\var{h},\var{o},\var{r}, \var{n}, \var{s}\} =$
\item \label{SetOpListEltsEx-(135+234)*246}
$\bigl( \{1,3,5\} \cup \{2,3,4\} \bigr) \cap \{2,4,6\} =$
\item \label{SetOpListEltsEx-(135*234)+246}
$\bigl( \{1,3,5\} \cap \{2,3,4\} \bigr) \cup \{2,4,6\} =$
\end{enumerate}
\end{exers}

\begin{exers} \label{SetOp1stPfEx} \ 
%Write your proofs in English.
\begin{enumerate}
\item \label{SetOp1stPfEx-cinA}
Assume $A$ and $B$ are sets. Prove that if $c \in A \cap B$, then $c \in A$.
\item \label{SetOp1stPfEx-rinX}
Assume $X$, $Y$, and~$Z$ are sets. Prove that if $r \in (X \cap Y) \cup (X \cap Z)$, then $r \in X$.
\end{enumerate}
\end{exers}

\begin{rem} \ 
\begin{enumerate}
\item It is not difficult to see that $\cup$ and~$\cap$ are commutative. That is, for all sets $A$ and~$B$, we have
$$ \mbox{$A \cup B = B \cup A$ \quad and \quad $A \cap B = B \cap A$.} $$
\item It is also not difficult to see that $\cup$ and~$\cap$ are associative. That is, for all sets $A$, $B$, and~$C$, we have
$$ \mbox{$(A \cup B) \cup C = A \cup (B \cup C)$ \quad and \quad $(A \cap B) \cap C = A \cap (B \cap C)$.} $$
So there is no need for parenthesis when writing $A \cup B \cup C$ or $A \cap B \cap C$. (However, you \emph{do} need parentheses when writing something like $A \cup (B \cap C)$ or $(A \cup B) \cap C$, which uses both $\cup$ and~$\cap$.)
\end{enumerate}
\end{rem}

\begin{eg}
A Venn diagram can include more than two sets. For example, here are Venn diagrams of $A \cap B \cap C$ and $A \cap (B \cup C)$.
\begin{center}
\centerline{\includegraphics[scale=0.4]{PDF/Venn3.pdf}}
 $A \cap B \cap C$ is shaded \hskip 0.5in $A \cap (B \cup C)$ is shaded
\end{center}
\end{eg}

\begin{exer} \label{SetOpVennEx}
Draw a Venn diagram of each set. \noneed
\begin{tasks}(4)
\task\fixtask \label{SetOpVennEx-A+B+C}
$A \cup B \cup C$
\task\fixtask \label{SetOpVennEx-A+(B*C)}
$A \cup (B \cap C)$
\task\fixtask \label{SetOpVennEx-(A+B)*C}
$(A \cup B) \cap C$
\task\fixtask \label{SetOpVennEx-(A*C)+(B*C)}
$(A \cap C) \cup (B \cap C)$
\end{tasks}
\end{exer}

%\begin{exer} \label{SetOp3ColExer}
%Provide a two-column proof (and appropriate symbolization key) for the following deduction:
%\begin{earg}
%\item[] $\bigl( x \in (A \cap B) \bigr) \eiff \bigl( ( x \in A) \eand (x \in B) \bigr)$
%\item[] $\bigl( x \in (A \cap C) \bigr) \eiff \bigl( ( x \in A) \eand (x \in C) \bigr)$
%\item[] $\bigl( x \in (B \cup C) \bigr) \eiff \bigl( ( x \in B) \eor (x \in C) \bigr)$
%\ \item[] $\Bigl( x \in \bigl( (A \cap B) \cup (A \cap C) \bigr) \Bigr) \eiff \Bigl( \bigl( x \in (A \cap B)\bigr) \eor (x \in (A \cap C)\bigr) \Bigr)$
%\item[] $\Bigl( x \in \bigl(A \cap (B \cup C) \bigr) \Bigr) \eiff \Bigl( ( x \in A) \eand \bigl(x \in (B \cup C) \bigr)\Bigr)$
%\conclusion $\Bigl( x \in \bigl(A \cap (B \cup C) \bigr) \Bigr) \eiff \Bigl( x \in \bigl( (A \cap B) \cup (A \cap C) \bigr) \Bigr)$
%\end{earg}
%\end{exer}




\subsection{Set difference and complement} \label{SetDiffSect}

The ``set difference'' is another fundamental operation. 
	%(The ``complement'' is an important special case.)
\begin{eg}
If there is a list of people that Alice would like to invite to the party, and also a list of people that Bob refuses to allow to come to the party (the ``veto list''), then it would be reasonable to invite the people that are on Alice's list, but not on the veto list. That is, they could start with Alice's list, and remove all of the names that are on Bob's list. This is the \define[set!difference]{set difference} of Alice's list and Bob's list. 
%(In arithmetic, the difference of two numbers $a$ and~$b$ is $a - b$; that is, what results from starting with~$a$ and taking away~$b$.)
%\item If we have the list of people that are being invited to the party,
%then we might also be interested in having a list of all the people that are \emph{not} being invited to the party. (Perhaps we want to check to make sure that no one important is missing.) This is the \emph{complement} of the invitation list.
\end{eg}

%\vskip -0.5in


\begin{defn}
Suppose $A$ and $B$ are sets.
\begin{enumerate}
\item The \define[set!difference]{set difference} of~$A$ and~$B$ is the set
	$$A \sm B = \{\, x \in A \mid x \notin B \,\} = \{\, x \mid (x \in A) \eand (x \notin B) \,\}.
	\nindex{$\sm$}
	$$
\item The \define[complement of a set]{complement} of~$B$ is the set
	$$\comp{B} = \univ \sm B = \{\, x \mid x \notin B \,\} ,
	\nindex{$\comp{\phantom{\ j}}$}
	$$ 
where $\univ$ is the universal set, as usual.
\end{enumerate}
\end{defn}

\begin{othernot}
Some authors write $A - B$, instead of $A \sm B$. Also, some authors write $B^c$, instead of~$\comp{B}$
\end{othernot}


\begin{rem}
Here are Venn diagrams. 
\medskip
\begin{center}
\centerline{\includegraphics[scale=0.35]{PDF/SetDifference.pdf}}
 $A \sm B$ is shaded \hskip 0.5in $B \sm A$ is shaded
\end{center}
\medskip
\begin{center}
\centerline{\includegraphics[scale=0.35]{PDF/Complement.pdf}}
 $\comp{A}$ is shaded \hskip 1.25in $\comp{B}$ is shaded
\end{center}
\end{rem}


 


\begin{eg}
Suppose $\univ = \var{PEOPLE}$ is the set of all people.
\begin{enumerate}
\item $\comp{\var{CHILDREN}} = \var{ADULTS}$, because adults are the people who are not children.
\item $\var{FEMALES} \sm \var{CHILDREN}$ is the set of all adult women.
\end{enumerate}
\end{eg}


\begin{exers} \label{ComplementEasyEx}
Assume $\univ = \{1,2,3,\ldots,10\}$. 
Specify each set by listing its elements.
\noneed
\begin{tasks}(2)
\task\fixtask \label{ComplementEasyEx-13579/4567}
$\{1,3,5,7,9\} \sm \{4,5,6,7\} = $
\task\fixtask \label{ComplementEasyEx-4567/13579}
$\{4,5,6,7\} \sm  \{1,3,5,7,9\}= $
\task\fixtask \label{ComplementEasyEx-13579}
$\comp{\{1,3,5,7,9\} }= $
\task\fixtask \label{ComplementEasyEx-4567}
$\comp{\{4,5,6,7\}} = $
\end{tasks}
\end{exers}

\begin{exer} \label{ComplementVennEx}
Draw a Venn diagram of each set.
\noneed
\begin{tasks}(3)
\task\fixtask \label{ComplementVennEx-A+B}
$\comp{A \cup B}$
\task\fixtask \label{ComplementVennEx-A*B}
$\comp{A \cap B}$
\task\fixtask \label{ComplementVennEx-(A/B)/(A/C)}
$(A \sm B) \sm (A \sm C)$
\task\fixtask \label{ComplementVennEx-A/(B/C)}
$A \sm (B \sm C)$
\task\fixtask \label{ComplementVennEx-(A+B)/C}
$(A \cup B) \sm C$
\end{tasks}
\end{exer}

\begin{eg}
Suppose $A$ and~$B$ are sets.
Show that if $c \in \comp{A \cup B}$, then $c \in \comp{A} \cap \comp{B}$.
\end{eg}

\begin{solution}
Assume $c \in \comp{A \cup B}$. By definition of the complement, this means $c \notin A \cup B$. 
In other words, it is not true that $c \in A \cup B$. From the definition of $A \cup B$, we conclude that 
	$$ \text{it is not true that either $c \in A$ or $c \in B$} .$$
By the rules of negation, this means $c \notin A$ and $c \notin B$. Now:
	\begin{itemize}
	\item since $c \notin A$, we have $c \in \comp{A}$,
	and
	\item since $c \notin B$, we have $c \in \comp{B}$.
	\end{itemize}
Therefore, we know $c \in \comp{A}$ and $c \in \comp{B}$, so $c \in \comp{A} \cap \comp{B}$.
\end{solution}

\begin{exer} \label{SetOpCompPfEx}
Suppose $A$ and~$B$ are sets.
 Show that if $c \in \comp{A} \cap \comp{B}$, then $c \in \comp{A \cup B}$.
\end{exer}







\subsection{Disjoint sets} \label{DisjointSect}

\begin{defn}
Two sets $A$ and~$B$ are said to be \define[disjoint sets]{disjoint} iff their intersection is empty (that is, $A \cap B = \emptyset$). In other words, they have no elements in common: 
$$ \mbox{$A$ and~$B$ are disjoint} \quad \eiff \quad
 \begin{matrix}\mbox{there does \emph{not} exist an~$x$,}
 \\ \mbox{such that $\bigl( (x \in A) \eand (x \in B) \bigr)$} . \end{matrix} $$
We may also say that $A$ is \define[disjoint sets]{disjoint from~$B$}.
\end{defn}

\begin{eg} \ 
\begin{enumerate}
\item The sets $\{1,3,5\}$ and $\{2,4,6\}$ are disjoint, because they have no elements in common.
\item The sets $\{1,3,5\}$ and $\{2,3,4\}$ are \emph{not} disjoint, because $3$ is in their intersection.
\item The following Venn diagram illustrates two disjoint sets $A$ and~$B$ (they do not overlap):
\smallskip
\begin{center}
\includegraphics[scale=0.4]{PDF/VennDisjoint.pdf}
 \\$A$ and~$B$ are disjoint
\end{center}
\end{enumerate}
\end{eg}

\begin{rem} \label{card(DisjointUnion)Rem}
Let us point out some well-known facts that will be formally proved in \cref{CardinalityChap}.
\begin{enumerate}
\item \label{card(DisjointUnion)Rem-A+B}
 If $A$ and $B$ are two disjoint sets, then $\#(A \cup B) = \#A + \#B$.
\item \label{card(DisjointUnion)Rem-many}
 The situation is similar even if there are more than $2$ sets: Suppose $A_1,A_2,\ldots,A_n$ are \define[disjoint sets!pairwise-]{pairwise-disjoint} sets. (This means that $A_i$ is disjoint from~$A_j$ whenever $i \neq j$.) Then
	$$ \#(A_1 \cup A_2 \cup \cdots \cup A_n) = \#A_1 + \#A_2 + \cdots + \#A_n .$$
\item If $A$ and~$B$ are two finite sets that are \emph{not} disjoint, then $\#(A \cup B) < \#A + \#B$.
\end{enumerate}
\end{rem}

%\begin{warn} 
%Do not assume that a statement using the word ``and'' must refer to the intersection of two sets;
%depending on how the sentence is phrased, the union can be described by using \emph{either} the word ``or'' or the word ``and\rlap.'' Namely, both of the following refer to the union of Alice's list with Bob's list:
%\begin{itemize}
%\item A name will be on the invitation list if it is on either Alice's list \emph{or} Bob's list.
%\item The invitation list will include all of Alice's list \emph{and} all of Bob's list.
%\end{itemize}
%\end{warn}




%\begin{exers} \ 
%\begin{enumerate}
%\item Find two sets $A$ and $B$, such that $A \sm B \neq B \sm A$.
%\item Find two sets $A$ and $B$, such that $A \sm B = B \sm A$.
%\item Draw a Venn diagram of $(A \sm B) \sm (A \sm C)$.
%\item Draw a Venn diagram of $A \sm (B \sm C)$.
%\item Find three sets $A$, $B$, and~$C$, such that $(A \sm B) \sm (A \sm C) \neq A \sm (B \sm C)$.
%\item Suppose $A$, $B$, and~$C$ are sets. Show $(A \sm B) \sm (A \sm C) \subset A \sm (B \sm C)$.
%\end{enumerate}
%\end{exers}







\subsection{The power set} \label{PowerSetSect}

\begin{eg}
It is not difficult to list all of the subsets of $\{a,b,c\}$.  One way to do this is to consider the possible number of elements in the subset:
\begin{enumerate} \setcounter{enumi}{-1}
\item A subset with $0$ elements has no elements at all. It must be the empty set $\emptyset$.
\item Consider a subset with $1$ element. That one element must be one of the elements of $\{a,b,c\}$. That is, the element of the set must be $a$, $b$, or~$c$. So the 1-element subsets are $\{a\}$, $\{b\}$, and~$\{c\}$.
\item Consider the subsets with $2$ elements. 
\begin{itemize}
\item If $a$ is one of the elements in the subset, then the other element must be either $b$ or~$c$. 
\item If $a$ is not in the subset, then the subset must contain both $b$ and~$c$.
\end{itemize}
Hence, the $2$-element subsets are $\{a,b\}$, $\{a,c\}$, and $\{b,c\}$.
\item A subset with $3$ elements must have all of the elements of $\{a,b,c\}$, so the subset must be $\{a,b,c\}$.
\item[($\ge 4$)] Because $\{a,b,c\}$ has only $3$ elements, we know that no subset can have more than~$3$ elements.
\end{enumerate}
Thus, the subsets of $\{a,b,c\}$ are
$$ \emptyset, \ \{a\}, \{b\}, \{c\}, \ \{a,b\}, \{a,c\}, \{b,c\}, \ \{a,b,c\} .$$
Counting them, we see that there are exactly $8$ subsets. 
\end{eg}

\begin{rem} \label{P(A)=2^nRem}
In general, one can show that any set with $n$~elements has exactly $2^n$ subsets. In the above example, we have $n = 3$, and the number of subsets is $2^3 = 8$.
\end{rem}

\begin{exers} \label{ListSubsetsEx} 
\noneed
\begin{tasks}(2)
\task\fixtask \label{ListSubsetsEx-a} 
List the subsets of $\{a\}$.
\task\fixtask \label{ListSubsetsEx-ab} 
List the subsets of $\{a,b\}$.
\task\fixtask \label{ListSubsetsEx-abcd} 
List the subsets of $\{a,b,c,d\}$. % should we renumber to make this last !!!
\task\fixtask \label{ListSubsetsEx-0} 
List the subsets of $\emptyset$.
\end{tasks}
\end{exers}

We can make a set by putting set braces at the ends of the above list of subsets of $\{a,b,c\}$:
 $$ \bigl\{ \emptyset, \ \{a\}, \{b\}, \{c\}, \ \{b,c\}, \{a,c\}, \{a,b\}, \ \{a,b,c\} \bigr\} .$$
 In general, the set of all subsets of a set is called its \emph{power set}:
 
 \begin{defn}
 Suppose $A$ is a set. The \define{power set} of~$A$ is the set of all subsets of~$A$. It is denoted $\power(A)$.%
\nindex{$\power$}
 This means
  $$ \power(A) = \{\, B \mid B \subset A \,\} .$$
  \end{defn}

\begin{rem}
From \cref{P(A)=2^nRem}, we see that if $\#A = n$, then $\# \power(A) = 2^n$. This formula involving ``two-to-the-$n$th-\emph{power}'' can be considered a justification for calling $\power(A)$ the \emph{power} set.
\end{rem}

\begin{exers} \label{PowerSetEx} \ 
\begin{enumerate}
 \item \label{PowerSetEx-abcd}
 Describe each of the following sets by listing its elements.
\\ \noneed
 \begin{tasks}[item-indent=-1ex](3) % would like slight negative space to line up with enumii, but it doesn't work !!!
\task\fixtask \label{PowerSetEx-abcd-0}
$\power (\emptyset)$
\task\fixtask \label{PowerSetEx-abcd-a}
$\power \bigl(\{\var{a}\} \bigr)$
\task\fixtask \label{PowerSetEx-abcd-ab}
$\power \bigl(\{\var{a},\var{b}\} \bigr)$
\task\fixtask \label{PowerSetEx-abcd-abc}
$\power \bigl(\{\var{a},\var{b},\var{c}\} \bigr)$
\task\fixtask \label{PowerSetEx-abcd-abcd}
$\power \bigl(\{\var{a},\var{b},\var{c},\var{d}\} \bigr)$
\end{tasks}

\item \label{PowerSetEx-Inacd}
Which of the following are elements of $\power \bigl( \{\var{a},\var{c},\var{d}\} \bigr)$?
\\ \noneed
 \begin{multicols}{4}
\begin{enumerate}
\item \label{PowerSetEx-Inacd-a}
$\var{a}$
\item \label{PowerSetEx-Inacd-(a)}
$\{\var{a}\}$
\item \label{PowerSetEx-Inacd-(ab)}
$\{\var{a},\var{b}\}$
\item \label{PowerSetEx-Inacd-(ac)}
$\{\var{a},\var{c}\}$
\end{enumerate}
\end{multicols}

\item \label{PowerSetEx-InPower(A)}
Suppose $A$ is a set.
\begin{multicols}{2}
\begin{enumerate}
\item \label{PowerSetEx-InPower(A)-0}
Is $\emptyset \in \power(A)$? \emph{Why?}
\item \label{PowerSetEx-InPower(A)-A}
Is $A \in \power(A)$? \emph{Why?}
\end{enumerate}
\end{multicols}

\item \label{PowerSetEx-PowerIsEmpty}
Does there exist a set~$A$, such that $\power(A) = \emptyset$?

\medskip % match the spacing of the other parts of the exercise !!!

\item \label{PowerSetEx-V}
Let 
	$$ \text{$V_0 = \emptyset$,
	\quad
	$V_1 = \power(V_0)$,
	\quad
	$V_2 = \power(V_1) = \power\bigl( \power(V_0) \bigr)$,
	\quad and so forth.} $$
 In general, $V_n = \power(V_{n-1})$ whenever $n > 0$.
\begin{enumerate}
\item \label{PowerSetEx-V-card}
What are the cardinalities of $V_0$, $V_1$, $V_2$, $V_3$, $V_4$, and~$V_5$?
\item \label{PowerSetEx-V-0123}
Describe $V_0$, $V_1$, $V_2$, and~$V_3$ by listing their elements.
\item \label{PowerSetEx-V-4}
(harder) Describe $V_4$ by listing its elements.
\item \label{PowerSetEx-V-5}
Is it reasonable to ask someone to list the elements of~$V_5$? \emph{Why?}
\end{enumerate}
\end{enumerate}

\end{exers}




\begin{summary}
\item Important definitions:
\begin{itemize}
\item set
\item element %, member
%\item ordered pair
\item subset
\item proper subset
\item predicate
\item union
\item intersection
\item set difference
\item complement
\item disjoint
\item pairwise-disjoint
\item power set
\end{itemize}

\item A set is unordered and without repetition.
\item $\emptyset$ and~$A$ are subsets of~$A$.
\item $A = B$ if and only if we have both $A \subset B$ and $B \subset A$.
\item For our purposes, predicates usually have only one or two variables.  
\item If a predicate has two variables, the order of the variables is important. 
\item Venn diagrams are a tool for illustrating set operations.
\item $\#\power(A) = 2^{\#A}$
\item Notation:
\begin{itemize}
\item $\{ \ \ \  \}$
\item $\in$, $\notin$
\item $\emptyset$ (empty set)
%\item $(x,y)$ (ordered pair)
\item $\#A$
\item $A \subset B$, $A \notsubset B$, $A \supset B$
\item $P(x)$, $x \mathrel{Q} y$ \quad (predicates)
\item $\{\, a \in A \mid P(a) \,\}$
\item $\univ$ (universe of discourse)
%\item $\forall a \in A$, $\exists a \in A$, $\exists! a \in A$
\item $\natural$, $\natural^+$, $\integer$, $\rational$, $\real$
\item $A \cup B$
\item $A \cap B$
\item $A \sm B$
\item $\comp{A}$
\item $\power(A)$
\end{itemize}
\end{summary}

