CS 173: Skills list for the final

The Final is Comprehensive

New topics are listed below.

Countability

• 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 one-to-one function from A to B.
  • Know the definitions:
    • A countably infinite set is a set with the same cardinality as the integers (or the natural numbers).
    • A countable set is either countably infinite or finite.
    • Uncountable sets: infinite sets too large to be countable.
• Know these examples of countable sets, identify examples similar to these as countable.
  • pairs of integers or natural numbers
  • rational numbers
  • the set of finite-length strings (with some specified finite character set)
  • the set of all finite formulas or computer programs (each item finite, but with no restriction on length).
  • subsets of countable sets
  • a finite product of countable sets (E.g. if A is countable then so is the set of 5-tuples of elements of A.)
  • a countable union of countable sets
• 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 of 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)
  • the set of infinite-length sequences of bits
  • the set of all functions from an infinite set (e.g. the integers) to a set with at least two elements
• Other uncountability facts
  • Know that, for any set A, the power set of A has larger cardinality than A.
  • Know that there are functions that don't have finite formulas, and functions that can't be computed by any program.
  • Know that it's impossible to build a program that determines whether an input program halts or runs forever (aka the Halting Problem).
  • (You won't need to reproduce the constructions (e.g. diagonalization) that were used to prove these results.)