UDC 517:518.5:164

MATHEMATICS

E. Yu. NOGINA

ON EFFECTIVELY TOPOLOGICAL SPACES

(Presented by Academician P. S. Aleksandrov on 5 XI 1965)

In the present note we consider certain constructive (in the sense of \((^1)\)) analogues of a number of topological concepts and results \((^2,{}^3)\) (we also considered other analogues of them, not set forth here for lack of space).

A set of points \(X\), together with its enumeration (i.e., a mapping onto \(X\) of some set of natural numbers) \(\alpha\) and a metric \(\rho\), is called an effectively metric space (e.m.s.), if there exists a computable function (c.f.) which, from a pair of numbers of two points \(x,y\) from \(X\), gives the number of the element \(\rho(x,y)\) of the constructive continuum*. The enumerated constructive continuum is an e.m.s.

A system \(\mathfrak T=(X,\alpha,\mathfrak U,\beta)\), where \(X\) is the set of points of a topological space; \(\mathfrak U\) is its base, and \(\alpha\) and \(\beta\) are enumerations of \(X\) and \(\mathfrak U\), respectively, will be called an effectively topological space (e.t.s.), if the following conditions are satisfied: 1) there exists a c.f. which, from the number of a point of \(X\), gives the number of an element of \(\mathfrak U\) containing it; 2) there exists a c.f. which, from the numbers of two elements of \(\mathfrak U\) and the number of a point in their intersection, gives the number of a base element containing this point and belonging to the intersection. Every point \(x\) of \(X\) will be called a point of the space \(\mathfrak T\). An e.m.s. becomes an e.t.s. as soon as the collection of all its spherical neighborhoods with rational radii, enumerated by the number of the pair \((^7)\) \((m,r)\), is taken as a base, where \(m\) is the number of the center of the spherical neighborhood and \(r\) its radius. In what follows, speaking of an e.m.s., we shall have in mind the corresponding e.t.s. A set \(W\subseteq X\) will be called effectively open (e.o.) in the e.t.s. \(\mathfrak T=(X,\alpha,\mathfrak U,\beta)\), if

\[ W=\bigcup_m U_{g(m)}, \]

where \(g\) is a c.f., the arguments and values of which are natural numbers, and for every \(m\), \(U_{g(m)}\in\mathfrak U\); any number of the function \(g\) will be regarded as a number of the set \(W\). Let us note that the empty set and an arbitrary enumerable union of e.o. sets are e.o.; the set of all points of the space and the intersection of two e.o. sets need not be e.o. Further, there exists an e.t.s. for which there can be no c.f. that, from the numbers of two e.o. sets and the number of a point \(x\) in their intersection, finds the number of an e.o. set containing the point \(x\) and contained in the intersection. Such a c.f. is certainly found for an e.t.s. possessing the following *property A: there exists an enumerable set \(G\) of pairs of natural numbers such that, if \(m\) is the number of a point of the space and \(n\) is the number of a base element, then the pair \((m,n)\) belongs to \(G\) if and only if the point with number \(m\) belongs to the base element with number \(n\).

Every e.m.s. has property A. There exists, however, an e.m.s. and two e.o. sets in it whose intersection is not e.o. We shall call complements of e.o. sets effectively closed (e.c.) sets and enumerate them by the numbers of the corresponding e.o. sets. Let us note,

* Concepts essentially equivalent to the concept of an e.m.s. are considered in \((^4,{}^5)\). In \((^6)\) the corresponding concept covers another class of spaces.

** By an enumeration of the constructive continuum is meant an arbitrary Cantor enumeration or any enumeration equivalent to it \((^7)\).

*** By the number of a c.f. is understood its number relative to an arbitrary, but fixed (for example, Gödel) principal enumeration \((^7)\).

that, although the supply of closed sets is, as a rule, considerably richer than the supply of effectively closed sets, the latter proves sufficient for obtaining, by their intersection, the closure of any set of points of an e.t.s.

