Re: theorems/problems with lots of quantifiers

From: Aatu Koskensilta (aatu.koskensilta_at_xortec.fi)
Date: 09/07/04 

Date: Tue, 07 Sep 2004 17:58:55 +0300

Mitch Harris wrote:

> Most mathematical theorems and conjectures seem to have low quantifier
> depth, that is, the nesting of quantifiers is not very deep.
>
> However, I would like to have some examples of not too obscure, fairly
> accessible problems (conjectures or thms) where it -is- nested deeply.

You need to specify what sort of language you wish these conjectures or
theorems to be expressed in or alternatively what sort of objects do you
accept quantification over. All arithmetical problems, for example, can
be expressed using just one universal quantifier binding a function
variable and one existential quantifier binding a number variable.
Obviously this is not what you're after. 

-- 
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Relevant Pages

  • Re: theorems/problems with lots of quantifiers
    ... > depth, that is, the nesting of quantifiers is not very deep. ... theorems to be expressed in or alternatively what sort of objects do you ... variable and one existential quantifier binding a number variable. ...
    (sci.logic)
  • Re: theorems/problems with lots of quantifiers
    ... > depth, that is, the nesting of quantifiers is not very deep. ... theorems to be expressed in or alternatively what sort of objects do you ... variable and one existential quantifier binding a number variable. ...
    (sci.math)
  • Re: Theory of groups with functions - Help on a question
    ... This is sort of a misuse of the existential quantifier. ... The original problem is arguably mis-phrased. ... constants 'a','b','c' (from the beginning of the alphabet). ...
    (sci.logic)
  • Re: /^From:.*?([w.-]+@[w.-]+)/
    ... A> optional and non-greedy. ... the other is a modifier (makes the previous quantifier ... don't assume any sort of relationship because of the use of ...
    (comp.lang.perl.misc)