Finite Mathematics

Robert S. Wilson

4. Natural Numbers

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

n + 1.

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

#(A )

Definition 4.6: If m and n are natural numbers define

m < n

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.

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

m < n

m = n

or

n < m

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

#(S - {s }) = n - 1.

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

(n + 1) - 1 = n

b) If n is any nonzero natural number,

(n - 1) + 1= n

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

#(S) = m.*

5. Counting