推 weeeeeeeeell:這篇讚 09/11 22:02
※ 引述《mqazz1 (無法顯示)》之銘言：
: if A is any set,
: prove that |A| < |power set(A)|
: 請問這題該怎麼證明呢?
Let P(A) be the power set of A.
Consider the function f:A -> P(A), given by f(x) = {x}; it's easy to see
that f is an injective; hence, |A|≦P(A).
If |A| = |P(A)|, we can find g:A->P(A), where g is a bijection.
Let B = {x is in A| x is not in g(x)}.
We can find y in A such that g(y) = B.
If y is in B, then y is not in g(y) = B -><-
If y is not in B, then y is not in B = g(y); but from the definition
of B, y is in B -><-
Consequently, we CANNOT find such g. So, |A| < |P(A)|.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.162.216