SI342: Set theory introduction

What is a set

Sets are the data structures of mathematics. They give us a formal language for math that's like a programming language, but much more flexible, while still being precise. They are tremendously useful for computer scientists and the kinds of mathematics they need.

A set is a collection of objects (called elements) with two key properties: the elements are unordered within the set, and there are no duplicates. A set is often defined by listing its elements, comma-delimited, with $\{\ \}$s.

So, for example, sets $\{2,\text{rat},3/5\}$ and $\{\text{rat},3/5,2\}$ are the same, since the order of elements is not meaningful. Similarly, sets $\{\text{blue},22\}$ $\{\text{blue},22,\text{blue}\}$ are the same, since the duplicate "$\text{blue}$" element is ignored.

Important! Mathematical objects have "type", just like objects in programs, and a set is a type. So, 4 and $\{4\}$ are different! The first is the number four, and the second is the set whose only element is the number four. So "$4$" is a number and "$\{4\}$" is a set. They have different type and therefore cannot be the same. By the same reason, $\{4\}$ and $\{\{4\}\}$ are not the same. Also by the same reason, $0$ and $\emptyset$ and "" are all different, because the first is a number, the second is a set, and the third is a string.

Set basics

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\}$. The "..." means "and so on following the pattern". This gives us some flexibility!
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\}$, but $42 \notin \{1,2,3,4\}$.
Common Sets: There are certain common sets that we use all the time, and they have special symbols: $\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 $\{\ \}$, often denoted $\emptyset$, i.e. the set with no elements.
Formal Descriptions Often 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 \ \big|\ \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}\ \big|\ x \geq 0\}$. Note: read the $|$ as "such that". So we read the above as "the set of all integers $x$ such that $x \geq 0$."
Set operators — $A\cup B$, $A \cap B$, $\overline{A}$, and $A - B$:
- union: $A \cup B = \{ x \ \big|\ x \in A \vee x \in B\}$ Remember: "$\vee$" means "or"! Ex: $\{3,a,\pi\} \cup \{b,\pi,3,4\} = \{3,a,\pi,b,4\}$
- intersection: $A \cap B = \{ x \ \big|\ x \in A \wedge x \in B\}$ Remember: "$\wedge$" means "and"! Ex: $\{3,a,\pi\} \cap \{b,\pi,3,4\} = \{3,\pi\}$
- complement: $\overline{A}$ = "the complement of $A$", which is all elements from the "universe" that are not in $A$. This operation only makes sense if there is some underlying notion of "universe". Ex: If the universe is $\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\}$ then $\overline{\{\diamondsuit,\heartsuit\}} = \{\clubsuit,\spadesuit\}$
- difference: $A - B = \{ x \ \big|\ x \in A \wedge x \notin B\}$ Ex: $\{3,a,\pi\} - \{b,\pi,3,4\} = \{a\}$
Note: If $A$ is a set with a finite number $n$ of elements, we say that the cardinality of $A$, written $|A|$ is $n$.
Subsets "$A$ is a subset of $B$" means that every element of $A$ is also an element of $B$. So, for example, $\{2,4\}$ is a subset of $\{1,2,3,4\}$, though the other way round doesn't work!
Important! is $\emptyset$ a subset of $\{1,2,3,4\}$? Yes! Think like a mid trying to get out of trouble: can you show me a single element of $\emptyset$ that isn't in $\{1,2,3,4\}$? Nope! Therefore $\emptyset$ must be a subset of $\{1,2,3,4\}$! In fact, for any set $A$, we have $emptyset$ is a subset of $A$. Also note that every set is a subset of itself.
We have nice notations for subset related stuff: $A \subseteq B$ means that $A$ is a subset of $B$. $A \subset B$ means that $A$ is a 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\} \}$.
Cartesian Product $\times$: One of the most important operations on sets is the ``Cartesian Product'', which produces the set of all possible pairs of elements from two sets — i.e. all possible ordered pairs whose first component comes from the first set, and second component comes from the second set. 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! For example, $$\{foo,bar\}\times\{0,1,2\} = \{(foo,0),(bar,0),(foo,1),(bar,1),(foo,2),(bar,2)\}$$ Thus, we compose objects in set theory 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$.
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 $|A| = \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$.
Quantification over the elements of sets: We will be using the quantifiers $\exists$ (there exists) and $\forall$ (for all) a lot in this class. With sets we can restrict the universe from which these quantifiers consider objects. For example, $\forall x \in \mathbb{N}[ x + 1 \gt 0]$ means "for all natural numbers $x$, it holds that $x + 1 \gt 0$", which is (of course) a true statement. However, $\forall x \in \mathbb{Z}[ x + 1 \gt 0]$ is not true. Can you find a counterexample? I.e. a value for $x$ that shows that the formula is not true?

