Misc
Final Exam
Wednesday, May 10, 12:00 noon
Comprehensive, but emphasizes material since second hour exam (e.g., set theory, functions, equivalence relations, infinite cardinalities, etc.)
Designed for about 1 1/2 hours, you’ll have 2 1/2.
There will be one closed-book question at the beginning of the test, then the rest will be open-book (and open-notes, open-computer, etc.)
Otherwise the rules and format will be similar to the hour exams.
I’ll bring donuts and cider.
Review Session
I’ve had one request to do one on study day, would that be generally popular?
I’ll look for a time during the afternoon when we can do it.
SOFIs
No responses yet. Please do fill it out.
Questions?
Countable Sets
Prove that the cross product of 2 countably infinite sets is countably infinite.
Relevant ideas or questions from the last reading (section 9.2):
- There really wasn’t anything about cross products.
- But the essence of a cross product is ordered pairs, so was there anything in the reading that involved pairs of any sort?
- The proof that the set of positive rationals is countably infinite did, in the sense that every rational number is a numerator paired with a denominator.
- So what was that proof’s key idea for dealing with pairs?
- To realize that numbering them along the diagonals of a table gives you a way to eventually assign a natural number to every pair (i.e., the numbering is surjective), and to ensure that each natural number maps to a unique rational (i.e., the numbering is injective).
Proof. Write the ordered pairs in a tabular form, with pair (i,j) in row i, column j of the table (since both sets are countable their elements can be mapped to natural numbers for the “(i,j)” notation if they aren’t natural numbers to begin with). Then assign natural numbers to the pairs along diagonals of this table. Every pair corresponds to a unique natural number in this numbering scheme, so the numbering is a bijection. Thus the set of ordered pairs in the cross product of two countably infinite sets is equivalent to the naturals, and so the cross product is countably infinite.
Comments:
- This is another step up from the countably infinite hotel and unions, in that they informally corresponded to saying that the sum of countably infinite cardinalities is still countably infinite, but now we have that a product is too.
Next
Uncountable Sets.
Read textbook section 9.3 if you haven’t already.