Recitation of Mar. 19, 2013

We quickly went through the proof of uncountability of the reals again. I showed a practical consequence of this: some problems cannot be solved by computers.

We then discussed countability of the set of pairs of natural numbers (sketching an alternate proof using the uniqueness of prime decomposition), and went through exercise 4.48 in details.

In the test, it will be enough to show how to build a sequence to show that a set is countable (i.e. no need to give an explicit formula, as long as it is clear how to construct the sequence). In general, the question: "what is the right level of details needed in a mathematical proof ?" is a difficult one that essentially depends on who is going to read your proof :-) . You should give enough details so that everybody (including you) reading your proof can be absolutely convinced of its correctness.

Personally, I believe it is possible to give too much details, to the point of hurting understanding. An extreme example is the book Principia Mathematica published at the beginning of the 20th Century by Russel and Whitehead, which takes 379 pages to prove that 1 + 1 = 2.