ACTIVITY - Set stuff

Break up into groups of three

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 $U = \{\ a,\ \{a\},\ \{\ \}\ \}$. Write out all the subsets of $U$. Hint: there are eight subsets. Why? $|U|=3$ and for each of the three elements you have two choices: put the element in the subset, or leave it out. This gives $2\cdot 2\cdot 2 = 8$ possible outcomes.
Let $W$ be a set. Is it possible for some $X$ to be both an element of $W$ and a subset of $W$? I.e. is it possible for $X\in W$ and $X \subseteq W$ to both be true?
Let $A = \{1,2,3\}$. Write out the elements of $A\times A$.
Let $A = \{1,2,3\}$. Write out the elements of $\{(u,v) \in A \times A\ \big|\ u + v = 4\ \}$.
Write out the elements of $\{x \in \mathbb{R}\ \big|\ x^2 + x - 1 = 0 \}$
Write out the elements of $\{ x \in \{0,1,\ldots,40\}\ \big|\ \exists y \in \mathbb{N} [\ y^2 = x\ ] \}$
If $\Sigma$ is an alphabet, we denote the set of all strings over $\Sigma$ as $\Sigma^*$. Given alphabet $\Sigma$, give a short english description of the set $\{w\in\Sigma^*\ \big|\ w = w^R\}$.
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. Note: A SS& like 123-45-6789 should be represented as $(123,45,6789)$.
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}\ \big|\ i = xy \mbox{ for some $y \in \mathbb{N}$} \} $$ Give a (short!) english language description of the set: $$P = \{i \in \mathbb{N}\ \big|\ |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$.

Functions!

Functions are hugely important in mathematics and computer science. You know them from math classes, you know them from programming, and you know them from first-order logic. So what are functions from the perspective of set theory? Informally, a function maps an input, which is an element of the function's domain, to an output, which is an element of the function's codomain. The rules are:

for any input $x$ in the domain, the function must produce an output $y$ from the the codmain, and
every time the function is applied to input $x$ it must produce the same output $y$.

Let $A$ and $B$ be sets, and let $f \subseteq A \times B$. $f$ is a function from domain $A$ to codomain $B$ if

$\forall x \in A\left[ \exists y \in B [ (x,y) \in f ]\right]$, and
$\forall x, y, y'[ (x,y)\in f \wedge (x,y') \in f \Longrightarrow y = y' ]$.

