From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Mon Jan 14 14:53:35 2008 Date: Mon, 14 Jan 2008 14:50:42 -0500 From: "William J. Rapaport" Subject: Countability To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: Countability ------------------------------------------------------------------------ After today's class, several of you asked me about "countability": What does it mean to say that a set is countable? (By the way, some mathematicians use the term "denumerable" instead.) Informally, a set is countable if you can count its members. So, what does it mean to count the members of a set? Well, you put the members in some order, and then you start counting: 1, 2, 3, .... You have to make sure that you count each member, and you have to make sure that you don't count any member more than once. (That's why you put them in some order.) More formally, counting just means matching each member of the ordered set with a unique member of the set of counting numbers, which are usually taken to be N+, the positive natural numbers: 1, 2, 3, .... (Only some weird mathematicians and computer scientists count starting with 0, i.e., by using N, the natural numbers: 0, 1, 2, 3, .... :-) Such a matching is called a "1-1 correspondence". If a set can be put into 1-1 correspondence with (a subset of) N+, then it is countable. Obviously, N+ is countable. As I noted in lecture, so are N, Z, and Q. If you can count these sets, then how many members do they have? The number of members of a finite set is the last element of N+ that is needed in the 1-1 correspondence. E.g., the set {a,b,c,d,e,f,g,h,i,j} has 10 members, because of this 1-1 correspondence: a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 For infinite sets, it's a bit different. By definition, the size (also called the "cardinality" or "cardinal number") of N+ is denoted by the Hebrew letter aleph, with the subscript 0: aleph_0, pronounced "aleph-null". Because the size (or "cardinality") of N+ = the size of N = the size of Z = the size of Q they all have cardinality aleph_0. What about R? There is a proof that R has more members than Q, not merely because it's continuous and has no gaps, but because it is not countable. That is, it cannot be put into 1-1 correspondence with N+. By definition, its size is called aleph_1, which is > aleph_0. How big is aleph_1? The "continuum hypothesis" says that aleph_1 = 2^aleph_0, i.e., 2 raised to the aleph_0 power. No one has proved this. Rather, what has been proved is that it cannot be proved. Moreover, neither can its negation! In other words, the continuum hypothesis is "independent" of the rest of set theory. You can take it as an axiom, if you want; but you can equally take its negation as an axiom! For more information, see Rosen, pp. 158-160, and these websites: http://plato.stanford.edu/entries/settheory-early/ http://mathworld.wolfram.com/Aleph-0.html http://en.wikipedia.org/wiki/Countable http://en.wikipedia.org/wiki/Aleph_number