DIMACS TR: 96-08

Abstract Deducibility and Domain Theory

Authors: Vladimir Yu.Sazonov and Dmitri I.Sviridenko


According to the thesis ``computability = deducibility'' [D.Scott, LNCS 140] there are investigated intensional aspects of domain theory as mathematical theory of computability.

A logistic system is any pair of sets , where R \subseteq Conf(A) := Powerset(A) x (A union {#}), # \notin A. The intended interpretation: A is a set of sentences, R is a rule of inference, and # is a contradiction sign. As usually, R induces a relation |-_R \subseteq Conf(A) of (reflexive) deductive inference and also the classes Cl() \subseteq Powerset(A) of the closed sets under |-_R and Th() \subseteq Cl() of consistent closed sets (theories) partially ordered by the inclusion relation. The followimg more general notion of deducibility ||-_R, which may be non-reflexive, playes an important role. Let G ||-_R f iff there exists a (well-founded) tree of inference G ||-_R f which contains at least one configuration in R (i.e. is non-trivial). By imposing, if necessary, on deducibility notion suitable finitarity conditions (and others) it is possible to characterise rather naturally, from the point of view of the abovementioned thesis, various classes of domains, e.g. classes of all complete lattices with a base, conditionally complete partially ordered sets with a base, complete f_0-spaces (defined in [Ju.L.Ershov, Algebra and Logic, 11, N4], the same as Scott's algebraic domains; cf. also [D.Scott, LNCS 140] where only finitary reflexive deducibility is considered), Ershov's complete A_0-spaces [Algebra and Logic, 12, N4] = Scott's continuous domains, and Scott's continuous lattices. For example, Th(< A,|- >) is an (arbitrary) complete A_0-space under \subseteq if for some R \subseteq Conf(A) there holds

(1) G/f \in R => G is finite, (i.e. R is finitary),

(2) G ||-_R f => G^ ||-_R f, where G^ := union {g^ : g \in G and g^ := {h : g ||-_R h}, and

(3) G |- f <=> G ||-_R f^ and $G |- # <=> G ||-_R #.

The goal of this paper is just to give an English extended version of the above text published only in Russian [V.Yu.Sazonov and D.I.Sviridenko, Abstract Deducibility and Domain Theory, Seventh All Union Conference on Mathematical Logic, Abstracts, Novosibitsk, 1984, p. 158] in connection with a related recent paper [R.Hoofman, Continuous Information Systems, Information and Computation 105, 42--71 (1993)]. It contains also an Appendix to this Abstract (written by the first author) with additional details, proofs and some comparisons with Hoofman's approach.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-08.ps.gz

DIMACS Home Page