We study elementary second order extensions of the theoryID 1 of non-iterated inductive definitions and the theoryPA Ω of Peano arithmetic with ordinals. We determine the exact proof-theoretic strength of those extensions and their natural subsystems, and we relate them to subsystems of analysis with arithmetic comprehension plusΠ 1 1 comprehension and bar induction without set parameters.

Büchi, J. R. The monadic second order theory of [omega symbol]₁.--Büchi, J. R. and Siefkes, D. Axiomatization of the monadic second order theory of [omega symbol]₁.

The paper argues that no second order theory is ontologically commited to anything beyond what its individual variables range over.

Let be a relational system whereby D is a nonempty set and P1 is an m1-ary relation on D. With we associate the (weak) monadic second-order theory consisting of the first-order predicate calculus with individual variables ranging over D; monadic predicate variables ranging over (finite) subsets of D; monadic predicate quantifiers; and constants corresponding to P1, P2, …. We will often use ambiguously to mean also the set of true sentences of.

We show that the weak monadic second order theory of the structure is first order interpretable in its automorphism group.

We prove that PTCN cannot be a model of U12. This implies that there exists a first order sentence of bounded arithmetic which is provable in U12 but does not hold in PTCN.

Let H be a proof system for quantified propositional calculus (QPC). We define the Σqj-witnessing problem for H to be: given a prenex Σqj-formula A, an H-proof of A, and a truth assignment to the free variables in A, find a witness for the outermost existential quantifiers in A. We point out that the Σq1-witnessing problems for the systems G*1and G1 are complete for polynomial time and PLS (polynomial local search), respectively. We introduce and study the systems G*0 and G0, (...) in which cuts are restricted to quantifier-free formulas, and prove that the Σqj-witnessing problem for each is complete for NC1. Our proof involves proving a polynomial time version of Gentzen’s midsequent theorem for G*0 and proving that G0-proofs are TC0-recognizable. We also introduce QPC systems for TC0 and prove witnessing theorems for them. We introduce a finitely axiomatizable second-order system VNC1 of bounded arithmetic which we prove isomorphic to Arai’s first order theory AID + Σb0-CA for uniform NC1. We describe simple translations of VNC1 proofs of all bounded theorems to polynomial size families of G*0 proofs. From this and the above theorem we get alternative proofs of the NC1 witnessing theorems for VNC1 and AID. (shrink)

We try to answer the question which is the “right” foundation of mathematics, second order logic or set theory. Since the former is usually thought of as a formal language and the latter as a first order theory, we have to rephrase the question. We formulate what we call the second order view and a competing set theory view, and then discuss the merits of both views. On the surface these two views seem to be (...) in manifest conflict with each other. However, our conclusion is that it is very difficult to see any real difference between the two. We analyze a phenomenon we call internal categoricity which extends the familiar categoricity results of second order logic to Henkin models and show that set theory enjoys the same kind of internal categoricity. Thus the existence of non-standard models, which is usually taken as a property of first order set theory, and categoricity, which is usually taken as a property of second order axiomatizations, can coherently coexist when put into their proper context. We also take a fresh look at complete second order axiomatizations and give a hierarchy result for second order characterizable structures. Finally we consider the problem of existence in mathematics from both points of view and find that second order logic depends on what we call large domain assumptions, which come quite close to the meaning of the axioms of set theory. (shrink)

This is an introductory paper to a series of results linking generic absoluteness results for second and third order number theory to the model theoretic notion of model companionship. Specifically we develop here a general framework linking Woodin’s generic absoluteness results for second order number theory and the theory of universally Baire sets to model companionship and show that (with the required care in details) a $$\Pi _2$$ -property formalized in an appropriate language for second (...) order number theory is forcible from some $$T\supseteq \mathsf {ZFC}+$$ large cardinals if and only if it is consistent with the universal fragment of T if and only if it is realized in the model companion of T. In particular we show that the first order theory of $$H_{\omega _1}$$ is the model companion of the first order theory of the universe of sets assuming the existence of class many Woodin cardinals, and working in a signature with predicates for $$\Delta _0$$ -properties and for all universally Baire sets of reals. We will extend these results also to the theory of $$H_{\aleph _2}$$ in a follow up of this paper. (shrink)

There is little doubt that a second-order axiomatization of Zermelo-Fraenkel set theory plus the axiom of choice (ZFC) is desirable. One advantage of such an axiomatization is that it permits us to express the principles underlying the first-order schemata of separation and replacement. Another is its almost-categoricity: M is a model of second-order ZFC if and only if it is isomorphic to a model of the form Vκ, ∈ ∩ (Vκ × Vκ) , for κ (...) a strongly inaccessible ordinal. (shrink)

