Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Dik T. Winter on 26 Jan 2007 07:06 In article <1169806783.611087.268930(a)a75g2000cwd.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > On 26 Jan., 02:41, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: .... > > In the von Neumann model. But that is a model about ordinal numbers, that > > start at 0. There are a few subtle differences. I think you are a bit > > confused here. In the von Neumann model we have that an ordinal number > > 'k' is the set of all its predecessors ( {0, 1, 2, ..., k-1), if k is not > > a limit ordinal). And so the union of two ordinals is the larger one. > > In this case, the ordinal 'k', is also the ordinal number of the set of > > predecessors. When you shift to '1' base, the latter statement is no > > longer true. > > It has nothing to do with sophisticated models at all. They only have > to simulate the basic fact. A natural number in its most basic > representation, namely unary or unadic, simply is the superset of all > smaller numbers and a subset of all larger numbers. In that case you have first to *define* what you mean with "union of representations". There is no definition for it in mathematics. > That is the origin > which has to be simulated by every correct theory of natural numbers. > II is a subset of III. By what definition? In what way are II and III sets? > This kowledge as to be taken into account when > denoting these numbers by 2 and 3. It has been done by the notation 2 < > 3. In the von Neumann model, indeed. a < b if a subset b. That is the definition of <. In the Peano axioms < can also be defined, using the successor function, but there it has not necessarily anything to do with subsetting. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Andy Smith on 26 Jan 2007 07:25 In message <emzkWscAvcuFFw+N(a)phoenixsystems.demon.co.uk>, Andy Smith <Andy(a)phoenixsystems.co.uk> writes >davidmarcus(a)alum.mit.edu writes >>> I'm not sure what you mean by "permutation". Do you mean enumeration or >>> listing? Maybe you mean bijection (a map that is one to one and onto). >>> Let's be more precise: >>> >>> Let's suppose that by "permutation" you mean a bijection . Suppose p is >>> a permutation of [0,1] and f: N -> R is a surjection. Let g be defined >>> by g(x) = p(f(x)). Then g is a surjection N -> R. >> >>> On the other hand, if h: N -> R is not a surjection, why should this >>> imply that no surjection exists? >> No please scratch my previous post, not very familiar with the terminology. But in any event I think this is off the point. As I understand it an injection f:A->B means that for every element in A , f identifies a unique element of B, but E elements of B not mapped; it is- one-to-one but not onto. A surjection f:A->B means that f maps every element of A onto an element of B such that for every element in B E at least one corresponding member of A, but this is not unique (onto but not one-to-one) For the reals to be countable, there has to be an injection from R->N, but since there is a bijection from N to any infinite subset of N, for the reals to be countable there also has to be a bijection R->N. I think? If there exists a bijection R->N , there will then be a 1:1 mapping between N and R taken in any order (given a bijection between R->N we can swap the mappings from N to R as a chain so that we can map R in ANY order (i.e. any permutation) that we choose). So if we can show that there is no one to one mapping between N and R taken in some given order, then that would imply that there is no bijection R->N ? I think. -- Andy Smith
From: William Hughes on 26 Jan 2007 07:36 On Jan 26, 4:37 am, mueck...(a)rz.fh-augsburg.de wrote: > William Hughes schrieb: > > > > > S can be and is larger than L. S is not countable. > > > > That again is an unjustified and provably wrong assertion. > > > The sequences belong to the countable union of the finite trees. > > > Take any sequence s in S. We know that each initial segment > > of a s belongs to a finite tree t(s). However there is no single > > finite tree t_D such that every initial segment of s belongs to t_D. > > s does not correspond to a single finite tree, > > s corresponds to a sequence of finite trees. >We are not interested in a finite single tree. Correct. s does not correspond to a single tree. s corresponds to a sequence of finite trees. This is an important point. > Every initial segment s > of a path has lengths n, where n is in N. If the union of all initial > segments of a path is infinite, then you should try to explain how an > infinite number could creep in and can exist unrecognized as a finite > natural number among the natural numbers. There is no initial segment of s which contains s. Therefore there is no initial segment of s which is the same length as s. The fact that every initial segment is finite does not tell us whether or not s is finite. s corresponds to a set of finite objects. We know that there is an (potentially) infinite set of finite objects (e.g. the natural numbers), so the fact that s corresponds to a set of finite objects does not tell us whether or not s corresponds to an (potentially) infinite set. > > > > > > *Everything* in this union is countable. > > > Yes, but s is a sequence of things from the union. The set of > > infinite sequences from a countable set is not countable. > That is a different matter. Each of our sequences has a length n. We have now established that: s is not an element of the union s is a sequence of elements from the union. Since s is not an element of the union, the fact that every element of the union is finite cannot tell us whether s is finite. s is a sequence of elements from the union. The question is now, "How many sequences are there?". s does not have length n for any natural number n. Each of the initial segments of s has length n, (n changes for each initial sement), but as no initial segment of s contains s, we cannot say that s has length n. s is an (potentially) infinite sequence. There are an uncountable number of (potentially) infinite sequences whose elements are drawn from a countable set. - William Hughes
From: Dave Seaman on 26 Jan 2007 07:43 On Fri, 26 Jan 2007 12:25:11 GMT, Andy Smith wrote: > In message <emzkWscAvcuFFw+N(a)phoenixsystems.demon.co.uk>, Andy Smith ><Andy(a)phoenixsystems.co.uk> writes >>davidmarcus(a)alum.mit.edu writes >>>> I'm not sure what you mean by "permutation". Do you mean enumeration or >>>> listing? Maybe you mean bijection (a map that is one to one and onto). >>>> Let's be more precise: >>>> Let's suppose that by "permutation" you mean a bijection . Suppose p is >>>> a permutation of [0,1] and f: N -> R is a surjection. Let g be defined >>>> by g(x) = p(f(x)). Then g is a surjection N -> R. >>>> On the other hand, if h: N -> R is not a surjection, why should this >>>> imply that no surjection exists? > No please scratch my previous post, not very familiar with the > terminology. > But in any event I think this is off the point. > As I understand it an injection f:A->B means that for every element in A > , f identifies a unique element of B, but E elements of B not mapped; it > is- one-to-one but not onto. A surjection f:A->B means that f maps every > element of A onto an element of B such that for every element in B E at > least one corresponding member of A, but this is not unique (onto but > not one-to-one) An injection is required to be one-to-one, but it doesn't matter whether it is onto or not. Some injections are also bijections. > For the reals to be countable, there has to be an injection from R->N, > but since there is a bijection from N to any infinite subset of N, for > the reals to be countable there also has to be a bijection R->N. I > think? > If there exists a bijection R->N , there will then be a 1:1 mapping > between N and R taken in any order (given a bijection between R->N we > can swap the mappings from N to R as a chain so that we can map R in ANY > order (i.e. any permutation) that we choose). Yes, there would have to be lots of other bijections, but it doesn't follow that every mapping R->N would have to be a bijection. > So if we can show that there is no one to one mapping between N and R > taken in some given order, then that would imply that there is no > bijection R->N ? But there is a quite natural one-to-one mapping (injection) N->R. The point is that there is no injection going the other way, and from this we conclude that there is no bijection. > I think. -- Dave Seaman U.S. Court of Appeals to review three issues concerning case of Mumia Abu-Jamal. <http://www.mumia2000.org/>
From: Andy Smith on 26 Jan 2007 08:02
Dave Seaman <dseaman(a)no.such.host> writes > >> If there exists a bijection R->N , there will then be a 1:1 mapping >> between N and R taken in any order (given a bijection between R->N we >> can swap the mappings from N to R as a chain so that we can map R in ANY >> order (i.e. any permutation) that we choose). > >Yes, there would have to be lots of other bijections, but it doesn't >follow that every mapping R->N would have to be a bijection. Sure, I just meant that if there was an injection R->N, then there would be a 1:1 and onto correspondence between N and the elements of R taken in any order that we chose. > >> So if we can show that there is no one to one mapping between N and R >> taken in some given order, then that would imply that there is no >> bijection R->N ? I should have said/ meant to say "So if we can show that there is no one to one and onto mapping between N and the elements of R ..." > >But there is a quite natural one-to-one mapping (injection) N->R. The >point is that there is no injection going the other way, and from this we >conclude that there is no bijection. > This is still following on from trying to show that the reals are uncountable based on trying to count them systematically, showing that that fails in that instance, and trying to infer that there is no injection R->N. (because, for me at any rate, that is a direct approach, and would provide an explanation meaningful to me as to why the reals are uncountable). even if one buys the argument above, there is still an issue as to whether the failure of the counting scheme might not be circumvented by some other means i.e. does the failure of the counting scheme show that the reals taken in that order are truly uncountable. I would say yes, because there is no scope for any more compact non-infinite representation of the reals than their infinite binary expansions. -- Andy Smith |