Harold Hodes

Two slogans define structuralism: contemporary mathematics studies structures; mathematical objects are places in those structures. Shapiro’s version of structuralism posits abstract objects of three sorts. A system is “a collection of objects with certain relations” between these objects. “An extended family is a system of people with blood and marital relationships.” A baseball defense, e.g., the Yankee’s defense in the first game of the 1999 World Series, is a also a system, “a collection of people with on-field spatial and ‘defensive-role’ relations”. “A structure is the abstract form of a system” ; it consists of “a collection of places [sometimes called positions or offices] and a finite collection of functions and relations on these places”.

I prove that the Boolean Prime Ideal Theorem is equivalent, under some weak set-theoretic assumptions, to what I will call the Cut-for-Formulas to Cut-for-Sets Theorem: for a set F and a binary relation |- on Power(F), if |- is finitary, monotonic, and satisfies cut for formulas, then it also satisfies cut for sets. I deduce the CF/CS Theorem from the Ultrafilter Theorem twice; each proof uses a different order-theoretic variant of the Tukey- Teichmüller Lemma. I then discuss relationships between various cut-conditions in the absence of finitariness or of monotonicity.

This paper and its sequel “look under the hood” of the usual sorts of proof-theoretic systems for certain well-known intuitionistic and classical propositional modal logics. Section 1 is preliminary. Of most importance: a marked formula will be the result of prefixing a formula in a propositional modal language with a step-marker, for this paper either 0 or 1. Think of 1 as indicating the taking of “one step away from 0.” Deductions will be constructed using marked formulas. Section 2 presents the model-theoretic concepts, based on those in [7], that guide the rest of this paper. Section 3 presents Natural Deduction systems IK and CK, formalizations of intuitionistic and classical one-step versions of K. In these systems, occurrences of step-markers allow deductions to display deductive structure that is covered over in familiar “no step” proof-theoretic systems for such logics. Box and Diamond are governed by Introduction and Elimination rules; the familiar K rule and Necessitation are derived (i.e. admissible) rules. CK will be the result of adding the 0-version of the Rule of Excluded Middle to the rules which generate IK. Note: IK is the result of merely dropping that rule from those generating CK, without addition of further rules or axioms (as was needed in [7]). These proof-theoretic systems yield intuitionistic and classical consequence relations by the obvious definition. Section 4 provides some examples of what can be deduced in IK. Section 5 defines some proof-theoretic concepts that are used in Section 6 to prove the soundness of the consequence relation for IK (relative to the class of models defined in Section 2.) Section 7 proves its completeness (relative to that class). Section 8 extends these results to the consequence relation for CK. (Looking ahead: Part 2 will investigate one-step proof-theoretic systems formalizing intuitionistic and classical one-step versions of some familiar logics stronger than K.)

Part 1 [Hodes, 2021] “looked under the hood” of the familiar versions of the classical propositional modal logic K and its intuitionistic counterpart. This paper continues that project, addressing some familiar classical strengthenings of K and GL), and their intuitionistic counterparts. Section 9 associates two intuitionistic one-step proof-theoretic systems to each of the just mentioned intuitionistic logics, this by adding for each a new rule to those which generated IK in Part 1. For the systems associated with the intuitionistic counterparts of D and T, these rules are “pure one-step”: their schematic formulations does not use □ or ♢. For the systems associated with the intuitionistic counterparts of K4, etc., these rules meet these conditions: neither □ nor ♢ is iterated; none use both □ and ♢. The join of the two systems associated with each of these familiar logics is the full one-step system for that intuitionistic logic. And further “blended” intuitionistic systems arise from joining these systems in various ways. Adding the 0-version of Excluded Middle to their intuitionistic counterparts yields the one-step systems corresponding to the familiar classical logics. Each proof-theoretic system defines a consequence relation in the obvious way. Section 10 examines inclusions between these consequence relations. Section 11 associates each of the above consequence relations with an appropriate class of models, and proves them sound with respect to their appropriate class. This allows proofs of some failures of inclusion between consequence relations. Section 12 proves that the each consequence relation is complete or weakly complete, that relative to its appropriate class of models. The Appendix presents three further results about some of the intuitionistic consequence relations discussed in the body of the paper. For Keywords, see Part 1.

Relative to any reasonable frame, satisfiability of modal quantificational formulae in which “= ” is the sole predicate is undecidable; but if we restrict attention to satisfiability in structures with the expanding domain property, satisfiability relative to the familiar frames (K, K4, T, S4, B, S5) is decidable. Furthermore, relative to any reasonable frame, satisfiability for modal quantificational formulae with a single monadic predicate is undecidable ; this improves the result of Kripke concerning formulae with two monadic predicates.

