The Medvedev lattice of degrees of difficulty
Andrea Sorbi · Cambridge University Press eBooks · 1996
Introduction The Medvedev lattice was introduced in [5] as an attempt to make precise the idea, due to Kolmogorov, of identifying true propositional formulas with identically “solvable” problems. A mass problem is any set of functions (throughout this paper “function” means total function from ω to ω; the small Latin letters f, g, h ,… will be used as variables for functions). Mass problems correspond to informal problems in the following sense: given any “informal problem”, a mass problem corresponding to it is a set of functions which “solve” the problem, and at least one such function can be “obtained” by any “solution” to the problem (see [10]). Example 1.1 If A, B ⊆ ω are sets, and φ is a partial function, then the following are mass problems: { C A } (where C A is the characteristic function of A ): this is called the problem of solvability of A ; this mass problem will be denoted by the symbol S A ; { f : range( f ) = A }: the problem of enumerability of A ; this mass problem will be denoted by the symbol ε A ; (Other examples) The problem of separability of A and B , i.e. { f : f −1 (0) = A & f −1 (1) = B }; of course, this mass problem is empty if A∩B ≠ Ø: it is absolutely impossible to “solve” the problem in this case. The problem of many-one reducibility of A to B : { f : f −l ( B ) = A }. The problem of extendibility of φ: { f : f ⊇ φ}.