Logical Topologies and Semantic Completeness

Valentin Goranko

Abstract

We study a generic problem of proving semantic completeness of a logical system with respect to a class of “standard models”, provided a weaker completeness result with respect to a larger class of “general models” has been obtained. We propose a natural topological approach to this problem based on the notion of logical topology and the related concept of logical approximation. We then obtain some general results regarding these concepts and then discuss them in the framework of first-order logic. The paper ends with an example of a particualr application of the ideas developed here, and a discussion on further research.

Contents

1 Introduction 2 1.1 The relative completeness problem . . . . . . . . . . . . . . . . . 2 1.2 A topological approach. . . . . . . . . . . . . . . . . . . . . . . . 2

2 Preliminaries 3

3 Logical topologies on theories and structures. 4

4 Logical topologies in first-order logic and elementary approximations of structures. 6

5 An application: a relative completeness result of the first-order theory of coloured ω-trees. 9

6 Concluding remarks. 10

To Johan van Benthem, on the occasion of his fiftieth birthday, with high respect.

1 Introduction

1.1 The relative completeness problem

The present study is motivated by the following, often arising in logical studies, generic problem. A deductive system L (of any nature) in a certain logical language is intended to axiomatize a class of standard models SM. A completeness theorem is proved with respect to a larger class of general models GM , i.e. it is proved that

L ⊢ ϕ iff L ⊧_{GM} ϕ

The goal is to prove completeness of L with respect to the standard models, i.e.

L ⊢ ϕ iff L ⊧_{SM} ϕ

Here are two typical cases:

1. Finite model property in classical, modal, or other non-classical logics. The “general models” are all models for the logic L, and the “standard models” are the finite models. While completeness with respect to general models is a uniform result in classical logic, due to Gődel’s completeness theorem, completeness with respect to “standard” (i.e. finite) models is an essentially nontrivial property, as Trakhtenbrot’s theorem testifies.

2. Kripke-frame completeness in modal logic. The “general models” are all Kripke models for the logic L, and the “standard models” are those Kripke models based on frames for L . Again, the completeness with respect to the class of general models is a general result in modal logic (based on the standard canonical construction) but the completeness with respect to the standard models, i.e. Kripke completeness, is the non-trivial and important one For more details and numerous results, see [van Benthem, 1985].

There is no general method for solving the problem described above, but usually some specific model-theoretic constructions are applied which transform general into standard models while preserving satisfiability.

Here we do not offer a solution to that problem either, but rather a methodology based on a natural topological approach which can be applied in various particular cases. An example of a non-trivial application is outlined at the end of the paper.

1.2 A topological approach.

The idea is to find an appropriate topology T on the class of general models GM such that:

(i) The class of standard models SM is dense in GM with respect to T , i.e. the closure in T of SM is GM.

(ii) Validity is a continuous property with respect to T , i.e. preserved in cluster points of nets (in particular, limits of sequences) of models.

The following proposition is immediate.

Proposition 1.1 If the two conditions above hold for some topology T on GM then completeness with respect to GM implies completeness with respect to SM.

Alternatively, we can associate with every general model its theory, i.e. the set of its valid formulae, and look for an appropriate topology on the set of all theories of general models, for which an analogous result can be stated. This approach has some technical advantages, but the two approaches are essentially equivalent, as it will be shown further.

Although many intimate connections between logic and topology have been established and studied, it seems that topological methods and results have so far been under-utilized for solving purely logical problems. Besides extensive research on abstract model theory involving topological machinery (see [Barwise and Feferman, 1985]) I am aware of not many other publications, such as [Rasiowa and Sikorski, 1963] and [Goldblatt, 1985], which more explicitly pursue that direction.

In this paper we begin systematic exploration of the idea of using basic topological techniques and results to obtain relative completeness results in logic. The preliminary section 1 contains some background from logic and topology. In section 2 we introduce the notion of logical topology and the related concept of logical approximation, and study their basic properties. In particular, as a direct consequence of Baire’s category theorem, we obtain a general relative completeness result (theorem 3.5, and theorem 4.6 as a particular case in first-order logic) which seemingly has so far been unnoticed, or certainly not popular, despite the well-known relationship of Baire’s theorem to logic (see [Rasiowa and Sikorski, 1963] and [Goldblatt, 1985]).

