infinity ...
in [Math]
|
Prev: math
Next: The proof of mass vector.
From: Tony Orlow on 20 Oct 2005 15:41 Virgil said: > In article <1129725511.849831.257090(a)g47g2000cwa.googlegroups.com>, > albstorz(a)gmx.de wrote: > > > William Hughes wrote: > > > albstorz(a)gmx.de wrote: > > > > > > <snip> > > > > > > > > > > > If we accept the uncountability as a form of infinity, this leads to > > > > the paradoxon that the natural numbers are not countable. > > > > > > No, the natural numbers are countable precisely because > > > they do count themselves. > > > > This is exact my argument: there are uncountable many natural numbers > > (nothing other means infinity many) but the natural numbers are shurely > > countable since they count themself. > > You are not able to recognise a paradoxon if you see it. > > > The only "paradox" here is AS using "countable" versus "uncountable" in > two mutually contradictory senses in one sentence. > > In standard terminology 'countable' does not require finiteness. But, as it turns out, every set you call countably infinite is actually unbounded but finite, so Albrecht is right is a sense. > > 'Countable' merely requires that there be a surjection from the set of > naturals to the set in question, or, equivalently, an injection from the > set in question to the set of naturals. And the set of naturals has both. Oh that finite set of finite naturals used by finite set theorists. > > To be uncountable, a set must be not countable by the definition above, > so for AS to claim that the set of naturals is both countable and > uncountable is HIS error, not anyone else's. So, the power set of the naturals is countable? No one seems to be able to tell me why my bijection is invalid, so I guess it's not, and the power set of the naturals is countable too, as well as the reals, which have an order bijectible with the naturals as well (*N, not N, which is finite). Sure is good to know. Thanks Virgil! > -- Smiles, Tony
From: William Hughes on 20 Oct 2005 15:47 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} > snip > Which subset, specifically, is left unmapped? If you claim there is one, then > surely you can name it? Well, let's try the classial diagonal technique. We work from left to right. We construct e The leftmost elment of f(0) is 0 so e_0 = 1 The second from the left of f(1) is 0 so e_1 = 1 The third from the left of f(2) is 0 so e_2 = 1 It is easy to see this pattern continues, For any natural n, the binary values at position n from the left is 0. Therefore all elements of e are 1. So a subset that is left unmapped is the subset that contains all element of N*. Roughly speaking, for any n in N only about log_2(N) positions are non-zero. So there is no way to get all positions filled with ones. - William Hughes
From: Tony Orlow on 20 Oct 2005 15:52 David R Tribble said: > 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). No more FINITE naturals. Does *N include infinite values or not? > > 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. Uh, when do we run out of the unending list of infinite natural numbers? Which is the last one? For every one, there is always another after it, right? So, when does the bijection break down? After the 2^Nth element of the set of N naturals? > > > 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. What? Every element of *N has an infinite number of bits, even if the string represents a finite value. Just because an element has an infinite value, and is represented by an equally infinite bit position, that is not a problem, since infinite values in binary REQUIRE 1 bits in infinite positions in the string. > > 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. You are assuming a finite natural number of bits, but that is simply not the case with *N, or it would ony contain finite values. Are we talking about the same set? Lets say that, since we are using binary, you mean 0:111...111 with N digits. This number is 2^N-1. That's the number that corresponds to the subset containing the first N elements. It's not IN those first N elements, but it's in the infinite set. > 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. Ah, but they can, if you avoid assuming in some way that you have identified the last of them. That's what infinite bijections are all about. You simply push all differences down the line, until theyre infinitely far away and you can't see them any more. At lease, that's how transfinite cardinality works. > > 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. But that conclusion assumes a last element, whence it draws its contradictions. > > -- Smiles, Tony
From: Tony Orlow on 20 Oct 2005 15:57 Virgil said: > 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? I never said that. However, if you can enumerate the power set in order, you can take the power set of the power set, and represent each set of sets as a bitstring where membership of an element of the power set is any such set of sets is denoted by a bit. > > 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. What is the limit on the number of bits? One bit for every real number in the entire real interval. How's that? > > > > > I got a little confused, > > 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. So, which element of the power set does not have a natural mapped to it? > -- Smiles, Tony
From: Tony Orlow on 20 Oct 2005 15:59
Virgil said: > 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. I have said repeatedly and consistently that bijection alone does not indicate equality of size for infiite sets. You know that, dorkenburger. > > This is life in TOmatics. > -- Smiles, Tony |