[FOM] Wolfram and intermediate degrees

[Harvey Friedman]

Reply to Baldwin 8:24PM /24/03.

>Harvey wrote
>>
>>What is the least number of quantifiers needed for a sentence in 
>>one binary relation symbol to have a set of consequences in the 
>>same language, of INTERMEDIATE DEGREE?
>>
>>CONJECTURE: At least 8.

>...With my tongue slightly in my cheek,
>I propose a different resource bound
>
>How many variables are needed for a set of sentences in one binary 
>relation symbol to have a set of consequences in the same language, 
>of INTERMEDIATE DEGREE?
>
>
>Answer.  If I count correctly 3.   Let X be a set of intermediate 
>degree.  Assert A) S is the graph of a 1-1 and onto function and B) 
>add the sentence: "there is a cycle of length n if n is in X.  and 
>C)  add the sentence: "there is no cycle of length n if n is not  in 
>X.
>By standard tricks each of the last sentences uses only three 
>variables (although the quantifier complexity is unbounded.)

"tongue slightly in my cheek" makes sense since your INFINITE set of 
sentences goes in the opposite direction to what I was driving at...

Nevertheless, this business of the number of VARIABLES needed to 
express things in predicate calculus (with equality) is an 
interesting topic about which I gather there is a lot of literature. 
The number of variables might be very small but the number of 
quantifiers might be enormous.

Could you give us a brief guide to it, including some highlights?

Harvey Friedman