7.2. Proof by Contradiction

Try these first

1. 1.

   What is the power set of a set {a, b}?

   Hint

   Remember to list all subsets.

2. 2.

   Consider the set A = {x, y}; how many elements are in P(A)?

   Hint

   Each element can either be included or not included.

3. 3.

   What theorem shows that the cardinality of a set is less than that of its power set?

   • Axiom of Choice
   • Cantor's Theorem
   • Zermelo's theorem

   Hint

   Think about who originally presented the concept of comparing sizes of infinity.

4. 4.

   If a set has 5 elements, how many elements does its power set have?

   • True
   • False

   Hint

   Remember the formula for calculating the power set.

5. 5.

   Consider a set with 4 elements. Prove that there exists no surjective function from this set to its power set.

   Hint

   Define the function and illustrate the mapping before finding S.

6. 6.

   If we apply Cantor's theorem repeatedly, what can we say about the cardinality of the power set of the power set of the natural numbers?

   Hint

   Remember that each application of Cantor's theorem shows distinct infinities.