Re: theorems/problems with lots of quantifiers
From: The Last Danish Pastry (clivet_at_gmail.com)
Date: 09/07/04
- Next message: David C. Ullrich: "Re: Norm of Fractal Function"
- Previous message: David C. Ullrich: "Re: Co-re set with no infinite r.e. subset"
- In reply to: Mitch Harris: "theorems/problems with lots of quantifiers"
- Next in thread: Mitch Harris: "Re: theorems/problems with lots of quantifiers"
- Reply: Mitch Harris: "Re: theorems/problems with lots of quantifiers"
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 7 Sep 2004 12:43:40 +0100
"Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message
news:2q5dqdFr1envU1@uni-berlin.de...
> Most mathematical theorems and conjectures seem to have low quantifier
> depth, that is, the nesting of quantifiers is not very deep.
>
> For example, if you formalize the fundamental thm of arithmetic, you
> get something like "for all integers n, there exists a unique
> factorization into primes".
>
> However, I would like to have some examples of not too obscure, fairly
> accessible problems (conjectures or thms) where it -is- nested deeply.
>
> For example, the pumping lemma for regular languages (notorious to
> students of automata/computability) has (at least) 4 quantifiers.
>
> I suppose I care more about "natural" problems rather than
> er..."unmotivated" ones.
>
> (I suppose a related notion is algorithmic problems with running time
> a higher degree polynomial: most of the algorithms we care about are
> degree 3 or less. what are some high degree ones? like the latest n^12
> primality testing, or some of those n^6 group theory algorithms)
If x and the a_i's are integers it is true that:
(Ax)
((Ea_1)((Ea_2)((Ea_3)((Ea_4)((Ea_5)((Ea_6)((Ea_7)((Ea_8)((Ea_9)
((Ea_10)((Ea_11)((Ea_12)((Ea_13)((Ea_14)((Ea_15)((Ea_16)((Ea_17)
((Ea_18)((Ea_19)((Ea_20)((Ea_21)((Ea_22)((Ea_23)((Ea_24)((Ea_25)
((Ea_26)((Ea_27)((Ea_28)((Ea_29)((Ea_30)((Ea_31)((Ea_32)((Ea_33)
((Ea_34)((Ea_35)((Ea_36)((Ea_37)
(x=a_1^5+a_2^5+a_3^5+a_4^5+a_5^5+a_6^5+a_7^5+a_8^5+a_9^5+
a_10^5+a_11^5+a_12^5+a_13^5+a_14^5+a_15^5+a_16^5+a_17^5+
a_18^5+a_19^5+a_20^5+a_21^5+a_22^5+a_23^5+a_24^5+a_25^5+
a_26^5+a_27^5+a_28^5+a_29^5+a_30^5+a_31^5+a_32^5+a_33^5+
a_34^5+a_35^5+a_36^5+a_37^5)
)))))))))))))))))))))))))))))))))))))
-- Clive Tooth http://www.clivetooth.dk
- Next message: David C. Ullrich: "Re: Norm of Fractal Function"
- Previous message: David C. Ullrich: "Re: Co-re set with no infinite r.e. subset"
- In reply to: Mitch Harris: "theorems/problems with lots of quantifiers"
- Next in thread: Mitch Harris: "Re: theorems/problems with lots of quantifiers"
- Reply: Mitch Harris: "Re: theorems/problems with lots of quantifiers"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
