1.2. Elementary set theory

Following the discussion in the Introduction, I will assume that I intuitively know what a set is, and that I can reasonably talk about the relation $\in$ in the language of sets. I write $x\in A$ if the set $x$ is element of $A$, or in other words if $x$ belongs to $A$.

Basic properties of sets

I denote by $\varnothing$ the set with no elements. That is, the set satisfying that (recall that $\forall$ represents “for all”)

$$\forall x,x\notin \varnothing .$$

Definition.

Given two sets $A$ and $B$, I say $A$ is a subset of $B$, or $A$ is contained in $B$, in symbols,

$$A\subseteq B$$

if for all $x$, $x\in A$ implies $x\in B$. I say the sets $A$ and $B$ are equal, in symbols,

$$A=B,$$

if they are subsets of each other. That is, $A\subseteq B$ and $B\subseteq A$.

Remark.

The sets $A$ and $B$ are equal if and only if for all $x$,

$$x\in A⟺x\in B.$$

This is a great moment to develop some skills that will serve you in learning math in general. Whenever encountering a definition for the first time, always do the following exercise:

Exercise scheme.

1. What is the negation of the definition? In this case, what does it mean for $A$ to not be a subset of $B$? I use the symbol $A⊈B$.
2. What are examples and non-examples of the situation? In this case, can you list out all subsets of the set $\{0,1\}$?
3. Write down a proof of a set being a subset of another set. Write down a proof of a set not being subset of a given set. What techniques did you use to prove these different statements?

Proposition.

For any sets $A,B$ and $C$,

1. $A\subseteq A$ (Reflexivity);
2. $\varnothing \subseteq A$ (Minimum element / Vacuous truth);
3. if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$ (Transitivity); and
4. if $A\subseteq B$ and $B\subseteq A$, then $A=B$ (Anti-symmetry).

Exercise.

Prove the above properties from the definition.

Basic operations on sets

Below, family is just another word for set, to avoid saying “set of sets.”

Definition.

The powerset of a set $X$, denoted by $\mathcal{P}(X)$, is the family of all subsets of $X$.

Examples.

1. $\mathcal{P}(\varnothing )=\{\varnothing \}$.
2. $\mathcal{P}(\{\varnothing \})=\{\varnothing ,\{\varnothing \}\}$.

In this course, I do not formally define the ordered pair $(a,b)$, but all you need to know about it is that $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$. So, for instance, $(0,1)\ne (1,0)$ even though $\{0,1\}=\{1,0\}$.

Definition.

Let $A$ and $B$ be sets. I define the following operations.

1. The union $A\cup B=\{x:x\in A\vee x\in B\}$. ($\vee$ represents “or”)
2. The intersection $A\cap B=\{x:x\in A\wedge x\in B\}$. ($\wedge$ represents “and”)
3. The Cartesian product $A\times B=\{(a,b):a\in A\wedge b\in B\}$.
4. The difference $A\setminus B=\{a\in A:a\notin B\}$.

Exercise.

Show that for any $A$, $B$ and $C\in \{A,B\}$,

$$A\cap B\subseteq C\subseteq A\cup B.$$

Exercise.

Show that the following statements are equivalent for any sets $A$ and $B$.

$$A\cup B=BA\subseteq BA\cap B=A$$

Solution.

Assume that $A\cup B=B$ and let us show that $A\subseteq B$. Given any $x$, if $x\in A$, then in particular $x\in A\cup B=B$. Therefore, $x\in B$.

Now assume that $A\subseteq B$ and let us decide what $A\cap B$ is. It is obvious that $A\cap B\subseteq A$. Given $x\in A$, my assumption tells us that $x\in B$. Thus, $x\in A\cap B$ and this proves the other containment. Therefore, $A\cap B=A$.

Finally, assume that $A\cap B=A$. Clearly, $B\subseteq A\cup B$. Given $x\in A\cup B$, there are two cases. Either $x\in A$, in which case, since $A=A\cap B$, $x$ is also an element of $B$; or $x\in B$. In either case, $x$ must be an element of $B$, which proves that $A\cup B=B$.

Reflect.

I sought out to prove three equivalence statements, yet this proof only contains three implications, instead of six. Convince yourself that my proof is indeed complete.

Finite sets (informal discussion)

This definition is informal and this concept will be formalized in a later chapter, but it is good enough to give examples and exercises now.

Definition.

A set $A$ is finite if there exist $x_1,x_2,\dots ,x_n$ such that $A=\{x_1,x_2,\dots ,x_n\}$.

A set is infinite if it is not finite.

Proposition.

1. Subsets of finite sets are finite.
2. The union of two finite sets is finite.

The lattice of subsets

Note:

The concept of lattice is not explicitly part of the course, but several important examples are seen in the lectures. These follow informal discussions (and are hence inadequate for these notes) that summarize large portions of theory.