15
$\begingroup$

I'm looking for an open problem in analysis or number theory with just one "genuine" or "second order" quantifier.

E.g.

  • "Every continuous function $\mathbb{R} \rightarrow \mathbb{R}$ has the property $\theta$", where $\theta$ is expressible using only quantifiers over rationals.

  • "Every set $S$ of natural numbers has the property $\theta$", where $\theta$ is expressible using only quantifiers over rationals.

No cheat examples like "For every real number, Goldbach's conjecture holds"! That's an arithmetical problem.

In technical terms, I'm looking for a $\Pi^1_1$ sentence that we don't know how to reduce to an arithmetical sentence.

I'd also like it to be easy to state and obviously $\Pi^1_1$, so that it can be included in a logic paper without requiring much explanation.

$\endgroup$
16
  • 1
    $\begingroup$ Problems of the form: is there a countable graph with such-and-such first-order property? Is there a countable structure with such-and-such first-order property? Negative answers would have the desired form $\Pi^1_1$. $\endgroup$ Aug 8, 2021 at 12:18
  • 3
    $\begingroup$ $\forall (x,y).\zeta(x+iy)=0\implies x={1\over 2}$ is a natural thing to write, but RH turns out to have a $\Pi^1_0$ form. So your question has subtleties. $\endgroup$
    – none
    Aug 8, 2021 at 17:02
  • 1
    $\begingroup$ I suspect the four exponentials conjecture and some other problems in transcendental number theory could qualify. $\endgroup$
    – Wojowu
    Aug 9, 2021 at 15:35
  • 2
    $\begingroup$ Sorry, what is meant by "genuine" quantifier? Doesn't the term "continuous function" implicitly contain quite a few quantifiers? (EDIT: Oh I see -- the condition that a given function be continuous is arithmetical, so the only analytic quantifier is over the function itself) $\endgroup$
    – Tim Campion
    Aug 9, 2021 at 15:52
  • 1
    $\begingroup$ @TimCampion a continuous function can be presented as a continuous function on rationals. $\endgroup$ Aug 11, 2021 at 10:11

1 Answer 1

4
$\begingroup$

The Littlewood conjecture is an example that meets all my requirements.

It is easy to state and obviously $\Pi^1_1$. Furthermore this comment by Christian Reiher gives me confidence that it has no known reduction to an arithmetical sentence. (Hopefully it even lacks a known reduction to a $\Sigma^1_1$ sentence.)

$\endgroup$
1
  • $\begingroup$ Thanks to everyone that helped, either by suggesting possible answers, or by pointing out that various $\Pi^1_1$ sentences suggested by me or others did in fact have a known reduction to an arithmetical sentence. $\endgroup$ Aug 17, 2021 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.