Under a weak set-theoretic assumption we interpret second-order logic in the monadic theory of order.

Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).

In this paper we explore the connections between the monadic second-order theory of one successor (MSO[<] for short) and the theories of ?-layered structures for time granularity. We first prove that the decision problem for MSO[<] and that for a suitable first-order theory of the upward unbounded layered structure are inter-reducible. Then, we show that a similar result holds for suitable chain variants of the MSO theory of the totally unbounded layered structure (this allows us to (...) solve some decision problems about theories of time granularity left open by Franceschet et al. [FRA 06]). (shrink)

Both second-order logic and set theory can be used as a foundation for mathematics, that is, as a formal language in which propositions of mathematics can be expressed and proved. We take it upon ourselves in this paper to compare the two approaches, second-order logic on one hand and set theory on the other hand, evaluating their merits and weaknesses. We argue that we should think of first-order set theory as a very high-order logic.

Secrecy and “social cocooning” are critical mechanisms allowing the normalization of corruption within organizations. Less studied are processes of normalization that occur when corruption is an “open secret.” Drawing on an empirical study of Greek public-sector organizations, we suggest that a second-order normalization process ensues among non-corrupt onlookers both inside and beyond the organization. What is normalized at this level is not corruption, but its tolerance, which we disaggregate into agent-focused tolerance and structure-focused tolerance. Emphasizing the importance of (...) non-corrupt bystanders, we claim that second-order normalization helps corruption persist in situations where its presence is openly acknowledged. This adds an important new dimension to normalization theory and we unpack its implications for both future research and practice in this area. (shrink)

Open peer commentary on the article “Constructivist Model Building: Empirical Examples From Mathematics Education” by Catherine Ulrich, Erik S. Tillema, Amy J. Hackenberg & Anderson Norton. Upshot: I address the value of Ulrich et al.’s distinction between three types of second-order models. I conclude that their work contributes to the theorizing of adaptive teaching on the basis of a constructivist stance on knowing and learning.

In this paper, we generalize the set-theoretic translation method for polymodal logic introduced in [11] to extended modal logics. Instead of devising an ad-hoc translation for each logic, we develop a general framework within which a number of extended modal logics can be dealt with. We first extend the basic set-theoretic translation method to weak monadic second-order logic through a suitable change in the underlying set theory that connects up in interesting ways with constructibility; then, we show how (...) to tailor such a translation to work with specific cases of extended modal logics. (shrink)

Context: The problems that are most in need of interdisciplinary collaboration are “wicked problems,” such as food crises, climate change mitigation, and sustainable development, with many relevant aspects, disagreement on what the problem is, and contradicting solutions. Such complex problems both require and challenge interdisciplinarity. Problem: The conventional methods of interdisciplinary research fall short in the case of wicked problems because they remain first-order science. Our aim is to present workable methods and research designs for doing second-order (...) science in domains where there are many different scientific knowledges on any complex problem. Method: We synthesize and elaborate a framework for second-order science in interdisciplinary research based on a number of earlier publications, experiences from large interdisciplinary research projects, and a perspectivist theory of science. Results: The second-order polyocular framework for interdisciplinary research is characterized by five principles. Second-order science of interdisciplinary research must: 1. draw on the observations of first-order perspectives, 2. address a shared dynamical object, 3. establish a shared problem, 4. rely on first-order perspectives to see themselves as perspectives, and 5. be based on other rules than first-order research. Implications: The perspectivist insights of second-order science provide a new way of understanding interdisciplinary research that leads to new polyocular methods and research designs. It also points to more reflexive ways of dealing with scientific expertise in democratic processes. The main challenge is that this is a paradigmatic shift, which demands that the involved disciplines, at least to some degree, subscribe to a perspectivist view. Constructivist content: Our perspectivist approach to science is based on the second-order cybernetics and systems theories of von Foerster, Maruyama, Maturana & Varela, and Luhmann, coupled with embodied theories of cognition and semiotics as a general theory of meaning from von Uexküll and Peirce. (shrink)

