Re: infinity ...

David R Tribble said:
> Tony Orlow wrote:
> >> I already showed you the bijection between binary *N and P(*N).
> >> What didn't you like about it? It is valid.
> >
>
> David R Tribble said:
> >> No, you showed a mapping between *N and R, which is equivalent
> >> to a mapping between *N and P(N). That's easy.
> >
>
> Tony Orlow wrote:
> >> No, it was specifically a bijection between two sets of infinite binary
> >> strings representing, on the one hand, the whole numbers in *N starting
> >> from 0, both finite and infinite, in normal binary format, and on the other
> >> hand, the specification of each subset of whole numbers in *N, where each
> >> bit which, in the binary number, represents 2^n denotes membership of n in
> >> the subset. This is a bijection between the whole numbers in *N and P(*N),
> >> using an intermediate bijection with a common set of infinite binary
> >> strings.
> >
>
> David R Tribble said:
> >> But that's an incomplete mapping, because there are not enough infinite
> >> binary strings in *N to enumerate all of the subsets of *N. Try it,
> >> if you don't believe me.
> >
>
> Tony Orlow wrote:
> > Not enough infinite binary strings? How many in *N and in P(*N)?
> > Are you saying that I cannot construct a bijection between the two on an
> > element-by-element basis which continues infinitely through the set of
> > binary strings?
>
> That's exactly what I'm saying.
>
> card(*N) = c, but card(P(*N)) = 2^c, and c < 2^c.
At what point does the bijection break down? It certainly works for all finite
cases, does it not? What makes you think it falls apart at some point? For
which element is there not a corresponding subset? For which subset is there no
corresponding element? Name either one of these, as a counterexample, or
explain why you think the bijection fails.
>
>
> > Where does it stop? You aren't beginning to see that determining the
> > infinite value range is crucial to this problem after all, are you?
>
> If you think that approach will work, then show us how.
>
> By the way, what is the "range" of a powerset, whose members are
> sets themselves?
Sets don't have an inherent measure beyond raw size, and the power set is not
well ordered as far as subset size goes, so it doesn't make sense to talk about
a value range on the power set exactly. However, one might think of the binary
mapping of the power set to the set, and say that the power set of an ordered
set has an order based on that mapping, taking each bitstring as a natural. In
this case, you might be tempted to say, if the set has N elements, the power
set has a range of 2^N-1.
>
>
> > What do you want me to try, anyway, and infinite mapping,
> > element-by-element? A bijection's a bijection, right?
>
> Yes, that would be nice. Please show us your bijection.
f(0) = ...000 = {}
f(1) = ...001 = {0}
f(2) = ...010 = {1}
f(3) = ...011 = {0,1}
f(4) = ...100 = {2}
f(5) = ...101 = {0,2}
f(6) = ...110 = {1,2}
f(7) = ...111 = {0,1,2}

etc. Any questions?
>
>
> > These sets are obviously of the same cardinality, since I have a
> > bijection which carries to infinity, right?
>
> No, their sizes are different cardinalities, which happen to be
> different infinities. Both sets are infinite, but one set is
> larger than the other.
But I have constructed a bijection between the two using an intermediate binary
representation. What is the specific rule I have broken concerning the
construction of bijections. If I haven't broken any such rule, then is it true
that a bijection between two sets means that have the same size, or even
cardinality?
>
>
> > For every subset there is a unique natural and for every natural there is
> > a unique subset. If you disagree, please state which of either has no
> > corresponding element in the other.
>
> Like I said, there are not enough naturals to map to every subset
> of the naturals.
Which subset, specifically, is left unmapped? If you claim there is one, then
surely you can name it?
>
> This is true whether you've got infinite naturals or not; there are
> not enough members in N to enumerate all the subsets in N, and
> likewise there are not enough members in *N to enumerate all the
> subsets in *N.
But, as the keepers of that standard say, what holds for the finite case does
not necessarily hold for the infinite case. Once you have infinite sets,
neither one ends, and there is always a natural for any subset, and always a
subset for any natural. Isn't this the way the standard treatment of bijection
goes for infinite sets?
>
>
> > Please try to frame your objection in a more operative manner. How do you
> > know there aren't a large enough infinity of bits for the power set vs the
> > values in the set?
>
> Because I can prove it (and it's a very old proof). A powerset of
> a nonempty set contains more elements that the set. Can you prove
> otherwise?
No, I fully agree with that conclusion. However, there is nothing that
precludes a bijection between any ordered infinite set and its power set,
despite the different sizes. My point is that bijection alone does not mean
equal size, as this example shows well. Two infinite sets may have a bijection
while one contains some finite number of elements more than the other, some
finite multiple of the other's number of elements, or some formulaic relation
that shows one to be infinitely greater than the other, like N^2. Such
bijections are taken to imply equal size, or at least cardinality, and yet, a
bijection CAN be constructed between any ordered infinite set and its power
set, which contradicts the power set rule.
>
>

--
Smiles,

Tony
.

Relevant Pages

  • Re: Well Ordering the Reals
    ... >> the power set of the power set of the power set of the naturals? ... There is really no reason to ... and that is why the precise measurement and comparison of infinite ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... > I suppose if you have the null set, the power set of the null set is ... You haven't given me a separate meaning of "infinite ... > If *N is the set including al naturals finite and infinite, ... But *N cannot exist as a set of strings until after it has been created ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... >>> want to map to the power set of the power set of the power set of ... >>> the naturals? ... >> As an example, from any given infinite set S, I can generate a set ... For finite sets of n members, their power sets contain 2^n members, and ...
    (sci.math)
  • Re: Orlow cardinality question
    ... Then it is incomplete, which cardinality is not. ... > the infinite set of natural numbers and the sets they each define. ... bijected with the naturals. ... So the allegedly "impossible" bijection obviously exists. ...
    (sci.math)
  • Re: Distinct linear orderings on Z
    ... a bijection between the evens and the naturals. ... bijection that exists between the naturals and the rationals. ... > can draw a bijection between each of these infinite groups and the ...
    (sci.math)