A most interesting historical overview of Cantor's work on infinite sets of different cardinalities is : "Constructive Mathematics" - Alan Calder (Sci.American 1979, p134-143) "Problem with Cantor's diagonal argument" . . . sci.math 15-feb-2002  NB (24dec04): I will explain the clue of "different orders of infinity" once again, using the *generative* view of three infinite sets (otherwise we don't really know what we are talking about) generated by n, n^2, 2^n. Hopefully this will suffice for you to answer your own questions. Just remember: this is all very simple, don't over-complexify please! No philosophy is involved, nor meta-physics, nor religion. . . . . Why the attack on Cantor's Theory? Re: Sequential Dimension (sci.math 27feb99) I said (re 'uncountable' infinite set 2^N > countable set N of naturals): > Cantor's diagonal argument simply proves this to the satisfaction of > any serious and competent mathematician (it took me a while, but then: > I am an engineer - though with some extended math background - > see my book http://home.iae.nl/users/benschop/preface.htm ) > So controversies you mention are fake, and due to not understanding > the essense of Cantor's result!< JM: Yes, most certainly. Controversies (paradoxes) are always fake. NB: I do not agree : I find a controversy usually arises from different points of view, or different priorities, or different assumed axioms. And even : due to not understanding the clue of a matter, which is the case here, regarding Cantors different kinds of infinity. JM : "However, his definitions and axioms, though mathematically self-consistent and thus logical and forward-thinking wrt functionality and mathematics, are misleading, absurd and backward wrt metaphysics." NB: Not misleading : his stuff is simple (really, I'll show you next). But it is wrongly interpreted, resp. over-interpreted, by people who do NOT understand its simplicity (aided by wrong teachers who misrepresent it;-( - - and want to apply it in mysterious ways. NB: In fact he studied Fourier analysis (function decomposition into periodic functions) in the general case of 'any' function on the reals. JM: Was it a solution for "squaring the circle"? NB: No, that has little to do with it. For details, again : > For a practical view of this, see my homepage on the subject > http://home.iae.nl/users/benschop/cantor.htm JM: Did you invent the usage of "GENERATORS" here? NB: No, this is a standard term in the algebra of closed systems. DEF1: a closed system S(#) is a set S closed under operation (#), - - - meaning that the composition c = a # b of any pair a,b in S - - - yields a unique element c that is also in S. DEF2: a subset A of S(#), write A < S, generates S if A* = S, - - - meaning that all compositions of any length over (#) - - - cover all elements of S. The elements of such A are - - - generators of S under operation (#) - - - Preferably one takes a minimal set A of generators, - - - which however need not be unique (apart from its order). For instance the set N of all positive integers (called the naturals) is generated by the number 1 under addition, written as N(+) = 1*. (1) Set N is the first infinity I present to you. It is referred to in Péano's axiomas of integer arithmetic, and concernes his 'successor function' : s(n) = n+1. Starting with n=1 and repeating ad infinitum, you get the 'countable' infinite set N of all positive integers. This is almost axiomatic, and intuïtively trivial (I hope;-) Think of the pos.integers on a straight line from origin 0 to the right = half the known 'integer number line'. (2) The next infinity I introduce is the seemingly much larger set of all (grid-) points with positive natural coordinates in the XY plane, Denoted N^2 for obvious reasons: the two orthogonal axes X and Y are like set N, spanning the upper right quarter (positive.int) plane. Now comes a clue : the cardinality of plane N^2 = card. of line N. How come? This has to do with the definition of 'equal cardinality'. DEF3: sets S and T have equal cardinality if there is a one-to-one - - - mapping between their elements (especially for infinite sets) Now card(N) = card(N^2) because N^2 can be generated by a zig-zag curve, or single line stepping through all gridpoints of the right-top quarter of the (x,y)-plane: start at (0,0) goto (0,1) (1,0) --> (2,0) (1,1) (0,2) --> (0,3) (1,2) (2,1) (3,0) --> (4,0) (3,1) etc. Notice the diagonals of constant_sum but increasing like N ? This is a 1-1 map between N and N^2, so they have the same infinity class (equal cardinality). More generally, such 1-1 mapping can be found for each finite k-dimensional hypercube. E.g. 3D integer-grid space N^3 is also 'countably infinite', like N. So linear N and polynomially generated sets N^k all have the same order-of-infinity : the same cardinality as the countable integers N. (3): Now exponential generation R01 = 2^N of all binary strings over a 2-letter alphabet, say A = {0,1}. Which you can, by the way, see as all reals on interval [0,1) coded as infinite binary representation to the right of the binary point (hence the name R01 for this 'set'). Now comes the clue of Cantor's diagonal proof: there is no 1-1 map between 2^N and N, resulting in a higher infinity-order of 2^N, called uncountable, versus countable ('linear infinity') N. Fill a square infinite matrix of N rows and N columns with 0's and 1's. This N x N binary matrix is countably infinite in two directions: right and down. Each row represents the binary code of a real between 0 and 1 (thus a fraction r < 1). in fact, by its rows or columns the matrix represents a countably infinite set of reals between 0 and 1. Now consider the diagonal starting at the left-top origin going right-down, of countably infinite length = the code of real d < 1. Then no matter how the binary matrix is filled, the bitwise complement c of d is a real that is not equal to any row or column of the matrix, since it differs in at least one place (the diagonal place) from the bits in each row & column. Hence there is NO 1-1 mapping between reals 2^N in [0,1) and the naturals in N. . . . and 2^N is called uncountable. . QED Summary : - - For 'infinity' consider closed systems rather than sets. 0. Consider infinte sets only by the way they are generated. - - This is to enable you to find (or disprove) any 1-1 map. 1. The system N(+) of naturals has one generator: 1 (Péano). 2. The integer grid plane N^2 has card(N) : also countable. 3. R(+) = 2^N of reals in [0,1) can't have one generator (Cantor) 4. So 2^N is uncountable, - - as are all A* = k^N strings over |A| = k > 1. Whatever you want to do with these different infinity classes is up to you, but I'd suggest not to over-interprete these simple results, please. . . . >> Subject: E.T.Bell "The Development of Mathematics" (*) >> Re your request (wsm-7064): the E.T.Bell book, and his style, >> see http://home.iae.nl/users/benschop/quotes.htm (*) Cantor and the irrationals & transcendentals (pg 78) Ciao, Nico. On dividing by zero ... countable and uncountable infinities. . . . . It's how to generate them that counts! From: Nico Benschop Re: How I Divided by Zero, and Lived to Tell About It! Newsgrp: sci.math 14may2001 "David W. Cantrell" wrote: > > "Mapi32" 'Matthias' wrote: > > > > Hello, I'm not a mathematician, but I have noticed that many > > "scientists" rather like to dismiss certain issues that make > > logical sense, but have been left out of our rather ancient > > view of numbers. > > Hello, Matthias. You must be very careful as to what does or does > not make sense. Sometimes it is not obvious whether something makes > sense or not. Making that distinction can be especially difficult for > a novice, such as yourself. > > > Take, for example, the fact that for any 2 points (real numbers), > > there are in infinite number of points between them. Here is an > > interesting case, as no one could logically deny that, if difference > > between 1 & 2 is oo (infinite), and the difference between 2 & 3 > > is also oo, than oo+oo is greater than the original oo. NB: You're asking for trouble here (;-) because, as you should know, among the positive reals there is NO SMALLEST real. That's why there are "infinitely many" of them between any n and n+1, for instance. So _how_ are you ever to "count" the number of reals between 1 and 2 ? The words "counting" and "real-number" are contradictory for that reason! Hence you have to be _very_ careful with infinite sets, and their "size" or rather 'cardinality'. If you _do_ want something more constructive than that, about different kinds of infinite sets -- for instance compare the set N of all positive integers (Péano) with the set 2^N of all its subsets, or with the set N! of all its permutations (group)- or the set N^N of all its transformations (semigroup) - then look at the minimal number of GENERATORS (which I call the 'sequential dimension' seqdim, for the moment) and you'll see the essential difference: N = {+1}* has one generator "1", under addition (+); 2^N has two generators {0,1} or {a,b} -- while group Z! has 3 generators, namely {a,b,c}* with a: n+1 (add), b: n-1 (subtract), c: swap (0<->1) readily seen if you replace N by Z (all signed integers) See http://home.iae.nl/users/benschop/cantor.htm and http://home.iae.nl/users/benschop/ism.htm (integer_state machines) One calls the set N "countable", which then means: ONE generator, and immediately you see that 2,4,6,8,... ALSO is countable, with ONE generator, namely "2" (under addition). In fact ANY number, say "a", generates countable infinite set a* of all strings over one letter 'a'. So "countable" is NOT some arithmetic property of infinity, but the TYPE of infinity that can be generated by repetition (ad infinitum;-) of a SINGLE GENERATOR (no matter what you call it: it is just a model of the concept of "iteration" or "repetition", that's all;-) which can NOT be equivalent to an infinity that NEEDS 2 generators, can it? Such infinity (like 2^N or 2^Z) one calls "uncountable": so seqdim > 1. ... Of which there are more than one type, of course, differentiated by the minimal number of generators: so N^N or rather Z^Z (the state machine with all integers Z as state set, and all its transformations as 'input-sequences', then Z^Z = A^Z with basic alphabet A of 4 inputs: A = {+1, -1, swap2, merge2} is an "uncountable infinity of type_4". See: -- http://home.iae.nl/users/benschop/ism.htm (infinite state machines) PS: This applies of course ONLY to infinite sets with an "operation", which yields with any pair their composition: an element also in the set. Only _then_ can one talk about 'seqdim' = the smallest nr of "generators". Just "infinite Set" without any qualification of HOW to GENERATE such infinity can hardly be considered mathematics with a logical basis. -- Ciao, Nico (NB)  How diagonal is Cantor's diagonal ? . . . (NFB: sci.math, 10jun98) A super_exponential dynamic bootstrap process to resolve a static paradox. Let me just explain how I got to this example in Cantor's diagonal argument, namely: 0.111* at first (where * means: repeat last digit). As engineer concerned with digital circuit design methods I take, if at all possible, a generative point of view, to fix the attention and specify more precisely what you are really doing. That's why I like Cantor's diagonal proof : it starts with representing the reals in decimal (or binary) expansion to the right of the decimal point "." (or other natural base b>1). However, it is rather loose about the precise listing specification, except it assumes the list to be complete as basic assumption to derive a contradiction. Now with the digit-reverse code that I posted earlier, I attempt to generate a complete list of reals on [0,1) in binary code. Let me explain in more detail the generation process involved. In base b=2: for k=3 we get the next complete list, in bit-reverse code, of all 2^3 strings of length 3:  Cantor's partial diagonal .0 0 0 - - - - - .0 - - .1 - - .1 0 0 - - - - - .- 0 - ---> .- 1 - .0 1 0 - - - - - .- - 0 .- - 1 .1 1 0 x - - - - .0 0 1 - x - - - .1 0 1 - - x - - .0 1 1 - - - x - .1 1 1 - - - - x .1 _ k 1 _ _ _ m  k + m = 2^k bits . . . ( m extra bits to complete the diagonal 'x' ) For Cantor's "diagonal" consider such bit-reverse ordering for any k, by symmetry with all naturals generated in the usual manner, adding 1 repeatedly: Peano's (+1)* generating successive binary codes for all n \in N, to generate all reals on [0,1). In fact at any k, consider Cantor's diagonal of as many bits as there are elements in the list. There are 2^m -1 strings not in the list for each string in the list, namely the non-zero strings filling all m "- | x" places per row. Hence a total of 2^k.(2^m -1) non-list strings: an overwhelming amount over the 2^k listed strings. Notice that m+k = # bits per string = 2^k bits. -- Now add all missing strings to the list, which thus expands to all 2^(2^k) strings of 2^k bits each. So the missing strings by Cantor's argument changed now into "regularly generated" strings for the case k' = 2^k. -- At the next level of generation, a diagonal of length 2^(2^k) results, requiring a next round of "completing" the list, expanding it with all missing strings of length k" = 2^(2^k), etc. This defines recursively the list length, which grows as the " super-exponential " function defined by : 2#(r+1) = 2^(2#r), where 2#2=2^2 . . (r=2). This way we don't miss a string, including at each expansion step all missing strings. Now all infinitely long bitstrings to the right of '.' are known to cover all reals on [0,1). Clearly any such process can be called "finite", but I mean the limit of such process for the number of steps (not k, but #r rounds). The main characteristic is the rate of growth to infinity, a dynamic property, of the generative process. This is indeed an awfully fast growing list, as-it-were a "bootstrap" to produce the reals on [0,1). For me Cantor's proof is charming and seemingly very detailed. It's dynamic interpretation bootstraps into the infinite precision reals at a rate that is 'super-exponential', taking care of all generatable strings, and all missing strings (what other strings are there?). xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx  Cantor Diagonal : Successive Naturals in Binary matrix, & Permute Rows Subject: Re: Question about Cantor's diagonal proof (sci.math 11dec01) -------- Scott Strattner wrote: > > Thanks for all the replies...I guess I still don't understand why the > representation of an integer matters when discussing the properties > of the numbers considered abstractly...if '1' and '...0001' are the > same, numerically (in other words, they represent the same set > cardinality :)), then you should be able to use them interchangeably. > If you can't; if performing an operation on one representation leads > to different results than the other, then isn't the operation you are > doing not applicable to the numbers themselves but only to that > particular representation (ie, don't mistake the map for the > terrain)? So the standard integers (one way to represent a whole > number) are of lesser infinitude than the reals (thanks to > Cantor's proof), but that doesn't mean the INTEGERS (those things > of same cardinality as the integers, represented differently) are. > And since 'integer' and INTEGER are two valid ways to represent > numbers, then we can't make any claim to the validity of Cantor's > proof to numbers themselves...ok, my head hurts now. No need to > reply, I just wanted to think out loud. I'll ponder this some more, > or just drop it and get back to the TV. :) NB: Cantor's proof is based on considering infinite strings over a finite alphabet A of at least 2 elements, for instance A={a,b}. It is confusing to mix their arithmetic interpretation into it! Cantor's diagonal proof has 'nothing' to do with arithmetic & numbers, and everything about strings over an alphabet, it's as simple as that! The essence of his proof is about a square table with entries (symbols) taken from A, and the 'size' of the table is w x w (countably square;-) Consider a countably long list of countably long strings over A. Nothing arithmetical about it. Then by the Cantor diagonal argument: there's always at least one (countably long: w) string over A that is not in *any* w x w table over A. Convergence (of reals) and of integers (if ever defined;-) are irrelevant concepts. That is Cantor's syntax, no more & no less: There are uncountably many strings of countable length over A iff |A|>1. Moreover: it does not make sense to talk about an infinite set *without* defining HOW it is GENERATED. Hence the need to only consider closed *systems* , i.e. with an operator. The only difference with 'countable' is that Peano defined |A|=1, so a single-letter alphabet, often taken A = {1} with an arithmetic interpretation of "generating the positive integers" by iteration: all n-length strings over '1' denoted n \in N (countable set N of naturals). The clue is thus: the number |A| of 'sequential generators' for the strings: if =1 then 'countable' infinity, if >1 then 'uncountable' ,, Of course you can endlessly 'mekker' about arithmetic interpretations, but then, I guess, you're missing Cantor's point...;-) -- NB http://home.iae.nl/users/benschop/cantor.htm http://home.iae.nl/users/benschop/seqdim.htm  [** Christian Bau wrote: . . . . . . . . . . (sci.math, 12jun98) As for Cantor's diagonal proof, it is obvious that if there are any counter examples (real numbers not included in a supposedly complete countable list of all real numbers), then there must be more than countable many: Otherwise the reals WOULD be countable after all. **] NB: . . Sure, an assumed list of all reals - yet being not complete by Cantor's diagonal argument, should imply the reals being uncountable. What I did is to resolve this 'paradox' into a generative process "squaring the diagonal" as it were, yielding an awsome fast generation process (see also an earlier posting in this thread). Recall Newton's iteration process to approach a root of a polynomial, sometimes called regula falsi method. It starts with a initial approximation, and applies an (additive) correction derived from that polynomial. This is an interesting approach in general, also for approaching a "closure" (in this case of the reals on [0,1] ). It resolves an apparent 'static paradox' into a dynamic generation , namely a bootstrap process of alternating the two alternatives. In Cantor's case the two alternatives are: . . (1) . . list complete . . ( listlength of 2^k binary strings, each of length k ) . . (2) diagonal complete ( necessary for comparing two strings of same length as the listsize ) They cannot hold simultaneously, so the 'bootstrap' is defined by first producing a complete list (1), and next completing the diagonal (2), originally of length k, to length = new listsize = 2^k. The bootstrap process is indefinite iteration { (1),(2) }* which yields the super-exponential growth function 2#r, that is r-1 times repeated (^) on base 2. The first noted transcendental real (Liouville, 1844) is the very fast converging series: t = \sum 2^{-n!}. Notice that n! grows faster than polynomial, and hence t is not algebraic. Limit t cannot be a root of a polynomial of any degree, because this series converges faster, by rest term 1/2^n!, than polynomial. Could the very fast generation process of 'squaring the diagonal' as described earlier, with listsize growth 2#r = 2^(2^(2^(...(2^2)))..) -- that is r-1 times repeated exponentiation -- be interpreted as a measure of the 'density' of the reals? . . After all, density is minimum distance, that is 2^{-m} for an m-bit string, and in general for m = f(n): 2^{-f(n)}. For the cardinality of some infinity, it may be characteristic to consider the convergence rate of some generating series defining it, with rest-term 2^{-f(n)}. Converging in this case not to a single limit value, but towards completeness, hence closure. Define for any natural base b>1: . . . b#{r+1} = b^(b#r) . . . Then (#) is repeated (^), the natural next operator beyond (^) as repeated (*), which itself is repeated (+). With (^) not associative, placing brackets makes a difference. This definition of super exponential (#), as in 2#r = 2^(2^(2^(...(2^2)))..) with brackets rightmost, yields the next faster growing function, beyond exponential f(n)=2^n, corresponding to the cardinality of the r-1 times repeated power-set of S, with |S|=2. sci.math(17dec98) Cantor's diagonal (in square table) | .0 0 0 - - - - - .0 - - .1 - - | .1 0 0 - - - - - .- 0 - ---> .- 1 - | .0 1 0 - - - - - .- - 0 .- - 1 .1 1 0 x - - - - .0 0 1 - x - - - .1 0 1 - - x - - .0 1 1 - - - x - .1 1 1 - - - - x .1 _ k 1 _ _ _ m k + m = 2^k bits . . . ( m extra bits to complete the diagonal 'x' ) Notice that there is for finite k NO 1-1 mapping k <--> 2^k, let alone for k-->N (all naturals, that is: k--> w). Hence my initial urge to use "induction" -- which is here rather heavy & unnecessary. For instance, consider k = 2^i, then for *each* of the k strings in Cantor's square table (nec. due to "diagonal";-) there are 2^{k-i} strings in the complete set of 2^k. Obviously for no such k is there a bijection! And letting k increase makes this impossibility only more obvious... While Cantor's argument does suffice, producing only ONE string not in the initial table, it represents a rather "thin" image of what's happening, I feel. As it were: Cantor uses a thin spider's thread, while there is an extremely thick cable of proof (of the non-existence of a 1-1 correspondence N .vs. 2^N) Remains it's interpretation. To me, this result means that comparing the set of naturals N, and its powerset 2^N (of all its subsets): ------ is like comparing two DIFFERENT DATA TYPES: ----------- ------ in other words: there *is* no comparison;-( ----------- >>>>>> SETS and NUMBERS are not comparable datatypes <<<<<<< .... and again something else are the N^N FUNCTIONS: N --> N .... NB: n^k < 2^n < n^n (for large enough n) -------------------- Let your diagonal be diagonal ---------------- --------------------- Hence your table be square ------------------ ==== sci.math 28dec98:  Re: -- Cantor's diagonal --> square_table (coun_table w x w) In article <763g2l$sfu@seaman.cc.purdue.edu>, ags@seaman.cc.purdue.edu (Dave Seaman) wrote: > In article <762p7g$h00$1@nnrp1.dejanews.com>, wrote: > >In article <75uhkv$pna@seaman.cc.purdue.edu>, > > ags@seaman.cc.purdue.edu (Dave Seaman) wrote: > >[...] > > Since you think this part is the crux of the matter, I take it you now > agree that statements (1), (2) and (3) are equivalent, and your > objection is that the Cantor Diagonal Proof (CDP) does not establish > (3): > > (1) R is uncountable. > (2) There is no surjection f: w -> R. > (3) For each mapping g: w -> R, there exists x in R > (depending on g) such that x != g(k) for each k in w. > ^^^^^^^^^^^^^^^^ > > Did you miss the "depending on g" part in (3)? > [...] No, I did not. And I appreciate your elaborations in [...]. However, just one more question regarding these mappings g_i (I'm a slow learner;-) "Cantor's diagonal" is a generative process which, given any countable subset X_i of powerset 2^N, produces at least one new element d_i (not in X_i): the corresponding complemented diagonal (re: binary string representation). ---< Addendum: Of course the indexing g_i is insufficient in case there are un-countably many countable subsets of 2^N ;-) But surely this should be investigated first, should'nt it? Also: each countable subset X produces many more than one diagonal, considering the w! permutations of X ( |X|=w ) certainly not all generating the same diagonal... That *also* influences the cardinality of the union of all produced diagonals. And circularity must be watched: diagonals generated by one X should not overlap with another X' , or if some do, they should be discarded; say by taking X' disjoint from \union{X , Diag(X) } where Diag(X) is the set of diagonals produced by permuting X. Without such structural analysis the UnCountability proof is incomplete, (to say the least;-) >--- Is it not relevant to consider the generative power of this diagonal process? In other words, without an analysis of the cardinality of CD={\union d_i} the proof seems to be incomplete (since Cantor's diagonal only concerns a countable w x w square table). What if it turns out that CD is only countable? Then un-countability is in fact disproven. This problem of incompleteness occurs due to the fact that the CD process cannot hold for the "complete" powerset 2^N, but only for any countable subset. Just curious... Ciao, Nico Benschop -- http://home.iae.nl/users/benschop/cantor.htm Subject: Re: Millionaire Mathematics (sci.math 17 Apr 2002) ------------------ "Dik T. Winter" wrote: > > Nico Benschop writes: > > "David C. Ullrich" wrote: > >> Look. Say S_n is the set of all strings of 0's and 1's of > >> length n. Then S_n has 2^n elements - this grows exponentially. > >> But the union of the S_n is countable. [...] -- David C. Ullrich > > > > Indeed for finite n. Now let n --> w, yielding strings of > > countably infinite length having the above given arithmetic > > semantics as reals on (0,1). > > At no point will the union contain any string of infinite length, > because there is no single set that contains a string of infinite > length. So also in the limit the union will not contain any string > of infinite length. -- dik t. winter Right you are, I have to get used to the difference. Even 1/3 in binary code has an infinite representation: 1/3 = .010101010101... thus .(01)* in repetition notation 2/3 = .101010101010... thus .(10)* with '...' : limit + ------------------------- 1 = .111111111111... thus .(1)* Natural Binary 'NB' (Cantor) table up to n=6 (incl. 0, reals >= 1/2): \ \ ^^^^^^^^^^^ 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 1. 1 0 0 0 0 0 0 1 1 0 0 0 0 0 2. 2. 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1. 3. 1 1 1 0 0 0 0 1 1 1 1 0 0 0 4. 4. 1 1 1 1 0 0 0 1 1 1 0 0 0 0 3. 5. 1 1 1 1 1 0 0 1 1 1 1 1 1 0 6. 6. 1 1 1 1 1 1 0 1 1 1 1 1 0 0 5. \ \ D= 0 0 0 0 0 0 0 D= 0 1 0 1 0 1 0 <-> 1/3 <-> even n \in N. In terms of Cantor Diagonals (D) - notice: uncomplemented -, in binary code representing subsets of naturals set N, with place 1 just right of the binary point, etc.: 1/3 <-> all even n \in N <-> D of all C2 (swap) perm's (2i-1,2i) i>0 2/3 <-> all odd n \in N <-> D of all C2 (swap) perm's (2i-2,2i-1) i>0 1 <-> all n \in N <-> -D : Complemented Diagonal of Nat_Bin table. For infinite subsets, resp. reals in (0,1) - this representation of 2^N by special permutations of the NB_table rows (disjoint cycles of adjacent rows) suffices, doesn't it? -- NB - http://home.iae.nl/users/benschop/cantor.htm Re: Problem with Cantor's diagonal argument A* : Uncountable iff |A| > 1 Subject: Re: Millionaire Mathematics (sci.math 17 Apr 2002) ------------------ "Dik T. Winter" wrote: > > Nico Benschop writes: > > "Dik T. Winter" wrote: > > > At no point will the union contain any string of infinite > > > length, because there is no single set that contains a string > > > of infinite length. So also in the limit the union will not > > > contain any string of infinite length. -- dik t. winter > > > > Right you are, I have to get used to the difference. > > So, here there is exponential grow but the result is countable. > And you said that exponential grow implied uncountable, so that > was wrong, showing that was the purpose of Ullrich's example. > ... > > Natural Binary 'NB' (Cantor) table up to n=6 > > (including 0, for 2/3): > > Now you have an unlimited number of swaps. In this case you get > 1's at all odd places. But that is of course something completely > different. I have a feeling of deja vu (from a long time ago). That's right, I'm occasionally working on it, see : http://home.iae.nl/users/benschop/cantor.htm and */ism.htm > The map you have here is neither injective nor surjective. > > > For infinite subsets, resp. reals in (0,1) - this representation > > by special permutations of the NB_table rows (disjoint cycles of > > adjacent rows) suffices, doesn't it? > > Suffices for what? You mean: > > > This maps each element (= subset of N) of Boolean lattice 2^N > > (coded by countably long binary strings) 1-1 into group N! > > of all permutations of N, ... > > You give a map from sequences of swaps of the positive integers > to the reals. No, as mentioned: I map each subset of N (in other words an element of lattice 2^N) - which is coded uniquely by a binary string as diagonal in the Natural Binary table - into group N! of permutations of N (here: a permutation of the rows of that table) This is a 1-1 mapping into N! due to the construction of the perm'n, corresponding uniquely to the ordered set of adjacent rows that are cyclically permuted to obtain the desired diagonal = binary coded subset of N. The mapping is from 2^n to n! elements, with 2^n < n! for finite n>4 (good point, thanks). PS: That the full group N! (resp. Z!) be 'generated by two permutations' is irrelevant here (so I drop that claim;-) since I map only to a special subset of permutations, namely permuting cyclically disjoint subsets of adjacent rows of the table. These cycles are disjoint, so they can (I think) be obtained by commuting sub sequences of three 'basic' permutations in A={a,b,c} mentioned earlier: shift_up n+1, shift_down n-1, and 'swap' (0,1) - where naturals N are replaced by integers Z (forming a group). > I do not see where the lattice comes in. > And the map you have given is not 1-1. > > To show that it is not injective: > Consider a 4x4 table. There are 24 permutations but only 16 > different possible diagonals. > To show that it is not surjective: > A real that terminates in its binary expansion is equal to some > real that goes on with a continuous series of 1's. That is, the > single swap (12) gives the same real as the infinite series of > swaps (23)(34)(45)(56)... But the latter is of course not a > permutation of the integers. -- dik t. winter I'm now not concerned with reals in (0,1) - which have the problem of multiple representations as you mention - but with 2^N (resp. 2^Z) to be represented by certain type of permutations of N (resp. Z). It's just strings in B* over B={0,1} <--> Diagonals <--> Row permut's. -- NB sci.math (3jan99) : ----------------- NB: >[...] >One other observation: the N! permutations of countable set N, > corresponding to row_permutations of a binary w x w square table, > say the identity matrix (with all_1 diagonal), >yield many distinct Cantor diagonals - probably all 2^N of them, (*) >don't they? And if 2^n is uncountable ('UC') then so is N! Brian M. Scott answered: [...] The easiest way to look at permutations is as 1-1 functions from a set onto itself. Let N! denote the set of permutations of N. Then yes, N! is uncountable. Indeed, its cardinality is w^w = 2^w. ------------**] Re(*): As I posted earlier, the 2^N subsets of N occur in the N! permutations of N, namely as fixed_point subsets. Let permutation p: N --> N have set F_p \in N be fixed, so p: n --> n for each n \in F_p, then all permutations with this property (fixing F_p) form a group G(F_p): the "stabiliser" of F_p. And for each pair of subsets S,T of N: G(S v T) = G(S) & G(T), so the stabiliser of a union is the intersection of the stabilisers (correct me if I'm wrong here). Now it is known that each full symmetric group has 2 generators, and I guess this would consistently hold also for G_N, the full group of all N! permutations of N. Then it seems reasonable that 2^N, as fixed-pointsets of permutations in G_N, are sequentially to be generated by 2 elements, versus Peano's one generator 's': n --> n+1, for all n \in N. ... Makes sense? So: G_N is not countable, but of "dimension 2", and by consequence (via contradiction?) also 2^N. Then 2 is the minimum nr of sequential generators for N! *and* 2^N (maybe even less than 2 for 2^N, but definitely more than one... What is say 3/2 generator? ... don't restrict your imagination ;-) --------endcopy --------------------- sci.math (12jan99)------------------------ dik@cwi.nl (Dik T. Winter) wrote: > benschop@iae.nl (Nico benschop) writes: > > Similarly, by the same proof method: > > With S = {0,1} and S^k = all binary strings of length k. > > Then S^k is a countable set for each k, and the union of > > all the S^k is also countable. > > It follows 2^N, as uncountable, cannot be the union of the S^k. > > ;-( > > Excellent, you are learning. -- dik t. winter Thank you Dik. What I learned is roughly (correct me if I'm wrong): an UnCountable (UC) closure must have an UC set of generators, and: a Countable set of generators cannot generate an UC closure. The UC concept, beyond countable and proof-by-induction (-;) may be welcome, I guess, to an abstract person (who tries to take as large a distance from reality & all practical purposes as possible;-) But, true to my simple needs: wanting something practical out of discrete math, I see Cantor's Diagonal not as a "closure_breaking" divice (countable --> uncountable), but as a "generating_device". Namely considering not just *one* complemented diagonal [after all: w+1=w is no big deal, finite intuition: 'one extra' breaks closure, does not hold - even countably inf. extra diagonals don't suffice] but *all* possible diagonals generated from a countable square w x w table (say the Boolean identity matrix of order w, see below) by permutating all |N|=w rows (or equivalently: all columns). This yields permutation group N! which, like powerset 2^N , is also UC. Yet N! -- or rather Z! for group-reasons (Peano's {+1}* is not a permutation, as Dave S. noticed), might be finitely generatable (?) At first (and still) I thought by 3 basic permutations. But then, if generation is not of interest (let alone finite- or countable- generators), or even excluded a priori, then I will be satisfied with approaching 2^Z from above via Z! in some more restricted sense. To at least have a finitely generated closure which includes powerset 2^F, where F = {fixed-sets of all permutations in group Z! = A*/Z }. ...If you get my drift ;-) ----------------------------------------------copy-5jan99------: NB: The classical "UnCountability" is not so much my aim, really, as related to "reals". Rather, my suggestion re permutations was to generate 2^N by just two generators sequentialy, in the N! group. The Cantor diagonal was my natural context, with Boolean Identity matrix of size w x w, representing the naturals by (say) its rows: 012345678... 0<->1 row_swap 0 100000000... 1 010000000... 1 010000000... 0 100000000... 2 001000000... 2 001000000... 3 000100000... 3 000100000... 4 000010000... 4 000010000... 5 000001000... 6 000000100... 7 000000010... 8 0000000010.. . . . Cantor Diagonal CD: Permuted table: CD= (1*)' = 0* CD= (001*)' = 110* : 2-element subset in 2^N. --------------------------------------------------copy-9jan99----: NB: I generated all 4! = 24 state-permutations for a 4-state ISM(Q,A) with stateset Q={0,1,2,3} input alphabet A={a,b,c} defined for all integers n in Z (although for finite Q=Z mod 4: only a,c suffice): a: n --> n+1 (global increment) b: n --> n-1 (global decrement) c: n --> n, except 0<-->1 (local swap) Indeed |A*| = 4! with generative Spectrum = {3,6,6,5,3,1} , the number of new permutations in A^i (i=1..6). Your pairwise twist came up last (!): "aacbbc" = (0<->1)(2<->3) in A^6, a good testcase. Notice that ab = ba = cc = e: the identity permutation. So in general, minimal length representations over A have form (a*.c.b*.c)* where c functions as marker ("comma"). The code is then a sequence of repetitions (naturals) of two kinds: a and b alternating, possibly (?) not countable (Peano +1* / Cantor UC) ------------------------------------------------------endcopy--- PS: What I'm after is a characterization of the known "data types" by the algebra's they allow (associative, commutative, idempotent) and by the minimal number of generators of a 'full' closure : ^^^^^^^^^^^^^^^^^^^^^^^^^^^^(Seq_Dimension) Symbol Type SeqDim Generators Algebra Closure ----+--------+---+-----------------+-----------------+------------ N Naturals 1 {+1}* Assoc, Commut've PosInt N(+) Z Integers 2 {+1,-1} Assoc, Commut've Ring Z(+,.) 2^Z Sets 3 (not sequential) Assoc, Cmt, Idt Lattice Z! Permut's 3 {+1,-1,swap2} Assoc, Const_Rank Group Z^Z Functions 4 {+1,-1,swap2,merge2) Assoc, Reduc_Rank Semigroup ------------------------------------------------------------------ sci.math 16jan99: ---------------- In article <77ofvj$3kv$1@nnrp1.dejanews.com>, benschop@iae.nl wrote: > In article <77nouf\$lft@seaman.cc.purdue.edu>, > ags@seaman.cc.purdue.edu (Dave Seaman) wrote: > > In article <369E7F64.4C4@iae.nl>, Nico Benschop wrote: > > >Dave Seaman wrote: > > >> No matter how you permute the rows of that table, you can't > > >> ever produce a diagonal that has all 1's on it. Because the > > >> first row is all zeroes, and no matter where you put it you > > >> are guaranteed to get a 0 on the diagonal. -- Dave Seaman > > > > > > But I take only the singleton rows (one 1, rest zero) -- a > > > perfect model for naturals set N, namely '1' on position n > > > for natural n. Row 0* does not occur then, and the initial > > > diagonal is 1* (all 1). This may seem to restrict Cantor's > > > procedure, but the advantage is that this identity table > > > I_w is a *complete* list of all n in N. -- NFB > > > > I take it you mean that the exact contents of the wxw table > > are prescribed in advance and are not arbitrary. > > If we assume that the original table is > > > > 1000... > > 0100... > > 0010... > > . > > . > > as you suggest, if I understand you correctly, then what > > permutation of the rows will give you 01111... on the > > diagonal (exactly one zero, that is)? -- Dave Seaman > > Good point (again), Dave. > But easily solved by noticing that 1* and 0*, the initial main > diagonal and its complement, are not in N (repres'd by I_w rows) > So consider with each element (bitstring) its complement ( )'. > Then your 01* = (10*)' is the complement of the first row. > > Now how to interpret this in terms of group N! (rather: Z!) ? > To each permutation of N belong two subsets: its fixed_pointset, > and its moved_pointset: the complement of the former. Call it a > 'balanced' generation process. Each string in A* =(a* c b* c)* > yields a permutation of Z, with *two* subsets of Z (in lattice > 2^Z) which are each others complement (bitwise inversion). > I would need to think about how to incorporate the rows of > initial I_w, the generating structure, as elements of group Z! > But they certainly play a special role in this process. > In fact if you consider N <=> I_w as countable set of rows > (with a single 1), then so is the set of their complements > (with a single 0), and we need not interprete them at all > as group elements. A better suggestion? ... > ... (we are constructively 'brainstorming' here;-) After some more reflection: write D(x) for the diagonal belonging to permutation x of Z, for instance D(a)=D(n-->n+1)=0* (all zero). And let CD(x) be its (bitwise) complement in 2^Z, the "complemented diagonal" (or "Cantor Diagonal" if you like;-) Then your 01* = CD(bc) because, if we consider integer stateset Z, then 'c' swaps 0<-->1 only, while D(b)= D(n-->n-1)= 0* : \| b -1 100000 0 010000 1 001000 2 000100 3 000010 | \ D(b)=0* \| bc -1 100000 1 001000 0 010000 2 000100 3 000010 | \ D(bc)=*0 1 0* and CD(bc) = *1 0 1* of which your 0 1* is the right half. (Note: *1 is all ones to-the-left) All ones should be denoted *1* ;-) Clear is the need for integers Z (vs. naturals N) in this permutation group Z! Hope this helps. Ciao, Nico Benschop - - - - | -- http://home.iae.nl/users/benschop/cantor.htm | One is Always Halfway Anyway xxxxxxxxxxxxx1.1xxxxxxxxxxxx ------------------------------------------------------------------- sci.math 18jan99: ---------------- NB: > >For the time being "countable" means for me: > > one generator suffices, > >and "uncoutable": > more than one generator required to generate a closure. > > DS: > The group S_3 of permutations on three objects has order 6, > but it requires two generators. > Does that mean that 6 is uncountable? ..(*) > -- Dave Seaman It depends whether, or not, you compare 'structure'd closures (which I tend to do, following Peano's N(+) = {+1}* ;-) The definition of "countable" set S is ambiguous about that, in the sense that it requires comparing a set without structure (or rather: with the structure of a lattice 2^|S| ) to a set _with_ structure, namely N(+)={+1}*. Indeed, my interpretation of countable/uncountable emphasizes the structural aspect of the two sets S and N, by a generative view. I admit this is highly unorthodox, and I'm not going to defend my view against the established view of just looking at the cardinality -- a valid viewpoint allright -- and that's how it was started by Cantor, I guess. But just look at his proof, via (say binary) representation in a (necessarily square w x w) table. Does that not, at least, suggest to take also structure into account? Which is precisely what I did: look at the representation of "all" rows in I_w ( = order w identity boolean matrix, with 1* main diag.) in a lattice structured 2^N (with N represented by the respective matrix rows, each having one '1' and rest zero) Due to the idempotent lattice algebra (bitwise AND, OR for intersection, union) the full N is required as infinite but countable set of generators of that lattice, under union (|). Cantor's proof of "uncountable" then boils down simply to checking the number of ones, say in the complemented diagonal which is NOT in N obviously because it does not contain just _one_ 1, but none. In fact, the diagonal itself is all-Ones, hence _also_ not in N. Moreover, since this one_1 bitstring representation of N is indeed 'complete' -- a single string beyond it yields a convincing counter example --> 2^N is not "countable" (2^N : all bitstrings length w, with _any_ number of 1's, thus not restricted to single_1 strings). This definition of "(un)countable" leans towards distinction by data type, certainly suggested by incorporating (seq_)structure. This version of Cantor's proof, by comparing structured sets (there seem to be already several versions, to which I add just another one;-) is an interpretation of the dichotomy "countable vs. uncountable" based on a generative view: not uncommon for infinite sets (how else to specify;-) Unfortunately -- or if you will fortunately -- this distinction can also be made for _finite_ (structured) sets. Then indeed group S_3 of 6 permutations, needing two generators, is indeed "uncountable", meaning it cannot be isomorphically mapped into a cyclic group (viz. 1 generator), nor is it an image (projection) of such. Clearly, for comparing cardinalities of finite sets/systems one does not bother Cantor;-) -- straight counting will do...;-) However, for infinite sets/systems it might well be very useful to take a generative viewpoint ... to resolve endless discussions, and solve ambiguously defined problems. Why not .?. Of course, to prevent confusion the term "(un)countable" should not be used, and I suggest "sequential dimension" (seq_dim) as the minimal number of generators to generate a covering closure (that is: of which the set/system is a sub_closure). Then, for instance, any finite group is of seq_dim 2, since the full symmetric group S_m of all m! permutations of m states has requires 2 generators. Using infinite integer state set Z, as shown, the infinite group Z! requires 3 (seq)generators. Then the classical concept of "countable", referenced to the one-sided infinity N(+)={+1}*, is a 1_dimensional concept. And the integers Z(+,-) = {+1, -1}* is of seqdim=2, a two-sided infinity. A closed "function": mappings of a set into itself, is a seqdim=3 concept in the finite case. While for the infinite case seqdim=4, since all functions f: Z-->Z form a semigroup of 4 seq_generators: A = {a: increment, b: decrement, c: swap2, d: merge2} Just a suggestion;-) Ciao, Nico Benschop. ------------------------------------------------------------------ sci.math 20jan99: ----------------- Brian Scott: >>> You've got to get this #c --> inf. business out of your head: >>> it's completely irrelevant and is just misleading you. (%) > > NB: >>Re(%): Maybe I will, if you can answer me this: >> Since infinite A* is countable, as you say, its elements >> can be put into 1-1 correspondence with the naturals set N >>(for instance represented by the rows of the order w identity >> binary matrix I_w). But then A* can be generated by just one >> element, the characteristic of 'countable'. BS: >Not true. Let A={0,1}, let L0 be the set of words containing no 1, >let L1 be the set of words containing no 0, and let L be the union > of L0 and L1. (L corresponds to the expression 0* v 1*.) ..(#) > Clearly L is countable, ..(#) > and clearly it requires more than one generator. ..(#) > Or if you want permutations, note that you can't even generate > all permutations of a 3-element set with just one generator. A > single generator produces only countably many words/permutations, > but not every countable set of words/permutations can be produced > by a single generator. -- Brian M. Scott NB: Re(#): I would think |L| = 2 ;-) Excluding finite strings, how many are there of type 1* ? Just one, if I'm not mistaken, and also just one 0*. They are the two complementary extremal strings in lattice 2^N (powerset of naturals N): its 'top' and 'bottom' element resp. Of all_0 strings with a single 1 there are countably infinite, because the "position" of the '1' must be specified - counting from the beginning position --> Clearly showing that we talk here about a one-sided infinity;-) Which fact I miss in most discussions on countable infinity, or do *I* miss something here? There =is= a way to sequentially generate both 1* and 0* -- and all other binary strings of length w (omega |N|) in 2^N. Namely as fixedpoint sets (with complementary 'movedpoint sets') of all permut's in group Z! permuting the integers (state)set Z, in the proposed Integer State Machine ISM(Z,A) with A={a,b,c}={incr1,decr1,swap2} under *one* sequencing operation. Where Z! has seqdim=3, with general string structure (a* c b* c)*, similar to 2^N with string structure (0* 1*)* with sequencing (*), clearly _not_ set intersection or union. -------- ================================================================ Subj: Re: Why the attack on Cantor's Theory? Date: 14 Mar 1999 From: Nico Benschop Org.: The Math Forum Newsgrp: sci.math [**-------------------------------------------------------------- David Petry wrote: > You're trying to understand observability from within a framework > of thought honed from the study of Cantor's Theory. You cannot > succeed that way. You must start from your understanding of the > finite world observable through computation, and then use the > principle of observability as a guide to extending the finitary > concepts into the world of the infinite. > > If you hand me a Cauchy sequence of rationals, I will hand back > to you a real number. Whatever assurance you have given me that > you really have given me a Cauchy sequence, I will in turn give > back to you assuring you that I really have given you a real nr. Give me a countable list of all real numbers, and I give you back a real number not on your list, applying the diagonal process to your list. Whatever assurances you give me that you have a countable list, I will in turn give you to get a number ..(.#) not on your list. Gee, we just got Cantor back. - Brian Rothbach --------------------------------------------------------------**] NB(#): Not only _one_ number outside your list, but w! (omega factorial) of them (!-) For all permutations of the rows of the w x w table you seleceted, with the respective diagonals & complements thereof. And for those of every _other_ w x w table you may choose. So use Cantor's diagonal trick as a generating procedure, and see where you end-up: 2^Z embedded into infinite group Z! Z = {+1, -1}* : the 'linear' group of the integers -- 2^Z = {fixedpoint sets of permutations in group Z!} = Bool Lattice Z! = {+1,-1,swap01}* : a 3-generator infinite permutation group. {a,b,c}* with ab = ba = cc = e (identity permutation on Z) So each irreducible sequence in {}* has form {a*cb*c}* [c='comma'] "isomorphic" to all binary sequences {0*1*}* [runlength code] representing 2^N , hence all reals on interval [0,1). Only three sequential generators... (of niet soms?-) So is 2^N, which is in 2^Z, finitely generatable after all ?-) (3 generators) Ciao, Nico Benschop -- http://home.iae.nl/users/benschop/cantor.htm ================================================================== Subj: Compare N and 2^N (Peano Cantor) via Z and 2^Z in group Z! sci.math: Fri, 12 Mar 1999 --------- Fred W. Helenius wrote: > > Nico Benschop wrote: > >> Z ={+1,-1}* : an inf. group with two generators: seqdim(Z) =2 >>Z! ={+1,-1,swap01}* : an inf. group with 3 gen's: seqdim(Z!)=3 >>In both cases the number of generators cannot be reduced, >>so there is no way to make an isomorphism between them > (more completely to be proven;-) > > Could you please explain what you mean by "generator"? Under set A of generators of group G I understand a subset of G which under sequencing (function composition of permutations of stateset X by which G is represented) generates G, write G=A*/X. With equivalence: a = b in G <--> ia = ib in X, for all i in X. (using Clifford/Preston's left-to-right function notation;-) In this sense, we have the integers: Z(+) = {+1,-1}* since {+1} would only generate the naturals N, under sequencing: N = {+1}*. > In the group theory sense, Z needs only one generator, If one includes the group inversion operation, for instance 'complement' -1 of +1 in Z(+), then indeed only one generator {+1} suffices: a matter of difinition, cq a matter of taste... So much the better: then seqdim(N)= seqdim(Z)= 1, and closure S is declared "uncountable" iff seqdim(S) > 1 ..[1] - Beyond the normal interpretation of 'uncountable' relating to a higher infinity type than Peanos 'countable' naturals N. Another name for property seqdim(S)>1 should be used, of course. Moreover: property [1] can also hold for finite (assoc've) closures, a bit unusual to relate to countable/uncountable, clearly. And: I somehow assume some 'structure' allowing one to define a particular infinite closure in the first place (I don't quite see how a generative view of 'infinity' can be avoided: how otherwise to be specific enough about some infinity - *without* a generative process? Can one specify an infinite set by complete display of all elements?-). > and the symmetric group on Z cannot be finitely generated. > Previously, you said something about allowing infinite products; > if so, how are they defined? Apparently, one needs some axiomatic setup for infinite sequences ('products'). Here I take the usual associative sequencing operation, isomorphic to function coomposition. In Clifford/Preston's left-to-right notation (semigroup theory): define function 'fg': X --> X, by x(fg)=(xf)g for all x in X. Some proper axiomas should define existence for infinite X = N, or rather (cyclic) group structured infinite X = Z(+). Which, by my understanding, would just mean that the syntax (assoc) of this composition would also be declared valid & the same for infinite |X| (whatever that would imply...;-) Correct me if I'm wrong, or talking nonsense here (;-) because uptill now my only experience is with finite state machines FSM(T,A) on finite state set T and input alphabet A, with sequential closure (semigroup) S = A*/T. Here we have an infinite state machine IMS(Z,A) = A*/Z over the integers as infinite state set, with A = {+1,-1,swap01}. I certainly intend to check if such A suffices to generate Z! = A*/Z while this was uptill now just an assumed extension of the finite case, where each finite symmetric 'full' group G_m of order m! has 2 generators: any m-cycle and any 2-cycle (fixing the remaining m-2 states). I would be surprised if this cannot be extended to the infinite case (under sensible definitions...) > What, for example, would be the image of > zero under the product of infinitely many copies of "+1"? Do you mean: the 'product' (=sequence) of n copies of '+1' as {+1}^n ? This would with argument 0 yield 0{+1}^n = n (natural n) And for n --> w (omega), this yields countable infinity w. In finite case Z(+) mod m, we have -1 = (+1)^{m-1} (mod m), yielding the inverse (rather: complement) -1, so only one generator suffices to generate Z mod m, including the inverse -1 of generator +1. In the infinite case Z this is not so: complement -1 is not in {+1}*, hence my suggestion to consider it as a separate generator. Comments are welcome. Ciao, Nico B.   Re: A Loophole In Cantor's Argument? (sci.math 15apr99) From: Nico Benschop (AmSpade Research) John Savard wrote: > > Mark Adkins wrote, in part: > >> If anyone had the audacity, after reading it, to claim that >> no point in a line is next to *anything*, it should be >> obvious that this is impossible, since a line is continuous. > > The real number line only contains one copy of each number. > Thus, since points have zero extension, if a point touched > another point, those two points would have to have the > _same position_, which means they are the same point. > > Hence, that a line is continuous does *not* mean the points > in it are "touching"; you are using a physical intuition > which is not applicable. > > John Savard (teneerf is spelled backwards) > http://members.xoom.com/quadibloc/index.html In other words: the problem of 'understanding' the continuum on the 'real line' comes from the fact that there is *NO mimimal distance*, hence: NO minimal number... period. I guess most contradictions with practical (finite) intuition arise from this rather artificial axiom. Unlike with the (infinite) set N of naturals, which *do* have a unique minimal element '1', which by repetition "added" to itself N = 0{+1}* yields the whole closure (one-sided infinity). Signed integers Z = 0{+1,-1}* have *two* minimal generators -1 and +1. The reals, not even on [0,1) have NO generator, hence that "set" must by axiom be imposed to exist, "out of the blue sky"... with intersection (&) and union (|) as idempotent (non-generating) operators: S & S = S, and S | S = S for any set S. -- Ciao, Nico Benschop. | AHA: One is Always Halfway Anyway http://home.iae.nl/users/benschop | Institute of Advanced Engineering PS: Notice that, in the 'real' and 'continuous' line set_theory, Descartes' condition for clear logic reasoning: "the apparent distinction between objects", is not satisdfied! Thus one is asking for trouble, as it were: Condemned to pure syntax, and 'semantics' not supported by finite intuition.  Subject: Re: Cantor's diagonalisation argument and the naturals sci.math: 14 Apr 99 [**----------------------Paola Cattabriga replied to N.G.duBois: Hi Mr Injection :-), >Today I received Prolog - Programming for Artificial Intelligence >Ivan Bratko via the Koninklijke Bibliotheek. Good Luck! >But I have the "intuitive feeling" that 1111011 etc. does exist > in my list ;-)) So I think I did not construct a "new" number, > so Cantor's method seems to me not valid. [#] >Paola did I reinvented some "mathematical wheel"? >Or do I make some serious mistakes? It's the time for you to know that there are many method to show that reals can be counted or generated see for example: http://home.iae.nl/users/benschop/cantor.htm and my "Notes on subset enumerability" in "old works" of my homepage http://www.serdata.it/cattabriga/cat8.html By my own here the question is purely theoretical. It is now self-evident to me that ordinals are already a generation (and hence an enumeration) of all the decimal digits '...' in '0, ...' ( or in '1, ...', or in '___, ...'), exactly like they are an enumeration/generation of the naturals. Ordinals already show that your "intuitive feeling" (that 1111011 etc. does exist in my list ;-)) is correct. See my Notes or still Benshop method. See also << Re: 0.999..., 1.000... and Cantor's proof sci.math 26Jun98>> at the bottom of my homepage: http://www.serdata.it/cattabriga/default.html > I look out to your answer. I send a copy to sci.math Don't do that! You will become mad! ...[*] Your fancy beyond -- Paola Cattabriga ------------------------------------------------------------**] Re[*]: Not necessarily;-) You may get angry sometimes, but that's OK. Just develop some "eelt op de ziel" (hard crust around the soul), filter a lot, and retain the good (which is sparse, but existent) Re[#]: A contradiction follows ONLY if it was claimed/assumed that the initial list is complete. But this cannot be the case, because a "diagonal" assumes a SQUARE TABLE, in this case of w x w bits ( w=|N| : 'omega' = cardinality of countable infinity of naturals) Moreover: The concept that a single counter-example disproves a global claim is 'borrowed' from the finite, and thus, by the usual argument of Cantorists, must be suspect: our finite intuitions do not apply to the infinite ! (re: vanishing counter_evidence ;-) But again: Cantor's diagonal argument does NOT invoke the concept of 'contradiction', since (see above) it necessarily applies an incomplete w x w table.... All that the diagonal argument says is: there are more nrs than you think, and certainly more than w. Hence my argument: USE the diagonal as *generating* process, re: w! permutations of an initial table --> generate group Z! > 2^Z Ciao, Nico Benschop -- http://home.iae.nl/users/benschop/carry.htm IAE.nl -- Institute for Advanced Engineering ;-) Subject: Re: Equivalency of Infinite Sets, and "countable" has one generator? sci.math: 7 Jun 1999 -------- Zdislav V. Kovarik wrote: > > In article , > Ross A. Finlayson wrote: > [...] > : On a totally different subject, I would write some things > : about decimals and decimal repsesentation. > : For a given base b, and number of decimal places p, for > : numbers between zero and one, including zero, there are > : b^p possible numeric representations. > : > : As an example, for base three, at two decimal places, > : there are 3^2possible numeric representations, > : .00, .01, .02, .10, .11, .12, .20, .21, and .22. > > (1) Look up the word "decimal" in a dictionary. It comes from > Latin "decem" which means "ten". > If you call a system of representation of numbers with > basis b other than 10 a "decimal" system, there is > considerable room for improvement of your vocabulary. > Bluntly speaking, your use of the word "decimal" is > illiterate - and of course incorrect. > > (2) These counting routines are taught in an introductory course > of probability (year I). The keyword is "counting in stages". > Counting techniques are a good topic for self-study, and many > good textbooks are written about them. Publishing a re-discovery > of such routine results by a beginner would be a total waste. > > (3) To make your head spin even more, there are "positional systems" > of representing numbers, which use different bases for different > positions. The imperial system is an example, with miles divided > into yards, yards divided into feet, feet divided into inches, > and then there is a mix of ways how to divide inches. > > (4) Learn about continued fractions. They are an efficient tool for > approximating numbers by rationals. A good author: Khinchin. > > Good luck, ZVK. May I suggest something along this line - related not so much to infinite sets, but to infinite closures *with* an operation that says how to generate such infinity (seems a necessary condition to me; the alternative: listing all elements seems a bit 'cumbersome';-) Putting it simply: if "countable" means "one generator" (like Peano's naturals: N(+) = {+1}*, star means repeat ad infinitum) then what does "uncountable" mean? Could "uncountable" possibly mean: needing more than one generator ?-) One objection against this simple approach, as brought to my attention earlier, is that also *finite* closures may require >1 generator, for instance non-cyclic groups (like the smallest case: C2 x C2: Klein's group of the direct product of two 2-cycles). But then: finite stuff can be counted trivially and listed completely, so we 'restrict' ourselves here to infinite closures. Moreover: the integers Z(+) require, under addition, _two_ generators: Z(+) = {+1,-1}* -- while in the classical (Cantor's) model this would be called a 'countable' set (having only 2w = w elements;-) After all, a one-sided infinity N, and a two-sided infinity Z, are in the known sense both "countbale", are'nt they (both of cardinality omega w)? But now the infinite group Z! of all permutations of Z, which requires all of three (3) generators for its generation: Z! = {+1,-1,swap2}*, where swap2 = any permutation swapping two integers and fixing the rest. _That_ would be uncountable, would'nt it? And powerset 2^N, or rather powerset 2^Z, which is not really just a set but a closure ('Boolean lattice') under no less than two operations: (sub)set intersection (&) and union (|), which unfortunately are idempotent: S&S=S and S|S=S for any set S of naturals, resp. integers. Now 2^Z can be approached 'from above' as lattice of fixedpointsets of permutations in Z! -- so sequentially not requiring more than 3 generators, although more then 2 surely: it is more complex then Z(+). Would this make sense, as a 'proof' that 2^Z (and hence 2^N) is uncountable? (needing more than the 2 generators of Z, and in fact 3 generators suffice to generate sequential closure Z! 'containing' 2^Z). PS: One could call a d_generator closure A*, with |A|=d as minimum necessary number of generators: "d_countable". Then the naturals N(+) are 1_countable, the integers Z(+) are 2_countable, permutations of integers Z! is 3_countable, and all integer transformations Z^Z (seq) 4_countable. For more details on this approach, see my homepage http://home.iae.nl/users/benschop/cantor.htm Does this make sense? -- Ciao, Nico Benschop - IAE - Institue of Advanced Engineering benschop@iae.nl -- http://home.iae.nl/users/benschop  Cantor.htm work.htm "Constant Rank State Machine structure" . . . Comments are welcome --- Ciao, Nico Benschop. Re: -- Cantor's diagonal --> countable square_table / UC threshold ? . . . sci.math 20jan99 Re: -- Integer State Machine (was: Understanding Cantor's Diagonal) . . . sci.math 18jan99 Re: -- Integer State Machine (was: Understanding Cantor's Diagonal) . . . sci.math 16jan99 Re: -- Cantor's diagonal --> countable square_table / UC threshold ? . . . sci.math 3jan99 Cantor's diagonal as Regula Falsi generator of reals on [0,1) . . . . . . . sci.math 16jun98 Re: How many reals are there ? . . . . . . . . . . . . . . . . sci.math 6nov98 Re: Cantor's Diagonal Proof: FLAWED! . . . . . . . . sci.math 20nov98 Re: Why the attack on Cantor's Theory? . . . . . . . . sci.math 27feb99 Re: Why the attack on Cantor ? . . . . . . . . . . . . . . . sci.math 1mar99 Compare N and 2^N (Peano Cantor) via Z and 2^Z in group Z! . . . sci.math 12mar99 Re: Cantor's diagonalisation method and the naturals . . . . . sci.math 15apr99 Re: Cantor's diagonalisation method and the naturals . . . . . sci.math 14apr99 Re: A Loophole In Cantor's Argument? . . . . . sci.math 15apr99 Re: Equivalency of Infinite Sets, and 'countable' has one generator? . . . sci.math 7jun99 Re: Why Cantor Was Wrong . . . . . . . . . . sci.math 20jul99 xxxxxxxxxxxxxxxxxxxxxxxxxxxx1.1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Re: Does the set of all sets exist? . . . sci.math 5oct99 - Cantor's Diagonals generate powerset 2^N by permutations in N! . There are k! > 2^k (k>3) permutations, but not all generate different diagonals. A table like the next (k=6) seems to be very 'prolific': \ 1. 1 0 0 0 0 0 Note: a diagonal entry is not changed if its row 2. 1 1 0 0 0 0 is replaced by a row with the same entry 3. 1 1 1 0 0 0 in that column. E.g: pair swapping involes 4. 1 1 1 1 0 0 4 entries: in rows i,j and cols i,j - 5. 1 1 1 1 1 0 producing a new CD only if the row distance 6. 1 1 1 1 1 1 (symm.difference) \neq 0 there. \ Let us call this the 'Normal Binary k_table': NB_k. If 'weight' r(i) is the number of 1's in row i, rank and R(r) the set of all k_strings of weight r, then symmetric analysis would require to generate all 'ranks' S(r) for w=0..k. E.g. swap rows (2,3): CD= 0 0 1 0 0 0 or if i 1 1 1 0 0 0 1 0 0 0 0 0 --> CD= 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 \ ...etc: Now each binary string is a sequence of 'clusters' of adjacent 1's, separated by zero's, and each such 1_cluster of length m is obtained by permuting the corresponding m+1 rows n the NB_k table. For instance with NB_6 generate CD= 0 1 0 1 0 1 by swaps (1,2)(3,4)(5,6). It follows that powerset 2^N can be generated by permutations in symmetric group N! - permuting adjacent rows in NB_w, corresponding to the 1_clusters representing each of the subsets of N ...( w=|N|, where N is Peano's countably infinite set of naturals, generated by iterating +1: the rows of NB_w). ---------------------------------------------------------------------- N.G. du Bois . . . . sci.math (05 Oct 1999) > >Hi everyone, I have a question: > Does the set of all sets exist? > a. Let us assume R is the set of all sets. > P(R) is the powerset of R, by definition containing all sets. > But when P(R) is a member of R, I immediately can > create a new powerset P'(R) which originally was NOT in R. ..[*] > But then I must conclude that R is not the set of all sets. > > b. Let's assume P(R) is not in R. > Then I must conclude that R is not the set of all sets. > >Does anyone have some idea's about this? - Best regards, Nico du Bois. NB: This kind of contradiction you are guaranteed to get if you stay too 'abstract', or rather: too vague, in your concepts. There is in fact no balance between the syntax and the semantics, meaning (roughly;-) that the abstract concepts are not made 'hard' by some definition of *how* to construct the elements in your argumentation. Like: what is a SET, *how* do you construct a POWERSET (under what conditions can you 'construct' such without running into logical trouble as above?) For instance, the concept of 'powerset' came into being (as far as I know) due to Cantor's work on the cardinality of all subsets of the set of integers (or rather, of all positive integers: the set N of naturals), denoted 2^N because any finite image of it can be constructed by (countable_length) strings over any alphabet of two letters [with an arithmetic interpretation n = \sum 2^{-i} i=1-->inf, being the "reals" between 0 and 1] Now this 'exact' kind of description of a powerset should not be 'immediately' brought into the *much* larger context of the "set" of all sets. Because you have ignored the charcter of the Naturals, as Peano so nicely defined it: being a one_generator set, namely as-it-were: N = 0{+1}* , starting with 0 produce all its successors by "iteration" (or repetition: the star *, which is an intuitive concept, difficult to define more precisely, with the naturals under addition as a model -- equally 'vague' but it seems to work for most, although: N is a one-sided infinity -- starting at 0 -- while the integers Z={-inf .. 0 .. +inf} are a two-sided infinity, which *does* have effect on the number of generators you need "upto iteration", namely N needs one {1}, and Z needs two {-1,+1} ;-) And you know that Cantors's work ignited (and still does ignite) a lot of discussion. The problem *there* is that 2^N, which essentially has the structure of a lattice (with two idempotent operations: set intersection and union -- or: bitwise AND(&) and OR(V), is mapped onto the real line_segment [0,1) which is *asking* for conceptual trouble. Under (&),(V) the lattice 2^N has precisely N generators, arithmetically: the countable set {2^-i} for i=1..inf, or: i \in N, so of "infinite dimension" (because the operators are idempotent: a&a=a, aVa=a for any subset a of N, so the concept of 'iteration' does not exist in a lattice, such as 2^N, hence its enormous infinite generator set N;-) A LINE is 1-dimensional (intuitive: iteration) while 2^N is 2-dimensional, the concept of "dimension" understood as the minimal number of generators necessary for sequential generation of any element of the set in question. So, for instance, any finite (permutation) group G can be embedded (is a subgroup of) a group G_n of ALL n! permutations of a finite set S of n elements -- with dim(G_n)=2, so only 2 generators suffice to generate any 'full' (symmetric) finite group of degree n (viz: permutations of n states). And for infinite sets there is even more NEED for a generative definition, because how *otherwise* do we know what we're talking about? (listing all elements would be impossible, now would'nt it?) Then Peano's set N has dim(N)=1 -- the naturals have one generator under addition (or: sequencing, if you prefer). And upto iteration: 2^N (all binary strings of countable length over alphabet 0,1) has dim(2^N)=2, just as the set S of all strings over some alphabet A of k letters has dim(S_k)=k, of 'order' k^N. For some low-by-the-ground & simple engineer's interpretation of Cantor's diagonal argument, trying to interprete his work as much as possible in a constructive way (just like Cantor's constructive diagonal is: trying to reconcile 1-dim 'iteration' with 2-dim lattice, which CANNOT be done, they are different data-types! ) see http://home.iae.nl/users/benschop/cantor.htm Essentially, if you would want to go beyond Peano's N= 0{+1}* and Cantor's 2^N = A* over A={0,1} -- with or without arithmetic interpretation as "reals" -- I think it is wise to introduce some concept of "data-type" sothat one is NOT tricked into mapping a (multi-dimensional) lattice onto some vague "dense linear" medium as the "reals", where the concept of generator is ver te zoeken, taking off in-a-tangent & escaping into infinities unrepresentable (not even "upto iteration"...;-( Ciao, Nico Benschop - http://home.iae.nl/users/benschop http://home.iae.nl/users/benschop/finite.htm  Re: -- Naturals N={1}* vs unNaturals 2^N={0,1}* (Peano/Cantor) Subject: Re: -- Naturals N={1}* vs unNaturals 2^N={0,1}* (Peano/Cantor) sci.math: 8 Oct 1999 (Math Forum) ---- Fred W. Helenius wrote: > > benschop@iae.nl (Nico Benschop) wrote: > > [much snipped] > > > And in the infinite case > > of all N! permutations group G_N = {a,b,c}* with ...[#] > > with a= +1, b= -1, c= [swap(0,1) rest fixed] > >as shown earlier in > > http://home.iae.nl/users/benschop/cantor.htm ...[&] > > I presume you mean Z rather than N, since "-1" (which I understand > you intend to mean the map taking n to n-1) is not a function from > N to N. If so, what combination of those generators produces the > map that takes n to -n? > > I've pointed out before that, using conventional definitions, a > finite number of generators produces only a countable number of ..[%] > elements. > You have suggested that you can avoid this problem by defining > infinite products. I offer the question above so you can > see if you can find a reasonable definition that will make some > infinite product yield the map taking n to -n. If you can do > that, please try to show that your infinite products will produce > all of the permutations of Z. > -- Fred W. Helenius Re[#]: that should be G_Z indeed. As explained in [&]: N=0{+1}* is not a group, but Z=0{-1,+1}* is a group, where indeed -1 is necessary as separate generator since it is not in N. Re[%]: I never quite understood that a UC (uncountable) set like 2^N requires a UC set of generators. But I guess I understand what is meant: it's a matter of definition what "generator" means. In group theory, for instance, a cyclic group G = g* is meant to be the collection (set) of all iterations of some generator g under sequencing (sequential function composition), often noted as {g, g^2, g^3, ...} in some "multiplicative" notation. Also: N = {+1}* iss meant to have just one generator, namely '1' under addition, or repetition if you like: the set of strings of increasing lengths: {1, 11, 111, 1111, 11111, ... } written as set N, usually deonted as: {1, 2, 3, 4, 5, ... } having just _one generator_ "1" under addition (resp union). Now Cantor's set 2^N of all subsets of N: here the elements of N are represented for instance in binary code, as strings over {0,1} with the arithmetic interpretation of reals on interval [0,1) . It was my understanding that this 2^N is a Boolean lattice under union and intersection, which qua 0/1-strings can be represented by "bitwise" OR and AND. For instance in the simple finite case of 3-bit code: {0,1,2,3,4,5,6,7}={000,001,010,011,100,101,110,111} we have a 4-layer lattice, representing the 2^3 subsets involved: 111 110 101 011 001 010 100 <--- N_3 set of generators under (V) union 000 with the usual inclusion relation, like 010 < 110, and 010 < 011. The set of "singletons" N_3 (strings with one '1', rest 0) is a generating set under union, which is undersood as "up to repetition" like: 111 can be reached upon repeated union of elements from N_3, although indeed this requires two steps, such as 111 = (001 V 010) V 100. I guess that you mean with "conventional definitions" that this _up to repetition_ does not hold in the established Cantor theory. In that case there's a misunderstanding on my part ;-( In other area's of math (like group theory, and associative algebra of strings cq function composition) the concept of "generator" _does_ by definition mean: _upto iteration_ (or: upto repetition). Otherwise the whole concept of generator is rather empty... So in _that_ interpretation: N as set of singletons (all strings with a single 1, rest 0) _is_ a generator under union (bitwise OR) of 2^N, hence the countable set N generates the uncountable set 2^N of all binary strings of countable length. I hope you understand me now? Further comments, more about the essence of my proposal to shift emphasis from cardinality of the closure towards cardinality of a minimal generating set, please. Ciao, Nico Benschop - http://home.iae.nl/users/benschop/seqdim.htm http://home.iae.nl/users/benschop/cantor.htm Subject: Re: Prove all real numbers aren't rational (sci.math 21sep01) ------- Michael Abbott wrote: > > Nico Benschop wrote: > > > "Dik T. Winter" wrote: > >> > >> No. Contrariwise, you can prove that only countably many > >> irrationals can be constructed. The number of constructable > >> reals is countable. -- dik t. winter > > > > Just what I suspected;-) -- NB > >Uh. >This depends somewhat on how strict your notion of "constructible" >is, I think. To be more precise, the set of reals that can be >described by a finite (necessarily non terminating) computation is >clearly countable, as the set of possible programs is countable. >However, the set of "all" reals surely remains uncountable? Possibly here: "constructible" is equivalent to "countable";-) Cantor's uncountable reals R on [0,1) are an abstract concept, shown to not be (Peano-) 'countable', via his diagonal argument. They are hardly 'numbers' in the realistic/computable sense, but abstract entities satisfying certain arithmetic-like syntax rules. So they rather belong to the broad category of 'languages & data structures'. AFAIK considering them as 'elements', or 'real numbers', on a linear number-line breeds at lot of confusion. Not so much their cardinality ('amount' of reals;-) but their generation in a closed system R(+,*) with arithmetic & sequencing properties distinquishes them from Peano's naturals N(+) with one generator: 1 under (+), eqv. to iterating the 'successor FUNCTION'... This is not true for the reals R on [0,1) -- which map into Z! the group of all permutations of the integers Z, with 2 generators. These again map into the semigroup Z^Z of all transformations of Z, with 3 generators = all FUNCTIONS: Z --> Z (closing the Peano circle;-) -- NB -- http://home.iae.nl.users/benschop/cantor.htm */ism.htm */func.htm