2
$\begingroup$

Let $\mathbb{N}$ denote the set of positive integers. We define a relation $R \subseteq \mathbb{N}^4$ in the following way:

$(p,q,n,s)\in R$ if and only if there is $S\subseteq [0,1]^n$ with $|S| = s$ such that for all $x\in [0,1]^n$ there is $y\in S$ such that $\| x-y \|< \frac{p}{q}$.

Question. Is $R\subseteq \mathbb{N}^4$ computable?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Wojowu
    Commented Jan 9, 2023 at 12:44
  • $\begingroup$ Observe that $(p,q,n,s)\in R$ precisely when there is some $S\subseteq[0,1]^n$ with $|S|=s$ and $d(S,[0,1]^n)<\frac{p}{q}$ where $d$ denotes the Hausdorff metric. $\endgroup$
    – Joseph Van Name
    Commented Jan 9, 2023 at 19:18

1 Answer 1

Reset to default
5
$\begingroup$

The question whether $(p,q,n,s)\in R$ in any instance can be expressed as a sentence in the language of the structure $\langle\mathbb{R},+,\cdot,0,1,<\rangle$, a real-closed field, and by Tarski's theorem on real closed fields, there is a computable uniform decision procedure to decide the truth of all such sentences.

See further description at my answer to a related question.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you briefly describe how you get around the fact that you are quantifying over the dimension (which you mention in your linked answer as something you're "not allowed to do")? $\endgroup$
    – Kevin Casto
    Commented Jan 10, 2023 at 5:47
  • $\begingroup$ @KevinCasto Yes, this is a subtle point. Each particular instance statement $(p,q,n,s)\in R$ does not quantify over the dimension. Different statements have different dimensions $n$, yes, but given any input $(p,q,n,s)$, I can write down the sentence in the language of ordered fields, and ask the Tarski algorithm if it is true. $\endgroup$
    – Joel David Hamkins
    Commented Jan 10, 2023 at 9:36

You must log in to answer this question.

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