A Math Review

Relations

A relation is a subset of a cross product, i.e. R ⊆ A × B. A is the domain and B is the codomain. If (a,b) ⊆ R we write aRb. The inverse R^–1 ⊆ B × A is {(b,a) | aRb}.

Example: ≤ ⊆ N × N, and (5,7) ∈ ≤, so we can write 5 ≤ 7.

For R ⊆ A × A we define:

• R is reflexive iff ∀a. aRa
• R is irreflexive iff ∀a. ¬aRa
• R is symmetric iff ∀a b. aRb ⇒ bRa
• R is antisymmetric iff ∀a b. aRb ∧ bRa ⇒ a=b
• R is transitive iff ∀a b. aRb ∧ bRc ⇒ aRc
• R is total iff ∀a b. aRb ∨ bRa

More definitions

• R is an equivalence relation iff it is reflexive, symmetric, and transitive
• R is a partial order iff it is reflexive, antisymmetric, and transitive
• R is a total order iff it is asymmetric, transitive, and total

If R ⊆ A × B and S ⊆ B × C then the composition of R and S is S o R = {(a,c) | ∃b. aRb ∧ bSc}

Functions

A relation f ⊆ A × B is called a function iff every element of A appears exactly once as the first element of a pair in f. In this case we write f : A → B. If f is a function and (a,b) ∈ f we write f a = b, or f(a) = b, and say b is the value of f at a. The range of f is {b | ∃a. b = f a}.

Since functions are relations and therefore sets, we can write them in set notation, but there is also a nice short-cut called lambda-notation. These examples are all equivalent:

More examples of functions

If f is a function, do not say "the function f(x)" unless the function f when applied to x actually yields a function. Also do not say things like "the function n²" because n² is a number. The function you probably have in mind is λn. n².

Function iteration

• f⁰(x) = x
• f¹(x) = f(x)
• f²(x) = f(f(x))
• f³(x) = f(f(f(x)))
• ...
• fⁿ⁺¹(x) = f(fⁿ(x))

Be careful, though, because many mathematicians don't know the difference between sin²θ and (sin θ)², or they choose to blur the distinction and expect readers to figure out what they mean by context.

For f: A → B,

• f is a surjection (i.e., f maps A onto B) iff ∀b. ∃a. f a = b
• f is an injection (i.e., f maps A one-to-one to B) iff ∀a. ∀b. a ≠ b ⇒ f a ≠ f b
• f is a bijection, a.k.a. a one-to-one correspondence iff f is a surjection and an injection

If f is a bijection from A to B, then f^–1 is a bijection from B to A. Also ∀ a. f^–1(f a) = a and ∀ b. f(f^–1b) = b.

Cardinality

The cardinality of a set A is denoted |A| and obeys these axioms:

• |A| = |B| iff there exists a bijection from A and B.
• |A| ≤ |B| iff there exists an injection from A to B.
• |A| < |B| iff |A| ≤ |B| and |A| ≠ |B|

Finite and Infinite Sets

A set is infinite iff there is a bijection between it and a proper subset of itself. A set is finite iff it is not infinite.

Example: N is inifinite because λn.2n is a bijection from N to {0, 2, 4, 6, 8, ...}

If A is finite then there exists a bijection from it to {1, 2, ... k} for some k ≥ 0 in which case we define |A| = k. The cardinality of N is ℵ₀. A is countable iff A is finite or |A| = ℵ₀.

Examples:

Z is countable because λn. if even(n) then –n/2 else (n+1)/2 is a bijection from N to Z.

N × N is countable because this picture shows a bijection:

By a similar argument, Q, Nⁱ, and any countable union if countable sets are all countable.

Cantor's Theorem: For any set A, |A| < |2^A|. Proof: Clearly |A| ≤ |2^A|, so we only have to show |A| ≠ |2^A|. Proceed by contradiction assuming assume |A| = |2^A| which implies there is a function g mapping A onto 2^A. Consider Y = {x | x ∈ A ∧ x ∉ g(x)}. Is Y ∈ 2^A? No. Is Y ∉ 2^A? No. Thus g does not exist.

Similar arguments to Cantor's theorem show that the following sets are uncountable

• {x | x ∈ R ∧ 0 < x < 1}
• {f | f : N → N}
• R (because λx. (1/π)tan^–1x + (1/2) is a bijection to <0,1>)
• R × R

The fact that {f | f:N→N} is uncountable means that there are functions for which no computer program can be written to solve, because programs are strings of symbols from a finite alphabet and thus there are only a countably inifinite number of them.

Numbers

Numbers can be defined in terms of sets, but we're not showing how do to that here. Just know about

• Natural numbers (N = {0, 1, 2, 3, ...})
• Integers (Z)
• Rational numbers (Q)
• Real numbers (R)
• Complex numbers (C)

For natural numbers

