First-Order Logic with Isomorphism

arXiv1603.03092MaRDI QIDQ6271319

Dimitris Tsementzis

Publication date: 9 March 2016

Abstract: The Univalent Foundations requires a logic that allows us to define structures on homotopy types, similar to how first-order logic with equality ($ext{FOL}_{=}$) allows us to define structures on sets. We develop the syntax, semantics and deductive system for such a logic, which we call first-order logic with isomorphism ($ext{FOL}_{cong}$). The syntax of $ext{FOL}_{cong}$ extends $ext{FOL}_{=}$ in two ways. First, by incorporating into its signatures a notion of dependent sorts along the lines of Makkai's FOLDS as well as a notion of an $h$-level of each sort. Second, by specifying three new logical sorts within these signatures: isomorphism sorts, reflexivity predicates and transport structure. The semantics for $ext{FOL}_{cong}$ are then defined in homotopy type theory with the isomorphism sorts interpreted as identity types, reflexivity predicates as relations picking out the trivial path, and transport structure as transport along a path. We then define a deductive system $mathcal{D}_{cong}$ for $ext{FOL}_{cong}$ that encodes the sense in which the inhabitants of isomorphism sorts really do behave like isomorphisms and prove soundness of the rules of $mathcal{D}_{cong}$ with respect to its homotopy semantics. Finally, as an application, we prove that precategories, strict categories and univalent categories are axiomatizable in $ext{FOL}_{cong}$.

Has companion code repository: https://github.com/dimtsem/FOLiso

Mathematics Subject Classification ID

Model theory (03C99) Algebraic logic (03G99) Abstract deductive systems (03B22)

This page was built for publication: First-Order Logic with Isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6271319)