# Is there a name for sets for which it is easier to test membership than to find members---and vice versa?

This is a question my son Bob asked me. For some sets it is relatively easy to test for membership but a lot more difficult to find members, and for others the reverse is true. Here is an elementary example to get the idea across. An $m \times n$ real matrix $M$ defines a linear map $x \mapsto M x = y$, from ${\mathbb R}^n$ to ${\mathbb R}^m$. It is easy to test if $x$ is in the kernel; just compute $M x$ and see if it is zero, but to find an $x$ in the kernel you must solve $M x = 0$ which is more computationally intensive. Conversely it is easy to find an element in the range; just choose any $x$ and compute $M x$; but to test if $y$ is in the range you must solve $M x = y$. Does anyone know if there is a standard name for this distinction or for sets of these two types?

-
In $Mx=0$, assuming $x\ne 0$, there are two separate questions: is there such an $x$, and how do you find one if there is one. Conceivably the former could be easy while the latter is hard, so maybe some clarification of the question? – Bjørn Kjos-Hanssen Oct 14 '10 at 22:10
I don't know of any name for this, but just in case, to clarify: Would the set of transcendental numbers be another example? Are you specifically interested in subsets of $\mathbb R^n$? And are you only measuring difficulty in terms of computational complexity, as opposed to something else? (What could I mean by "something else"? There are results in descriptive set theory stating that definable sets of certain complexity must contain definable members of certain complexity.) – Andrés Caicedo Oct 14 '10 at 22:20
Bjørn: Remember, this is only meant as an example, so think of $M$ as a generic matrix, in which case I believe the two questions really are the same. – Dick Palais Oct 14 '10 at 22:20
It's only meant as an example, so I'll take a different example... if we let $f(x)$ be the unary representation of $x$, where $x$ is a number given in binary, then $f(x)$ always exists (so the question whether it exists is trivial), but is time-intensive to compute. – Bjørn Kjos-Hanssen Oct 14 '10 at 22:31

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 first 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.

• The converse situation, however, does occur in computability theory, and is a central phenomenon. Namely, there are sets of natural numbers whose members can be systematically generated---so the set is computably enumerable---but whose membership test is not computable. These are exactly the sets that are c.e. but not computable. Examples would include the halting problem (the set of programs $e$ halting on trivial input) and many other examples. It is easy to generate many halting programs---one can systematically enumerate them---but impossible to test in general if a given program halts. There is an intensively-studied hierarchy of Turing degrees instantiated by c.e. sets that are not decidable.

• 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.

-
This happens in other areas of computability theory as well. In Blum/Shub/Smale computability, it is possible for a set to be semidecidable even though it is not enumerable; I have heard the set of algebraic numbers give an example of this. In alpha recursion theory, the very definition of "enumerable" is made in terms of semidecidability rather than in terms of what is usually thought of as enumerability. Classical computability theory on the natural numbers is somewhat unique in making enumerability and semidecidability equivalent. – Carl Mummert Oct 15 '10 at 1:17
The consensus seems to be that there is no standard name for this phenomenon, but I have learned a lot from the answers about the many and varied situations in which it comes up. My thanks to all---and particularly to Joel for his well thought out and informative answer. – Dick Palais Oct 15 '10 at 12:04

A similar question was asked at cstheory.stackexchange; there are several examples from computational complexity given there. However, I agree that there seems to be no standard name for such things.

-