infinity ...
in [Math]
|
Prev: math
Next: The proof of mass vector.
From: Daryl McCullough on 21 Oct 2005 09:06 albstorz(a)gmx.de says... >You can biject all constructable subsets of P(N) to N, but not the >unconstructable. By "constructable" do you mean "definable"? Or do you mean "computable"? Or do you mean "finite", or what? Let me list the combinations here: 1. There is no bijection between N and the set of all subsets of N. 2. There is no computable bijection between N and the set of all computable subsets of N. 3. There is no definable bijection between N and the set of all definable subsets of N. Whatever notion of function we want, it is true that there is no function mapping N to the set of all functions from N into {0,1}. However, if you mix your notions of functions, you can get mixed results: 2'. There *is* a definable bijection between N and the set of all computable subsets of N, but that bijection is not computable. 3'. There *is* a bijection between N and the set of all definable (in the language of arithmetic) subsets of N, but that bijection is not definable in the language of arithmetic. 3' can be extended further: 3''. There *is* a bijection between N and the set of all definable (in the language of ZFC) subsets of N, but that bijection is not definable in the language of ZFC. If you stick to any one consistent notion of "function" and "subset", then Cantor's theorem tells you that there is no bijection (according to that notion) between N and the set of subsets (according to that notion) of N. -- Daryl McCullough Ithaca, NY
From: Tony Orlow on 21 Oct 2005 10:27 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: > >> >> > 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). Not in the bijection I offered. y is never in f(y). > > >> > >> 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). Yes, there is. I gave you one. You have yet to point out anything wrong with it, except to say it's impossible so it doesn't exist. One solid counterexample is all that is required to refute a proof of impossibility. > > >> > >> > >> > 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. Why, exactly? Hand waving and denial are not valid logical arguments. What rule of bijection have I violated, specifically? > > <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. It makes total sense, and it is consistent with what I have been trying to teach you for months. There is no exact number you can pin on these infinite sets. Assumption of any such largest element leads to a contradiction. This is all you have done with this proof. The fact remains that for any n in N, there is a corresponding subset denoted by that bitstring, and for any subset of N, there is a natural in N whose bitstring denotes that subset. If you claim this is not so, then please show me a natural or a subset which has no corresponding element. You have two infinite sets that go on forever. When does the correspondence end? > > <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. Except the bijection I offered, which works without flaw, despite your denials. In absence of any valid objection to the construction, my bijection stands. What is your specific objection? > > > 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? I am quite capable of seeing that it is yet another of your proofs by contradiction that derives from the assumption of a largest element and conflates the result to claim that something unrelated is impossible or doesn't exist. While it is true that within any GIVEN range of S there is no element within S that maps to S, it is NOT true that over the entire unending range there is any point where any element does not have a unique corresponding element in the other set. It is impossible to form a bijection between any finite set and its power set, but as you do with all sorts of unequally infinite sets, it is quite simple, as shown, to form a bijection between any infinite ordered set and its power set. Show me where my bijection fails, specifically. Denials don't cut the mustard. > > >> > >> 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? Not if you assign a specific range N to w. As soon as you limit the set by declaring some actual size N, then it is essentially finitized, and the bijection fails, because we note that the element mapping to it is at 2^N, and outside the stated range. Without this value range, the bijection continues forever and is a valid bijection. It doesn't prove the set is the same size as the power set. It proves bijections alone don't mean equality of set size for infinite sets. > > Stephen > -- Smiles, Tony
From: Tony Orlow on 21 Oct 2005 10:36 Virgil said: > In article <MPG.1dc078e83d0081bc98a4f6(a)newsstand.cit.cornell.edu>, > Tony Orlow <aeo6(a)cornell.edu> wrote: > > > I don't understand why an inductive proof of an equality relationship > > does not extend to infinite numbers. > > Informally, the Peano axioms may be stated as follows: > 1 There is a natural number 0. > 1 Every natural number a has a successor, denoted by S(a). > 3 There is no natural number whose successor is 0. > 4 Distinct natural numbers have distinct successors: > if not(a = b), then not(S(a) <> S(b)). > 5 If a property is possessed by 0 and also by the successor of > every natural number which possesses it, then it is possessed > by all natural numbers. (This axiom ensures that the proof > technique of mathematical induction is valid.) Says nothing about finiteness there...... > > More formally, we define a Dedekind-Peano structure to be an ordered > triple (X, x, f), satisfying the following properties: > 1 X is a set, x is an element of X, and f is a map from X to itself. > 2 x is not in the range of f. > 3 f is injective. > 4 If A is a subset of X satisfying: > 5 If [x is in A, and > (If a is in A, then f(a) is in A)] > then A = X. Nope, still no finiteness...... > > A member of the set of such objects so defined is defined as finite if > the set of such objects of which it is ultimately a successor is a > finite set by the Dedekind definition of finite sets. So, all finite numbers are successors to finite sets. Then, which finite is a successor to any infinite portion of the infinite set of finite naturals? None? Hmmmm..... That doesn't seem to work very well. > > With that definition of finiteness of such objects, all such objects are > provably finite. Only the ones that are successors to a finite set. The ones that are successors to infinite-size sets are infinite in value. So, you assume there are only finite naturals, and this is your reasoning for why induction doesn't work in the infinite case? You aren't actually capable of thinking about what your axioms mean, are you? You have given no reason why induction only works in the finite case. > -- Smiles, Tony
From: Randy Poe on 21 Oct 2005 10:44 Tony Orlow wrote: > Randy Poe said: > > > > 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? > Not given any particular x, no. Uhoh, we're hinting at "specifiable" again. Every element of S is a particular x. There are no "unparticular" elements of S. > > 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. > Yes. Good. > > 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. > That's true, and this is an interesting argument. I'm just repeating the Cantor argument for your particular mapping. I don't think it's easy to get an intuitive grasp for that argument without seeing how it works for a couple of examples. You have provided one example, but the proof is general. > You certainly cannot identify > any natural which maps to the entire set of naturals. Forget "identify". What you just agreed to is that there does not EXIST a natural y such that f(y) = S. > That would require > identifying some last element No it wouldn't. Where did "last element" come into it? All that came into it was agreeing that w = S, whether S has a last element or not. y is in w whether S has a last element or not. Therefore y is not in f(y), whether S has a last element or not. Therefore f(y) can not be S, whether S has a last element or not. > What rule am I breaking with this bijection? We just agreed that it is impossible under this "bijection" for S to appear on the right hand side. Therefore there is at least one subset of S (S itself) which does not appear on the right hand side. Therefore your bijection breaks the property of mapping to every subset of P(S). > Where does the correspondence break down? At element N+1? I don't know what other elements are not mapped. This is your obsession with finding the "end" again. We don't need to find the end. We just considered EVERY SINGLE ELEMENT and proved that f(y) can't be S FOR ANY ELEMENT y OF S. That rules out everything except y's which are not elements of S. But "bijection" S -> P(S) means that for every element s of P(S), there is y which IS AN ELEMENT OF S such that f(y) = s. S is an element of P(S). f(y) does not equal S for any y in S. So it's not a bijection. - Randy
From: Daryl McCullough on 21 Oct 2005 10:25
Tony Orlow says... >> 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. >Yes. >> >> 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. >That's true, and this is an interesting argument. You certainly >cannot identify any natural which maps to the entire set of naturals. That's why people say "There is no bijection between S and the the power set of S". They mean that for all maps f from S to P(S), there is a corresponding w in P(S) such that nothing gets mapped to w. (You would say "nothing identifiable gets mapped to w"). >What rule am I breaking with this bijection? It's not a bijection. >> So this means that no matter what y you pick, f(y) can't >> be S. So S is not mapped by your "bijection". > >Not within the range of S, no, Then you don't have a bijection. By definition, f is a bijection only if there is some y in S that maps to w. >> 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. >That is true. That means that f is not a bijection. -- Daryl McCullough Ithaca, NY |