21127 Study Guide - Midterm Guide: Countable Set, Uncountable Set, Enu
16 Dec 2015
School
Department
Course
Professor
Document Summary
Identify the following sets and their cardinalities. (no proof required, just an answer. ) (cid:92) x r (cid:92) x z (cid:92) x n (cid:91) x r (cid:91) x z (cid:91) x n. Sx (2) prove that r n is uncountably in nite. (hint: find a surjection from this set to another set. Or, nd an injection from some set to this one. ) (3) consider the set s of all in nite binary strings. We proved that s is uncountably in nite before. Consider the set t s that is the set of all in nite binary strings with only nitely many 1s. In this problem, you will prove that t is, in fact, countably in nite! (a) consider the set nk of all ordered k-tuples of natural numbers. (note: n1 = n and n2 = n n. ) Provide an inductive argument that shows that nk is countably in nite for every k n. (hint: this should be a pretty short proof.
