# [FOM] Wolfram and intermediate degrees

Harvey Friedman friedman at math.ohio-state.edu
Wed Jun 25 04:04:15 EDT 2003

```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

```