# Discrete Mathematics Lecture 1 — Set Theory

University course in discrete mathematics for computer science and engineering.

Aug 30, 2021
All Files ‐ Post Files

# Basic Notation

A set is defined in the following way

$A = \{1, 2, 3, 4\}$

The symbol $$\in$$ is used to describe if something is in a set. Do not confuse with the subset symbol $$\subseteq$$ which means that a set is a subset of another set.

$$A$$ has four elements, $$1 \in A, 2 \in A, 3\in A, 4 \in A$$.

You can also show that $$A$$ has $$2^4=16$$ subsets. For example.

$\{1\} \subseteq A$

$\{1, 2, 3\} \subseteq A$

Important to not forget that the empty set $$\emptyset$$ is also a subset of $$A$$ therefore $$\emptyset \subseteq A$$. Also that $$A$$ is also a subset of itself $$A \subseteq A$$ also called the improper subset.

# Notation of Numerical Sets

The set $$\mathbb{N}$$ is the set of natural numbers. Depending of several factors might begin with a $$0$$ or $$1$$. Here it will begin with 0.

$\mathbb{N} = \{0, 1, 2, ... \}$

To be more precise it is the set of all non-negative integers, reffered to as natural numbers. If you wan to make sure to declare that this set begins with 0 you can write.

$\mathbb{N}_0 = \{0, 1, 2, ... \}$

$\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C} \subseteq ...$

Where $$\mathbb{Z}$$ is the set of all negative and positive integers. Where $$\mathbb{Q}$$ is the set of all numbers which can be described as a qoute in the following way.

$\left \{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \neq 0 \right\}$

You can also write it with a colon in the following way.

$\left\{ \frac{a}{b} : a, b \in \mathbb{Z}, b \neq 0 \right\}$

Where $is the set of all finite and infinite decimal numbers such as $$\sqrt{2}$$ and $$\pi$$, such that cannot be described as a qoute of two numbers. Where $$\mathbb{C}$$ is the set of all complex numbers which can be described in the following way. $\left\{ a + b\sqrt{-1} \mid a, b \in \mathbb{R} \right\}$ or more properly $\left\{ a + bi \mid a, b \in \mathbb{R} \right\}$ Writing a set in the following way. $A = \left\{1, 3, 5, 7 ... \right\}$ may be inprecise since it may be interpreted in another way then the author intended. Therefore the following notation is better for clarity and correctness. $A = \left\{2n+1 \mid n \in \mathbb{N} \right\}$ Although keep in mind that if $$\mathbb{N}$$ in the context you are writing in does not start at $$0$$ must then be written as. $A = \left\{2n-1 \mid n \in \mathbb{N} \right\}$ # Set Combinations ## Foundational • Union - $$A \cup B$$ • Intersection - $$A \cap B$$ • Complement - $$A^c$$ ## Non foundational With their corresponding equivalence in terms of foundational combinations. • Set difference - $$A \setminus B$$ $$A \setminus B = A \cap B^c$$ • Symmetric difference - $$A \Delta B$$ • $$A \Delta B = (A \setminus B) \cup (B \setminus A)$$ • $$A \Delta B = (A \cup B^c) \cup (A \cap A^c)$$ • $$A \Delta B = (A \cup B) \setminus (A \cap B)$$ • $$A \Delta B = (A \cup B) \cap (A \cap B)^c$$ Priority rule — The component ex: $$A^c$$ has the highest priority when evaluating an expression, think of it as $$(A)^c$$. # Cartesian Product Def: Let $$A$$, $$B$$ be two sets. The cartesian product of $$A$$ and $$B$$ is the following set. $A \times B = \left\{(a, b) \mid a \in A, b \in B\right\}$ which is the set of all ordered pairs $$(a, b)$$ where $$a \in A$$ and $$a \in B$$. Def: The size of a set $$A$$ is the amount of elements in A and is written as $$|A|$$. For example: $A = \left\{x \mid x \in \mathbb{Z}, x^2\right\}$ evaluates to $A = \{0, \pm 1, \pm 2\}$ where $|A| = 5$ A priori $$|A| \in \mathbb{N} \cup \{\infty\}$$ Clause 1: $$|A \times B| = |A| \times |B|$$. Proof: Obvious. Ex: $$A = \{1, 2\}$$,$B = {3, 4, 5}. Then.

$A \times B = \left\{(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)\right\}$

Notation: $$A \times A = A^2$$. It is important to remember that this denotes the cartesian product not a multiplication of numbers.

Note: $$A \times B$$ and $$B \times A$$ are in general two different sets but they have the same size.

## Iterated Cartesian Product

In general: $$n$$ amount of sets $$A_1, A_2, ..., A_n$$.

$\prod_{i=1}^{n} A_i = A_1 \times A_2 \times ... \times A_n = \{(a_1, a_2, ... a_n) \mid a_i \in A_i, i=1, ... n\}$

The general multiplication principe says that

$\left|\prod_{i=1}^{n}A_i\right| = \prod_{i=1}^{n} |A_i|$

Notation: $$A \times A \times ... \times A = A^n$$.

Important example: $$\mathbb{R}^n$$ (n-dimensional euclidian space).

Def: Let $$A$$ be a set. The power set for $$A$$, which is written as $$\wp(A)$$ or $$2^A$$, is the set of which the elements are all subsets to $$A$$.

Ex: $$A=\{1, 2, 3\}$$

$\wp(A) = \left\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\right\}$

Notice that, $$\left| \wp(A) \right | = 8 = 2^3 = 2^{|A|}$$, which isn’t a coincidence.

Clause 2: $$\left| \wp(A) \right | = 2^{|A|}$$ is true for every set $$A$$.

Proof: Let $$|A| = n$$, list all of $$A$$s elements in some arbritrary order, \$A = {a_1, a_2, … a_n}. We can setup a one to one correspondence (bijection) between the subsets to $$A$$ and all n-digit binary numbers.

Idea: Let $$B \subseteq A$$ and let $$i \in \{1, ..., n\}$$. $$a_i \in B \Leftrightarrow 1$$ and $$a_i \notin B \Leftrightarrow 0$$.

Then

$\wp(A) = \left\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\right\}$

Can be made into the following set of binary numbers.

$\{000, 100, 010, 001, 110, 101, 011, 111\}$

Therefore there exists an equivalent amount of subsets as there is n-digit binary numbers.

But an n-digit binary member can be thought of as an element in $$\{0, 1\}^n$$. Also known as the n-fold cartesian product of the set $$\{0, 1\}$$. According to the multiplication principle the following can be written.

$\left|\{0, 1\}^n\right| = \left|\{0, 1\}\right|^n = 2^n = 2^{|A|}$

# Important Note

The set term is more subtle then you might perceive it as.

Def: A set $$A$$ is said to be normal if it does not include itself as an element.

This seems like it would not happen simply because it seems impossible. However it does.

Ex: The set of all infinite sets.

Lets say that $$N$$ is the set of all normal sets.
Question: Is $$N$$ normal? The following statements can be said.
1. $$N$$ is normal
2. $$N$$ is not normal
This is a logical paradox. For $$N$$ to be normal it should not contain itself as an element. But if $$N$$ itself is normal then it should be contained within itself but which it cannot do.