Abstract By limiting the range of the predicate variables in a second-order language, one may obtain restricted versions of second-order logic such as weak second-order logic or definable subset logic. In this note, we provide an infinitary strongly complete axiomatization for several systems of this kind having the range of the predicate variables as a parameter. The completeness argument uses simple techniques from the theory of Boolean algebras. This article is dedicated to our friend John N. Crossley on the occasion of his 86th birthday.

By Frege's Theorem is meant the result, implicit in Frege's Grundlagen, that, for any set E, if there exists a map υ from the power set of E to E satisfying the condition then E has a subset which is the domain of a model of Peano's axioms for the natural numbers. (This result is proved explicitly, using classical reasoning, in Section 3 of [1].) My purpose in this note is to strengthen this result in two directions: first, the premise will be weakened so as to require only that the map υ be defined on the family of (Kuratowski) finite subsets of the set E, and secondly, the argument will be constructive, i.e., will involve no use of the law of excluded middle. To be precise, we will prove, in constructive (or intuitionistic) set theory, the following Theorem. Let υ be a map with domain a family of subsets of a set E to E satisfying the following conditions: (i) ø ϵdom(υ) (ii)∀U ϵdom(υ)∀x ϵ E − UU ∪ x ϵdom(υ) (iii)∀UV ϵdom(5) υ(U) = υ(V) ⇔ U ≈ V. Then we can define a subset N of E which is the domain of a model of Peano's axioms.

Call a family of subsets of a set E inductive if and is closed under unions with disjoint singletons, that is, if A Frege structure is a pair (E, ν) with ν a map to E whose domain dom(ν) is an inductive family of subsets of E such that In [2] it is shown in a constructive setting that each Frege structure determines a subset which is the domain of a model of Peano's axioms. In this note we establish, within the same constructive setting, three facts. First, we show that the least inductive family of subsets of a set E is precisely the family of decidable Kuratowski finite subsets of E. Secondly, we establish that the procedure presented in [2] can be reversed, that is, any set containing the domain of a model of Peano's axioms determines a map which turns the set into a minimal Frege structure: here by a minimal Frege structure is meant one in which dom(ν) is the least inductive family of subsets of E. And finally, we show that the procedures leading from minimal Frege structures to models of Peano's axioms and vice-versa are mutually inverse. It follows that the postulation of a (minimal) Frege structure is constructively equivalent to the postulation of a model of Peano's axioms. All arguments will be formulated within constructive (intuitionistic) set theory.

Abstract We analyze Zorn's Lemma and some of its consequences for Boolean algebras in a constructive setting. We show that Zorn's Lemma is persistent in the sense that, if it holds in the underlying set theory, in a properly stated form it continues to hold in all intuitionistic type theories of a certain natural kind. (Observe that the axiom of choice cannot be persistent in this sense since it implies the law of excluded middle.) We also establish the persistence of some familiar results in the theory of (complete) Boolean algebras—notably, the proposition that every complete Boolean algebra is an absolute subretract. This (almost) resolves a question of Banaschewski and Bhutani as to whether the Sikorski extension theorem for Boolean algebras is persistent.

A key idea in both Frege's development of arithmetic in theGrundlagen[7] and Zermelo's 1904 proof [10] of the well-ordering theorem is that of a “type reducing” correspondence between second-level and first-level entities. In Frege's construction, the correspondence obtains betweenconceptandnumber, in Zermelo's (through the axiom of choice), betweensetandmember. In this paper, a formulation is given and a detailed investigation undertaken of a system ℱ of many-sorted first-order logic (first outlined in the Appendix to [6]) in which this notion of type reducing correspondence is accorded a central role and which enables Frege's and Zermelo's constructions to be presented in such a way as to reveal their essential similarity. By adapting Bourbaki's version of Zermelo's proof of the well-ordering theorem, we show that, within ℱ, any correspondencecbetween second-level entities (here calledconcepts) and first-level ones (here calledobjects) induces a well-ordering relationW(c) in a canonical manner. We shall see that, whencis the “Fregean” correspondence between concepts and cardinal numbers,W(c) is (the well-ordering of) the ordinalω+ 1, and whencis a “Zermelian” choice function on concepts,W(c) is a well-ordering of the universal concept embracing all objects. In ℱ an important role is played by the notion ofextensionof a concept. To each conceptXwe assume there is assigned an objecte(X) in such a way that, for any conceptsX, Ysatisfying a certain predicateE, we havee(X) =e(Y) iff the same objects fall underXandY.

The Sikorski Extension Theorem [6] states that, for any Boolean algebra A and any complete Boolean algebra B, any homomorphism of a subalgebra of A into B can be extended to the whole of A. That is, Inj: Any complete Boolean algebra is injective (in the category of Boolean algebras). The proof of Inj uses the axiom of choice (AC); thus the implication AC → Inj can be proved in Zermelo-Fraenkel set theory (ZF). On the other hand, the Boolean prime ideal theorem BPI: Every Boolean algebra contains a prime ideal (or, equivalently, an ultrafilter) may be equivalently stated as: The two element Boolean algebra 2 is injective, and so the implication Inj → BPI can be proved in ZF. In [3], Luxemburg surmises that this last implication cannot be reversed in ZF. It is the main purpose of this paper to show that this surmise is correct. We shall do this by showing that Inj implies that BPI holds in every Boolean extension of the universe of sets, and then invoking a recent result of Monro [5] to the effect that BPI does not yield this conclusion.

It is a well-known fact that two structures are ∞ω-equivalent if and only if they are isomorphic in some Boolean extension of the universe of sets (cf. [4]; an early allusion to this result appears in [8]). My principal object here is to show that arbitrary toposes defined over the category of sets may be used instead. Thus ∞ω-equivalence means isomorphism in the extremely general context of some universe of "variable" sets in which not only is much of the usual set-theoretic machinery unavailable but the underlying logic is not even classical. This provides further support for the view that ∞ω-equivalence is a relation between structures of fundamental importance.