For notation, we write $f:A\rightarrow B$ to indicate that $f$ is a function from $A$ to $B$ (this called the function's signature), and we write $f(x) = y$ to indicate that $(x,y) \in f$. [Note that the order of $x$ and $y$ matters!]

Examples:

$f_1 := \{ (0,b),(1,c),(2,b),(3,a) \}$ is a function, with $f_1:\{0,1,2,3\} \rightarrow \{a,b,c\}$.
$f_2 := \{ (0,b),(1,c),(1,b),(2,a) \}$ is not a function, since "$(1,c)$" and "$(1,b)$" violate point (2) of the definition, because there are multiple outputs for the same input.
If $f_3 := \{ (0,b),(1,c),(3,a) \}$, it is not the case that $f_3:\{0,1,2,3\} \rightarrow \{a,b,c\}$, because there is no output for $f_3(2)$, which violates point (1) of the definition.
If $f_4 := \{ (0,b),(1,a),(2,b),(3,a) \}$, it is correct to say $f_4:\{0,1,2,3\} \rightarrow \{a,b,c\}$ even though $c$ is never an output value, because it is not required that every element of the codomain is the output of some input.
Note: the range of a function is the set of all output values that actually appear.

Ways we define particular functions

We see from the definition that we can always define a particular function by describing the set of input/output pairs. That's good to keep in mind, and in many cases that's what we do. There are two other common ways for us to define particular functions:

Define a function by a signature plus a rule for computing values
For example:

$$ \begin{array}{l} sqr:\mathbb{R}\rightarrow\mathbb{R}\\ sqr(x) = x\cdot x \end{array} $$

$$ \begin{array}{l} sqrt:\{x \in \mathbb{R}\ \big|\ x \geq 0\} \rightarrow\mathbb{R}\\ sqrt(x) = y,\text{ where } sqr(y) = x \wedge y \geq 0 \end{array} $$

$$ \begin{array}{l} floor: \mathbb{R} \rightarrow \mathbb{Z}\\ floor(x) = y, \text{ where } y\leq x \wedge x < y + 1 \end{array} $$

Often we need to break the rule into different cases, which we do by listing the output expressions along with conditions on the input for which the output expressions apply. for example:

$$ \begin{array}{l} abs:\mathbb{R}\rightarrow\mathbb{R}\\ abs(x) = \left\{ \begin{array}{cl} x & \text{ if } x \geq 0\\ -x & \text{ otherwise} \end{array} \right. \end{array} $$

$$ \begin{array}{l} sqrt^*: \mathbb{R} \rightarrow \mathbb{C}\\ sqrt^*(x) = \left\{ \begin{array}{cl} sqrt(x) & \text{ if } x \geq 0\\ i\cdot sqrt(abs(x)) & \text{ otherwise} \end{array} \right. \end{array} $$

Important! Functions in mathematics are really a lot like programming functions in a language like C or C++. The signature + rule is analogous to a C/C++ prototype plus function definition. The difference is, in mathematics you are almost completely unconstrained in how you describe the "rule" for the function. Anything that another mathematician can follow unambiguously is pretty much of. For example: $$ \begin{array}{l} f: \mathbb{Z}_+ \rightarrow \mathbb{N}, \text{ where $\mathbb{Z}_+$ means the positive integers}\\ f(n) = \text{ the number of distinct prime factors of $n$} \end{array} $$ That is totally OK, even though I haven't really told you how to compute it. From this it's clear that $f(12) = 2$, because 2 and 3 are the only prime factors of 12.

Important! Functions of multiple inputs just have domains defined by cartesian products
For functions that take multiple inputs, perhaps even of different types, we use cartesian product. So, in some sense, there is always only one input, it is just that the input may be a tuple:
We can define the "divides" predicate like this: $$ \begin{array}{l} \text{divides}:\mathbb{N}\times\mathbb{N} \rightarrow \{true,false\}\\ \text{divides}(a,b) = \exists k\in\mathbb{N}[a\cdot k = b] \end{array} $$

Here's a nice example that uses everything we've talked about and ... is recursive! $$ \begin{array}{l} \text{pow}:\mathbb{R}\times\mathbb{N} \rightarrow \mathbb{R}\\ \text{pow}(x,k) = \left\{ \begin{array}{cl} 1 & \text{ if }k = 0\\ x\cdot\text{pow}(x,k-1) & \text{ otherwise} \end{array} \right. \end{array} $$

Finite functions can be described by a table.
We saw this over an over again in SI242, with boolean functions and the addition and multiplication functions defined for the integers mod $n$.

Addition function for $\mathbb{Z_3}$	a "GPA" function
$$ \begin{array}{l} +:\mathbb{Z_3}\times\mathbb{Z_3}\rightarrow\mathbb{Z_3}\\ \begin{array}{c\|ccc} +&0&1&2\\ \hline 0&0&1&2\\ 1&1&2&0\\ 2&2&0&1\\ \end{array} \end{array} $$	$$ \begin{array}{l} \text{GPA}:\{A,B,C,D,F\}\rightarrow\mathbb{R}\\ \begin{array}{ccccc} A&B&C&D&F\\ \hline 4.0&3.0&2.0&1.0&0.0\\ \end{array} \end{array} $$

ACTIVITY

Given the definition below, what are the values of: $q(2.3,true)$, $q(-2.3,true)$, $q(2.3,false)$, $q(-2.3,false)$? $$ \begin{array}{l} q:\mathbb{R}\times \{true,false\}\rightarrow \mathbb{Z}\\ q(x,b) = \left\{ \begin{array}{cl} \lfloor x \rfloor & \text{ if } x \geq 0 \wedge \neg b \vee x \lt 0 \wedge b\\ \lceil x \rceil & \text{ otherwise} \end{array} \right. \end{array} $$
Give a formal definition of the function mid that takes two real numbers and returns the midpoint between them.
Give a formal definition of the function dist that takes two real numbers and returns the distance between them. Note: find a way to do it without using the absolute value function!
Let $A = \{ \text{rock}, \text{paper}, \text{scissors} \}$. Use a table to define the $beats(\cdot,\cdot)$ function, which returns true if and only if the first argument beats the second in rock/paper/scissors. For example, $beats(\text{paper},\text{scissors})=\text{false}$ because paper does not beat scissors.
Consider the function $m$ defined below. $m(3) = $_____________________________________ $$ \begin{array}{l} m:\mathbb{N}\rightarrow2^{\mathbb{N}}\\ m(k) = \{ i\cdot k\ \big|\ i \in \mathbb{N} \} \end{array} $$

Reading

Warning!

What is a set

Set basics

ACTIVITY - Set stuff

Functions!

Ways we define particular functions

Relations