Review Note

Basics about Mathematics

Basic Groups

Even: $\{x \in \mathbb{Z} 2|x \in \mathbb{Z}\}$ Odd: $\{x \in \mathbb{Z} 2|(x-1) \in \mathbb{Z}\}$ Natural(N): $\{0, 1, 2,...\}$

• [n] = $\{1, 2, ..., n\}$ Rational(Q): $\mathbb{Q}=\{\frac{a}{b} | a\in\mathbb{Z} \land b\in\mathbb{Z}^{+}\}$

Group Theory:

• N closed under: sum, product

• Z closed under: sum, difference, product, division(if divisible)

• Z/R/Q closed under: sum, difference, product, division(non-zero)

• Integer exponentiation is not within group

Basic Set Theory

Proper Subset($\subset$ or $\subsetneq$): $A\subseteq B$ and $A\neq B$ Power set: Let $A$ be a set, $\mathcal{P}(A)$ is the set of all subset of $A$. (including A itself)

• $\emptyset, A \subseteq \mathcal{P}(A)$.

• $\mathcal{P}(A) = {\emptyset, {a}, {b}, A}$

• :warning: $\mathcal{P}(\emptyset) = \{\emptyset\}$

• :warning: $\mathcal{P}(\mathcal{P}(\emptyset)) = \{\emptyset, \{\emptyset\}\}$

• :warning: $\mathcal{P}(\mathcal{P}(\mathcal{P}(\emptyset))) = \{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \{\emptyset, \{\emptyset\}\}\}$

• $P(P(P({})))={{}, P((P({})))}}$

Complement($A^\complement$ or $\overline{A}$, or $A^\mathsf{c}$): $\overline{A}=\{x\in U | x\notin A\}=U\backslash A$

Index: $\{A_i\}_{i\in I} = \{A_i | i\in I\}$ is an family of sets indexed by $I$

Indexed Intersections($\bigcap$): $<span class="arithmatex"><span class="MathJax_Preview">\bigcap_{i\in I}A_i = \{x\in U | \forall i\in I, x\in A_i\}</span><script type="math/tex">\bigcap_{i\in I}A_i = \{x\in U | \forall i\in I, x\in A_i\}$

Indexed Unions($\bigcup$): $<span class="arithmatex"><span class="MathJax_Preview">\bigcup_{i\in I}A_i = \{x\in U | \exists i\in I, x\in A_i\}</span><script type="math/tex">\bigcup_{i\in I}A_i = \{x\in U | \exists i\in I, x\in A_i\}$

Cartesian Product: $A\times B = \{(a, b) | a\in A \land b\in B\}$

• Cartesian product with emptyset is emptyset

Alternating Quantifiers

When both $\exists$ and $\forall$ in a statement, order matters. "All people loves some people"

Let $P(x, y)$ denotes "x loves y"

1. $(\forall x \in U)(\exists y \in U)P(x, y)$ means "everybody loves somebody."
2. $(\exists y \in U)(\forall x \in U)P(x, y)$ means "there is somebody who is loved by everybody."

Connectives

Implication: $P \implies Q \equiv \lnot P \lor Q$

DeMorgan's Law

• $\lnot(P\land Q)\equiv \lnot P\land\lnot Q$, $\lnot(P\lor Q)\equiv \lnot P\lor\lnot Q$

• $\overline{A \cap B} = \overline{A} \cup \overline{B}$, $\overline{A \cup B} = \overline{A} \cap \overline{B}$

Distributive Law for Connectives:

• $P\land (Q\lor R)\equiv (P\land Q)\lor (P\land R)$

• $P\lor (Q\land R)\equiv (P\lor Q)\land (P\lor R)$

Other Laws:

• contraposition: $P\implies Q \equiv \lnot Q \implies P$

• converse: $Q\implies P$ is converse of $P\implies Q$

• inverse: $\lnot P \implies \lnot Q$ is inverse of $P\implies Q$

• $\text{converse} \equiv \text{inverse}$

Induction

Sequence

The Fibonacci Sequence:

• fn = 0 if n = 0 (base case)

• fn = 1 if n = 1 (base case)

• fn = f_{n-1) + f_{n-2}} (inductive step)

Weak Induction (PMI)

Claim: $(\forall n \in \mathbb{N})P(n)$
Proof: We processed by induction on $n \in \mathbb{N}$

- Base Case: P(0) holds because ____.

- Inductive Step: Let $n \in \mathbb{N}$ s.t $P(n)$ holds. (IH) Show $P(n+1)$ holds.

- By PMI, we have $(\forall n \in \mathbb{N})P(n).$

Strong Induction (SPMI)

Claim: $(\forall n \in \mathbb{N})P(n)$
Proof: We proceed by strong induction on $n\in \mathbb{N}$

- Base Case: P(0) holds because... (may be more base cases)

