From: Tony Orlow on
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
From: William Hughes on

albstorz(a)gmx.de wrote:
> William Hughes wrote:
>
> >
> > > Coincidently natural numbers and cardinalities are undistinguishable in
> > > finity.
> >
> > They are very similar, but they are not quite "undistinguishable".
> > A natural number is a set, a cardinality is an equivalence class.
>
> You make me hopefull. Some experts make "äääh", "hömm" and
> "üüüh" if I said "A natural number is a set." One sees a
> correspondence between natural numbers and von Neumann sets after all.
> You are free to say "A natural number is a set." without "äääh-",
> "hömm-" and "üüüh-" comments. Be lucky. You are right.
> And natural numbers don't behave in any other way than sets. So, if
> there is an infinite set there is an infinite number. If there is no
> infinite number there is no infinite set. And vic versa.



You have made exactly this mistake before. Yes every number
is a set. No, not every set is a number. For example
{peach, apple, plum, fiddle} is a set but not a number.
Just because you have a set does not mean you have a number.
So yes, there is an infinite set. But this does not mean
that this set is a number. Indeed, no infinite set is a number.

- William Hughes


P.S Actually it is not true that natural numbers must be sets, but
they can be. As you insist on using a model in which the natural
numbers are sets, I am playing along to be polite.

From: Randy Poe on

Tony Orlow wrote:
> 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?

What is "the" bijection? The proof that card(S) < card(P(S))
shows that no bijection exists. That proof has been given a
few times in this thread and I see you're trying to get through
it. Whether you believe the proof or not yet, you do realize
that the proposition is "Let f(S) be any mapping from S to
P(S). Then f can't be a bijection." Right?

If the proof is correct (as it is), then ALL bijections break
down. The proof consists of showing that no matter what
mapping you choose, there's an unmapped element of P(S).

> It certainly works for all finite cases, does it not?

Absolutely not. Let S = {1,2,3}.
Then P(S) has 8 elements:
{},
{1}, {2}, {3},
{1,2}, {2,3}, {1,3},
{1,2,3}

There is no bijection between the 3 elements of S and the
8 elements of P(S).

> What makes you think it falls apart at some point?

It falls apart for EVERY set.

> For which element is there not a corresponding subset?

It breaks apart in the other direction: there is (at least
one) subset for which there is no corresponding element.

First you have to define your mapping rule. Given any mapping
rule, a subset can be identified for which there is no
corresponding element.

- Randy

From: imaginatorium on

Tony Orlow wrote:
> stephen(a)nomail.com said:
> > Tony Orlow <aeo6(a)cornell.edu> wrote:
> > > stephen(a)nomail.com said:

<showing that there cannot be a bijection from a set to its power
set...>

> > >> Let f be a function from S to P(S).
> > > Our proposed mapping bijection....
> > >>
> > >> Define the set w as follows:
> > >>
> > >> w= { x : x in S and x is not in f(x) }
> > > So, w is the set of all elements which are not members of the subsets which
> > > they map to through f(x)....
> > >>
> > >> Clearly w is a subset of S, and so w is an element of P(S).
> > > Clearly...but properly?
> >
> > >> We now show that w is not in the image of f. That is,
> > >> there does not exist a y such that f(y)=w.
> > > So, there can be no y such that it maps to the subset of all elements which do
> > > not map to subsets containing themselves? We'll see.....
> > >>
> > >> Suppose such a y exists. If such a y exists, it must
> > >> either be an element of w, or not.
> > > One or the other. I'll accept the excluded middle....
> >
> > >>
> > >> If y is an element of w, then y is in f(y), which means
> > >> it is not an element of w.
> > > If y is in w, this means y is a member of the set of elements which map to
> > > subsets which do not contain themselves. This means that y is in S but not in f
> > > (y). So, indeed, it IS a member of w. There is no reason why both x and y
> > > cannot map to subsets which do not contain themselves.
> >
> > If y is in w, then y is in f(y), because w=f(y). Remember,
> > we are assuming there exists a y such that f(y)=w. However
> > w is defined such that y can only be in w, if y is not in f(y).

> Okay, I hit this one at the end of the day, and got confused halfway through it

Yes, that sounds fairly typical. You are about to show that eleven
million (whatever, I've forgotten the numbers already, and I made them
up anyway) mathematicians have been getting it wrong for 100 years with
an 8-line proof. But you hit it at the end of the day and got confused.

> and forgot that you're assuming y is mapped to w. Sorry about that. It is clear
> that no element in the set maps to a subset that contains itself, as I
> illustrated below. If f(y)=w, then y can't be in w, but then that means y IS in
> f(y), which means it's in w. Got it.
>
> That certainly causes a bit of a contradiction, based on the largest-finite
> kind of argument, since you are noting that whatever subset you choose, it
> never contains the natural that maps to it, and the question remains what
> number maps to the set containing just that natural. You are assuming some
> completed w, where some identifiable y is the number that maps to it. But that
> number has to be larger than any of the elements in w. So, you draw a
> contradiction from the assumption that y is in N and also maps to N. Clearly,
> the power set is LARGER than the set.

