We develop domain theory in constructive and predicative univalent foundations (also known as homotopy type theory). That we work predicatively means that we do not assume Voevodsky's propositional resizing axioms. Our work is constructive in the sense that we do not rely on excluded middle or the axiom of (countable) choice. Domain theory studies so-called directed complete posets (dcpos) and Scott continuous maps between them and has applications in programming language semantics, higher-type computability and topology. A common approach to deal with size issues in a predicative foundation is to work with information systems, abstract bases or formal topologies rather than dcpos, and approximable relations rather than Scott continuous functions. In our type-theoretic approach, we instead accept that dcpos may be large and work with type universes to account for this. A priori one might expect that complex constructions of dcpos result in a need for ever-increasing universes and are predicatively impossible. We show that such constructions can be carried out in a predicative setting. We illustrate the development with applications in the semantics of programming languages: the soundness and computational adequacy of the Scott model of PCF and Scott's $D_\infty$ model of the untyped $\lambda$-calculus. We also give a predicative account of continuous and algebraic dcpos, and of the related notions of a small basis and its rounded ideal completion. The fact that nontrivial dcpos have large carriers is in fact unavoidable and characteristic of our predicative setting, as we explain in a complementary chapter on the constructive and predicative limitations of univalent foundations. Our account of domain theory in univalent foundations is fully formalised with only a few minor exceptions. The ability of the proof assistant Agda to infer universe levels has been invaluable for our purposes.
翻译:我们以建设性和预言性单一基础(也称为同质类型理论)发展了域论。我们的工作预言性地意味着我们不以Voevodsky的主张重塑轴心。我们的工作具有建设性,因为我们不依赖被排斥的中间或(可计算)选择的轴心。在它们之间进行所谓的直接整形(dcpos)和Scott连续的地图研究,并在编程语言语义、较高类型易变和结构学方面的应用中具有应用性。在预言性基础中处理大小问题的常见做法是,与信息系统、抽象基础或形式表情学而不是dcpos一起工作。我们的工作是具有建设性关系,而不是斯科特的连续功能。在我们的类型理论学方法中,我们相反地认为,dcpos可能很大,而与类型宇宙打交道的预言事只能对此负责。我们先行的模型性结构,使得我们不断增长的宇宙变得非正统。我们发现,而预知性地表明,这种结构基础的构造基础可以以正值为基础,而代言地解释着我们的货币的精度。