Marcus Holmes

This is a brief report on results reported at length in our paper [2], made for the purpose of a presentation at the workshop to be held in November 2011 in Cambridge on the Principia Mathematica of Russell and Whitehead ([?], hereinafter referred to briefly as PM ). That paper grew out of a reading of the paper [3] of Kamareddine, Nederpelt, and Laan. We refereed this paper and found it useful for checking their examples to write our own independent computer type-checker for the type system of PM ([1]), which led us to think carefully about formalization of the language and the type system of PM A modern mathematical logician reading PM finds that it is not completely formalized in a modern sense. The type theory in particular is inarguably not formalized, as no notation for types is given at all! In PM itself, the only type annotations which appear are occasional numerical indices indicating order; the type notation we use here extends one introduced later by Ramsey. The authors of PM regard the absence of explicit indications of type as a virtue of their system: they call it “systematic ambiguity”; modern computer scientists refer to this as “polymorphism”. The language of PM is also not completely formalized, and it is typographically inconvenient for computer software to which ASCII input is to be given. The notation of PM for abstractions (propositional functions) does not use head binders; the order of the arguments of a complex expression is determined by the alphabetical order of the bound variables. For example ˆa < ˆb is the “less than” relation while ˆb < ˆa is the “greater than” relation (this is indicated by the alphabetical order of the variables). In PM , the fact that a variable is bound in a propositional function is indicated by circumflexing it. Variables bound by quantifiers are not circumflexed. A feature of the notation of [3], carried over into ours, is that no circumflexes are used: notations for propositions and the corresponding propositional functions are identical..

Andrzej Kisielewicz has proposed three systems of double extension set theory of which we have shown two to be inconsistent in an earlier paper. Kisielewicz presented an argument that the remaining system interprets ZF, which is defective: it actually shows that the surviving possibly consistent system of double extension set theory interprets ZF with Separation and Comprehension restricted to 0 formulas. We show that this system does interpret ZF, using an analysis of the structure of the ordinals.

An ω-model (a model in which all natural numbers are standard) of the predicative fragment of Quine's set theory "New Foundations" (NF) is constructed. Marcel Crabbe has shown that a theory NFI extending predicative NF is consistent, and the model constructed is actually a model of NFI as well. The construction follows the construction of ω-models of NFU (NF with urelements) by R. B. Jensen, and, like the construction of Jensen for NFU, it can be used to construct α-models for any ordinal α. The construction proceeds via a model of a type theory of a peculiar kind; we first discuss such "tangled type theories" in general, exhibiting a "tangled type theory" (and also an extension of Zermelo set theory with Δ 0 comprehension) which is equiconsistent with NF (for which the consistency problem seems no easier than the corresponding problem for NF (still open)), and pointing out that "tangled type theory with urelements" has a quite natural interpretation, which seems to provide an explanation for the more natural behaviour of NFU relative to the other set theories of this kind, and can be seen anachronistically as underlying Jensen's consistency proof for NFU

This paper discusses a sequence of extensions ofNFU, Jensen's improvement of Quine's set theory “New Foundations” (NF) of [16].The original theoryNFof Quine continues to present difficulties. After 60 years of intermittent investigation, it is still not known to be consistent relative to any set theory in which we have confidence. Specker showed in [20] thatNFdisproves Choice (and so proves Infinity). Even if one assumes the consistency ofNF, one is hampered by the lack of powerful methods for proofs of consistency and independence such as are available for use withZFC; very clever work has been done with permutation methods, starting with [18] and [5], and exemplified more recently by [14], but permutation methods can only be applied to show the consistency or independence of unstratified sentences (see the definition ofNFUbelow for a definition of stratification). For example, there is no method available to determine whether the assertion “the continuum can be well-ordered” is consistent with or independent ofNF. There is one substantial independence result for an assertion with nontrivial stratified consequences, using metamathematical methods: this is Orey's proof of the independence of the Axiom of Counting fromNF(see below for a statement of this axiom).We mention these difficulties only to reassure the reader of their irrelevance to the present work. Jensen's modification of “New Foundations” (in [13]), which was to restrict extensionality to sets, allowing many non-sets (urelements) with no elements, has almost magical effects.

We analyze the representation of binary relations in general, and in particular of functions and of total antisymmetric relations, in monadic third order logic, that is, the simple typed theory of sets with three types. We show that there is no general representation of functions or of total antisymmetric relations in this theory. We present partial representations of functions and of total antisymmetric relations which work for large classes of these relations, and show that there is an adequate representation of cardinality in this theory. The relation of our work to similar work by Henrard and Allen Hazen is discussed. This work can be understood as part of a program of assessing the capabilities of weak logical frameworks: our results are applicable for example, to the framework in David Lewis’s Parts of Classes.

Systems TRC and TRCU of illative combinatory logic are introduced and shown to be equivalent in consistency strength and expressive power to Quine's set theory ‘New Foundations’ and the fragment NFU + Infinity of NF described by Jensen, respectively. Jensen demonstrated the consistency of NFU + Infinity relative to ZFC; the question of the consistency of NF remains open. TRC and TRCU are presented here as classical first-order theories, although they can be presented as equational theories; they are not constructive

The usual construction of models of NFU (New Foundations with urelements, introduced by Jensen) is due to Maurice Boffa. A Boffa model is obtained from a model of (a fragment of) Zermelo–Fraenkel with Choice (ZFC) with an automorphism which moves a rank: the domain of the Boffa model is a rank that is moved. “Most” elements of the domain of the Boffa model are urelements in terms of the interpreted NFU. The main result of this paper is that the restriction of the membership relation of the original model of set theory with automorphism to the domain of the Boffa model is first-order definable in the language of NFU. In particular, all information about the extensions in the original model of the urelements of the model of NFU is definable in terms of NFU. A corollary (answering a question of Thomas Forster) is that the urelements in a Boffa model are not homogeneous

This paper described a formal theory of type judgments for propositional logic notations of PM; I felt the need of my own automated type checker to check their examples. The type checker I wrote did indeed serve to help me referee the paper, but also took a rather different approach to notation and typing for propositional functions of PM, which proved worth writing up independently in our own paper: Holmes, M. Randall, “Polymorphic type– checking for the ramified theory of types of Principia Mathematica”, in Fairouz Kamareddine, ed., Thirty–five Years of Automating Mathematics, Kluwer, 2003, pp. 173-215.

Three systems of double extension set theory have been proposed by Andrzej Kisielewicz in two papers. In this paper, it is shown that the two stronger systems are inconsistent, and that the third, weakest system does not admit extensionality for general sets or the use of general sets as parameters in its comprehension scheme. The parameter-free version of the comprehension principle of double extension set theory is also shown to be inconsistent with extensionality. The definitions of the systems and a self-contained exposition of their properties is given, sufficient to develop the inconsistency proofs.