- Inductive Step: Let $n \in \mathbb{N}$ with $n \geq \text{last base case}$ s.t $(\forall i \in \mathbb{Z})(0 \leq i \leq n \implies P(i))$ holds. Show $P(n+1)$ holds.

- By SPMI, we conclude...

TODO: practice prove prime/product of prime TODO: practice Game of Chomp

Well Ordering Property

TODO: might not be in text, see lecture note October 5, 2020 Idea of Infinite Descent

Relations

Let $R \subseteq S \times S$:

• reflexive(R): iff $(\forall x \in S)((x,x) \in R)$ (any element is related to itself) 自己和自己比永远存在

• irreflecsive(IR): iff $(\forall x \in S)((x,x) \notin R)$ (no element is related to itself, notice it is not the opposite of relfecsive) 自己和自己比永远不存在

• symmetric(S): iff $(\forall x,y \in S)((x, y) \in R \implies (y, x) \in R)$ 正反永远成立

• antisymmetric(AS): iff $(\forall x,y \in S)((x, y) \in R \land (y, x) \in R \implies x = y)$ 正反成立则相等

• transitive(TR): iff $(\forall x, y, z \in R)((x, y)\in R \land (y, z)\in R \implies (x, z) \in R)$ 传递

• Total(To): $(\forall x, y \in S)(x \neq y \implies ((x, y) \in R \lor (y, x) \in R))$ 两个数总有正或反联系

Set	Relation	Ref	Irrefl	Symm	Antisymm	Trans
$\mathbb{R}$	$<$	N	Y	N	Y	Y
$\mathbb{Z}$	divisible	Y	N	N	N	Y
$\mathcal{P}(S)$	$\subseteq$	Y	N	N	Y	Y
$S$	$=$	Y	N	Y	Y	Y
$\mathbb{R}$	$\leq$	Y	N	N	Y	Y
$\mathcal{P}(S)$	$\subsetneq$	N	Y	N	Y	Y

Ordering Relation

Partial Order: reflexive, antisymmetric, and transitive. ($S, R$ poset)

• $(\mathcal P(S), \subseteq)$, $(\mathbb{R}, \leq)$

Strict Partial Order: irefflexive, antisymmetric, and transitive. ($S, R$ strict poset)

• $(S, \subsetneq)$, $(\mathbb{R}, <)$

Total Order: partial(reflexive, antisymmetric, transitive), total.

• $(a, b) \prec (c, d) \iff ((a < c) \lor (a = c \land b < d))$

Equivalence Relations

Equivalence: reflexive, symmetric, and transitive Equivalence Class: $[x]_R = \{y \in S | (x, y) \in R\}$ Set of Equivalence Classes: $S/R = \{[x]_R | x \in S\}$ ($S/R$ forms a partition of $S$, breaking into {S_i}_{i\in I}) For Modulo m: $\mathbb{Z} /m \mathbb{Z} = \{[0]_m, [1]_m, ... [m-1]_m\}$

Partition

Partition:

• each non-empty: $(\forall [x]_R \in S/R)([x]_R \neq \emptyset)$

• intersection empty: $(\forall [x]_R, [y]_R \in S/R)([x]_R \neq [y]_R \implies [x]_R \cap [y]_R = \emptyset)$

• union complete: $\bigcup_{[x]_R \in S/R} [x]_R = S$

Functions

