ISSN 1064–5624, Doklady Mathematics, 2006, Vol. 73, No. 1, pp. 36–37. © Pleiades Publishing, Inc., 2006. Original Russian Text © A.A. Vladimirov, 2006, published in Doklady Akademii Nauk, 2006, Vol. 406, No. 3, pp. 295–297.
MATHEMATICS
Hierarchies of Finite Sets A. A. Vladimirov Presented by Academician Yu.I. Zhuravlev May 23, 2005 Received May 30, 2005
DOI: 10.1134/S1064562406010091
The subject of this paper goes back to the report of A.A. Markov at IV All-Union Mathematical Congress (Leningrad, 1961). A brief exposition of the approach and results related to this report can be found in commentary [6] by Nagornyi.
Following [7, Section 7; 6], we assume that the idea of a set of words is relativized by means of the language . Definition 1. A set of words over an arbitrary fixed alphabet A is any word of the form {x |F},
1. As is known (see [2, Section 4]), for constructive objects that are described indirectly in terms of their properties rather than presented explicitly, the notion of existence becomes ambiguous. Namely, the potential implementability of a constructive object does not coincide with its double negation, quasi-implementability (existence in the classical sense). Inside the arising gap between potential implementability and quasi-implementability, other (intermediate) characters of the existence of a constructive object can be considered.
(1)
where F is a one-parameter formula in the language and x is the only parameter of this formula. An element of set (1) is any word over A such that substituting it into F for x gives a closed formula that is true in the semantics of the language . We consider also lists of words, which are understood as words in the alphabet obtained by adding a disjunctive symbol * to the initial alphabet. Definition 2. A list of words in an alphabet A is any word L over A* that begins and ends with the letter * and contains no different occurrences of a word of the form *Q*. An element of the list L is any word Q over A for which *Q* is contained in L. In what follows, we briefly call sets of words over the alphabet A simply sets, and we call lists of words over A simply lists. Definition 3. A list L' is called a sublist of a list L if any element of L' is also an element of L. Lists L and L' that are sublists of each other are said to be equivalent. Definition 4. A list of elements of a set M is any list L whose elements are precisely all elements of the set M. In what follows, we denote empty words over various alphabets by Λ. 3. Each of the types of finite sets given in [6] is related to some modification the following general idea: A list of elements of a given set is quasi-implementable among the elements of a potentially implementable solvable set of words over the alphabet A*. More specifically, the definitions from [6] can be restated as follows. Definition 5. A finitary set is a set for which the list of elements is potentially implementable (i.e., quasiimplementable among the elements of a potentially implementable one-element solvable set of words over the alphabet A*).
The idea of the finiteness of sets in constructive objects is traditionally related to the existence of a certain auxiliary constructive object, the list of elements of the set. Thus, it splits into a whole spectrum of different notions corresponding to different characters of the existence of a list of elements. In the early 1960s, Markov discovered that some of the standardized versions of the notion of a finite set of constructive objects are nonequivalent. In [6], four such versions were mentioned, namely, the notions of finitary, subfinitary, quasi-finitary, and noninfinitary sets. The purpose of this paper is to construct more ramified hierarchies of types of finite sets of constructive objects. 2. In what follows, we assume that some logicobject language adjusted to formalizing judgements about words over various alphabets is fixed. The possible syntax of such a language is described in [3–5]. We also assume that the semantics of closed formulas in the language is compatible with derivability by means of classical predicate calculus.
Computer Center, Russian Academy of Sciences, ul. Vavilova 40, GSP-1, Moscow, 119991 Russia e-mail:
[email protected] 36
HIERARCHIES OF FINITE SETS
Definition 6. A subfinitary set is a set for which the list of elements is quasi-implementable among the sublists of a potentially implementable list. Definition 7. A quasi-finitary set is a set for which the list of elements is quasi-implementable among lists having potentially implementable upper bound for the number of different occurrences of the letter *. Definition 8. A noninfinitary set is a set for which the list of elements is simply quasi-implementable. In relation to the last definition, the following definition can be introduced. Definition 9. Let be an everywhere defined normal algorithm over A* such that, for any list L, a word Q over A with the property LQ = Λ is potentially implementable. Then, the -finiteness code (of a set M) is defined as a pair {M, Q} consisting of the set M and the word Q over A such that the list of elements of the set M is quasi-implementable among the lists L with the property LQ = Λ. Accordingly, a set M is said to be -finite if its -finiteness code is potentially implementable. The central result of this paper is the following theorem. Theorem 1. Let and ' be normal algorithms satisfying the requirements specified in Definition 9. Suppose that there is a potentially implementable word V over the alphabet A such that, for any word Q over A, there exists a list L satisfying the equality LV = Λ and such that any equivalent list L' satisfies the inequality ' L'Q = Λ. Then, any algorithm which converts each -finiteness code {M, Q} into an '-finiteness code {M, Q'} of the same set is nonimplementable. In the framework of the constructive understanding of mathematical judgements (see [7]), Theorem 1 admits the following equivalent reformulation. Theorem 2. Let and ' be normal algorithms satisfying the requirements of Theorem 1. Then, it is false that any -finite set is '-finite. In the statements of corollaries to Theorem 1, we use the same notation as in the statement of Theorem 2. 4. The first corollary to Theorem 1 is a theorem of Markov stated in [6].
DOKLADY MATHEMATICS
Vol. 73
No. 1
2006
37
Corollary 1 (Markov’s theorem). In the framework of the constructive understanding of mathematical judgements, (i) it is false that any noninfinitary set is quasi-finitary; (ii) it is false that any quasi-finitary set is subfinitary; (iii) it is false that any subfinitary set is finitary. To state yet another corollary to Theorem 1, we introduce the following definition. Definition 10. Let N be an arbitrary positive integer different from 0. A set for which the list of elements quasi-implementable among N potentially implementable lists is said to be N-subfinitary. In particular, a set is 1-subfinitary if and only if it is finitary. Corollary 2. For any nonzero positive integers N and N' satisfying the inequality N > N', it is false in the framework of the constructive understanding of mathematical judgements that any N-subfinitary set is N'-subfinitary. Corollary 2 shows that the types of N-subfinitary sets form an enumerable-infinite hierarchy of constructively nonequivalent types of finite (and even subfinitary) sets. ACKNOWLEDGMENTS This work was supported by the Russian Foundation for Basic Research (project no. 03-06-80166). REFERENCES 1. A. A. Markov, Tr. Mat. Inst. im. V.A. Steklova, Akad. Nauk SSSR 67, 8–14 (1962). 2. A. A. Markov, Izv. Akad. Nauk SSSR, Ser. Mat. 31 (1), 161–208 (1967). 3. A. A. Markov, Dokl. Akad. Nauk SSSR 214, 40–43 (1974). 4. A. A. Markov, Dokl. Akad. Nauk SSSR 214, 279–282 (1974). 5. A. A. Markov, Dokl. Akad. Nauk SSSR 214, 1262–1264 (1974). 6. N. M. Nagornyi and A. A. Markov, Selected Works (MTsNMO, Moscow, 2003) [in Russian]. 7. N. A. Shanin, Tr. Mat. Inst. im. V.A. Steklova, Akad. Nauk SSSR 52, 226–311 (1958).