In section 3 we discuss logical topologies and logical approximation in classical logic. Not surprisingly, we show that a topology on the set of all complete theories in a first-order language is logical iff it contains Stone topology (proposition 4.1) and briefly study a simple and natural extension of Stone topology in languages with infinite signature. In section 4 we mention a specific application to the first-order theory of discrete trees, and outline a proof of completeness based on ideas and results from the paper. The last section 5 discusses a research program arising from this study.

2 Preliminaries

Here we summarize some basic topological facts that will be used further. For details on definitions and related results, [Ebbinghaus et al, 94] and [Hodges, 93] are general references on the necessary logical background, and [Engelking, 85]

– on topology.

Let L be a first-order language, SEN(L) be the set of sentences of L, and C(L) be the set of complete theories in L. The Stone topology S(L) is defined on the set C(L) by a base of clopen sets {[ϕ]|ϕ ∈ SEN(L)} where [ϕ] = {T ∈ C(L)|ϕ ∈ T }. It is easy to see that the closed sets in C(L) are precisely the sets {T ∈ C(L)|Γ ⊆ T } where Γ is a theory in L and that S(L) is a totally disconnected compact Hausdorff topological space.

The topology S(L) determines a topology S_{ST R}(L) on the class of all Lstructures ST R(L), called by Tarski the elementary topology, where the closed subclasses are precisely the first-order axiomatizable classes. This topology is pseudo-metrizable when the language is countable and every first-order axiomatizable class, considered as a subspace of S_{ST R}(L) then becomes a complete pseudo-metric space.

Given a topology T and a set A in T , by Cl_{T} (A) we denote the closure of A in T .

Definition 1 A subset A of a topological space T on a set X is dense if Cl_{T} (A) = X. A subset A of a set B in a topological space T on a set X is dense in B if Cl_{T |B}(A) =B, . where T |B is the topology on B induced by T .

Definition 2 A topological space T has Baire’s property if every countable intersection of dense open sets in T is dense in T.

A version of Baire category theorem states that every complete pseudometric space, and every compact Hausdorff space has Baire’s property.

A topology is first-countable if every point has a countable base of open neighbourhoods. It is easy to see that a Stone topology is first countable iff the language is at most countable. In first-countable topologies continuity and closure can be characterized in terms of convergent sequences, while in general, they are characterized in terms of convergent nets or clustering filters.

3 Logical topologies on theories and structures.

Let us fix an arbitrary logical language L with specified semantics, i.e. a class of L-structures and a relation ⊧ of validity of L -formulae in L-structures.

Let T be a topology on the class of L-structures.

Definition 3 The topology T is logical on a class of L -structures M if validity is a continuous property with respect to the topology on M induced by T . T is logical if it is logical on the class of all L-structures.

For every L-structure A, we denote by T H(A) the theory of A, i.e. the set of L-formulae valid in A.

Now, let T be a topology on a set TH of theories of L-structures and Cl_{T} (F) be the closure of F with respect to T .

Definition 4 The topology T is logical on TH if for every subset F ⊆TH, ⋂ F = ⋂ Cl_{T} (F).

T is logical if it is logical on the set of all theories of L-structures.

There is an easy duality between the two notions of logical topologies. For every topology T on a class of structures M we can associate a topology T_{T H} on the set of their theories, where the closed sets are of the type {T H(A)|A ∈ C} for each closed set C in T . Conversely, for every topology T on a set of theories T we can associate a topology T_{ST R} on the class of all models of theories from T, with closed sets of the type {A|T H(A) ∈ C} for each closed set C in T .

Proposition 3.1 1. If T is a logical topology on a class M of L-structures,

then T_{T H} is a logical topology on the set T of their theories.

2. If T is a logical topology on a set T of theories of L-structures, then T_{ST R} is a logical topology on the class M of their models.

Proof:

1. It is sufficient to note that for every F ⊆ T_{T H}, the closure of F in T_{T H} consists of all theories of structures which are in the closure of {A|T H(A) ∈ F} in T .

2. Likewise. ♣

Thus, both notions are essentially equivalent. While most of the ideas and concepts discussed here look more natural when formulated in terms of structures, it is technically more convenient and elegant to state and prove many of the results in terms of theories, so we shall use interchangeably the two frameworks.

Proposition 3.2 If T , R are topologies on a set of theories TH, T ⊆ R, and T is logical, then R is logical, too.

Proof: T ⊆ R implies Cl_{R}(F) ⊆ Cl_{T} (F), so ⋂ F ⊆ ⋂ Cl_{T} (F) ⊆ ⋂ Cl_{R}(F) for every F ⊆ TH. ♣

