Finite Mathematics

Robert S. Wilson

5. Counting

Theorem 5.1: (The Well Ordering Principle) Every nonempty set of natural numbers has a smallest element.

Theorem 5.2: (Strong Induction) Let P(n) be a statement which depends on a natural number n. If P(no) is true for some natural number no and if P(k) is true for all no < k < m implies that P(m) is true, then P(n) is true for all natural numbers n > no.

Theorem 5.3: No set is equivalent to a proper subset of itself.

Theorem 5.4: (The Well-Definedness of Cardinality) Let S be a set. If there are natural numbers m and n such that #(S ) = n and #(S ) = m, then m = n.

Theorem 5.5: Let A and B be sets. There is a one to one correspondence

if and only if #(A ) = #(B ).

Theorem 5.6: Let m and n be two natural numbers.

m + 1 = n + 1

if and only if

m = n.

Theorem 5.7: (Uniqueness of Predecessors) n - 1 = m - 1 if and only if n = m.

Theorem 5.8: If S is any set, then

{ } x S = S x { } = { }

Theorem 5.9: Let S be any set and let {a} be a set with one element. Then #(S x {a}) = #(S).

Theorem 5.10: Every nonempty set of natural numbers has a largest element.


6. Arithmetic