After reviewing various natural bi-interpretations in urelement set theory, including second-order set theories with urelements, we explore the strength of second-order reflection in these contexts. Ultimately, we prove, second-order reflection with the abundant atom axiom is bi-interpretable and hence also equiconsistent with the existence of a supercompact cardinal. The proof relies on a reflection characterization of supercompactness, namely, a cardinal κ is supercompact if and only if every Π11 sentence true in a structure (...) M (of any size) containing κ in a language of size less than κ is also true in a substructure m≺M of size less than κ with m∩κ∈κ. (shrink)

In [12], Ernst Zermelo described a succession of models for the axioms of set theory as initial segments of a cumulative hierarchy of levelsUαVα. The recursive definition of theVα's is:Thus, a little reflection on the axioms of Zermelo-Fraenkel set theory shows thatVω, the first transfinite level of the hierarchy, is a model of all the axioms ofZFwith the exception of the axiom of infinity. And, in general, one finds that ifκis a strongly inaccessible ordinal, thenVκis a model of all of (...) the axioms ofZF. Doubtless, when cast as a first-order theory,ZFdoes not characterize the structures 〈Vκ,∈∩〉 forκa strongly inaccessible ordinal, by the Löwenheim-Skolem theorem. Still, one of the main achievements of [12] consisted in establishing that a characterization of these models can be attained when one ventures into second-order logic. For let second-orderZFbe, as usual, the theory that results fromZFwhen the axiom schema of replacement is replaced by its second-order universal closure. Then, it is a remarkable result due to Zermelo that second-orderZFcan only be satisfied in models of the form 〈Vκ,∈∩〉 forκa strongly inaccessible ordinal. (shrink)

In this article I investigate the phenomenon of minimum and minimal models of second-order set theories, focusing on Kelley–Morse set theory KM, Gödel–Bernays set theory GB, and GB augmented with the principle of Elementary Transfinite Recursion. The main results are the following. (1) A countable model of ZFC has a minimum GBC-realization if and only if it admits a parametrically definable global well order. (2) Countable models of GBC admit minimal extensions with the same sets. (3) (...) There is no minimum transitive model of KM. (4) There is a minimum β-model of GB+ETR. The main question left unanswered by this article is whether there is a minimum transitive model of GB+ETR. (shrink)

In this paper, we generalize the set-theoretic translation method for poly-modal logic introduced in [11] to extended modal logics. Instead of devising an ad-hoc translation for each logic, we develop a general framework within which a number of extended modal logics can be dealt with. We first extend the basic set-theoretic translation method to weak monadic second-order logic through a suitable change in the underlying set theory that connects up in interesting ways with constructibility; then, we show how (...) to tailor such a translation to work with specific cases of extended modal logics. (shrink)

Quine’s most important charge against second-, and more generally, higher-order logic is that it carries massive existential commitments. The force of this charge does not depend upon Quine’s questionable assimilation of second-order logic to set theory. Even if we take second-order variables to range over properties, rather than sets, the charge remains in force, as long as properties are individuated purely extensionally. I argue that if we interpret them as ranging over properties more reasonably (...) construed, in accordance with an abundant or deflationary conception, Quine’s charge can be resisted. This interpretation need not be seen as precluding the use of model-theoretic semantics for second-order languages; but it will preclude the use of the standard semantics, along with the more general Henkin semantics, of which it is a special case. To that extent, the approach I recommend has revisionary implications which some may find unpalatable; it is, however, compatible with the quite different special case in which the second-order variables are taken to range over definable subsets of the first-order domain, and with respect to such a semantics, some important metalogical results obtainable under the standard semantics may still be obtained. In my final section, I discuss the relations between second-order logic, interpreted as I recommend, and a strong version of schematic ancestral logic promoted in recent work by Richard Heck. I argue that while there is an interpretation on which Heck’s logic can be contrasted with second-order logic as standardly interpreted, when it is so interpreted, its differences from the more modest form of second-order logic I advocate are much less substantial, and may be largely presentational. (shrink)

Larry Wright and others have advanced causal accounts of functional explanation, designed to alleviate fears about the legitimacy of such explanations. These analyses take functional explanations to describe second order causal relations. These second order relations are conceptually puzzling. I present an account of second order causation from within the framework of Eells' probabilistic theory of causation; the account makes use of the population-relativity of causation that is built into this theory.

It is widely accepted that a theory of truth for arithmetic should be consistent, but -consistency is a highly desirable feature for such theories. The point has already been made for first-order languages, though the evidence is not entirely conclusive. We show that in the second-order case the consequence of adopting -inconsistent theories of truth are considered: the revision theory of nearly stable truth T # and the classical theory of symmetric truth FS. Briefly, we (...) present some conceptual problems with ω-inconsistent theories, and demonstrate some technical results that support our criticisms of such theories. (shrink)

