**Definitions:**Defining a set by listing its elements or giving an informal description. Ex: $A = \{17,2.5,-8\}$ or $B = \{3,5,7,\ldots\}$.**Element $\in$**A set consists of elements, and we write ``$a$ is an element of set $A$'' as $a \in A$. Ex: $3 \in \{1,2,3,4,5,6,7,8,9\}$.**Common Sets**There are certain common sets that we use all the time, and they have special sybmols: $\mathbb{N}$ --- the natural numbers (i.e. non-negative integers), $\mathbb{Z}$ --- the integers, and $\mathbb{R}$ --- the real numbers. Finally, we have the ever popular empty set, $\emptyset$.**Formal Descriptions**Usually we won't define a set by explicitly listing all of its elements --- after all this isn't possible for infinite sets! Instead we write $\{x \in A| \mbox{$x$ has property $P$}\}$ to mean the set of all elements of $A$ that satisfy some property $P$. For example, we could define $\mathbb{N}$ as $\{x \in \mathbb{Z}| x \geq 0\}$.**Cartesian Product $\times$**One of the most important operations on sets is the ``Cartesian Product'', which pairs elements from two sets to create composite objects. Ex: $\mathbb{R} \times \mathbb{R}$ is the set of all ordered pairs of real numbers, i.e. the set of points in the plane! Thus, we compose objects in set theory \textbf{just like we compose objects in class definitions in C++!!!} We use $A^k$ to indicate $A \times A \times \cdots \times A$, $k$-times over. So, for example, 3-diomensional space is $\mathbb{R}^3$.**$\cup$,$\cap$,', and $-$****Subsets**You should know what a subset is. $A \subseteq B$ means that $A$ is a subset of $B$. $A \subset B$ means that $A$ is a \emph{proper} subset of $B$, i.e. $A \neq B$. Ex: $\mathbb{Z} \subset \mathbb{R}$. If $A$ is a set, we denote by $2^A$ the set of all subsets of $A$. Ex: If $A = \{1,2,3\}$, then $2^A = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,3\}, \{1,2,3\} \}$.**Operations Over Sets**Many operations in mathematics are defined ``over a set''. For example, if $A = \{1,7,3,5,2\}$ we write $\sum_{x \in A} x^2$ to mean $1^2 + 7^2 + 3^2 + 5^2 + 2^2$. Also, we write $min(A)$ to be the smallest element of $A$. Notice how both of these expressions only make sense because the elments of $A$ are numbers ... after all, if $A$ consisted of characters, then ``$+$'' wouldn't make a lot of sense, or if $A$ was a set of people then ``smallest'' wouldn't make a lot of sense. This is just like C++, where operations (like $+$) only make sense for certain classes. These kinds of operations over sets are like programming, acutally. For example, the cardinality of a set $A$ (denoted $|A|$) can be defined as $\sum_{x \in A}1$, which is a lot likeint cardinality(set A) { k = 0; for each x in A do k++; return k; }

**Unions and Intersections of Many Sets**Suppose we have $n$ sets $A_1,\ldots, A_n$. We often write $\bigcup_{i=1}^n A_i$ or $\bigcap_{i=1}^n A_i$ to denote the union or intersection of all of the $A_i$'s. Sometimes we take the union or intersection of an infinite number of objects. For example, let $B_i$ be the set of strings of zeros and ones of length $i$ and with first character one. Then the set of valid representations of binary numbers (so we are not allowing leading zeros here!) is $\{0\} \cup \bigcup_{i=1}^\infty B_i$.

- Let $A = \{x1, x3, x5, \ldots\}$. Give an element of $A$ other than $x1$, $x3$, and $x5$.
- Let $B = \{\{0\},\{1\},\{2\}\}$. True or false, the elements of $B$ are numbers.
- Let $C = \{\{\},\{a\},\{\{b\}\},\{c\}\}$. Explicitly list the elements of the set $\{x|\mbox{ there is a $y \in C$ such that $x \in y$}\}$.
- Let $F = \{0,5,10,15,20,25,\ldots, 50000\}$. Give a formal definition of $F$ without using ``$\ldots$''.
- Give a formal definition of the set of perfect squares.
- Let $D_i$ be the set of $i$-digit decimal natural numbers. Give a definition of the set of all social security numbers in terms of the $D_i$'s.
- Let $V$ be the set of vertices in a directed graph in which each edge is assigned a real number as a weight. Give a definition of the set of all possible edges in the graph. Remember: an edge is defined by the source and destination vertices, as well as the edge weight. Note: This is analogous to the definition of an \texttt{Edge} class in C++. What data elements would such a class contain?
- Let $A$ be a finte subset of $\mathbb{R}$. Give an expression for the average of the elements of $A$.
- Let $D_i$, where $i \in \mathbb{N}$ be defined as: $$ D_i = \{x \in \mathbb{N} | i = xy \mbox{ for some $y \in \mathbb{N}$} \} $$ Give a (short!) english language description of the set: $$P = \{i \in \mathbb{N}\ |\ |D_i| = 2\}$$ (Hint: Start by asking questions like this: Is 12 in $P$? Is 13 in $P$?) Note: This definition of the set $P$ is a lot like a computer program. I define a ``subroutine'' called ``$D_i$'' and use it in my ``main program'', which is the definition of $P$.