Prev: math
Next: The proof of mass vector.
From: Tony Orlow on 19 Oct 2005 12:03 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. > > > > 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. 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. My point is that bijection alone does not mean equal size, as this example shows well. Two infinite sets may have a bijection while one contains some finite number of elements more than the other, some finite multiple of the other's number of elements, or some formulaic relation that shows one to be infinitely greater than the other, like N^2. Such bijections are taken to imply equal size, or at least cardinality, and yet, a bijection CAN be constructed between any ordered infinite set and its power set, which contradicts the power set rule. > > -- Smiles, Tony
From: William Hughes on 19 Oct 2005 12:06 albstorz(a)gmx.de wrote: > William Hughes wrote: > > > > > > Coincidently natural numbers and cardinalities are undistinguishable in > > > finity. > > > > They are very similar, but they are not quite "undistinguishable". > > A natural number is a set, a cardinality is an equivalence class. > > You make me hopefull. Some experts make "äääh", "hömm" and > "üüüh" if I said "A natural number is a set." One sees a > correspondence between natural numbers and von Neumann sets after all. > You are free to say "A natural number is a set." without "äääh-", > "hömm-" and "üüüh-" comments. Be lucky. You are right. > And natural numbers don't behave in any other way than sets. So, if > there is an infinite set there is an infinite number. If there is no > infinite number there is no infinite set. And vic versa. You have made exactly this mistake before. Yes every number is a set. No, not every set is a number. For example {peach, apple, plum, fiddle} is a set but not a number. Just because you have a set does not mean you have a number. So yes, there is an infinite set. But this does not mean that this set is a number. Indeed, no infinite set is a number. - William Hughes P.S Actually it is not true that natural numbers must be sets, but they can be. As you insist on using a model in which the natural numbers are sets, I am playing along to be polite.
From: Randy Poe on 19 Oct 2005 12:11 Tony Orlow wrote: > 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. > > > > > > > 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. > At what point does the bijection break down? What is "the" bijection? The proof that card(S) < card(P(S)) shows that no bijection exists. That proof has been given a few times in this thread and I see you're trying to get through it. Whether you believe the proof or not yet, you do realize that the proposition is "Let f(S) be any mapping from S to P(S). Then f can't be a bijection." Right? If the proof is correct (as it is), then ALL bijections break down. The proof consists of showing that no matter what mapping you choose, there's an unmapped element of P(S). > It certainly works for all finite cases, does it not? Absolutely not. Let S = {1,2,3}. Then P(S) has 8 elements: {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} There is no bijection between the 3 elements of S and the 8 elements of P(S). > What makes you think it falls apart at some point? It falls apart for EVERY set. > For which element is there not a corresponding subset? It breaks apart in the other direction: there is (at least one) subset for which there is no corresponding element. First you have to define your mapping rule. Given any mapping rule, a subset can be identified for which there is no corresponding element. - Randy
From: imaginatorium on 19 Oct 2005 12:22 Tony Orlow wrote: > stephen(a)nomail.com said: > > Tony Orlow <aeo6(a)cornell.edu> wrote: > > > stephen(a)nomail.com said: <showing that there cannot be a bijection from a set to its power set...> > > >> 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 Yes, that sounds fairly typical. You are about to show that eleven million (whatever, I've forgotten the numbers already, and I made them up anyway) mathematicians have been getting it wrong for 100 years with an 8-line proof. But you hit it at the end of the day and got confused. > 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. Well, that was a jumble, wasn't it? What is a "completed" w? Normal set theory talks about sets, and a set contains its members. It contains all of its members, all the time, never contains anything else, never becomes tired, "unidentifiable", or "tenuous", just sits there containing all the elements it contains. (Notice that this immediately means that normal set theory can't accommodate things like sets that contain different collections of all of something, one of the direct consequences of the "infinite numbers are just the same as finite numbers only bigger" crank line.) Notice also how you are again unable to consider abstract sets, and keep mumbling about "numbers". Why on earth should the y be "larger" than any element in w? We've proved that y cannot exist at all, but there is no a priori reason any notion of "largeness" is involved. If we were considering the set of all finite simple groups or the set of all Platonic solids, there would be no "larger", but the proof applies exactly the same. > However, given the definition of bijections, it is easy to map any well-ordered > infinite set to its power set .... Blah blah blah. This one line after a proof that no such bijection exists. Well, it's no wonder you can't do mathematics. Brian Chandler http://imaginatorium.org
From: Tony Orlow on 19 Oct 2005 12:29
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. 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. -- Smiles, Tony |