A mapping \(\Psi\) of an e.t.s. \(\mathfrak X_1=(X_1,\alpha_1,\mathfrak U_1,\beta_1)\) into an e.t.s. \(\mathfrak X_2=(X_2,\alpha,\mathfrak U,\beta_2)\) is called computable if there exists a computable function \(\theta\) such that, for all \(n\) satisfying the condition \(\alpha_1(n)\in X\), one has
\[ \alpha_2(\theta(n))=\Psi(\alpha_1(n)). \]
A computable mapping \(\Psi\) of an e.t.s. \(\mathfrak X_1\) into an e.t.s. \(\mathfrak X_2\) is called effectively continuous (e-continuous) if there exists a computable function \(\zeta\) (we shall regard any number of the pair \((\theta,\zeta)\) (7) as a number of \(\Psi\)) which, from the number of an e.o. set \(W\) in \(\mathfrak X_2\), gives the number of an e.o. set in \(\mathfrak X_1\), namely \(\Psi^{-1}(W)\). Two spaces are called effectively homeomorphic if one can establish between them a one-to-one correspondence that is an e-continuous mapping in both directions. By an e-continuous function on an e.t.s. we shall mean its e-continuous mapping into the numbered constructive continuum. If \(f\) is an e-continuous function on an e.t.s., then \(g\) such that \(g=C\cdot f\) (where \(C=\mathrm{const}\)) is e-continuous; if \(f\) is e-continuous and is such that, for every \(x\), \(f(x)\geq 0\), then \(g=\sqrt f\) is also e-continuous. However, there exist e.t.s. (and even e.m.s.) and such e-continuous functions on them whose sum and product are not e-continuous.

We shall say that an e.t.s. has property B if there exists a computable function which, from the numbers of any two e.o. sets, gives the number of an e.o. set that is their intersection. On an e.t.s. with property B, the sum and product of two e-continuous functions are e-continuous. Let \(f_i\) be e-continuous functions on an e.t.s. with property B. If there exist two computable functions, one of which gives, from \(i\), a number of \(f_i\), and the other, from any rational \(\varepsilon>0\), gives an \(m\) such that, for every point \(x\) of the space and \(n\geq m\),
\[ \left|\sum_{i=n}^{\infty} f_i(x)\right|<\varepsilon, \]
then
\[ f=\sum_{i=0}^{\infty} f_i \]
is e-continuous on the e.t.s.

An e.t.s. will be called an e.\(T_0\)-space if there exists a computable function which, from a pair of numbers \((m,n)\) of two distinct points of the e.t.s., gives a pair consisting of the number of a base element containing exactly one of them and a natural number \(k\), equal to \(m\) or \(n\) according as which of the two given points it contains. An e.t.s. will be called an e.\(T_1\)-space if there exists a computable function which, from a pair of numbers of two distinct points \(x\) and \(y\) of the e.t.s., gives a pair of numbers of base elements \(V\) and \(W\) such that the conditions
\[ x\in V\setminus W,\qquad y\in W\setminus V \]
are satisfied. An e.t.s. will be called an e.\(T_2\)-space if there exists a computable function which, from a pair of numbers of two distinct points \(x\) and \(y\), gives a pair of numbers of base elements \(V\) and \(W\) such that
\[ V\cap W=\Lambda,\qquad x\in V,\qquad y\in W. \]
An e.\(T_0\)-space will be called an e.\(T_3\)-space if there exists a computable function which, from the numbers of a point \(x\) and of an e.c. set \(F\) not containing it, gives a pair of numbers of e.o. sets \(V\) and \(W\) such that
\[ V\cap W=\Lambda,\qquad x\in V,\qquad F\subseteq W. \]
An e.\(T_3\)-space will be called an e.\(T_4\)-space if there exists a computable function which, from the numbers of two disjoint e.c. sets \(F_1\) and \(F_2\), gives numbers of two e.o. sets \(W_1\) and \(W_2\) such that
\[ W_1\cap W_2=\Lambda,\qquad F_1\subseteq W_1,\qquad F_2\subseteq W_2. \]

1. An e.\(T_i\)-space (e.\(T_i\)P.) is a \(T_i\)-space* \((i=0,\ldots,4)\).

2. An e.\(T_i\)P. is an e.\(T_{i-1}\)P. \((i=1,\ldots,4)\). This assertion ceases to be true for \(i=4\) if, in the definition of e.\(T_4\)P., each occurrence of e.\(T_3\) is replaced by e.\(T_2\).