This paper casts doubt on a recent criticism of Frege's theory of concepts and extensions by showing that it misses one of Frege's most important contributions: the derivation of the infinity of the natural numbers. We show how this result may be incorporated into the conceptual structure of Zermelo- Fraenkel Set Theory. The paper clarifies the bearing of the development of the notion of a real-valued function on Frege's theory of concepts; it concludes with a brief discussion of the claim (...) that the standard interpretation of second-order logic is necessary for the derivation of the Peano Postulates and the proof of their categoricity. (shrink)

In this paper, I shall provide a defence of second-order logic in the context of its use in the philosophy of mathematics. This shall be done by considering three problems that have been recently posed against this logic: (1) According to Resnik [1988], by adopting second-order quantifiers, we become ontologically committed to classes. (2) As opposed to what is claimed by defenders of second-order logic (such as Shapiro [1985]), the existence of non-standard models of (...) first-order theories does not establish the inadequacy of first—order axiomatisations (Melia [1995]). (3) In contrast with Shapiro’s suggestion (in his [1985]), second-order logic does not help us to establish referential access to mathematical objects (Azzouni [1994]). As I shall argue, each of these problems can be neatly solved by the second-order theorist. As a result, a case for second-order logic can be made. The first two problems will beconsidered rather briefly in the next section. The rest of the paper is dedicate to a discussion of the third. (shrink)

A second-order preference is a preference over preferences. This paper addresses the role that second-order preferences play in a theory of instrumental rationality. I argue that second-order preferences have no role to play in the prescription or evaluation of actions aimed at ordinary ends. Instead, second-order preferences are relevant to prescribing or evaluating actions only insofar as those actions have a role in changing or maintaining first-order preferences. I establish these claims (...) by examining and rejecting the view that second-order preferences trump first-order preferences. I also examine and reject the view that second-order preferences give additional normative force to an agent’s preferred first-order preferences. I conclude by arguing that second-order preferences should be integrated into an agent’s object-level preference ordering, and by explaining how best to make sense of this integration. (shrink)

This dissertation develops an inferentialist theory of meaning. It takes as a starting point that the sense of a sentence is determined by the rules governing its use. In particular, there are two features of the use of a sentence that jointly determine its sense, the conditions under which it is coherent to assert that sentence and the conditions under which it is coherent to deny that sentence. From this starting point the dissertation develops a theory of quantification as marking (...) coherent ways a language can be expanded and modality as the means by which we can reflect on the norms governing the assertion and denial conditions of our language. If the view of quantification that is argued for is correct, then there is no tension between second-order quantification and nominalism. In particular, the ontological commitments one can incur through the use of a quantifier depend wholly on the ontological commitments one can incur through the use of atomic sentences. The dissertation concludes by applying the developed theory of meaning to the metaphysical issue of necessitism and contingentism. Two objections to a logic of contingentism are raised and addressed. The resulting logic is shown to meet all the requirement that the dissertation lays out for a theory of meaning for quantifiers and modal operators. (shrink)

We discuss the differences between first-order set theory and second-order logic as a foundation for mathematics. We analyse these languages in terms of two levels of formalization. The analysis shows that if second-order logic is understood in its full semantics capable of characterizing categorically central mathematical concepts, it relies entirely on informal reasoning. On the other hand, if it is given a weak semantics, it loses its power in expressing concepts categorically. First-order set theory (...) and second-order logic are not radically different: the latter is a major fragment of the former. (shrink)

Ignacio Jane has argued that second-order logic presupposes some amount of set theory and hence cannot legitimately be used in axiomatizing set theory. I focus here on his claim that the second-order formulation of the Axiom of Separation presupposes the character of the power set operation, thereby preventing a thorough study of the power set of infinite sets, a central part of set theory. In reply I argue that substantive issues often cannot be separated from a (...) logic, but rather must be presupposed. I call this the logic-metalogic link. There are two facets to the logic-metalogic link. First, when a logic is entangled with a substantive issue, the same position on that issue should be taken at the meta- level as at the object level; and second, if an expression has a clear meaning in natural language, then the corresponding concept can equally well be deployed in a formal language. The determinate nature of the power set operation is one such substantive issue in set theory. Whether there is a determinate power set of an infinite set can only be presupposed in set theory, not proved, so the use of second-order logic cannot be ruled out by virtue of presupposing one answer to this question. Moreover, the legitimacy of presupposing in the background logic that the power set of an infinite set is determinate is guaranteed by the clarity and definiteness of the notions of all and of subset. This is also exactly what is required for the same presupposition to be legitimately made in an axiomatic set theory, so the use of second-order logic in set theory rather than first-order logic does not require any new metatheoretic commitments. (shrink)

