kHx8a

Discrete Mathematics Lecture 1 — Set Theory

University course in discrete mathematics for computer science and engineering.

Aug 30, 2021
Downloads ‐ HTML, Markdown, PDF
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\)
A \cup B
\(A \cup B\)
  • Intersection - \(A \cap B\)
A \cap B
\(A \cap B\)
  • Complement - \(A^c\)
A^c
\(A^c\)

Non foundational

With their corresponding equivalence in terms of foundational combinations.

  • Set difference - \(A \setminus B\)
A \setminus B
\(A \setminus B\)

\(A \setminus B = A \cap B^c\)

  • Symmetric difference - \(A \Delta B\)
A \Delta B
\(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\} \]

Figure of A \times B and B \times A plotted on a coordinate system.
Figure of \(A \times B\) and \(B \times A\) plotted on a coordinate system.

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.

Russels Paradox

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.

The paradox

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.

References