Prev: math
Next: The proof of mass vector.
From: Tony Orlow on 20 Oct 2005 14:53 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: > >> What do you want me to try, anyway, and infinite mapping, > >> element-by-element? A bijection's a bijection, right? > > > > David R Tribble said: > >> Yes, that would be nice. Please show us your bijection. > > Tony Orlow wrote: > > 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? > > Where are the infinite subsets, such as the set of even numbers? > > Well, infinitely far down the list of course! .. .. .. .. f(N/3) = 0:010101.....010101 = {0,2,4,6,8,....} f(2N/3)= 0:101010.....101010 = {1,3,5,7,9,....} Oh, now comes the list of primes (sigh) Uh, um.... f(N/pi) = ....1010001010110 = {2,3,5,7,11,13,...} PS, I'm kidding about the N/pi part (I think). -- Smiles, Tony
From: Tony Orlow on 20 Oct 2005 15:09 Randy Poe said: > > Tony Orlow wrote: > > David R Tribble said: > > > Tony Orlow wrote: > > > 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} > > Since this infinite strings are supposed to represent subsets > of *N, I presume that they have |*N| bits. There is one bit > for each element of *N. Sure they're as infinite as the set. What was that exact number again? Oh yeah, bijection doesn't care..... > > So what you are claiming is that this is a bijection between > the bit strings of length *N, and the elements of *N. Both infinite. > > I claim that there is no x such that f(x) = *N. There is no x in any initial segment which maps to that segment, if that's what you mean, and for the overall set, there is no end to the bits, so it's really rather hard to say which element this would be. Of course, for any subset ypou specify, you can specify a natural. > Here's a > TO-ish argument: > > For initial subsets {0,1,...,x} for any x, this is mapped > by f(y) where y = 2^x - 1. Clearly y > x for all x, and > the list f(1), f(2), ... f(y) is longer than the list > 1, 2, ..., x. Since this is true for all finite x, it is > also true for x = *N. So there are not enough elements > in *N to complete the list f(1), f(2), ..., f(2^*N - 1). That's not exactly my type of argument, but I'll respond anyway. Both sets are infinite, so it does not make sense to talk of completing the full infinite unending list, does it? At least, that's what you tell me. If for every element of each set there is a uniquely mapped element in the other, it's a bijection. No one has yet been able to tell me what rule of bijection I am breaking, so I guess this is a bijection, even if the infinite sets are different sizes. > > Another argument by TO-induction: The elements mapped > by f(1),f(2), .., f(x) only include elements among > {0,1,...,log2(x)}. Thus the list f(1), f(2), ..., f(*N) > only includes elements among {0,1,..., log2(*N)}. It > isn't long enough to include {0,1,..., *N}. > > - Randy > Listen, Randy, annd well. I am not arguing that the power set is not larger than the set, for finite or infinite sets. The powerset is clearly larger, and I accept the inductive proof that shows it is 2^n for set size n, finite or infinite. My point is that a bijection can be formed, without apparently breaking any rules of bijection. If this bijection is disallowed, I would like to know by which rule this occurs. What makes this bijection invalid? > -- Smiles, Tony
From: William Hughes on 20 Oct 2005 15:11 Tony Orlow wrote: <snip> > I gave the mapping rule: > natural <-> binary string <-> subset, ordered naturally from 0. Clearly there is a bijection binary string <-> subset (this is pretty much notation). So we need to show that there is no bijection natural <-> binary string. To do this we need only assume that the bijection exists and show that it is not in fact a bijection. The classical way to do this is: Let the Naturals be N, the Binary strings be B, an element b in B has entries b_n equal to 0 or 1 (with the the interpretation that for any n in N, b_n equal to 0 if n is not in the subset represented by b). Let our assumed bijection be f. For any n, f(n) is a binary string with elements f(n)_m (m in N) Construct an element of B, call it d by defining for all n in N d_n = f(n)_n. Let e be the element of B such that e_n is 0 if d_n is 1 and e_n is 1 if d_n is 0. Then there is no m in N such that f(m) is equal to e. Thefore e is not is the range of f, and therefore f is not a bijection. -William Hughes
From: Tony Orlow on 20 Oct 2005 15:14 stephen(a)nomail.com said: > Tony Orlow <aeo6(a)cornell.edu> wrote: > > David R Tribble said: > >> Tony Orlow wrote: > >> > >> > >> > 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} > > If we define > w= { x : x not in f(x) } > then we get > w = {0, 1, 2, 3, ...... } > > So for what y does f(y) = { 0, 1, 2, 3, ..... }? > > And is y in f(y)? > > Let me guess. You will claim that F(N) = { 0, 1, 2, 3, ..... }. > So is N in { 0, 1, 2, 3, ..... }? If it is, then N is not in > w, and F(N) does not equal w. If it is not, then N is in w, > and F(N) does not equal w. > > <snip> > > > 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? > > No you have not. > > Stephen > Notice above that no natural maps to a subset which contains it, so w is all of N. Imagining any completed w leads to a contradiction, since the natural that would map to it is always bigger than every natural in that set. That's okay though, because for every natural, there's a larger one. If x exists, 2^x exists. The sets are infinite, so the bijection continues, even though there is a difference between the values which are in the subsets and the values which denote the subsets. -- Smiles, Tony
From: Tony Orlow on 20 Oct 2005 15:22
William Hughes said: > > Tony Orlow 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. 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. > > Well the binary notation is certainly convenient. Let's lay > things out in a sort of a square > > Take the set X > > How many columns do we need. One for every element of X > > How many rows do we need. One for every element of X > > Pity about the complement of the diagonal. > > Lets try X = N*. > > How many columns do we need. One for every element of N* > > How many rows do we need. One for every element of N* > > Pity about the complement of the diagonal. > > > > - William Hughes > > Ha ha ha. Nice try, William. Let's get real. You want a sqaure? It's not square. We have a set with N elements. We will enumerate the elements of the powerset, represented as binary strings with 1 bit per N elements, or N bits, per line of the table. Now, how many such subsets are there? We have a power set with 2^N elements, each with N bits. So, your pitiful diagonal only traverses the first N elements of the power set, leaving 2^N-N elements untouched. Your pitiable complement of the diagonal is somewhere in that unlisted vast majority, just like the natural which maps to your set at the supposed point of completion. The power set is larger than the set. Is it "uncountable"? Uh, no. Is it impossible to biject an infinite ordered set with its power set? Nope, not true either. Is the power set larger than the set? Oh, most assuredly, on that we agree, or at least most of us. -- Smiles, Tony |