Prev: math
Next: The proof of mass vector.
From: Virgil on 19 Oct 2005 14:30 In article <1129725929.185024.95960(a)f14g2000cwb.googlegroups.com>, 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. > > > Regards > AS We do not know what YOU are talking about. The proof that there is no surjection from and set X to its power set P(X) does not require, or even use, any form of induction whatsoever. Given any function f:X -> P(X), let S = { x \in X : NOT(x \in f(x)} then it transpires that (1) S is a well defined member of P(X), and (2) there is no y in X such that f(y) = S. Thus no f can be ONTO P(X). No induction requires.
From: David R Tribble on 19 Oct 2005 15:05 Tony Orlow: >> 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: >> 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: >> 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: >> 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: >> Not enough infinite binary strings? > Virgil: >> Precisely. > Tony Orlow: > So, you need more than an infinite amount? How many more? We can show a mapping (surjection) from the finite naturals in N to the finite subsets of N (the finite members of P(N)) using your mapping strategy. But then you don't have any more naturals left to map to the infinite subsets in P(N). Pretty much the same thing for *N - using your binary mapping stragegy, we can show a mapping between the finite naturals in *N to the finite subsets of *N (which are the finite subsets in P(*N)), and a mapping between the infinite naturals in *N to some of the infinite subsets in P(*N). But after we've run out of members in *N for mapping, there are still more infinite subsets remaining in P(*N) that we can't map. Consider the subsets S(n) for any n in *N, using your binary index mapping scheme. If n is finite, the subset S(n) is also finite; for example, S(42) = S(101010(2)) = {1,3,5}. If n is infinite, S(n) is also infinite; for example, S(...999) = S(...111(2)) = {0,1,2,3,...}. But there are still more subsets left in P(*N), and there are not enough left over members in *N, finite or infinite, to map to them. These subsets contain at least one infinite natural, and that natural has no bit index corresponding to a member of *N. For example, subset B = {0, ...999} has no corresponding n in *N that can map to it, because there is no natural bit index available to represent the second member. This example is just one of an infinite number of finite and infinite subsets of *N that cannot be mapped with the finite and infinite members of *N. The conclusion is that there does not exist a surjection from the members of *N to the members of P(*N), and therefore no bijection between them is possible.
From: Virgil on 19 Oct 2005 15:15 In article <MPG.1dc01c72d14b842b98a4e0(a)newsstand.cit.cornell.edu>, Tony Orlow <aeo6(a)cornell.edu> wrote: > stephen(a)nomail.com said: > > 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. > > 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, and > the question remains what number maps to the set containing just that > natural. You are assuming some completed w, where some identifiable y > is the number that maps to it. But that number has to be larger than > any of the elements in w. So, you draw a contradiction from the > assumption that y is in N and also maps to N. Clearly, the power set > is LARGER than the set. > > However, given the definition of bijections, it is easy to map any > well-ordered infinite set to its power set through the binary > representation, such that each element's position starting at element > 0, represented as a binary natural, also represents a subset of the > naturals, where the bit in the 2^n position denotes membership of the > nth element. You may have a discrepancy in the values of the naturals > and the values in the subsets, but you have a complete bijection > nonetheless. For what set is TO assuming that each member of its power set can be represented by a single bit in an infinite sequence of bits? If that set is the set of all Dedekind infinite binary strings, which is uncountably infinite, or any set bijectable with it, then TO's assumption is false. Unless we are operating in TOmatics where an "infinite string of bits" can contain an uncountable number of bits. > I got a little confused, It appears to be a permanent condition > but you still haven't proven anything like > the impossibility of a bijection with the power set. We have to those who are not so permanently confused. > In other cases > bijections are performed without regard to such discrepancies. The 'discrepancy' is that when mapping a set to its power set, there must always be a member of the codomain which is not the image of anything in the domain. When that happens, whatever one does have, it is not a bijection.
From: Virgil on 19 Oct 2005 15:21 In article <MPG.1dc0376e59b8e8c98a4e1(a)newsstand.cit.cornell.edu>, Tony Orlow <aeo6(a)cornell.edu> wrote: > > > 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. > At what point does the bijection break down? It certainly works for > all finite cases, does it not? What makes you think it falls apart at > some point? For which element is there not a corresponding subset? > For which subset is there no corresponding element? Name either one > of these, as a counterexample, or explain why you think the bijection > fails. > > > > > > > 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? > Sets don't have an inherent measure beyond raw size, and the power > set is not well ordered as far as subset size goes, so it doesn't > make sense to talk about a value range on the power set exactly. > However, one might think of the binary mapping of the power set to > the set, and say that the power set of an ordered set has an order > based on that mapping, taking each bitstring as a natural. In this > case, you might be tempted to say, if the set has N elements, the > power set has a range of 2^N-1. > > > > > > > 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. > f(0) = ...000 = {} f(1) = ...001 = {0} f(2) = ...010 = {1} f(3) = > ...011 = {0,1} f(4) = ...100 = {2} f(5) = ...101 = {0,2} f(6) = > ...110 = {1,2} f(7) = ...111 = {0,1,2} > > etc. Any questions? > > > > > > > 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. > But I have constructed a bijection between the two using an > intermediate binary representation. What is the specific rule I have > broken concerning the construction of bijections. If I haven't broken > any such rule, then is it true that a bijection between two sets > means that have the same size, or even cardinality? > > > > > > > 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. > Which subset, specifically, is left unmapped? If you claim there is > one, then surely you can name it? > > > > 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. > But, as the keepers of that standard say, what holds for the finite > case does not necessarily hold for the infinite case. Once you have > infinite sets, neither one ends, and there is always a natural for > any subset, and always a subset for any natural. Isn't this the way > the standard treatment of bijection goes for infinite sets? > > > > > > > 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? > No, I fully agree with that conclusion. However, there is nothing > that precludes a bijection between any ordered infinite set and its > power set, despite the different sizes. Since 'more' in the context above means that there cannot be any bijection, To is now claiming that where there *are* reasons why no bijections can exist, there also are no reasons why bijections cannot exist. This is life in TOmatics.
From: Virgil on 19 Oct 2005 15:27
In article <MPG.1dc03e89763835a898a4e2(a)newsstand.cit.cornell.edu>, Tony Orlow <aeo6(a)cornell.edu> wrote: > William Hughes said: > > > > albstorz(a)gmx.de wrote: > > > David R Tribble wrote: > > > > 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? > > > > > > > > > Sad! First of all you don't argue on my claim of the thread. > > > Second, your above argueing is not clear to me, since both sets > > > are well-ordered. But it's nice, so I give this: > > > > > > N {1},{2},{3}, ... N/{1},N/{2},N/{3}, ... > > > {1,2},{1,3},{2,3},{1,4},... N/{1,2}, ... ... > > > > > > Now count in diagonal sequence. You may think of Cantor's first > > > diagonal proof. > > > > > > Which subset of N is not included? > > > > Sigh. Try {2,4,6,8,...} Or any other infinite subset that is not > > the complement of a finite set. > > > > It is common for people to note that the finite subsets of N are > > countable and incorrectly claim that the subsets of N are > > countable. Adding in the complements of the finite subsets does > > not change things very much. > > > > Those who do not study anti-cantor cranks are doomed to repeat > > their idiocies. > > > > - William Hughes > > > > P.S. No TO, going to TO-infinite rows is not going to help us. > > The problem is that for any TO-finite row, the subsets listed > > will have an bounded finite number of elements, or be the > > complement of a subset with a finite number of elements. Yes, > > you can claim (without a shred of motivation) that when you > > get to TO-infinite rows the subsets will suddenly have an > > unbounded number of elements, but all this tells us is that a > > bijection from the TO-naturals to P(N) exists. What we need > > is a bijection from the finite TO-naturals to P(N). > > > > > Look, it's certainly not my position that the pwoer set is the same > sie as the set. Since the argument is not about sizes but about lack of any surjection/bijection from any set X to its power set P(X), size in TO's sense, is not an issue, but bjiection is. > It's clearly not. I just see a bijection between them TO accepts the proof of no bijection then immediately turns around and claims to see a bijection. This is TOmatics at its best! Which is, as usual, not very good! |