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.”

-작성중-
  The Principle of Mathematical Induction is our principal source of “mathematical energy!”
  수학적 귀납법의 원리는 "수학적 능력"에 있어서 우리의 원칙적 원천이다!
  We usually don’t make axioms in a vacuum - there is usually some thought behind them. But that thought can be hidden! So here is an “explanation” of the axioms. First, let’s imagine that we go into the “back room,” where we don’t have to prove anything - just work on ideas! We “know” the integers exist, positive, zero and negative.
   우리는 보통 진공에서 공리들을 만들지 않는다 - 일반적으로 그것들 이면에 어떤 생각이 있다. 하지만 그 생각은 감추어질 수 있다! 그래서 공리들에 대한 '설명'이 있다. 첫째로, 위가 "무대 뒤"로 들어간다고 상상해 보자, 거기에서 우리는 어떤 것도 증명해야 하지 않다 - 단지 계속 생각하기만 하자! 우리는 정수의 존재, 양수, 0 그리고 음수를 "안다."
  The natural numbers are going to be our model of the non-negative integers. The successor function is “really” the function whose value at n, n ≥ 0, is n + 1 : s(n) = n + 1. Different non-negative integers “should” have different successors. This is what “s” is one–one” means. This is an assumption about the successor function! Saying 0 is not the successor of any non-negative integer means that 0
≠
 n + 1 for any non-negative integer n. The postulate about sets of non-negative integers is not something we usually take for granted. But the idea makes sense: if a set S contains 0, and contains the successor of each of its elements, then it also contains 1, and 2, and 3, and so on. So it ought to contain every non–negative integer, namely S = N.
 자연수는 우리의 비-음수인 정수의 원형이 될 것이다. 후속자 함수는 "실제로" n이 0보다 크거나 같을 때 n 값이
n + 1 : s(n) = n + 1인 함수이다. 상이한 비-음수 정수는 상이한 후속자들을 가져"야 한다." 이것은 "s"가 "일대일 대응"임을 의미한다. 이것은 후속자 함수에 대한 가정이다! 0이 어떠한 비-음수 정수의 후속자도 아니라고 말하는 것은 어떠한 비-음수 정수 n에 대해서도
0 ≠ n + 1임을 의미한다
. 비-음수 정수의 집합들에 대한 그 공준은 우리가 일반적으로 당연시하는 것이 아니다. 그러나 그 생각은 말이 된다: 만일 한 집합 S가 0을 포함하고, 그 집합의 원소들 각각의 후속자를 포함한다면, 그것은 또한 1, 2, 3 등을 포함할 것이다. 그래서 그 집합은 모든 비-음수 정수 각각을 포함해야 한다, 즉 S=N이다.

  In your experience, perhaps N starts with 1, not 0. There is an equivalent version of these axioms for that version of N. We simply replace each “0” in the first version with “1, ” and call the newset P, for positive integers. We will want to use induction “starting with 1.” But, instead of making another set of axioms, we can give the name 1 to s(0), and then we can deduce the proposed axioms, from the Peano Postulates, so they become a Theorem: a set of true mathematical statements whose truth is logically deduced from axioms, instead of being assumed.
 당신의 경험에서, 아마도 N은 0이 아니라 1로 시작할 것이다. N의 그 판에 대한 이러한 공리들에 상응하는 판이 있다. 우리는 간단하게 첫번째 판에서 각각의 "0"을 "1"로 대체하고, 새집합 P라고 부른다, 양의 정수이기 때문이다. 우리는 "1로 시작하는" 귀납법을 사용하기를 바랄 것이다. 그러나, 공리들의 또 다른 집합을 만드는 대신, 우리는 s(0)에 1이란 이름을 줄 수 있고, 그 다음으로 우리는 제시된 공리들을 연역할 수 있다, 페아노의 공준들로부터, 그래서 그것들은 정리가 된다: 참인 수학적 진술들의 한 집합, 그 진술의 참이 논리적으로 공리들로부터 연역된, 가정되는 대신에.
  (03) Theorem and Definition and Notation: There is a non-empty set P, whose elements we will call positive integers, a one-to-one function s : P → P, that we will call the successor function, and an element 1 ∈ P such that 1 is not in the image, s(P), of s. In addition, for all subsets E of P, if E contains 1, and s(E) ⊆ E, then E = P.
  (03) 정리와 정의 그리고 기수법: 비-공집합 P가 있다. P의 원소들을 우리는 양의 정수들이라고 부를 것이다. 그리고 일대일 대응 함수 s : P → P가 있다, 우리가 후속자 함수라고 부를. 그리고 1이 s(P)라는 s의 관념 속에 있는 1이 아닌 한 원소
1 ∈ P이 있다. 덧붙여서, P의 모든 부분집합들에 대해서, 만일 E가 1을 포함하고 s(E)
 ⊆ E 라면, E = P이다.
  The idea of the proof is to remove 0 from N to construct
P: P := N
＼
 {0}
. Then we have to check that each of the postulates can be re–interpreted in the newset. The Induction property is deduced by temporarily putting 0 back, then taking it out after applying the Principle of Mathematical Induction for N. We will not carry out the details of this proof unless you ask.
  그 증명에 대한 생각은
P: P := N
＼
 {0}를 구성하기 위해 N으로부터 0을 제거하는 것이다. 그래서 우리는 새집합에서 재-해석될 수 있는 그 공준들의 각각을 점검해야 한다. 그 귀납법 특성은 주기적으로 0을 되돌려 놓고, 다음으로 그 0을 N에 대한 수학적 귀납의 원리를 적용하는 것 뒤로 끄집어 냄으로써 연역된다.
  You have probably seen Mathematical Induction before, but it looked a little different then.
  당신은 아마도 이전에 수학적 귀납법을 봤을 테지만, 그것을 조금 다르게 봤을 것이다.
  Example (unofficial!): Use Mathematical Induction (school version) to show that for all positive integers n,
1 + 2 + 3 + · · · + n = n(n + 1)/2. In this Example, we will use your prior knowledge about P.
  예시 (비공식!): 수학적 귀납법을 사용하라 모든 양의 정수 n에 대해서
1 + 2 + 3 + · · · + n = n(n + 1)/2 임을 보이기 위해. 이 예시에서, 우리는 P에 대한 여러분의 사전지식을 사용할 것이다.
  The procedure is this:
1. Let P(n) denote the statement to be proved: P(n) must have n as its only free variable.
2. Verify that P(1) is true.
3. Show that, by assuming P(n) is true, you can deduce that P(n + 1) must be true.
  절차는 이러하다:
1. P(n)이 다음과 같이 증명될 진술을 표시하도록 하라: P(n)은 반드시 그것의 자유 변수로서만 n을 가져야 한다.
2. P(1)이 참임을 입증하라.
3. P(n)이 참임을 가정함으로써, 당신이 P(n+1)이 반드시 참이어야만 함을 연역할 수 있다는 것을 보여라.
  That is, prove the quantified mathematical statement “For all n in N, P(n) ⇒ P(n + 1).”
  Then Mathematical Induction assures us that P(n) is true for all n.
  즉, 양화된 수학적 진술 "N에서 모든 n에 대해 P(n)
 ⇒ P(n + 1)"을 증명하라.
  Let’s do it, for review.
  검코를 위해 해 보자.
  Step 1. Let P(n) denote the statement “1 + 2 + 3 + · · · + n = n(n + 1)/2.”
 
Step 2. P(1) is the statement
“1 = 1(1 + 1)/2.” This is true, by a very quick computation.
 
