This paper introduces a new family of models of intensional Martin-L "of type theory. We use constructive ordered algebra in toposes. Identity types in the models are given by a notion of Moore path. By considering a particular gros topos, we show that there is such a model that is non-truncated, i.e. contains non-trivial structure at all dimensions. In other words, in this model a type in a nested sequence of identity types can contain more than one element, no matter how great the degree of nesting. Although inspired by existing non-truncated models of type theory based on simplicial and on cubical sets, the notion of model presented here is notable for avoiding any form of Kan filling condition in the semantics of types.
Although our use of constructive algebra within toposes to make models of intensional type theory appears to be new, we are not the only ones to consider using some form of path with strictly unitary and associative composition to model identity types with a judgemental computation rule. Van den Berg and Garner @cite_7 use topological Moore paths and a simplicial version of them to get instances of their notion of for modelling identity types. The results of Sections and show that any ordered abelian group in a topos induces a path object category structure on that topos; and since the notion of fibration we use (Definition ) is closely related to the one used in @cite_7 (see Proposition 6.1.5 of that paper), one can get alternative, more abstract categorical proofs of Theorems and from the work of Van den Berg and Garner. However, the concrete calculations in the internal language that we give are quite simple by comparison; and this approach proves its worth in , whose results on obtaining function extensionality from the ordered ring structure are new.
@cite_7
1997582403 2550342065 2113550426 2748981990
In this paper we construct new categorical models for the identity types of Martin-Lof type theory, in the categories Top of topological spaces and SSet of simplicial sets. We do so building on earlier work of Awodey and Warren [2009], which has suggested that a suitable environment for the interpretation of identity types should be a category equipped with a weak factorization system in the sense of Bousfield--Quillen. It turns out that this is not quite enough for a sound model, due to some subtle coherence issues concerned with stability under substitution; and so our first task is to introduce a slightly richer structure, which we call a homotopy-theoretic model of identity types, and to prove that this is sufficient for a sound interpretation. Now, although both Top and SSet are categories endowed with a weak factorization system---and indeed, an entire Quillen model structure---exhibiting the additional structure required for a homotopy-theoretic model is quite hard to do. However, the categories we are interested in share a number of common features, and abstracting these leads us to introduce the notion of a path object category. This is a relatively simple axiomatic framework, which is nonetheless sufficiently strong to allow the construction of homotopy-theoretic models. Now by exhibiting suitable path object structures on Top and SSet, we endow those categories with the structure of a homotopy-theoretic model and, in this way, obtain the desired topological and simplicial models of identity types. Author(s): Johnson, William Andrew | Advisor(s): Scanlon, Thomas | Abstract: This dissertation is a collection of results in model theory, related in one way or another to fields, NIP theories, and elimination of imaginaries. The most important result is a classification of dp-minimal fields, presented in Chapter 9. We construct in a canonical fashion a non-trivial Hausdorff definable field topology on any unstable dp-minimal field. Usingthis we classify the dp-minimal pure fields and valued fields up to elementary equivalence. Furthermore we prove that every VC-minimal field is real closed or algebraically closed.In Chapter 11, we analyze the theories of existentially closed fields with several valuations and orderings, as studied by van den Dries. We show that these model complete theories are NTP2, and analyze forking, dividing, and burden in these theories. The theory of algebraically closed fields with n independent valuation rings turns out to be an example of such a theory. This provides a new and natural example of an NTP2 theory which is neithersimple nor NIP, nor even a conceptual hybrid of something simple and something NIP.In Chapter 8, we exhibit a bad failure of elimination of imaginaries in a dense o-minimal structure. We produce an exotic interpretable set which cannot be put in definable bijection with a definable set, after naming any amount of parameters. However, we show that these exotic interpretable sets are still amenable to some of the tools of tame topology: they mustadmit nice definable topologies locally homeomorphic to definable sets.Chapter 12 proves the existence of Z nZ-valued definable strong Euler characteristics on pseudofinite fields, which measure the non-standard “size” of definable sets, mod n. The non-trivial result is that these “sizes” are definable in families of definable sets. This could probably be proven e cohomology, but we give a more elementary proof relying heavily on the theory of abelian varieties.We also present simplified and new proofs of several model-theoretic facts, including the definability of irreducibility and Zariski closure in ACF (Chapter 10), and elimination of imaginaries in ACVF (Chapter 6). This latter fact was originally proven by Haskell, Hrushovski, and Macpherson. We give a proof that is drastically simpler, inspired by Poizat’s proofs of elimination of imaginaries in ACF and DCF. The order-enriched category of monotonic predicate transformers over posets is a model of the refinement calculus of higher order imperative programs and pre-post specifications. This category is shown to be equivalent to the category of spans over ideal relations, and ideal relations are shown to be spans over monotonic functions between posets. To do this we use a skew span construction because the standard categorical span constructions are inapplicable. Axioms are given for products and coproducts of underlying posets as well as the homset as a coexponent, using inequations (for various kinds of lax adjunctions) and conditional equations (for adjunctions in subcategories) that are shown to uniquely determine the structures. The model is described in elementary terms using power allegories, an axiomatic calculus of relations, which makes the proofs accessible to non-specialists and shows that the results generalize to other base categories. We formalise the axiomatic set theory second-order ZF in the constructive type theory of Coq assuming excluded middle. In this setting we prove Zermelo’s embedding theorem for models, categoricity in all cardinalities, and the correspondence of inner models and Grothendieck universes. Our results are based on an inductive definition of the cumulative hierarchy eliminating the need for ordinals and transfinite recursion.