On the Consistency of the Δ1 1-CA Fragment of Frege's Grundgesetze

It is well known that Frege's system in the Grundgesetze der Arithmetik is formally inconsistent. Frege's instantiation rule for the second-order universal quantifier makes his system, except for minor differences, full (i.e., with unrestricted comprehension) second-order logic, augmented by an abstraction operator that abides to Frege's basic law V. A few years ago, Richard Heck proved the consistency of the fragment of Frege's theory obtained by restricting the comprehension schema to predicative formulae. He further conjectured that the more encompassing ¹ ₁-comprehension schema would already be inconsistent. In the present paper, we show that this is not the case.     

Logic Without Contraction as Based on Inclusion and Unrestricted Abstraction

On the one hand, the absence of contraction is a safeguard against the logical (property theoretic) paradoxes; but on the other hand, it also disables inductive and recursive definitions, in its most basic form the definition of the series of natural numbers, for instance. The reason for this is simply that the effectiveness of a recursion clause depends on its being available after application, something that is usually assured by contraction. This paper presents a way of overcoming this problem within the framework of a logic based on inclusion and unrestricted abstraction, without any form of extensionality. This revised version was published online in June 2006 with corrections to the Cover Date.     

Erkenntnistheorie der Zahldefinition und philosophische Grundlegung der Arithmetik unter Bezugnahme auf einen Vergleich von Gottlob Freges Logizismus und platonischer Philosophie (Syrian, Theon von Smyrna u.a.)

The epistomology of the definition of number and the philosophical foundation of arithmetic based on a comparison between Gottlob Frege's logicism and Platonic philosophy (Syrianus, Theo Smyrnaeus, and others). The intention of this article is to provide arithmetic with a logically and methodologically valid definition of number for construing a consistent philosophical foundation of arithmetic. The – surely astonishing – main thesis is that instead of the modern and contemporary attempts, especially in Gottlob Frege's Foundations of Arithmetic, such a definition is found in the arithmetic in Euclid's Elements. To draw this conclusion a profound reflection on the role of epistemology for the foundation of mathematics, especially for the method of definition of number, is indispensable; a reflection not to be found in the contemporary debate (the predominate ‘pragmaticformalism’ in current mathematics just shirks from trying to solve the epistemological problems raised by the debate between logicism, intuitionism, and formalism). Frege's definition of number, ‘The number of the concept F is the extension of the concept ‘numerically equal to the concept F”, which is still substantial for contemporary mathematics, does not fulfil the requirements of logical and methodological correctness because the definiens in a double way (in the concepts ‘extension of a concept’ and ‘numerically equal’) implicitly presupposes the definiendum, i.e. number itself. Number itself, on the contrary, is defined adequately by Euclid as ‘multitude composed of units’, a definition which is even, though never mentioned, an implicit presupposition of the modern concept ofset. But Frege rejects this definition and construes his own - for epistemological reasons: Frege's definition exactly fits the needs of modern epistemology, namely that for to know something like the number of a concept one must become conscious of a multitude of acts of producing units of ‘given’ representations under the condition of a 1:1 relationship to obtain between the acts of counting and the counted ‘objects’. According to this view, which has existed at least since the Renaissance stoicism and is maintained not only by Frege but also by Descartes, Kant, Husserl, Dummett, and others, there is no such thing as a number of pure units itself because the intellect or pure reason, by itself empty, must become conscious of different units of representation in order to know a multitude, a condition not fulfilled by Euclid's conception. As this is Frege's main reason to reject Euclid's definition of number (others are discussed in detail), the paper shows that the epistemological reflection in Neoplatonic mathematical philosophy, which agrees with Euclid's definition of number, provides a consistent basement for it. Therefore it is not progress in the history of science which hasled to the a poretic contemporary state of affairs but an arbitrary change of epistemology in early modern times, which is of great influence even today. This revised version was published online in August 2006 with corrections to the Cover Date.     

Frege,Boolos, and Logical Objects

