SUNY Geneseo Department of Mathematics
Monday, May 6
Math 239 01
Spring 2019
Prof. Doug Baldwin
Sample questions are now available through Canvas.
Exam is next Monday, May 13, 12:00 Noon, in our regular classroom.
Comprehensive, but emphasizing material since 2nd hour exam (e.g., sets, functions, relations, infinite sets; problem sets 7 through 10).
Rules and format otherwise similar to hour exams, especially open-references rule.
2 1/2 hours but designed for about 2 hours, i.e., less time pressure
I’ll bring donuts and cider.
Thursday, May 9 (study day)
11:00 - 12:00
Fraser 213
Please bring things you want to talk about.
SOFIs are under way.
9 responses (37.5%) so far. Thank you!
But more responses are always helpful. I do read them and apply the feedback where possible to future classes (like the mid-semester feedback).
We proved Friday that the set of functions from ℕ to ℕ is uncountable.
We also suspected that the set of strings creatable from the symbols on a computer keyboard is countably infinite.
Prove this (or come up with a better classification of the cardinality of the set of strings).
Proof outline: enumerate (i.e., assign a (natural) number to) strings in order of their length. Let k be the number of distinct characters the keyboard can generate:
Enumerate the single length-0 string: assign it to 1
Enumerate the k length-1 strings: assign them numbers 2 through k+1
Enumerate the k2 length-2 strings: assign them numbers k+2 through (k+1) + k2.
Continue in this manner with the length-3, length-4, etc. strings.
This enumeration will assign a number to every string, i.e., given any string you can find its number in this enumeration. So the enumeration is a surjection. Furthermore, it only assigns one number to each string, i.e., it’s an injection. Thus we have a bijection between strings and natural numbers, so the set of strings is indeed countably infinite.
Another argument is to let the k characters stand for the base-(k+1) digits 1 through k (don’t use 0 to avoid problems with leading 0s). Then every string can be thought of as the base-(k+1) representation of a distinct natural number, so the set of strings corresponds to a subset of the naturals. Thus the set of strings is countable (but maybe finite). Furthermore, the set of strings is infinite. To see why, assume otherwise, i.e., the set of strings is finite. Then there is a longest string (or maybe several tied for longest). Take the longest string and add an “A” (or any other character) at the beginning. Now you have a string that’s longer than the longest, a contradiction. Since the set of strings is both countable and infinite, it must be countably infinite.
Why does this matter? Because every computer program is a string, so the number of possible programs is countably infinite. But the set of functions from ℕ to ℕ is a plausible set of things you might want to compute. In other words, there aren’t nearly enough possible programs to do all the possible computations. And some of those impossible computations are ones it really would be nice to do, e.g., perfect anti-virus protection.
Is the set of irrational numbers countable or uncountable? Prove your answer.
Claim: uncountable.
Proof outline: Contradiction. Assume the irrationals are countable. The reals are the union of the rationals and irrationals. We know the rationals are countable, and the union of 2 countable sets is countable, so the reals must be countable. But we know they aren’t.
Here is a formal version of this proof and its LaTeX source.
There are other ways of proving claims about cardinality beside finding bijections. In particular...
Cantor’s Theorem.
(Re-)read about it at the end of section 9.3.