Theo's Math Journal

An alphabet is a finite, nonempty set Σ of symbols. For example: Σ = {a, b} or Σ = {0, 1} or Σ = {a, b, c, d, e, f, g, h, i, j,...

A function is a rule that assigns one element to a unique (one and only one) element. Examples S1 = {a, b, c} S2 = {w, x, y, z} f: S1 ...

Background:  This proof is often used for the analysis of various algorithms. Example:  1 + 2 + ... + 100 = (100 * 101) / 2 If we wanted...

Length 0:  λ (lambda, the empty string) Length 1: 0, 1 Length 2: 00, 10, 01, 11 There is a useful recursive technique for finding all s...

For all n ≥ 0, if |S| = n, then |2 S | = 2 n Proof by induction on n. Base case: Consider a set S with 0 elements. Then S = ∅ so 2 S = ...