Discrete Mathematics Note Chapter 2

发表于 2024-06-14 更新于 2024-07-23 分类于 note 阅读次数：本文字数： 1.6k 阅读时长 ≈ 6 分钟

Basic Structures: Sets, Functions, Sequences, and Sums

Sets

Definition: A set is an unordered collection of objects. The objects in are called elements. It is said to contain its elements.

$a \in A$: Element $a$ belongs to set $A$.

Four ways to describe

Roster method: listing elements between braces. $S = {1, 2, 3,} $
Brace notation with ellipses $S = \{1, 2, \ldots, 100\}$
Specification using set builder: $S = \{x | P(x)\}$
Venn diagrams:
1. $U$ is represented in rectangle.
2. Different sets represented in circles in the rectangle.

$\emptyset$: Empty set, a set that contains nothing.

$U$: Universal set, containing all objects.

Relations between Two Sets

Subset: $A \subseteq B$

$\emptyset \subseteq A, A\subseteq A$.

Proper Subset: $A \subset B \Leftrightarrow (A \subseteq B\ \land\ A \neq B)$.

Equal: $A = B \Leftrightarrow (A \subseteq B\ \land \ B\subseteq A)$.

Size: If there are exactly $n$ elements in $S$, we call $S$ is finite and $n$ is the cardinality of $S$.

Power Set: The set containing all subsets of a given set. Attention, its elements are sets.

$P(S) = \{X | X \subseteq S\}$.

$|P| = 2^{|S|}$, so if $S$ is finite, then $P$ is finite.

Five rules: $x \in P(S) \Rightarrow x \subseteq S$; $x S {x} P(S) $; $S \in P(S)$.

$P(A) \in P(B) \Rightarrow A \in B$; $A \subseteq B \Rightarrow P(A) \subseteq P(B)$.

The ordered n-tuple $(a_1, a_2, \ldots, a_n)$. $(x, y) \neq (y, x)$.

The Cartesian product of two sets: $A \times B = \{(a, b) | a \in A \land b \in B\}$

Truth Set of predicate $P$ in domain $D$ is $\{x | P(x)\}$.

Set operations

Operation Names

Union: $A \bigcup B = \{x | x \in A \lor x\in B\}$.

Intersection: $A \bigcap B = \{x | x\in A \land x \in B\}$. If $A \bigcap B = \emptyset$, then we call they are disjoint.

$|A \bigcup B| = |A| + |B| - |A \bigcap B|$.

Difference: $ A - B = {x | x A x B} = A B$.

Complement: $\overline A = \{x | x \notin A \land x \in U\} = U - A$.

Symmetric Difference: $A B = (A B) - (A B) $.

Set Identities

Four ways to prove:

show that $A \subseteq B$ and $B \subseteq A$.
Use logical equivalence to prove equivalent set definitions.
Use membership tables (like truth table).
Use previously proven identities.

Some proven identities:

De Morgan's laws: $\overline {(A \bigcup B)} = \overline{A} \bigcap \overline{B}$; $\overline {(A \bigcap B)} = \overline{A} \bigcup \overline{B}$.
Distributive laws: $A \bigcup (B \bigcap C) = (A \bigcup B) \bigcap (A \bigcup C)$; $A \bigcap (B \bigcup C) = (A \bigcap B) \bigcup (A \bigcap C)$.

Computer Representations

Use bit strings to represent.

First we know $U = {a_1, a_2, a_3 ,\ldots}$, and $|U| = n$.

Then we can use a bit string $s$ of length $n$ to represent any set, $s_i = 1$ if $a_i$ is in this set.

Functions

Definition

A function(mapping) $f$ from $A$ to $B$: \[ f : A \rightarrow B\\ \forall a \exists! b (a \in A \rightarrow b \in B \land f(a) = b ) \] $A$ is called the domain, $B$ is called codomain.

$f(a) = b$, then $b$ is called image of $a$, $a$ is called preimage of $b$.

$f(A) = \{f(a) | a \in A\}$ is called range, and it's a subset of $B$.

If $f$ is a function, we can call f maps $A$ to $B$.

$f(\emptyset) = \emptyset$, $f(\{ a \}) = \{ f(a) \}$.

$f(A \bigcup B) = f(A) \bigcup f(B)$.

$f(A \bigcap B) \subseteq f(A) \bigcap f(B)$.

Graph of Functions

The graph of the function $f$ is the set $\{ (a, b) | a \in A \land b = f(a) \}$.

Injective & Surjective Functions

Injective (One-to-one) functions hold that \[ \forall a \forall b (f(a) = f(b) \rightarrow a = b ) \] That is, every element in domain has a unique image.

Surjective (Onto) functions hold that \[ \forall b \in B \exists a \in A (f(a) = b) \] That is, every element in codomain has at least one preimage.

Bijection (One-to-one correspondence) is both one-to-one and onto.

Bijection's domain and codomain must have the same cardinality.

Monotonic Function

Monotonically (strictly) increasing: $x < y \rightarrow f(x) < f(y)$.

Monotonically (strictly) decreasing: $x < y \rightarrow f(x) > f(y)$.

Inverse Functions

If $f$ is a bijection, the inverse function of $f$ can be defined as $f^{-1}$, that $f^{-1}(y) = x\ \mathrm{iff}\ f(x) = y$. $(f^{-1})^{-1} = f$.

Otherwise, the inversion doesn't exist.

Composition

