CS 173: Skills list for the 'final'

• [~12 points] 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.)

[~48 points] Cumulative review