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. How diagonal is Cantor's diagonal ? . . . (NFB: sci.math, 10jun98)
A super_exponential 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 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 _ _ _ mk + 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
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
-- Now add all missing strings to the list, which thus expands to
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
For me Cantor's proof is charming and seemingly very detailed. It's
dynamic interpretation xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Cantor Diagonal : Successive Naturals in Binary matrix, & Permute Rows[** 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
Recall Newton's iteration process to approach a root of a polynomial, sometimes
called
In Cantor's case the two alternatives are: 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,
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
Define for any natural base b>1: . . . b#{r+1} = b^(b#r)
This definition of
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>, Re: A Loophole In Cantor's Argument? (sci.math 15apr99) From: Nico Benschop 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 ;-) Cantor.htmwork.htm "Constant Rank State Machine structure". . . Comments are welcome --- Ciao, Nico Benschop.
Re: Does the set of all sets exist? . . . sci.math 5oct99 15feb02 - Re: Problem with Cantor's diagonal argument - 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 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 |