Below is some summary information on sets. You will be covering (or have covered) sets in Discrete Math, so this is just meant as a summary for folks that already have seen this material.

## Sets

• 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 SetsThere 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 $-$
• SubsetsYou 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 like
int 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$.

## Problems on sets

1. Let $A = \{x1, x3, x5, \ldots\}$. Give an element of $A$ other than $x1$, $x3$, and $x5$.
2. Let $B = \{\{0\},\{1\},\{2\}\}$. True or false, the elements of $B$ are numbers.
3. 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$}\}$.
4. Let $F = \{0,5,10,15,20,25,\ldots, 50000\}$. Give a formal definition of $F$ without using $\ldots$''.
5. Give a formal definition of the set of perfect squares.
6. 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.
7. 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?
8. Let $A$ be a finte subset of $\mathbb{R}$. Give an expression for the average of the elements of $A$.
9. 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$.