We give syntactic characterizations of1. the theories whose categories of models are closed under the formation of pullbacks, and of2. the locally ω-polypresentable categories.A somewhat typical example is the category of algebraically closed fields. Case is proved by classical model-theoretic methods; it solves a problem raised by H. Volger . The solution of case is in the spirit of the ones for the locally ω-presentable and ω-multipresentable cases found by M. Coste and P.T. Johnstone respectively. The problem was raised in (...) the context of Domain Theory by F. Lamarche. (shrink)

Let (K, v) be a henselian valued field of characteristic 0. Then K admits a definable partition on each piece of which the leading term of a polynomial in one variable can be computed as a definable function of the leading term of a linear map. The main step in obtaining this partition is an answer to the question, given a polynomial f(x) ∈ K[x], what is v(f(x))? Two applications are given: first, a constructive quantifier elimination relative to the leading (...) terms, suggesting a relative decision procedure; second, a presentation of every definable subset of K as the pullback of a definable set in the leading terms subjected to a linear translation. (shrink)

We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $ -formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$. As (...) a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $\mathcal {K}$ be positively computably embeddable in $\mathcal {K}'$ by $\Phi $, then for every $\Pi ^p_\alpha $ formula $\xi $ in the vocabulary of $\mathcal {K}'$ there is a $\Pi ^p_\alpha $ formula $\xi ^{*}$ in the vocabulary of $\mathcal {K}$ such that for all $\mathcal {A}\in \mathcal {K}$, $\mathcal {A}\models \xi ^{*}$ if and only if $\Phi (\mathcal {A})\models \xi $. We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings. (shrink)

Image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. This unary type constructor [A] has turned up previously in a syntactic form as a way of erasing computational content, and formalizing a notion of proof irrelevance. Indeed, semantically, the notion of a support is sometimes used as surrogate proposition asserting inhabitation of an indexed family. We give rules for bracket types in dependent type theory and provide complete semantics using (...) regular categories. We show that dependent type theory with the unit type, strong extensional equality types, strong dependent sums, and bracket types is the internal type theory of regular categories, in the same way that the usual dependent type theory with dependent sums and products is the internal type theory of locally Cartesian closed categories. We also show how to interpret first-order logic in type theory with brackets, and we make use of the translation to compare type theory with logic. Specifically, we show that the propositions-as-types interpretation is complete with respect to a certain fragment of intuitionistic first-order logic, in the sense that a formula from the fragment is derivable in intuitionistic first-order logic if, and only if, its interpretation in dependent type theory is inhabited. As a consequence, a modified double-negation translation into type theory (without bracket types) is complete, in the same sense, for all of classical first-order logic. (shrink)

Working in the fragment of Martin-Löfs extensional type theory [12] which has products (but not sums) of dependent types, we consider two additional assumptions: firstly, that there are (strong) equality types; and secondly, that there is a type which is universal in the sense that terms of that type name all types, up to isomorphism. For such a type theory, we give a version of Russell's paradox showing that each type possesses a closed term and (hence) that all terms of (...) each type are provably equal. We consider the kind of category theoretic structure which corresponds to this kind of type theory and obtain a categorical version of the paradox. A special case of this result is the degeneracy of a locally cartesian closed category with a morphism which is generic in the sense that every other morphism in the category can be obtained from it via pullback. (shrink)

The notion of a natural model of type theory is defined in terms of that of a representable natural transfomation of presheaves. It is shown that such models agree exactly with the concept of a category with families in the sense of Dybjer, which can be regarded as an algebraic formulation of type theory. We determine conditions for such models to satisfy the inference rules for dependent sums Σ, dependent products Π, and intensional identity types Id, as used in (...) homotopy type theory. It is then shown that a category admits such a model if it has a class of maps that behave like the abstract fibrations in axiomatic homotopy theory: they should be stable under pullback, closed under composition and relative products, and there should be weakly orthogonal factorizations into the class. It follows that many familiar settings for homotopy theory also admit natural models of the basic system of homotopy type theory. (shrink)

We give a syntactic characterization of (finitary) theories whose categories of models are closed under the formation of connected limits (respectively the formation of pullbacks and substructures) in the category of all structures. They are also those theories whose consistent extensions by new atomic facts admit in each component an initial structure (respectively an initial term structure), and also thoseT for whichM(T) is locally finitely multi-presentable in a canonical way. We also show that these two properties of theories are nonuniform.

We show that a morphism of locales is open if and only if all its pullbacks are skeletal in the sense of [P.T. Johnstone, Factorization theorems for geometric morphisms, II, in: Categorical Aspects of Topology and Analysis, in: Lecture Notes in Math., vol. 915, Springer-Verlag, 1982, pp. 216–233], i.e. pulling back along them preserves denseness of sublocales . This result may be viewed as the ‘dual’ of the well-known characterization of proper maps as those which are stably closed. We also (...) investigate the circumstances in which a particular sublocale, or set of sublocales, of a given locale, may be ‘declared closed’. (shrink)

We give a formal interpretation of Martin-Löf's Constructive Theory of Types in Elementary Topos Theory which is presented as a formalised theory with intensional equality of objects. Types are interpreted as arrows and variables as sections of their types. This is necessary to model correctly the working of the assumption x ∈ A. Then intensional equality interprets equality of types. The normal form theorem which asserts that the interpretation of a type is intensional equal to the pullback of its (...) “alignment” along some “base” arrow relates this interpretation to categorical semantic of types. (shrink)

This paper uses the locale theory approach to topology. Two descriptions are given of all locale limits, the first description using suplattice constructions and the second preframe constructions. The symmetries between these two approaches to locale theory are explored. Given an informal assumption that open locale maps are parallel to proper maps we argue that various pairs of locale theory results are ‘parallel’, that is, identical in structure but prove facts about proper maps on one side of the pair and (...) about open maps on the other. The pairs of results are: pullback stability of proper/open maps, regularity of the category of compact Hausdorff/discrete locales, and theorems on information systems. Some remarks are included on a possible formalization of this parallel as a duality. (shrink)

Let Ω be the least uncountable ordinal. Let K(Ω) be the category where the objects are the countable ordinals and where the morphisms are the strictly monotonic increasing functions. A dilator is a functor on K(Ω) which preserves direct limits and pullbacks. Let $\tau \Omega: \xi = \omega^\xi\}$ . Then τ has a unique "term"-representation in Ω. λξη.ω ξ + η and countable ordinals called the constituents of τ. Let $\delta and K(τ) be the set of the constituents of τ. (...) Let β = max K(τ). Let [ β ] be an occurrence of β in τ such that τ [ β] = τ. Let $\bar \theta$ be the fixed point-free version of the binary Aczel-Buchholz-Feferman-function (which is defined explicitly in the text below) which generates the Bachman-hierarchy of ordinals. It is shown by elementary calculations that $\xi \mapsto \bar \theta(\tau \lbrack \gamma + \xi \rbrack)\delta$ is a dilator for every $\gamma > \max\{\beta. \delta.\omega\}$. (shrink)

In this paper we study the category of hyper MV-algebras and we prove that it has a terminal object and a coequalizer. We show that Jia's construction can be modified to provide a free hyper MV-algebra by a set. We use this to show that in the category of hyper MV-algebras the monomorphisms are exactly the one-to-one homomorphisms.