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


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\}



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.

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


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

Table of Content