作者susophist (窄宅)
看板logic
標題Re: [請益] 證明a=b,then b=a
時間Wed Dec 18 03:03:33 2013
※ 引述《MathTurtle (恩典)》之銘言:
: ※ 引述《chantaltw (nous)》之銘言:
: : 這是台大邏輯考古題
: : 題目是:使用推論規則證明 a=b /then b=a
: : 我不太有頭緒要從哪證明起......
: : 念數學的人說,要證明這個,要先知道a=b和b=a有不同
: : 但根據定義,它們是相同的。所以如果他要證明,答案很可能是"根據定義"。
: : 但哲學系應該不太會這樣子證明(?)
: : 所以來請教大家,你們的想法。^^
: 嗯, a=b 和 b=a 的確不同, 一個是 'a' 在前面, 一個是'b'在前面。
: 在一般的述詞邏輯裡面, 如果有 '=' 這個述詞, 通常給的 axioms 只有下面兩條:
: (1) for all x, x=x
: (2) for all x for all y, if x=y, then Fx iff Fy
: 也就是只有 reflexivity 和 Leibniz's Law, 並不包含 a=b和b=a要等價。
: 至於證明的話, 就是要從 (1)和 (2) 推出 a=b, therefore b=a
: 1. a=b Ass.
: 2. a=a (1) UI
: 3. if a=b then a=a iff b=a (2) UI
: 4. a=a iff b=a 1, 3 MP
: 5. if a=a then b=a 4 'iff'
: 6. b=a 2, 5. MP
自反性(reflexivity, "(x)Rxx")不是「等同性」,雖然,「等同性」是自反性的一種,
另一個自反性的例子是:__是__的子集合。
萊布尼茲等同律(LL),包含有「等同性」的內容之外,多了,對事物「性質」的討論,
萊布尼茲等同律是「二階邏輯」,它對「性質」(述詞, e.g. 'F')進行了量限:
LL: (x)(y)(F) [x=y ≡ (Fx≡Fy)]
事實上它包含兩個部分:
(x)(y)(F) [x=y → (Fx≡Fy)],「等同項之不可分辨律」,這是你用的公設(axiom);
(x)(y)(F) [(Fx≡Fy) → x=y],「不可分辨項之等同律」。註:這在哲學界有爭議
您的證明中,「Fx」用「x=a」代入,怪怪的;這似乎,不是邏輯上合法的(代入)規則。
若用LL證明,其步驟如下:
1(1) a=b P. premise
2(2) ┐(b=a) A. assumption
(3) (x)(y)(F) [x=y ≡ (Fx≡Fy)] LL.
(4) a=b ≡ (Ga≡Gb) (3) x/a, y/b, F/G 「/」表示,用__代入
(5) b=a ≡ (Gb≡Ga) (3) x/b, y/a, F/G
1(6) Ga≡Gb (1), (4) MP 前斷律
1(7) (Ga→Gb) & (Gb→Ga) (6) '≡' equivalent 等同律
1(8) (Gb→Ga) & (Ga→Gb) (7) '&' commutation 交換律
1(9) Gb≡Ga (8) '≡' equivalent
1(10) b=a (9), (5) MP
1,2(11) b=a & ┐(b=a) (10), (2) Conj 連言律
1(12) b=a (2)-(11) IP (矛盾)歸謬法 Q.E.D.
註:
項式前面的號碼('1'or'2'or'1,2')係「前提號碼」,「空格」代表空集合、
表示「從邏輯定理而來」;述詞邏輯的推導證明,用前提號碼來標示:
結論「純」由前提而來,以避免UG、UI、EG、EI之不合法的代入/量限化使用。
以上,謝謝。
參考資料:
http://www.scu.edu.tw/philos/97class/97-2%20peng/L-logic/12.pdf (彭孟堯講義)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.118.67
1F:→ zoneline:他沒說「自反性就是等同性」,他說的是:第一條axiom在講 12/19 20:26
2F:→ zoneline:等同關係是reflexive 12/19 20:26
我沒說「他說」自反性就是等同性。
3F:→ zoneline:第二條其實是axiom schema,可能是為了簡化才沒講吧 12/19 20:44
4F:→ zoneline:source: Hunter, Geoffrey. metalogic, pp.195-6. 12/19 20:45
你的「第二條」是指「不可分辨項之等同律」麼,不太明白為何其實是「axiom schema」
,可以說明一下嗎?第二問,「為了簡化」什麼?
5F:→ zoneline:順帶一提,你的證明不用歸謬法也可以,刪掉2,11,12 12/19 20:53
6F:→ zoneline:就是簡單一點的direct proof 12/19 20:53
感謝提醒,可以比較短路徑直接證明;不過「二階邏輯」似乎是不完備的,用LL証「a=b,
therefore b=a」似乎是有問題的......
※ 編輯: susophist 來自: 180.176.200.225 (12/21 00:43)