**Definition 4.1**: An **empty set** is a
set that has no elements.

**Theorem 4.1**: An
empty set is a subset of any set.

**Theorem 4.2**: Any
two empty sets are equal.

As a result of Theorem 4.2, we can refer to the empty set. The most commonly used notation for the empty set is the Greek letter

**Axiom 4**: The empty set is a
set.^{1}

We can now define the natural numbers. The first natural number is 0.

**Definition 4.2**: The number 0 is the
empty set.

**Definition 4.3**: If n is a natural
number, the **successor** of n is a natural number and is the set

Any natural number is obtained by taking successive successors starting from 0.

** **

**Notation**: If n is a natural number, we will denote the
successor of n by

**Theorem 4.3: (Weak
Induction)**: Let P (n ) be a statement which depends on a natural
number n. If

a) (anchor) P (0) is true,

and if

b) (induction) whenever P (k ) is true then so is P (k +1)

then P (n ) is true for all natural numbers n.

**Theorem 4.4**: A
natural number is a set.

**Definition 4.4**: If there is a one to one
correspondence between the elements of a collection of objects and
the elements of a natural number, then we say that the collection is
**finite**.

All collections of objects that we will be considering will be finite. When we say "set", we will mean finite set.

**Definition 4.5**: Let A be a set. We say
that A has **n elements** if there is a one to one correspondence
between A and the natural number n. In this case n is called the
**number of elements in A** or the **cardinality of A**.

**Notation**: The number of elements in a set A will be denoted
by

**Definition 4.6**: If m and n are natural
numbers define

if

If m __<__ n but m and n are not equal, we will write m <
n.

**Theorem 4.5**: Let
m and n be any natural numbers.

- m
__<__m. - m
__<__n and n__<__m, then m = n. - If m
__<__n and n__<__p then m__<__p.

**Theorem 4.6: (The
Trichotomy Law for Natural Numbers)**: If m and n are two natural
numbers then either

or

**Theorem 4.7: **Let
n be a natural number. If

then

**Theorem 4.8**:
Every nonzero natural number n has a largest element.

**Definition 4.7**: Let n be a nonzero
natural number. Then the largest element of n is called the
predecessor of n.

: We will denote the predecessor of n by n - 1.

**Theorem 4.9**: Let
S be a nonempty set with n elements. If

then

**Theorem 4.10:
**a) If n is any natural number,

b) If n is any nonzero natural number,

**Theorem 4.11**:
Any finite collection of natural numbers is a set.

**Theorem 4.12**:
If n is a natural number and

then there is a natural number m such that