Prev: math
Next: The proof of mass vector.
From: stephen on 18 Oct 2005 14:33 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 18 Oct 2005 14:36 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 18 Oct 2005 16:02 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 18 Oct 2005 16:21 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 18 Oct 2005 16:59
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 |