Step 3. Assume that P(n) is true for some n.
Then P(n + 1) is the statement “1 + 2 + 3 + · · · + (n + 1) =
(n+1)(n+2)/2.” We have 1+2+3+· · ·+(n+1) = 1+2+3+· · ·+n+(n+1) = (1+2+3+· · ·+n)+(n+1) = n(n+1)/2 +2(n+1/2) = (n+1)(n+2)/2, by a few basic algebraic manipulations. The equality of the first and last expressions in
this chain of equalities is P(n + 1), shown to be true under the assumption that P(n) is true. The truth of P(n) for all n is now established, by Mathematical Induction.
   
1단계. P(n)이 "
1 + 2 + 3 + · · · + n = n(n + 1)/2"라는 진술을 표시하도록 하라.
   2단계. P(1)은 "
1 = 1(1 + 1)/2"라는 진술이다. 이것은 참이다, 매우 즉각적인 계산에 의해.
   3단계. P(n)이 어떤 n에 대해 참이라고 전제하라. 그래서 P(n + 1) 은 "
1 + 2 + 3 + · · · + (n + 1) =
(n+1)(n+2)/2"이라는 진술이다. 그래서 우리는 약간의 기초적인 대수적 조작들을 통해
1+2+3+· · ·+(n+1) = 1+2+3+· · ·+n+(n+1) = (1+2+3+· · ·+n)+(n+1) = n(n+1)/2 +2(n+1/2) = (n+1)(n+2)/2 를 가진다, P(n)이 참이라는 저제 하에 참이라 보여지는. 모든 n에 대한 P(n)의 참은 이제 확정된다, 수학적 귀납법에 의해서.
 
  Remark: Note that, were P(n) false, the statement P(n) ⇒ P(n + 1) would be true vacuously. Thus we can
eliminate that possibility, and concentrate on what happens if P(n) is true.
   주의: 다음을 주의하라. P(n)이 거짓이라면,
P(n) ⇒ P(n + 1)이라는 진술은 허황된 참일 것이다. 따라서 우리는 그 가능성을 고려하지 않을 수 있고, P(n)이 참이라면 어떤 일이 일어나는지에 집중할 수 있다.
  The way we will often “do” Mathematical Induction differs only a little from this (and you may certainly use the old way in your papers in this class). The set–theoretic version of the argument for this example:
Let E := {n ∈ P : 1 + 2 + 3 + · · · + n = n(n+1)2}. We show 1 ∈ E (just as we just did), and that n ∈ E implies n + 1 ∈ E (just as we just did). Then E = P by Mathematical Induction.
  우리가 자주 '할' 수학적 귀납법의 방식은 이것(그리고 당신이 확실히 이 수업에서 당신의 paper들에서 사용했을지 모르는 그 오래된 방식)과 약간만 다르다. 이 예시에 대한 논증의 집합론적 판:
E := {n ∈ P : 1 + 2 + 3 + · · · + n = n(n+1)2}라고 하자. 우리는
1 ∈ E 임을 보이고(바로 우리가 방금 했던 것처럼),
n ∈ E 이
n + 1 ∈ E을 시사함을 보인다(바로 우리가 방금 했듯이). 그래서 수학적 귀납법에 의해 E = P이다.

