May 2006 - mathfun@mailman.xmission.com

Re: [math-fun] quantifier depth
by dasimov＠earthlink.net 07 May '06

07 May '06

Rich writes: << What's the maximum quantifier depth for doing everyday mathematics? . . . So it looks like routine math might use a maximum depth of 8 or so. Presumably there are a few specialties that go much deeper. (?) Evaluating a game tree is an example. >> The theorem T(n): "For every finite perfect information 2-player game of maximum length n, one player has a strategy" has the following proof ***for each n***, in which F1, S3, etc., mean the First player's 1st play, the Second player's 3rd play, etc. ~[(all F1) (exist S1) (all F2) (exist S2) . . . (all Fn) (exist Sn) such that S wins] <=> (exist F1) (all S1) (exist F2) (all S2) . . . (exist Fn) (all Sn) such that F wins. This is depth 2n, of course. Is there a way to prove the obvious fact: (all n) T(n) within the same elementary logic system (set theory?) by, say, induction? In any case, is it true that the theorem (all n) T(n) requires arbitrarily high depth? Or is there a more direct proof of (all n) T(n) ? --Dan

1 0

[math-fun] quantifier depth
by Schroeppel, Richard 06 May '06

06 May '06

What's the maximum quantifier depth for doing everyday mathematics? I count groups of quantifiers of the same type as 1, so that a block of variables of the shape (all x,y,z), or the statement that there's a magic square of size 3x3 (exists a,b,c,d,e,f,g,h,i) are counted as one quantifier. So I'm really talking about Alternating Quantifier Depth. The definition of "a function f is continuous at a point x" has depth 3: (all epsilon) (exists delta) (all y) 0 < |y-x| < delta => |f(y)-f(x)| < epsilon and "f is continuous" is also depth 3: (all x,epsilon) (exists delta) (all y) etc. etc. The theorem that "the sum of continuous functions is continuous" is depth 5: (all f,g) (exists h) (all x,epsilon) (exists delta) (all y) h(x) = f(x)+g(x) And { 0 < |y-x| < delta => ... } So it looks like routine math might use a maximum depth of 8 or so. Presumably there are a few specialties that go much deeper. (?) Evaluating a game tree is an example. Rich

2 1

[math-fun] Ma & Pa Kettle: 5 * 14 = 25
by Marc LeBrun 06 May '06

06 May '06

A friend sent me a .wmv file of an amusing clip where Ma & Pa Kettle give multiple proofs that 25 / 5 = 14. For those interested, I'd enjoy forwarding a link to it, but I don't know where to find it on the Internet. If any of you know, please clue me in. Thanks!

2 1

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

04 May '06

Michael Kleber wrote: << > A set is finite if there exists no bijection of it onto one of its > proper subsets. Unfortunately, that's not true. Or rather, there are models of set theory in which this definition ("Dedekind-finite") is equivalent to the usual notion of "finite", but there are others in which it is not. The Axiom of Choice is more than enough to imply they are equivalent, but that seems like much more than you want to get into if you're looking for beautiful stand-alone theorems. >> Actually, in suggesting the exercise [that boils down to] There is an injection i: X u {X} -> X <=> There is a surjection s: X -> X u {X}, it struck me that the => direction is simple enough, but the <= direction seems to require the Axiom of Choice. I.e., =>: ----------- Define a surjection S_i: X -> X u {X} via S_i(x) = i^(-1)(x), if x is in Im(i); else S_i(x) = X. But for <=: ------------- Define an injection I_s: X u {X} -> X via I_s(x) = some member of s^(-1)(x), if x is in s^(-1)(X); else I_s(x) = some member of s^(-1)(X). (I'm not sure how to get around the use of AC in <=.) --Dan

2 1

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

04 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 04 May '06

04 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