Well, that was a jumble, wasn't it? What is a "completed" w? Normal set
theory talks about sets, and a set contains its members. It contains
all of its members, all the time, never contains anything else, never
becomes tired, "unidentifiable", or "tenuous", just sits there
containing all the elements it contains. (Notice that this immediately
means that normal set theory can't accommodate things like sets that
contain different collections of all of something, one of the direct
consequences of the "infinite numbers are just the same as finite
numbers only bigger" crank line.)

Notice also how you are again unable to consider abstract sets, and
keep mumbling about "numbers". Why on earth should the y be "larger"
than any element in w? We've proved that y cannot exist at all, but
there is no a priori reason any notion of "largeness" is involved. If
we were considering the set of all finite simple groups or the set of
all Platonic solids, there would be no "larger", but the proof applies
exactly the same.

> However, given the definition of bijections, it is easy to map any well-ordered
> infinite set to its power set ....

Blah blah blah. This one line after a proof that no such bijection
exists. Well, it's no wonder you can't do mathematics.

Brian Chandler
http://imaginatorium.org

From: Tony Orlow on
William Hughes said:
>
> albstorz(a)gmx.de wrote:
> > David R Tribble wrote:
> > > Albrecht S. Storz wrote:
> > > >> Cantor proofs his wrong conclusion with the same mix of potential
> > > >> infinity and actual infinity. But there is no bijection between this
> > > >> two concepts. The antidiagonal is an unicorn.
> > > >> There is no stringend concept about infinity. And there is no aleph_1,
> > > >> aleph_2, ... or any other infinity.
> > > >
> > >
> > > David R Tribble wrote:
> > > >> For that to be true, there must be a bijection between an infinite
> > > >> set (any infinite set) and its powerset. Bitte, show us a bijection
> > > >> between N and P(N).
> > > >
> > >
> > > Albrecht S. Storz wrote:
> > > > At first, you should show, that bijection means something to
> > > > notwellordered infinite sets.
> > > >
> > > > Bijection is a clear concept on finite sets, it also works on
> > > > wellordered infinite sets of the same infinite concept.
> > > > Aber: Show me a bijection between two infinite sets with the same
> > > > cardinality, where one of the sets is still not wellorderable.
> > > > Than I will show you a bijection between N and P(N) or N and R or P(N)
> > > > and P(P(N)) or what you want.
> > >
> > > I see. I'm supposed to show you a proof before you can show me your
> > > proof. Okay, I give up, you win, so your proof must be correct.
> > >
> > > Come on, now. It's up to you to prove your own claim, especially
> > > when it contradicts established mathematics. I know you cannot show
> > > a bijection between N and P(N).
> > >
> > >
> > > P.S.
> > >
> > > Let
> > > D(n,i) = floor(n/2^i) mod 2, for all i=0,1,2,3,...
> > > This is the i-th binary digit of natural n
> > > L(n) = i where D(n,i) = 1 and D(n,j) = 0 for all j > i
> > > This is the number of binary digits of natural n, or ceil(log2(n))
> > > Let
> > > M(n) = sum{i=0 to L(n)} 1/2^(i+1) where D(n,i) = 1
> > > This reverses the binary digits of n.
> > >
> > > Then M(n) is a mapping N -> N, from all n in N to M(n) in N,
> > > but the set of all M(n) is not a well-ordered set.
> > > Happy?
> >
> >
> > Sad!
> > First of all you don't argue on my claim of the thread.
> > Second, your above argueing is not clear to me, since both sets are
> > well-ordered. But it's nice, so I give this:
> >
> > N
> > {1},{2},{3}, ...
> > N/{1},N/{2},N/{3}, ...
> > {1,2},{1,3},{2,3},{1,4},...
> > N/{1,2}, ...
> > ...
> >
> > Now count in diagonal sequence. You may think of Cantor's first
> > diagonal proof.
> >
> > Which subset of N is not included?
>
> Sigh. Try {2,4,6,8,...} Or any other infinite subset
> that is not the complement of a finite set.
>
> It is common for people to note that the finite subsets of N
> are countable and incorrectly claim that the subsets of N are
> countable. Adding in the complements of the finite subsets
> does not change things very much.
>
> Those who do not study anti-cantor cranks are doomed to
> repeat their idiocies.
>
> - William Hughes
>
> P.S. No TO, going to TO-infinite rows is not going to help us.
> The problem is that for any TO-finite row, the subsets
> listed will have an bounded finite number of elements, or be
> the complement of a subset with a finite number of elements.
> Yes, you can claim (without a shred of motivation) that
> when you get to TO-infinite rows the subsets will suddenly
> have an unbounded number of elements, but all this tells us
> is that a bijection from the TO-naturals to P(N) exists.
> What we need is a bijection from the finite TO-naturals
> to P(N).
>
>
Look, it's certainly not my position that the pwoer set is the same sie as the
set. It's clearly not. I just see a bijection between them, which only bolsters
my argument that bijection alone is not sufficient to equate the sizes of two
sets.

When it comes to the evens (let's start with 0), the value 0:010.......1010101
represents such a subset, and is essentially binary N/3.
--
Smiles,

Tony
First  |  Prev  |  Next  |  Last
Pages: 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Prev: math
Next: The proof of mass vector.