- mathfun@mailman.xmission.com - mailman.xmission.com

Re: [math-fun] Re: favorite theorem
by dasimov＠earthlink.net 03 May '06

03 May '06

Franklin wrote: << The normal axioms of set theory don't require [that a set cannot be a member of itself]. I'm not sure which axioms you're thinking of, but the Axiom of Regularity of Zermelo-Frankel set theory (cf. http://en.wikipedia.org/wiki/Axiom_of_regularity) does indeed imply that no set can be a member of itself. --Dan

2 1

Re: [math-fun] Re: favorite theorem
by Schroeppel, Richard 03 May '06

03 May '06

>From Dylan Thurston ... On Sun, Apr 30, 2006 at 11:42:43PM -0400, dasimov(a)earthlink.net wrote: > How would you phrase the theorem(s) you're referring to? I would say something like: Thm. The finite cardinals are in natural bijection with the finite ordinals. The "cardinals" are equivalence classes of sets under bijection, while the "ordinals" have an inductive definition. Unfortunately I don't know how to define "finite" in a natural way. Peace, Dylan

3 2

Re: [math-fun] Re: favorite theorem
by dasimov＠earthlink.net 03 May '06

03 May '06

Gene wrote: << A set is finite if there exists no bijection of it onto one of its proper subsets. . . . >> Maybe a bit simpler is to say either 1. a set X is finite if there is no surjection s: X -> X u {X}, or 2. a set X is finite if there is no injection i: X u {X} -> X. Exercise: Show 1. <=> 2. --Dan

2 1

[math-fun] Emcee++: Rapper to the computer geeks
by Schroeppel, Richard 03 May '06

03 May '06

Henry Baker offers: What computer science graduate school in the Midwest will do to you... Download some "geeksta" rap... http://www.mcplusplus.com/

1 0

[math-fun] Re: Strip mining...
by R. William Gosper 03 May '06

03 May '06

>Zbl 0762.05009 Gosper, William Strip mining in the abandoned orefields of nineteenth century mathematics. (English) [CA] Computers and mathematics, Proc. Int. Conf., Stanford/CA (USA) 1986, Lect. Notes Pure Appl. Math. 125, 261-284 (1990). Hi, Sergey, the reviewer blew it. The correct formula is \sum {n\ge 1}{2^{-n}\over 1+x\^{2^{-n}}}={1 \over \log x}+{1 \over 1-x}. E.g., (c195) sum(2^-n/(1+x^2^-n),n,1,inf) = 1/log(x)+1/(1-x) inf ==== \ 1 1 1 (d195) > ------------ = ------ + ----- / 1 log(x) 1 - x ==== -- n = 1 n n 2 2 (x + 1) (c196) apply_nouns(subst([x = 0.5d0,inf = 64],%)) (d196) 0.55730495911104d0 = 0.55730495911104d0 This is really not deep. You can change it to a finite, telescoping sum of k terms by replacing x by x^2^-k and subtracting. I wonder if we can get the review corrected. Actually, I'm happy it got reviewed at all (English?), since that paper contains an important idea that the world is ignoring. --Bill Gosper PS, I uploaded the Strip-Mining TeX sources and dvis to http://gosper.org/ stanfordn1.tex, ... , stanfordn4.tex You might also enjoy the identities at www.tweedledum.com/rwg/idents.htm

1 0

Re: [math-fun] Re: favorite theorem
by dasimov＠earthlink.net 03 May '06

03 May '06

Jim Propp wrote: << Come to think of it, I was hasty in asserting that the axiom of infinity can't be proved. It seems to me that Cantor's construction of the counting numbers (where 0 is defined as the empty set, 1 is defined as {0}, 2 is defined as {0,1}, 3 is defined as {0,1,2}, etc.) deserves to be called a constructive proof of the existence of an infinite set. It certainly doesn't FEEL like circular reasoning, even if it's unclear how one would formalize it. (Someone who knows more about Bolzano, Dedekind et al. should chime in here.) >> 1. Which reasoning doesn't feel like circular reasoning? 2. Without the Axiom of Infinity, I don't see how the existence of the Cantorian natural numbers implies there's a set whose members they comprise. And I doubt one can prove even the existence of each such number without the A.I. though you can clearly prove that all numbers up to any N exist. 3. I'm not fond of the Axiom of Infinity, either, and it would be very nice if it could be inferred from more natural axioms. --Dan

2 1

[math-fun] Re: favorite theorem
by James Propp 02 May '06

02 May '06