In this paper, the authors discuss Frege's theory of logical objects (extensions, numbers, truth-values) and the recent attempts to rehabilitate it. We show that the eta relation George Boolos deployed on Frege's behalf is similar, if not identical, to the encoding mode of predication that underlies the theory of abstract objects. Whereas Boolos accepted unrestricted Comprehension for Properties and used the eta relation to assert the existence of logical objects under certain highly restricted conditions, the theory of abstract objects uses unrestricted Comprehension for Logical Objects and banishes encoding (eta) formulas from Comprehension for Properties. The relative mathematical and philosophical strengths of the two theories are discussed. Along the way, new results in the theory of abstract objects are described, involving: (a) the theory of extensions, (b) the theory of directions and shapes, and (c) the theory of truth values.     

Frege and the rigorization of analysis

This paper has three goals: (i) to show that the foundational program begun in theBegriffsschrift, and carried forward in theGrundlagen, represented Frege's attempt to establish the autonomy of arithmetic from geometry and kinematics; the cogency and coherence ofintuitive reasoning were not in question. (ii) To place Frege's logicism in the context of the nineteenth century tradition in mathematical analysis, and, in particular, to show how the modern concept of a function made it possible for Frege to pursue the goal of autonomy within the framework of the system of second-order logic of theBegriffsschrift. (iii) To address certain criticisms of Frege by Parsons and Boolos, and thereby to clarify what was and was not achieved by the development, in Part III of theBegriffsschrift, of a fragment of the theory of relations.     

Non-monotonicity and Informal Reasoning: Comment on Ferguson (2003)

In this paper, it is argued that Ferguson’s (2003, Argumentation 17, 335–346) recent proposal to reconcile monotonic logic with defeasibility has three counterintuitive consequences. First, the conclusions that can be derived from his new rule of inference are vacuous, a point that as already made against default logics when there are conflicting defaults. Second, his proposal requires a procedural “hack” to the break the symmetry between the disjuncts of the tautological conclusions to which his proposal leads. Third, Ferguson’s proposal amounts to arguing that all everyday inferences are sound by definition. It is concluded that the informal logic response to defeasibility, that an account of the context in which inferences are sound or unsound is required, still stands. It is also observed that another possible response is given by Bayesian probability theory (Oaksford and Chater, in press, Bayesian Rationality: The Probabilistic Approach to Human Reasoning, Oxford University Press, Oxford, UK; Hahn and Oaksford, in press, Synthese).     

Squares in Fork Arrow Logic

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are axiomatized by adding three equations to RAs equational axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is U×U for some set U) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares.     

Many Concepts and Two Logics of Algorithmic Reduction

Within the program of finding axiomatizations for various parts of computability logic, it was proven earlier that the logic of interactive Turing reduction is exactly the implicative fragment of Heyting’s intuitionistic calculus. That sort of reduction permits unlimited reusage of the computational resource represented by the antecedent. An at least equally basic and natural sort of algorithmic reduction, however, is the one that does not allow such reusage. The present article shows that turning the logic of the first sort of reduction into the logic of the second sort of reduction takes nothing more than just deleting the contraction rule from its Gentzen-style axiomatization. The first (Turing) sort of interactive reduction is also shown to come in three natural versions. While those three versions are very different from each other, their logical behaviors (in isolation) turn out to be indistinguishable, with that common behavior being precisely captured by implicative intuitionistic logic. Among the other contributions of the present article is an informal introduction of a series of new — finite and bounded — versions of recurrence operations and the associated reduction operations. Presented by Robert Goldblatt     

Fregean Abstraction, Referential Indeterminacy and the Logical Foundations of Arithmetic

In Die Grundlagen der Arithmetik, Frege attempted to introduce cardinalnumbers as logical objects by means of a second-order abstraction principlewhich is now widely known as ``Hume's Principle' (HP): The number of Fsis identical with the number of Gs if and only if F and G are equinumerous.The attempt miscarried, because in its role as a contextual definition HP fails tofix uniquely the reference of the cardinality operator ``the number of Fs'. Thisproblem of referential indeterminacy is usually called ``the Julius Caesar problem'.In this paper, Frege's treatment of the problem in Grundlagen is critically assessed. In particular, I try to shed new light on it by paying special attention to the framework of his logicism in which it appears embedded. I argue, among other things, that the Caesar problem, which is supposed to stem from Frege's tentative inductive definition of the natural numbers, is only spurious, not genuine; that the genuine Caesar problem deriving from HP is a purely semantic one and that the prospects of removing it by explicitly defining cardinal numbers as objects which are not classes are presumably poor for Frege. I conclude by rejecting two closely connected theses concerning Caesar put forward by Richard Heck: (i) that Frege could not abandon Axiom V because he could not solve the Julius Caesar problem without it; (ii) that (by his own lights) his logicist programme in Grundgesetze der Arithmetik failed because he could not overcome that problem.     

