An uncountable countable set
in [Math]
|
Prev: integral problem
Next: Prime numbers
From: Dik T. Winter on 6 Jul 2006 09:58 In article <1152189366.413919.218240(a)p79g2000cwp.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > Dik T. Winter schrieb: > > > But the order type of your set of transpositions is w * w. > > Sorry, I do not see that. Every sequence of transpositions leaves a > first, a second, a third element. And there is no element number oo. By > definiton, that is order-type omega. That is a well-ordered set with > ordinal number omega. You have a sequence of transpositions T1, T2, T3, ..., followed by a sequence of transpositions T1', T2', T3', ..., followed, ..., etc. That total sequence of transpositions has order type w * w. > > Moreover, > > different orderings of the same subset of transpositions will yield > > different results. In the formula I gave for the diagonal number, > > calculation of one digit does *not* depend on the calculation of > > another digit. > > And what is the consequence of this? That the calculation of the digits can be done in parallel? > > It is Cauchy's theorem that proves that the limit exists, using the > > epsilon argument. > > But Cantor's arguing is that without epsilon. I do not know Cantor's argument exactly. I think that he implicitly uses that result. In my formulation it was abundantly clear that I did use it. > > > When I stay within the domain of finite numbers. > > > > You do not. Or you are re-ordering a subset of the rationals, not all > > rationals. > > Which part do I not re-order? Sorry, I did misread. > > > > If the transpositions are well-ordered, they are indexed by finite > > > numbers - up to the last one. > > > > Wrong. In the first place, there is not necessarily a last transposition, > > OK. So let's better say: The transpositions are indexed by finite > numbers - up to every one. > > > and in the second place they are not necessarily indexed by finite numbers. > > Consider the following (well-ordered) sequence of transpositions (where I > > use, as you do, index numbers): > > (1, 2)(3, 4)(5, 6)(7, 8)...(1, 3)(2, 4)(5, 6)(7, 8)... > > what is the finite index number of the transposition (1, 3)? > > I don't know it because the set of transpositions has not the > order-type omega. But if all the transpositions are countable (which is > correct without doubt) and if countability means that every member of > the set (of transpositions) can be enumerated, then (1, 3) has a finite > number. It can be indexed by a finite number. Right. But in that case there is no connection between the index numbers and the ordering. > But recently you raised the problem that the ordinal number of the set > of all transpositions is not omega. This is in fact a problem, as your > above question shows again, because we cannot count up to or even > beyond the first limit-ordinal number. But I think I can remedy this > disadvantage in the following way. > > Start with transpositions of the indices: > (1, 2) > (2, 3) > (1, 2) > This orders the set of the first three elements by size. Then order the > set of the first 4 elements by size. > (1, 2), (3, 4) > (2, 3) > (1, 2) > > And so on. After the set of the first n elements has been ordered by > size, order the set of the first n+1 element by size. At most n-1 > transpositions are required for a set of n elements. Now, the complete > set of transpositions is of order type omega. And it maintains the > well-order by index while it achieves well-order by size. And again, it maintains the well order as long as you remain in the finite domain. So up to every finite n, you have ordered the first n elements of the well-ordered list, retaining a finite list. And back again to problem 1 with this. How do you define that when n grows without bound? How do you define the "limit"? And if you define that, is that "limit" also well-ordered? Those are things you have to prove. -- 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 6 Jul 2006 10:28 In article <1152193390.830398.326300(a)q16g2000cwq.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: .... > > > Either the diagonal number 0.111... is not distinguished from all > > > finitely large numbers of the list > > > 0. > > > 0.1 > > > 0.11 > > > 0.111 > > > ... > > > then Cantor's proof fails. If we assume that that list contains natural numbers in some unary notation (as I think you do) than: > > > Or 0.111... is distinguished from all finitely large numbers of the 0.111... is not a natural number in unary notation. So it is inherently different from all elements of the list. > "To be different" means for all unary representations of n > An : 0.111... - n =/= 0 How do you propose to define that subtraction when 0.111... is not a natural number? > Every digit can be indexed by a natural number means that there is no > digit, which is different from all unary representations of natural > numbers. Right. > By construction of 0.111... this means further that every > digit at position n and all digits at smaller positions can be indexed. > This means there does not exist any digit which differs from all unary > representations. > not forall n: 0.111... - n =/= 0 But that is a wrong conclusion. Let's call 0.111... (as a sequence of digits) K. And let's define K[i] is the i'th digit of K and An[i] the i'th digit of An. The following statement is correct: There is no i such that for all n K[i] != An[i] (1) > En : 0.111... - n = 0. And that is wrong, because that means: There is an n such that for all i K[i] = An[i]. (2) pray tell us under what logical reasoning you transform (1) to (2). And to simplify it, take A0 = 0.10, A1 = 0.01, K = 0.11. (1) is satisfied, (2) is not satisfied. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: David Hartley on 6 Jul 2006 10:45 In message <1152191768.157605.15960(a)b68g2000cwa.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de writes > >David Hartley schrieb: >> >> Infinite processes can be brought to an end if they have a clearly >> defined limit. You haven't defined what you mean by the limits of the >> orderings or mappings produced by your process. To make "this result >> occur unavoidably" you need to give definitions of both limits and show >> that the limit of the mappings is an order-isomorphism from N to the >> limit of the orderings. Using the definitions I offered, the sequence of >> orderings does have a limit, and it is the usual ordering of the >> positive rationals. The limit of the associated sequence of mappings >> from N would be an order-isomorphism if it existed but - no surprise - >> it doesn't. > >The limit is clear. The question is why it is not reached. >> >> Unless you at least try to define these limits, and to prove the >> required relationship between them, I see little point in continuing >> this discussion. > >Here is a set of transpositions of order type omega. Therefore we stay >once and for all in the finite natural numbers. >Start with transpositions of the indices: > (1, 2) > (2, 3) > (1, 2) >This orders the set of the first three elements by size. Then order the >set of the first 4 elements by size. > (1, 2), (3, 4) > (2, 3) > (1, 2) > >And so on. After the set of the first n elements has been ordered by >size order the set of the first n+1 element by size. At most n-1 >transpositions are required for a set of n elements. Now, the complete >set of transpositions is of order type omega. And it maintains the >well-order by index while it achieves well-order by size. Your quoted transpositions don't alter the ordering as you want, but the intention is clear and that does work. (It is the sequence I suggested a couple of days ago.) Now let a_n be the first element of the ordering achieved by rearranging the first n elements of the original order. It is clearly the minimum of the first n elements. The sequence <a_n> is thus non-increasing and unbounded below (in the positive rationals). Let f_n be the mapping from N which indexes the ordering achieved at the nth stage. You claim this sequence "clearly" has a limit, say f. Given that f_n(1) = a_n, what is f(1)? And don't say f(1) must be the non-existent smallest positive rational and so set theory is inconsistent. You need to prove, within standard set theory, that there *is* a well-defined limit with the required properties before you can claim a contradiction. Good-bye. -- David Hartley
From: Virgil on 6 Jul 2006 13:13 In article <1152180620.790783.87220(a)75g2000cwc.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > > > > > > Also, in ZF, ZFC and NBG, any countable union of countable sets can be > > proved countable, so "mueckenh"'s attempts to claim otherwise must fail. > > Feferman and Levy showed that one cannot prove that there is any > non-denumerable set of real numbers which can be well ordered. In ZFC and NBG, every set is in theory well-orderable. > Moreover, they also showed that the statement that the set of all real > numbers is the union of a denumerable set of denumerable sets cannot be > refuted. Where did they show this, and for what system did they show this??? Absent any such reference, I doubt that it is valid in ZFC, and ZFC is demonstably as consistent as ZF.
From: Christian Clason on 6 Jul 2006 13:32
Virgil wrote: > In article <1152180620.790783.87220(a)75g2000cwc.googlegroups.com>, > mueckenh(a)rz.fh-augsburg.de wrote: >> Moreover, they also showed that the statement that the set of all real >> numbers is the union of a denumerable set of denumerable sets cannot be >> refuted. > > Where did they show this, and for what system did they show this??? > Absent any such reference, I doubt that it is valid in ZFC, and ZFC is > demonstably as consistent as ZF. That would be the Feferman-Levy model of ZF (M9 in the treatise of Howard and Rubin [1], if I recall correctly), where R is indeed a countable union of countable sets. Of course, not even countable choice can hold in this model. In this thread, it should be mentioned explicitly that this does not imply that R is countable, since in this model countable union of countable sets do not have to be countable. Best regards, Christian Clason [1] Howard, Rubin, Consequences of the Axiom of Choice, AMS Math. Surveys and Monographs 59, 1998 |