Prev: math
Next: The proof of mass vector.
From: Tony Orlow on 21 Oct 2005 13:08 William Hughes said: > > 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). Okay, so you want to claim that the infinite strings cannot be mapped to the infinite binary strings representing n in *N. Sure. Let's see which version of the largest finite you bring out. > 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. Oh, what a shock! No largest finite, but the old diagonal argument, this time applied no to the uncountability of the reals in [0,1], but to the uncountability (?) of the set of infinite naturals. But wait, P(N) is uncountable, right? So, P(*N) must be too. It seems like we could very well have a bijection, even given your own "rules". I will repeat what I have said regarding the diagonal proof regarding the reals. It has nothing to do with the reals, and proves nothing about the ability to count a set. In that proof, as in this one, you are constructing a full list of digital representations, traversing it diagonally, and inverting those bits to form an antidiagonal which is supposedly not in the list. At each point, as you add another string to the list, you can perform this operation to get a string not on the list. But, this proof is so flawed so as to be more of a joke than a logical argument. N=S^L. N=S^L. N=S^L. Remember this. Here's the completed list 0000000000.... 1000000000.... 0100000000.... 1100000000.... What's the antidiagonal? 11111...... It's at the end of the list. Why does it not appear to be on this list? It's not on the diagonal, but the diagonal does not traverse the entire list. Did you say you have N digits in each of your strings? How many strings do you then have? N=S^L!!! In this case, L=N and S=2, so we have 2^N strings in our list. It's not square, NxN. That's not how digital numbers work outside of unary. The diagonal does not traverse all strings. Your antidiagonal is on the list, below the diagonal. In this case, you want to use the antiadiagonal to say there is no element on the list that maps to that set. It's plainly false. > > -William Hughes > > -- Smiles, Tony
From: Tony Orlow on 21 Oct 2005 13:18 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: > >> >> 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 means that imagining any completed bijection also leads to a > contradiction. w has just as much existence as your bijection. > If the bijection is complete, so is w. The bijection is never "completed". The sets are infinite, and the correspondences between element do not end. What is the final value for x in the mapping f(x)=2x. What is 2x at that point. Is x the largest finite natural? Then what is 2x, the largest finite even? None of these infinite bijections end. That's why they work as bijections. That's why they fail as measures of the sets. Define a value range, but do not declare it as an inherent property of the set, unless you want contradictions. > > > > 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. > > It is not a bijection. N is a subset of N, and is therefore > in the powerset of N, and if no natural maps to N, then > there is no bijection. There is always a natural for every subset, but you cannot define the entire set so that any such natural can be identified for it. When you speak of a mapping to the entire set, you include the implicit identification of the last element and the completed set. It's unending. There is no point you can stop and say it's over. No matter what set you have, there is a number corresponding to it that is greater. No matter what number you have, there is a set containing it further down the bijection. > > Stephen > -- Smiles, Tony
From: Tony Orlow on 21 Oct 2005 13:22 William Hughes said: > > Tony Orlow wrote: > > 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. > > Right we will have N rows (each row represents the > value of the "enumeration" at a given element and there > are 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. > > Right there are N columns > > > Now, how many such subsets are there? We have a power set with 2^N > > elements, > > And you are somehow going to fit these 2^N elements into N > rows. No, you can't. You can only traverse N rows with the diaginal, since you only have N columns. Your antidiagonal does not exist in the first N rows. But, there are 2^N-N rows left. It's in one of those. The diagonal argument is hogwash. N=S^L. That's all you need to know about digital systems. > > > - William Hughes > > -- Smiles, Tony
From: David Kastrup on 21 Oct 2005 13:29 Tony Orlow <aeo6(a)cornell.edu> writes: > 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...... Finiteness happens to be a property possessed by 0, and possessed by the successor of every finite number. -- David Kastrup, Kriemhildstr. 15, 44793 Bochum
From: Tony Orlow on 21 Oct 2005 13:33
David R Tribble said: > 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}? Let's stick to binary, use N digits per naural, and say B = {0,111...111}. Then, the natural number corresponding to this subset is 100...001, with 2^N digits. > Or the subset C = {2, ..., ...997, ...998, ...999}? I assume this means all naturals from 2 through 999...999? Okay In binary, with N digits/natural: {10,....,111...111} maps to 111...100 with 2 ^N digits. > > 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.) No, that is according to standard theory. A bijection can be made between the finite naturals and sets of finite naturals, which are always finite, since the set is unbounded and seemingly endless. The bijection between *N and P(*N) also continues forever, this time actually. Since you can always keep borrowing naturals from further down the set, you never run out of naturals to map to your subsets. Of course, the power set IS bigger, bijection genuflection notwithstanding. > > 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). That doesn't even make sense. if that line of argument is part of the standard, you're worse off than I even imagined. At what point do you think the digits run out in *N, anyway? The digits are infinite. Given any particular number of digits, what you say is true. Given an undending supply, bijection is easy. > > -- Smiles, Tony |