In this paper, we rigorously prove the existence of type-level ordered pairs in Quine’s New Foundations with atoms, augmented by the axiom of infinity and the axiom of choice (NFU + Inf + AC). The proof uses the cardinal squaring principle; more precisely, its instance for the (infinite) universe (VCSP), which is a theorem of NFU + Inf + AC. Therefore, we have a justification for proposing a new axiomatic extension of NFU, in order to obtain type-level ordered pairs almost (...) from the beginning. This axiomatic extension is NFU + Inf + AC + VCSP, which is equivalent to NFU + Inf + AC, but easier to reason about. (shrink)

The main feature of NF/NFU is the notion of stratification, which sets it apart from other set theories. We define stratification and prove constructively that every stratified formula has the (unique) least assignment of types. The basic notion of stratification is concerned only with variables, but we extend it to abstraction terms in order to simplify further development. We reflect on nested abstraction terms, proving that they get the expected types. These extensions enable us to check whether some complex formula (...) is stratified without rewriting it in the basic language. We also introduce natural numbers and a variant of the axiom of infinity, in order to precisely introduce type level ordered pairs, which are crucial in simplifying the definitions in the last part of the article. Using these notions we can easily define the sets of ordinal and cardinal numbers, which we show at the end of the article. The same approach can be readily applied to NF. (shrink)

Provability logic is a modal logic for studying properties of provability predicates, and Interpretability logic for studying interpretability between logical theories. Their natural models are GL-models and Veltman models, for which the accessibility relation is well-founded. That’s why the usual counterexample showing the necessity of finite image property in Hennessy-Milner theorem (see [1]) doesn’t exist for them. However, we show that the analogous condition must still hold, by constructing two GL-models with worlds in them that are modally equivalent but not (...) bisimilar, and showing how these GL-models can be converted to Veltman models with the same properties. In the process we develop some useful constructions: games on Veltman models, chains, and general method of transformation from GL-models/frames to Veltman ones. (shrink)

New Foundations with Urelements (NFU) is a theory that extends Quine’s original theory (New Foundations) by adding “urelements” (atoms). It was discovered by Jensen in 1969, who proved that NFU is relatively consistent with Peano arithmetic and consequently with Zermelo–Fraenkel set theory (ZF). Jensen’s proof is rather hard to follow, so Boffa introduced a more straightforward method of constructing models for NFU from a model of ZF. However, Boffa’s presentation of his construction is extremely terse with many essential details omitted, (...) since he probably only wanted to emphasize the differences from Jensen’s construction. Our main goal is to elaborate on this construction in great detail, and also to prove that the said construction yields some results that are either not present in the contemporary literature, or are accepted as true at face value. Namely, besides proving that this construction gives a model for NFU, we will also use it to define models for NFU with the Axiom of Infinity, NFU with the Axiom of Choice, and NFU with both of those axioms. (shrink)

Normal forms for wide classes of closed IL formulas were given in Čačić and Vuković. Here we quantify asymptotically, in exact numbers, how wide those classes are. As a consequence, we show that the “majority” of closed IL formulas have GL-equivalents, and by that, they have the same normal forms as GL formulas. Our approach is entirely syntactical, except for applying the results of Čačić and Vuković. As a byproduct we devise a convenient way of computing asymptotic behaviors of somewhat (...) general classes of formulas given by their grammar rules. Its applications do not require any knowledge of the recurrence relations, generating functions, or the asymptotic enumeration methods, as all these are incorporated into two fundamental parameters. (shrink)