Prev: math
Next: The proof of mass vector.
From: Tony Orlow on 20 Oct 2005 16:11 Virgil said: > In article <MPG.1dc044c61d46b15798a4e8(a)newsstand.cit.cornell.edu>, > Tony Orlow <aeo6(a)cornell.edu> wrote: > > > albstorz(a)gmx.de said: > > > > > > > You must proof it independently for finite and for infinite sets. In > > > this sense the argument is stupid. > > > > > > > > > Regards > > > AS > > > > > > > > Albrecht, do you accept the axiom of induction? If so, it is easily provable > > inductively that the power set of a set of size n has size 2^n, and since > > this > > is an equality property, it holds for the infinite case. The power set of an > > infinite set is infinite, but a larger infinity than the set. > > That is only true if 'size' means cardinality, since it is based > entirely on injection/surjection/bijection arguments. No, cardinality only comes to this conclusion through the clumsiest of methods, like a bear that scratches his back by getting himself run over by a truck. > > And TO correcting albstorz is a perfect illustration of the blind > leading the blind. Yes, that's how it looks, to the blind. > -- Smiles, Tony
From: Tony Orlow on 20 Oct 2005 16:26 William Hughes said: > > Tony Orlow wrote: > > William Hughes said: > > > > > > albstorz(a)gmx.de wrote: > > > > David Kastrup wrote: > > > > > albstorz(a)gmx.de writes: > > > > > > > > > > > Virgil wrote: > > > > > >> In article <1129684276.251366.121150(a)g47g2000cwa.googlegroups.com>, > > > > > >> albstorz(a)gmx.de wrote: > > > > > >> > > > > > >> > David R Tribble wrote: > > > > > >> > > > > > > >> > > > > > > > >> > > 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? > > > > > >> > > > > > > >> > This argument is stupid. Is there any magic in the powerfunction? > > > > > >> > > > > > >> "Proofs" are not stupid until they can be refuted. The proof that for an > > > > > >> arbitrary set S, Card(S) < Card(P(S)) has not been refuted by anyone. > > > > > > > > > > > > > > > > > > Even if you think that the powersets of finite and infinite sets > > > > > > have both a greater cardinality than their starting sets, you would > > > > > > not really think it depends on the same cause in both cases. > > > > > > > > > > > > You must proof it independently for finite and for infinite sets. In > > > > > > this sense the argument is stupid. > > > > > > > > > > Uh, no. The proof depends merely on the fact that some value has to > > > > > be either a member of a set, or not. And if some value is in one set, > > > > > bur not another, then those two sets are different. > > > > > > > > > > That's all. Finiteness or infiniteness does not even play into it. > > > > > The proof just constructs a set which differs by the membership of at > > > > > least one particular value with every target set in the assumedly > > > > > complete mapping of set to powerset. > > > > > > > > > > -- > > > > > David Kastrup, Kriemhildstr. 15, 44793 Bochum > > > > > > > > > > > > > > > > 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. > > > > > > Perhaps you are thinking about proving that n<2^n for all natural > > > numbers n? This can be done by induction, and indeed this proof > > > doen not extend to infinite numbers. However, this is not the > > > proof usually used to show that there is no bijection between a > > > set and its powerset. The standard proof does not use induction, > > > nor does it require finiteness. > > I don't understand why an inductive proof of an equality relationship does not > > extend to infinite numbers. > > Because we are discussing standard mathematics here and there > are no infinite natural numbers (only infinite ordinals and cardinals > which are not the same thing). Yes it is true that the semi-mythical > TO naturals have infinite members and that induction sometimes > holds, but that is irrelevent here. No it's not at all. The bijection I offered is between *N, which has infinite values as members, and its power set. Besides, your claim that induction only holds for finite n is based on your belief that there ARE no infinite n, which is false. This is why the inductive proof that all naturals are finite is entirely circular. Without the assumption of the conclusion, the conclusion isn't there. If you allow for infinite n, then you need to make sure your inductive proof doesn't depend on a difference with a limit of zero at oo. That's the only reason to limit induction to the finite case, but it's not generally necessary. > > >Only relationships which disappear at n=oo are > > limited to the finite case, as far as I can see. I think your statement is the > > result of the definition based on natural numbers, and the belief that all > > naturals are finite, but I just don't see why induction in general should be > > limited to finite iterations. It seems to me that the inductive proof of that > > equality works without flaw. > > Well, as you have not even defined 2^N for infinite TO naturals, you > have > some work to do. Defined 2^N? It's 2 to the Nth power. What do you need to know? In binary, it's a 1 followed by N 0's. Please state your complaint in the form of a question. > > - William Hughes > > -- Smiles, Tony
From: Tony Orlow on 20 Oct 2005 16:44 stephen(a)nomail.com said: > 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 > But, if this set went on forever, then i WOULD be in the set, and for any subset, you could identify an x such that it mapped to that set. It is true that no bijection is possible in the finite case. In the proof, a last element of the set is assumed when we assume there is some string representing the entire set. However, to whatever extent we have considered the set, say to N elements, we can always consider it to N+1, or 2^N elements. If this is the set of all naturals, for instance, then N in the set implies 2^N in the set. There is no end to the bijection. The proof assumes one. So tell me, what rule of bijection did I break, and at what point does the mapping through the infinite binary strings break down. For lack of answers to thses questions, my bijection stands. -- Smiles, Tony
From: David R Tribble on 20 Oct 2005 16:49 Stephen said: >> 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. > Tony Orlow wrote: > Then can you explain how the bijection between *N and P(*N) violates rules > for bijections? > Stephen said: >> If nothing in S maps to w, and w is in P(S), then f is not a bijection. > Tony Orlow wrote: > 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. How about the subset B = {0, ...999}? Or the subset C = {2, ..., ...997, ...998, ...999}? If you use your binary encoding method to map members of *N to the subsets of *N (i.e., the members of P(*N)), you will find that all of the finite naturals in *N map to some of the finite subsets of *N, and that all of the infinite naturals in *N map to some of the infinite subsets of *N. All of the subsets mapped contain only finite naturals, though. (You should check this, so you can see this for yourself.) The remaining subsets of *N contain infinite naturals, and since you've used up all of the finite and infinite naturals in *N mapping the other subsets, there are no members left in *N to map to these remaining subsets. And there are a _lot_ more remaining sets than mapped sets in P(*N). Thus there can be no bijection between *N and P(*N), and *N has fewer members than P(*N).
From: stephen on 20 Oct 2005 16:55
Tony Orlow <aeo6(a)cornell.edu> wrote: > stephen(a)nomail.com said: >> Tony Orlow <aeo6(a)cornell.edu> wrote: >> > Look, it's certainly not my position that the pwoer set is the same sie as the >> > set. It's clearly not. I just see a bijection between them, which only bolsters >> > my argument that bijection alone is not sufficient to equate the sizes of two >> > sets. >> >> > When it comes to the evens (let's start with 0), the value 0:010.......1010101 >> > represents such a subset, and is essentially binary N/3. >> >> So which number does that first 1 represent? > log2(N-1). Perhaps we should say we have 2^N subsets and strings of N digits. > That's what I should have said. Then that number is 2^N/3, and the first 1 in > it represents N-2, since the bits are numbered from 0 through N-1. So this is not the set of all even numbers then, because according to you there are even numbers larger than log2(N-1). >> Presumably that is >> the "last" infinite even number. > The last one before N. There is no ultimate last even, as we all know, silly > canilly. So this is not the set of all even numbers and you were wrong when you claimed it was. Why did you claim that that string represented all the even numbers when you in fact knew that it did not? >> And which 0 represents >> 0:010........10101? It is an odd number afterall, so one of those >> 0's must represent it. > No, that number is 2^N/3, and would be represented by the 2^N/3th bit, which is > not in the first N bits, right? This is the heart of your power set proof. That makes no sense, but that is besides the point. You claimed that 0:010......10101 represents the set of all even numbers. You now are claiming that it only represents some of the even numbers. So where is the string that represents all the even numbers? Your arguments would be a lot more consistent and sensible if you just dropped the whole notion of "infinity". It is clear that you do not actually believe in infinite sets. For you all sets must have a first and last element, and all your arguments require all sets to be finite. Stephen |