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.