Discrete-math 24

Cardinality #definition

\begin{matrix} Sets A, B are said to have the same cardinality (size, to some extent) iff there exists \\ a bijective function f : A \to B \\ Denoted as A \sim B or | A | = | B | \end{matrix}

\begin{matrix} For each n \in N \\ Define I_{n} = {1, 2, \dots, n} \\ I_{0} = {} = \emptyset \\ Set A is called finite iff there exists n \in N \cup {0} \\ such that A \sim I_{n} \\ In this case, we denote it as | A | = n \\ If there is no such n, then A is called an infinite set \end{matrix}

\begin{matrix} Let \sim be a relation on some set of sets \\ \sim is reflexive, \forall A \in X : A \sim A, we use I_{A} : A \to A to show it \\ \sim is symmetric, A \sim B ⟹ B \sim A, we use f^{- 1} : B \to A to show this \\ \sim is transitive, A \sim B \land B \sim C ⟹ A \sim C, we use (g \circ f) : A \to C to show this \\ ⟹ \sim is an equivalence relation \end{matrix}

\begin{matrix} Z \sim N \\ Proof: \\ Let f : Z \to N, f (z) = {\begin{cases} 2 z + 1 & z \geq 0 \\ - 2 z & z < 0 \end{cases} \\ Let g : N \to Z, g (n) = {\begin{cases} - k & n = 2 k, k \in N \\ k & n = 2 k + 1, k \in N \cup {0} \end{cases} \\ (g \circ f) (z) = g (f (z)) = z ⟹ (g \circ f) = I_{Z} \\ (f \circ g) (n) = f (g (n)) = n ⟹ (f \circ g) = I_{N} \end{matrix}

\begin{matrix} N \times N \sim N \\ Proof: \\ Let N \times N be an infinite chess-board: \\ (\begin{array}{cc} 1 & 2 & 3 & 4 & \dots \\ 1 & (1, 1) & (1, 2) & (1, 3) & (1, 4) & \dots \\ 2 & (2, 1) & (2, 2) & (2, 3) & \dots & \dots \\ 3 & (3, 1) & (3, 2) & \dots & \dots & \dots \\ 4 & (4, 1) & \dots & \dots & \dots & \dots \end{array}) \\ Let us count pairs by diagonals: \\ (1, 1) = 1 \\ (2, 1) = 2, (1, 2) = 3 \\ (1, 3) = 4, (2, 2) = 5, (3, 1) = 6 \\ (4, 1) = 7, (3, 2) = 8, (2, 3) = 9, (1, 4) = 10 \\ \dots \\ We can get to each pair in a finite number of steps \\ ⟹ N \times N \sim N \\ Formal function: \\ f ((n, m)) = \frac{1}{2} (n + m - 1) (n + m) \end{matrix}

\begin{matrix} Set A is called countable if it is finite or A \sim N \\ Otherwise A is not countable \\ Cardinality of N is denoted as | N | = ℵ_{0} \end{matrix}

\begin{matrix} Let A, B be sets \\ | A | \leq | B | iff exists f : A \to B which is injective \\ This is equivalent (without proof) to: \\ | A | \leq | B | iff exists g : B \to A which is surjective \end{matrix}

\begin{matrix} | N | < | R | \\ And is denoted as: | R | = ℵ_{1} \\ | R | < | P (R) | = ℵ_{2} \\ | P (R) | < | P (P (R)) | = ℵ_{3} \\ And so on \end{matrix}

\begin{matrix} Let A be a set \\ Then | A | < | P (A) | \\ Proof: \\ Let g : A \to P (A), g (a) = {a} \\ g is injective ⟹ | A | \leq | P (A) | \\ Now, let f : A \to P (A) be a bijection \\ Let B = {a \in A | a \notin f (a)} \\ B \subseteq A ⟹ B \in P (A) \\ ⟹ \exists x \in A : f (x) = B \\ Case 1. x \in B \\ x \in B ⟹ x \notin f (x) = B ⟹ x \notin B - Contradiction! \\ Case 2. x \notin B \\ x \notin B ⟹ x \notin f (x) ⟹ x \in B - Contradiction! \\ ⟹ ∄ x \in A : f (x) = B ⟹ f is not surjective ⟹ ∄ f : A \to P (A) that is a bijection \\ ⟹ | A | \neq | P (A) | ⟹ | A | < | P (A) | \end{matrix}