We have already introduced the notion of a set here. Recall that a set is an unordered collection of distinct objects, which are called members or elements. We use $\{\ \}$ to denote a set. For example, the set containing 2, 3, 5 is written as $\{2,3,5\}$. While $\{2,3,5\}=\{3,5,2\}$, the following sets are different.

1. $\{2,3,5\}$ contains 3 members 2, 3, 5.
2. $\{\{2\},\{3\},\{5\}\}$ contains three singleton sets $\{2\}$, $\{3\}$, $\{5\}$ as members.
3. $\{\{2,3,5\}\}$ contains a single element $\{2,3,5\}$.

Example. Some Important Examples of Sets

1. $\emptyset$=$\{\ \}$=$\Box$=the empty set, the set containing no object. If I remember correctly, the notation $\Box$ for the empty set was introduced by Nicolas Bourbaki, a secretive group of mathematicians.
2. $\mathbb{N}=\{0,1,2,3,\cdots\}$, the set of all natural numbers.
3. $\mathbb{Z}=\{\cdots,-3,-2,-1,0,1,2,3,\cdots\}$, the set of all integers.
4. $\mathbb{Q}$=the set of all rational numbers.
5. $\mathbb{R}$=the set of all real numbers.

The notation $\in$ is used to express membership. For example, $a\in S$ says $a$ is a member of the set $S$. The set of elements of $A$ that satisfy the predicate $P$ is written as$$\{x\in A: P(x)\}$$

Example. The set of all even integers can be written as $$\{n\in\mathbb{Z}: n\ \mbox{is even}\},$$ $$\{n\in\mathbb{Z}:n=2m\ \mbox{for some}\ m\in\mathbb{Z}\},$$ or $$\{2m: m\in\mathbb{Z}\}$$

A subset $A$ of a set $B$, we write $A\subseteq B$, is defined by $$A\subseteq B\ \mbox{iff}\ [x\in A\Longrightarrow x\in B]$$ If $A\subseteq B$, $B$ is called a superset of $A$. Two sets $A$ and $B$ are said to be equal, we write $A=B$, if $A\subseteq B$ and $B\subseteq A$. If $A\subseteq B$ and $A\ne B$, we write $A\subsetneq B$ and $A$ is called a proper subset of $B$. The notation $A\subset B$ is also frequently used in mathematics to mean that $A$ is a subset of $B$.

Example.

1. $\emptyset$ is a subset of every set.
2. Every set is a subset of itself.
3. $\mathbb{N}\subseteq\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}$.

The power set of a set $A$, denoted by $\wp(A)$ or $2^A$, is the set of all subsets of $A$. For example, if $A=\{3,17\}$, then $\wp(A)=\{\emptyset,\{3\},\{17\},\{3,17\}\}$. If $|A|=n$, then $|\wp(A)|=2^n$.

Now let us discuss set operations. First, we define $A\cup B$, the union of two sets $A$ and $B$ by $$A\cup B=\{x:x\in A\ \mbox{or}\ x\in B\}$$ Next, $A\cap B$, the intersection of two sets $A$ and $B$ is defined by $$A\cap B=\{x:x\in A\ \mbox{and}\ x\in B\}$$ Clearly, $\cup$ and $\cap$ are commutative. $\cup$ and $\cap$ are also associative, namely \begin{align*}(A\cup B)\cup C&=A\cup (B\cup C)\\(A\cap B)\cap C&=A\cap (B\cap C)\end{align*} Lastly, $\bar A=A^c$, the compliment of a set $A$ is defined by $$\bar A=\{x:x\notin A\}$$ Note that while $\cup$ and $\cap$ are binary operations, $\bar{}$ is a unary operation. The empty set $\emptyset$ is an identity element for $\cup$, i.e. for any set $A$, $A\cup\emptyset=A$. $\emptyset$ is also regarded as an operation which is called a nullary operation. Those of you who are interested in learning more details about operations may be referred to [2] below. Using the compliment, we can define $A-B$, the difference of $A$ and $B$ is defined by $$A-B=A\cap\bar B$$ This set minus is not an operation but the composite of two operations $\cap$ and $\bar{}$. If $A\subseteq X$, $X-A$ is also frequently written as $X\setminus A$.

Theorem. Distributive Laws \begin{align*}A\cap(B\cup C)&=(A\cap B)\cup(A\cap C)\\A\cup(B\cap C)&=(A\cup B)\cap(A\cap C)\end{align*}

Proof. We prove only the first one. The proof of the second one is left as an exercise. \begin{align*}x\in A\cap(B\cup C)&\Longleftrightarrow x\in A\ \mbox{and}\ x\in B\cup C\\&\Longleftrightarrow x\in A\ \mbox{and}\ [x\in B\ \mbox{or}\ x\in C]\\&\Longleftrightarrow[x\in A\ \mbox{and}\ x\in B]\ \mbox{or}\ [x\in A\ \mbox{and}\ x\in C]\\&\Longleftrightarrow x\in A\cap B\ \mbox{or}\ x\in A\cap C\\&\Longleftrightarrow x\in(A\cap B)\cup(A\cap C)\end{align*}

The Cartesian product of two sets $A$ and $B$, denoted by $A\times B$, is defined by the set of ordered pairs with the first component taken from $A$ and the second component taken from $B$. $$A\times B=\{(a,b):a\in A\ \mbox{and}\ b\in B\}$$ Note that $\times$ is not an operation.

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

[2] A Course in Universal Algebra, Stanley N. Burris and H. P. Sankappanavar, Graduate Texts in Mathematics, Springer-Verlag, 1981. The book is available online for free at the first named author’s web page here.