16
$\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.

Improve this question
$\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$
    – Joel David Hamkins
    Commented 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
    Commented 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
    Commented 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
    Commented Aug 9, 2021 at 15:52
  • 1
    $\begingroup$ @TimCampion a continuous function can be presented as a continuous function on rationals. $\endgroup$
    – Paul Blain Levy
    Commented Aug 11, 2021 at 10:11

1 Answer 1

Reset to default
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.)

Improve this answer
$\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$
    – Paul Blain Levy
    Commented Aug 17, 2021 at 20:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .