
\subsection{Definitions}

A \emph{set} is a collection of objects (Collection, object are
undefined terms)\.

The order of elements is not important\. I.e., the sets 
$\{1,2\}$ and $\{2,1\}$ are considered the same set\.
Each element is included only once\. So, if we write
$\{a,b\}$ or $\{a,a,b\}$ they both denote the same set
and the element $a$ is considered to be present in the set 
only once. (repeating an element in the description of 
a set may be useful sometimes)\.

Here are some examples of sets: 
\begin{itemize}
\item $\{1,2,3\}$.  This is a simple finite set, obtained by
  enumerating all the elements.
\item $\emptyset$, the \emph{empty set}.  A special case of a finite
  set, with \emph{no} elements.
\item $\{\emptyset\}$.  This funny set is different from $\emptyset$\.
  It has one element, which is a set.
\item $\{1,\{1,2\}\}$.  This one contains two elements, one of which
  is a set itself\.  The set happens to contain the other element $1$,
  but that does not contradict the condition that an element is
  included only once.
\item $\{n\in \naturals \given n \hbox{ is even }\}$.  This is an
  infinite set, specified by giving a universal set (domain of
  discourse) and a property\.  In general, given a domain of discourse
  $D$ and a predicate $P$ over $D$, $\{x\in D \mid P(x)\}$ denotes the
  set of all $x$ in $D$ that satisfy predicate $P$.
\end{itemize} 
We write that $a\in A$ (``$a$ is in $A$'' or ``$a$ is an element of
$A$'') if $a$ is an object in the set $A$\.  The empty set satisfies
the proposition $(\forall x) x \notin \emptyset$\.

Sets can be defined by axioms and deduction rules, giving a very
formal \emph{axiomatic set theory}\.
But usually, people reason about sets less formally, using \emph{naive
set theory}\.
Either way, set theory can be used as the basis for defining almost
everything else in mathematics and is therefore
regarded as the most fundamental part of math\.

In fact natural numbers can be defined as certain kinds of sets (!)\.
For example we can represent the number $0$ by the empty set $\emptyset$,  
number $1$ by the set $\{\emptyset\}$, number $2$
by $\{\emptyset,\{\emptyset\}\}$, and so on.
In general, if $S_n$ is the set representing the number $n$,
the successor of $n$ can be represented by the set
$S_{n+1} = \{\emptyset\}\cup \{\{x\}\mid x\in S_n\}$.
Then the properties natural numbers can be \emph{proved as
theorems} of set theory, 
rather than being assumed\.

The axioms of set theory seem ridiculously obvious but aren't\.  Here
are some examples:
\begin{itemize}
\item The \emph{axiom of extensionality} says that two sets are equal
  if and only if they have the same elements\.  For example, the two
  sets $\{n\in \naturals \given \mbox{$2$ divides $n$}\}$ and $\{2n
  \mid n \in \naturals\}$ are defined in different ways\.  But they
  are ``equal'' as sets because they have exactly the same elements\.
\item The \emph{axiom of comprehension} says that we can form a new
  set by including all objects of a given set that share a common
  property\.  For example, $\{x \in \reals \given P(x)\}$ where
  $P(x)=\mbox{``x is rational''}$ denotes the set of all rational
  numbers. The axioms says that this is a set\.
\end{itemize}
The set building notation that we used above has given the universe of
discourse explicitly\.  Sometimes, when this seems obvious, we will
leave this out\.  Just like what we did for predicate quantifiers\.
E.g., we might write: $\{n \mid \mbox{$n$ is even}\}$ if the universe
$\naturals$ seems clear\.  (This \emph{could} be confusing---the
universe could alternatively be the integers, positive and negative.)
\begin{definition}
  We say that $A\subseteq B$ (``$A$ is a subset of $B$'' or 
  ``$A$ is contained in $B$'') if every
  element of $A$ is also an element of $B$ (that is, $(\forall x)(x\in
  A \implies x \in B)$).
\end{definition}
\begin{definition}
  We say that $A$ is a \emph{proper} subset of $B$
  ($A\subset B$) if $A\subseteq B$ and $A\neq B$.
\end{definition}
Note that $(\forall X) \emptyset \subseteq X$, i.e. the empty set 
is contained in any other set\.
\begin{example}
  Can we have both $A\in B$ and $A\subseteq B$? Yes, consider $\{ 1,
  \{ 1 \} \}$.
\end{example}
\begin{theorem}
  $A=B$ if and only if $A \subseteq B$ and $B \subseteq A$.
\end{theorem}
The proof is by the axiom of extensionality.  But we won't bother
giving it\.
This observation is very important as it provides a simple way to
prove that 2 sets are equal\.
\begin{example}
  Prove that the two sets $\{n\in \naturals \given \mbox{$2$ divides
    $n$}\}$ and $\{2n \mid n \in \naturals\}$ are equal.
  \begin{proof}
    We must show containment in both directions.
    
    $\subseteq$: We assume $x \in \naturals$ and $2 \mbox{ divides }
    n$, and show that there is some $y \in \naturals$ such that $x =
    2y$\.  This is true by definition of divisibility.
    
    $\supseteq$: Assume $x = 2y$.  Then $x$ is divisible by $2$, again
    by the definition of divisibility.
  \end{proof}
\end{example}
Here's a slightly more interesting one:
\begin{example}
  The set of evens $\geq 2$, i.e., $\{ 2n \mid n \in \naturals, n \geq
  1 \}$, is equal to $\{x \in \naturals \mid \exists y, z \mbox{ odd},
  x = y + z \}$.
  \begin{proof}
    Again, we have to show containment in both directions.
    
    $\subseteq$: If $x = 2n$, then write $x = 1 + (x - 1)$, sum of two
    odds.
    
    $\supseteq$: If $x = y + z$, where both $y$ and $z$ are odd, then
    write $y = 2a + 1$, $z = 2b + 1$\.  Then $x = 2(a+b+1)$, which is
    even.
  \end{proof}
\end{example}
The size of a set $A$ (the number of elements it contains) is written
$|A|$\.  
For example, the set $\{a,b,c\}$ has size 
$|\{a,b,c\}|=3$\. The empty set has size 
$|\emptyset|=0$\.
The size of a finite set is a natural number\.
Notice that for any two finite sets $A,B$, we have 
$|A\cup B| \leq |A|+|B|$\. Equality holds if and only if 
$A\cap B=\emptyset$\.

