Re: An uncountable countable set
- From: Tony Orlow <tony@xxxxxxxxxxxxx>
- Date: Tue, 05 Sep 2006 11:16:08 -0400
David R Tribble wrote:
Tony Orlow wrote:Any finite number of bit positions produces a finite set of strings.
Any countably infinite set of bit positions produces an uncountable set of
strings.
Tony Orlow wrote:Which explains why the reals are uncountable (when represented as
infinite binary fractions in [0,1)).
Tony Orlow wrote:Yes, ala Cantor's second proof of uncountability.
David R Tribble wrote:But it does not explain your claim that the naturals are uncountable
when represented as finite bitstrings. It's pretty straightfoward to
show that a countable number of bits produces a countable number
of bitstrings. There is no "in-between" cardinality.
Tony Orlow wrote:You just contradicted yourself.
You agree that [me] "Any countably infinite set of bit positions
produces an uncountable set of strings", right? That's what [you]
"explains why the reals are uncountable (when represented as infinite
binary fractions in [0,1))"?But, [you] "a countable number of bits
produces a countable number of bitstrings"? Is a countably infinite
number of bits countable or not? If so, then does a countably infinite
number of bit positions produce a countable, or an uncountable, set of
strings?
Why did you attribute the sentence, "a countable number of bits produces a countable number of bitstrings", to me, when you clearly wrote it right above? You contradicted yourself.
A slight misunderstanding, so I'll rephrase it (even though you've
heard it all before).
If every bitstring contains a finite number of bits, the set of all
finite bitstrings (or binary naturals, or finite-length binary tree
paths) is countably infinite.
According to your theory, if the set contains EVERY finite bit string, yes.
If the bitstrings are infinite, containing a countably infinite number
of bits, the set of all infinite bitstrings (or nonterminating binary
real fractions, or nonterminating infinite binary tree paths) is
uncountably infinite.
Right. So, why did you say that "It's pretty straightfoward to
show that a countable number of bits produces a countable number
of bitstrings"????
.
David R Tribble wrote:It also flies in the face of your statements about infinite binary
trees. If each node is numbered with a natural (being the finite
bitstring of the left/right paths traversed from the root to the node),
then the nodes, and thus the naturals, are obviously countable.
On the other hand, you don't understand that the infinite paths in
the tree (the ones that don't have a terminating node) are uncountable
and correspond directly to your infinite bitstrings and to the real
binary fractions in [0,1).
Tony Orlow wrote:I'll wait for your response on the above, since you're still not ready
for the answer you've already heard for this. Please don't snip it. It's
a good question, and a prime example of standard issues.
- Prev by Date: Re: Questions about Axiom of Choice
- Next by Date: Re: Possible textbook error: fixed point functional iteration limit proof
- Previous by thread: Re: An uncountable countable set
- Next by thread: Re: An uncountable countable set
- Index(es):
Relevant Pages
|
