An uncountable countable set
in [Math]
|
Prev: integral problem
Next: Prime numbers
From: Virgil on 1 Jul 2006 17:13 In article <1151760151.357832.139990(a)75g2000cwc.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > > > > But the "number" of infinite paths through any node equals the "number" > > of infinite paths starting at the root node, and is therefore > > necessarily infinite. > > Of course it is infinite. And the number of nodes in this tree is a > large as the number in the whole tree. What do you mean by "the number in the whole tree"? If you mean the number of paths, you are wrong. > > > Where ever you look at the tree: you will see this pattern: > > | > o > /\ > o o > / \ / \ The set of reals between 0 and 1 is uncountable. The set of all their binary representations is a superset of that, since some reals have dual representations. There is a bijection from the set of binary representations to the set of all paths in an infinite binary tree, in which a 0 in the nth binary digit of the real means a left branch from the nth node and a 1 means a right branch. > Obviously there are more edges than paths. Infinitely many paths contain each "edge", which I understand to mean a branch connecting one node to the next. Each path is a set of edges (branches) connecting succesive parent nodes to child nodes. Or can you believe that > there are more paths than edges? Yes, at least for infinite trees. > How can you close your eyes in spite of this fact? My questin is: How can you close your eyes to the facts of INFINITE trees. > > > > > An infinite binary tree is such that each node except the root node is > > the child end of a branch > > Customarily they are called edges. > > > So each path can be identified with a subset of S = {1,2,3,...} by > > including n in the subset if and only if the the n'th branch is a left > > branch (one could equally well have chosen to include n for right > > branching, instead of left ones). > > This analysis is wrong. You must show that each path is different from > each other path. In order to do so they must differ by nodes and edges. If two subsets of N are different then there is some n which is a member of one but not the other. Then the paths they correspond to are different, since at that nth branching, one path must branch left while the other branches right. Thus there are as many paths as different subsets of N. > > > Thus the set of paths bijects with the set of subsets of {1,2,3,...}. > > And therefore you need again Hessenberg's proof which, as we have seen, > fails because of the imprdicable definition of K. What you claim to "see" does not always exist. There is no failure of the proof that for every set S no surjection can carry S onto P(S). So nothing is shown. That is certainly true of "mueckenh"'s arguments. > Obviously there are always more edges than paths. What is "obvious" always requires justification, and occasionally turns out to be false, as in this case. What holds for finite trees need not be true for infinite trees, particularly when proved untrue, as has "mueckenh"'s claim of more edges than paths been proved untrue for infinite trees.
From: David Hartley on 1 Jul 2006 18:43 In message <vmhjr2-1B2D19.14091601072006(a)news.usenetmonster.com>, Virgil <vmhjr2(a)comcast.net> writes >In article <1151758813.109076.7170(a)b68g2000cwa.googlegroups.com>, > mueckenh(a)rz.fh-augsburg.de wrote: > >> Dik T. Winter schrieb: >> >> >> > I wrote: P(k) = lim{k -> oo} (k,k+1)(k,k+2)...(k,k+n) where I explicitly >> > wrote that I used some intuitive form of limit here. This is the only >> > way I can make sense of "infinitely many transpositions". >> >> A transposition is an element of the set of transpositions, i.e. a set >> of pairs of numbers. The set af rationals is also a set of pairs of >> numbers. Do you raise any questions concerning this infinite set? Do >> you need some limit in order to well-order the set of rationals? > >If one stars with the normally ( and denslely) ordered rationals, no >sequence of transpositions will make it any less densely ordered. > >If one stars with the rationals well ordered, no sequence of >transpositions will make it any less well ordered. > >Thus you alleged conversion form one form to the other does not and >cannot occur. I'm not sure about this. Suppose we use the following sequence of permutations on the naturals with the usual ordering. (1 2), (1 3 2), (1 4 3 2), ... After the nth permutation, the ordering becomes n+1, n, n-1, ..., 2, 1, n+2, n+3, ... Given any i, j with i < j, for any n>j, i comes after j in this ordering and so, using the obvious definition, i comes after j in the limit ordering. Thus the limit ordering is the reverse of the usual one. A sequence of permutations can destroy a well-ordering. Each permutation can be broken down into a chain of transpositions so, with a little care, we get a sequence of transpositions which destroys the well-ordering. (We cannot replace each (1 n n-1 ... 2) by (1 2), (1 3), ..., (1 n) as the resulting sequence of orderings doesn't have a limit. But if we break it down as (n 1), (n 2), ..., (n n-1) then the limit exists.) Looking now at the rationals with usual ordering. Apply the sequence of transpositions (0 2), (1 2), (0 3), (1 3), (0 4), (1, 4), ... The limit ordering of Q has 0 > 1 > q for ever q /= 0,1 and so is not densely ordered. Now suppose q_1, q_2, ... is an enumeration of Q and suppose q_1 < q_2 < ... < q_(n-1) in the usual sense. If q_(n-1) < q_n we do nothing, otherwise apply the sequence of transpositions (q_i q_n), (q_(i+1) q_n), .. , (q_(n-1) q_n) where i is the least integer such that q_i > q_n. The new ordering has q_1 < q_2 < .. < q_n. If we do this for each n from 2 upwards, we get a sequence of transpositions which gives a sequence of well-orderings whose limit is the usual ordering. >> The set of rationals is taken to be well-ordered. The following >> transpositions operate on that set simultaneously (given are the >> indices): >> (1,2), (3,4), (5,6), ... >> where Elements q 2n-1 and q 2n are interchanged, if they deviate from >> order by size. >> In the next step the pairs >> (2,3), (4,5), (6,7), ... >> are ordered by size, in the next step the pairs >> (1,2), (3,4), (5,6), ... >> are ordered by size, and so on. There are exactly as many steps as are >> required to define the diagonal of a Cantor list. And there is the same >> definition of "infinitely" as in Cantor's diagonal proof. > >Then there must be a ->first<- transposition after which there is no >longer any first element in the current ordering of the rationals, if >the final result is to be the usual ordering of the rationals. > >But that is clearly impossible. I'm afraid this argument is on a par with "each set {1,2,..,n} has a maximum, therefore N has a maximum". I don't think WM's construction works, but even if it does, it proves nothing because sequences of transpositions needn't preserve well-ordering. >> > So you define a series of mappings. But the series is infinite. How do >> > you define such an infinite series? >> >> Ask Cantor. > >The difference being that Cantor's sequence of non-diagoal digits need >not be created seqeuentially, but can be done independently and >simultaneously, whereas yours cannot. >> >> > Again you are starting with a conclusion about the finite and extending it >> > to the infinite. You have to prove that you can do that. >> >> Ask Cantor, how he can be sure that his diagonal is different from >> every number of the list in case of infinitely many numbers. > >One does not have to ask Cantor to explain what is transparently clear. >All Cantor needs do is specify a rule which can be applied >simultaneously to ever number in a given list to produce something that >cannot be a member of the list. > >> I am not an advocate of infinity. > >You are not an advocate of sanity either. >> >> Regards, WM -- David Hartley
From: Dik T. Winter on 1 Jul 2006 19:12 In article <1151758813.109076.7170(a)b68g2000cwa.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: > > > I wrote: P(k) = lim{k -> oo} (k,k+1)(k,k+2)...(k,k+n) where I explicitly > > wrote that I used some intuitive form of limit here. This is the only > > way I can make sense of "infinitely many transpositions". > > A transposition is an element of the set of transpositions, i.e. a set > of pairs of numbers. Indeed. > The set af rationals is also a set of pairs of > numbers. Do you raise any questions concerning this infinite set? No. > Do > you need some limit in order to well-order the set of rationals? No, but that is unrelated. Transpositions operate on a set. A sequence of transposition hence also operates on a set. There is *no* definition how an infinite sequence of transformations operates on a set. > > > If what I > > wrote is not valid, please provide me with a definition of "infinitely > > many transpositions". How do they operate on a set all together? Does > > the result depend on the order? So there are many questions. > > The set of rationals is taken to be well-ordered. The following > transpositions operate on that set simultaneously (given are the > indices): > (1,2), (3,4), (5,6), ... > where Elements q_2n-1 and q_2n are interchanged, if they deviate from > order by size. Well, in the first place, this is false as written. The transpositions are conditional. But indeed, given the well-ordered set of rationals Q1, this gives a different ordering of the rationals, say the well-ordered set Q2. We can call that an infinite permutation. > In the next step the pairs > (2,3), (4,5), (6,7), ... And this does the same on Q2, giving Q3. > are ordered by size, in the next step the pairs > (1,2), (3,4), (5,6), ... And now we get Q4. > are ordered by size, and so on. There are exactly as many steps as are > required to define the diagonal of a Cantor list. There is one problem with this. There is no definition of an infinite sequence of "infinite permutations", so you should provide us with a definition. You keep assuming that the definition of the anti-diagonal of a list of reals is an ongoing steps. That is false. There is only a single step, the definition. After that we can determine each and every digit of the diagonal number without the need to know other digits. Moreover, by Caucy, such a sequence of digits defines a real number. I do not know of any definition of a sequence of overlapping "infinite permutations" that allows an inifinite sequence. Pray provide one. > > Eh? Your example just lists infinitely many transpositions without any > > definition of meaning. > > There is the same definition of "infinitely" as in Cantor's diagonal > proof. See his original paper "=DCber eine elementare Frage der > Mannigfaltigkeitslehre" , Jahresbericht der Deutsch. Math. Vereing. Bd. > I, S. 75-78 (1890-91). There is not a single word said about the > meaning of infinitely many comparisons. Because there are not infinitely many comparisons, there is a single definition. > > > So you define a series of mappings. But the series is infinite. How do > > you define such an infinite series? > > Ask Cantor. No, I ask you. > > Again you are starting with a conclusion about the finite and extending it > > to the infinite. You have to prove that you can do that. > > Ask Cantor, how he can be sure that his diagonal is different from > every number of the list in case of infinitely many numbers. > I am not an advocate of infinity. Yes, we know. In that case you should start with some form of mathematics without infinity. Go ahead. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Dik T. Winter on 1 Jul 2006 19:29 In article <1151759090.073603.122700(a)m79g2000cwm.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: > > > Eh? K(f) is defined regardles the kind of mapping of f. How can you > > come to the conclusion that it is not defined for some particular f? > > What part of the definition fails for some particular f? > > Remember what I said: > Map |R (including |N) on P(|N) with the only condition that a natural > number has to be mapped on that set K e P(|N) which contains all > natural numbers which are not mapped on sets containing them. Yes, such a map is impossible, but that proves nothing about the impossibility to have a surjective mapping from R to P(N). If a mapping is surjective the requirement is that *each* element of the target should be the image of an element in the source. There is nothing that requires that element in the source to be a natural number, *unless* the source is the set of natural numbers (or a subset of it). So what does it prove that such a required mapping is impossible? > You should be able to find out that in case of a surjective mapping, K > is undefined. No. In a surjective mapping f: R -> P(N), K(f) is *not* undefined. The requirement of surjectivity is that K(f) is the image of an element of R, *not* that it is the image of a natural number. Please look up the definition of surjectivity. > > What part of the definition fails? > > Remember what I said: .... Please remember the discussion and do not snip context. That question was *not* related to what you write here. To quote: > > 1. Let f be any function from N to P(N). > > 2. Let K(f) be { x in N | x is not an element of f(x) }. > > 3. Then K(f) is not in the image of f. > > 4. But K(f) is an element of P(N). Now you said: > K(f) is *not defined* in case of a surjective mapping f. And so I came to my question. So again the question: what part of the definition fails? Next you come with something completely different: > Map |R (including |N) on P(|N) with the only condition that a natural > number has to be mapped on that set K e P(|N) which contains all > natural numbers which are not mapped on sets containing them. Yup, a mapping with such a condition can not be found. In the case of N -> P(N) this proves that there is no surjective mapping. In the case of R -> P(N) this proves nothing like that. > > > You are confused. K(f) is required to be the image of a natural number. > > > > That is a complete misstatement of the Hessenberg condition. To be clear, > > let's have given a set A and a set of sets B (I do not yet state what the > > elements of A and B are). Let's also have a mapping f from A to B. > > Now construct the set K(f) = {x in A and x !in f(x)}. This set is > > well-defined. > > Remember what I said: The set K e P(|N) which contains all > natural numbers which are not mapped on sets containing them. That makes no sense. It depends on the map. So you should talk about K(f) (with f the mapping assumed). But what is wrong with what I wrote? -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: mueckenh on 2 Jul 2006 08:36
Gc schrieb: > mueckenh(a)rz.fh-augsburg.de kirjoitti: > > > An uncountable countable set > > > > There is no bijective mapping f : |N --> M, > > where M contains the set of all finite subsets of |N > > and, in addition, the set K = {k e |N : k /e f(k)} of all natural > > numbers k which are mapped on subsets not containing k. > > > > This shows M to be uncountable. > > > > Regards, WM > > The set M exist only if you have already defined exactly funktion f, > because there is now certain set K before the funktion is exactly > defined. So you have bijection g: N ---> M/K . Then you can add the set > K to finite sets and get M. This is no paradox and this is very > different than funktion f: N ---> P(N) because P(N) contains K by > definition. No, it does not. P(N) cannot contain K by definition, because K does not exist. You can see this by the following argument: Map |R (including |N) on P(|N) with the only condition that a natural number has to be mapped on that set K e P(|N) which contains all natural numbers which are not mapped on sets containing them. Here we have not at all any problem with too less elements in the source. Nevertheless there is no surjection possible. Regards, WM |