Re: An uncountable countable set

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?

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.

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.


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.

.

Relevant Pages

  • Re: Well Ordering the Reals
    ... You are confusing arithmetic exponentiation and the cardinality of powersets - they are not the same thing, ... These are precisely the types of expressions I want to see distinguished, not all lumped together as if arithmetic becomes meaningless for infinite values. ... Since each term represents the number of points your mapping defines at each step, we conclude that your mapping defines only a countably infinite number of points in total. ... a countably infinite number of points, which is far too small to cover the reals. ...
    (sci.math)
  • Re: Limit of Binary Lists
    ... we were filling in agrid. ... example of a Cantor space is the countably infinite topological ... I found the phrase "countably infinite topological product" ...
    (sci.math)
  • Re: Earth 8??
    ... Ophidian wrote: ... The usual proof goes as follows (we'll only consider positive reals ... countably infinite list to begin with. ... If you have a countably infinite set and an uncountably infinite set, ...
    (rec.arts.comics.dc.universe)
  • Re: Uncountability of the Rationals?
    ... absolute size and those that do not. ... infinite sets, especially the standard N, starting at 0. ... Wouldn't it be easier to say that some chosen countably infinite ... since it contains all of the countable naturals. ...
    (sci.math)
  • Re: Uncountability of the Rationals?
    ... absolute size and those that do not. ... infinite sets, especially the standard N, starting at 0. ... Wouldn't it be easier to say that some chosen countably infinite ... since it contains all of the countable naturals. ...
    (sci.math)