Stewart Shapiro, Foundations without foundationalism: A case for second-order logic. Oxford: Clarendon Press, 1991. xvii + 277 pp. £35.00 A. Diaz, J, Echeverria and A. Ibarra (eds.), Structures in mathematical theories: Reports of the San Sebastian International Symposium, September 25‐29, 1990. Erandio (Vizcaya): Universidad del Pais Vasco, 1990, 492 pp. No price stated J. Echeverria, A. Ibarra, and T, Mormann (eds.), The space of mathematics: philosophical, epistemological, and historical explorations, Berlin and New York: Walter de Gruyter, 1992. xvii + 422 pp., DM 228.00 Jean-Michel Salanskis and Hourya Sinaceur (eds.) Le labyrinthe du continu. Paris: Springer‐Verlag France, 1992. xi + 452 pp. No price stated J. Largeault (ed.) Intuitionisme et théorie de la démonstration. Textes de Bernays, Brouwer, Gentzen, Gödel, Hubert, Kreisel, Weyl. Paris: Vrin, 1992. 556 pp. FF 320 Claude Panaccio, Les mots, les concepts et les choses. La sémantique de Guillaume d’Occam et le nominalisme d’aujourd’hui (Collection Analytiques, volume 3.) Montréal, Bellarmin; Paris, Vrin: 1991. 288 pp. 29,95 Can.$ Desmond Paul Henry, Medieval mereology. (Bochumer Studien zur Philosophie, volume 16.) Amsterdam and Philadelphia: B. R. Grüner, 1991. xxv + 609 pp. Dfl. 240/$130 Stefano Besoli, Il valore della verità, Studio sulla ‘logica della validità’ nelpensiero di Lotze, Firenze: Ponte alle Grazie, 1992, 238 pp. 35000 Lire The Essential Peirce, Selected Philosophical Writings. Volume 1 (1867‐1893). Edited by Nathan Houser and Christian Kloesel. Bloomington and Indian‐apolis: Indiana University Press, 1992. xli + 399 pp. £33.50 (cloth)/£15.99 (paper) Joseph Brent, Charles Sanders Peirce, A Life, Foreword by Thomas Sebeok. Bloomington and Indianapolis: Indiana University Press, 1993. xvi + 386 pp. £28.50 The Collected Papers of Bertrand Russell, Volume 6, Logical and Philosophical Papers 1909‐13, Edited by John G. Slater with the assistance of Bernd Frohmann, London and New York: Routledge, 1992, lxix + 562 pp. £100.00 Francisco Rodriguez‐Consuegra, The mathematical philosophy of Bertrand Russell: Origins and Development. Basel: Birkhäuser Verlag 1991. xiv + 236pp. SFr 98.00 J. Alberto Coffa, The semantic tradition from Kant to Carnap: to the Vienna station, Cambridge: Cambridge University Press, 1991. xi + 445 pp. No price stated Peter Simons. Philosophy and logic in central Europe from Bolzano to Tar ski: selected essays. Dordrecht, Kluwer, 1992. xiv + 441 pp. DA230, $139.00/£79.00 Imre Ruzsa, Intensional logic revisited, Budapest: 1991. viii + 146pp. No price stated W. T. Parry and E. A. Hacker, Aristotelian logic. Albany, NY: State University of New York Press, 1991. x + 545 pp. $49,50 (boards)/$16.95 (paper) P. Bailhache, Essai de logique déontique. Paris: Vrin, 1991. 224 pp. 168F G. Sher, The bounds of logic, A generalized viewpoint, Cambridge, Massachusetts and London, England: The MIT Press, 1991. xv + 178 pp Julian Roberts, The logic of reflection. New Haven and London: Yale University Press, 1992. vii + 307 pp, £25.00 S. Stenlund, Language and Philosophical Problems. London: Routledge, 1990. 231 pp. £35.00 G. Corsi, M, L, Dalla Chiara and G. C, Ghirardi (eds,), Bridging the gap: philosophy, mathematics, and physics, Dordrecht: Kluwer, 1993, xi + 320pp, Dfl. 175/£60.00 Katalin G. Havas, Thought, Language and Reality in Logic. Budapest: Akadémiai Kiadö, 1992. 211 pp. $22.00 K. Devlin, Logic and Information. Cambridge: Cambridge University Press, 1991. xii + 308 pp. £17.95 Bernard Bolzano, Les paradoxes de l’infini, Introduction and translation by Hourya Sinaceur. Paris: Seuil, 1993. 192pp. 140 Ffr Denis Vernant, La philosophie mathématique de Russell. Paris: Vrin, 1993. 509pp. 174 Ffr Anita Burdman Feferman, Politics, logic, and love: The life of Jean van Heijenoort. London: Jones and Bartlett, 1993. xv + 415pp. $29.95.