show that the powerset of the natural numbers is not denumerable
To show that the powerset of the natural numbers
Step-by-step Proof (Using Cantor’s Diagonal Argument)
1. Assume for contradiction:
Suppose
2. Construct a special subset:
Define a subset
3. Check whether appears in the list:
Since we assumed all subsets are listed,
- If
, then by definition of , ⇒ contradiction. - If
, then ⇒ contradiction.
In either case, we get a contradiction.
Conclusion:
This contradiction shows our assumption was false. Therefore:
It is, in fact, uncountably infinite.
No comments:
Post a Comment