This phenomenon occurs both positively and negatively in
many parts of logic, but to my knowledge, there is no
particular adjective that is always used in such
situations.
- In classical computability theory, the phenomenon does not
occur. If one can computably test membership in a set, in
the usual Turing sense, then one can computably generate
an instance, simply because one can computably enumerate
all objects in the domain of discourse, and systematically
test them. This is related to the classical fact that if the graph of a
function is decidable, then the function is computable.
Thus, to my mind, the phenomenon is intimately
wrapped up with the ability to effectively enumerate, in the relevant sense, the
objects in the domain of discourse.
- In complexity theory, there is a sense in which there are
negative examples. One can imagine a polynomial-time
decidable set $A$, all of whose members are very large,
and hence difficult to produce. To make the problem
precise, however, one should really have a sequence $A_n$
of sets such that membership $x\in A_n$ is polynomial
time decidable in $(x,n)$---that is, uniformly in
$n$---but such that there is no polynomial time
computable function $f$ such that $f(n)\in A_n$. Such an
example is provided simply by the sets $A_n$ consisting
of all numbers at least $2^n$. Given a pair $(x,n)$, it
is polynomial-time decidable in $(x,n)$ whether $x\geq
2^n$, but there is no polynomial function exceeding
$n\mapsto 2^n$.
Similar examples would be provided by any sequence of sets
$A_n$, all of whose members were very large in comparison
with $n$, but such that the membership problem $x\in A_n$
is easily decided.
In various sorts of higher computability theory, there
are additional negative instances. For example, with the
theory of infinite time Turing machines, there are
infinite time decidable sets of reals with no computable members.
Indeed, the Lost Melody Theorem asserts precisely that there are infinite
time decidable singletons $\{c\}$, such that the real
$c$ is not writable by any infinite time Turing machine.
That is, there are reals $c$, such that it is decidable
by infinite time Turing machines whether a given real $x$
is $c$ or not, by no such machine can produce $c$ on its
own. This seems to be the essence of your phenomenon. (The
``lost melody'' terminology arises from the situation,
where a person is able to recognize a given melody when someone else
sings it, but is unable to sing it on their own.)
In descriptive set theory, one would look at whether a
set of reals at a given level in the descriptive
set-theoretic hierarchy has members at that same level.
This is false in general, although there are special circumstances
(some involving large cardinal hypotheses) in which instances
of it are true. One way to look at it
is as a Choice principle: given a subset $A$ of the plane
$\mathbb{R}\times\mathbb{R}$, can one find a function $f$
of the same complexity with $\text{dom}(f)=\text{dom}(A)$ such that
$(x,f(x))\in A$ for all $x\in\text{dom}(A)$? This problem is also
known as the uniformization problem.
In a more general set theoretic setting, it is natural to consider
the situation of ordinal-definable sets. Does every
non-empty ordinal definable set contain an
ordinal-definable member? This turns out to be equivalent
to the assertion known as $V=HOD$, which is independent of
ZFC, as explained in the edited version of this MO
answer.
The reason is that the set of non-ordinal-definable sets of
minimal rank is ordinal definable.