• Addition: x⁽¹⁾y = x + y
• Multiplication: x⁽²⁾y = x × y = x + x + ... + x [y x's]
• Exponentiation: x⁽³⁾y = x^y = x^y = x × x × ... × x [y x's]
• Tetration: x⁽⁴⁾y = x^^y = x ^ x ^ ... ^ x [y x's] (also called hyper4 or power-tower)
• Pentation: x⁽⁵⁾y = x^^^y = x ^^ x ^^ ... ^^ x [y x's]
• And on and on....

Addition, multiplication, and exponentiation work for real numbers too. There are also "inverses"

• Subtraction: x–y = the z such that y+z=x
• Division: x÷y = the z such that y×z=x
• Logarithm: log_y(x) = the z such that y^z=x
• And there are "inverses" of the operators beyond exponentiation as well

Also important:

• The floor of a real number x, denoted ⌊x⌋, is the largest integer ≤ x.
• The ceiling of a real number x, denoted ⌈x⌉, is the smallest integer ≥ x.

Exponents and Logarithms

(This section is courtesy of Phil Dorin)

Examples

• log₂ 1024 = 10 since 2¹⁰ = 1024
• log₁₀ 1000 = 3 since 10³ = 1000
• log₁₀ 0.01 = –2 since 10^–2 = 0.01

Properties

Computing Some Logs

• log₁₀ 1 = 0 [by definition]
• log₁₀ 2 ≈ 0.3 [Example above]
• log₁₀ 4 = 2 log₁₀ 2 ≈ .60
• log₁₀ 8 = 3 log₁₀ 2 ≈ .90
• log₁₀ 10 = 1 [by definition]
• log₁₀ 9 ≈ 0.95 [interpolating from log₁₀ 8 and log₁₀ 10]
• log₁₀ 3 = (1/2) log₁₀ 9 ≈ .48
• log₁₀ 6 = log₁₀ 2 + log₁₀ 3 ≈ .775 ≈ .78
• log₁₀ 7 ≈ .84 [interpolating from log₁₀ 6 and log₁₀ 8]
• log₁₀ 5 = log₁₀ 10 - log₁₀ 2 ≈ .70

How well did we do?

Not bad! Let's keep going...

• log₁₀ 11 ≈ log₁₀ ( 100 / 9 ) = 2 – log 9 = 1.05
• log₁₀ 12 = log₁₀ 3 + log₁₀ 4 ≈ 1.08
• log₁₀ 13 ≈1.115 [interpolating from the logs immediately above and below]
• log₁₀ 14 = log₁₀ 2 + log₁₀ 7 ≈ 1.15
• log₁₀ 15 = log₁₀ 3 + log₁₀ 5 ≈ 1.18
• log₁₀ 16 = 4 log₁₀ 2 ≈ 1.20
• log₁₀ 17 ≈ 1.225 [interpolating]
• log₁₀ 18 = log₁₀ 2 + log₁₀ 9 ≈ 1.25
• log₁₀ 19 ≈ 1.28 [interpolating]
• log₁₀ 20 = log₁₀ 10 + log₁₀ 2 ≈ 1.30
• log₁₀ 21 = log₁₀ 3 + log₁₀ 7 ≈ 1.32
• log₁₀ 22 = log₁₀ 2+ log₁₀ 11 ≈ 1.35
• log₁₀ 23 ≈ 1.365 [interpolating]
• log₁₀ 24 = log₁₀ 3 + log₁₀ 8 ≈ 1.38
• log₁₀ 25 = 2 log₁₀ 5 ≈ 1.40
• log₁₀ 30 = 1 + log₁₀ 3 ≈ 1.48
• log₁₀ 40 = 1 + log₁₀ 4 ≈ 1.60
• log₁₀ (0.2) = log₁₀ (2/10) = log₁₀ 2 -1 ≈ -0.70
• log₁₀ (0.3) = log₁₀ 3 -1 ≈ -0.52

Using logs to estimate

• 23⁴⁷ = 10^{log(23^47)} = 10^{47 log 23} ≈ 10^47(1.365) ≈ 10^{48(1 + 1/3)} = 10⁴⁸⁺¹⁶ = 10⁶⁴
  [calcuator says 1.002786070953 × 10⁶⁴]
• 898²⁵ = 10^{25 log 898} ≈ 10^{25 log 900} ≈ 10^25(2.95) = 10^295/4 = 10^73.75 ≈ 6 × 10⁷³
  [calcuator says 6.790604183554 × 10⁷³]

More Approximations

(This section is courtesy of Phil Dorin)

• e ≈ 2.718
• 1 / e ≈ 0.368
• π ≈ 3.1416
• 1 / π ≈ 0.318
• Stirling's Approximation: n! ≈ (n / e)ⁿ × sqrt(2πn)
• π seconds ≈ 1 nanocentury
• π × 10⁹ seconds ≈ one century (with an error of less than one-half of one percent)

Big Numbers

Don't miss Robert P. Munafo's big numbers pages.

Other Topics

Also useful in computer science, but not covered here:

• Counting principles (pigeonhole, addition, multiplication)
• Permutations
• Combinations
• Probability
• Recurrence Relations