MthT 430 Chapter 2a Numbers of Various Sorts
MthT 430 Chapter 2a Numbers of Various Sorts
Natural numbers N


We denote by N the set of counting numbers
1, 2, 3, ¼.
The natural numbers (counting numbers, positive integers) N satisfy the Principle of Mathematical Induction : (PMI):
If A is a subset of N such that
ì
ï
í
ï
î
1 Î A,
Whenever k Î A, k + 1 Î A,
then
A = N.
PMI is also stated as
Suppose P(n) is a statement for each natural number n. If
ì
ï
í
ï
î
P(1) is true,
Whenever P(k) is true, P(k + 1) is true.
then
P(n) is true for all n Î N.


PMI is used :
·
Proving formulas such as
12 + 22 + ¼+ n2 = n (n + 1) (2 n + 1)
6
·
Recursive definitions:
ì
ï
í
ï
î
1 ! = 1
n ! = n ·(n - 1)!,
n > 1.


There are two statements which are equivalent to PMI.


·
Well Ordering Principle (WOP): Every nonempty subset A of N has a least element - a number a Î A such that a £ x for all x Î A.


·
Principle of Complete Induction (PCI):
If A is a subset of N such that
ì
ï
í
ï
î
1 Î A,
Whenever 1, ¼, k Î A, k + 1 Î A,
then
A = N.


Integers Z and Rational Numbers Q


The natural numbers N seem to satisfy
·
P1 (addition is associative) Yes
·
P2 (zero) No
·
P3 (additive inverse) No
·
P4 (commutative addition) Yes
·
P5 (multiplication is associative) Yes
·
P6 (one) Yes
·
P7 (multiplicative inverse) No
·
P8 (commutative multiplication) Yes
·
P9 (distributive) Yes
The positive set P = N satisfies
·
P10 (trichotomy) Yes
·
P11 (P + P Ì P) Yes
·
P12 (P ·P Ì P) Yes
By adjoining 0 and the negative integers, with some effort we can recover P2 and P3. For the integers , Z, the positive set which satisfies P10, P11, and P12 is still N.
The rational numbers , Q, are objects of the form [p/q], p, q integers, q ¹ 0. The set P of positive rational numbers is ... (left to the reader).
The Rationals are not All Real Numbers
We shall rely on the following fact outlined in Chapter 2, Problem 17:
Every natural number n satisfies one and only one of the following
ì
ï
í
ï
î
n = 1,
n is a prime number,
n = a b, a,b Î N, 1 < a,b < n.

The definition of a prime number is given in Chapter 2, Problem 17.

Definition. A natural number p is called a prime number if it is impossible to write p = a b for natural numbers aand bunless one of these is p and the other 1. For convenience, we also agree that 1 is not a prime number.


Theorem. Every natural number n > 1 can be written as a product of primes. The factorization is unique except for the order of the factors (not proved here).
Thus every (positive) rational number r can be written as
r = p
q
 ,
where p and q are 1 or are are written as products of primes with no common factors.

Theorem. There is no rational number r such that
r2 = 2.
 Proof: If r2 = 2, write r = [p/q], where p and q are 1 or are written as products of primes with no common factors. Then
æ
è 		p
q
 ö
ø 		2

 
= 2 ,
p2
= 2 q2,
so that 2 is a factor of p2 and p. Thus p = 2k and 2 q2 = 4 k2 so that 2 is a factor of q2 and q also.
Remark: The prove of the above theorem is an example of proof by contradiction . What is the contradiction? The statement
p and q are 1 or are written as products of primes with no common factors of 2.
is both true and not true .
A real number which is not a rational number is called an irrational number .
N. B. There is an argument (Spivak, Chapter 2, Prob. 17) which shows that

Theorem. Suppose that M > 1, t > 1, are natural numbers. Then the tth root of M,
t
Ö
 
M
 
is irrational unless M = pt for some natural number p.

Theorem. Suppose that p, q, t, M are natural numbers such that M > 1, p and q have no common factor and
æ
è 		p
q
 ö
ø 		t

 
 = M.
Then
M = pt.

Proofs by Induction

We wish to prove that a statement [proposition] P(n) is true for all n. P(n) may be a sentence, formula, property, ¼.
A good proof by PMI requires:
·
State precisely and unambiguously P(n).
·
Prove the base case : P(1) is true. This step usually requires only a close look at the meaning of the statement "P(1) is true."
·
The induction step : P(k) implies P(k + 1).
·
Write down and assume P(k).
·
Perform any valid operations to arrive at P(k+1). It may help to say "We are to show that P(k+1) (write it down!) is true." Remember that you are free to use valid operations on P(k) and even P(1), ¼, P(k).


File translated from TEX by TTH, version 3.77.
On 04 Sep 2007, 19:59.