Re: infinity

David R Tribble said:
> David R Tribble said:
> >> The difference between the sizes of *N and P(*N). Apparently, you
> >> think they are the same, but they aren't.
> >
>
> Tony Orlow wrote:
> > No, I think that you can construct a bijection between their binary
> > representations, DESPITE the fact that they are obviously not the same size.
> > That's my point.
>
> I'd like to see this alleged bijection between *N and P(*N) before I
> believe it. If we agree that they are different sizes, then such a
> bijection cannot exist.
>
>
Consider the infinite binary tree. Each path consists of an infinite string of
bits. Each infinite string of bits corresponds to one of the infinite strings
of bits in the set of binary representations of n in *N, as well as to the
infinite bit strings representing membership of each of those n in each of the
set members of P(*N). In the first, each path is a number in *N and in the
second each path is a set in P(*N). The infinite bit strings are enumerated in
the usual natural order, ...00001, ...00010, ...0011, ...00100, etc. Is not a
common bijection with a set of paths in an infinite binary tree a bijection by
virtue of the transitivity of bijection?

Now, of course, these sets are not the same size. We can see this by looking at
where the naturals lie in the second tree, because obviously the subsets of *N
do not lie in the first. In the second tree, each path, each bit string,
represents a set as defined by the inclusion or exclusion of each n in *N. The
first bit of each path determines whether 1 is in each set, the second whether
2 is a member, etc. So, in the second tree, each n in *N is represented by a
horizontal row of branches in the tree, not a path of branches through the
tree. For each successive level added to the tree, the number of paths is
doubled, so the number of paths is 2^n at level n. That is why the power set
for a set of size n has 2^n members. The second tree has the same number of
levels as the first has of paths.

So, bijection <> equivalence.
--
Smiles,

Tony
.

Relevant Pages

  • Re: Cantor and the binary tree
    ... I consider an infinite tree. ... If you mean that there is a bijection between paths and reals, ... Assume a binary tree in which each node is a parent and has a left-child ...
    (sci.math)
  • Re: Orlow cardinality question
    ... >> the infinite set of natural numbers and the sets they each define. ... >>> infinite in a a maximal binary tree. ... > bijected with the naturals. ... I never said the bijection doesn't exist. ...
    (sci.math)
  • Re: Another set with cardinality |Z|
    ... Or if we view it as a directed tree, ... Suppose there were a bijection ... an infinite path in the tree is a mapping from the naturals to the set ... A "Zwicker path" starts by picking a integer i. ...
    (sci.math)
  • Re: infinity
    ... >>> that bijection comes first. ... >>> If either the number of characters in the alphabet or the string ... >> If you either allow an infinite alphabet or infinite strings? ... >>> One maximal binary tree works for both. ...
    (sci.math)
  • Re: Another set with cardinality |Z|
    ... Or if we view it as a directed tree, ... Suppose there were a bijection ... an infinite path in the tree is a mapping from the naturals to the set ... A "Zwicker path" starts by picking a integer i. ...
    (comp.theory)