>I think you're mistaken in dismissing this as a "theorem". >Once when I TA'd in a course "math for elementary school teachers" >taught by Leon >Henkin, he went over a proof of this theorem---I thought it was >pretty revealing, (although I have to say it wasn't very appropriate >for the future elementary school teachers, who didn't understand the >point.) I'm glad to hear that I was hasty in dismissing the theorematic nature of the claim. Such a nice claim should have a proof, even if it's rated M ("for (mathematically) Mature audiences only"). Come to think of it, I was hasty in asserting that the axiom of infinity can't be proved. It seems to me that Cantor's construction of the counting numbers (where 0 is defined as the empty set, 1 is defined as {0}, 2 is defined as {0,1}, 3 is defined as {0,1,2}, etc.) deserves to be called a constructive proof of the existence of an infinite set. It certainly doesn't FEEL like circular reasoning, even if it's unclear how one would formalize it. (Someone who knows more about Bolzano, Dedekind et al. should chime in here.) Jim

1 0

[math-fun] "Stable polyhedron" (?) problem
by dasimov＠earthlink.net 02 May '06

02 May '06

I'm not sure of the correct name of this old problem, but it's been around since at least the mid 1800's. (There's a legend about George Boole's discussing this with a teacher.): Does there exist a convex polyhedron P in 3-space such that, if it has constant positive 3D density, then when its center of gravity is projected orthogonally onto the planes of its faces, at least one such projection lies inside the face. (I.e., there is a face F such that if P is placed on F on a horizontal plane under gravity, it won't fall over.) An old heuristic nonexistence proof is that if P existed, then placing P on an infinite plane under gravity would lead to a perpetual motion machine. (I don't find this argument persuasive even in the realm of physics.) But in any case, does anyone know whether this problem has been settled? Reference(s) ? (And what is it called?) Thanks, Dan

4 3

[math-fun] NYTimes: In Sudoku, Nine Little Numbers Add up to a Big Challenge
by Henry Baker 02 May '06

02 May '06

At 04:12 PM 5/1/2006, dasimov(a)earthlink.net wrote: >Henry Baker wrote: > ><< >Notice that the NYTimes huffs at other newspapers that print Sudoku's, because it >doesn't print any itself. >>> > >(I hadn't noticed the huffing -- can you point to a URL, say?) > >Frankly if they're going to print only one additional mind-puzzle, I'd much rather >it were in the form of a recreational math puzzle that varied daily. > >--Dan See article, below. I notice that NYT now has Sudoku in their online, edition, however. http://www.nytimes.com/ref/crosswords/sudoku/easy.html?8qa (For some reason, this hung my Mozilla Firefox browser.) BTW, I did a Google search on "sudoku" and "direct product", but didn't come up with anything interesting. Since 9=3*3, isn't it possible that at least some Sudoku's are direct product constructions? Aren't at least some Sudoku's the product table of a 9-element group? ----- http://www.nytimes.com/2006/05/01/arts/01conn.html The New York Times May 1, 2006 Connections In Sudoku, Nine Little Numbers Add up to a Big Challenge By EDWARD ROTHSTEIN "When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth." Â Sherlock Holmes When it comes to sudoku, there is no escape. The grids of these puzzles seem to shut down the mental apparatus, enclosing one's faculties in a tightly constrained universe Â a 9 by 9 array that must be carefully filled up with the numbers 1 to 9, following certain rules. That enclosure is hypnotic. Publisher's Weekly recently counted 23 sudoku books in print with total sales of 5.7 million copies. Newspapers wage circulation wars by running sudoku in their pages. And sudoku Web sites and forums proliferate internationally (for example, see sudoku.jouwpagina.nl). The teams in the first World Sudoku Championship Â held in Lucca, Italy, in March Â came from 22 countries, including the Philippines, India, Venezuela, and Croatia. The winner was a 31-year-old woman, a Czech accountant. The Independent of London recently reported that a 700 percent increase in the sale of pencils has been attributed to the sudoku craze. Last November, British Airways sent a memo to all its cabin crews, forbidding them to work on sudoku puzzles during takeoffs and landings. The international appeal, of course, may have something to do with the fact that no language is needed to solve sudoku puzzles; neither, for that matter, is any mathematics. The puzzler is given an 81-square grid, with about 20 squares filled in (the "givens"). That large grid is itself divided into nine 3 x 3 grids. The challenge is to fill in the blanks so that each nine-cell row, each nine-cell column and each nine-cell mini-grid contains all the numbers from 1 to 9, with no repetitions or omissions. This is not a novel challenge. Magic squares of various kinds were part of many ancient cultures. Benjamin Franklin published a paper about magic squares, and he obsessively fiddled with them during the same years he was helping to form a more perfect union. The 18th-century Swiss mathematician Leonhard Euler studied the properties of Latin Squares in which each row and column would contain a complete list of the elements of a set of numbers or letters. Sudoku-style puzzles Â which add the twist of the mini-grids within a larger array Â were titled Number Place when they began appearing anonymously in 1979 in the periodical Dell Pencil Puzzles and Word Games. Will Shortz, the crossword puzzle editor of The New York Times, deduced the author's identity with sudoku-style argument: anytime the Dell publication contained one of these puzzles Â and never otherwise Â the list of contributors included Howard Garns, an architect from Indianapolis; Mr. Garns died in 1989. The American-born puzzles made their way to Japan in 1984, where the publisher Nikoli ended up calling them sudoku Â meaning single numbers. And in 1997, Wayne Gould, a New Zealander who had served as a judge in Hong Kong, came across them while vacationing in Tokyo. In 2004 he successfully lobbied The Times of London to introduce the puzzles to Britain, beginning the craze in the West. Strangely, in Japan, where Nikoli has trademark control over the name sudoku, the puzzles are still familiarly known by the English title Number Place, while in the English-speaking work, their Japanese pedigree is widely assumed. But what is their lure? A mathematician I spoke with dismissed the puzzles as mere "bookkeeping" Â keeping track of where things go. And there surely is some of that, since one technique for solving them involves tentatively writing miniature numbers in each little square to figure out the various possibilities. The grid for a difficult puzzle can begin to look like the first draft of a major corporation's balance sheet. This is hardly higher mathematics. In fact, numbers are hardly necessary: the same puzzle can be posed using nine colors or nine national flags. Yet mathematicians have been taking more of an interest in sudoku Â not necessarily in solving the puzzles, but in understanding more about their character. In a recent essay in The American Scientist, Brian Hayes described the difficulty of determining the difficulty of these puzzles: it bears little connection with how many numbers are given at the start. And while numbers are really not that important to sudoku itself, they certainly proliferate in discussions about it. In MathWorld, an online mathematical journal (mathworld.wolfram.com) Eric W. Weisstein cited research showing that 6,670,903,752,021,072,936,960 completed grids are possible for sudoku puzzles, though only 5,472,730,538 unique grids remain once equivalent solutions are eliminated. In a September 2005 column by Ed Pegg Jr. on the site of the Mathematical Association of America (maa.org/news/mathgames.html) also pointed out that the graph theorist Gordon Royle had collected more than 10,000 sudoku puzzles, each with 17 givens. That may be the smallest number of givens that will yield unique solutions (any fewer givens will allow multiple answers), though apparently that hypothesis has not yet been proven. The exhaustive Wikipedia article on sudoku goes into even greater detail (en.wikipedia.org/wiki/Sudoku) What many of these studies focus on, though, is how many sudoku possibilities there are. Each puzzle, using only the simplest of elements, combined according to the simplest of rules, pulls a single solution out of a mind-boggling number of possibilities. The puzzle is an act of reduction and elimination. Often, in solving a puzzle, we work toward an answer, accumulating information. Something must be calculated or produced. In a crossword puzzle, the words have to be pulled out of one's experience. Here, though, each square has only nine possibilities and the work mainly involves not finding the possible but eliminating the impossible, filtering away everything that does not fit Â ruling out the number 4 for a particular square, for example, if a 4 appears in the same row or column or mini-grid. Sudoku does not open up into the world; it reduces the world to its boundaries, forcing everything extraneous to be discarded. There is something more technological about it than mathematical: we know what we must produce; the problem is in getting rid of everything that doesn't fit. This must help account for sudoku's tremendous appeal: it seems to distill complication into elemental clarity, even when that task becomes difficult. On the blog onigame.livejournal.com, the puzzle master Wei-Hwa Huang (who came in third at the world competition in March) devised a unusual system, using colored loops, for solving sudoku that is more knotty than seems possible given the puzzle itself. But the solution is still something easily understood once complete. And it is always immensely satisfying, because finally, all impossibilities have been eliminated, leaving behind a neat array of 81 numbers, that however improbably reveal the trivial truth. Connections, a critic's perspective on arts and ideas, appears every other Monday.

1 0

Misattribution Re: [math-fun] Don't hire authoritarian programmers
by dasimov＠earthlink.net 01 May '06

01 May '06

I should've attributed the quote in previous e-mail to Henry (not Bill G.). My apologies.

1 0