• Injective: $a \neq a’ \rightarrow f(a) \neq f(a’)$
• Surjective: $\forall b\in B, \exists a\in A, f(a) = b$
• Bijective

$\mathbb{N} = \mathbb{Z}$
Countable = finite or countably infinite
Cantor’s Theorem
For any non-empty set $A$, $|A|\lt |P(A)|$. This can be proven by diagonalization. $S = a\in A: a\notin f(a)$ $S$ is defined by diagonalization so that $S$ cannot equal any $f(a)$.
Continuum Hypothesis (Hilbert’s 1st Problem)
There is no set $S$ such that $|\mathbb{N}|\lt |S|\lt |P(\mathbb{N})|$

String encoding: Computational problems can be serialized into a string

Computational Complexity

• Every multitape TM has an equivalent single tape TM.
• Running time depends on the particular model you choose
• Running time is defined as $T_A(n) = max{# \text{steps A takes on I}}$ (max input instance)
• intrinsic complexity is defined by $min$ (min algorithm).
• Entscheidungsproblem: Decide whether a given statement is valid with a given set of axioms
• To compute summations:
  • Rough bounding
  • Exact computation
  • Induction
  • Telescoping series ($\frac{1}{i(i+1)}$)
  • Comparison with an integral
• Master Method
  For $T(n) \le a\dot T(\frac{n}{b}) + O(n^d)$,
  • $a = b^d$, $O(n^dlog n)$
  • $a < b^d$, $O(n^d)$
  • $a > b^d$, $O(n^{log_ba})$

Countable:

• countable cartesian product of countable sets
  • Prime factorization
• Countable union of countable sets
• Set of Finite Subsets of Countable Set
  • Induction