Re: [問題] 請問1+1=2是如何證出來的
※ 引述《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.
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.247.33
推
218.166.83.69 06/28, , 1F
218.166.83.69 06/28, 1F
推
61.229.69.217 08/28, , 2F
61.229.69.217 08/28, 2F
推
01/10 17:57, , 3F
01/10 17:57, 3F
推
01/10 17:58, , 4F
01/10 17:58, 4F
推
01/10 18:00, , 5F
01/10 18:00, 5F
推
01/10 18:05, , 6F
01/10 18:05, 6F
推
01/10 18:13, , 7F
01/10 18:13, 7F
推
01/10 18:23, , 8F
01/10 18:23, 8F
推
01/10 18:25, , 9F
01/10 18:25, 9F
推
01/10 18:26, , 10F
01/10 18:26, 10F
推
04/24 18:08, , 11F
04/24 18:08, 11F
推
05/16 00:29, , 12F
05/16 00:29, 12F
→
03/30 18:46, , 13F
03/30 18:46, 13F
推
07/18 07:41, , 14F
07/18 07:41, 14F
推
09/07 00:05, , 15F
09/07 00:05, 15F
推
09/11 02:07, , 16F
09/11 02:07, 16F
推
09/11 09:13, , 17F
09/11 09:13, 17F
→
11/21 18:01, , 18F
11/21 18:01, 18F
推
09/08 16:39, , 19F
09/08 16:39, 19F
推
09/19 14:23, , 20F
09/19 14:23, 20F
推
11/05 03:13, , 21F
11/05 03:13, 21F
推
11/05 03:19, , 22F
11/05 03:19, 22F
推
11/05 08:08, , 23F
11/05 08:08, 23F
推
11/05 10:25, , 24F
11/05 10:25, 24F
推
11/21 19:39, , 25F
11/21 19:39, 25F
→
11/21 19:40, , 26F
11/21 19:40, 26F
推
11/21 19:44, , 27F
11/21 19:44, 27F
推
11/21 19:56, , 28F
11/21 19:56, 28F
推
11/21 20:01, , 29F
11/21 20:01, 29F
推
11/21 20:12, , 30F
11/21 20:12, 30F
推
11/21 21:28, , 31F
11/21 21:28, 31F
推
01/10 17:45, , 32F
01/10 17:45, 32F
→
04/07 23:40, , 33F
04/07 23:40, 33F
→
04/07 23:41, , 34F
04/07 23:41, 34F
推
05/10 21:12, , 35F
05/10 21:12, 35F
推
05/12 15:12, , 36F
05/12 15:12, 36F
推
05/27 13:11, , 37F
05/27 13:11, 37F
推
07/08 15:14, , 38F
07/08 15:14, 38F
→
07/08 15:18, , 39F
07/08 15:18, 39F
還有 175 則推文
推
07/15 22:30, , 215F
07/15 22:30, 215F
推
08/05 16:33, , 216F
08/05 16:33, 216F
推
08/30 23:00, , 217F
08/30 23:00, 217F
推
09/29 06:02, , 218F
09/29 06:02, 218F
推
12/13 14:08, , 219F
12/13 14:08, 219F
推
01/09 09:40, , 220F
01/09 09:40, 220F
推
01/10 01:32, , 221F
01/10 01:32, 221F
推
03/07 11:19, , 222F
03/07 11:19, 222F
推
04/25 21:35, , 223F
04/25 21:35, 223F
推
05/09 12:03, , 224F
05/09 12:03, 224F
推
09/01 12:55, , 225F
09/01 12:55, 225F
推
09/13 21:27, , 226F
09/13 21:27, 226F
推
10/23 10:10, , 227F
10/23 10:10, 227F
推
11/12 15:19, , 228F
11/12 15:19, 228F
推
01/10 12:09, , 229F
01/10 12:09, 229F
推
01/14 22:41, , 230F
01/14 22:41, 230F
推
01/14 22:42, , 231F
01/14 22:42, 231F
→
01/14 22:45, , 232F
01/14 22:45, 232F
推
01/14 22:46, , 233F
01/14 22:46, 233F
推
01/22 02:35, , 234F
01/22 02:35, 234F
推
01/22 14:58, , 235F
01/22 14:58, 235F
推
02/03 20:29, , 236F
02/03 20:29, 236F
推
03/12 09:44, , 237F
03/12 09:44, 237F
推
04/06 15:39, , 238F
04/06 15:39, 238F
推
06/03 00:19, , 239F
06/03 00:19, 239F
推
06/03 22:34, , 240F
06/03 22:34, 240F
推
06/04 13:55, , 241F
06/04 13:55, 241F
推
09/10 18:24, , 242F
09/10 18:24, 242F
推
09/25 01:33, , 243F
09/25 01:33, 243F
推
09/25 21:23, , 244F
09/25 21:23, 244F
推
09/25 21:25, , 245F
09/25 21:25, 245F
推
10/15 15:00, , 246F
10/15 15:00, 246F
推
10/17 22:12, , 247F
10/17 22:12, 247F
推
12/02 01:47, , 248F
12/02 01:47, 248F
推
12/05 15:42, , 249F
12/05 15:42, 249F
推
12/05 15:53, , 250F
12/05 15:53, 250F
推
12/08 19:26, , 251F
12/08 19:26, 251F
推
01/03 14:35,
5年前
, 252F
01/03 14:35, 252F
推
03/17 00:04,
5年前
, 253F
03/17 00:04, 253F
推
09/25 12:22,
4年前
, 254F
09/25 12:22, 254F