3. For each \(i\) \((i=1,\ldots,4)\) one can construct an e.t.s. that is an e.\(T_{i-1}\)P. and a \(T_i\)-space, but not an e.\(T_i\)P.

4. An e.m.s. is an e.\(T_2\)P., but not always an e.\(T_3\)P.

Let us call an e.t.s. effectively separable (e.s.) if there exists an enumerable set \(P\) of numbers of points of the space and a computable function which, from the number of any element \(U\) of the base, gives a number from \(P\) that is the number

* \(T_2\)-spaces are otherwise called Hausdorff, \(T_3\) regular, and \(T_4\) normal.

some point \(x\) of \(U\). We shall call any point of an e.t.s. that has a number in \(P\) a separability point.

It is known (Tikhonov’s theorem) that every \(T_3\)-space with a countable base is a \(T_4\)-space. One of the constructive analogues of a space with a countable base is naturally taken to be an e.c. e.t.s. with an enumerable base. It turns out that such a constructive analogue of Tikhonov’s theorem is false: there exists an e.c. e.t.s. with an enumerable base which is an e.\(T_3\)s., but not an e.\(T_4\)s.

Let us give an example of such an e.t.s. Let \(\xi\) be a one-to-one natural (7) numbering of the set \(X\). As elements of the base we take every singleton set \(\{\xi(n)\}\), supplied with the number \(n+2\) \((n=0,1,2,\ldots)\), and the sets \(Q\) and \(S\), supplied with the numbers respectively 0 and 1, where \(Q\) and \(S\) are defined as follows: the set of those points of \(X\) whose numbers belong to the complement of some maximal set (8), is divided into two infinite nonintersecting sets \(K\) and \(L\); then \(Q=X\setminus K,\ S=X\setminus L\).

The above-mentioned Tikhonov theorem is a consequence of the fact that a topological space is normal if it has the following property: every open set \(U\) is the union of at most a countable set of open sets whose closures lie in \(U\). Let us introduce for consideration the constructive analogue of this property—the property of an e.t.s.: there exists a c.f. which, from the number of a base element \(U\), gives the number of an enumerable set of pairs of numbers \((n_0,m_0),(n_1,m_1),\ldots\) such that \(n_i\) is the number of an e.o. set \(W_i\), \(m_i\) is the number of an e.c. set \(F_i\), and the conditions \(W_i\subseteq F_i\subseteq U\) and \(\bigcup W_i=U\) are fulfilled.

Theorem 1. An e.\(T_3\)p. with properties \(B\) and \(C\) is an e.\(T_4\)p.

Corollary. An e.c. e.m.p. is an e.\(T_4\)p. (it is, as is not difficult to show, an e.\(T_3\)p. and has properties \(B\) and \(C\)).

We shall call an e.t.s. \(\mathfrak X=(X,\alpha,\mathfrak U,\beta)\) an e.\(T_\phi\)-space (e.\(T_\phi\)p.) if it is an e.\(T_3\)p. and there exists a c.f. which, from the numbers of two nonintersecting e.c. sets \(F_1\) and \(F_2\) of the e.t.s. \(\mathfrak X\), gives the number of an e-continuous function mapping \(F_1\) to 0, \(F_2\) to 1 and such that, for all \(x\) from \(X\), the value \(f(x)\) lies between 0 and 1. Every e.\(T_\phi\)p. is an e.\(T_4\)p.

Theorem 2. An e.\(T_4\)p. with properties \(A\) and \(B\) is an e.\(T_\phi\)p.

Corollary 1. An e.c. e.m.p. is an e.\(T_\phi\)p.

Corollary 2. An e.\(T_0\)p. with properties \(A\), \(B\), and \(C\) is an e.\(T_\phi\)p.

For the proof it is enough to note that an e.\(T_0\)p. possessing properties \(A\) and \(C\) is an e.\(T_3\)p.

We shall call an e.t.s. effectively metrizable if it is effectively homeomorphic to an e.m.p. It is known (Urysohn’s theorem) that a \(T_3\)-space with a countable base is metrizable. The constructive analogue of this theorem is false: there exists an e.c. e.\(T_3\)p. with an enumerable base which is not effectively metrizable.

