infinity ...
in [Math]
|
Prev: math
Next: The proof of mass vector.
From: Tony Orlow on 18 Oct 2005 17:06 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. > > 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. > > 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? 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? What do you want me to try, anyway, and infinite mapping, element-by-element? A bijection's a bijection, right? These sets are obviously of the same cardinality, since I have a bijection which carries to infinity, right? 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. 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? -- Smiles, Tony
From: Tony Orlow on 18 Oct 2005 17:12 David R Tribble said: > 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). The only reason you cannot show a bijection between those two is that you claim to have an infinite number of finite naturals, so you would have infinite bit strings in P(N) and only finite bit strings in N. But, of course, this is an artificial and incorrect interpretation of the situation, as I have repeatedly tried to convey. > > > 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? Is that supposed to make me happy? The set of binary strings is not well ordered? Doesn't it have a first element, which is all 0's, and a successor to every string in the set? Hmmm..... What is your point? > > -- Smiles, Tony
From: stephen on 18 Oct 2005 17:13 Tony Orlow <aeo6(a)cornell.edu> wrote: > 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 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). > 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. What is x? If y is a member of w, then y is in f(y), and by the definition of w, w is not a member 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. > 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? The contradiction is that if y is in w, then it is not in w, and if y is not in w, then it is in w. That is a pretty obvious contradiction. You apparently failed to grasp the very important fact that w=f(y). So once again, is y in w? If y is in w, then y is in f(y), because w=f(y). If y is in f(y), then y is not in w, because w is defined as containing the elements x in S such that x is not in f(x). w cannot contain y, because y is in f(y). If y is not in w, then y is not in f(y), because w=f(y). If y is not in f(y), then y is in w, because w is defined as containing the elements x in S such that x is not in f(x). w must contain y, because y is not in f(y). >> >> 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. Yes. The fact that you cannot understand a simple proof does not make the proof invalid. >> >> 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. You apparently misintrepted all of it. Do you understand that we are assuming that w=f(y)? Do you understand that y is in w if and only if y is not in f(y)? Do you understand that y is in w if and only if y is not in w is a contradiction? Stephen
From: David R Tribble on 18 Oct 2005 19:17 David R Tribble said: >> But you have not provided a mapping between any set and its powerset, >> infinite or otherwise. > Tony Orlow wrote: >> Have too. Stephen said: >> No you have not Tony. > Tony Orlow wrote: > Have, too! > Stephen said: >> The proof that there does not exist >> a bijection between a set and its power set is quite short. >> 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. Here's a more visual example of that proof... Let B(n,i) = floor(n/2^i) mod 2, for all n = 0,1,2,3,... So B(n,i) is the i-th binary digit of natural n. Let F(n) = { i where B(n,i+1) > 0 for all i = 0,1,2,3,...} for all n = 0,1,2,3,... So F(n) is the set of all naturals representing non-zero binary digits of natural n. Example: n = 69 n = 1000101 (binary) n = 1x2^0 + 0x2^1 + 1x2^2 + 0x2^3 + 0x2^4 + 0x2^5 + 1x2^6 B(69,0) = 1 B(69,2) = 1 B(69,6) = 1 so F(69) = {0,2,6} Thus we have a mapping function that generates a subset F(n) of N for any natural n in N. Now we list the subsets F(n) for all n: F(0) = {} F(1) = {0} F(2) = {1} F(3) = {0,1} F(4) = {2} F(5) = {0,2} F(6) = {1,2} F(7) = {0,1,2} F(8) = {3} F(9) = {0,3} ... Clearly the F(n) sets are all the finite subsets of N, with each subset corresponding to a unique finite natural n in N (and vice versa). It is also clear that since every F(n) is subset of N, it is also a member of P(N), the powerset of N. Now, applying Stephen's (Cantor's) set W, we let W = { n : n in N and n is not in F(n) } In other words, W is the set of all naturals n in N where n is not itself a member of subset F(n). From the list of F(n)'s above, it is obvious that none of the F(n) subsets contains the n that generated it, i.e., for every given n, F(n) does not contain n. (This is because for any n, the largest member of F(n) is ceil(log2(n)), which is always less than n, so n cannot itself be a member of F(n).) This means that set W is simply N itself, since none of the members in N appear in their corresponding F(n) subset; thus every member n of N is a member of W, so W = N. The final step of the proof is: there does not exist a y in N such that F(y) = W. Assume that y exists and that F(y) = W. Is y in W? If y is a member of W (and N), then y is a member of F(y), because we just assumed that W = F(y). But the definition of W means that y cannot be in F(y). Contradiction. If y is not a member of W (or N), then y is a not a member of F(y) either, because W = F(y). But the definition of W means that since y is not a member of F(y), y must be a member of W. Contradiction. So either way, y cannot both be a member and not be a member of F(y) = W = N. So there does not exist a y in N that maps to N itself. Which means that the P(N), the powerset of N, has members that cannot be mapped by any member of N itself, which means that P(N) has more members than N. (This proof also works for infinite sets with infinite naturals, such as *N and P(*N).) <http://en.wikipedia.org/wiki/Cantor%27s_theorem>
From: David R Tribble on 18 Oct 2005 19:41
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. > 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? > 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. > 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. > 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. 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. > 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? |