\documentclass[11pt]{article}

\usepackage{precalc}
\usepackage{fancyvrb}

\begin{document}

\VerbatimFootnotes

\assigntitle{1}{\LaTeX\ and Set Theory}

\section{\LaTeX}

The first part of your assignment this week is to become familiar with
\LaTeX, which is the primary system we will be using to communicate.
The accompanying \LaTeX\ tutorial will guide you through the process
of installing it on your computer, and show you the basics of how to
prepare a document in \LaTeX\ format.

\section{Set Theory}

\topic{These marginal notes name the topic
  being discussed to their right; they are to help you find things
  when you refer back to these notes later.}
The second part of your assignment is a basic introduction to set
theory. You should make a copy of \texttt{solution-template.tex},
rename it to something like \texttt{01-set-theory-solutions.tex}, and
fill it in with your solutions, using the sample solution
(\texttt{solution-example.tex}) and the \LaTeX\ tutorial as guides.
Be sure to also read the expectations outlined in the syllabus.  When
you are done, you should turn in the \texttt{.tex} file with your
solutions, along with the generated PDF file.

\subsection{Definitions}

\begin{defn}{set}
A \term{set} is a collection of objects, which are called 
\term{elements}.  The order of the elements does not matter, and each
element may occur no more than once.
\end{defn}

\topic{set examples}
For example, $\{1,2,5\}$ denotes a set with three elements: $1$, $2$,
and $5$.  $\{2,5,1\}$ is the same set, since the order of the elements
does not matter.  $\{2,2,2\}$ is not a valid set, because the element
$2$ occurs more than once.  Note that the elements of a set do not
have to be numbers; they could be any sort of object, like people,
types of cheese, triangles, binary operations, or even other sets.

\begin{problem}
  Which of the following are valid sets?
  \begin{subproblems}
    \item $\{5,4,3,1\}$
    \item $\{2,5,7,2\}$
    \item $\{\{2,5,1\},\{2,5\},\{2\}\}$
    \item $\{\{\{\pi\}\}\}$
  \end{subproblems}
\end{problem}

\subsection{Notation}

\topic{set notation}
As seen above, one way to describe a set is to literally list its
elements and place them in curly braces, like this: $\{ 1, 3, 69
\}$. (Remember that because curly braces have special meaning to
\LaTeX, you will have to put backslashes in front of them.)

\topic{special sets: $\emptyset$, $\N$, $\Z$, $\Q$, $\R$, $\C$} 
There are also some important sets which have
special notation.  Here are a few:
\begin{itemize}
\item $\emptyset$ denotes the empty set---the unique set which
  contains no elements.  Sometimes it is also written $\{\}$.
\item $\N$ stands for the set of all natural numbers, that is, $\N =
  \{0, 1, 2, 3, \dots\}$.
\item $\Z$ stands for the set of all integers, that is, $\Z = \{\dots,
  -2, -1, 0, 1, 2, \dots\}$.
\item $\Q$, $\R$, and $\C$ stand for the set of all rational numbers,
  all real numbers, and all complex numbers, respectively.
\end{itemize}

\begin{problem}
  Are $\emptyset$ and $\{\emptyset\}$ the same?  If not, what is the
  difference?
\end{problem}

\begin{problem}
  Let $S_0$ denote the empty set, and define $S_n$ (for any positive
  integer $n$) to be the set $\{S_0, S_1, \dots, S_{n-1}\}$.  For
  example, $S_1 = \{S_0\} = \{\emptyset\}$, and $S_2 = \{S_0, S_1\} =
  \{\emptyset, \{\emptyset\}\}$.  Write
  out $S_4$.\footnote{Believe it or not, this is actually a common way
    to \emph{formally} define the natural numbers using nothing other
    than set theory!}
\end{problem}

\topic{$\in$, ``element of''}
To specify that something is an element of a particular set, use the
$\in$ symbol.  For example, $a \in \Z$ means that $a$ is an integer.
$y \in \{0,1\}$ means that $y$ is either zero or one.  It is common to
write several things in front of $\in$ separated by commas; for
example, $a,b,c \in \Z$ means that $a$, $b$, and $c$ are all
integers. To say that something is \emph{not} an element of a set, you
can use the symbol $\not \in$, just like you use $\neq$ to indicate
that two things are not equal.

