Even: $\{x \in \mathbb{Z} 2|x \in \mathbb{Z}\}$, Odd: $\{x \in \mathbb{Z} 2|(x-1) \in \mathbb{Z}\}$ Cartesian Product: $A\times B = \{(a, b) | a\in A \land b\in B\}$ The Fibonacci Sequence: defined (0, 0), (1, 1) for base case.

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...

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))$ 两个数总有正或反联系

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

• 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

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)$ 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)$

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)$

Compare Cardinality

$|A| \leq |B| \iff (\exists \text{injection} A \hookrightarrow B)$, $|A| \geq |B| \iff (\exists \text{surjection} A \rightarrowtail B)$ Cantor's Theorem: $|\mathcal{P}(S)| > |S|$

Number Theory

coprime(relatively prime): gcd(a,b) = 1 1.Bezout's Lemma: $\exists am+bn=1$ 2.Euclid's Lemma: $a|bc \implies a|c$ when $gcd(a,b)=1$ 3.Euclid's Lemma(p=prime): $p|bc \implies p|b \lor p|c$ Multiplicative Inverse (MIRP): $ac \equiv 1 \pmod b$

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))$

Order: $ord_p(n) = max\{a\in \mathbb{N} | p^a|n\}$ -> expressed as $n=p_1^{ord_{p_1}(n)}p_2^{ord_{p_2}(n)}...$ $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\}}$

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: check coprime for all modular (broken down by prime^n factorization), 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$