## 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(n_{o}) is true for some natural number
no and if P(k) is true for all n_{o} < k < m implies
that P(m) is true, then P(n) is true for all natural numbers n >
n_{o}.

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