\begin{problem}
  Which of the following statements are true, and which are false?
  \begin{subproblems}
    \item $2 \in \{2,5,7\}$
    \item $3 \not \in \Z$
    \item $9.4 \not \in \Z$
    \item $\{2\} \in \{2,5,7\}$
    \item $3 \in \{\{1\}, \{2\}, \{3\}\}$
    \item $\{2,5\} \not \in \{\{6,7\}, \{2,5,1\}\}$
    \item $\emptyset \in \{5, \varphi, \emptyset\}$
  \end{subproblems}
\end{problem}



\topic{such-that notation} 
Another way to describe a set is using so-called ``such-that''
notation.  The notation \[ \{ P \suchthat Q \}, \] read ``$P$ such
that $Q$,'' denotes the set of all values of $P$ for which $Q$ is
true.  For example, \[ \{ x \suchthat x \in \Q \text{ and } x > 6 \}
\] denotes the set of all rational numbers greater than 6. As another
example, \[ \{ x^2 \suchthat x \in \Z \} \] denotes the set of all
perfect squares. As a third example, $\Q$ can be defined this way: \[
\Q = \left\{ p/q \suchthat p,q \in Z \text{ and } q \neq 0
\right\}. \]

\topic{interval notation} Yet another way to describe certain special
sets is \term{interval} notation.  It's possible you've seen this
notation before.  In particular, \[ [a,b] \] denotes the set of all
\emph{real} numbers between $a$ and $b$ (inclusive).  In other words,
\[ [a,b] = \{ x \suchthat x \in \R, x \geq a, x \leq b \}. \] (Note
that using commas as above is a common shorthand for ``and,''
\emph{i.e.} we write `$x \in \R, x \geq a$' instead of `$x \in \R \text{
  and } x \geq a$,' and so on.) The square brackets around $[a,b]$
indicate that both endpoints are included in the set; parentheses
indicate that one or both endpoints are not included.  For example,
$(3,5]$ is the set of all real numbers which are \emph{greater than}
(but not equal to) $3$, and less than or equal to $5$.  Likewise,
$[3,5)$ indicates that $3$ is included but not $5$; $(3,5)$ indicates
that neither endpoint is included.

If one end of an interval has no endpoint, we write $-\infty$ or
$\infty$ enclosed in a parenthesis.  For example, $(-\infty, 6]$ is
the set of all real numbers less than or equal to $6$.


\subsection{Set operations}

There are a few fundamental operations we can perform on sets.

\topic{union, $\union$}
The \term{union} of two sets, denoted $S \union T$, is the set which
contains all the elements of $S$ and all the elements of $T$.  For
example, $\{1,2,3\} \union \{3,4,5\} = \{1,2,3,4,5\}$.  Notice that it
is OK for $S$ and $T$ to overlap; their union only contains one copy
of each element, even if it occurs in both $S$ and $T$.

\topic{intersection, $\intersect$}
The \term{intersection} of two sets, denoted $S \intersect T$, is the
set which contains all the elements which are in \emph{both} $S$ and
$T$. For example, $\{1,2,3\} \intersect \{3,4,5\} = \{3\}$.

\topic{difference, $\setminus$}
The \term{difference} of two sets, denoted $S \setminus T$ (also
sometimes $S - T$), is the set which contains all the elements which
occur in $S$ but not in $T$.  For example, $\{1,2,3\} \setminus
\{3,4,5\} = \{1,2\}$.

\topic{complement, $\overline{S}$} The \term{complement} of a set,
denoted $\overline{S}$, is the set which contains everything which is
\emph{not} an element of $S$.  This only makes sense with respect to
some ``universal set'' of all objects under consideration (sometimes
called the ``universe of discourse''), which is usually clear from
context.  For example, it's nonsensical (or at least, not very useful)
to say that $\overline{\{2\}}$ is the set which contains ``everything
except $2$'', including $6$, $97.3$, Archimedes, the Leaning Tower of
Pisa, dirty socks\dots Rather, we would say that, with respect to the
integers, for example, $\overline{\{2\}}$ contains all integers except
$2$; with respect to the universal set $\{1,2,3\}$, the complement of
$\{2\}$ is $\{1,3\}$, and so on.  Another way to say this is that if
$U$ is the universal set, then $\overline{S} = U \setminus S$.

\topic{cardinality, $|S|$}
Finally, the \term{cardinality}, or size, of a set is simply the number of
elements it contains.  The cardinality of $S$ is usually denoted $|S|$
(or sometimes $\#S$).  For example, $|\{2,4,6,7\}| = 4$.  Of course,
this definition breaks down when we start talking about infinite
sets---for example, what is $|\Z|$?  We'll explore the cardinality of
infinite sets in a few weeks.

\begin{problem}
  \begin{subproblems}
    \item What is $[1,5) \intersect [2,6)$?
    \item Is $2 \in (-\infty, 0) \union [1/2, 3) \union (9, 12]$?
    \item What is $\overline{(-\infty, 0) \union [1/2, 3) \union (9, 12]}$?
  \end{subproblems}
\end{problem}

For problems~\ref{prob:set-compute}--\ref{prob:set-construct}, assume
that the following sets are defined.  All set complement operations
are with respect to the universal set $\Q$.
\begin{align*}
  A &= \{1,2,3\} \\
  B &= \{0,5,3,8,1\} \\
  C &= \{1,7,9,3\} \\
  D &= \overline{\{1/2, 3/4, 5/7\}}  \\
  E &= \{x^2 \suchthat x \in \Z\} \\
  F &= \{p/(2^q) \suchthat p \in \Z \text{ and } q \in \N \} \\
  G &= \{|A|, |B|, |C|\}
\end{align*}

\begin{problem} \label{prob:set-compute}
  List the elements of each of the following sets, or describe them if
  there are an infinite number of elements.

  \begin{subproblems}
  \item $A \union B$
  \item $A \intersect C$
  \item $\overline{D} \intersect F$
  \item $A \union (E \intersect C)$
  \item $B \setminus G$
  \end{subproblems}
\end{problem}

\begin{problem} \label{prob:set-construct}
  For each set, write down an expression which is equal to it, using
  only the sets $A$ through $G$ defined above and the set operations.

  \begin{subproblems}
  \item $\{3,1,9,7,5,4\}$
  \item $\{1\}$
  \item $\{5/7\}$
  \item $\emptyset$
  \end{subproblems}
\end{problem}

\begin{problem}
  Explain why, for any sets $A$ and $B$, it is always true that
  $\overline{A \union B} = \overline{A} \intersect \overline{B}$.
\end{problem}

\begin{problem}
  Is it also always true that $\overline{A \intersect B} =
  \overline{A} \union \overline{B}$?  If so, explain why; if not, give
  a counterexample (particular sets $A$ and $B$ for which it is not
  true).
\end{problem}

\begin{problem} 
  Which set has more elements: the set of all integers, or the set of
  all even integers?  Does it even make sense to ask this question?
  Justify your answers.  Note that I don't care if you get this
  question ``right'' (we'll talk about the ``right'' answer in a few
  weeks) but just for you to think about it carefully.
\end{problem}

\section{Set notation and \LaTeX}
\label{sec:set-notation-latex}

You can, of course, look at the \LaTeX\ file for this assignment to
see commands used to produce special set-related symbols.  However,
for your convenience I have provided
Table~\ref{tab:set-notation-latex} as a reference.


\begin{table}[htp]
\begin{center}
\begin{tabular}{c|c}
  Symbol & command \\
  \hline \\
  
  $\{$   & \verb|\{| \\
  $\suchthat$ & \verb|\mid|, \verb|\suchthat| \\
  $\}$   & \verb|\}| \\
  $\in$  & \verb|\in| \\
  $\not \in$ & \verb|\not \in| \\
  $\emptyset$ & \verb|\emptyset| \\
  $\N$   & \verb|\N| \\
  $\Z$   & \verb|\Z| \\
  $\Q$   & \verb|\Q| \\
  $\R$   & \verb|\R| \\
  $\C$   & \verb|\C| \\
  $\union$ & \verb|\cup|, \verb|\union| \\
  $\intersect$ & \verb|\cap|, \verb|\intersect| \\
  $\setminus$ & \verb|\setminus| \\
  $\overline{S}$ & \verb|\overline{S}| \\
  $\infty$ & \verb|\infty| 
\end{tabular}
\end{center}
\caption{\LaTeX\ commands for set-related symbols.
  \label{tab:set-notation-latex}}
\end{table}

\verb|\mid|, \verb|\cup| and \verb|\cap| are standard \LaTeX\
commands, for which I have provided the easier-to-remember aliases
\verb|\suchthat|, \verb|\union| and \verb|\intersect|, respectively,
in \texttt{precalc.sty}.  Feel free to use either, or to define your
own aliases using \verb|\newcommand|.  I have also provided \verb|\N|
and company as aliases for \verb|\mathbb{N}| and so on, which typesets
the characters using the special double-stroked ``blackboard bold''
font which is commonly used for these symbols.

\end{document}