→ Xixan :如果|*|是cardinality的話，這樣只能證有限個喔… 09/09 21:00
※ 引述《mqazz1 (無法顯示)》之銘言：
: if A is any set,
: prove that |A| < |power set(A)|
: 請問這題該怎麼證明呢?
|power set(A)| = 2^|A|
當A是空集合 |A|=0 |power set(A)|=1 不等式成立
當A只有一個元素 |A|=1 |power set(A)|=2 不等式成立
當A只有兩個元素 |A|=2 |power set(A)|=2^2=4 不等式成立
假設當A只有k>1個元素 |A|=k |power set(A)|=2^k 且不等式成立 i.e 2^k>k
當A只有k+1個元素 |A|=k+1 |power set(A)|=2^(k+1)=2*2^k>2k>k+1 不等式成立
得証
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.177.40