Prove that the cardinality of the power set of any set exceeds the cardinality o

Question

Explanation / Answer

Let X be any set, and P(X) denote the power set of X. Assume that it is possible to define a one-to-one mapping M : X ? P(X) Define s0, s1, s2, ... to be a trace, where the ?rst element of the trace is any arbitrary s0 ? X, and all further elements sj where j > 0, of the trace are such that sj ? M(sj-1) Define t belonging to X to be a simple element, if all possible traces beginning with t terminate. Note that a trace s0, s1, s2, ..., sf terminates at sf if M(sf ) is the empty set. Define N = {t belonging to X|t is a simple element} The set N, which is a subset of X, cannot lie in the range of M. Suppose there exists an n ? X such that M(n) = N, then n should be a simple element since all traces beginning with element n also terminate. Thus n ? N, but then n is no longer a simple element, since not all traces beginning with n are terminating traces (e.g. “n, n, n, ...” is one such non-terminating trace). Thus the set N is out of the range of mapping M. Q.E.D.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.