Theorem 3. In order that an e.t.s. with an enumerable base be effectively metrizable, it is necessary and sufficient that it be an e.c. e.\(T_0\)p. with properties \(A\), \(B\), and \(C\).

Necessity is easily established. Sufficiency follows from \(1^\circ\)—\(7^\circ\).

\(1^\circ\). \(\mathfrak X\)—an e.\(T_\phi\)p. (Corollary 2 of Theorem 2).

\(2^\circ\). In an e.\(T_\phi\)p. with property \(C\) there exists a c.f. \(g\) which, from the number of an element \(U\) of the base, gives the number of an e-continuous function \(f\) satisfying the conditions \(f(X\setminus U)=0\) and \(0<f(U)\leq 1\).

\(3^\circ\). Since \(\mathfrak X\) is an e.t.s. with an enumerable base, there exists an everywhere-defined c.f. \(h\) which enumerates without repetition the base of the numbering \(\beta\). Denote by \(\Phi_n\) the e-continuous function with number \(g(h(n))\).

\(4^\circ\). Put

\[ \rho(x,y)=\left(\sum_{n=0}^{\infty}\left(\frac{\Phi_n(x)-\Phi_n(y)}{2^n}\right)^2\right)^{1/2}. \]

The function \(\rho\) defines a metric on \(X\).

\(5^\circ\). \(X\), together with \(\alpha\) and \(\rho\), is an e.m.s. Denote it by \(\mathfrak{M}\).

\(6^\circ\). The identity mapping of \(\mathfrak{M}\) onto \(\mathfrak{T}\) is e-continuous. 1) It is computable. 2) For every natural \(n\) and every point \(x\) of \(U_{h(n)}\), the spherical neighborhood with center at \(x\) and radius less than \(\Phi_n(x)/2^n\) lies in \(U_{h(n)}\). Further, for every natural \(n\) and arbitrary point \(x\) of \(U_{h(n)}\), there exists a spherical neighborhood containing \(x\), with center at a separability point \(c\) from \(U_{h(n)}\) and with rational radius \(r\) less than \(\Phi_n(c)/2^n\). (Indeed, fix \(n\) and \(x\), and define an e-continuous function \(\Psi\) on \(\mathfrak{T}\) by the equality \(\Psi(y)=\rho(x,y)-\Phi_n(y)/2^n\). The complete preimage \(W\), under the mapping \(\Psi\), of the e.o. set \((-\infty,0)\) in the numbered constructive continuum is effectively open in \(\mathfrak{T}\) and nonempty.) Finally, for an e.s. e.t.s., by the properties of \(A\), there exists a c.f. which, from the number of a base element \(U\), gives the number of the enumerable set of numbers of all separability points belonging to \(U\).

\(7^\circ\). The identity mapping of \(\mathfrak{T}\) onto \(\mathfrak{M}\) is e-continuous. 1) It is computable. 2) The spherical neighborhood with center at \(x\) and radius \(r\) is the complete preimage of the interval \((-r,r)\) of the constructive continuum under the e-continuous mapping \(f\), defined by \(f(y)=\rho(x,y)\), e.t.s. \(\mathfrak{T}\) into the numbered constructive continuum.

The author expresses deep gratitude to V. A. Uspenskii for suggesting the topic of the research and for his constant attention to the work.

Moscow State University
named after M. V. Lomonosov

Received
3 XI 1965

REFERENCES

1. V. A. Uspenskii, UMN, 12, 1, 99 (1957).
2. P. S. Aleksandrov, Introduction to General Theory of Sets and Functions, Moscow–Leningrad, 1948.
3. A. A. Markov, Mathematics in the USSR for 30 Years, Moscow–Leningrad, 1948, p. 183.
4. G. S. Tseitin, DAN, 128, No. 1, 49 (1959).
5. Y. N. Moschovakis, Fund. Math., 55, 3, 215 (1964).
6. D. Lacombe, In: Constructivity in Mathematics, Amsterdam, 1959, p. 128.
7. V. A. Uspenskii, Lectures on Computable Functions, Moscow, 1960.
8. R. M. Friedberg, J. Symb. Logic, 23, 309 (1958).