→ booom:嚇死人....... 推 61.224.12.216 04/12
※ 引述《weii (德布西的月光)》之銘言：
: ※ [本文轉錄自 Math 看板]
: 作者: plover (+oo) 看板: DAIC
: 標題: Re: [問題] 請問1+1=2是如何證出來的
: 時間: Sat Jan 11 17:27:47 2003
: ※ 引述《bigjuto (用過的都說棒)》之銘言：
: : 是用皮亞諾公設嗎...
: : 該如何去證？
: Author: Pinter
: We will proceed as follows: we define
: 0 = {}.
: In order to define "1," we must fix a set with exactly one element;
: thus
: 1 = {0}.
: Continuing in fashion, we define
: 2 = {0,1},
: 3 = {0,1,2},
: 4 = {0,1,2,3}, etc.
: The reader should note that 0 = {}, 1 = {{}}, 2 = {{},{{}}}, etc.
: Our natural numbers are constructions beginning with the empty set.
: The preceding definitions can be restarted, a little more precisely,
: as follows. If A is a set, we define the successor of A to be the set
: A^+, given by
: A^+ = A ∪ {A}.
: Thus, A^+ is obtained by adjoining to A exactly one new element,
: namely the element A. Now we define
: 0 = {},
: 1 = 0^+,
: 2 = 1^+,
: 3 = 2^+, etc.
: 現在問題來了, 有一個 set 是包括所有 natural numbers 的嗎 ? (甚至問
: 一個 class). 這邊先定義一個名詞, 接著在引 A9, 我們就可以造出一個 set
: 包括所有的 natural numbers.
: A set A is called a successor set if it has the following properties:
: i) {} [- A.
: ii) If X [- A, then X^+ [- A.
: It is clear that any successor set necessarily includes all the natural
: numbers. Motivated bt this observation, we introduce the following
: important axiom.
: A9 (Axiom of Infinity). There exist a successor set.
: As we have noted, every successor set includes all the natural numbers;
: thus it would make sense to define the "set of the natural numbera" to
: be the smallest successor set. Now it is easy to verify that any
: intersection of successor sets is a successor set; in particular, the
: intersection of all the successor sets is a successor set (it is obviously
: the smallest successor set). Thus, we are led naturally to the following
: definition.
: 6.1 Definition By the set of the natural numbers we mean the intersection
: of all the successor sets. The set of the natural numbers is designated by
: the symbol ω; every element of ω is called a natural number.
: 6.2 Theorem For each n [- ω, n^+≠0.
: Proof. By definition, n^+ = n ∪ {n}; thus n [- n^+ for each natural
: number n; but 0 is the empty set, hence 0 cannot be n^+ for any n.
: 6.3 Theorem (Mathematical Induction). Let X be a subset of ω; suppose
: X has the following properties:
: i) 0 [- X.
: ii) If n [- X, then n^+ [- X.
: Then X = ω.
: Proof. Conditions (i) and (ii) imply that X is a successor set. By 6.1
: ω is a subset of every successor set; thus ω 包含於 X. But X 包含於 ω;
: so X = ω.
: 6.4 Lemma Let m and natural numbers; if m [- n^+, then m [- n or m = n.
: Proof. By definition, n^+ = n ∪ {n}; thus, if m [- n^+, then m [- n
: or m [- {n}; but {n} is a singleton, so m [- {n} iff m = n.
: 6.5 Definition A set A is called transitive if, for such
: x [- A, x 包含於 A.
: 6.6 Lemma Every natural number is a transitive set.
: Proof. Let X be the set of all the elements of ω which
: are transitive sets; we will prove, using mathematical induction
: (Theorem 6.3), that X = ω; it will follow that every natural
: number is a transitive set.
: i) 0 [- X, for if 0 were not a transitive set, this would mean
: that 存在 y [- 0 such that y is not a subset of 0; but this is
: absurd, since 0 = {}.
: ii) Now suppose that n [- X; we will show that n^+ is a transitive
: set; that is, assuming that n is a transitive set, we will show
: that n^+ is a transitive set. Let m [- n^+; by 6.4 m [- n
: or m = n. If m [- n, then (because n is transitive) m 包含於 n;
: but n 包含於 n^+, so m 包含於 n^+. If n = m, then (because n
: 包含於 n^+) m 包含於 n^+; thus in either case, m 包含於 n^+, so
: n^+ [- X. It folloes by 6.3 that X = ω.
: 6.7 Theorem Let n and m be natural numbers. If n^+ = m^+, then n = m.
: Proof. Suppose n^+ = m^+; now n [- n^+, hence n [- m^+;
: thus by 6.4 n [- m or n = m. By the very same argument,
: m [- n or m = n. If n = m, the theorem is proved. Now
: suppose n≠m; then n [- m and m [- n. Thus by 6.5 and 6.6,
: n 包含於 m and m 包含於 n, hence n = m.
: 6.8 Recursion Theorem
: Let A be a set, c a fixed element of A, and f a function from
: A to A. Then there exists a unique function γ: ω -> A such
: that
: I. γ(0) = c, and
: II. γ(n^+) = f(γ(n)), 對任意的 n [- ω.
: Proof. First, we will establish the existence of γ. It should
: be carefully noted that γ is a set of ordered pairs which is a
: function and satisfies Conditions I and II. More specifically,
: γ is a subset of ω╳A with the following four properties:
: 1) 對任意的 n [- ω, 存在 x [- A s.t. (n,x) [- γ.
: 2) If (n,x_1) [- γ and (n,x_2) [- γ, then x_1 = x_2.
: 3) (0,c) [- γ.
: 4) If (n,x) [- γ, then (n^+,f(x)) [- γ.
: Properties (1) and (2) express the fact that γ is a function from
: ω to A, while properties (3) and (4) are clearly equivalent to
: I and II. We will now construct a graph γ with these four properties.
: Let
: Λ = { G | G 包含於 ω╳A and G satisfies (3) and (4) };
: Λ is nonempty, because ω╳A [- Λ. It is easy to see that any
: intersection of elements of Λ is an element of Λ; in particular,
: γ = ∩ G
: G[-Λ
: is an element of Λ. We proceed to show that γ is the function
: we require.
: By construction, γ satisfies (3) and (4), so it remains only to
: show that (1) and (2) hold.
: 1) It will be shown by induction that domγ = ω, which clearly
: implies (1). By (3), (0,c) [- γ; now suppose n [- domγ. Then
: 存在 x [- A 使得 (n,x) [-γ; by (4), then, (n^+,f(x)) [- γ,
: so n^+ [- domγ. Thus, by Theorem 6.3 domγ = ω.
: 2) Let
: N = { n [- ω | (n,x) [- γ for no more than one x [- A }.
: It will be shown by induction that N = ω. To prove that 0 [- N,
: we first assume the contrary; that is, we assume that (0,c) [- γ
: and (0,d) [- γ where c≠d. Let γ^* = γ - {(0,d)}; certainly
: γ^* satisfies (3); to show that γ^* satisfies (4), suppose that
: (n,x) [- γ^*. Then (n,x) [- γ, so (n^+,f(x)) [- γ; but n^+≠0
: (Theorem 6.2), so (n^+,f(x))≠(0,d), and consequently (n^+,f(x)) [-
: γ^*. We conclude that γ^* satisfies (4), so γ^* [- Λ; but γ is
: the intersection of all elements of Λ, so γ 包含於 γ^*. This is
: impossible, hence 0 [- N. Next, we assume that n [- N and prove
: that n^+ [- N. To do so, we first assume the contrary -- that is,
: we suppose that (n,x) [- γ, (n^+,f(x)) [- γ, and (n^+,u) [- γ
: where u≠f(x). Let γ^。 = γ - {(n^+,u)}; γ^。 satisfies (3) because
: (n^+,u)≠(0,c) (indeed, n^+≠0 by Theorem 6.2). To show that γ^。
: satisfies (4), suppose (m,v) [- γ^。; then (m,v) [- γ, so
: (m^+,f(v)) [- γ. Now we consider two cases, according as
: (a) m^+≠n^+ or (b) m^+ = n^+.
: a) m^+≠n^+. Then (m^+,f(v))≠(n^+,u), so (m^+,f(v)) [- γ^。.
: b) m^+ = n^+. Then m = n by 6.7, so (m,v) = (n,v); but n [- N,
: so (n,x) [- γ for no more than one x [- A; it follows that v = x,
: and so
: (m^+,f(v)) = (n^+,f(x)) [- γ^。.
: Thus, in either case (a) or (b), (m^+,f(v)) [- γ^。, thus, γ^。
: satisfies Condition (4), so γ^。[- Λ. But γ is the intersection
: of all the elements of Λ, so γ 包含於 γ^。; this is impossible,
: so we conclude that n^+ [- N. Thus N = ω.
: Finally, we will prove that γ is unique. Let γ and γ' be functions,
: from ω to A which satisfy I and II. We will prove by induction that
: γ = γ'. Let
: M = { n [- ω | γ(n) = γ'(n) }.
: Now γ(0) = c = γ'(0), so 0 [- M; next, suppose that n [- M. Then
: γ(n^+) = f(γ(n)) = f(γ'(n)) = γ'(n^+),
: hence n^+ [- M.
: If m is a natural number, the recurion theorem guarantees the
: existence of a unique function γ_m: ω -> ω defined by the
: two Conditions
: I. γ_m(0)=m,
: II. γ_m(n^+) = [γ_m(n)]^+, 對任意的 n [- ω.
: Addition of natural numbers is now defined as follows:
: m + n = γ_m(n) for all m, n [- ω.
: 6.10 m + 0 = m,
: m + n^+ = (m + n)^+.
: 6.11 Lemma n^+ = 1 + n, where 1 is defined to be 0^+
: Proof. This can be proven by induction on n. If n = 0,
: then we have
: 0^+ = 1 = 1 + 0
: (this last equality follows from 6.10), hence the lemma holds
: for n = 0. Now, assuming the lemma is true for n, let us show
: that it holds for n^+:
: 1 + n^+ = (1 + n)^+ by 6.10
: = (n^+)^+ by the hypothesis of induction.
: 把 n = 1 並且注意 2 = 1^+, 故 1 + 1 = 2.
life is short, play more
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.181.35