※ 引述《mqazz1 (無法顯示)》之銘言：
: Let R be a relation on a set A.
: Show that if R is reflexive and transitive,
: then R^n = R, for all positive integer n.
: 請問這題該怎麼證明呢?
: 是用歸納法嗎?
證明 RR = R 才是重點，但證明也只有一個重點：觀察 x R y R y。
先假設 R^2 = R，以下是歸納法的部分：
根據定義 R^1 = R。
若 R^n = R, 則 R^(n + 1) = RR^n = RR = R 根據歸納前提以及假設。
因此根據歸納法得證。
因為 R^n 定義是依賴歸納法的，只要需要展開定義，
就算引用其他證明結果，其中一定會用到歸納法的。
而用 axiom of extensionality 證明同樣也會用到歸納法
令 (x, y) \in R^n, 想要得到
x R x_1 R x_2 R ... R y => x R y
以及令 (x, y) \in R
x R y => x R y R y ... R y
這兩個結果，事實上就是遞歸展開 R^n 定義
加上遞歸證明 transitive 的性質，從 x R y R z => x R z
強化到 x R x_1 R .. R x_n => x R x_n。
--
盡量作 point-free 的證明比較簡單啦 ...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 147.188.193.87
※ 編輯: xcycl 來自: 147.188.193.87 (07/26 04:38)