# Set Theory
These lecture notes are mainly based on Rosen's (2011) *Discrete Mathematics and its Applications 7th Edition*.
#### Definition from Rosen (2011)
>A **set** is an unordered collection of objects, called **elements** or **members** of the set. A set is said to **contain** its elements. We write $a \in A$ to denote that $a$ is an element of the set $A$. The notation $a \notin A$ denotes that $a$ is not an element of the set $A$.
## Describing Sets
**Roster Method**. Sets can be described by listing the elements of the set. The set:
$$
S=\{a,b,c\}
$$
Describes a set called $S$ containing the elements $a$,$b$, and $c$.
Other examples:
- Set of all primes, less than 10: $P=\{2,3,5,7\}$
- Set of all primary colors: $C=\{\text{red},\text{blue},\text{yellow}\}$
- A random set, $R=\{A,3,25,\text{Cebu}\}$
- Set of all natural numbers, $\mathbb{N}=\{0,1,2,3,4,\ldots\}$
**Set Builder Notation**. Sets can also be described by specifying the properties of its elements.
$$
S=\{x~|~P(x)\}
$$
The members of this set are all elements who satisfy the property described in the predicate $P(x)$. This is read as: "S is the set of all $x$ such that $P(x)$"
Other examples:
- Set of all odd numbers: $O=\{2k+1~| ~k \in \mathbb{Z}\}$
- Set of all words with starting letter "R": $R=\{w~|~\text{w is a word with starting letter "R"}\}$
**Interval Notation**. Sets can be described using intervals
- $[a,b] = \{x~|~a \leq x \leq b\}$
- $(a,b) = \{x~|~a < x < b\}$
- $(a,b] = \{x~|~a < x \leq b\}$
- $[a,b) = \{x~|~a \leq x < b\}$
## Important number sets
Listed below are numbers sets you need to familiarize with.
##### Set of Natural Numbers
$$
\mathbb{N}=\{0,1,2,3,\ldots\}
$$
##### Set of Integers
$$
\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}
$$
##### Set of Positive Integers
$$
\mathbb{Z}^+=\{1,2,3,\ldots\}=\{x\in \mathbb{Z}~|~x>0\}
$$
##### Set of Negative Integers
$$
\mathbb{Z}^-=\{-1,-2,-3,\ldots\}=\{x\in \mathbb{Z}~|~x<0\}
$$
##### Set of Rational Numbers
$$
\mathbb{Q}=\Big\{\frac{p}{q}~|~p \in \mathbb{Z},q \in \mathbb{Z},q\neq 0\Big\}
$$
##### Set of all Real Numbers
$$
\mathbb{R}
$$
##### Set of all Complex Numbers
$$
\mathbb{C}
$$
## Set of sets
A set's elements can be anything. Including sets:
$$
S=\{\{1\},\{1,2\},\{1,2,3\}\}
$$
Set $S$ is a set containing the sets $\{1\}$,$\{1,2\}$, and $\{1,2,3\}$.
## Set equality
Definition form Rosen (2011)
>Two sets are **equal** if and only if they have the same elements. Therefore, if $A$ and $B$ are sets, then $A$ and $B$ are equal if and only if $\forall x (x \in A \leftrightarrow x \in B)$. We write $A=B$ to denote that $A$ and $B$ are equal sets.
For example:
$$
\{1,8,12\}=\{12,1,8\}=\{1,1,1,8,8,12,12,12,12,12\}
$$
These sets are all equal to each other since all members of one set is a member of the other set.
## Empty Set
The **empty set** is a special set that contains no elements. It is also called the **null set**. It is denoted by:
$$
\emptyset
$$
or:
$$
\{~\}
$$
The null set should not be confused with the set containing the empty set denoted by $\{\emptyset\}$.
## Universal Set
The universal set is a set containing all the elements in the agreed upon domain. This is usually denoted by $U$.
## Subsets
Definition from Rosen (2011)
>The set $A$ is a subset of $B$ if and only if every element of $A$ is also an element of $B$. The notation $ A\subseteq B$ to indicate that $A$ is a subset of $B$. We say that $A \subseteq B$ if and only if $\forall x (x \in A \to x \in B)$. We use the notation $A \nsubseteq B$ to indicate that $A$ is not a subset of $B$.
Examples
- $\{A,B,C\} \subseteq \{A,B,C,D\}$
- $\mathbb{Z}^+ \subseteq \mathbb{Z}$ since all positive integers are also integers
- $\{x \in \mathbb{R}~|~ x<10\} \subseteq \{x \in \mathbb{R}~|~ x<20\}$
It is important to note that the empty set $\emptyset$ is a subset of any set. We know this because of the definition of subsets. The criteria for some set $A$ to be a subset of some set $B$ is that $\forall x (x \in A \to x \in B)$. Since an empty set contains no elements. This means that the $x \in \emptyset$ is always false for any object $x$. This means that the hypothesis in the predicate of the quantification $\forall x (x \in \emptyset \to x \in S)$ is always false, which makes the implication statement always true (false hypotheses in implications make any implication automatically true). Therefore, $\emptyset \subseteq S$ for an arbitrary set $S$.
### Proper Subsets
> The set $A$ is proper subset of $B$ if and only if $A \subseteq B \land A \neq B$. The notation $A \subset B$ is used to indicate that $A$ is a proper subset of $B$.
- $\{A,B,C\} \subseteq \{A,B,C\}$ but $\{A,B,C\} \not \subset \{A,B,C\}$
## Venn Diagrams
This is a venn diagram representing two sets, A and B.
- Let $A$ = set of all Bug Type Pokemon and
- Let $B$ = set of all Pokemon weak to fire
In this case since all bug type pokemon are weak to fire, then the set of all bug type pokemon is a subset of the set of all pokemon weak to fire. But since pokemon weak to fire are not necessarily bug type, then the set of all pokemon weak to fire is not a subset of the set of all bug type pokemon. This is shown in the diagram in the way that set $A$ is fully inside set $B$.
## Power Sets
Definition from Rosen (2011)
> Given a set $S$, the **power set** of set $S$ is the set of all subsets of $S$. The power set of $S$ is denoted by $\mathcal{P}(x)$.
For example the power set of the set $\{1,2,3\}$ is
$$
\mathcal{P}(\{1,2,3\}) = \{ \emptyset, \{1\}, \{ 2 \}, \{ 3 \}, \{ 1,2 \}, \{1,3 \}, \{2,3\}, \{1,2,3\} \}
$$
If a set $S$ has $n$ elements then $\mathcal{P}(S)$ has $2^n$ elements.
## Cartesian Products
Definition from Rosen (2011)
> Let $A$ and $B$ be sets. The **Cartesian product** of $A$ and $B$, denoted by $A \times B$, is the set of all ordered pairs $(a,b)$, where $a \in A$ and $b \in B$. Or,
> $$
> A\times B = \{(a,b)~|~ a \in A \land b\in B\}
> $$
>
For example the Cartesian product of $A=\{1,2,3\}$ and $B=\{x,y\}$ is,
$$
A \times B = \{(1,x),(2,x),(3,x),(1,y),(2,y),(3,y)\}
$$
This is different from the Cartesian product of $B$ and $A$,
$$
B \times A = \{(x,1),(y,1),(x,2),(y,2),(x,3),(y,3)\}
$$
> Ordered pairs are are ordered 2-tuples. n-tuples are fundamental structures like sets. They are similar to sets since they are also collection of objects. Ordered n-tuples consider the arrangement of its members, $(1,2,3) \neq (2,1,3)$. Same elements in one n-tuple are considered different from each other $(1,2)\neq (1,1,2)$.
## Set Notations and Quantifiers
Usually you will see quantifiers with a set restriction on a domain,
$$
\forall x \in \mathbb{R}(x^2>0)
$$
This quantifier reads:
> "For all $x$ element of the set of real numbers, $x^2$ is greater than 0"
or
> "All squares of real numbers are greater than zero"
In general any quantification that follows the pattern:
$$
\forall x \in S(P(x)) \\
\exists x\in S(P(x))
$$
means, for all elements of $S$, $P(x)$. The restriction to the domain is the predicate $x\in S$.
## Truth Sets
The truth set of a given predicate $P$ over a set $S$ is the set of all elements $x$ such that $P(x)$. Or:
$$
\{x \in S~|~P(x)\}
$$
## Size of Sets
Cardinality Definition from Rosen (2011)
> Let $S$ be a set. It there are exactly $n$ distinct elements in $S$ where $n$ is a nonnegative integer, we say that $S$ is a **finite set** and that $n$ is the **cardinality** of $S$. The cardinality of a set $S$ is denoted by $|S|$.
##### Examples
- Let $A=\{a,b,c,d\}$, $|A|=4$
Two sets $A$ and $B$ are said to be of the same cardinality if and only if each element in the set $A$ can be paired with exactly one element in set $B$ end every element in $B$ can be paired with exactly one element in set $A$. Two sets with the same cardinality are said to be **equinumerous**.
The ordinality of a set $S$ is the smallest natural number not needed to label a set in a well ordered manner. The ordinality of a finite set $S$ is just equivalent to its cardinality.
## Set Operations
Sets can also be described using a combination of sets and operations:
#### Union
Definition from Rosen (2013)
> Let $A$ and $B$ be sets. The **union** of the sets $A$ and $B$, denoted by $A \cup B$, is the set that contains elements that are either in $A$ and $B$ or in both.
> $$
> A \cup B=\{x~|~(x \in A) \lor (x \in B)\}
> $$
>
The venn diagram above depicts the shaded region $A \cup B$.
##### Examples
- $\{1,2,3,4\} \cup \{3,4,5,6\}=\{1,2,3,4,5,6\}$
- $\mathbb{Z}^+ \cup \{0\}=\mathbb{N}$
##### Intersection
Definition from Rosen (2011)
> Let $A$ and $B$ be sets. The **intersection** of the sets $A$ and $B$, denoted by $A \cap B$, is the set that contains elements that are both in $A$ and $B$.
> $$
> A \cap B=\{x~|~(x \in A) \land (x \in B)\}
> $$
>
The shaded region of the venn diagram above corresponds to $A \cup B$
##### Examples
- $\{1,2,3,4\}\cap \{3,4,5,6\}=\{3,4\}$
- $\mathbb{Z}^+ \cap \mathbb{N}=\mathbb{Z}^+$
##### Joint vs Disjoint sets
Two sets are said to be disjoint if and only if their intersection is the null set. They are joint if otherwise. The sets $\{1,2,3,4\}$ and $\{3,4,5,6\}$ are joint but the sets $\{1,2,3,4\}$ and $\{5,6,7,8\}$ are disjoint.
#### Difference
Definition from Rosen (2011)
> Let $A$ and $B$ be sets. The **difference** of the sets $A$ and $B$, denoted by $A - B$, is the set that contains elements that are in $A$ but not in $B$. The difference of $A$ and $B$ is also called the **complement of $B$ with respect to $A$**. The difference of $A$ and $B$ is sometimes denoted as $A /B$
> $$
> A - B=\{x~|~(x \in A) \land (x \notin B)\}
> $$
>
The shaded region on the venn diagram above depicts $A-B$.
##### Examples
- $\{1,2,3,4\}-\{3,4,5,6\}=\{1,2\}$
- $\mathbb{Z}-\mathbb{Z}^+=\mathbb{Z}^-\cup\{0\}$
#### Complement
Definition from Rosen (2011)
> Let $A$ be a set. The **complement** of the set $A$, denoted by $\overline{A}$, is the complement of set $A$ with respect to $U$.
> $$
> \overline{A}=U-A=\{x~|~x \notin A\}
> $$
>
The shaded region in the venn diagram above depicts $\overline{A}$.
##### Examples
- Say $U$ is the set of integers $\mathbb{Z}$, $\overline{\{3,4,5,6\}}=\{\cdots,-2,-1,0,1,2\} \cup \{7,8,9,10,\cdots\}$
- $\overline{\emptyset}=U$
## Set Identities
| Identity | Name |
| ------------------------------------------------------------ | -------------------------- |
| $A \cap U =A \cup \emptyset=A$ | Identity Laws |
| $A\cup U=U$, $A\cap \emptyset=\emptyset$ | Domination Laws |
| $A\cup A=A\cap A=A$ | Idempotent Laws |
| $\overline{(\overline{A})}=A$ | Double Complementation Law |
| $A \cup B = B \cup A$, $A \cap B = B \cap A$ | Commutative Law |
| $A \cup (B \cup C)=(A \cup B) \cup C$, $A \cap (B \cap C)=(A \cap B) \cap C$ | Associative law |
| $A \cup (B \cap C)=(A \cup B) \cap (B \cup C)$, $A \cap (B \cup C)=(A \cap B) \cup (B \cap C)$ | Distributive Law |
| $\overline{A \cup B}=\overline{A} \cap \overline{B}$, $\overline{A \cap B}=\overline{A} \cup \overline{B}$ | De Morgan's Law |
| $A \cup (A \cap B) = A \cap (A \cup B)=A$ | Absorption Law |
| $A\cup \overline{A}=U$, $A \cap \overline{A} = \emptyset$ | Complement Law |
### Membership Tables
Membership tables function like truth tables which can be used to prove set identities
The following membership table shows that the absorption law is indeed true
| Member of $A$ | Member of $B$ | Member of $A \cap B$ | Member of $A\cup (A \cap B)$ |
| :-----------: | :-----------: | :------------------: | :--------------------------: |
| T | T | T | T |
| T | F | F | T |
| F | T | F | F |
| F | F | F | F |
## Generalized Union and Intersection
You can express a series of unions as the generalized operation:
$$
A_1\cup A_2 \cup A_3\cup \cdots \cup A_n=\bigcup_{i=1}^{n}{A_i}
$$
The same can also be done with intersection
$$
A_1\cap A_2 \cap A_3\cap \cdots \cap A_n=\bigcap_{i=1}^{n}{A_i}
$$
## Bit Representation of Sets
One of the ways to represent sets in computers is using bit representation. Supposing there exists a finite set representing the universal set $U$ as $U=\{1,2,3,4,5,6,7\}$. You can represent the following sets bitwise:
- $\{1,2,3,4\}$ is 111 1000
- $\{2,4,6\}$ is 010 1010
- $\{4,5,6\}$ is 000 1110
Using these representations it is easy to find the union, intersection, and difference and complement sets
- $\overline{\{1,2,3,4\}}$ is 000 0111 (all zeroes become one and all ones become zero)
- $\{2,4,6\} \cap \{4,5,6\}$ is 010 1010 $\cap$ 000 1110 or
$$
\begin{align*}
& 010~1010 \\
\land ~ &000~1110 \\
\hline
&000~1010
\end{align*}
$$
(0 is false and one is truth, the intersection is calculated by calculating conjunction bitwise). The set represented by 000 1010 is $\{4,6\}$
## Transfinite Numbers
#### Transfinite Cardinals
Consider a set $A$, the cardinality of set $A$ is the amount of distinct elements in $A$. One way describing a set's cardinality is using cardinal numbers. For example the set containing $\{1,2,3,4\}$ has cardinality 4 since there are 4 distinct elements in the set. Another way of describing a set's cardinality is using injections and surjections.
For example the set $A=\{1,2,3,4\}$ and $B=\{a,b,c,d\}$ can be shown to have the same cardinality, ($|A|=|B|$) since there exists some bijective function $f$ such that $f:A \to B$.
Set $A$ can be shown to have lesser cardinality than set $C$ ($|A| \leq |B|$), defined as $C=\{a,b,c,d,e\}$, since there exists an injective function $g$ such that $g:A \to B$.
Set $A$ can also be shown to have strictly lesser cardinality than $C$ ($|A|<|B|$), since there exists an injective function $f$, but there exists no surjective function $h$ such that $h:A \to B$.
Now consider a set with infinite elements like the set of natural numbers. Sets like these contain more elements than any finite set since you can show that for any finite set $F$ there exists an injective function but no surjective function that maps $F$ to $\mathbb{N}$. No matter how numerous set $F$ is, you can infinitely construct natural numbers that are not images of $F$.
$$
\begin{align*}
&\text{Let } F=\{s_0,s_1,s_2,s_3,...,s_n\}\\
&\text{Let } f:F\to \mathbb{N}\\
\\
&\text{Let }f(s_0)=0\\
&\text{Let }f(s_1)=1\\
&\text{Let }f(s_2)=2\\
&\vdots\\
&\text{Let }f(s_n)=n\\
&\text{Let }f(s_{n+1})=n+1\\
\\
& \text{Since } s_{n+1} \notin F \land n+1 \in \mathbb{N} \\
&\text{Therefore, } f \text{ is not surjective}
\end{align*}
$$
Since the cardinality of a finite set is always a natural number, what you need to describe the cardinality of a set such as $\mathbb{N}$ is a cardinal number bigger than all natural numbers. The smallest of which is the transfinite number called **aleph null**
$$
\aleph_0 = |\mathbb{N}|
$$
What about the cardinality of other infinite sets, like the set of even natural numbers $E$? It wouldn't be far-fetched to assume that the cardinality of $E$ is smaller than $\aleph_0$ since there are half as much even numbers as there are natural numbers. But transinfinite numbers behave differently. Since we can show that there exists a bijection between the set of natural numbers $\mathbb{N}$ and the set of even numbers $E$ namely:
$$
f:\mathbb{N}\to E, f(x)=2x
$$
Every natural number $x$ can be paired with every even number $2x$
- $f(0)=0$
- $f(1)=2$
- $f(2)=4$
- ...
This means that $\mathbb{N}$ is equinumerous to $E$, which means they have the same cardinality $\aleph_0$. This equinumerosity relationship with $\mathbb{N}$ can also be observed with other infinite sets. We call these sets **countably infinite sets**:
- set of all odd numbers
- set of all numbers divisible by 4 and 5
- set of all rational numbers (proven via the diagonal method)
- set of all natural numbers except 5
Some sets can be shown to have a cardinality greater than $\aleph_0$ (shown by Cantor using the diagonal argument),
- powerset of $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$
- set of all natural numbers $\mathbb{R}$
- $(a, b)$ where both $a$ and $b$ are real numbers such that $a < b$
All of the sets above actually have the same cardinality, $2^{\aleph_0}$ (also denoted as, $\mathfrak{c}$), There are even bigger infinities other than this such as $\mathcal{P(\mathcal{P}(\mathbb{N}))}$
#### Transfinite Ordinals
A well ordering of a given set $A$ is an inductive function that describes some kind of succession starting from the first element up to the last element, listing each element exactly once. One of the axioms of modern set theory (Zermelo-Frankel Set Theory) states that there exists a well ordering of a given set.
Given some well ordering of a set, its order type can be described using the smallest ordinal number not need to order the number in the said well ordered manner.
The order type of a finite set is easy to describe. It is simply equal to its cardinality. On the other hand, infinite sets like $\mathbb{N}$, is described to have an order type of the smallest transfinite ordinal number omega
$$
\omega
$$
It is important to note the the ordinal number $\omega$ is not equal to $\aleph_0$. The cardinal number $\aleph_0$ describes a countably infinite **amount** of elements while the ordinal number $\omega$ describes the **order/rank** of an element that succeeds $\aleph_0$ elements. Basically, $\omega$ is what you use as an ordinal label when run out of natural number labels.
Consider the set of natural numbers below, we know that this set has cardinality $\aleph_0$
$$
\{0,1,2,3,4,5,6,7,\cdots\}
$$
The union of this set with $\{-1\}$ describes another set with cardinality $\aleph_0$ as well.
$$
W=\{0,1,2,3,4,5,6,7,\cdots\} \cup \{\omega\}
$$
That's because you can describe the bijective function $f$, that maps $\mathbb{N}$ to $W$.
$$
f(x)=
\begin{cases}
\omega & x=0\\
x-1 & x>0
\end{cases}
$$
But if you insist on well ordering the elements in increasing order, you have to label each natural number $x$ with the natural number $x$. This means that you need to label an $\aleph_0$ amount of elements before labelling the element $\omega$. This means that by definition, $\omega$ will be labelled as the $\omega^{th}$ element. Therefore the set $W$ will have an order type of $\omega + 1$.
Although it sounds counter-intuitive, the element $\omega$ does not contribute to the cardinality of $W$. It still has $\aleph_0$ elements but its order type is now $\omega+1$. Adding the element $\omega+1$ will describe a new set with order type $\omega +2$ . Adding the element $\omega +2$ will describe a new set with order type $\omega +3$ and so on. Suppose continuously add countably infinite items in this manner, we will be able to describe the set below:
$$
W_2=\{0,1,2,3,4,\cdots,\omega,\omega+1,\omega+2,\cdots,\omega+\omega\}
$$
It is important to note that this set still has the cardinality $\aleph_0$ this is because we can describe the bijection $g:\mathbb{N}\to W_2$:
$$
g(x)=
\begin{cases}
\frac{x}{2} & x \text{ is even}\\
\omega+\frac{x-1}{2} & x \text{ is odd}
\end{cases}
$$
The set below also has the same cardinality:
$$
W_3=\{1,2,3,4,\cdots,\omega^2\}
$$
Which is also true for this set:
$$
W_3=\{1,2,3,4,\cdots,\omega^\omega\}
$$
Or in fact any set constructed (using ZFC's axiom schema of replacement) in a well ordered and countable manner.
#### The continuum hypothesis
In the same way that we are able to describe the existence of an infinite set. One that cannot be constructed using finite operations on finite amounts. We can also describe even bigger set, a set that contains all countable ordinal numbers:
$$
\{1,2,3,\cdots,\omega,\omega+1,\omega+2,\cdots,\omega+\omega,\cdots,\omega^2,...,\omega^\omega,\cdots\}
$$
Since this set is well ordered this set also has a some kind of well ordering. The order type of this set cannot be any ordinal number already in this set. That is because, by definition, the order type of any set is bigger than any of the labels in the set. By definition this set has the order type **omega-1**:
$$
\omega_1
$$
Now, since this set has an order type larger than any countable set ordinal. It must, by definition have a cardinality larger than any countably infinite set. This means that its cardinality defined as $\aleph_1$ is greater than $\aleph_0$
$$
\aleph_1>\aleph_0
$$
It is also important to note that there are no cardinals in between $\aleph_0$ and $\aleph_1$. This is because a set with lesser cardinality than $\aleph_1$ is countable, and therefore equal to $\aleph_0$.
This leads us to one of the greatest unanswered questions in math. "Is the continuum hypothesis true?". Or, "Is the cardinality of the continuum ($\mathfrak{c}$ or $|\mathbb{R}$| or $2^{\aleph_0}$), equal to the cardinality of a set with order type $\omega_1$ ($\aleph_1$)?"
$$
\mathfrak{c}=\aleph_1?
$$
Sign in with Wallet
Connect another wallet