Function: $f:A \to B = f \subseteq A \times B$ Well-defined: $(\forall a \in A)(\exists b \in B)(f(a) = b)$ and $(\forall a, a' \in A)(a=a' \implies f(a)=f(a'))$ Identity: $Id_S: S \to S \text{ s.t. } (\forall x \in S)(Id_S(x) = x)$ Equality: $f : A\to B, g:A\to B$ be functions. $f = g \iff (\forall a \in A)(f(a) = g(a))$ Composition: $f(g(x)) = (f \circ g)(x)$ Inverse: $g = f^{-1} \iff f \circ g = id_B \land g \circ f = id_A$ when $f: A \to B$ and $g: B \to A$.

• $f \text{is invertible} \iff f \text{is a bijection}$

• inverse is unique

Image & Preimage

$f:A\rightarrow B$ be a function. Let $X \subseteq A \land Y \subseteq B$

• image: $Im_f(X)=\{b\in B | (\exists a \in X)(f(a) = b)\}$, $Im_f: \mathcal{P}(A) \rightarrow \mathcal{P}(B)$

• preimage: $PreIm_f(Y)=\{a\in A | f(a) \in Y)\}$, $PreIm_f: \mathcal{P}(B) \rightarrow \mathcal{P}(A)$

TODO: sample Image&Preimage Problem

Surjection, Injection, Bijection

surjection: $f:A \rightarrowtail B \iff Im_f(A) = B \iff (\forall x, y \in A)(f(x) = f(y) \implies x=y)$ injection: $f: A \hookrightarrow B \iff (\forall x, y \in A)(f(x) = f(y) \implies x=y) \iff (\forall x, y \in A)(x\neq y \implies f(x) \neq f(y))$

Schröder–Bernstein Theorem (CBS, injection): $(\exists f : A \hookrightarrow B) \land (\exists g : B \hookrightarrow A) \implies (\exists h : A \to B)$ Partition Principle: $(\exists f : A \hookrightarrow B) \iff (\exists g : B \rightarrowtail A)$

Cardinality

Finite: $(\exists n \in \mathbb{N})(f:[n] \to S \text{ is a bijection})$ Countable: Finite or Countably Infinite Countably Infinite: $|S| = |\mathbb{N}| = \mathcal{N}_0$

• $\mathbb{N}, 2\mathbb{N}, \mathbb{Z}, \mathbb{N}^2, \mathbb{Q}$

Uncountably infinite: $|S| > |\mathbb{N}|$

• $\mathcal{P}(\mathbb{N})$, $\mathbb{R}$, $(0, 1)$, $\{0, 1\}^{\mathbb{R}}$ (infinite zeros and ones)

Compare Cardinality

$|A| \leq |B| \iff (\exists \text{injection} A \hookrightarrow B)$ $|A| \geq |B| \iff (\exists \text{surjection} A \rightarrowtail B)$ $|A| = |B| \iff (\exists \text{bijection} A \to B)$

Cantor's Theorem: $|\mathcal{P}(S)| > |S|$

If $\{A_i\}_{i \in [n]}$ is countably infinite set, then $A_1 \times ... \times A_n = \prod_{i=1}^n {A_i}$ is a countably infinite.

Theorem: The union of countably infinite set $\{A_n\}_{n\in \mathbb{N}}$ is countably infinite.

• If $\{A_i\}_{i\in [n]}$ is a finite family of countably infinite sets, then the union is countably infinite

• If $\{A_i\}_{i\in \mathbb{N}}$ is a family of countable sets then the union is still countable

Diagonazation

TODO 021

Number Theory

prime: $n = ab \implies a=1 \lor b=1$ coprime(relatively prime): gcd(a,b) = 1

• Bezout's Lemma: $\exists am+bn=1$

• Euclid's Lemma: $a|bc \implies a|c$ when $gcd(a,b)=1$

• Euclid's Lemma(p=prime): $p|bc \implies p|b \lor p|c$

• Multiplicative Inverse (MIRP): $ac \equiv 1 \pmod b$

composite: $(\exists a,b \in \mathbb{Z})(1 < a \leq b < n \land n=ab)$

Greatest Common Divisor (GCD): $d=gcd(a,b) \iff d|a \land d|b \land (\forall x \in \mathbb{Z})(x|a \land x|b \implies x \leq d)$

• gcd(0, n) = n; gcd(0, 0) undefined

Bezout's Lemma

1. rewrite gcd: $(\exists x, y \in \mathbb{Z})(ax+by = gcd(a,b)))$
2. $(x,y \in \mathbb{Z} \land ax+by>0 \implies ax+by \geq gcd(a,b))$

Corollaries to Bezout's Lemma:

1. $t|a \land t|b \implies t|gcd(a,b)$
2. $gcd(a,b) | c \iff (\forall c \in \mathbb{Z})(\exists m, n \in \mathbb{Z})(c=am + bn)$
3. $(\forall m \in \mathbb{Z}^+)(gcd(ma, mb)= m \times gcd(a,b))$

Theorem (of divide gcd): $gcd(\frac{a}{gcd(a,b)}, \frac{b}{gcd(a,b)}) = 1$ for none zero a,b. Proposition (of plus): $a|b \land a | c \implies a| (bx+cy)$

Algorithms

Euclidean Algorithm: $gcd(my+x, y)=gcd(x, y)$, formally a sequence created by recursively divide.

Division Algorithm (DA): if $a, b \in \mathbb{Z}$ with $b > 0$, then there exists unique $q,r \in \mathbb{Z}$ s.t. $a=bq+r \land 0<=r<b$ Corollary to Division Algorithm: let $a, b, in \mathbb{Z}$ with $b!=0$. $a=bq+r \implies gcd(a,b) = gcd(b,r)$

• note that q and r doesn't have to be correct divisor or remainder TODO: understand division algorithm

LCM

• $lcm[a,b] = |b| \iff a|b$

• $lcm[ma, mb] = m \times lcm[a, b]$

Prime Factorizations

Fundamental Theorem of Arithmetic (FTA): Every integer n > 1 can be written as a product of primes in a unique way. TODO: The Infinitude of Primes might not be in the test

Order: $ord_p(n) = max\{a\in \mathbb{N} | p^a|n\}$

