# Basic Set Theory

Edward A. Roualdes

Introduction
Sets
Set Operations

## Introduction

Set theory is the starting point for a wide range of topics. At its most basic level, sets just describes groups of things and the theory describes how to logically rearrange sets into new sets. The things are most often numbers, but since we are headed towards an introduction to probability, our sets don't necessarily have to consist of numbers. As such, these notes comprise a collection of material that one should know to understand a short introduction to probability. These notes are not intended to be a comprehensive review of set theory in general.

Two sections follow, Sets and Set Operations. The section Sets describes the basic components of sets and introduces new notation to describe elements of sets. The section Set Operations mostly consists of binary operations on sets. From these binary operations, new sets can be constructed.

## Sets

A set is a collection of things. In mathematics, the things are most often numbers. In the world of probability and statistics, the items in sets are commonly numbers or the outcomes of a process. Sometimes the outcomes of a process are represented as numbers, but it's important to remember that statistics is generally interested in the randomness that generated the outcomes of the process.

The symbol $$\emptyset$$ is known as the empty set. Using curly braces, this set is written as $$\emptyset = \{\}$$. This is the set that consists of no elements. It may seem boring, but it's an important set in mathematical statistics.

Of course, not all sets are empty. The symbol $$\in$$ is used to state that an element is a member of a set. Written $$x \in \mathcal{X}$$, we read $$x$$ is an element of the set $$\mathcal{X}$$. To state that an element is not an element of a set, use the symbol $$\notin$$.

For a non-empty set example, let's move to a set of numbers. We write $$\mathcal{X} = \{1, 2, 3, 4, 5, 6 \}$$, and read this as the set $$\mathcal{X}$$ consists of the integers $$1, 2, 3, 4, 5,$$ and $$6$$. You might imagine a single die roll here, but a set of numbers might represent the outcome of some process.

Imagine random sampling families and counting the number of children each family has. A set of possible number of children in each family could be $$\mathcal{X} = \{1, 2, 3, 4 \}$$. The process here is that of a family having children.

Sets can be very contextualized and yet intangible. For instance, there exists a set of all faculty computers on the Chico State campus. Occassionaly our campus IT tries to make this set more tangible by ensuring that their records appropriately match the hardware in faculty offices. We might write this set as $$\mathcal{X} = \{x_1, x_2, \ldots, x_N \}$$, where $$x_n$$ might be a unique ID associated with each computer.

Sets need not be finite. The interval of all real numbers from $$0$$ to $$1$$ inclusive is infinite, although bounded. We often write this set as $$\mathcal{X} = [0, 1]$$.

In theory sets can be constructed by specifying a set of rules that must hold for an element to be included. Consider the so called set builder notation, to specify the values of $$f(x) = x^2$$ such that the input $$x > \sqrt{5}$$, $$\{ x^2 | x > \sqrt{5} \}$$. The vertical pipe is to be read as such that or given; the set of values of $$x$$ squared, such that $$x$$ is strictly greater than $$\sqrt{5}$$.

## Set Operations

Much like $$+$$ is an operation on two numbers, the following set operations are binary operators where the operands are sets instead of numbers.

To indicate set inclusion, that one set is contained in another set, the symbol $$\subset$$ is used. For instance, $$\{ 1, 2 \}$$ is a subset of $$\{1, 2, 3\}$$. This is written as $$\{ 1, 2 \} \subset \{1, 2, 3\}$$. If the subset has the potential to be equal to the superset, then the symbol $$\subseteq$$ is used. Though, some authors use the symbol $$\subset$$ even when equality is possible. When equality is not possible, the term proper subset is used.

More generally, we might visualize a set hierarchy such as $$A \subset B \subset \mathcal{X}$$ as follows. Imagine that there are elements in the sets, even if they're not drawn.

The next two operations either combine the contents of two sets, or reference only the elements contained in both sets. These two operations are union $$\cup$$ and intersection $$\cap$$, repsectively. Pictures are my preferred strategy for understanding $$\cup$$ and $$\cap$$.

Let $$A, B \subset \mathcal{X}$$. The union of $$A$$ and $$B$$, written $$A \cup B$$, is equal to the set that consists of all elements in either set (counted only once). In set builder notation, $$A \cup B = \{x | x \in A \text{ or } x \in B \}$$. The following display visualizes in blue the set $$\color{#00BFFF}{A \cup B}$$. to addition.

Let $$A, B \subset \mathcal{X}$$. The intersection of $$A$$ and $$B$$, written $$A \cap B$$, is equal to the set that consists of only the elements in both sets. In set builder notation, $$A \cap B = \{x | x \in A \text{ and } x \in B \}$$. The following display visualizes in pink the set $$\color{#00B78D}{A \cap B}$$.

Set difference is the analogue to subtraction. Let $$A \subset B$$. The set difference $$\color{#FF6DAE}{B \setminus A}$$ consists of all the elements of $$B$$ after removing those elements that are also in $$A$$. Think of this as $$B$$ remove $$A$$.

In another analogy to binary operations on numbers, the symbol $$\times$$ when applied to sets is called the Cartesian product. Let $$A, B \subset \mathcal{X}$$. The set $$A \times B = \{(a, b) | a \in A \text{ and } b \in B \}$$, that is the set of ordered pairs that consist of one element from each of the two sets in the product.

Our last set operation is named cardinality. Cardinality measures the number of elements in a set. For the set of suits in a standard deck of cards $$S = \{$$ ♠, , ♣, $$\}$$, the cardinality of $$S$$ is $$|S| = 4$$.

A deck of cards is a set of 52 elements. This set can be thought of as the Cartesian product of the two sets $$S = \{$$ ♠, , ♣, $$\}$$ and $$N = \{ A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K \}$$. Since $$|S| = 4$$ and $$|N| = 13$$, the cardinality of a standard deck of cards $$|D| = |S \times N| = 52$$. This is the thinking behind the analogy between the Cartesian product and multiplication.