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

Group Theory:

\emptyset \subset [6] \subset \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}

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)

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): \bigcap_{i\in I}A_i = \{x\in U | \forall i\in I, x\in A_i\}

Indexed Unions(\bigcup): \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\}

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


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

DeMorgan's Law

Distributive Law for Connectives:

Other Laws:



The Fibonacci Sequence:

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


Let R \subseteq S \times S:

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)

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

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

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




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.

Image & Preimage

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

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)


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

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

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.


TODO 021

Number Theory

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

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)

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)


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)


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

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

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

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

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:

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


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


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)


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

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}

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: 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 {n + k - 1 \choose k - 1}

Table of Content