SUNY Geneseo Department of Mathematics
Wednesday, April 25
Math 239 01
Spring 2018
Prof. Doug Baldwin
Thursday, May 3, 12:00 noon to 2:30 PM, in our regular room.
Comprehensive, but with an emphasis on material since the 2nd hour exam (e.g., induction, sets, functions, relations, infinite sets).
Designed to be 2 to 2 1/2 times as long as the hour exams, but you have 3 times as much time.
Rules and format otherwise similar to hour exams, especially the open-references rule.
I’ll provide a sample from a past semester.
I’ll bring donuts and cider.
2 have been done so far. Thank you!
They are useful to me in improving courses for the future, and thus useful to you if you ever take another course with me (and you get 1 printing dollar per SOFI), so please fill them out.
Section 9.1.
Show that the set of people in this room is equivalent to the set {A,B,C,...Y}.
You can do this by simply checking that you can assign a letter to each person in the room. That assignment of letters to people is a bijection between the set of people and the set of letters, i.e., what it takes to establish that the sets are equivalent.
You could also achieve the same thing by counting the people in the room and the letters and checking that the counts are equal. This is the idea that equivalent sets have the same size.
Show that the set of integers is equivalent to the set of natural numbers.
Note that “equivalent” in this context is a technical term, it specifically means that there is a bijection between the sets, not the more colloquial meanings of the word such as the two sets simply being the same or interchangeable in some sense.
So we need to find a bijection between the naturals and the integers.
One way to do this is to list a matching of the two sets to get a sense for whether a bijection can exist, and if so what it might look like.
Now we should nail things down by actually defining the bijection as a function, although we can be fairly flexible in how we do that. One possibility is the function from problem set 9 that happens to be a bijection between naturals and integers:
Another possibility is a piecewise function motivated by thinking about a bijection from integers to naturals (either way is sufficient, since bijections are invertible, so having a bijection from set A to set B implies that there is also a bijection from B to A).
This example of “equivalence” is much more puzzling than the previous one, because intuitively there are more integers than naturals. And yet at the same time there aren’t, because as the picture and bijections show, you can match every integer with a natural and vice versa. The moral is that all your intuitions about numbers break down when dealing with infinity.
Prove that the set of perfect squares (i.e., { 0, 1, 4, 9, 16, ... }) cannot be finite.
Idea 1 (If you know the set of naturals is infinite): Show that the perfect squares and naturals are equivalent, e.g., with the bijection f(n) = (n-1)2.
Idea 2 (Using just ideas from today’s reading): Assume the set of perfect squares is finite. Then it is equivalent to ℕk for some natural number k. Now consider any bijection, call it f, between the perfect squares and ℕk. Such a bijection must exist, because the sets are equivalent. That bijection maps the k perfect squares between 1 and k2 to distinct elements of ℕk, because it is a bijection. But it also has to map 0, which by the pigeonhole principle must map to the same element of ℕk as one of the squares between 1 and k2. Thus f is not a bijection after all, which is a contradiction.
Equivalence means bijection.
Infinity is a tricky thing.
Techniques for proving sets infinite.
Countable (but often infinite) sets.
Read section 9.2.