April 2005 - mathfun@mailman.xmission.com

[math-fun] Infinite epsilon-chains (set theory)
by Daniel Asimov 21 Apr '05

21 Apr '05

On of the Zermelo-Frankel axioms for set theory (the Axiom of Regularity, aka the Axiom of Foundation) implies the nonexistence of left-infinite epsilon chains. Let eps denote set membership. Then Regularity implies there is no function f with domain Z+ such that for all n, f(n+1) eps f(n). I'm not at all convinced this is a necessary condition for set theory. If you think of a set as a matryoshka (babushka) doll, there seems no problem in conceiving of an inwardly nested sequence of dolls indexed by Z+. E.g., the spheres of radius 1 + 1/n about 0 in R^3 for n = 1,2,3,.... The objection to such a situation seems to be that a set S with a left-infinite epsilon-chain is not ultimately "founded" on anything -- which I agree is a bit troubling. But such a set S seems analogous to the concept that time has no beginning, that it might locally correspond to all real numbers less than "now". This too is a bit troubling, but imo by no means beyond the realm of possibility. ------------------------------------------------------------------------ Another consequence of Regularity is the nonexistence of (finite) circular epsilon chains: A_1 eps A_2 eps ... eps A_n eps A_1. This I find even less palatable than a left-infinite epsilon-chain -- but not enough to want to ban it. Because, topologically it's easy to conceive of a finite set of circularly-nested matryoshka dolls: (Let S_k be the sphere of radius k about 0 in R^3. Now let X be all the space between S_1 and S_(n+1), inclusive. Now identify S_(n+1) with S_1 by central projection to get a quotint spac Y of X. Then Y has a finite circular sequence of spheres S_1,...,S_n, each "contained" within the next.) ----------------------------------------------------------------------------- What do others think of possibly tossing out Regularity as a set theory axiom? --Dan

3 2

Re: [math-fun] Infinite epsilon-chains (set theory)
by Daniel Asimov 21 Apr '05

21 Apr '05

Mike, my first concern is that one can still prove everything important that used to be provable. Fwiw, I've found assertions in Wikipedia (which for those who don't know it is an amazingly good source of math info: www.wikipdia.com) saying that without Regularity, virtually everything that was true for ordinary sets still is. I don't know what to say about the examples you bring up. If there were a concrete example of something that ought to be true, but without Regularity seems impossible to prove, then I'd say there is a problem. --Dan ----------------------------------------------------------------- Mike Speciner writes: << Intuitively, you prove things by induction by showing it true in one place (typically the null set), and then showing it true for the "next", and so on. Equivalently, you assume the "least" place where something is false, and then find a smaller example. But with sets that can chase their own tail, how do you do either? If you start somewhere and go "upwards", you never create a set which chases its own tail. If you start with such a set, you can't necessarily find a smaller thing. Note that for set theory, we do transfinite induction. Integers are merely countable. Daniel Asimov wrote: > Mike, can you give an example of where a problem might arise? > > Ordinary induction is one of the Peano Axioms for the integers. > Would this be torpedoed by tossing out Regularity? > > Mike Speciner asks: > << > Well, Dan, how would you do induction? Or can you do without it? > > Dan Asimov wrote: > << > . . . > . . . > What do others think of possibly tossing out Regularity as > a set theory axiom? > >> >>

1 0

Re: [math-fun] Infinite epsilon-chains (set theory)
by Daniel Asimov 20 Apr '05

20 Apr '05

Mike, can you give an example of where a problem might arise? Ordinary induction is one of the Peano Axioms for the integers. Would this be torpedoed by tossing out Regularity? Mike Speciner asks: << Well, Dan, how would you do induction? Or can you do without it? Dan Asimov wrote: << . . . . . . What do others think of possibly tossing out Regularity as a set theory axiom? >> >> --Dan

2 1

Re: [math-fun] Density question
by David Gale 20 Apr '05

20 Apr '05