Non-Adjunctive Inference and Classical Modalities

The article focuses on representing different forms of non-adjunctive inference as sub-Kripkean systems of classical modal logic, where the inference from □A and □B to □A∧B fails. In particular we prove a completeness result showing that the modal system that Schotch and Jennings derive from a form of non-adjunctive inference in (Schotch and Jennings, 1980) is a classical system strictly stronger than EMN and weaker than K (following the notation for classical modalities presented in Chellas, 1980). The unified semantical characterization in terms of neighborhoods permits comparisons between different forms of non-adjunctive inference. For example, we show that the non-adjunctive logic proposed in (Schotch and Jennings, 1980) is not adequate in general for representing the logic of high probability operators. An alternative interpretation of the forcing relation of Schotch and Jennings is derived from the proposed unified semantics and utilized in order to propose a more fine-grained measure of epistemic coherence than the one presented in (Schotch and Jennings, 1980). Finally we propose a syntactic translation of the purely implicative part of Jaśkowski's system D₂ into a classical system preserving all the theorems (and non-theorems) explicilty mentioned in (Jaśkowski, 1969). The translation method can be used in order to develop epistemic semantics for a larger class of non-adjunctive (discursive) logics than the ones historically investigated by Jaśkowski.     

Algebraic Semantics for Deductive Systems

The notion of an algebraic semantics of a deductive system was proposed in [3], and a preliminary study was begun. The focus of [3] was the definition and investigation of algebraizable deductive systems, i.e., the deductive systems that possess an equivalent algebraic semantics. The present paper explores the more general property of possessing an algebraic semantics. While a deductive system can have at most one equivalent algebraic semantics, it may have numerous different algebraic semantics. All of these give rise to an algebraic completeness theorem for the deductive system, but their algebraic properties, unlike those of equivalent algebraic semantics, need not reflect the metalogical properties of the deductive system. Many deductive systems that don't have an equivalent algebraic semantics do possess an algebraic semantics; examples of these phenomena are provided. It is shown that all extensions of a deductive system that possesses an algebraic semantics themselves possess an algebraic semantics. Necessary conditions for the existence of an algebraic semantics are given, and an example of a protoalgebraic deductive system that does not have an algebraic semantics is provided. The mono-unary deductive systems possessing an algebraic semantics are characterized. Finally, weak conditions on a deductive system are formulated that guarantee the existence of an algebraic semantics. These conditions are used to show that various classes of non-algebraizable deductive systems of modal logic, relevance logic and linear logic do possess an algebraic semantics.     

A linear conservative extension of Zermelo-Fraenkel set theory

In this paper, we develop the system LZF of set theory with the unrestricted comprehension in full linear logic and show that LZF is a conservative extension of ZF^– i.e., the Zermelo-Fraenkel set theory without the axiom of regularity. We formulate LZF as a sequent calculus with abstraction terms and prove the partial cut-elimination theorem for it. The cut-elimination result ensures the subterm property for those formulas which contain only terms corresponding to sets in ZF^–. This implies that LZF is a conservative extension of ZF^– and therefore the former is consistent relative to the latter. Hiroakira Ono     

AN INTUITIONISTIC CHARACTERIZATION OF CLASSICAL LOGIC

By introducing the intensional mappings and their properties, we establish a new semantical approach of characterizing intermediate logics. First prove that this new approach provides a general method of characterizing and comparing logics without changing the semantical interpretation of implication connective. Then show that it is adequate to characterize all Kripke_complete intermediate logics by showing that each of these logics is sound and complete with respect to its (unique) ‘weakest characterization property’ of intensional mappings. In particular, we show that classical logic has the weakest characterization property , which is the strongest among all possible weakest characterization properties of intermediate logics. Finally, it follows from this result that a translation is an embedding of classical logic into intuitionistic logic, iff. its semantical counterpart has the property .      

What Harmony Could and Could Not Be

