A digression You will need to learn new ways to use (the Principle of) Mathematical Induction. You are probably familiar with Mathematical Induction as a tool for verifying formulas. We will need to use Mathematical Induction for other purposes. For example, we will need to know whether certain kinds of functions from N to N exist. There may be one function for each n, or maybe our statement will be that there is NO such function, for ANY n. We will then construct a set S := {n ∈ N : a function fn : N → N exists such that “thus and so” is true about fn}.
Then we will follow the “same” pattern as in school induction:
Step 0: Showthat 0 is in S. The way we show that 0 is in S will depend on what the criterion is for membership in S. But the objective of Step 0 is always the same: make sure 0 ∈ S.
Step 1: Let someone choose an arbitrary element n of N, then showthat the statement “n ∈ S ⇒ s(n) ∈ S” is true. This is the objective of Step 1, then: showthat (∀n ∈ N)(n ∈ S ⇒ s(n) ∈ S) is true. Since this is a statement with a universal quantifier, we have to be able to show that every one of the statements n ∈ S ⇒ s(n) ∈ S is true. We knowb y nowthat there is one easy way for this statement to be true: in case n ∈ S is false! We usually don’t mention this possibility; we just assume that n ∈ S is true. Then we try to use the truth of “n ∈ S” to deduce the truth of “s(n) ∈ S.” But we can’t always work that way! Sometimes we have to use the contrapositive of “n ∈ S ⇒ s(n) ∈ S, ” namely “s(n) not ∈ S ⇒ n not ∈ S.” That is, we assume that “s(n) not ∈ S” is true. Then we try to use the truth of “s(n) not ∈ S” to deduce the truth of “n not ∈ S.” This second approach is logically equivalent to the first way, but it is not psychologically the same! Step 1 is the “heart” of an induction proof. But Step 0 is essential!
Step 3: We apply the Principle of Mathematical Induction by noting that S = N. This step is one we do automatically; it’s like a coda in a piece of music. . . end of this digression
(04) Example: Let’s prove that s(N) = P. We need to recall that P = N\{0}. We want to show that every n in P is s(m) for some m in N. By Postulate (01C) we know that (∀n ∈ N)(s(n) ≠ 0) is true. Thus s(N) ⊆ N\{0} = P. To showequalit y, it remains to showthat P ⊆ s(N). We do already knowof one element of P that is in s(N), namely 1 = s(0). Thus 1 ∈ {n ∈ P : there exists m ∈ N such that n = s(m)} =: E. We will use induction for P instead of N. We already did Step 0 (or ought it be Step 1, for P?)! We need to showthat, for all n in P, “n ∈ E ⇒ s(n) ∈ E” is true. Well, “n ∈ E ⇒ s(n) ∈ E” is true if “n ∈ E” is false. Since “n ∈ E” has to be true or false, we have to see what happens if “n ∈ E” is true. So, we next suppose that “n ∈ E” is true. Now, “n ∈ E” means that there exists m ∈ N such that n = s(m). But then, s(n) = s(s(m)), by the Substitution Rule. The criterion for membership of s(n) in E is that there exists m ∈ N such that s(n) = s(m). This is confusing at first, because we just saw that n = s(m) because n ∈ E. The important thing to learn here is that variables in quantifiers are “dummy” variables; we can use any convenient letter to denote them! In the present context, we just use “s(m)” as our convenient “letter!” Thus, s(n) ∈ E. Then, by Mathematical Induction (set version, for P), E = P. In other words, every n in P is the successor of some m in N, as desired.
If you have time, I recommend that you read (listed as [3] in the References at the end of this Note) Foundations of Analysis, by Edmund Landau, Chelsea Publishing Co., NewY ork, 1951. Despite the author’s request, do read the preface for the teacher. Read the preface for the student too, and the book too, a little bit at a time. What Landau does is to carefully develop the properties of the positive integers from the axioms (the version for P). Here are some exercises, adapted from theorems in that book. In these exercises, do not use your prior knowledge, just use the axioms.
(05) Exercise: Showthat, for all n in N, and for all m in N, if n ≠ m then s(n) ≠ s(m).
(06) Problem: Showthat, for all n in N, s(n) ≠ n. You will need induction!
(07) Exercise: Showthat, for all n in N, if n ≠ 0 then there exists exactly one m in N such that n = s(m). You may need induction!
(08) Notation: If n ∈ N and n ≠ 0 we let n−1 denote the unique m in N (provided by Exercise (07)) such that n = s(m). That is, n = s(n − 1). An important point: n − 1 does not exist for all n in N; n − 1 exists only for n 0. This is not subtraction! The meaning of n − 1 is “predecessor of n.”
-작성중-