This is old news by now but re that question about density one half, (A) Dan's proof is fine but a more general statement has a proof which is almost two-liner and doesn't need anything as deep as Lebesgue density. A couple of people C. Gardner and Y. Peres pointed out the following: _____________________________________________________________________ I write A(int)B for intersection, and m(S) for outer measure of S. THEORM.There is no set S (measurable or not) in [0,1] with the property that m(S(int)[a,b]) = (b-a)/2 for all intervals [a,b] in[0,1]. FACT; Every open set in R is a countable union of DISJOINT open intervals. Proof of Theorem. Assume S exist. Then m(S)=1/2, so there is an open set O containing S with 1/2<m(O) < 2/3. Using FACT, O is union of disjoint intervals J (where J will stand for the interval and also its length), but by assumption m(S(int)J)= J/2 so by subadditivity of outer measure m(S)<Summation(J/2) < 1/3<1/2, contradiction. At 09:42 PM 4/18/2005, you wrote: >1. A point of density of a set is a point such that for small enough >neighborhoods, the density of the set in that neighborhood is arbitrarily >close to 1. I.e. every neighborhood smaller than delta has 99.99% of >points in the set, etc. The Lebesgue density theorem asserts that almost >every element of any measurable set is a point of density. > I.e. for any measurable subset of R (or any other space) almost every > point has neighborhoods with density approaching 1 or density approaching > 0. This is a fundamental principle of measure theory, I think it is (or > at least it should be) in the basic texts. It really comes from the way > measure is defined. > >2. You can take an irrational rotation of the circle R/Z like x -> x + >sqrt(2). The orbits of this rotation are all isomorphic to Z --- i.e. >points never return to themselves. Pick a point from each orbit, using the >axiom of choice. Partition the orbit into the even images and the odd >images of this point. The union of all odd points in all orbits is "half" >the circle in the sense that its congruent by a translation to its >complement. In fact you can take odd powers of the rotation arbitrarily >close to the identity, so you can make the set match its complement by an >arbitrarily small rotation. This example is covered by an example in R >--- you could think of this as taking any action of Z^2 (or Z^k would also >work) by translations on R with dense orbits, then partitioning the orbits >into cosets of a subgroup of index 2 acting on a selected point. > >It's known that there's no definition or rule or humanly comprehensible >procedure to actually make such a selection. > Bill >On Apr 18, 2005, at 9:24 PM, Michael Kleber wrote: > >>Dan Asimov wrote: >> >>><< >>>Can someone give me an example of a set of density 1/2 on every >>>interval of the real numbers? >>> >>>If such a set must be measurable, then no such set exists. >>> >>>On the other hand, there do exist partitions of the reals into >>>two dense homogeneous subsets that are related by a translation. >> >>Probably I should know why both of these are true, but right now >>it seems that I don't. Can you explain? >> >>--Michael Kleber >> >>ps: "all reals whose last digit is even" :-? >> >>-- >>It is very dark and after 2000. If you continue you are likely to be >>eaten by a bleen. >> >>_______________________________________________ >>math-fun mailing list >>math-fun(a)mailman.xmission.com >>http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

RE: [math-fun] Density question
by Daniel Asimov 20 Apr '05

20 Apr '05

David WIlson asks: << Can someone give me an example of a set of density 1/2 on every interval of the real numbers? >> If such a set must be measurable, then no such set exists. On the other hand, there do exist partitions of the reals into two dense homogeneous subsets that are related by a translation. --Dan A.

6 7

RE: [math-fun] 'Mersenne Numbers' snapshot of 1990
by Schroeppel, Richard 20 Apr '05

20 Apr '05

I'm glad to see this on the web! Guy, is it practical to convert it to either an ascii file, or tex? One notable omission is Speciner's work at MIT AI Lab c. 1970, using Schonhage-Strassen (now days we call this Karatsuba). He was beaten out by Gillies in finding M19937, showing that the faster machine sometimes beats a better algorithm. I looked at Chris Caldwell's page on prime number records by date, mwntioned below. He supposes that Fermat probably knew that 223 | M29, since he knew the theorem about factors of Mp being 2kp+1, and that 47 | M23 and 233 | M37. I've come across some contradictory indications, but can't point to the source. It may be in some of Bell's biographical work, maybe The Last Problem. Another curiosity on Caldwell's page is a remark (by Robinson?) about his SWAC program that found M521,607,1279,2203, and 2281: It was Robinson's first program, and it worked the first time. This is hard to credit. Did SWAC provide builtin bugnums? The program must have been either in machine code or assembly language. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com on behalf of Guy Haworth Sent: Wed 4/20/2005 4:00 AM To: math-fun(a)mailman.xmission.com Subject: [math-fun] 'Mersenne Numbers' snapshot of 1990 After an overlong delay following Richard Schroeppel's kind return-supply of a copy of my 'Mersenne Numbers' notes of 1983-1990, I have scanned them in to text-searchable pdf. They are available at http://www.cs.reading.ac.uk/people/G.Haworth.htm?publications and specifically as http://www.cs.reading.ac.uk/common/publications/02116.pdf This is the 22/01/90 version, and so a retrospective, looking back 15 years. Please use as you see fit. If my scanning technique or technology proves to be significantly off the pace, I'll rescan. I suppose it might be worth building a database, off which review-reports of this kind might be derived. So I am interested in views of how to update the content, information management and presentation. I'm also trying to find a copy of my 'Mersenne Numbers: Consolidated Results' which covered the collation of previous results, together with the ICL DAP's second-sourcing and occasional correction of those results. Incidentally, Mersenne's conjecture about prime M(p) with p between 1 million and 2 million was disproved in 1996 with: M(1,257,787), the 34th prime M(p) and M(1,398,269), the 35th prime M(p) I attended the Celebration of David Wheeler's work at Cambridge University's Computer Laboratory on Monday. There was brief mention of the Miller/Wheeler paper in Nature(1951) [v168, p868] which "ushered in the computer-age of prime-finding" . I see others agree ... http://primes.utm.edu/notes/by_year.html#MW The footnote is that their program was used to test the integrity of EDSAC 1. Guy _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