The notion of harmony has played a pivotal role in a number of debates in the philosophy of logic. Yet there is little agreement as to how the requirement of harmony should be spelled out in detail or even what purpose it is to serve. Most, if not all, conceptions of harmony can already be found in Michael Dummett's seminal discussion of the matter in The Logical Basis of Metaphysics. Hence, if we wish to gain a better understanding of the notion of harmony, we do well to start here. Unfortunately, however, Dummett's discussion is not always easy to follow. The following is an attempt to disentangle the main strands of Dummett's treatment of harmony. The different variants of harmony as well as their interrelations are clarified and their individual shortcomings qua interpretations of harmony are demonstrated. Though no attempt is made to give a detailed alternative account of harmony here, it is hoped that our discussion will lay the ground for an adequate rigorous treatment of this central notion.     

The Undecidability of Iterated Modal Relativization

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 ¹₁–complete. Two of these fragments do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 ⁰₁–complete. These results go via reduction to problems concerning domino systems.     

Note on the Scope of Truth-functional Logic

A plausible and popular rule governing the scope of truth-functional logic is shown to be indequate. The argument appeals to the existence of truth-functional paraphrases which are logically independent of their natural language counterparts. A more adequate rule is proposed.     

Pure Extensions, Proof Rules, and Hybrid Axiomatics

In this paper we argue that hybrid logic is the deductive setting most natural for Kripke semantics. We do so by investigating hybrid axiomatics for a variety of systems, ranging from the basic hybrid language (a decidable system with the same complexity as orthodox propositional modal logic) to the strong Priorean language (which offers full first-order expressivity).We show that hybrid logic offers a genuinely first-order perspective on Kripke semantics: it is possible to define base logics which extend automatically to a wide variety of frame classes and to prove completeness using the Henkin method. In the weaker languages, this requires the use of non-orthodox rules. We discuss these rules in detail and prove non-eliminability and eliminability results. We also show how another type of rule, which reflects the structure of the strong Priorean language, can be employed to give an even wider coverage of frame classes. We show that this deductive apparatus gets progressively simpler as we work our way up the expressivity hierarchy, and conclude the paper by showing that the approach transfers to first-order hybrid logic.A preliminary version of this paper was presented at the fifth conference on Advances in Modal Logic (AiML 2004) in Manchester. We would like to thank Maarten Marx for his comments on an early draft and Agnieszka Kisielewska for help with the proof reading.Special Issue Ways of Worlds II. On Possible Worlds and Related Notions Edited by Vincent F. Hendricks and Stig Andur Pedersen     

Modal Logic,Truth, and the Master Modality

In the paper (Braüner, 2001) we gave a minimal condition for the existence of a homophonic theory of truth for a modal or tense logic. In the present paper we generalise this result to arbitrary modal logics and we also show that a modal logic permits the existence of a homophonic theory of truth if and only if it permits the definition of a so-called master modality. Moreover, we explore a connection between the master modality and hybrid logic: We show that if attention is restricted to bidirectional frames, then the expressive power of the master modality is exactly what is needed to translate the bounded fragment of first-order logic into hybrid logic in a truth preserving way. We believe that this throws new light on Arthur Prior's fourth grade tense logic.     

Decidability of Quantified Propositional Intuitionistic Logic and S4 on Trees of Height and Arity ≤ω

Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers p, p, where the propositional variables range over upward-closed subsets of the set of worlds in a Kripke structure. If the permitted accessibility relations are arbitrary partial orders, the resulting logic is known to be recursively isomorphic to full second-order logic (Kremer, 1997). It is shown that if the Kripke structures are restricted to trees of at height and width at most , the resulting logics are decidable. This provides a partial answer to a question by Kremer. The result also transfers to modal S4 and some Gödel–Dummett logics with quantifiers over propositions.     

Extensions As Representative Objects In Frege's Logic

Matthias Schirn has argued on a number of occasions against the interpretation of Frege's ``objects of a quite special kind' (i.e., the objects referred to by names like `the concept F') as extensions of concepts. According to Schirn, not only are these objects not extensions, but also the idea that `the concept F' refers to objects leads to some conclusions that are counter-intuitive and incompatible with Frege's thought. In this paper, I challenge Schirn's conclusion: I want to try and argue that the assumption that `the concept F' refers to the extension of F is entirely consistent with Frege's broader views on logic and language. I shall examine each of Schirn's main arguments and show that they do not support his claim.