Second-order logic has a number of attractive features, in particular the strong expressive resources it offers, and the possibility of articulating categorical mathematical theories (such as arithmetic and analysis). But it also has its costs. Five major charges have been launched against second-order logic: (1) It is not axiomatizable; as opposed to first-order logic, it is inherently incomplete. (2) It also has several semantics, and there is no criterion to choose between them (Putnam, J (...) Symbol Logic 45:464–482, 1980 ). Therefore, it is not clear how this logic should be interpreted. (3) Second-order logic also has strong ontological commitments: (a) it is ontologically committed to classes (Resnik, J Phil 85:75–87, 1988 ), and (b) according to Quine (Philosophy of logic, Prentice-Hall: Englewood Cliffs, 1970 ), it is nothing more than “set theory in sheep’s clothing”. (4) It is also not better than its first-order counterpart, in the following sense: if first-order logic does not characterize adequately mathematical systems, given the existence of non - isomorphic first-order interpretations, second-order logic does not characterize them either, given the existence of different interpretations of second-order theories (Melia, Analysis 55:127–134, 1995 ). (5) Finally, as opposed to what is claimed by defenders of second-order logic [such as Shapiro (J Symbol Logic 50:714–742, 1985 )], this logic does not solve the problem of referential access to mathematical objects (Azzouni, Metaphysical myths, mathematical practice: the logic and epistemology of the exact sciences, Cambridge University Press, Cambridge, 1994 ). In this paper, I argue that the second-order theorist can solve each of these difficulties. As a result, second-order logic provides the benefits of a rich framework without the associated costs. (shrink)

In this paper, we are concerned with the development of a general set theory using the single axiom version of Leśniewski’s mereology. The specification of mereology, and further of Tarski’s geometry of solids will rely on the Calculus of Inductive Constructions (CIC). In the first part, we provide a specification of Leśniewski’s mereology as a model for an atomless Boolean algebra using Clay’s ideas. In the second part, we interpret Leśniewski’s mereology in monadic second-order logic using names (...) and develop a full version of mereology referred to as CIC-based Monadic Mereology (λ-MM) allowing an expressive theory while involving only two axioms. In the third part, we propose a modeling of Tarski’s solid geometry relying on λ-MM. It is intended to serve as a basis for spatial reasoning. All parts have been proved using a translation in type theory. (shrink)

Context: Philosophy of science is the branch of philosophy that deals with methods, foundations, and implications of science. It is a theory of how to create scientific knowledge. Presently, there is widespread agreement on how to do science, namely conjectures, ideally in the form of a mathematical model, and refutations, testing the model using empirical evidence. Problem: Many social scientists are using a conception of science created for the physical sciences. Expanding philosophy of science so that it more successfully encompasses (...) social systems would create new avenues of inquiry. Two dimensions could be added to philosophy of science: the amount of attention paid to the observer and the amount of impact of a theory on the system described. Method: My approach is to illuminate underlying assumptions. I claim that there are at least three epistemologies and that they can be combined to form a more robust conception of knowledge and of how to do research. There are at least four models and four basic elements being used by scientists. Results: The article identifies the logical propositions underlying second-order science. It suggests strategies for developing second-order science. And it describes several methods that can be used to practice second-order science, including how past theories have not only described but also changed the phenomenon being studied. Implications: The task for members of the scientific community, particularly social scientists, is to practice second-order science and to develop further its theories and methods. A practical implication is to accept methods for acting as well as theories as a contribution to science, since methods explicitly define the role of an observer/ participant. Constructivist content: The paper is an extension of the work of Heinz von Foerster and other second-order cyberneticians. (shrink)

Second-order quantifier elimination in the context of classical logic emerged as a powerful technique in many applications, including the correspondence theory, relational databases, deductive and knowledge databases, knowledge representation, commonsense reasoning and approximate reasoning. In the current paper we first generalize the result of Nonnengart and Szałas [17] by allowing second-order variables to appear within higher-order contexts. Then we focus on a semantical analysis of conditionals, using the introduced technique and Gabbay’s semantics provided in [10] (...) and substantially using a third-order accessibility relation. The analysis is done via finding correspondences between axioms involving conditionals and properties of the underlying third-order relation. (shrink)