-蟲-
출처 : www.math.umn.edu/~jodeit/course/Peano3.pdf

  THE NATURAL NUMBERS
  자연수
 
  We are ready for the official introduction of the natural numbers. I ask you to suspend belief in the truth of the things you already know about the natural numbers. I insist you keep every bit of your knowledge - just stop taking things for granted. “The Natural Numbers” is now a name only, to be used in the following list of mathematical statements, each of which you are asked to regard as true.
  우리는 자연수에 대한 공식적인 입문(개론)의 준비가 되어 있다. 나는 당신에게 당신이 자연수에 대해 이미 알고 있는 것들의 진실성에 대한 믿음을 보류할 것을 요청한다. 나는 당신이 당신 지식의 모든 낱낱을 붙들어 둘 것을 강력히 주장한다 - 그것들을 당연시 하는 것은 확실히 중단하자. "자연수"는 이제 하나의 명칭일 뿐이다. 그 명칭은 아래의 수학적 진술들의 목록에서 사용될 것이며, 당신에게는 그 진술들의 각각을 참으로 간주할 필요가 있다.
  This is where the course really starts. What came before was “preliminary.” We still have some preliminary stuff to do. But the natural numbers will literally be the foundation on which are built the ordinary integers, the rational numbers, and then the real and the complex numbers, which all form the foundations for Calculus.
  그 교육 과정은 실제로 여기서 시작한다. 앞서 나왔던 것은 "예비적인 것"이었다. 우리는 아직 해야할 몇몇 예비적인 것들을 가지고 있다. 그러나 자연수는 문자 그대로 기초가 될 것이다. 그 기초 위에 정수, 유리수, 그리고 실수와 복소수가 세워진다. 그 모든 수들은 계산을 위한 기초를 이루는 것들이다.

(01) The Peano Postulates (or Axioms)
(01) 페아노 공준 (혹은 공리)
  We assume that the four following mathematical statements are true.
  우리는 다음 네 가지 수학적 진술들이 참이라고 가정한다.
(01A) There exists a non-empty set N, whose elements we will call natural numbers.
(01A) 공집합이 아닌 하나의 집합 N이 있다. 우리는 그 집합의 원소들을 자연수라 부를 것이다.
(01B) There exists a one-to-one function s : N → N, that we will call the successor function.
(01B) 하나의 일대일 대응 함수 s : N → N이 있다. 우리는 그 함수를 후속자 함수라고 부를 것이다.
(01C) There exists an element 0 ∈ N such that 0 is not in the image, s(N), of s.
(01C) N에 포함되는(0 ∈ N) 하나의 원소 0이 있다. 그 같은 0은 s집합의 상인 s(N) 내에 없다.
(01D) For all subsets S of N, if S contains 0, and s(S) ⊆ S, then S = N.
(01D) N의 모든 부분집합 S에 대해서, 만일 S가 0을 포함하고, s(S)가 S에 동치이거나 포함된다면(s(S) ⊆ S), S는 N이다.
  Here is a restatement of these axioms, in a less dense form:
  여기 이 공리들에 대한 조금은 덜 난해한 형식의 재진술이 있다:
  (02-1) There exists a non-empty set N, called the set of natural numbers, and a function s on N, called the successor function, whose value, s(n), at any n in N, is called the successor of n, such that (02-2) Different elements of N have different successors (s is one-to-one), (02-3) There is an element, 0, of N that is not the successor of any element of N (0 is not in the image of s), (02-4) Every subset S of N that contains 0 and also contains the successor of each element of S must be equal to N (if S contains 0, and s(S) ⊆ S, then S = N).
  (02-1) 공집합이 아닌 집합 N이 있다. N은 자연수의 집합으로 부른다. 그리고 N에 대해 함수 s가 있다. 함수 s는 후속자 함수라 부른다. 함수 s의 값 s(n)은, N 내에서 어떠한 n에서든, n의 후속자라고 부른다. (02-2) N의 그러한 서로 다른 원소들은 서로 다른 후속자들을 가진다 (s는 일대일 대응이다). (02-3) N의 원소 0이 있다. 0은 N의 어떠한 원소에 대해서도 후속자가 아니다 (0은 s의 상 내에 없다). (02-4) 0을 포함하고 또한 S의 각 원소들에 대한 후속자를 포함하는 모든 부분집합 S는 반드시 N에 동치여야만 한다 (만일 S가 0을 포함하고, s(S) ⊆ S라면, S = N).

  According to the Encyclopedia Britannica, 15th edition, the five Peano postulates are:

  브리트니 백과 15번째 편집본에 따르면, 다섯 가지 페아노 공준들이 있다:
