# Sets

Starting from this section, we will describe a few common mathematical terms that we’ll need. You’ll probably be familiar with most of these, but please read on anyway. We begin with sets.

Important: When reading these, you don’t need to memorize the terms. We won’t give you an exam about them. Instead, we want you to really understand them. If you encounter a term again in a later chapter but forgot what it means, you can simply refer back to this page. No penalties for that!

Anyway, what is a set? You can think of a set as just a collection of objects, such as physical objects, numbers, and even other sets.

To write a set, we simply list the elements together, separate them with commas, and enclose them with curly brackets. For example, the set $\{1, 2.35, 11\}$ is a set containing exactly three elements (or members): the numbers $1$, $2.35$ and $11$. Also, the set $\{0, \{0, 1, \{2, 3\}\}\}$ contains exactly two elements: the number $0$ and the set $\{0, 1, \{2, 3\}\}$. Note that:

• The order you list the elements doesn’t matter. For example, $\{1, 2.35, 11\}$ and $\{11, 1, 2.35\}$ are the same sets.
• It doesn’t matter how many times you write an element. For example, $\{1, 2\}$ and $\{1, 1, 2, 1, 1, 1\}$ are the same sets. (If we want collections where repetitions matter, we use multisets.)

There’s another way of writing sets, and that is by specifying the properties that the members of the set must have. For example, an alternative way of writing $\{1, 2, 3, 4, 5\}$ is $\{x : \text{$x$is an integer and$1 \le x \le 5$}\}$. You can read this notation as “The set of all $x$ such that $x$ is an integer and $1 \le x \le 5$”, which is obviously the same as $\{1, 2, 3, 4, 5\}$. There are other similar notations, and I bet you can figure out how they work:

• $\{x^2 : x \in \mathbb{Z}\}$ denotes the set of all perfect squares. ($\mathbb{Z}$ is the standard notation for the set of integers.)
• $\{x \in \mathbb{Z} : x < 0\}$ denotes the set of all negative integers.

## Comparisons of sets

Two sets are equal if they contain the same elements. For example, $\{1, 2.35, 11\} = \{11, 1, 2.35\}$, but $\{1, 2.35, 11\} \not= \{1, 2\}$.

Let $S$ and $T$ be two sets. (For set variables, we usually use capital letters.) We say $S$ is a subset of $T$ if all members of $S$ are also in $T$. We usually write this as $S \subseteq T$. For example, $\{1\} \subseteq \{1, 2\}$. You can also write $T \supseteq S$, read “$T$ is a superset of $S$”, but that’s rarer.

You might observe that this definition says that $\{1, 2\}$ is also a subset of $\{1, 2\}$. In other words, any set is a subset of itself. Although true, we usually want to refer to the more interesting subsets; those which don’t contain all elements of the set. We say that $S$ is a proper subset of $T$, denoted $S \subset T$, if $S$ is a subset of $T$ and there is an element of $T$ not in $S$. Otherwise, we say a subset is improper. Every set has exactly one improper subset: itself. Also, notice the similarity of this notation with the notation for inequalities, i.e. compare $\{\subset, \subseteq, \supset, \supseteq\}$ with $\{<, \le, >, \ge\}$.

The empty set is the set containing nothing. We denote this usually as $\{\}$ or $\emptyset$. An interesting property of the empty set is that it’s a subset of any set!

The size of a set is the number of elements it contains. We usually write the size of $S$ as $\left|S\right|$. For example, $\left|\{10, 30\}\right| = 2$ and $\left|\emptyset\right| = 0$. But some sets are infinite, like the set of natural numbers $\mathbb{N} = \{1, 2, 3, 4, \ldots\}$. For these sets, we won’t be dealing much about their sizes (although there are in fact ways to make sense of sizes of infinite sets).

## Sequences and Tuples

By definition, a set is an unordered collection of things. But sometimes we want to talk about ordered collections. We call such a collection a sequence, and we use parentheses instead of curly brackets, for example $(1, 2, 2)$.

In sequences, order matters, and repetition matters. For example, $(1, 2) \not= (2, 1)$ and $(1, 2, 2) \not= (1, 2)$. Like sets, sequences can be infinite, such as the sequence of natural numbers $(1, 2, 3, \ldots)$.

Finite sequences are usually called tuples. A sequence with $k$ elements is called a $k$-tuple. For example, $(3, 4, 5)$ is a $3$-tuple, or a triple. A $2$-tuple is also called a pair.

Finally, sets can contain sequences as elements, and sequence can also contain sets (and other sequences) as elements. These are all just different kinds of objects after all.

## Operations on sets

Just like you can add or subtract two numbers, you can also perform operations on sets. We describe here some useful ones.

The union of two sets $S$ and $T$, denoted $S\cup T$, is the set containing all elements from $S$ and $T$. Elements included in both sets are counted exactly once. For example, $\{1, 2\} \cup \{2, 3\} = \{1, 2, 3\}$. We can also define the union using math notation:

$$S\cup T = \{x : x\in S \vee x\in T \}$$

The intersection of two sets $S$ and $T$, denoted $S\cap T$, is the set containing elements found in both $S$ and $T$. For example, $\{1, 2\} \cap \{2, 3\} = \{2\}$ and $\{1, 2\} \cap \{3, 4\} = \emptyset$. We can also define the intersection using math notation:

$$S\cap T = \{x : x\in S \wedge x\in T \}$$

We can also talk about the complement of a set $S$, which is roughly the set of elements not contained in $S$, but this only makes sense if we have a universal set, which is just the set of things relevant in the current discussion. For example, if our universal set is the set of integers $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots \}$, then the complement of the set of even integers is the set of odd integers. But if our universal set is the set of real numbers $\mathbb{R}$, then the complement of the set of even integers is the set of odd integers together with the set of all noninteger real numbers! So it’s important to know the universal set, but this is usually clear in the discussion.

We can also talk about the cross product of sets. The cross product of $S$ and $T$, denoted $S\times T$, is the set of pairs of elements, where the first element is from $S$ and the second is from $T$. For example, $\{1, 2\}\times \{\text{'s'}, \text{'t'}\} = \{(1,\text{'s'}),(1,\text{'t'}),(2,\text{'s'}),(2,\text{'t'})\}$. Using math notation:

$$S\times T = \{(x,y) : x\in S \wedge y\in T\}$$

Note that $S\times T$ is not the same as $T\times S$!

The power set of a set is the set of all its subsets. For example, the power set of $\{1, 2\}$ is $\{\{\}, \{1\}, \{2\}, \{1, 2\}\}$. Note that the power set of $\emptyset$ is $\{\emptyset\}$, the set containing the empty set, which is different from $\emptyset$. Power sets also exist for infinite sets, though the power sets are also infinite.

## Why sets

The idea of sets sounds simple enough, so what’s the point of sets? Well it turns out that sets are used nowadays to define everything in mathematics, including numbers, functions, algebraic objects, etc. We won’t be dealing with that here, though.