Practice Proof By Contradiction (7.2) - Cantor's Theorem - Discrete Mathematics

Practise this section

9 questions

Flashcard drill
3 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What is the power set of a set {a, b}?
Show hintHide hint
Remember to list all subsets.
Question 2.
Consider the set A = {x, y}; how many elements are in P(A)?
Show hintHide hint
Each element can either be included or not included.
3Question 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
Show hintHide hint
Think about who originally presented the concept of comparing sizes of infinity.
4Question 4.
If a set has 5 elements, how many elements does its power set have?
- True
- False
Show hintHide hint
Remember the formula for calculating the power set.
Question 5.
Consider a set with 4 elements. Prove that there exists no surjective function from this set to its power set.
Show hintHide hint
Define the function and illustrate the mapping before finding S.
Question 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?
Show hintHide hint
Remember that each application of Cantor's theorem shows distinct infinities.

5 more questions in this section. Enroll free to practise them all.