infinity ...
in [Math]
|
Prev: math
Next: The proof of mass vector.
From: stephen on 19 Oct 2005 16:57 Tony Orlow <aeo6(a)cornell.edu> wrote: > stevendaryl3016(a)yahoo.com said: >> albstorz(a)gmx.de says... >> >> >I don't know what you are talking about. The proof for finite sets >> >needs just a complete induction. This will not hold for infinity I >> >think. >> >> There is no induction involved in the finite case, and the >> infinite case is *exactly* the same proof as the finite case. >> >> Here it is once again: >> >> Let A be any set whatsoever, finite or infinite, it doesn't matter. >> Let f be any function from A to P(A). >> Let w = { x in A | x is not an element of f(x) }. >> Let x = any set in A. >> Let u = f(x). We prove that u is not equal to w. >> >> By definition of w, we have x in w <-> x is not an element of f(x). >> So x in w <-> x is not an element of u. That means that there are >> two cases: Case 1: x in w, and x is not in u. In that case, u cannot >> equal w. Case 2: x is not in w, and x is in u. In that case, u cannot >> equal w. >> >> So what we have proved is that forall x, w is not equal to f(x). So >> w is not in the image of f. So f is not a bijection between A and P(A). >> >> There's no induction. There's no assumption that A is finite. > But there is an assumption that y is in S. Of course there is an assumption that y is in S. The goal is to find a bijection f from S to P(S). That means that for every element x in P(S), there must be an element y in S such that f(y)=x. w is an element of P(S). In order for f to be a bijection, there must exist an element y in S such that f(y)=w. If y is not in S, then it is irrelevant to the question of whether or not f is a bijection from S to P(S). Do you consider the following a bijection from S={a,b,c} to its power set? f(a) = {} f(b) = {a} f(c) = {b} f(d) = {c} f(e) = {a,b} f(g) = {a,c} f(h) = {b,c} f(i) = {a,b,c} If w= { x : x in S and x not in f(x) } then w= {a,b,c}. Is there a y in S such that f(y) = {a,b,c}? No. Is there a y such that f(y) = {a,b,c}? Yes, f(i)={a,b,c}, but i is not in S, and is not part of a bijection from S to P(S). The above function is a bijection from {a,b,c,d,e,g,h,i} to P({a,b,c}). It is not a bijection from {a,b,c} to P({a,b,c}). Stephen
From: Tony Orlow on 19 Oct 2005 17:05 stephen(a)nomail.com said: > Tony Orlow <aeo6(a)cornell.edu> wrote: > > stephen(a)nomail.com said: > >> 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). > > Okay, I hit this one at the end of the day, and got confused halfway through it > > 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. > > No, that is not clear at all. It is entirely possible that an > element maps to a set that contains itself. However no element > maps to w. You still do not get it. Well, it's really not possible, given the general bijection I have offered between an infinite ordered set and its power set. No natural is a member of the subset of naturals which it denotes, as I demonstrated. > > Here is a simple mapping from N to P(N). > > 1 -> {1} > 2 -> {1,2} > 3 -> {1,2,3} > 4 -> {1,2,3,4} > ... > > Every element is contained in the subset that it is mapped > to. For this mapping, w={}, and no element is mapped to {}. And not every subset is included, so this is not a bijection. > > > > 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, > > No. Try again. No need. I gave my general bijection, and this fact is true for it. I see no other bijection between a set and its power set, but this one holds, and that fact si true. No natural maps to a set which contains it. Any set mapped by a natural n has a maximal element no larger than log2(n). > > >> > 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. > > Yes, there is no element y in any given set S which maps to S. That element > > would be element 2^|S|-1, outside the scope of S. > >> > >> >> > >> >> 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. > > Well, y is in w, as are all the elements. y does not map to w. For any given > > set, there is no element in the set which maps this way to the set itself. And > > yet, when you have infinite sets such as this, can't I just map element 2^S-1 > > to subset S? > > What is element "2^S-1"? S is a set. Element "2^S-1" means > nothing to me. If set S has S elements, from number 0 through S-1, then the element which maps to the entire set is a string of 1's which is S long, which corresponds to a value of 2^S-1, which would be element number 2^S (not 2^S-1, sorry - damned error of 1!). > > >> > >> You apparently failed to grasp the very important fact that w=f(y). > >> So once again, is y in w? > > Not if w=f(y). If w=f(y), then y is not in S, and therefore not in w. > > If y is not in S, then it is not part of the bijection. > f is function from S to P(S). It makes no sense to plug > in a value that is not in S into f. That all depends. If you place a value range on the set, which is essentially what you're doing when you ask what element maps to the set as a whole, then you have elements in the power set of S which map to elements outside the range of S. You derive your contradiction by assuming this upper bound, which is not a mistake. The result of this proof is that the power set is a larger set, even for the infinite case, and is correct. There is nothing in this proof that makes a bijection impossible. > > >> > >> 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). > > Got it. y is not in S, and therefore not in w. > > No. You still do not get it. Y is beyond the range of the completed S. Sure, for any n elements in S there are 2^n elements in P(S). You cannot draw a bijection between any finite S and its power set, for sure. You also cannot draw any bijection between the naturals and the odds within any given value range; there will be twice as many naturals. In the infinite case, you can draw bijections for both. Do bijections imply equality of set size? No, not necessarily. > >> > >> >> > >> >> 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. > > I got a little confused, but you still haven't proven anything like the > > impossibility of a bijection with the power set. In other cases bijections are > > performed without regard to such discrepancies. > > There is no bijection between a set and its powerset. > It does not matter what the set is, it does not matter > if it is finite, or infinite. Then can you explain how the bijection between *N and P(*N) violates rules for bijections? > >> > >> >> > >> >> 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. > > not entirely. > >> > >> Do you understand that we are assuming that w=f(y)? > > No, I forgot that in figuring out what we were talking about specifically. I > > don;t see anything in it proving bijection impossible. If w=f(y) then y is not > > in S, assuming some limit to S. But, S goes on forever and ever, and we can > > always borrow for our bijection, having sets containing elements with at most > > the log2 of the value of the element that maps to it. As long as there's a 1-1 > > correspondence, what's the problem? > > If nothing in S maps to w, and w is in P(S), then f is not a bijection. But S is infinite. For any element of P(*N) you name, I can name an element in *N that corresponds to it. Try me. > It is that simple. Nothing in S maps to w. If you think otherwise, > tell us what element of S is mapped to w. Element 2^S maps to the entire set from 0 through S-1, all S elements. > > You still do not understand the proof at all. It is a relatively > simple proof. I understand it. You do not understand my response to it. It was offered as a proof that a bijection is impossible, but I see no mention of bijections in the proof. Explain this. > > Here are some examples that might help you out. Although > you will likely snip them as "tedious nonsense." Not unless they are. > > First, look at the finite case. Let S={a,b,c}. Okay, that's tedious. I agree there is no bijection between a finite set and its power set or any other set of a different size. That is only possible for infinite sets. > > Lets look at > f(a) = { a } > f(b) = { a, c } > f(c) = { a, b, c } > > w = { x : x not in f(x)}, so w={b}. {b} is not in the image of f. > We can try again. > f(a) = { a } > f(b) = { b } > f(c) = { a, b, c } > Now w={}, which is not in the range of f. > How about > f(a) = { } > f(b) = { a } > f(c) = { a, b } > Now w={a,b,c}. We can keep playing this game, but w will > never be in the image of f. Yes, well, besides, those are relatively random mappings, anyway. Let's move on to the infinite case. > > Of course in the finite case it is obvious that there > cannot be a bijection from S to P(S) because P(S) has > 2^|S| elements, and when |S| is finite it is obvious that > 2^|S| > |S|. Yup. Agreed. > > However the above proof makes no mention or use > of the set being finite, and it applies equally well > to finite and infinite sets. It demonstrates that the power set is larger, but what does it say about bijections? > > Lets look at the natural numbers and the "bijection" > albstorz proposed: > > 1 -> N > 2 -> {} > 3 -> {1} > 4 -> N\{1} > 5 -> {2} > 6 -> N\{2} > 7 -> {1,2} > 8 -> N\{1,2} > 9 -> {3} > 10 -> N\{3} > 11 -> {1,3} > 12 -> N\{1,3} > 13 -> {4} > 14 -> N\{4} > 15 -> {1,4} > 16 -> N\{1,4} > 17 -> {2,3} > 18 -> N\{2,3} > 19 -> {5} > 20 -> N\{5} > ... > > In this case > w={ 2,3,5,7,9,11,13,15,17,19 .... } > > Where does this show up in teh above list? If you > claim it shows up in position y, then is y in w or not? Yes, well, in this case you have some elements that map to subsets which contain them, since Albrecht decided to entertain both ends of the set at once, so as to avoid the Twilight Zone. Now, you are asking where 1010.....0101010110 exists? Somewhere beyond N. It's essentially (2^(N+1)/3)+1. In Albrecht's notation, it's N\{1,4,6,8,10,.....} over a range of 2^N. > > Stephen > > -- Smiles, Tony
From: Randy Poe on 19 Oct 2005 17:43 Tony Orlow wrote: > stephen(a)nomail.com said: > > What is element "2^S-1"? S is a set. Element "2^S-1" means > > nothing to me. > If set S has S elements, from number 0 through S-1, then the element which maps > to the entire set is a string of 1's which is S long, which corresponds to a > value of 2^S-1, which would be element number 2^S (not 2^S-1, sorry - damned > error of 1!). So you would say that no element x is in f(x), correct? Therefore for this mapping, the set w = {x in S: x not in f(x)} contains every element of S, right? That is, w = S. Now let's consider every element y of S. Obviously y is in w, since w = S. But then y is not in f(y), since that's what it means for y to be in w. Then f(y) can't be S. So this means that no matter what y you pick, f(y) can't be S. So S is not mapped by your "bijection". What's wrong with your "proof"? Simple. You have f(z) = S, where z is NOT a member of your original set S. You don't have f(y) = S for any y IN your set S. - Randy
From: stephen on 19 Oct 2005 18:19 Tony Orlow <aeo6(a)cornell.edu> wrote: > stephen(a)nomail.com said: >> Tony Orlow <aeo6(a)cornell.edu> wrote: >> > stephen(a)nomail.com said: >> >> 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). >> > Okay, I hit this one at the end of the day, and got confused halfway through it >> > 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. >> >> No, that is not clear at all. It is entirely possible that an >> element maps to a set that contains itself. However no element >> maps to w. You still do not get it. > Well, it's really not possible, given the general bijection I have offered > between an infinite ordered set and its power set. No natural is a member of > the subset of naturals which it denotes, as I demonstrated. What is really not possible? It really is possible for y to be a member of f(y). What is really not possible is that f is a bijection from S to P(S). >> >> Here is a simple mapping from N to P(N). >> >> 1 -> {1} >> 2 -> {1,2} >> 3 -> {1,2,3} >> 4 -> {1,2,3,4} >> ... >> >> Every element is contained in the subset that it is mapped >> to. For this mapping, w={}, and no element is mapped to {}. > And not every subset is included, so this is not a bijection. Of course. There is no bijection from S to P(S). >> >> >> > 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, >> >> No. Try again. > No need. I gave my general bijection, and this fact is true for it. I see no > other bijection between a set and its power set, but this one holds, and that > fact si true. No natural maps to a set which contains it. Any set mapped by a > natural n has a maximal element no larger than log2(n). Your bijection is not a bijection. Sorry. <snip> >> >> > 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. >> > Well, y is in w, as are all the elements. y does not map to w. For any given >> > set, there is no element in the set which maps this way to the set itself. And >> > yet, when you have infinite sets such as this, can't I just map element 2^S-1 >> > to subset S? >> >> What is element "2^S-1"? S is a set. Element "2^S-1" means >> nothing to me. > If set S has S elements, from number 0 through S-1, then the element which maps > to the entire set is a string of 1's which is S long, which corresponds to a > value of 2^S-1, which would be element number 2^S (not 2^S-1, sorry - damned > error of 1!). So what is element 2^S-1? If there are only |S| elements in S, then there is no element 2^S-1. Remember, you are mapping elements of S to subsets of S. There is no element 2^S-1 to be mapped to S. So what you are saying makes no sense. <snip> >> We can try again. >> f(a) = { a } >> f(b) = { b } >> f(c) = { a, b, c } >> Now w={}, which is not in the range of f. >> How about >> f(a) = { } >> f(b) = { a } >> f(c) = { a, b } >> Now w={a,b,c}. We can keep playing this game, but w will >> never be in the image of f. > Yes, well, besides, those are relatively random mappings, anyway. Yes, they are random. That is the point. No matter what you pick for f, it is not a bijection. > Let's move on > to the infinite case. >> >> Of course in the finite case it is obvious that there >> cannot be a bijection from S to P(S) because P(S) has >> 2^|S| elements, and when |S| is finite it is obvious that >> 2^|S| > |S|. > Yup. Agreed. >> >> However the above proof makes no mention or use >> of the set being finite, and it applies equally well >> to finite and infinite sets. > It demonstrates that the power set is larger, but what does it say about > bijections? It says that a bijection does not exist. Are you really incapable of understanding that? >> >> Lets look at the natural numbers and the "bijection" >> albstorz proposed: >> >> 1 -> N >> 2 -> {} >> 3 -> {1} >> 4 -> N\{1} >> 5 -> {2} >> 6 -> N\{2} >> 7 -> {1,2} >> 8 -> N\{1,2} >> 9 -> {3} >> 10 -> N\{3} >> 11 -> {1,3} >> 12 -> N\{1,3} >> 13 -> {4} >> 14 -> N\{4} >> 15 -> {1,4} >> 16 -> N\{1,4} >> 17 -> {2,3} >> 18 -> N\{2,3} >> 19 -> {5} >> 20 -> N\{5} >> ... >> >> In this case >> w={ 2,3,5,7,9,11,13,15,17,19 .... } >> >> Where does this show up in teh above list? If you >> claim it shows up in position y, then is y in w or not? > Yes, well, in this case you have some elements that map to subsets which > contain them, since Albrecht decided to entertain both ends of the set at once, > so as to avoid the Twilight Zone. Now, you are asking where 1010.....0101010110 > exists? Somewhere beyond N. It's essentially (2^(N+1)/3)+1. In Albrecht's > notation, it's N\{1,4,6,8,10,.....} over a range of 2^N. Somewhere beyond N? What does that mean. Is "Somewhere beyond N" in w or not? Stephen
From: Virgil on 19 Oct 2005 18:44
In article <MPG.1dc0779a8507946398a4f5(a)newsstand.cit.cornell.edu>, Tony Orlow <aeo6(a)cornell.edu> wrote: > stevendaryl3016(a)yahoo.com said: > > albstorz(a)gmx.de says... > > > > >I don't know what you are talking about. The proof for finite sets > > >needs just a complete induction. This will not hold for infinity I > > >think. > > > > There is no induction involved in the finite case, and the > > infinite case is *exactly* the same proof as the finite case. > > > > Here it is once again: > > > > Let A be any set whatsoever, finite or infinite, it doesn't matter. > > Let f be any function from A to P(A). > > Let w = { x in A | x is not an element of f(x) }. > > Let x = any set in A. > > Let u = f(x). We prove that u is not equal to w. > > > > By definition of w, we have x in w <-> x is not an element of f(x). > > So x in w <-> x is not an element of u. That means that there are > > two cases: Case 1: x in w, and x is not in u. In that case, u cannot > > equal w. Case 2: x is not in w, and x is in u. In that case, u cannot > > equal w. > > > > So what we have proved is that forall x, w is not equal to f(x). So > > w is not in the image of f. So f is not a bijection between A and P(A). > > > > There's no induction. There's no assumption that A is finite. > But there is an assumption that y is in S. NO! There is a consideration of what must happen if y is in S, which is quite different from assuming that S is non-empty. > If you are assuming you have the > complete set of naturals, This is quite independent of the nature of the sets involved, and they need not be sets of naturals. > that you have identified the last The what? There is TO going on about finding an end to the endless again. Only in TOmatics do things which have no end have an end. |