Re: Countability of real numbers
- From: Virgil <virgil@xxxxxxxxxxx>
- Date: Fri, 03 Nov 2006 17:29:46 -0700
In article <454b7923@xxxxxxxxxxxxxxxxxxx>,
Tony Orlow <tony@xxxxxxxxxxxxx> wrote:
Ajeet wrote:
Hi Everyone,
I have a question related to diagonalization in the countability of
real numbers. I have read that the set of all strings is countable. The
proof involves enumerating all strings with length 1, 2, and so on.
Shouldnt we be able to extend this to real numbers? for example, start
with all real numbers with the number of digits = 1, 2, .. etc.
Viewing this in another way, shouldnt Cantor's proof that real numbers
are uncountable extend to the set of all strings on an alphabet as
well?
Am I missing something? Any help is appreciated.
Regards,
Ajeet
Hi Ajeet -
I looked at the other responses, and while Jesse might think he's being
helpful, it's got that, "No, here's where you're wrong" feel to it that
set theorists love to create. I'll not complain further about that...
Essentially, what "countable" means is that every element in the set,
given some order, has a finite index in the set, that is, is finitely
far from the beginning. When such a set is defined as "all finite
indexes", that's countably infinite. It's considered infinite because
the set of finite naturals can have an injection into a proper subset of
itself, because it has no upper bound, and any bijection just continues
until...whenever.
When a set is "uncountable", that means that, in any given order, there
exist elements which are infinitely far from the beginning of the
sequence. What this translates into, as far as the language of the
number system used to represent these numbers, is that there will exist
elements in the set which require infinitely long strings.
To the extent that the sets cannot be indexed by finite strings, T is
right, but that does not require that an uncountable set be indexable by
infinite strings either.
In ZF, P(P(N)) is uncountable bur cannot be so indexed.
So, back to Cantor's diagonal argument. It uses an alphabet, {w, m}
originally, but often using decimal these days. It constructs numeric
strings according to n-ary representation (binary and up), and assumes a
countably infinite list, where each string need not be more than finite.
It notes that, at any finite point in the list, one can always construct
a string which does not already exist on the list, and therefore, no
matter how many reals you list, there must always be more. It's true.
There are more reals in the unit interval than can be listed using
finite indexes.
While the argument is significant in a sense, it's not beause of the
difference between countable and uncountable, or potential and actual
infinity. That's not really new. It's basically the same as the power
set relation, where the power set of a set is always larger than the
set. The set of strings of length L from an alphabet of size S is S^L,
larger than S for S>1 and L>1. And, this holds true for all S and L.
N=S^L. :)
Only for finite S and L.
.
Tony
- References:
- Countability of real numbers
- From: Ajeet
- Re: Countability of real numbers
- From: Tony Orlow
- Countability of real numbers
- Prev by Date: Re: A simple question?
- Next by Date: Re: regular maps
- Previous by thread: Re: Countability of real numbers
- Next by thread: Re: Countability of real numbers
- Index(es):
Relevant Pages
|