[math-fun] sequences from Hilbert's 16th problem?
by N. J. A. Sloane 20 Apr '05

20 Apr '05

Dear Math-Fun and Seqfans, In his 2002 survey, MR1898209 (2003c:34001) Ilyashenko, Yu. Centennial history of Hilbert's 16th problem. Bull. Amer. Math. Soc. (N.S.) 39 (2002), no. 3, 301--354 (electronic). (Reviewer: Lubomir Gavrilov) 34-02 (34C07 37C10 37F75) the author mentions that Petrovskii and Landis gave an incorrect proof that the Hilbert number H(n) is bounded above by P_3(n), "a certain polynomial of degree 3 [in n]". The reference is to: MR0073004 (17,364d) Petrovski\u\i, I. G.; Landis, E. M. On the number of limit cycles of the equation $dy/dx=P(x,y)/Q(x,y)$, where $P$ and $Q$ are polynomials of 2nd degree. (Russian) Mat. Sb. N.S. 37(79) (1955), 209--250. My question is, what is this sequence P_3(n) ? Later in the article Ilyashenko mentions a second Hilbert-type sequence E(n) (on page 305). Same question. NJAS

2 1

[math-fun] 'Mersenne Numbers' snapshot of 1990
by Guy Haworth 20 Apr '05

20 Apr '05

After an overlong delay following Richard Schroeppel's kind return-supply of a copy of my 'Mersenne Numbers' notes of 1983-1990, I have scanned them in to text-searchable pdf. They are available at http://www.cs.reading.ac.uk/people/G.Haworth.htm?publications and specifically as http://www.cs.reading.ac.uk/common/publications/02116.pdf This is the 22/01/90 version, and so a retrospective, looking back 15 years. Please use as you see fit. If my scanning technique or technology proves to be significantly off the pace, I'll rescan. I suppose it might be worth building a database, off which review-reports of this kind might be derived. So I am interested in views of how to update the content, information management and presentation. I'm also trying to find a copy of my 'Mersenne Numbers: Consolidated Results' which covered the collation of previous results, together with the ICL DAP's second-sourcing and occasional correction of those results. Incidentally, Mersenne's conjecture about prime M(p) with p between 1 million and 2 million was disproved in 1996 with: M(1,257,787), the 34th prime M(p) and M(1,398,269), the 35th prime M(p) I attended the Celebration of David Wheeler's work at Cambridge University's Computer Laboratory on Monday. There was brief mention of the Miller/Wheeler paper in Nature(1951) [v168, p868] which "ushered in the computer-age of prime-finding" . I see others agree ... http://primes.utm.edu/notes/by_year.html#MW The footnote is that their program was used to test the integrity of EDSAC 1. Guy

1 0

[math-fun] screwy sequence
by R. William Gosper 19 Apr '05

19 Apr '05

Numerical experiments suggest that, for m = 1..9, ..., f(m) := inf ==== m k \ %pi (k 2 - 5) n (- 1) > tan(--------------) (- 1) inf / n + m ==== ==== 2 5 m - 1 \ n = 1 3 2 > --------------------------------------- / m ==== m 3 10 %pi (k 2 - 5) k = - inf (k 2 - 5) csc(-----------------) 2 m 2 ------------------------------------------------------------ 3 5 %pi %pi csc(-----) m 2 = 2, 8, 32 - sqrt(2), 113, 382, 833, 1822, 3713, 7582, ... --rwg

2 4

[math-fun] A better name for math-funners?
by Daniel Asimov 19 Apr '05

19 Apr '05

We've never decided on a nice word to mean math-funner. Math-funner is the default, but it seems to lack panache. Someone has also used munster. Not ruling anything out, including the above, do people feel like making suggestions, just in case one of them receives wide acclaim??? IN ORDER TO avoid influencing each other, I suggest all submissions be e-mailed directly to me at dasimov(a)earthlink.net without posting to math-fun. Please include the above subject line in your subject line. I will then post all submissions received by 6 am EDT, Monday April 25, in the order of receipt. Multiple submissions are fine. Perhaps we could then vote on whether we want to adopt one of them. (Though a mere plurality, or even majority, vote doesn't seem sufficient for adoption.) --Dan

1 0