# CS 173: Skills list for Examlet 3

• Cardinality
• Define what it means for two sets to have the same cardinality: i.e. there is a bijection mapping one onto the other.
• Show that two sets have the same cardinality by constructing a specific bijection between them.
• Define when |A| <= |B|, i.e. there is a surjective (onto) function from B to A.
• One can also conclude |A| <= |B| if there is an injective (1-to-1) function from A to B
• Cantor-Schroeder-Bernstein Theorem: If |A| <= |B| and |B| <= |A| then |A| = |B|. Very useful in proving that two sets have the same cardinality as sometimes coming up with a bijective function is difficult.
• Know the definitions:
• A countably infinite set is a set with the same cardinality as the natural numbers.
• A countable set is either countably infinite or finite.
• Uncountable sets: infinite sets that do not have the same cardinality as the natural numbers.
• Know these examples of countable sets, identify examples similar to these as countable.
• pairs of integers or natural numbers
• rational numbers
• Cartesian product of countable sets, i.e., if A and B are countable then AxB is also countable.
• Union of countable sets is countable, i.e., if A and B are countable then AuB is countable.
• Know these examples of uncountable sets, identify examples similar to these as uncountable
• the reals, an interval of the reals (e.g. [0,1])
• the power set of the integers (or any other countably-infinite set)
• products containing an uncountable set (e.g. pairs of reals, complex numbers)
• a set that contains an uncountable subset (e.g. the reals with other stuff added)
• set of functions from natural numbers to {0,1}.
• Other uncountability facts
• Know that, for any set A, the power set of A has larger cardinality than A.
• Know how to use diagonalization to prove sets to be uncountable.