Project ForgeLet N be the set of natural numbers. Consider the following sets:
P: Set of rational numbers (positive and negative) Q: Set of functions from {0,1} to N R: Set of functions from N to {0,1} S: Set of finite subsets of N
Which of the sets above are countable?
- AQ and S only
- BP and S only
- CP and R only
- P, Q and S only
Explanation
P (rationals) is famously countable. Q (functions from a 2-element set to N) is equivalent to N×N, which is countable. S (finite subsets of N) is a countable union of countable sets (subsets of each finite size), hence countable. R (functions from N to {0,1}) is equivalent to the power set of N — this has the cardinality of the continuum and is UNCOUNTABLE (diagonalization argument). So P, Q, and S are countable.
Source: GATE CS 2018 (2018)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.