Definition 5 Let T be a logical topology on the class of L-structures. A structure A is logically approximated (with respect to T ) in a class of structures M if A belongs to the closure of M (with respect to T ). A class of structures K is logically approximated (with respect to T ) by M if every structure from K is logically approximated in M. The closure Cl_{T} (K) of K, i.e. the class of all structures logically approximated in the class K, will be called the logical closure of K (with respect to T ).

The following theorem, the proof of which is straightforward, formalizes the idea outlined in the introduction and provides formal grounds for application of our approach to solving the relative completeness problem.

Theorem 3.3 Let L be a deductive system in the language L, complete for a class of structures K, T be logical on K, and M be a dense with respect to T subclass of K. Then L is complete for M.

A direct application of Baire category theorem yields the following result.

Lemma 3.4 Let K be a class of L-structures, T be a logical topology on K with Baire’s property, and {M_{k}}_{k∈N} be a family of open subclasses of K such that K is logically approximated by each M_{k}. Then K is logically approximated by M = ⋂_{k∈N} M_{k}.

The following theorem is a combination of the previous two statements.

Theorem 3.5 Let L be a deductive system in L, complete with respect to a class of L-structures K, T be a logical topology on K with Baire’s property and {M_{k}}_{k∈N} be a family of open and dense subclasses of K. Then L is complete with respect to M = ⋂_{k∈N} M_{k}.

4 Logical topologies in first-order logic and elementary approximations of structures.

We now fix an arbitrary first-order language L. With no risk of confusion we shall denote both the Stone topology on C(L) and the elementary topology S_{ST R}(L) by S, and the closure operator in both topologies by Cl_{S}.

Note that for every F ⊆ C(L), Cl_{S}(F) = {T ∈ C(L)| ⋂ F ⊆ T } . On the other hand, for every class of L-structures K , Cl_{S}(K) is the elementary closure of K, i.e. the smallest elementary class which contains K. Thus, Cl_{S}(K) = MOD(T H(K)), the class of all models of the first-order theory of K. Therefore, a theory T is complete for a class K iff T H(K) = T i.e. K is dense in MOD(T).

Proposition 4.1 A topology T on C(L) is logical iff it contains the Stone topology.

Proof: First, suppose T is logical and let F ⊆ C(L) be closed in S(L), i.e. F = {T ∈ C(L)| ⋂ F ⊆ T }. Then ⋂ F ⊆ ⋂ Cl_{T} (F), so Cl_{T} (F)⊆ F, i.e. Cl_{T} (F) = F. For the converse, by proposition 3.2, it suffices to show that Stone topology is logical. Indeed, for any F ⊆ C(L), if T ∈ Cl_{S}(F) then ⋂ F ⊆ T, hence ⋂ F ⊆ ⋂ Cl_{S}(F). ♣

Thus, Stone topology is the weakest logical topology on the class of all L -structures, but there can be even weaker logical topologies suitable on some subclasses. Besides, sometimes it may easier to deal with logical topologies stronger than Stone topology. A typical example of such a topology in firstorder logic can be introduced by using an appropriate metric (which need not be inducing the Stone topology) on C(L).

The notion of quantifier rank of a formula is introduced as usual in languages with relational signatures, and appropriately modified for languages including constant and functional symbols, as in [Ebbinghaus et al, 94], p. 257.

Let SEN^{(n)}(L) be the set of L-sentences of (modified) rank ≤ n and for every Γ ⊆ SEN, Γ^{(n)} = Γ ∩ SEN^{(n)}(L).

First, we define distance in C(L) as follows:

d(T_{1}, T_{2}) = \{ \begin{matrix}0 & if T_{1} = T_{2}, \\ \frac{1}{n+1} & if n is the least integer such that T_{1}^{(n)} ≠ T_{2}^{(n)}. \end{matrix}

Proposition 4.2

1. ⟨C(L), d⟩ is a bounded and complete metric space.

2. The topology C_{d}(L) on C(L) induced by d is logical.

Proof:

1. To see that d is a metric it is sufficient to note that d(T_{1}, T_{3}) ≤ max(d(T_{1}, T_{2}), d(T_{2}, T_{3})) for any T_{1}, T_{2}, T_{3} ∈ T (L). Boundedness is obvious. For completeness^{1}, let T_{1}, T_{2}, …, T_{n} … be a Cauchy sequence in T (L). Then, for each n ∈ N there is N ∈ N such that for all p, q > N, T_{p}^{(n)} = T_{q}^{(n)}. Let us denote the latter by Γ_{n}. Thus we obtain a chain of theories Γ_{0} ⊆ Γ_{1} ⊆ . . .. Let Γ = ⋃_{n=0}^{∞} Γ_{n}. Γ is a complete theory. Indeed, Γ is closed. For, let Γ ⊧ ϕ where ϕ ∈ SEN^{(m)}(L) for some m. Then Γ_{k} ⊧ ϕ for some k. Hence ϕ ∈ Γ_{max(k,m)}, so ϕ ∈ Γ. Furthermore, for every ϕ ∈ SEN^{(m)}(L) for some m, either ϕ or ¬ϕ is in Γ_{k} for every k≥m. Finally, it is clear that lim_{n→∞} T_{n} = Γ.

2. We shall prove that C_{d}(L) contains Stone topology. Let F be a closed set in S(L). Then F = {T ∈ C(L)| ⋂ F ⊆ T }. Since every metric space is firstcountable, it is sufficient to show that the limit T in C_{d}(L) of any sequence T_{0}, T_{1}, … from F is in F. Indeed, ⋂ F ⊆ T since every sentence from ⋂ F with a rank n will belong to all theories in the open \frac{1}{n+1} -neighbourhood of each theory from F. Thus, F is closed in C(L).

♣

Proposition 4.3 For every first-order language L the following are equivalent:

1. The language L has finitely many non-logical symbols.

2. The topology C_{d}(L) coincides with the Stone topology.

3. The space C_{d}(L) is compact.

4. C_{d}(L) is totally bounded.

5. For every n ∈ N, the set {T^{(n)}|T ∈ C(L)} is finite.

6. For no n ∈ N there is an infinite independent subset of SEN^{(n)}(L).

Proof:

(1) ⇒ (2): Let F ⊆ C(L) be closed in C_{d}(L) and Γ = ⋂ F. We shall prove that F = {T ∈ C(L)|Γ ⊆ T } . We only need to show that T ∈ F whenever Γ ⊆ T. Indeed, for every n ∈ N, T^{(n)} is finite, so it is included in some T_{n} ∈ F, otherwise ¬ ⋀ T^{(n)} ∈ Γ, so T would be inconsistent. Thus, T is the limit in C_{d}(L) of a sequence T_{1}, T_{2}, ... in F, hence T ∈ F.

1Cifuentes, Sette and Mundici have proved in [Cifuentes et al, 1996] the stronger result, that for any first-order language L, the elementary topology S_{ST R}(L) is Cauchy complete, i.e.

every Cauchy net converges.

(2)⇒(3) Follows from compactness of Stone topology.

(3)⇔ (4): Every complete metric space is compact iff it is totally bounded. (4)⇔ (5): Since the theories in every \frac{1}{n+1} -neighbourhood of T (L) share

the same SEN^{(n)}(L)-fragment, T (L) is covered by finitely many open balls of radius \frac{1}{n+1} iff there are finitely many SEN^{(n)}(L)-fragments of theories from T (L).

(5) ⇒ (6): Suppose Γ is an infinite independent subset of SEN^{(n)}(L) for some natural n. For each δ ∈ Γ we consider the consistent theory Γ_{δ} = Γ − {δ} ∪ {¬δ}. All these theories have different SEN^{(n)}(L) -fragments.

(6) ⇒ (1): If the language has infinitely many non-logical symbols, then there are infinitely many atomic formulae of (at most) one variable and rank not greater than 1, no two of which share non-logical symbols, hence there is an infinite independent set of sentences in SEN^{(2)}(L). ♣

Thus, we see that, although C_{d}(L) is stronger than Stone topology, it is simpler and easier to deal with in case of infinite languages, especially in uncountable languages where the latter is not first-countable.

The logical approximation with respect to S(L) will be called elementary approximation, and the approximation with respect to C_{d}(L) — strong elementary approximation. Note that a structure A is strongly elementarily approximated in a class K iff for every n ∈ N there is A_{n} ∈ K such that A ≡_{n} A_{n}. The class of all structures which are strongly elementarily approximated in K will be called the strong elementary closure of K. Thus, every structure, strongly elementarily approximated in a class K, is elementarily approximated in K, but the converse need not hold in a language with an infinite signature. Respectively, every elementary closure is a strong elementary closure, but not conversely, and the elementary closure of any class K contains its strong elementary closure.

Elementary approximation and closure are already well-understood from various classical model-theoretics results, and we shall only mention just two characterizations of elementary approximation. The first one, in S(L) is essentially equivalent to the compactness theorem (see [Hodges, 93]): a theory T ∈ C(L) is elementarily approximated by a set F ⊆ C(L) iff every finite subset of T is included in some theory from F. The second one, in S_{ST R}(L), is a well-known preservation result: a structure A is elementarily approximated by a class of structures K iff A elementarily equivalent to an ultraproduct of structures from K .

Here are two easy characterizations of strong elementary approximations.

Definition 6 A net of L-structures ⟨A_{i}⟩_{i∈D} , where D is a directed indexing family, is strongly convergent if it is convergent in C_{d}(L).

Theorem 4.4 A class K of L-structures is a strong elementary closure iff it is closed under elementary equivalence and ultraproducts of strongly convergent nets.

Proof: If K satisfies the closure conditions, then every structure strongly elementarily approximated in K belongs to K since the ultraproduct of ⟨A_{i}⟩_{i∈D} over any free ultrafilter on D is elementarily equivalent to the limit of that net. Conversely, every strong elementary closure is closed under elementary equivalence and therefore, under ultraproducts of strongly convergent nets. ♣

In the case of a countable language, the result above can be stated in terms of converging sequences, rather than nets.

A simple game-theoretic characterization of strong elementary approximations exists, too.

Definition 7 Ehrenfeucht game with choice of a companion: Given a structure A, and a class of structures K, the game goes between two players as follows. In his first move Player I selects a natural number n. Then Player II selects a structure B from K. Then the game continues as the usual Ehrenfeucht game for A and B and ends after n more moves. The winning conditions are the same as for the usual Ehrenfeucht games.

Proposition 4.5 A structure A is strongly elementarily approximated in a class K iff Player II as a winning strategy for every game with choice of a companion.

Finally, we state a useful, though seemingly not popular, result on relative completeness, which is a particular case of theorem 3.5. (Recall that a first-order theory T is complete with respect to a class K iff K is dense in MOD(T).)

Definition 8 A class of first-order structures is co-elementary if its complement is elementary.

Theorem 4.6 Let {M_{k}}_{k∈N} be a family of co-elementary classes of L-structures, and let T be a first-order theory complete with respect to each M_{k}. Then T is complete with respect to M = ∩_{k∈N}M_{k}.

5 An application: a relative completeness result of the first-order theory of coloured ω-trees.

In this section we shall mention just one sample completeness result obtained by applying ideas and results from the previous sections. For detailed proofs and more related results see [Goranko, 98]

By a tree we mean any (strictly) partially ordered set with a least element (root), in which every element has a linearly ordered set of predecessors. The elements of a tree will be called nodes. A child of a node x is a successor of x which is not a successor of any successor of x. A tree will be called discrete if every successor of a node is either a child or a successor of a child of that node. (This, every well-ordered tree is discrete.) A path in a tree is any maximal linearly ordered subset. A tree in which every path has the order type of ω will be called an ω-tree. Given a node a in a tree, the set of nodes {b|b < a} will be called the stem of a. A sibling of a node t in a tree T is any other node in T which has the same stem as t. For any order type τ, a τ-level in a tree T is the set T_{τ} of all nodes whose stems have an order type τ. The finite levels in a tree are all α-levels for finite ordinals α. (Thus, the 0-level consists of the root of the tree). A discrete tree is finitely branching if every node has finitely many siblings; it is finitely branching on a level α if all nodes on that level have finitely many siblings.

Here we shall consider trees enriched with finitely many additional unary predicates, which will be called colours, and the resulting structures coloured trees.

Note that the class of all discrete trees is first-order definable.

Theorem 5.1 The first-order theory T T_{ω} of all coloured ω-trees is complete with respect to the class of finitely branching coloured ω -trees.

Sketch of proof: Let M_{ω} be the class of all models of T T_{ω} and M^{f} be the subclass of M_{ω} consisting of all trees which are finitely branching on all finite levels and in which every satisfiable formula of one variable is satisfiable on a finite level.

The proof goes through two major steps. The first step is to prove that T T_{ω} is complete with respect to M^{f} by showing that M^{f} is dense in M_{ω} with respect to the elementary topology. That can be done using theorem 4.6, since M^{f} can be represented as an intersection of the family of open classes {M_{k}}_{k∈N} , where M_{k} consists of the models M of T T_{ω} finitely branching at the first k levels and satisfying on finite levels the first k formulae of some enumeration, satisfiable in M. It can be proved, using Ehrenfeucht’s theorem, that each M_{k} is dense in M_{ω}.

The second step then is to prove completeness with respect to the class of finitely branching ω-trees, and it uses the omitting types theorem. ♣

6 Concluding remarks.

In this paper we have only discussed some rather immediate results regarding logical topologies. This topic can be further developed both from logical and from topological perspective.

¿From topological perspective, there is much more to be done, as there is a number of non-trivial topological results which can be usefully reformulated in logical terms and applied for solving relative completeness (and other) problems. For instance, it is known (see [Fraïssé 67]) that S_{ST R}(L) are uniform spaces, which brings additional useful properties, little explored and used in logic so far.

A major logical perspective is to study logical topologies in second-order, infinitary, modal, etc. logics and to apply them to non-trivial completeness problems in these logics. Some of the results in first order logic easily generalize to a wide variety of other logical languages and systems. For instance, an analogue of Stone topology can be introduced in every logical language which has a disjunction, and the theories under consideration are consistent and prime in sense that α∨β ∈ T iff α ∈ T or β ∈ T. Then it is easy to check that Cl(F) = {T ∈ TH| ⋂ F ⊆ T } defines a topological closure, and the logical topologies in that language are precisely the extensions of the resulting topology. Still, in these and other cases it is interesting and important to search for other useful constructions of topologies, logical on a class of structures.

A generic problem of particular importance in second-order logic is to study elementary approximation of second-order properties. A typical completeness problem in that respect can be stated as follows: given a second-order theory T, and a first-order fragment T_{1} of T, is the class of models of T_{1} elementarily approximated in the class of models of T? In other words: is T_{1} complete with respect to the class of models of T ? An interesting special case is the case of Π_{1}^{1}-theories. For every Π_{1}^{1}-sentence Φ we can consider the first-order schema Φ_{1}^{p} obtained from Φ by restricting the universal second-order quantification to all instances of parametrically first-order definable relations and functions and thus obtain a natural first-order fragment of the theory of Φ. A number of elaborated positive completeness results for such fragments are obtained in [Doets, 87] and [Backofen et al, 95]. It would be interesting to explore this problem using logical topologies.

Finally, there are a number of basic model-theoretic constructions used in modal logic to transform Kripke models into “standard” ones for the logic under consideration, such as Segerberg’s filtration and bisimulation (which subsumes most of the others), the latter, inter alia, introduced in modal logic by Johan van Benthem under the name of zig-zag morphism (see [van Benthem, 1984]). We hope that these constructions can be linked into the topological framework discussed here and thus the toolkit for proving completeness in modal logic can be strengthened and expanded.

References

[Backofen et al, 95] Backofen R., J. Rogers, & K. Vijay-Shanker, A First-order Axiomatization of the Theory of Finite Trees, Journal of Logic, Language and Information, 4, 1995, 5-39.

[Barwise and Feferman, 1985] Barwise J. and S. Feferman (eds.) Model-Theoretic Logics, Springer-Verlag, 1985.

[van Benthem, 1984] van Benthem J., Correspondence Theory, in: D. Gabbay and F. Guenthner (eds.), Handbook of Philosophical Logic, vol. II, pp 167-247, Reidel, Dordrecht, 1984.

[van Benthem, 1985] van Benthem J., Modal Logic and Classical Logic, Bibliopolis, Napoli, 1985.

[Cifuentes et al, 1996] Cifuentes J., A. Sette, D. Mundici, Cauchy Completeness in Elementary Logic, J. Symb. Logic, 61(4), 1996, 1153-1157.

[Doets, 87] Doets K., Completeness and Decidability, Ph. D. Thesis, Univ. of Amsterdam, 1987.

[Ebbinghaus et al, 94] Ebbinghaus H.-D., J. Flum, W. Thomas, Mathematical Logic, Springer-Verlag, 2nd ed., 1994.

[Engelking, 85] Engelking R., General Topology (2nd ed.), PWN, Warsaw, 1985.

[Fraïssé 67]  Fraïssé R.,  Course  de  logique

mathématique, tome 1, Gauthier-Villars, Paris, 1967.

[Goldblatt, 1985] Goldblatt R., On the Role of the Baire Category Theorem and Dependent Choice in the Foundations of Logic, J. Symb. Logic, 50(2), 1985, 412-422.

[Hodges, 93] Hodges W., Model Theory, Cambridge Univ. Press, 1993.

[Goranko, 98] Goranko V., Discrete trees and finite branching, manuscript, 1999.

[Rasiowa and Sikorski, 1963] Rasiowa H. and R. Sikorski, The Mathematics of Metamathematics, PWN, Warsaw, 1963.