Return to Answer

Proof. Suppose that there were such a procedure in the case $n=1$. Let $K_0=[0,2]$, $K_1=[0,1)$ and $K_2=[1,2]$. The algorithm will halt in finitely many steps, having made queries about reals $q_0$, $q_1$, ... $q_n$, and stating that one of the sets, lets suppose $K_1$, is convex, which is true. Consider now the modification of the sets by selecting a point $r>2$ such that no $q_i$ is in the interval $(2,r]$. Let $K_0'=[0,r]$, $K_1'=[0,1)\cup\{r\}$ and $K_2'=[1,r)$. Since the answers to the queries about the $q_i$ are exactly the same for this configuration as in the original problem, the algorithm will again say that $K_1'$ is convex, but in this case, it would be incorrect. QED

Proof. Suppose that there were such a procedure in the case $n=1$. Let $K_0=(0,2)$, $K_1=(0,1)$ and $K_2=[1,2)$. The algorithm will halt in finitely many steps, having made queries about reals $q_0$, $q_1$, ... $q_n$, and stating that one of the sets, lets suppose $K_1$, is convex, which is true. Consider now the modification of the sets by letting $r$ be the largest $q_i$ below $2$ (or $\frac32$, whichever is larger), and using $K_1'=(0,1)\cup (r,2)$ and $K_2'=[1,r]$. Since the answers to the queries about the $q_i$ are exactly the same for this configuration as in the original problem, the algorithm will again say that $K_1'$ is convex, but in this case, it would be incorrect. QED

Theorem. In the $\mathbb{Q}^n$ formalization, in the context where the input sets $K_1$ and $K_2$ might both be convex, then there is no computable procedure that will always work.

Theorem. In the $\mathbb{Q}^n$ formalization, in the context where the input sets $K_1$ and $K_2$ might both be convex (and in such a case only, we allow the boundary to be a hyperplane), then there is no computable procedure that will always work.