• so n can be expressed as $n=p_1^{ord_{p_1}(n)}p_2^{ord_{p_2}(n)}...$

GCD-LCM Theorem

We can express $a = \prod_{i=1}^n p_q^{a_i}$ $b = \prod_{i=1}^n p_q^{b_i}$ Then $gcd(a,b) = \prod_{i=1}^n p_i^{min\{a_i, b_i\}}$ $lcm(a,b) = \prod_{i=1}^n p_i^{max\{a_i, b_i\}}$

Corollary to GCD-LCM Theorem: $ab = gcd(a,b) \times lcm[a,b]$

Modular Arithmetic

$a \equiv b \pmod m \iff m | a-b \iff (\exists k \in \mathbb{Z})(a = b + km)$

Complete Residue System modulo m(CSRM): iff every integer is congruent to exactly one element in the set under modulo m

• The Least Non-negative Residues modulo m: $\{{0, 1, ..., m-1}\}$

• The Least Positive Residues modulo m: $\{1, 2, ..., m\}$

• The Least Absolute Residues modulo m:

  • if m is odd: $\{0, 1, -1, ..., \frac{m-1}{2}, -\frac{m-1}{2}\}$
  • if m is even: $\{0, 1, -1, ..., \frac{m-2}{2}, -\frac{m-2}{2}, \frac{m}{2}\}$

$\mathbb{Z} /m \mathbb{Z} = \{[0]_m, [1]_m, ..., [m-1]_m\}$

Calculation: add, subtract, product, and...

• $a \equiv b \pmod m \implies a^n \equiv b^n \pmod m$ for $n \in \mathbb{Z}^+$

• $ac \equiv bc \pmod m \implies a \equiv b \pmod {\frac{m}{gcd(c, m)}}$

Multiplicative Inverse (MIRP)

Multiplicative Inverse (MIRP): $ab\equiv 1 \pmod m)$ Existence of Inverse Corollary: $(\exists m \in \mathbb{Z})(ax \equiv b \pmod m) \iff gcd(a, m) | b Finding a inverse:

• check all number of b s.t. $gcd(a, b) = 1$ from $[0, b-1]$

Procedure for short:

1. try to turn into $\equiv 1$, check existence.
2. find one, then find equivalence class

Procedure for long:

1. or use gcd(m, left) check existence=1.
2. find the inverse mod 1, multiply and cancel with inverse into original equation to single x out.

Linear Diophantine Equations

Existence: $gcd(a, b) | c \implies (\exists{x, y \in \mathbb{Z}})(ax+by = c)$ Find: $(\exists (x_0, y_0)) \implies \{(x_0 + k(\frac{b}{gcd(a, b)}), y_0 - k(\frac{a}{gcd(a, b)}) | k \in \mathbb{Z})\}$ Procedure:

1. turn into mod, eliminate y.
2. solve modular x under m, turn into equation, fix k.
3. substitute x, solve for y.

The Chinese Remainder Theorem (CRT)

Procedure for combine: 0. check coprime for all modular (broken down by prime^n factorizatio)

1. start with biggest mod, turn into equation with k, substitute into other mod, simplify k, turn into equation with...

Combinatorial

The Pigeonhole Principle (PHP): if $|A|=n$, then $(\exists i \in [k])(|A_1|\geq \lceil \frac{n}{k} \rceil)$

Arrangement

k-arrangements: $\frac{n!}{(n-k)!}$ (arrange k<n seats for n people) permutation: $n!$ (arrange n seats for n people)

k-arrangements with repetition: $n^k$ (construct strings of n letter from k alphabets)

Selection

k-selection: ${n\choose k} = \frac{n!}{k!(n-k)!}$

• $k < 0 \lor k > n \implies {n\choose k} = 0$

The Binomial theorem: Let $x, y \in \mathbb{R} \land n \in \mathbb{N}$, then $(x+y)^n = \sum_{k=0}^n {n \choose k} x^ky^{n-k}$ TODO: understand binomial theorem

Selection with Repetition: ${n+k-1 \choose k-1} = {n+k-1 \choose n}$

• equal to the number of nonnegative integer solution to $x_1+x_2+...+x_k=n$.

Summary of Proof Techniques

Contraposition Double Containment Biconditional Imply Chain of Equivalence Prove bijection by construct inverse Diagonazation

TODO: 007-Non-Constructive Direct Proof TODO: 007-Indirect Proof

TODO-LIST

TODO: review previous exams and homework problems

Other Stuff

Diagonalzation proof Ordering relation proof Principle of Inclusion and Exclusion: formalize

What is a string?

Selection with Repetition

Selection: order no matter Repetition: Method: 0's and 1's $<span class="arithmatex"><span class="MathJax_Preview">{n + k - 1 \choose k - 1}</span><script type="math/tex">{n + k - 1 \choose k - 1}$