EvLer said:
so among countable sets there is no ordering of cardinality except the power set (that is the only one I have heard about); and so power set of a countable set is also countable, right?
sorry for all the questions: have exam coming up...
edit:
oh, so power set of a countable set is not countable?
Could someone provide a proof sketch? I have been searching, but can't find much relevant stuff...
I'm not sure what you mean by "no ordering of cardinality except the power set". The power set is a set, not an "ordering". It is true that the cardinality of of the power set of set A is always strictly larger than that of A itself. However, given any two sets, A, B, one and only one of these three must be true:
1) Cardinality of A is larger than Cardinality of B.
2) Cardinality of A is smaller than Cardinality of B.
2) Cardinality of A is equal to Cardinality of B.
(In other words, order by cardinality is a linear order.)
In your first post you asked
can someone give an example when Cantor's diagonalization is applied to countable sets and how it works out...
It's not clear to me what you mean by that: You CAN'T apply Cantor's diagonalization to countable sets since it implies uncountability. You may mean "what goes wrong when you
try to apply it".
Here's a "proof" that the set on counting numbers itself is uncountable- you often see it given by people who think they can show Cantor's method is wrong. There's an obvious error. See if you can find it.
Order the counting numbers in the obvious way: 1, 2, 3, etc. Think of each of them as an infinite string of digits by appending an infinite string of 0's : ...000000...00001, ...00000...00002, etc. Now go through the list of counting numbers creating a new number, x, by applying Cantor's method: if the nth (from the right- the ones place) digit of the nth number is a 2, write a 7 in the nth digit of x, if it is not a 2, write a 2. (I've pretty much just chosen those numbers at random.) Obviously this new number x will not be equal to any of the numbers on the list (it is different from the nth number in the list in the nth digit) and so is not on the list itself. Since, given any list of counting numbers we can produce a new number that is not on the list, it follows that the set of
counting numbers is not
countable!
Again, that is
not a valid proof! Can you see the error?