We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we decide to ask it here:
$$ \Xi_A = \{ n \in N \mid \exists k^2 \in A : k^2 \leq n \}, \quad A \text{ is an arbitrary r.e set.}$$
The multiple choice is as follows:
I) $ \Xi_A$ is decidable.
II) $ \Xi_A$ is r.e but is not decidable.
III) $ \Xi_A$ is not an r.e set, but complement of $ \Xi_A$ is r.e set.
IV) $ \Xi_A$ just only is r.e when $A$ be r.e-complete.
The questioner say which is choice is correct? infact we never see this type of question. powerful person that is on MSE site, would you please help us in negotiating with this question?
Edit 1: some of student says I is correct, but just guess after interview :)
Assuming the definition is really $$ \Xi_A = \{ n \in N \mid \exists k \in A: k^2 \leq n \} $$ (because $\exists k^2\in A$ is not syntactically well-formed), then the answer is (I): $\Xi_A$ is decidable no matter what $A$ is.
This is a well-known family of "trick questions", where the underlying point is that whether a set is decidable (or not) or r.e. (or not) depends only on what its elements are -- not on how the set is defined.
In this case there are two possibilities:
Either $A$ is empty. In that case $\Xi_A$ is empty too, and the empty set is trivially decidable.
Or $A$ contains a smallest element $k_0$. In that case $\Xi_A$ is the same set as $\{n\in\mathbb N\mid n\ge k_0^2\}$. This is trivially decidable too -- you just build the number $k_0^2$ into the deciding program as a literal constant and compare to it.
If the definition of $A$ is complicated (or it's just a random set that doesn't have a definition), we may not know which of these two cases hold -- or what $k_0$ is in the second case. But we can know that some program that happens to decide exactly the set $\Xi_A$ exists, even if we can't know which program that is.
Note that we don't need to assume that $A$ is r.e. for this argument to work -- it is true for every $A\subseteq \mathbb N$, even ones that are not r.e. or not arithmetical.