From: stephen on
Tony Orlow <aeo6(a)cornell.edu> wrote:
> David R Tribble said:
>>
>> But you have not provided a mapping between any set and its powerset,
>> infinite or otherwise.
> Have too.

No you have not Tony. The proof that there does not exist
a bijection between a set and its power set is quite short.

Let f be a function from S to P(S).

Define the set w as follows:

w= { x : x in S and x is not in f(x) }

Clearly w is a subset of S, and so w is an element of P(S).

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.

Suppose such a y exists. If such a y exists, it must
either be an element of w, or not.

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 not an element of w, then y is not in f(y), which
means it is an element of w.

These are both contradictions. So y cannot be an element
of w, and it cannot not be an element of w. So y
cannot exist.

So there is at least one element in P(S) which is
not in the image of f, so f is not an onto function,
and it is not a bijection.

What is wrong with this proof in your opinion?

Stephen
From: Virgil on
In article <1129622094.019699.233300(a)g44g2000cwa.googlegroups.com>,
albstorz(a)gmx.de wrote:

> David R Tribble 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.

If either of two sets is well-orderable and there is a bijection between
the sets, then that bijection induces well-order-ability on the other.

So that you cannot have a bijection between two sets when one is
well-orderable and the other is not.
From: David R Tribble on
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.

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.

From: David R Tribble on
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?

From: Tony Orlow on
stephen(a)nomail.com said:
> Tony Orlow <aeo6(a)cornell.edu> wrote:
> > David R Tribble said:
> >>
> >> But you have not provided a mapping between any set and its powerset,
> >> infinite or otherwise.
> > Have too.
>
> No you have not Tony.

Have, too!

> The proof that there does not exist
> a bijection between a set and its power set is quite short.
Then it shouldn't take too much looking to see where it goes wrong....
>
> 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 a member of w, then all you can say is that y does not map to any
subset which contains itself. Y does not map to w. Neither does x.
>
> If y is not an element of w, then y is not in f(y), which
> means it is an element of w.
If y is not a member of w, then y maps to a subset which contains y as a
member, and y IS in f(y). Is this possible? We'll see what you think.....

>
> These are both contradictions. So y cannot be an element
> of w, and it cannot not be an element of w. So y
> cannot exist.
Neither of those possibilities causes a contradiction. You are getting confused
with your double negatives. If w is the set of all elements which do not map to
subsets containing themselves, then being a member of w means simply that y
does not map to a subset containing y, which is perfectly possible. Not being a
member of w means that an element maps to a subset which DOES contain itself.
Where is the contradiction?
>
> So there is at least one element in P(S) which is
> not in the image of f, so f is not an onto function,
> and it is not a bijection.
Sorry, not so.
>
> What is wrong with this proof in your opinion?
You confused yourself with double negatives. If I misinterpreted any of what
you said, please clarify. On the face of it, you ain't got no proof.

Let's put this in terms of the bijection between *N and P(*N). Given the common
binary string representation of the binary naturals and the subset
specifications, and starting from 0, let's see what's in w. 0 maps to a string
of all 0's, representing the null set. 1 maps to the set containing only zero.
2 maps to the set containing only 1. 3 maps to the subset containing 0 and 1. 4
maps to the subset containign only 2. f(5)={0,2}, f(6)={1,2}, f(7)={0,1,2}, f
(8)={3}. Do you see a pattern here? Do you see ANY elements of *N which map to
subsets of *N which contain themselves? There aren't any. Your proof doesn't
apply. there is no contradiction in it. *N bijects with P(*N) through the set
of infinite binary strings.

Now, w seems to be the entire set S, since there is no element which is a
member of the subset it denotes as a binary string. So what element maps to w?
It would appear to be an infinite string of 1's, one for every element. You
might also think this infinite string of 1's represents the largest element of
*N, in which case you might think that this is the one number that is not in w.
But, be careful! If you have a string of N 1's for the N elements of S, then in
binary this string of N digits equals 2^N-1, and you have 2^N subsets, from 0
through this number. So, despite the fact that you can create the bijection,
the two sets are clearly different sizes, and bijection is shown NOT to
indicate equivalence between sets.

Give me a Q! Q!!! Give me an E! E!!! Give me a D! D!!! Whaddya got? QED!!!!!
>
> Stephen
>

--
Smiles,

Tony
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Prev: math
Next: The proof of mass vector.