* Volker to Kevin (nonrepeating decimals) Kevin > My question is whether there really is such a thing as an infinite > nonrepeating decimal? Personally, I have never seen one. Of course there is: 0.1 01 001 0001 00001 000001 0000001 ..... etc etc it sure is not repeating, and sure is not a rational number regards Volker * Kevin to Volker Volker, The challenge is to write a computer program that will print that number for perpetuity. The algorithm seems easy, we can write 1 followed by n zeros. In BASIC this can be done with an infinite loop. n = 0 Loop n+=1 print 1 for x = 1 to n print 0 next Repeat Can this go on for ever? We are limited by the size of n. Is n an integer, a double integer? The length of the decimal I am printing is determined by the value of n. Once that is reached, the computer crashes or starts to repeat. << it sure is not repeating, and sure is not a rational number >> I agree. It will not repeat. The algorythm is not rational. But is it infinite? There is no way to create an infinite nonrepeating decimal with finite logic. The only way to create an infinite non-repeating decimal is by using an infinite logic (whatever that may be). This means that in order to use infinite non-repeating decimal in a proof, you have to have made some type of assumption about the nature of infinity to create an infinite logic. That means that your assumption will come back up in some form or another in any proofs you make using infinite decimals. kd * Kevin to Volker Volker, << Well, you lost me here - what is "completed infinity"? >> I am failing you again. I thought had a nice quote translated into English in which Georg Cantor spoke of a diffence between the complete infinite and something which was undetermined or unbounded, or some sort of thing. I could have sworn also that I had a quote inwhich David Hilbert used the term "completed infinity." I looked through my books and couldn't find them straight off. Here's some quotes from Morris Kline in "Mathematics the Loss of Certainty" p.199 "... Cantor regarded infinite sets as totalities, as entities that can be considered by the human mind, he broke with long standing judgement. From Artistotle onward, mathematicians had made a distiction between actual infinity and objects and a potential infinity..." p.203 "Henri Poincare thought the theory of infinite sets a grave malady and pathologic. 'Later generations,' he said in 1908, 'will regard set theory as a disease from which one has recovered.' ..." I will try to show what I mean by completed infinity. I already spoke about doing the diagonal method on sets of permutations. Following are all of the permutations which can be made from a two character alphabet which is three characters long: 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 There are 2^3 elements in this set. Taking any diagonal segment of any portion of this set and converting the 1s to 0s and 0s to 1s will produce a number which is not crossed by the diagonal, but which is a member of the set. For example the diagonal starting in the upper left hand corner is (1,0,1). The Diagonal Product DP(1,0,1) is (0,1,0) which is a member of the set of possible permutations, but not a member of set of permutations crossed by the diagonal. For a finite set of permutations, the diagonal method shows that the set of permutations is greater than the number of permutations crossed by a diagonal. The set of permutations is wider than it is deep. 2^n > n for n > 1. Only when infinity is complete does the diagonal proof show that the Reals are not countable. The diagonal proof is the same for repeating decimals, Rationals, up until the completed infinity when Cantor makes the distinction that the Real Numbers are transfinite and the Rationals are not. The whole theory is full of these wonderful things that happen when infinity is complete. The power set of the Natural Numbers is transfinite when infinity is complete, while the power set of a set of Natural Numbers with n members has 2^n members when n if finite. Another example. Let's say I spend my life matching the natural numbers to all multiples of 1/2, with the mapping n --> n/2. If I start at 1. I would have as mapping that looks like this: 1 2 3 4 5 ... n ... 1/2 1 3/2 2 3/2 ... n/2 ... Now, for any value of n, I can prove that my list of multiples of 1/2 is incomplete because I can always point to a number not yet in my mapping - Namely n. Clearly n is a member of the set of multiples of 1/2, but at any given point in my ordering n is not in my listing. Only with n = infinity (the completed infinity) is n in both the set of natural numbers and the ordered list of halves. Still not convinced. Okay, let's say I am writing out a list of the postive rational numbers. since Rational numbers are denumerable, this should be possible. Well, at any point during my list, I can point to a number not yet on my list, namely, the sum of all of the numbers I have so far listed. Since Addition is closed under addition, this number should be a Rational number, it should also be bigger than the biggest number in my list. When infinity is completed, suddenly the sum of all of the rational numbers is no longer a member of the Rational numbers. Likewise n + 1, where n is a natural number, is a natural number. Suddenly, when infinity is complete it is a transfinite number. If you do not accept the idea of a complete infinity then the rational numbers are no longer denumerable, the set of positive even numbers is smaller than the Natural Numbers. With a little work on definitions, the entire system is consistent. The only really big problem is that Calculus based on limit theory no longer works, because you cannot define a continuous dense neighborhood for (x,f(x)). Now if you had an algebraic approach to the Calculus, then math would be happy and whole again. You could even use limits as a convenient tool for estimating the derivative. kd * Lynn to Kevin You have seen plenty of irrational numbers. Look at anything square; the diagonal / side ratio is irrational. The confusion comes when you try to *represent* irrationals in decimal form. What we get is just an example of the inadequacy of the decimal notation to describe the beasts. Computers are of little help: they don't even do arithmetic very well, and the only way you can describe a transcendental number to a computer is as a *function* of the rationals. We don't really have much trouble with the concept, only with its representation. Lynn * Ian to all (4 number problem) All, This is my first message here, so appologies if this is not an appropriate place/question. My brother is currently giving this question to the kids he teaches (my phrasing): "Imagine a square with integers at each of the corners. Construct another square which has the modulus of the difference of the numbers. Repeat until you reach (0,0,0,0). The number of iterations is the 'size' of the initial four numbers. Find values with a 'size' of 10." I've probably expressed this badly, so here's an example. The notation I will use is to give the four values of the square starting at the top left-hand corner and working clockwise, thus: (1,2,3,4) -> (1,1,1,3) -> (0,0,2,2) -> (0,2,0,2) -> (2,2,2,2) -> (0,0,0,0) So size(1,2,3,4) = 6. Obviously it *is* possible to generate a 'size' of 10, but the purpose of the question is to get the kids thinking (they are 8-year-olds). The questions he (and I) would like to know the answers to are: (i) is it possible to calculate 'size' simply? (ie without applying the above rules)? (ii) is there an upper bound given either a maximum sum for the four numbers or a maximum value for any of the initial integers? So far I've only noticed obvious things, like: it's possible to define a 'normalised' form for the numbers where one of the four values is zero and the rest have no common factors. Hope you find this interesting, Ian * Kevin to Mike (calculus, truth and beauty) Mike, You caught me in yet another typographical error. Yes, g(x) = f(x) - f'(x)x. The way it works is that f'(x) is the equation for the slope of the line tangent to f(x). g(x) is the equation for the y-intercept of the tangent. Let's say that the line y = mx + c is tangent to y = f(x) at point p. In that case p would be a double root of the equation f(x) - mx - c = 0. (i.e. it could be divided evenly by (x - p)^2.) Well, m = f'(p) and c = g(p); So f(x) - f'(p)x - g(p) = 0 will be divisible by (x - p)^2. I haven't seen this technique in any books or magazines. I came up with it 10 years ago when I came up with the technique used in ALGCLC.ZIP, which i haven't seen in any books or magazines either for that matter. kd * Marten to all (a problem in statistics) I work as research assistant for a Professor for whom I am trying to determine the size of the bias of a single index cut-off point for malnutrition that is used by the UN Food and Agricultural Organization (FAO). The problem is the following: I need to pick suitable distributions for calorie intake in the population. This is going to be a bivariate distribution. The first dimension of calorie intake is that spent on physical activity - the physical activity level (PAL); those below a certain cut-off point are deemed undernourished by the FAO in that they are not consuming enough calories consistent (in a probabilistic sense) with healthy economic activity. The other dimension is the basal metabolic rate (BMR) that is a function of the minimum body weight consistent with health. Both are thus measured in calories. Since data in these countries is notoriously unreliable, I want to get an idea of the bias of using the FAO's single calorie cut-off point by looking at different distributions. I would very much appreciate getting some advise on which bivariate distribution functions to try. Naturally, I am going to try the Gaussian, but I also want to look at skewed distributions to see what effect this has. I don't want to consider higher moments than the third, as I am agnostic about how they should look. Also, I would like to try at least one distribution with a closed form after integration, so that I can calculate explicitly how the bias is affected by the covariance matrix. Of course, the direction of the bias is obvious in this instance, but it would be nice to get an explicit relation for at least one distribution. So what suitable distributions close to the Gaussian shape have a closed form? I seem to recall that the logistic d.f.n. has this property, but I don't recall exactly. Which computer program might be good for this kind of exercise? I looked into the manual for Mathematica, but it does not seem to have a built in bivariate Gaussian, only the one dimensional. I have access to a number of other packages, and would appreciate any advise on this point as well. TIA, Marten * Ed to Marten Marten, Our company has a program called The Risk Master which may or may not be of help, but I thought I'd mention it. We use it for electronics analysis to estimate probabilities of failure. You type in an equation of interest, the the program asks you to define the variables, including the probability distributions. It allows you to quickly 'sketch' the distribution you want. After entering the data, the program gives you the min/max results, and a probability plot of the distribution of the results. Since the program uses an estimating algorithm, it may not be precise enough for your needs, but we find it very useful. If you're interested let me know and I'll mail you some data. -Ed * Ron to Michael (MathCad and iterations) Mike: You'll find that the 'Advanced Math Handbook' also uses the implied matrix method by using indexes. Anytime you use indexes to create multiple solutions, you create at least one matrix in memory. You will have the flexibility of playing around with partition sizes (h) in the Runge-Kutta method just as you do with a calculator. I want to emphasize something here. MathCad does *NOT* have a built-in solver for ODE's. The 'Advanced Math Handbook' illustrates *HOW TO* use familiar methods to solve first and second order ODE's by using matrices to create the successive solutions from initial values at y(0). You must cut and paste from the examples or create your own set of instructions to get the results you want for your problems. Maple, on the other hand, *DOES* have built-in ODE solvers, symbolic and numeric. ...Ron * Sumedha to Marten Have you tried the software S-Plus ? You will need to prepare short macro or program to use the software to fit your needs. * Glenn to all (greatest common divisor) Question, Is there a formula to determine the greastest Common Divisor for a set of numbers? I am trying to write a program that will accomplish this & need the formula, if one exists. Thank you, Glenn * To Glenn There is a formula for the gcd of two numbers a and b only if you know their prime factors, which is very difficult for large numbers. For calculating the gcd one uses the Euclidean algorithm, which can be programmed as follows in C: int mcd (int a, int b, int *D) {int r; if (a<0) a=-a; if (b> I put the subsets containing 1 member in the 1st row of a table, those containing 2 in the 2nd, etc. Where do you put the subsets containing an infinite number of elements -- and how long is that row or rows? * Kevin to me and to Bill Bill & Josef, The first list starts with the null set. At any finite point where you stop the mapping the list will only include finite sets. When the list is taken to infinity, it will have infinite sets. A second list starts with the set of all Natural Numbers - {N}. The second member of it has all sets in {N} except those in the second member of the first list. This list contains only infinite sets. A third list contains these first two lists shuffled together. kd * Kevin to Bill (defending his power set) Bill, I should have added a line to include all sets that Mr. Snyder names, and incorporate it in the proof. Let's skip to the end of the debate. You will end up taking a diagonal of my list and saying that the set of all sets not in the diagaonal is not in the list. I'll add a new series which is the diagonal product of all previous lists. I will incorporated it in the proof so that every other member is a diagonal product. We now have an interesting version of the Russell paradox. You will say that's not fair. I'll concur, then point at the first list and say that you just showed that the method used to show that the Rational Numbers are denumerable is insufficient. It can't work for one set and not for others. This will put us at a new point. The Rational Numbers are no longer denumerable. kd * Lou to Kevin > When the list is taken to infinity, it will have infinite sets. Not so. Given any subset of N, you must be able to point to a row that subset is on, or you haven't succeeded in doing what you say you have done. * Bill to Kevin No, if you insist on skipping to the end of the debate, I'll resolve any & all paradoxes by drawling, "Whut we got here is failure to c'municate..." and whacking you over the head with a club. Let's take our time and dot the i's and cross the t's instead. Not having seen your "proof" yet or being able to derive it from your brief description, I will simply have to say for the time being that I don't believe for a moment that there is any paradox. The talk about 'lists' of subsets is a tipoff that you are assuming your conclusion in one way or another. When examined closely, that list of infinite subsets is going to turn out to be either too incomplete to serve your purpose, or not a 'list' -- i.e. not denumerable -- in the first place. * Bill to Kevin OK, I've looked over your file now. Your mapping's domain is the union of a) the set of finite subsets of the natural numbers, and b) the set of all complements of finite subsets of the natural numbers. You set out to prove that this set is countable. I only glanced at your construction method, since its validity or lack of it is not the issue; the union you are working with is indeed countable, whether you've correctly proven it or not. But you haven't proved that this union is the power set of the natural numbers. And of course you can't, because it isn't. Your method does not map any infinite set whose complement is also infinite -- as you can easily see if you try to specify the row in which, say, "the set of all odd natural numbers" falls. * Kevin to all (a new diagonal proof) Hi, I apologize to those who don't want to download this, but I just finished a new article concerning the diagonal proof, that some people might want to see. I propose two sequences: The first member of the first sequence is .10101... All following members are produced by taking a diagonal product of the preceding numbers, then finishing with the remaining digits of the first number. I list the numbers from top to bottom. The sequence looks like this: 0 0 0 0 0 0 . . . . . . 1 0 0 0 0 0 ... 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 ... The number on the diagonal is .10101... The diagonal proof will always produce a number not yet in the series. So the series is not denumerable. All of the members in the series but the last are rational numbers. My second series is the same as the first, except the first number in the sequence is 1. All others are generated by taking the diagonal of preceding members. If the diagonal does not exist, the digit is 0: 1 0 0 0 0 0 . . . . . . 0 1 1 1 1 1 ... 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 ... Once again, the diagonal proof will create a number that is not yet in the list, indicating that it is not denumerable. A twist, all of the numbers terminate in repeating zeros, so they are Rational. If infinity is completed, the last number would be a 0.111111 = 1 (in binary) which is the first number. thank you. kd * Gerald to ... (the sci.math newsgroup) * can anyone tell me the full address of the usenet newsgroup sci.math? Newsgroups do not have "addresses". The full name of the newsgroup is "sci.math". When you access the newsgroups (on my Unix machine, I use trn for this) go to newsgroup "sci.math". With trn, the command is "g sci.math". As far as I know, it is not (yet) possible to access such newsgroups directly from CompuServe. * Kevin to Bill Bill & Lou, I gave some thought to your arguments. Imagine first that I perform the mapping on a set of Natural Numbers of an arbitrary size n. I can easily find the precise location of any set, such as the complement of the diagonal, the set of even numbers, the set of all numbers, or any set describe in terms of the entire set. The trick is that I have to describe the location in terms of n. For example, the set of all numbers would be 2^n. The set of even numbers would be at a position such as (n/2)^2-3n. I can describe with absolute precision any set defined in terms of the total set. Now, if n is infinite, I can still describe the location of any infinite set of Naturals so long as I write the position in terms of n. The set of all naturals would be in position 2^n, the set of evens would be at (n/2)^2-3n, etc. The first mapping is complete. I didn't need to include that second mapping with the complements of the first set. kd PS speaking of the set of all Natural numbers, I was wondering if you had a program that could write a computer program to print the set? * To Kevin (Cantor's second diagonal argument) Kevin, There is a diagonal proof which shows that the power set of the set N of natural numbers is not countable. Suppose that A(0),A(1),A(2),... is a complete countable list of all subsets of N. Whe shall find a subset B of N which is not an element of this list. In order to define any subset B of N we must specify for each natural number n if it belongs to B or not. Now for our B we agree that n belongs to B if and only if n doesn't belong to A(n). But then certainly B is different from each A(n). In set theory this is called Cantor's second diagonal argument, it was used by him precisely to show that uncountable sets exist. If you try to repeat the proof above using the characteristic functions (in this case sequences) of the sets we considered, i.e., the sequences whose n-th element is 1 if n belongs to the set, and 0 if it doesn't, and then think of any such sequence as of the (essentially unique) 2-adic representation of a real number contained in the unit interval, you obtain Cantor's proof that the set of real numbers is not countable. Your diagonal argument, by which one shows that a set is countable, is called Cantor's first diagonal argument. Josef * To Glenn What I said about a = s*b + c holds any time, if such an equation is true, for a,s,b,c integers. In the Euclidean algorithm, with a>b>0 (after a change of sign, if necessary) you shall choose s as the integer quotient of a by b and c as the remainder (if a=360 and b=84, you will take s=4 and c=24). In this way the couple (b,c) is smaller than the couple (a,b), and after at most a steps (it is easy to see that one can give a better upper bound which involves the golden section or the Fibonacci numbers, see P.S.) the algorithm shall come to an end. There should be no difficulty with the simple C-function I indicated. Perhaps your compiler requires the older style declaration of parameters, try int gcd (a,b,D) int a,b,*D; {...} instead of int gcd (int a, int b, int *D) {...} Josef P.S. The worst case is, you may agree, the following, if we begin from the end: 2=2*1 3=1*2+1 5=1*3+2 8=1*5+3 13=1*8+5 ... The numbers 1,1,2,3,5,8,13,21,34,55,89,... are the famous Fibonacci numbers. If F(n) is the n-th one, then one shows that F(n+1)/F(n) tends to the limit g=(1+sqrt(5))/2, and this is the golden section, which you obtain if you divide a line segment of length 1 into two pieces of lengths x and 1-x in such a way that 1:x = x:(1-x) and then define g as the common value of this ratio. There is a nice and not expensive booklet on elementary number theory (in fact there are many more, but this one is especially quick to read and paying): C. Ogilvy/J. Anderson: Excursions in number theory. Dover 1988, 170p. 0-486-25778-9. $6. Continued fractions are among the most mysterious concepts in mathematics, they are easy to begin with (being practically exactly equivalent to the Euclidean algorithm, if you use a good notation), but imagine that there is a theorem that says that every solution of a quadratic equation with integer coefficients can be calculated (very quickly) by a periodic infinite continued fraction (and viceversa), but nobody knows the continued fraction of the third root of 2 or any other cubic irrational! * Bob to Mike (on Marilyn's walking problem) Great stuff, Mike. Appreciate your taking time to share it with us. I enjoy Marilyn's column for the most part although every now and then I get the impression she deliberately clouds her explanations to encourage more people to write that she can "correct." e.g., the 3 doors problem which I think is easier to understand than she explains. I am a little concerned that not two weeks after she published bogus criticism of FLT she had a problem that she analyzed completely incorrectly. Thanks also for the new word. Bob * Donald to Mike (a high IQ) <<> I agree strongly with A & disagree strongly with B. I think her criticisms are excellent for a layman. Her recounting of history is fine. I fit in her niche (high IQ, interest in math, career in another field so only college level formal education in math). My IQ might well be as high as her (measurement above 170 or so is guesswork) so I can relate to her POV. And her book was fun & informative for a VERY niche audience likely to buy it (a few math majors & Mensans). Note that she never says FLT proof/Wiles is false. Also note the proof is possibly flawed/false & certainly not proven. All of her caveats may in fact be actual proof problems. And they may not. And she says so. Graduate math work or at least majoring is required for good familiarity with non- Euclidean geometry so its a nice intro. The biggest problem for me with the book (and it was a small one) was that people unfamiliar with her were not explicitly told where she was coming from (ie a smart layman learning details about FLT for the first time, not a career number theorist or even mathematician). The whole I-Net post sounded like a nonsocial grumpy career math wierdo with no lay friends-- the book after all never remotely claims to be an actual academic challenge to the proof, nor MOST IMPORTANTLY does she ever say she feels FLT is not yet proven. It is a thought provoker, & an attempted boon to her syndication claim (highest IQ). All IMO. Don * Kevin to me josef, << Now for our B we agree that n belongs to B if and only if n doesn't belong to A(n). >> Like the diagonal proof on the Reals, all this proves is that the list of power sets is wider than it is deep. I can show you exactly where in my list you can find the set B. I have to define the position in terms of n where n is the size of the set of Natural Numbers. B will be in a position greater than n such as 2n-1. The mapping is complete. To find a position of a member that is defined on the set of all natural numbers, I will not be able to tell you the position in relation to 1 but in relation to n (The total number of members of the Natural Numbers.) Perform the diagonal method on power set of the first 8 Naturals. The set B will be a member of the set, but it will not be among the first 8 subsets. If you calculate B on a set is of arbitrary length, the position of B can only be defined in terms of n. You will be able to find B for any arbitrary size of n. Its position will always be greater than n. Another way to look at B is as an algorithm. For any B(n) where n is a finite number, I can show you the exact location of B(n) in my proof. I can create an algorithm to describe the location of B(n) for any arbitrarily large value of n. I am willing to accept your assertion that the Power Set is not denumerable. Here is a problem you have to resolve. Cantor proved that the Rationals are denumerable by placing them in a table and asserting that the table is denumerable. I placed the power set in a table in the same manner, yet you say it is not denumerable. This means that Cantor never proved that the Rationals are denumerable! A universal proof can't simply work on Monday and not on Tuesday. kd * Volker to Kevin Kevin, one simple question - When will you enlight us with a proof that a circle can be squared with compass and ruler, using the classical geometric construction? I do perhaps repeat myself - but you should take your time and learn a little bit more about the things you are talking about, otherwise you run a very high danger of making yourself ridiculous. Perhaps I am wrong, but I have the serious suspicion that you never understood the method (and the relevance) of the diagonal proof .... . So, PLEASE, get yourself a couple of books on modern analysis - or, better yet, study a few years of mathematics at any decent university. (It sure does help in arguments like this ) If you deny the validity of any method of proving something - that's fine with me - there even is a "faction" among mathematicians which do not allow for a "tertium non datur" proof, but you have to come up with VERY SOUND reasoning - which I sometimes cannot find in your posts (especially concerning the set of all subsets of N). BTW, the subset of all primes, where do you find it in your table? regards Volker Bandke Germany * Bill to Kevin >> The mapping is complete. To find a position of a member that is defined on the set of all natural numbers, I will not be able to tell you the position in relation to 1 but in relation to n (The total number of members of the Natural Numbers.) Your second sentence contradicts the first. To prove a set is countable, you must prove the existence of a 1-1 mapping >> into the natural numbers <<. You don't have such a mapping. If I pick an arbitrary subset of the power set of the natural numbers, e.g. the set of all multiples of 37, you cannot tell me where it appears in your table. The reason you can't is very simple: it *doesn't* appear in your table. Given an arbitrary element of the (putative) domain of your mapping, you must be able to guarantee that there exists a specific natural number which is the image of that element, (or an upper bound on the image, which as best I remember is the formal requirement). And you can't. The best you can do is mumble about infinite cardinals. Cantor's table and diagonal traversal meet this requirement. Given any specific rational, one can say in essence, "Yes, this particular rational DOES have an image in the natural numbers under this mapping, a natural number <= K, for it clearly will be mapped at or before the Kth step." It is not possible to do likewise for an arbitrary subset of the natural numbers in your construction. The domain of Cantor's mapping is *all* the rationals; the domain of your mapping is only a *countable subset* of the power set of the naturals. * Kevin to all (on (x+y)^a/b) hi, I can expand (x + y)^2 = x^2 + 2xy + x^2. Is there any way to expand (x + y)^(1/3)? Or the general formula (x + y)^(a/b)? kd * Kevin to Bill Bill, I can tell you exactly where the set of all multiples of 37 are. Only I have to say it in relation to n, where n is total number of Natural Numbers. If you perform an operation on the whole set, the only way to the result in in relation to the whole set. The same is true of the Rationals. If I ask the location of a number defined in relation to the whole set, you can only tell me the position in relation to the whole. I realized after your postings that I need to make some modifications to PowSet.Txt to make this clear; so I am removing it from the Library. If any one is interested in seeing the revisions please let me know. kd * Bill to Kevin Likely this is where I should start quoting Strother Martin on gettin' your mind right, and reaching for my billy club, but what the heck, let's try it one more time... What you say about specifying location "in relation to..." the whole set simply isn't so. That is *not* the way it's done in a real proof. And it makes the critical difference between the construction of the rationals and your own construction, the difference between *proving* that the constructed mapping is a 1-1 correspondence defined over the entire set allegedly being proved countable, and simply *saying* that it is because a) you want it to be, and/or b) you don't understand the requirements for proving countability. With the matrix/diagonal construction of the rationals, one can prove -- not claim, but *prove* -- that *every* rational has an image in the natural numbers -- in the intuitive, everyday sense of corresponding to an ORDINARY, FINITE counting number. That is *required* to show that the mapping does indeed "cover the ground." It is *not* legitimate to talk about position or image in terms of the cardinality of the rationals or the reals, as though you could look into the matrix and actually locate "row aleph-0 - 5," then run your finger along that row until you hit "column aleph-0 * 50 + 3." Let's approach this from another angle. Here is the standard tabular/diagonal method of proving that the countable union of countable sets is countable: 1) By assumption, the union itself is countable. I.e. we can associate with each individual set S in the union a specific, unique natural number _i_. So we may validly denote the sets as S1, S2, S3 ... Sn, Sn+1..., and the union as (Union over i) Si. 2) By assumption, each individual Si is countable, i.e. given an arbitrary Si in the union, we may associate with any arbitrary element x of Si a specific, unique rational number _j_. Thus we may validly denote the first element of S1 as S1-1 (where the dash separates the halves of a dual subscript), the fifth element of S19 as S19-5, etc. 3) Lay out the sets and elements as a matrix, where the first portion of the subscript denotes the row and the second the column, e.g. S17-3 is in the 17th row, 3rd column. Construct a mapping from this matrix into the natural numbers by counting along the minor diagonals of the matrix. Skip over any element which has already been mapped. Assuming the first few elements are unique, and letting "->" denote "maps into," we get: S1-1 -> 1, S1-2 -> 2, S2-1 -> 3, S1-3 -> 4, S2-2 -> 5, S3-1 -> 6,... 4) So far, this looks like your "proof." Now here comes the one where a *real* proof by this technique stands up, and yours falls on its face. Given any arbitrary element in the union, we can *PROVE* that it maps into a natural number. No invoking the cardinality of the naturals, we can -- and *must* if the proof is to be valid -- show that it occupies SPECIFIC, FINITE coordinates in the matrix, and accordingly that its image falls within a bounded subset of the naturals. If X is an arbitrary element in the union, it belongs to at least one Sj. Since Sj is countable, X may be said to occupy some specific position, k, in the counting scheme for that set. Then X appears in the matrix at row j, column k. Note that I did *NOT* drag in any doubletalk about the total number of elements in the union: j and k are ordinary natural numbers. Let m be the maximum of j and k. Then X is within the box with corners at (1,1), (1,m), (m,1), and (m,m). Since there are m^2 elements in this box, the image of X is a natural number <= m^2. That is, by the time we have counted up to m^2, we have counted every element in that box (and possibly more, since all elements may not be unique). Again, *nothing* about the total size of the union; I must show -- and I have shown -- shown that ANY ARBITRARY X IN THE UNION DOES MAP INTO A NATURAL NUMBER. You have *not* proven the corresponding result for your table -- you have not shown that every member of the power set appears in the table in a position which can be assigned a finite upper bound on the coordinates, and accordingly must get mapped into an ORDINARY, FINITE COUNTING NUMBER. You have merely claimed it. And claiming it to be true is all you can do: you can't prove it, because it isn't so. * Bill to Kevin Correction -- >> Let m be the maximum of j and k. Then X is within the box with corners >> at (1,1), (1,m), (m,1), and (m,m). Since there are m^2 elements in >> this box... Aaarrrggghhh, I can't believe I said that. Of course the matrix is "scanned" by triangles, not squares. Make that the triangle with corners at (1,1), (1,2m), and (2m,1), containing 2m^2 elements. * Kevin to me josef, << In order to define any subset B of N we must specify for each natural number n if it belongs to B or not. Now for our B we agree that n belongs to B if and only if n doesn't belong to A(n). But then certainly B is different from each A(n) >> Here's an interesting set. The first element is {}. All other elements are produced by performing this diagonal test on all previous sets in the list. The first set in the set is {}. Since this does not contain the number 1, the second set would be {1}. Since the first set does not contain 1 and the second does not contain 2, the third set is {1,2}. The nth set is {1,2,3...n} 1 {} 2 {1} 3 {1,2} 4 {1,2,3} 5 {1,2,3,4} ... n {1,2,3,4, ... ,n} Since the diagonal test will produce a number not yet in the list, this set is not denumerable. The set of all Numbers less than n is not denumerable! kd * Steven to Kevin Look up THE BINOMIAL THEOREM (for real exponents) in a college algebra textbook. You'll find what you want in that section. Steve * Kevin to Steven Steven, << Look up THE BINOMIAL THEOREM (for real exponents) in a college algebra textbook. >> Could you specify a book? All of the ones I have seen define the binomial expansion only when the exponent is a Natural Number. Right now I am looking at "A First Undergraduate Course in Abstract Algebra" by Hillman/Alexanderson. The following books don't have what I am looking for: In each case the exponent is defined as a Natural Number. Tucker, Alan, "Applied Combinatorics" Ross, Sheldon, "A First Course in Probablity" Hogg, Robert, "Probability and Statistical Inference Rice, John A., "Mathematical Statistics and Data Analysis" I guess I will try to figure it out on my own. I did it once a long time ago, but I remember the math was really hairy. kd PS would you know the answer to (a/b)!, where a and b are Natural numbers and b>1? * Gerald to Kevin * Is there any way to expand (x + y)^(1/3)? Yes, this goes back to Newton. However, when the exponent is not a positive integer, the expansion is an infinite series. (1 + u)^(1/3) = 1 + C(1/3,1)*u + C(1/3,2)*u^2 + C(1/3,3)*u^3 + ... which converges for |u| < 1. The coefficients C(r,k) are defined by: r*(r-1)*(r-2)*...*(r-k+1) C(r,k) = ----------------------------- k! For example C(1/3,1) = 1/3 and C(1/3,2) = -1/9. To expand (x+y)^(1/3), factor out the larger of the two: x^(1/3) * (1 + (y/x))^(1/3), and apply the series above with u = y/x. * Andrew to Kevin Kevin, I have a few responses to your arguments: >> Another way to look at B is as an algorithm. For any B(n) where n is a finite number, I can show you the exact location of B(n) in my proof. I can create an algorithm to describe the location of B(n) for any arbitrarily large value of n. First of all, this would imply that every set in P(N) is recursively enumerable. We all know that there are only denumerably many recursive functions (e.g. recursive sets), and thus you are (by this argument) assuming that P(N) is denumerable - Which is what you're trying to prove. (Note that I have not had the chance to read POWSET.TXT). >> The same is true of the Rationals. If I ask the location of a number defined in relation to the whole set, you can only tell me the position in relation to the whole. Definitely not so. Observe: 1 2 3 4 ... If we look at this crude example, --------------- just follow the path in the table 2| 1 2 6 f(1) = 2/2 | f(2) = 3/2 3| 3 5 f(3) = 2/3 | f(4) = 2/4, etc. 4| 4 ... Given this mapping, and ANY rational number, I can tell you (in a finite amount of time :>) what natural number is mapped to it. >> I can tell you exactly where the set of all multiples of 37 are. Only I have to say it in relation to n, where n is total number of Natural Numbers. If you perform an operation on the whole set, the only way to the result in in relation to the whole set. I'd have to see some hard cardinal numbers to believe that. Anyway, when I was an undergraduate set theory student I assaulted the same windmill. I went about it in a very different manner. Start with Omega. Perform the trivial 1-1 mapping from Omega to Omega+1. Repeat this process. At limit ordinals, compose all of the functions that you have generated thus far (I won't go into the hoops you have to jump through to make sure you can do this!). Stop when you get to Aleph-1. Well, the problem with this is that you would have to take the composition of uncountably many functions to reach the goal! So, all I succeded in proving is that all denumerable ordinals are denumerable :( Well, that's not true, I convinced myself once and for all that P(N) is truly, and I mean truly, uncountable. Besides, Godel believed that |P(N)| = Aleph-17. -Andy * Kevin to Andrew Andy, I don't define the position of the set of evens in terms of Aleph-0. I find the position of an arbitarily large set of evens in terms of an arbitrary large set of Natural Numbers. If I try to write the answer in terms of Aleph-0, I would be assuming Cantor's version of the transfinite in my proof which would leasd to inconsistencies. I have to remove all references to infinity from the proof and replace it with the words a set of "arbitrary length." The results should be consistent with Cauchy. kd * Andrew to Kevin Kevin, But what does "a set of arbitrary length" mean. Is it a reference to an enumeration of the set, or to the cardinality of the set. There is a bit difference between "size" and "length". Also, whichever way you go, if you are refering to a set of arbitrary size OR length, you will have to use transfinite induction. Once you break the Omega/Aleph-1 limit, all bets are off. I'd like to see a current version of POWSET.TXT, if possible. I would like to understand your argument better. -Andy * Lewis to all (a new theorem on polynomials) While it would seem that most everything that needs to be said about polynomials has been said, here is what this writer believes is a new observation. All polynomials of a degree j will have the identical linear recurrence rule. The coefficients of the recurrence rule are binomial coefficients of alternating sign. The polynomial coefficients determine the initial values for the recurrence rule, but have no effect on the recurrence coefficients. For example, a fourth degree polynomial always has the following recurrence rule, no matter what the coefficients are: F(N+1) = 5F(N)-10F(N-1)+10F(N-2)-5F(N-3)+F(N-4) Has anyone seen this result before, and if so, where????? Regards, Bob * To Lewis This is a formula in difference calculus. For a function f(x), where x is a variable, write (Df)(x) := f(x+1)-f(x), and consider this as a new function of x. Then (D...Df)(x) = (sum over k: k=0,...,n)((-1)^(n-k))*C(n,k)*f(x+k), where C(n,k) are the binomial coefficients, if on the left hand side you have the D operator iterated n times. When f is a polynomial of degree d, Df shall have degree d-1, therefore (D...DDf) = 0, if now on the lhs you have iterated D (n+1) times. It is a very old theorem, important however. Josef P.S. Before computers came up, people had much more time to write down things with pencil (or whatever) and paper, so it is rather difficult to find new formulas without bringing in some abstract new point of view. * Lewis to me Josef: Thank you for your post. Forgive my lack of knowledge of this obvious result from finite difference calculus. Your help is much appreciated. Regards, Bob. * Gerald to Lewis Your rule appears in many texts on combinatorics. For example, I would look in CONCRETE MATHEMATICS, by Graham, Knuth, and Patashnik. * Kevin to Gerald Gerald, Thank you Gerald & Steve. This is exactly what I need. I did look in five texts before posting the message, and it was not there. kd This is a strange question, but is there an expansion for (a/b)!? I know the factorial is an integer function, but I was wondering if there was a function like (a^2 + a)/2 which is equivalent to the sum of 1 through a? * Kevin to Andrew Andy, If I get time to rewrite the argument, I will put it up in the library. Before I do so, I want to read all of the references people have given me, and I will also try to force myself to use consistent syntax, and to spell things right. kd * Jon to all (canoe problem) Is there an easy algebraic type formula to solve this problem? I can guess the answer but I'm having trouble coming up with a formula to slove the problem (if it contained different variables).--A boater rents a canoe for 6 hours. He can travel upstream at 2mph and downstream at 4mph. How many miles can the boater go upstream before having to turn around? Jon / CA * Ron to Jon jon: tu = time upstream, td = time downstream, d = distance tu + td = 6 therefore: d/2 + d/4 = 6 3d/4 = 6 d = 8 ...Ron * Oliver to Kevin Methinks you are wrong! Producing a number not on a list does not prove that the set the list is a list of is non-denumerable, unless you can show that the diagonally created number should have been in the set in the first place. In Cantor's argument, by hypothesis the reals are countable, and therefore any number should appear on the list, thus the diagonal argument proves, by r.a.a., that they are uncountable. I think in your case the diagonal argument shows that your sequences do not exhaust the rationals, not that they are non-denumarable. However I only looked quickly at your message so please be polite if I missed the point. Oliver Reid * Kevin to Oliver Oliver, Let's see if I can remember this. One of the sets was the set of the "diagonal product" of all previous members. There are no numbers prior to the first number in the set, so it is zero. The second is 0.1 since there is a zero on the diagonal of the first number and so on. Here is the list: 1 0.0 2 0.10 3 0.110 4 0.1110 5 0.11110 The number on the diagonal will always be 0, the nth term in the list will be 1 - 2^(1-n). All of the numbers appear to be Rational; so I conclude that the mapping is denumerable. If it is, then if I take a diagonal across the entire set, I will produce a number which is _by_definition_ a member of the set, but which is not in the denumeration. This shows that the diagonal test taken in a vacuum is not sufficient to prove that a set is not denumerable. I did the same thing with the diagonal on the power set of the Naturals in a different message. kd * Mike to Kevin > This shows that the diagonal test taken in a vacuum is not sufficient to > prove that a set is not denumerable. Right. It's not the diagonalization per se that proves that the power set of the integers is not denumerable (or that the reals are not denumerable). It's that you hit a contradiction. Let's look at the proof again. Suppose the power set of the integers is denumerable. This means that we can put the power set into a one-one correspondence with the integers. I.e., we can list all of the subsets of the set of integers as S1, S2, ... Now, suppose we can prove that for any such list, we can find a subset of the integers which is not on the list. Then we have proved that the power set is not denumerable since there is no one-one correspondence with the integers. The diagonal method is simply a way of constructing such a set. Obviously, if we define a set S = { n | n integer, n not in Sn } then S must be different from each of the Sn. All of the elements must be present to show that the set is not denumerable. It's not enough to show that S is not in the original list -- we must also show that it should have been in the list. For the power set, this is trivial; obviously S is a subset of the integers. * Steven to Kevin What does (a/b)! mean if a/b is not an integer? Once that question is answered, the rest is easy. Try looking up the GAMMA function to provide you with an answer. Go to the local college MATH library and ask the librarian there. As far as the binomial theorem for real exponents, I said you should go to any COLLEGE ALGEBRA or PRECALCULUS textbook. The books you mention are neither of those. They are combinatorics books. Anyway,as an example you could look on page 585 of BEFORE CALCULUS (2nd Edition) by Louis Leithold, published by Harper and Row. Steve * Kevin to Steven Steve, Thank you. I have seen the Gamma Function before. This property, however, was hidden in the problems at the end of the chapter (I hate when text book writers do that). You have been a great help again. kd * Lynn to Kevin For non-integer arguments, the factorial function maps into the Gamma function, Gamma(1+x) <=> x!. You can find a description of it in any text on statistics, or on the more exotic functions. --- Lynn * Kevin to Lynn Lynn, Thank you. I saw the Gamma distribution in a statistics class. This property of the Gamma function was hidden in the answers at the end of the chapter. kd * Kevin to Mike Mike, << we must also show that it should have been in the list >> The set I described is by definition the set of sets which fail the diagonal test. BY DEFINITION the set generated by the diagonal test on the entire set will be a member of this set. It should be in the list, but is not; therefore it is not denumerable. kd * Mike to Kevin All you've shown is that there is one list of your numbers which doesn't include them all. You have not shown that there is no list which contains them all. To use the diagonalization method, you must 1. Propose a set of numbers. 2. Show that for EVERY denumeration of this set, you can generate a number which is in the set and not in the denumeration. In your example, you've defined the set of numbers as being generated by finite diagonalizations and the diagonalization of the infinite list so generated. All you've done is prove that there is a list of some of your numbers which doesn't include all of them. That's trivial. But there are other lists to consider. For example, take the infinite diagonalization, put it first and follow it by all the other numbers in the order you've defined. This is a list of all the numbers in the set. You can apply the diagonalization, but you get a number which is not in the set -- that doesn't prove anything. You can't change the set in the middle -- you must define the set and then show that for EVERY list, there is a number which is in the set and not in the list. Cantor did that for the reals and the power set of the integers. You have not done this for your set. * Kevin to Mike Mike, << take the infinite diagonalization, put it first and follow it by all the other numbers >> I can't simply reorder the set since after reordering it will no longer fit the definition of the set. i.e. that each member is the diagonal product of the previous members. Since there is only _ONE_ possible denumeration for the set, then << for EVERY denumeration of this set, you can generate a number which is in the set and not in the denumeration. >> This set fulfills both of your conditions WORD for WORD! Let's say that I arbitrarily stuck a stange number in the 3rd position, since all the numbers are defined in their relation to preceding numbers, all of the numbers after the 3rd position would change, and the diagonal of the entire set will still be a member of the set. The set of all DPs with a strange number in the 3rd position: 1 0.0 2 0.1 3 0.10101 4 0.110 5 0.1101 6 0.11011 10 0.110111111 The strange number in the 3rd member has a 1 on the diagonal instead of a 0. By definition all proceding numbers will have a 0 in the 3rd decimal place, (including the diagonal product on the entire set). Once again all of these numbers are apparently Rational. kd PS If I put 0.111... as the 1st member, then all proceding members in the denumeration will begin 0, since the first digit of the 1st number is 1. Of course you can say that .111... = 1.000. I.e., if you begin the series with the number 1, you will have a circular proof in which the diagonal of the entire set is in the set. The same thing is true for the Reals. If you began a denumeration of the Reals with the number 1.0, and ordered them such that a 0 was on the diagonal for every member, then the diagonal product of the entire set would be .11111... = 1.0. Circular Proof. There are several reasons that I would dismiss such an argument. The set who 1st member is 1.0 and all subsequent members is the dp of the preceding members is not the set whose EVERY MEMBER is the dp of the preceding members. Also there is no such nifty equality such as 1 = .111... which you can use to dismiss the corresponding diagonal proof on the Power Set. Thanks, and I apologize for being too wordy. * Mike to Tom Here are a couple of related examples. A friend pointed out to me how odd it is that 3^3 + 4^3 + 5^3 = 6^3. Is this the only example of a solution in positive integers to a^3 + (a+1)^3 + (a+2)^3 = b^3 ? After making some progress on this, but not solving it, I came up with this question: Are there positive integral solutions to n^2 + (n+1)^2 + . . . + (n+j)^2 = (n+j+1)^2 + . . . + (n+j+k)^2 other than n=3, j=1, k=1? I found an answer to the first question by scanning Mathematical Reviews. Someone solved it in (I think) 1987. (It turns out a=3 is the only solution.) The second is, as far as I know, new, and a Ph.D. student at UT Austin called Chris Pinner spent a little time on it. He found some solutions other than the one I give above, but did not solve the general problem. Hope this is useful, Mike * Mike to Kevin But then you haven't proven any thing. In order to prove a set nondenumerable, you must show that for ANY sequence of members of the set, there is a member that is not in the sequence. Showing that one particular sequence is does not contain all members is worthless. The fact that you have defined the set with one denumeration does not mean that you cannot use others. Once the set is defined, changing the order doesn't matter. Again, first you define the set and then you show that for ANY sequence ... Again. You don't choose an order for the set. You 1. Define the set. 2. Show that for ANY sequence of members, you can construct an element that is in the set, but not in the set. * Kevin to Mike Mike, How do you dismiss the argument that the Reals can be organized so that the first member is 1 and there is a 0 on the diagonal for all following numbers? In this case the diagonal test would be 0.111... = 1.00 which is in the list. kd * Mike to Kevin The diagonal proof doesn't work well in binary. That's why one normally uses the decimal expansion with the rule. In the decimal expansion one can always choose the nth digit so that it is not the nth digit of the nth number and also not 9 or 0. That eliminates the possibility that you get a number which has two different representations. Have you actually seen a claimed proof using the binary representation? I've not and don't see how it could work because of the problem you note. Suppes (Axiomatic Set Theory) specifically uses the decimal expansion and constructs the nonmember as the nonmember as having a 2 in the nth place if the nth digit of the nth number is 1, 1 if it is not. The resulting number cannot be in the sequence since it only has one representation in decimal and that representation is not in the list. PS since .111... = 1.00 all Reals must have at least one 0 in them somewhere. * Tom to Mike Mike, Thanks. Five years ago I heard the famouns Hungarian mathematician (name? The guy who floats from home to home across the world) describe some of the very simply-stated unsolved problems. * Lou to Tom The famous Hungarian mathematician who floats from home to home across the world is Erdos. (There's a diacritical mark somewhere in that name. I don't have to embarrass myself by inserting it in the wrong place because ASCII doesn't support diacritical marks.) * Kevin to Mike Mike, << The diagonal proof doesn't work well in binary. >> IMHO the diagonal proof is clearer in binary than base ten. In binary there are only two states for each digit. Since there are 10 possible states in base 10, it is not clear whether the diagonal proof is a result of the multiple states, or the non-denumerability of the Reals. Cantor probably didn't use binary because in the 1880s binary was not widely used. If you take a diagonal starting at the 1st digit of the 2nd number, you can generate a proof. (It would be awkward going though.) The thing I hoped to do was to rob the diagonal proof of its elegance. Earlier, I posted proofs showing the diagonal proof on the set of permutations a n-character string with a 2 char alphabet. I think this clarifies the diagonal proof on infinite sets. The permutation of a 3 char string is: 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 The diagonal is 101, the diagonal product is 010. This number will be in the set, but not in the first 3 positions. On a set where n is an arbitrary value the diagonal product will be in the set, but not in the first n positions. This is reasonable since there are 2^n permuations. 2^n > n for n >= 1. I believe that this same characteristic is true for infinite sets. Likewise for power sets, the diagonal product on the power set of n Natural Numbers will not be in the first n sets. The power set of a set with n members has 2^n members. 2^n > n for n >= 1. Now then, lets take all possible 2 member sets created from a set of n members. If order is important, this set will have n^2 members. For n>=1, n^2 > n. There will be (2^n - n) sets not in the first n sets. Note, n^2 is the tabular proof. Remember Cantor put the Rationals in a table and called them denumerable. I put the Power Set in nested table, but they are not. This implies that the tabular proof is insufficient, which opens the question "are the Rationals are denumerable?" Since there are (n^2-n) sets not in the first n members of the tabular ordering, I would say that subsets of 2-member sets is not denumerable. Likewise I can generate an algorithm on the first n members to prove this. kd * Mike to Kevin It may be clearer in binary, but it's wrong without quite a bit more work. The problem is that in binary it is difficult to prove that the constructed number is not in the list since it may not have a unique representation. In base 4 or higher you can construct it in such a way that it is a number with only one representation and since that representation is not in the list, we know that the number is not in the list. There may be a way of fixing up the diagonal proof using binary notation, but why bother. Using decimal notation, the proof is clear and easy. This is getting a little ridiculous. You claim that the proof is clearer using binary notation, but then give a proof which is faulty, point out the error, and claim that this means that the reals are countable. Sorry, I'm going to insist that you use a correct proof. You have not created a sequence of elements of the power set which is exhaustive -- we know that's impossible by Cantor's proof. So far, you have been unable to prove anything. You parody the proof, ignoring the whole point. To prove that a set is not denumerable, you must 1. Define the set. 2. Show that for ANY sequence, there is an element of the set not in the sequence. Proving that given a finite sequence, you can find an element of the set not in the sequence only proves that the set is infinite -- not that it is nondenumerable. * Lou to Kevin > How do you dismiss the argument that the Reals can be organized so > that the first member is 1 and there is a 0 on the diagonal for all > following numbers? No one needs to dismiss that argument. Any time you make a statement that you can organize things in a certain way, *you* must prove that it is possible for you to do so. That's *prove*. Not merely *assert*. Your assertion that you can do this goes far beyond the standard reductio ad absurdum assumption that it is possible to organize the Reals so that they are in one-to-one correspondence with the natural numbers. You are asserting that you can find such a correspondence that has a specific property; the standard assumption makes no such assertion. * Kevin to Lou Lou, My assertion is not that I can order the Reals in such a way that they are denumerable, simply that I can order them in a way that there is a 0 on the diagonal for each real. I do this by first showing that all Real numbers must have at least one 0 in their binary representation. A Real that had no 0s in its binary representation would be .111... = 1.0. Likewise a any number ending in an endless strings of 1 can be reduced to a Rational Number. Although my proof doesn't prove the Reals are denumerable, it shows that the diagonal proof is not sufficient to prove the assertion. kd * Mike to Kevin > Although my proof doesn't prove the Reals are denumerable, it shows that the > diagonal proof is not sufficient to prove the assertion. No. You've shown that the diagonal proof as misstated by you is not sufficient. I think everyone agrees that your diagonal "proof" is not valid. Yes, it is possible to create a sequence of reals (non-exhaustive, of course) in which the diagonal is all zero and in which the first number is 1 in binary notation. So what? All that means is that you can't use the diagonal proof using binary notation (at least not in it's usual form). You have not shown that the diagonal proof as stated by Cantor, or by other authors, is invalid since they construct the number in such a way that it cannot have two representations and it's representation is not in the sequence. No author I have seen uses binary notation in proving that the reals are not denumerable. You may think that Cantor used decimal simply because that's what people are used to, but whether he chose it for good or bad reasons, he gives a valid proof. * Barry to all A few years ago there was an article in the New York Times science section about finding the shortest way of connecting points by adding other points. It said that it was proven that there is no way to find the best position of the added point. I saved this article for a time when I felt like playing with the problem, and that time finally came. Could someone tell me what I would figure out if I made the following calculations? What if you take a bunch of points and make circles around every combination of pairs of points (points 1 and 2, 1 and 3, and 2 and 3 if there are three points) so there would be two points at the edge of each circle and the circles would overlap. Then you make circles around each combination of pairs of circles, and then circles around each combination of pairs of those larger circles, ect. Then when you get tired, make the smallest circle possible that will fit around all the circles. If you spent an infinity making the smaller circles, would the midpoint of the large one be the best place to add the extra point if you want to join the origional points? If not, what kind of curve would the encompasing circles make as I continue the loop? Has this been done? * Kevin to Oliver Oliver, This is a rather petty argument, but I could start with .01010... The 2nd number is .1010.., and 3rd is 1.0000.... I could then order the Reals so that there are 0s on the first diagonal, and the sequence .101010 on the second diagonal. 0.01010101 10101010 1.00000000 ?.??10?? ?.???00?? ?.????10?... Likewise, you can take the first n diagonals, and I can construct an ordering in which the first n diagonals appear in the list. The trick is that I have to assure that all permutations of an n-digit binary string are representented on the cross-sections. BTW, I could have as easily begun the list with pi, and assured that the second diagonal product is pi. kd * Lou to Kevin No, you may not do any of those things. You must work with an *arbitrarily given* one-to-one correspondence of the reals with the rationals if you want to prove anything useful. * Oliver to Mike I think its time to terminate this thread. Sincerely yours, GEORG CANTOR * Oliver to Kevin How do you dismiss the argument that the Reals can be organized so that the first member is 1 and there is a 0 on the diagonal for all following numbers? In this case the diagonal test would be 0.111... = 1.00 which is in the list."Such list would not contain _all_ the reals because this is an undenurable number of choices for each position in the list. You can also adapt the diag. argument and chane the dgit one to the right of the diagonal position. This number would not be on the list."If it is, then if I take a diagonal across the entire set, I will produce a number which is _by_definition_ a member of the set, but which is not in the denumeration."from msg 114949If I understand your list, all the numbers on the list terminate. However the diagonal of the _whole_ list does not, so it is _not_ on the list. * Antonio to Kevin Many of the most insightful advances in math came from mathematician's in >their youth. Gauss, Abel, Galois were under 20 when they came up with many of >their most interesting observations. I fear today that the language used in >math is so difficult that students will not get to the frontiers until they >are in their late twenties and thirties. After they have lost the vigor of >youth.>Hardy said "No mathematician should ever allow himself to forget tha >mathematics,..., is a young man's game.">Today the language is so difficult to learn that the "young man," or woman for >that matter, is excluded from the debate.>kdI don't think a very bright person must know ALL the language of Math. Look at Hardy's protegie, Ramanujan. Knew very little of the language of math, indeed little of even proofs, yet had lots to say! * Jim to Lou Hi! BTW, I heard Erdos speak a few weeks ago at the Univ. of Minnesota which he is visiting. His topic was "Some of my favorite theorems and unsolved problems". The man was VERY entertaining and he has a marvelous wit. Some of the jokes and humorous anecdotes he told re/ very famous mathematicians were eye opening. Jim * Kevin to Antonio Antonio, Ramanujan (1887,1920) was a contemporary of Frege (1848,1925), Cantor (1845,1918) and Hilbert (1862,1943). When Ramanujan was at Trinity the works of Frege was somewhat scorned as it contained the Russell (1872,1970) paradox. Ramanujan was contemporary with the development of Symbolic Logic, the "language of math." Prior to this time, mathematicians had a completely different view of the relation of math to language to logic. In Hardy's "Apology" there seems to be a paradox, he dismisses all of "elementary math" as "trivial." Implying that only at the graduate level does math start getting interesting, but he also declares that it is an occupation for the young. Very few people are able to swim through mire of "elementary" math to get to the frontiers before they are 25. IMHO, Computers will change this. Young geniuses can launch off on their own studies, learning computer logic instead of symbolic logic. A couple months ago I was at a local University trying to find a mathematician studying the pedagogy of math. I found that there were 0.0% of the department studying this field. The math department dismissed education as trivial, and left it to the psychologists. If we wish to debate lowering mathematic skills, I would circle this problem and tack it squarely on the forehead of the president of the AMS. (prior to 1900 mathematicians concentrated heavily on the pedagogy of math, look at Dedekind's work on the Theory of Numbers. It was designed to be taught at the elementary. Certainly the work was skillful and at a graduate level, but it's aim was in developing the means of introducing higher ideas at the elementary level. Speaking of Pedagogy. Prior to the development of Symbolic Logic. Logical discourse was not only taught but was the central core of elementary education in the US. After its development, courses on logic disappeared from the school cirriculum. Interesting. kd * John to me Thank you for your reply. I shall consider it carefully. I especially appreciate the book reference. I shall obtain a copy of Kreyszig's differential geometry, and I suspect the world will not then hear from me for a while. * John to all I'm trying to understand what a tensor is, and I've been unable to understand the books I've seen. Josef Eschgfaeller has recommended Kreyszig's Differential Geometry, and it's on order, but that will take 3 weeks. In the mean time, can anyone recommend another? Why don't they do such abstract subjects with set notation? Is there a book on this that uses set notation? * Walter to all I am researching, for possible dissertation, papers on torgerson's transforms. These transforms of scale were discussed by W. Torgerson in the 50's (and late 40's.) I have only been able to find a couple of scant dissertations on scale transforms, only one of which dealt specifically with Torgerson. Has anyone seen other work on scale transformations that emphasize Warren Torgerson's work? Thanks! Walt * Eberhard to all I tried to find a combinatorical formula but unfortunately I found out that the problem below is not as trivial as I thought in the beginning. Maybe someone out here has more experience... Problem: How many ways are there to arrange n circles if it is allowed to draw each of them inside of another or besides another. I found out that this problem is equivalent to the question of how to combine pairs of parentheses. The series (just figured out by playing around) begins with: circles layouts patterns 1 1 () 2 2 ()() (()) 3 4 ()()() (())() (()()) ((())) 4 9 ()()()() (())(()) (((()))) ((()))() (())()() (()()()) (()())() ((()())) ((())()) I read in a book that the series is related to the theory of root trees and to the structure of chemical compounds but the explanations given there were too high for me to understand. Thanks in advance, Eberhard * To Eberhard These numbers are called Catalan's numbers. Each way of putting parentheses in a formal product is equivalent to a rooted tree, for example /\ /\ \ /\ \ \ /\ is equivalent to ((xx)x)(xx), and each such tree is equivalent to a hierarchy, which you obtain by putting subordinate vertices as circles inside a bigger circle which represents their common immediate superior. The tree above is for example equivalent to the configuration ___________________________________________________ | ______________________ ____________ | | | __________ __ | | __ __ | | | | | __ __ | |__| | | |__| |__| | | | | | |__||__| | | |____________| | | | |__________| | | | |______________________| | |___________________________________________________| For n>=1 the n-th Catalan number C[n] is (1/n)*C(2n-2,n-1), where C(n,k) is the binomial coefficient (beginning with C[1]=1). One puts C[0]=0. References: K. Jacobs: Einfuehrung in die Kombinatorik. De Gruyter 1983. H. Halder/W. Heise: Einfuehrung in die Kombinatorik. Hanser 1976. D. Stanton/D. White: Constructive combinatorics. Springer 1986. The book by Stanton/White uses a slightly different numeration, but gives a discussion which is very close to your original questions. * Eberhard to me Josef, thanks for your help. Unfortunately it's not the Catalan series 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012... but a series whose first terms I know are: 1,1,2,4,9,20,48,115,286,719,1842,4766... The reason for the slower growth of the 2nd series lies in the elimination of permutation duplicates of each configuration. The reference I found only gave the results above. and pointed towards a text which I gave no access to: G.Polya Kombinatorische Anzahlbestimmung in Gruppen, Graphen und chemischen Verbindungen. Acta Mathematica 68, 1937, p.145-254 Thanks -- Eberhard * To Eberhard You're right. Your trees are not ordered, and in fact the circles and the trees in my response are not equivalent. Sorry. The numbers (0,1,1,2,4,9,20,48,115,286,719,1482,4766,...) are called strunk numbers in Jacobs's book (pp. 203-210, 243). The rather complicated generating function for the sequence is derived in the following references: D. Knuth: The art of computer programming. First volume (Fundamental algorithms). Addison-Wesley. Pages 386 and 395 (section 2.3.4.4). H. Halder/W. Heise: Einfuehrung in die Kombinatorik. Pages 112-114. H. Wilf: Generatingfunctionology. Academic Press 1990. Page 94. I did not understand the relationship between this sequence and partitions (of numbers). Someone knows? Strangely enough, there is a relationship between rooted trees and ordinary differential equations (this is new to me, if I understand well, one counts the possible orders of differentiation, the algebraic theory one obtains seems to be especially useful for dealing with Runge-Kutta methods, a key word is Butcher series): E. Hairer/S. Norsett/G. Wanner: Solving ordinary differential equations I. Springer 1993. Pages 143-155. J.E. * Charles to John For a very thorough introduction to tensors, you might have a look at Spivak's "A Comprehensive Introduction to Differential Geometry", volume 1. To really understand what tensors are, I think one needs to understand the concepts of a manifold and a bundle over a manifold. The usual explanation is something like "well they are objects which transform like this (sleight-of-hand follows)". I'm willing to explain further, if you can stand it. Charles Yeomans * Charles to John With regard to vector spaces (and other topics), let me define by example. Consider the operation of passing from a (finite-dimensional) vector space V to its dual V*. Now, if one has a linear map f:V ---> W, then there is a corresponding map f*: W* ---> V*. Because the direction of the map is reversed, one says that the act of passing to the dual sapce is "contravariant" (or arrow-reversing, if you like). In fancier language, one would say that the dualization functor from the category of finite-dimensional vector spaces to itself is a contravariant functor. A "covariant" functor is one which does not reverse the direction of maps. Using vector spaces, here is an example. For two vector spaces V and W, let Hom(V,W) denote the collection of linear maps from V to W. Hom(V,W) is itself a vector space (and if you pick bases for V and W, it is just the space of appropriately sized matrices). If we fix a third vector space U, then we can define a functor from vector spaces to itself by sending a vector space V to Hom(U,V); the functor is usually called Hom(U, *). Now, given V, W and a linear map f:V ---> W, if we apply Hom(U,*) to everything we obtain a map f :Hom(U,V) ---> Hom(U,W), * defined by sending the element a in Hom(U,V) (it's really a function!) to the element f o a in Hom(U,W). So this is covariant (or arrow-preserving). Charles Yeomans * Charles to all A few years ago I was watching a NOVA episode on Ramanujan. Partitions of numbers was mentioned (which was new to me - I like math problems but my formal math ended with differential equations). NOVA also showed the formula that Ramanujan had developed for partitions. It was way over my head. I couldn't imagine this problem could be so hard. So after the program was over I spent the next few hours thinking about the problem. I wanted to come up with a simple algorithm for calculating partitions of numbers. Now I only concentrated on simple partitions. For example, the partitions of 5 would be 1+1+1+1+1, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, and 5. Before I went to bed that night, I had developed what I think is a new concept (since I had never heard of partitions before) and I called it partital partitions. This new concept allowed me to come up with an algorithm to calculate partitions very quickly. For example, I have a 2 page program, written in C, which can calculate the partitions of all numbers between 1 and 1000 (inclusive) in 15 seconds (back then I ran this on a 486/33). Is there any use for this? Does anybody care about such an algorithm? Has this been done before, i.e. are there simpler formulas than Ramanujan's (I have a feeling that Ramanujan's formula is all-inclusive and mine are a special case)? If anyone has any interest or information please let me know. Thanks. Charles Scalfani * Eberhard to me Josef, thanks for your help. I will have a look for the references you gave me. Eberhard * To Charles The theory of partitions is a part both of number theory and combinatorics. I'm not an expert in this field, so I can answer you only as a librarian. There is a huge literature, and there are many applications of partitions in completely different fields of mathematics, but usually research mathematicians don't bother about concrete applications. Some applications are in physics. The first concrete application I found once is the following post office problem: When you have a post office with 5 counters and n clients, then the number p'(n,5) of partitions of n with at most 5 summands can be interesting to the director of the office who regards the counters as equivalent. Denote by p(n,k) the number of partitions of n with exactly k summands (not 0) and by p(n) the number of all partitions as in your message. Then there are relations p(n+1,k+1) = p(n,k) + p(n-k,k+1) p'(n+1,k+1) = p'(n+1,k) + p'(n-k,k+1) (for 0<=k<=n) and p(n) = - (sum over k=1,...,n) a(k)*p(n-k) where a(k) is defined in the following way: Let o(m) = (3*m*m-m)/2 for every natural number m be the m-th pentagonal number. Then one shows first that o(m) != o(s) for m!=s, and then a(k) = 0 if k is different from all o(m), and = (-1)^m if k = o(m). Really beautiful things become when you use generating functions. There is an incredible interplay between formal sums and formal products. The recursion for p(n) should go back to Euler and can be used for a rather quick calculation of p(n). I have a table calculated with this formula where p(100) = 190569292, so when you are able to calculate p(1000), this must be a quite impressive number. It should be possible also to use the first recursion, because p(n) = (sum over k=0,...,n) p(n,k). This could become however rather slow for large n, if I remember well. Gives your program also the concrete partitions or only their number? I too would be interested in hearing about more applications, in economics or optimization, say. References (1% or 0.1% of the literature probably): G. Andrews: The theory of partitions. Cambridge Univ. Press 1981. T. Apostol: Introduction to analytic number theory. Springer 1986. C. Berge: Principles of combinatorics. Academic Press 1971. G. Hardy/E. Wright: An introduction to the theory of numbers. Oxford UP 1988. K. Jacobs: Einfuehrung in die Kombinatorik. De Gruyter 1983. H. Rademacher: Topics in analytic number theory. Springer 1973. * David to all Dear CompuServe Education Forum participants: I am a 4th year undergraduate finishing up my math degree at Carleton University in Ottawa, Canada. I am researching a topic for my fourth year honours thesis, computer aided instruction/learning. I have been visiting all of Ottawa's local resources and my search for information has been somewhat slow and sometimes unsuccessful. I am sure that there are many people involved and interested in this area of study. I would appreciate any ideas, comments, references, or information from any participants of this forum on this subject. My interests in CAI/CAL are systems that will teach a course in mathematics, either at the high school or first year college/university level. These systems might be independent of a lecturer or part of a tutorial program. You can send any messages to me at the following locations: CompuServe address: 73072,1420 Internet address: dcraig@ccs.carleton.ca Many thanks if you can help! David Craig Department of Mathematics & Statistics Carleton University Ottawa, Ontario, Canadac * Rick to David David: The NEW SCHOOL in New York City offers on-line CAI courses at both the HS/College (including Masters) Level...there is some information here in our library (old info) about this school. Rick Needham/SYSOP * Ken to all In playing with my old navigating instruments (drafting compass) recently, I drew a set of randomly distributed points and used each as the centers of circles drawn through each of the other points. I =should= write a little program to check it out (no "time" just now), but it, presently, seems to me that this little procedure provides dir- ectional (sequence) information that's useful with respect to calculat- ing the shortest overall route among the points. It's more than just taking radii between points. The curvatures of the circles through the points "point" to the next step in the route(?). (Each point comes to be marked by a set of arcs that's easily interpretable directionally - the few manual trials I did all seemed to work. In this way, the set of points is given a "group discipline" (J. J. Hopfield's term) which is necessary if the TSP's to be made tractable. (An article, "Breaking Intractability" by J. F. Traub, and H. Wozniakowski, _Scientific American_, Jan. 1994, p. 102, stimulated this "play".) This method doesn't resolve things like points lying relatively-close all on a line (2 correct sequences exist for such a segment of the route), &c, but I'm wondering if this's a useful way to delimit the size of the prob- lem? Or will I be embarassed if I ever get around to writing the program to test this? I can't do it just now, so I've decided to just swallow hard and offer this speculation to those who might wish to explore it further. Cheers, ken * Lou to David Have you looked at "Calculus & Mathematica" by Davis, Porta, & Uhl, and published by Addison-Wesley. (Due to hit bookstores Real Soon Now--we've been promised it'll be available for the spring term.) * Lynn to Charles For your information, partitions(1000) is 24061467864032622473692149727991. It took about an hour on my 20 MHz 386, using MAPLE (student edition). --- Lynn * Charles to Lynn >> It took about an hour on my 20 MHz 386, using MAPLE (student edition). << It took me 15 seconds to calculate p(1) thru p(1000) and an hour to calculate p(1) thru p(8000) which happens to be a 96 digit number of which I don't have in front of me at the moment. Please excuse my ignorance but what is MAPLE? * Gordon to all Could someone recommend a good source book for basic quaternion theory. It is to help me with personal research I am undertaking into certain aspects of fractals. Gordon Lamb * Rick to Gary (Abaci) Gary: Here is some information on the ABACUS...its not an instruction guide..however, it does contain a short bibliography which might guide you in the right direction. abacus -------------------------------- {ab'-uh-kuhs} An abacus is an instrument that helps a person make arithmetic calculations. In its best-known form, as the Chinese suan pan, it is composed of beads strung on parallel wires in a rectangular frame. In ancient times, however, the abacus was composed of a row of grooves in sand into which pebbles were placed. Later, the use of a slate or a board (in Greek, abax, from which the current name is derived) made it a portable device; and the pebbles were systematically arranged along parallel lines. The value assigned to each pebble (or bead, shell, or stick) is determined not by its shape but by its position: one pebble on a particular line or one bead on a particular wire has the value of 1; two together have the value of 2. A pebble on the next line, however, might have the value of 10, and a pebble on the third line would have the value of 100. Therefore, three properly placed pebbles--two with values of 1 and one with the value of 10--could signify 12, and the addition of a fourth pebble with the value of 100 could signify 112, using a place-value notational system of multiples of 10. Thus the abacus works on the principle of place-value notation: the location of the bead determines its value. In this way, relatively few beads are required to depict large numbers. The beads are counted, or given numerical values, by shifting them in one direction. The values are erased (freeing the counters for reuse) by shifting the beads in the other direction. An abacus is used simply as a memory aid by a person making mental calculations. In contrast, ADDING MACHINES, electronic calculators, and computers are used to make physical calculations. Bibliography: Moon, Parry H., The Abacus (1971); Pullan, J.M., The History of the Abacus (1969). Hope this helps... Rick * To Gordon A good treatment can be found in Ebbinghaus a.o.: Numbers. Springer 1991, 400p. 3-540-97497-0. Another reference could be Ian Porteous: Topological geometry. Cambridge UP 1981. Sometimes books on engineering geometry or cinematics contain introductions to quaternions. In libraries you may find Joly's Manual of quaternions (1905), but it is not easy reading. I heard about some recent research by John Milnor about higher dimensional Mandelbrot sets, perhaps quaternions play a role. I tried once to look what happens if one generalizes quadratic mappings to quaternions and other higher dimensional algebras, but it seemed to me that one obtains simply a Mandelbrot set which rotates about one axis and similar objects, I don't remember well. Someone has references on Milnor's work? Josef Eschgfaeller * Charles to Gordon Concerning your request for references to quaternions - it depends on what you wnat to know. Since your interest is in fractal geometry, I'd assume that you're not so interested in the algebraic theory of quarternions. Perhaps the best basic reference is "Hypercomplex Numbers: An Elementary Introduction to Algebras", by Kantor and Solodnikov, published by Springer. This book assumes as background only knowledge of basic linear algebra. If you have more specific questions, you can, of course, post them. Charles Yeomans * To all I duplicated the following problem to this forum, hoping for the help of some expert. Probably it is not easy to solve it completely here. I'm a mathematician, but I was not able to find a formulation in terms of conditional probability, say. Thanks for bibliographical hints and keywords. ------------------------------------------------------------------------------- [So, for example, the standard error on the SAT verbal is around 30 points. If your true score is 700, then about 34% of the times you take the test, you will score between 700 and 730; another 14% of the time you will score between 730 and 760.] You pose a problem in statistics. I'm not a statistician, so I'm not sure about what should be the precise statement, but I think one should distinguish between the standard deviation of the test and the standard error in taking it. More mathematically: You have a random variable X, which is the result of a random person taking the test. X has approximately a normal distribution with some standard deviation (sigma X). Then you have another random variable Y, which is the (random) result of a concrete fixed person taking the test. Assume that Y too has a normal distribution with some standard deviation (sigma Y). What is the relationship between (sigma Y) and (sigma X), especially if the mean values (mu X) and (mu Y) are very different? It is not even clear to me how to express mathematically the fact that Y comes from taking concretely that test. Why should there be any unique mathematical dependence between (sigma X) and (sigma Y)? I tried to do this for dice: Assume that a die is thrown 60 times, that the outcomes are exactly according to the expectations (10 times 1, 10 times 2, ...), but that there are some errors during the observation, so that in 10 observations for each value there are two errors, according to the following table: real outcomes (erroneously) observed outcomes 10 times 1 8 times 1, once 0, once 2 10 times 2 8 times 2, once 1, once 3 10 times 3 8 times 3, once 2, once 4 10 times 4 8 times 4, once 3, once 5 10 times 5 8 times 5, once 4, once 6 10 times 6 8 times 6, once 5, once 7 Call T the real outcomes (one should better say the correctly observed outcomes) and Y the erroneously observed outcomes. Than (mu T) = (mu Y) = 210/60 = 3.5, and (sigmasquare T) = 10*(1+4+9+16+25+36)/60 - 3.5*3.5 = 2.917, and (sigmasquare Y) = 10*(4+9+16+25)/60 + 9*(1+36)/60 + 49/60 - 3.5*3.5 = 3.117. For each "true" outcome k however sigmasquare = (8*k*k+(k-1)*(k-1)+(k+1)*(k+1))/10 - k*k = (10*k*k+2)/10 - k*k = 0.2. Of course here T and Y have a different type of distribution, but I don't think it does affect things much. So, returning to the original question, it seems that one had to determine experimentally the standard deviation of Y at each real outcome. Josef Eschgfaeller * Tom to me I think you're on the right track. There are two numbers that can be characterized by a second moment - one is the variance in the population, and the other is the variance in the test: if you tested one person a zillion times, what would the variance of his test scores look like. This happens in other places as well. Suppose you're cutting 10 foot beams of wood. There is the variance in the lengths of the beams, which would have one standard deviation, and then there is the variance in the tape measures you use to measure the length of the beams, which has another variance. Because you are really talking about two indepenent things - a saw and a tape measure, e.g., there is (in general) no way to go from one variance to the other. * Michael to Gary Although I don't know where to find information about abaci (sp?), if you are interested in an item that can give you some insight into numbers in general, look up Napier's bones. It was a system for multipling large numbers and was designed by the same guy who created logs. Then there's Napier's abacus which uses a checker board and is also avery interesting idea that can give you some insight into #'s. Mike Rattner * To Tom [Suppose you're cutting 10 foot beams of wood. There is the variance in the lengths of the beams, which would have one standard deviation, and then there is the variance in the tape measures you use to measure the length of the beams, which has another variance.] Such a concrete example shows that in general there shall be almost no relationship between the precision of the single measurement and the variance of the population. But how can one then assess the precision of a psychological test? It is almost impossible or senseless to repeat such a test on the same person. * Tom to me I think in practice what they do is to take groups that score 300, 400, 500 etc. and then retest them, and look at the mean and standard deviation of the second test score. * Gordon to me Thanks for your information, and I will endeavour to locate the works which you mention. My problem relates to higher dimensional Mandelbrot-type sets. I have been examining one with dimension greater than 2, and trying to compare it to quaternion-type sets. If you are interested, I will E-mail you in due course once I have got somewhere with my research. Gordon Lamb * Gordon to Charles Thanks for the information. Although my prime interest is in fractal geometry, the algebraic theory will certainly help with background studies. Once I have had a chance to digest whatever information I can find, including the reference which you provided, I may well take up your offer of help with specifics. Gordon Lamb * To Gordon Thank you. You can e-mail me on Internet too: esg at ifeuniv.unife.it * Ken to himself Yep. This mode of attack on the TSP is a keeper. No sorts are necesary. The arcs form a pattern that's uniquely-interpretable within the fixed geometrical space of the TSP (uniqueness even in the case of points on a straight line). Works in 3-D, too. What's happening in this arc method is that, for each instance of the TSP, a new number system's being created. (See AoK, Ap6.) The arc patterns form the units of these number systems. Then, all one has to do is count in that number system. The implicit pattern-recognition (pattern-classification) step does have considerable overhead, but this overhead is exactly the same for each city in a particular arc-method implimentation. So the size of the problem increases only by x (the size of the pattern-recognition step) for each city in a particular instance of the TSP. There're many methods similar to this arc-method. One that I find particularly-interesting substitutes shadow-casting for arc-drawing. Here, the process can be augmented if the "cities" are given some finite size - a small circle centered on the "city". Then perspective's added to the shadowing patterns. Going further: For those who've read AoK, these sorts of methods exist within the way brains process information. A particular environmental information set activates the various neural arrays, and sub-arrays (vision, touch, audition, &c.), which each, in turn, cast their "light" (activation) upon each other. The =extremely=very=important= thing is that, since each of the arrays and sub-arrays is located within the global neural topology (geometry; neuroanatomy) in ="fixed"= topological relationship with respect to each of the other arrays and sub-arrays, the resultant "shadow-casting" creates a circumstance in which the activation of each array and sub-array is uniquely-correlated with the activation of every other array and sub-array. The result is that, within the =abstract= (left-right, front-back, up-down) geometry of the brain, the activations of each sensory & motor modality becomes exquisitely-coordinated. Thus, a baseball player's musculature's activated with specific respect to an on-rushing line-drive via the activation "light" that the player's visual subsystem casts upon the other arrays and sub-arrays within the player's brain. The brain's constantly resolving a compound version of the TSP. In it, each "city" "moves" (alters its own activation) in a way that's correlated with the activation "light" that's cast upon it. (Also, the neuroanatomy restricts the directionality of the activation "light" - it's not all-to- all. By virtue of their positions in the overall geometry, the "cities" "recognize", and respond to such "light". Their response is predicted by the "shadow" patterns that such "light" casts". There are =many= important results of this. One of the most-easily comprehended of these is that each muscle of the body's activated with specific respect to the momentary stimulus set which, in the case of the baseball player, is the onrushing ball (ground underfoot, oxygen-content in atmosphere, noise from crowd, ambient temp, humidity, &c.). It's easy to extend this all the way up to cognition - as in memory classification & cross-correlation. Each memory has a correlated "shadow" pattern within every "city" in the brain. That is, every memory has a correlated activation of the little finger, for instance. Extend this until it includes the activation of everything in the body - by virtue of everything having its unique, "fixed" locus within the overall geometry, unique "light" shines forth from everywhere within the CNS. (The integrative mechanism which makes this enormous cross-correlation task possible is described in AoK.) There exist no "np-complete" problems - only problems that have not yet been given efficient methods of resolution. ken * Rollo to Gordon Please send a report of your results to me, too, Gordon. If they prove interesting, you might want to submit an article to Amygdala, the fractal newsletter that I publish. --Rollo Silver * Gordon to Rollo Rollo Will do but - don't hold your breath - have to fit in my fractal research around my business commitments. I may have come across a new line in M-sets but, it requires further investigation, espec on the maths side. I will contact you again and let you know how things have worked out - either way! Can you E-Mail me some details about your newsletter? Gordon Lamb * Tapan to all Suppose C(X,R) is the space of all continuous maps from a topological space X into the Reals R, where R has the usual metric topology. I want to show that the map f+g:x--->f(x)+g(x) belongs to C(X,R), where f and g are in the space C(X,R), x is in X, and f(x), g(x) is in R. I know that I need to consider open sets in R, and then use the fact that f and g are continuous to look at the inverses of these open sets in X. What I am stuck at is knowing what open sets of f-inverse and g-inverse I should look at, and what the intersection of these sets will be to obtain the inverse set of the function f+g, where f+g acts on an arbitrary open interval (a,b) of R. Any ideas/help will be greatly appreciated. ...Tapan * Owen to all Does anyone know anything about WAVELETS and how they can be applied to acheive large data compression ratios on digitized speech? In the August 24, 1990 issue of "Science", there is mentioned a 40 to 1 compression of digitized pictures. It is insinuated in the article that digitized speech can be compressed even more. I have found three files in this forum's libraries with programs that do wavelet analysis of input signals and I will download them and study them. Any help in wavelet theory and implementation would be greatly appreciated. -Owen * Jacob to all Here is the situation: a drunken sailor is doing a 1-dimensional random walk. If after N steps he is at the point X, then after N+1 steps he is at points X+1 or X-1 with equal probability 50%. Let's say his initial position is X=0. My question: what is his average maximal walk (i.e. maximal distance from 0) after N steps? For example, after 3 steps the maximal walk is 3 in 2 cases out of possible 8 (+++ and ---), it is 2 in 2 other cases (++- and --+), and it is 1 in the 4 remaining cases (+-+,+--,-+- and -++). So the average maximal walk is 2/8 * 3 + 2/8 * 2 + 4/8 * 1 = 1.75 I have seen a claim that asymptotically, this value is square root of N, which looks plausible. The person who made the claim refers to Feller's course on probability and statistics, but I could not find anything on this problem in that book. Does anyone know a book which contains the exact formula and/or proves the asymptotic result? In general, what is a good reference book on random walk theory? I would appreciate any replies. * Gerald to Jacob * what is his average maximal walk (i.e. maximal distance from 0) after N steps? This should be listed in the index of a (sufficiently advanced) probability book under "maximal function" or "maximal inequality". Asymptotically, it is proportional to sqrt(n log log n). This is known as the "law of the iterated logarithm". Find that in the index, too. * To Tapan (1) If you want to work with open sets, you can consider the mapping (f,g):X ----> RxR which sends x to (f(x),g(x)). If add:RxR ----> R is the addition, then (f+g)(x) = (add (f,g))(x). Since add is continuous (exercise), it remains to show that (f,g) is continuous. An open set in RxR is of the form UxV with U,V open in R. If prime means inverse, then (f,g)'(UxV) = f'(U) intersected with g'(V), and this is open since f and g are continuous. (2) If X is a metric space, you can give a more direct proof with sequences. Assume x[n] ----> x in X. Then f(x[n]) ----> f(x) etc. This same proof works also if X is not a metric space, if instead of sequences you use nets (= generalized sequences). See the books on general topology by Kelley or Willard for nets. * John to all (a new largest prime number) EAGAN, Minn., Jan 10 (Reuter) - Scientists announced Monday they have discovered the largest prime number found to date -- a 258,716-digit behemoth that would take eight newspaper pages to print. Prime numbers are those that can be divided only by themselves or one. Simple examples are 2, 3, 5, 7 and 11. There are an infinite number of them but they do not occur in a regular sequence, meaning that supercomputers are needed to hunt them. Cray Research Inc said its supercomputer had chased down the new champ number -- two multiplied by itself 859,433 times, minus 1. The previous largest such number, tracked down in 1992 by AEA Technology's Harwell Laboratory in England, had 227,832 digits. The company said such numbers are principally mathematical curiosities. REUTER Last page! * Charles to John [...] [The company said such numbers are principally mathematical curiosities.] To which I reply that this statement by Cray is misleading. From a purely mathematical viewpoint, the understanding of the prime numbers is fundamental. They are the building blocks of the integers, perhaps the fundamental object in mathematics. The most important unsolved question in mathematics is the Riemann hypothesis, which is, in a sense, concerned with the distribution of the prime numbers in the integers. A resolution of this problem would have profound consequences for mathematics. More practically, many encryption algorithms are based on the difficulty of number factorization. If you announced that you had an algorithm which could find the prime factors of a given number much faster than is currently possible, I guarantee you would attract the intense attention of everyone interested in data encryption and verification problems, including various "three-letter" government agencies. So while the actual value of the largest known prime is perhaps a curiousity, the techniques and machinery used to find them are of the greatest theoretical and practical importance. Charles Yeomans * Charles to all (on gaps in Wiles' proof) At the winter meeting of the AMS/MAA, Kenneth Ribet, a professor at Cal-Berkeley, gave a talk on the current status of Fermat's Last Theorem. Here is a very brief summary of what he said. First, recall that what Andrew Wiles announced was a proof of the semistable case of the Taniyama-Shimura conjecture, a conjecture relating elliptic curves over Q and modular forms. It has been known for about seven years by work of G. Frey, J-P. Serre and K. Ribet that an affirmative solution to the conjecture above implies FLT. The importance of this conjecture far outweighs the importance of FLT. There is a gap in Wiles' proof which currently invalidates the part of his work which implies FLT. Even if that gap remains unpatchable, the part of Wiles' work which has been checked constitutes a giant advance in arithmetic geometry. The precise gap is a technical point (though one of importance), and not a problem with the fundamental ideas of Wiles' work. Ribet did not express an opinion on whether or not the gap was fillable, pointing out that Wiles has put in seven years of intensive work in this area and probably has he best idea of the chances of fixing the gap. [Any errors are mine, not Ribet's] Charles Yeomans * Allan to Charles From what I have been able to gather, the 'gap' in Wiles proof DOES lie in one of the fundamental ideas. Wiles had many new techniques. One of these was a NEW technique for calculating bounds on orders of certain cohomology groups In one particular case, the computation was not correct. Wiles now is hard at work trying to correct it, it does not seem to be a matter of simple numerical errors. Most authorities seem to be secure he will be able to fix it perhaps in a few weeks (or months). But we have heard stories before like this regarding FLT theorem, haven't we? Stay tuned, the last chapter of this story hasn't been completed yes!! AT.. --- * I'm looking for a reference book/journal/paper on applications of * nonstandard analysis to the following topics: * General Topology, Measure Theory, Number Theory, Model Theory General Topology: try Robonson's original book, NONSTANDARD ANALYSIS. Measure Theory: a lot of recent work by Peter Loeb (I don't know whether there is a book or not, but certainly papers) Number Theory, ?? seems unlikely to me Model Theory: I would say the application is the other way: the entirety of Nonstandard Analysis is an application of model theory. For the direction you asked: I did once see a proof (by W.A.J. Luxemburg) by nonstandard analysis that Tychonov's theorem for Hausdorff spaces does not require the full Axiom of Choice, but follows from the weaker Boolean Algebra Prime Ideal Theorem [since the BAPIT is enough to establish NSA, and then for Hausdorff spaces no further use of choice is needed to prove Tychonov.] [Gerald E.] --- Gerald! Thanks for the references. In measure theory, I actually want to write a paper on the Loeb Measure, so your reference to Loeb is excellent. I was hoping for a book, as I have access to papers. Anyway, at least you've confirmed the fact to me. In terms of Model Theory, I am about to read the proof on Tychonoff's Theorem using N.A., hence my query if there were any other applications. Number theory was a shot in the dark. Have you read/heard of Moshe Machover in this field? He has written a number of papers in N.A., and has written a classic, along with Bell, called A Course in Math. Logic. Anyway, if you have heard of him, you may be interested to know that he is my supervisor (specially if you work in the field of N.A.). ...Tapan