Re: [問題] 請問1+1=2是如何證出來的

[plover (+oo)]

※ 引述《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
推 Zing119:哇靠好屌
推 ckclark:3銀
推 woomie:緊握小根根
推 woomie:緊握小根根
推 woomie:緊握小根根
推 woomie:緊握小根根
推 woomie:緊握小根根
推 woomie:緊握小根根
推 woomie:緊握小根根
推 woomie:緊握小根根
推 llewxam:￿￿￿￿￿
推 nicess:[email protected]
→ revivalworld:朝聖
推 wyob:借轉
推 tsecpr:test
推 Fxxxz:八卦板來朝聖 看到第四頁以後就笑了...
推 zsxa1234:XD
→ sebaceous:ㄎㄎ
推 paggei      :O_O
推 ptlove1222  :90902Bbbsai
推 myhole      :來朝聖
推 ntust661    :朝聖
推 giveme520   :朝聖 跨謀
推 Geffen1     :洗咧攻殺毀
推 tomshiou    :朝聖
→ e1q3z9c7    :跨隆謀
推 toya123     :來朝聖  原來1+1=2是這麼複雜的式子
推 piliboy     :朝聖
推 KI780804    :朝聖    請問甚麼是一 甚麼是二?  有必要那麼複雜嗎
推 pl726       :朝聖
推 enunion     :這不會有循環證法問題嗎???
推 chengwaye   :.......
→ eggsu       :-]這個屬於符號看得好累
→ eggsu       :要是x-]X可以改成x in X，會容易得多吧！
推 cj6u40      :２０１０／０５／１０
推 chenlytw    :2010 / 05 / 12
推 sorkayi     :2010/05/27
推 head109     :2010.7/8
→ KIRA1943    :朝聖
推 cheng135    :2010/07/08
推 majungyi    :真可怕...
推 alwaysOGC   :朝聖 2010/07/08
推 jasonkau    :朝聖 2010/07/08       另外緊握小根根是什麼東西= =
→ Fewer       :2010/7/8
推 pio298      :朝聖 2010/07/08
推 daliao626   :朝聖 2010/07/08
推 keenth      :朝聖 2010/07/08       另外緊握小根根是什麼東西= =
推 Adamsun0306 :2010/7/8
推 ruemann     :朝聖 2010/07/08
推 hochengyuan :朝聖 2010/07/08
推 johnson127  :朝聖 2010/07/08
推 jeff87821   :朝聖 2010/7/08
推 YSimpson    :有必要這麼累嗎?
推 eva577663   :朝聖 2010/08/12
推 romsqq      :2010/09/03
推 wuling510665:2010/09/10
推 xavier13540 :原po真神人也
推 wind90605   :朝聖 2010/10/01       另外握緊小根根是什麼東西= =
推 darren8221  :朝聖 2010/10/09
推 craig100    :朝聖 2010/10/10      話說這樣證好辛苦.....
推 turtleqqq   :朝聖~ 有沒有人可以貼費馬~ 9X頁的圖文證明~XD
→ red0210     :朝聖 2010/10/17       另外緊握小根根是什麼東西= =
推 worshipA    :緊握小根根
推 likeshit    :朝聖 2010/11/13
推 peter50505  :朝聖 2010/11/13
推 Scorpliu    :朝聖 2010/11/13
推 victorway   :朝聖2010/11/13
推 liufon      :朝聖 2010/11/13
推 kdogin1548  :朝聖 2010/11/14
推 tsoahans    :-----------------本篇文章值3元-------------------
推 x03692001   :朝聖  2011/01/10
→ b95236      :朝聖 2011/01/22 超強....
推 psplay      :朝聖 2011/01/22
推 ByronX      :朝聖 2011/01/22 還好我工學院會用就好~~
推 snowyba     :朝聖 2011/01/22
推 j003862001  :朝聖 2011/01/22
推 glacialfire :朝聖 2011/01/22 曾聽過我數學系朋友說過 果然是真的
推 latria      :朝聖 2011/02/09
推 ohjia       :朝聖 2011/2/17
推 heavenmusic :朝聖 2011/02/17
推 nottestella :朝聖 2011/03/03
推 Marcantonio :朝聖 2011/03/31 要是我唸數學系會崩潰吧
推 cckk3333    :朝聖 2011/04/17
推 Hodou       :朝聖 2011/05/01 想知道"緊握小根根"是什麼東西+1
推 samok       :朝聖 2011/05/05 太強了QQ
推 pkla0120    :朝聖 2011/06/18
推 robertchun  :朝聖 2011              這啥鬼....
推 skywidth    :朝聖 2011/06/18  幹!! 真強
推 Howard61313 :朝聖 2011/06/18
推 Rex1009     :朝聖 2011/06/18 緊握小根根到底是什麼
推 luming      :朝聖 2011/06/18
推 gfneo       :朝聖 2011/06/18  我回去做實驗就好......
推 jayleeabc   :朝聖 2011/06/18
推 CCC1231321  :朝聖 2011/06/18 緊握小根根
推 gp03dan     :朝聖 2011/06/18 緊握小根根
推 mouse711217 :朝聖 2011/06/18 完全看不懂
推 larsatic    :朝聖 2011/06/18 直接END
推 jlcsn       :朝聖 2011/06/18 感覺我念數學系也會崩潰orz
推 sseug2      :朝聖 2011/06/24
推 alfadick    :潮吹 2011/07/21
推 rifurdoma   :朝聖 2011/09/06
推 chy1010     :朝聖 2011/09/07 .... 學長名字裡面有根
推 tanaka0826  :朝聖 2011/09/08  還好我沒讀數學系
推 askaleroux  :朝聖 2011/10/02  我直接end了
推 rugomen     :朝聖 2011/10/05 pm 11:34 ....
推 littlemings :朝聖 2011/10/05
推 hey5566     :朝聖 2011/10/05
→ ibook0102   :朝聖 2011/10/05 PM 11:46
推 ps0grst     :朝聖 2011/10/15
推 KKlin813    :朝聖 2011/10/22
→ xgcj        :朝聖 2011/10/27
推 fishweeping :朝聖 2011/11/09
推 TRAP        :朝聖 2011/12/06
推 friendever  :朝聖 2011/12/13
推 cccooler    :朝聖                                        2011/
→ PhySeraph   :朝聖 2011/12/13
推 ds112115    :朝聖 2011/12/13
推 ptlove1222  :朝聖 2011/12/13 窩生ㄖ
推 tsoahans    :樓上生日快樂
推 Luluandlulu :朝聖 2012/01/17 XD
推 oyrac2      :朝聖 2012/02/03
推 peterqlin   :朝聖 2012/02/09
推 sh1357      :朝聖 2012/03/02
推 a187        :朝聖 2012/12/10
推 theeht      :朝聖 3012/02/30
推 andy810625  :朝聖 2012/03/07
推 LSC112233   :朝聖 2012/03/28
推 turtleqqq   :會成功嗎!?
推 theye       :朝聖 2012/04/26 01:21
推 fox49er     :朝聖
推 MSNboy      :將近十年的文章= =
推 Erict       :朝聖 2012/04/29
推 qDaniel     :八卦版在吵 來朝聖推
推 kevin21y    :朝聖 2012/04/29
推 general     :朝聖 2012/04/29
推 r81402      :朝聖 2012/04/29   完全看不懂...
推 smelly      :朝聖 2012/4/29
推 renmax      :朝聖 2012.04.29       另外握緊小根根是什麼東西= =
推 batista5566 :朝聖 2012/04/29
推 maryma      :朝聖 2012/04/30
推 panruru1224 :朝聖 2012/07/25
推 hermitdruid :朝聖                                        2012/
推 TaiwanXDman :朝聖                                        2012/
推 futureland  :朝聖 2012/08/24
推 bananasp    :朝勝
推 p3800       :朝聖 2012/09/08
→ sofaly5566  :朝聖 2012/09/08
推 onecent     :朝聖 2012/09/08
推 SRNOB       :朝聖 2012/09/23
推 vagic       :朝聖 2012/10/16
推 qp2dguxiou  :朝聖 2012/11/10
推 tsoahans    :握緊小根根
推 GoodElephant:朝聖 2012/12/03
推 handsomeKim :朝聖 2012/12/06
推 xyz100590   :朝聖2012/12/22
推 tomichy     :朝聖 2013/02/08
推 ChihYaoLin  :朝聖2013/02/26
推 uuuujoe     :朝聖
推 theyi       :朝聖                                        2013/
推 bobju       :路過 2013/10/09
推 allenryanpen:朝聖 2014/01/07
推 ChihYaoLin  :朝聖 2014/03/20 每年都要來膜拜一下
推 kmjhome     :朝聖 2014/4/14
推 aa58231     :靠 好猛
推 obboy       :2014/5/7
推 LAClippers  :簽到
推 frozenfish  :朝聖
推 ikebig      :偶像
推 evilture    :2014/5/10
推 aa85ss20    :2014/05/23
推 bbo6uis122  :朝聖 2014/06/13
推 s512874690  :朝聖 2014/6/25
推 contaminate : 20140922
推 chpinga     : 2014/11/28
推 hhh1234321  : 2014/12/26
推 Yuchann     : 朝聖～～2015
推 mopackc09971: 朝聖 2015.01.13
推 cattie0709  : 朝聖
推 JohnRambo   : 朝聖推
推 hhh1234321  : 臘月十七推一下
推 johnnyttttt : 2015/02/13 朝聖
推 waasabi     : 2015/03/06
推 chwa        : 朝聖 2015/03/16
推 iPolo3      : 工蝦 跨攏抹
推 FateOFP     : 朝聖 2015/03/25
推 ltameion    : 朝聖 2015/03/25
推 rataliepos  : 2015/3/25
推 gold97972000: 朝聖 2050/03/25
推 aij         : 朝聖 2100/03/25
推 jameskey    : 朝聖 2015/04/24
推 jerry73204  : 朝聖 2015/05/09 看到神了 <(_ _)>
推 jaytony     : 朝聖 2015/05/09 已跪
推 haocker     : 朝聖 2015/07/25 閃尿了
推 x710142857  : 朝聖 2015/08/20
推 Desperato   : 朝聖 2015/08/20 \ow o/
推 Luwan       : 2015 8/29  太屌了...
推 hhjkjk11    : 2015/9/5
推 ray81712    : 朝聖 2015/9/5  誇攏某
推 janna5566   : 朝聖RRR  看不懂QQ                          2015/
推 opmew       : 2015/09/05
推 l2687316988 : 太扯啦
推 leafhow     : 朝聖
推 SIRIUS      : 朝聖 2015/09/05
推 caffpetiy   : 快推 不然人家以為我看不懂
推 Curry5566   : 朝聖 2015/09/05
推 kobe9527    : 朝聖
推 tomoyari    : 朝聖
推 ioms        : 朝聖 順便貼個代碼 #0-7-C1CF (Math)         2015/
→ ChihYaoLin  : 朝聖
推 god829      : 朝聖2015/09/05 另外緊握小根根到底是什麼東西= =
推 KANEISBEACH : 跟我想得差不多 給推
推 hhh1234321  : 怪不得我的加法一直無法突破,懂了..... d(^_^)b
推 LeeMY       : 2016 04/11
推 regen1999   : 2016/06/27
推 evilture    : 2016/07/15 我到底看了三小
推 ckjonathan  : 2016/08/05
推 kevinyin9   : 2016/8/30
推 josephcc    : 2016/9/29
推 ms0705718   : 來朝聖 2016/12/13
推 Sidney0503  : 恩恩  跟我想的一樣                         2017/
推 FuwafuwaCAT : 太深奧了
推 twbbsbbs    : 大獅必推！
推 sustainer123: 朝聖 2017/4/25
推 a83a83cjcj  : 朝聖 2017/05/09 XD
推 Leafypc     : 2017/09/01 朝聖 plover大大生日快樂！
推 canucksteve : 朝聖 2017/09/12
推 dionysus522 : 朝聖 2017/10/23
推 ck0987515477: 2017/11/12 朝聖
推 sos976431   : 2018 1 10 推
推 AsllaPiscu  : 朝聖推
推 gfhnrtjpoiuy: 朝聖 2018/01/14
→ Anonym5566  : 朝聖 2018.01.14
推 SteveNeko   : 2018/01/14 朝聖
推 LiptonTea   : 2018/01/22 朝聖
推 Gauss       : 2018/1/22
推 mark10133   : 2018/02/03朝聖
推 GKki2012    :    [-是指 "belong to"嗎           ∈
推 Gauss       : 20180406
推 Felix30810  : 20180603朝聖
推 zxuanjia    : 2018/06/03朝聖
推 Aionaon     : 20180604 朝聖
推 anderson0815: 2018/9/10 朝聖
推 Jetinacn    : 2018.9.25 朝聖
推 tom282f3    : 107.09.25
推 tom282f3    : 緊握小根根
推 joj4211     : 2018.10.15朝聖數學的起源
推 waazxc77548 : 高二生瑟瑟發抖
推 xikless     : 2018.12.02
推 gcobs0834   : 2018.12.5
推 qqaatw      : 2018/12/5 朝聖
推 delvinnew200: ...朝聖
推 d880126d    : 2019.1.3  朝聖
推 a12349221   : 朝聖……
推 steven56138 : 2019/9/25 考古朝聖
推 Azraelx     : 2020.06.28 朝聖
推 jiexyz      : 20211127朝聖
推 Qkirito     : 2021/12/17朝聖 這次比較看的懂囉
推 oskens      : 看了李永樂的證明終於弄懂這文章在幹啥了  朝聖
推 boriszhang  : 朝聖 2023/12/07