Let $g$ be a function from $A$ to $B$, and $f$ be a function from $B$ to $C$. Then the composition of $g$ and $f$ is \[ f\ \circ\ g (a) = f(g(a)) \] The range of $g$ must be a subset of the domain of $f$.

Simple Important Functions

Floor Function $\lfloor x \rfloor$ (greatest integer below $x$) and Ceiling Function $\lceil x \rceil$ (least integer above $x$) are commonly used.

Properties

Floor Properties

$x - 1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1$.
$\lfloor -x \rfloor = - \lceil x \rceil$.
$\lceil -x \rceil = - \lfloor x \rfloor$.
$\lfloor x + m \rfloor = \lfloor x \rfloor + m, \lceil x + m \rceil = \lceil x \rceil + m$, if $m$ is an integer.

Sequence and Summations

Definition

A sequence is a function from a subset of the set of integers $[N]$ to a set $S$. We use the notation $a_n$ to denote $f(n)$.

Note that the order in a sequence matters.

Geometric Progression

A sequence of the form $a, aq, aq^2, \dots, aq^{n-1}$.

Arithmetic Progression

A sequence of the form $a, a + d, a + 2d, \ldots, a + (n - 1)d$.

Summation

\[ \sum_{i=m} ^n a_i,\quad \sum _{x\in S} f(x) \]

$m$: lower bound, $n$: upper bound, $i$: index of summation;

$S$ should be a subset of the domain of $f$.

Useful Closed Form

$\large\sum\limits_{k = 0}^{n} ar^k = a \dfrac{r^{n + 1} - 1}{r - 1} (r \neq 0, 1)$.
$\large\sum\limits_{k = 1}^n k^2 = \dfrac{n (n + 1) (2n + 1)}{6}$.
$\large \sum \limits_{k = 1}^{n} k^3 = \dfrac{n^2 (n + 1)^2}{4} = \left(\dfrac{n (n + 1)}{2}\right)^2$.

The cardinality of an infinite set

Definition

The cardinality of a set $A$ is equal to the cardinality of a set $B$, denoted $|A| = |B|$, $\mathrm{iff}$ there exists a bijection from $A$ to $B$.

If there is an injection from $A$ to $B$, then we have $|A| \le |B|$. And if they have different cardinality, we say $|A| < |B|$.

Any real interval have the same cardinality, so they are equal. A bijection $f$ from $(a, b)$ to $(c, d)$: $\dfrac{f(x)-d}{c-d}=\dfrac{x-a}{b-a}$.

If a set is finite or has the same cardinality as $N_{+}$, it is called countable. Otherwise it's called uncountable.

The cardinality of countable infinite set $S$ is aleph null $\aleph_0$.

Amazing conclusions

$|Z| = |N^+|, |Q^+| = |N^+|$.

To prove $|Q^+| = |N^+|$, define $S = \{ (p,q) | p, q \in N^+ \}$.

$Q^+ \subseteq S$, because $r = \frac{p}{q} \in Q^+$, then $(p, q)$ must be in $S$.

$|S| = |N^+|$, because $(p, q)$ can be put in the $q$-th column of $p$-th row in the table, and we can pick them up in the antidiagonal order $(1, 1), (2, 1), (1, 2), (3, 1), (2, 2) \ldots$.

$N^+ \subseteq Q^+$.

Property

No infinite set has a smaller cardinality than a countable set.
The union of two countable set is countable.
The union of finite number of countable sets is countable.
The union of countable number of countable sets is countable.

Cantor Diagonalization Argument

Theorem: The set of real number between $0$ and $1$ is uncountable.

Proof:

$|N^+| \le |A|$

a function $f(n) = \frac{1}{n+1}$ performs $f : N^+ \rightarrow A$.

$| N^+ | \neq |A|$

Assume $A$ is countable, then let $A = \{ r_1, r_2, \ldots, r_n \ldots \}$.

Then list

$r_1 = 0.d_{11}d_{12}d_{13}\ldots$

$r_2 = 0.d_{21}d_{22}d_{23}\ldots$

$r_3 = 0.d_{31}d_{32}d_{33}\ldots$

$\ldots$

Now construct $x = 0.x_1x_2x_3\ldots$

$x_i = p$ if $d_{ii} \neq p$, otherwise $x_i = p + 1$.

$x$ is not in $A$ since it's not equal to any $r_i$.

How to describe the cardinality of $(0, 1)$? We can see that $|(0, 1)| = |R|$.

Let $f(x) = \tan x$.

There is an bijection from $( -\frac{\pi}{2}, \frac{\pi}{2} )$ to $(- \infty, + \infty)$.

Then $|(0, 1)| = |( -\frac{\pi}{2}, \frac{\pi}{2} )| = |R|$.

The cardinality of $R$ is aleph one $\aleph_1$.

In cantor diagonalization argument, we try to list the elements of the set $S$ in a matrix.

Then we pick the them up in antidiagonal order, to form a sequence.

Finally if the sequence has the same cardinality as $N^+$, we can prove $|S| = |N^+|$.

Computability

A function is computable is it can be computed by some programming language. Otherwise it's incomputable.

Schrőder-Bernstein Theorem: If $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$.

To prove $|A| = |B|$, find $f : A \rightarrow B$ and $g : B \rightarrow A$.

The Continuum Hypothesis asserts that there's no cardinal number $a$ such that $\aleph_0 < a < \aleph_1$.