Class 18: Infinite Sets
Schedule
Before Thursday, everyone should have finished reading MCS Chapter 8.
Problem Set 8 is due Friday (4 November) at 6:29pm.
I am out of town Wednesday and will not be able to hold my normal office hours.
Friday, 4 November at 11am (Rotunda Dome Room): Steve Huffman (BSCS 2005, co-founder and CEO of Reddit), Computer Science Distinguished Alumni Speaker.
Exam 2
Exam 2 will be in class on Thursday, 10 November. It will be similar in format to Exam 1. If you need to make special arrangements for taking Exam 2, please contact me by the end of this week (Nov 6).
Resources. As with Exam 1, you will be permitted to use a single paper page of notes that you prepare and bring to the exam. It is fine to collaborate with others to prepare your notes. The page should be no larger than a US Letter size page ($8.5 \times 11$ inches), and you may write (or print) on both sides of the page. No other resources are permitted during the exam.
Content. The problems on the exam will cover material from Classes 1–17, Problem Sets 1–8 (including the provided solutions), and MCS Chapters 1–7. Exam 2 will emphasize material covered since Exam 1 (Classes 12–17, Problem Sets 6–8, and MCS Chapters 6–7), but will also include questions that cover earlier material in the class. In particular, you should not be at all surprised if Exam 2 includes questions very similar to Problem 4 and Problem 8 from Exam 1, so it would be quite foolish for any student to go into the exam without making sure they understand those problems and their solutions. There will not be any questions about trick-xor-treat protocols, despite their practical importance and mathematical beauty. If you understand the problems on the problem sets and questions on the class notes well enough to be able to answer similar questions, you should do well on the exam.
The main topics the exam will cover include:
State Machines (how to interpret and reason about a state machine given its formal description, how to model a problem with a state machine)
Invariant Principle (you should be able to construct a proof that uses the invariant principle to reason about properties of reachable states, and be able to understand proofs that use and mis-use the invariant principle)
Termination Proofs (you should be able to prove a state machine eventually reaches a terminating state, or that a program eventually terminates)
Stable Matching (you should understand the definition of a stable matching and the Gale-Shalpey algorithm for finding a stable matching, and be able to prove properties about matchings)
Recursive Data Types (how to define a data type constructively, operations on recursive data types; lists, trees, and other recursively defined data types)
Structural Induction (how to use the principle of structural induction to reason about all objects of a recursive data type; understand the connections and differences between structural induction, invariant principle, and induction on the natural numbers)
For most students, I believe the best way to prepare for the exam will be to (1) go over exam 1 and the problem sets and their solutions, and make sure you understand well any of the problems you did not get before; (2) go through the questions in the class notes and convince yourself you can answer them well; (3) re-read chapters of the book, solving the associated practice problems, especially for any sections on topics where you had difficulty on the problem sets. If you do #1 and understand well the problems on the problem set, you should be confident you’ll do well on the exam; if you struggled on the problem sets, you would benefit from doing #2 and #3 as well. If you have anything you want me to review before the exam, post on slack before Monday (7 November).
Links
Apostolos Doxiadis and Christos Papadimitriou. Logicomix: An epic search for truth, Bloomsbury USA, 2009.
Math Professors at UVa (1825-1900)
Courtenay’s tenure at Virginia was, in contrast to that of his predecessor, a resounding success. He was described as a model professor: “He never by look, act, word, or emphasis disparaged the efforts or undervalued the acquirements of his pupils. His pleasant smile and kind voice, when he would say, ‘Is that answer perfectly correct?’ gave hope to many minds struggling with science”
Charles Bonnycastle, UVA’s Professor of Mathematics, 1825-1840
As mathematics professor, “Old Bonny,” as he was fondly called, replaced the antiquated British approach to mathematical pedagogy typified by his own father’s texts with a new approach borrowed from French mathematicians. British writers had imitated Euclid by clinging to the deductive manner of presenting material. They opened their texts with axioms and definitions and proceeded to the derivation of facts and theorems. Although logically satisfying to mathematicians, the method did little to motivate beginning students. French textbook writers, on the other hand, approached mathematics analytically, leading from concrete examples to abstractions. Bonnycastle introduced this method at the University of Virginia and published his own college textbook, Inductive Geometry, or, An Analysis of the Relations of Form and Magnitude: Commencing with the Elementary Ideas Derived Through the Senses, and Proceeding by a Train of Inductive Reasoning to Develop the Present State of the Science (1834). Painfully prolix even by nineteenth-century standards, the innovative book was not a financial success. (Excerpt from article by Karen Parshall)
Infinite Sets
Finite Cardinality. The cardinality of the set $$ \mathbb{N}_k = { n | n \in \mathbb{N} \wedge n < k } $$ is $k$. If there is a bijection between two sets, they have the same cardinality. (Class 9)
Does this definition tell us the cardinality of $\mathbb{N}$?
###
Definition. A set $C$ is infinite if there is no bijection between $C$ and any set $\mathbb{N}_k$ (as defined above).
Dedekind-Infinite. A set $A$ is Dedekind-infinite if and only if there exists a strict subset of $A$ with the same cardinality as $A$. That is, $$\exists B \subset A \ldotp \exists R \ldotp R\ \text{is a bijection between}\ A\ \text{and}\ B.$$
Are the definitions of (standard) infinite and Dedekind-infinite equivalent?
##
Definition. A set $C$ is countable if and only if there exists a surjective function from $\mathbb{N}$ to $C$. (That is, $\le 1$ arrow out from $\mathbb{N}$, $ge 1$ arrow in to $C$.)
Definition. A set $C$ is countably infinite if and only if there exists a bijection between $C$ and $\mathbb{N}$.
Must a countable set that is Dedekind-infinite be countably infinite?
Prove that these sets are countable: $\mathbb{Z}$, $\mathbb{N} \times \mathbb{N}$, $\mathbb{Q}$ (rationals), $\emptyset$, $\mathbb{N} \cup (\mathbb{N} \times \mathbb{N}) \cup (\mathbb{N} \times \mathbb{N} \times \mathbb{N})$, all finite sequences of elements of $\mathbb{N}$.