SECTION 2.1 Elementary Number Theory 81
Therefore every elementn ∈ N is inG, which means that the above
statement is true for all positive integersn.
Let’s formalize this a bit. Assume that for each n ∈ N we assign
a propertyP(n) to this integer, which may be true or false. In the
previous section, the relevant propery was
P(n) : nhas at least one prime factor.In the example just discussed,P(n) : 1^2 + 2^2 + 3^2 +···+n^2 =n(n+ 1)(2n+ 1)
6.
The point is that once we have a property assigned to eachn∈N,
we may consider the setG ⊆∈ N of all integers n for which P(n) is
true, and the set (the criminals) of all integersnfor whichP(n) is false.
In trying to establish thatC=∅, we may streamline our argument via
Principle of Mathematical Induction. LetNdenote the set of
positive integers, and assume that for eachn∈N we have a property
P(n). Assume that
(i)P(a)is true, for somea∈N. (This “starts” the induction.)(ii) WheneverP(m)is true for alla≤m < n, (the so-calledinductive
hypothesis) thenP(n)is also true.ThenP(n)is true for alln≥a.
Proof. LetC be the set of all integers≥ a for whichP(n) is false.
We shall prove thatC =∅, which will imply thatP(n) is true for all
n ∈N. By hypothesis (i) above, we see that a 6∈C; therefore, if we
taken to be theleast element ofC, thenn 6 =a. Therefore, for any
positive integermwitha≤m < n,P(m) must be true. By hypothesis
(ii) above, we conclude that, in fact, P(n) must be true, which says
thatn 6∈C. This contradiction proves thatC = ∅, and the proof is
complete.
At first blush, it doesn’t appear that the above principle accom-
plishes much beyond what we were already able to do. However, it