1. 0 is a number.
1. 0은 수이다.
2. The successor of any number is also a number.
2. 어떤 수의 후속자든 또한 수이다.
3. No two distinct numbers have the same successor.
3. 그 어떤 별개의 두 수도 동일한 후속자를 가지지 않는다.
4. 0 is not the successor of any number.
4. 0은 그 어떤 수의 후속자도 아니다.
5. If any property is possessed by 0 and also by the successor of any number having that property, then all numbers have that property.
5. 만일 어떤 특성이든 0에 의해 그리고 또한 그 특성을 지닌 어떤 수의 후속자에 의해 소유된다면, 모든 수는 그 특성을 지닌다.
  Postulate 5, (01D) and (02-4) are certainly different. But all three versions amount to the same thing mathematically, when expressed in terms of set–selector notation. For, “property” has to refer to a mathematical statement P(n) about elements n of N. Thus, {n ∈ N : P(n) is true } is the set of all elements of N that possess the property P(n). If the “property” satisfies the conditions of postulate 5, then 0 ∈ {n ∈ N : P(n) is true }, and s({n ∈ N : P(n) is true }) ⊆ {n ∈ N : P(n) is true }, so {n ∈ N : P(n) is true } = N. On the other hand, let S be a subset of N. We define the “property (of n)” to be that n belongs to S. That is, P(n) is the statement “n ∈ S.” This “property” is then covered by postulate 5.
  공준 5, (01D)와 (02-4)는 확실하게 다르다. 그러나 세 가지 설명들 모두 수학적으로 동일한 것에 이르게 된다, 집합-선택자 기수법이란 용어로 표현될 때. 왜냐하면, "특성"은 N의 원소들 n에 대한
수학적 진술 P(n)를 나타내야 하기 때문이다. 만일 그 "특성"이 공준 5의 조건들을 만족시킨다면,
0 ∈ {n ∈ N : P(n) 가 참 }, 그리고 s({n ∈ N : P(n) 가 참 }) ⊆ {n ∈ N : P(n) 가 참 }, 그래서 {n ∈ N : P(n) 가 참 } = N 이다. 다른 한편, S를 N의 한 부분집합으로 두자. 우리는 그 "(n의) 특성"을 n이 S에 속한다는 것으로 정의한다. 즉, P(n)은 "
n ∈ S"라는 진술이다. 이 "특성"은 그래서 공준 5에 의해 포섭된다.
  Postulate 5 is about sets of natural numbers. You probably did not bring this postulate with you to this course, at least not explicitly. And yet, it will seem natural to you shortly, I hope. Here are the three versions of Postulate 5, collected in one place:
  공준 5는 자연수 집합들에 대한 것이다. 당신은 아마도 이 공준을 갖고 이 과정을 수행하진 않았을 것이다, 최소한 명백하게는 아닐 것이다. 그리고 아직, 그것이 당신에게 곧 자연스러워 보일 것이다, 내가 희망하기로는. 여기 공준 5의 세 판이 있다, 한 자리에 모은:
  For all subsets P of N, if P contains the element 0, and s(P) ⊆ P, then P = N; Every subset of N that contains 0 and also contains the successor of each of its elements must be equal to N; If any property is possessed by 0 and also by the successor of any number having that property, then all numbers
have that property.
  N의 모든 부분집합 P에 대해서, 만일 P가 원소 0을 포함한다면, 그리고
s(P) ⊆ P라면, P = N이다; 0을 포함하고또한 그 원소들의 각각에 대한 후속자를 포함하는 N의 모든 각각의 부분집합은 N과 동치여야만 한다; 만일 어떤 특성이든 0에 의해 그리고 또한 그 특성을 지니는 어떤 수든지 그에 대한 후속자에 의해 소유된다면, 모든 수는 그 특성을 지닌다.
  This Postulate is called The Principle of Mathematical Induction.
  이 공준은 수학적 귀납법의 원리라 부른다.

-蟲-

+ Recent posts

티스토리툴바