A systematic introduction suitable for readers who have little familiarity with logic. Provides numerous examples and complete proofs.

In order to be able to express all possible patterns of dependence and independence between variables, we have to replace the traditional first-order logic by independence-friendly (IF) logic. Our natural concept of truth for a quantificational sentence S says that all the Skolem functions for S exist. This conception of truth for a sufficiently rich IF first-order language can be expressed in the same language. In a first-order axiomatic set theory, one can apparently express this (...) same concept in set-theoretical terms, since the existence of functions can be expressed there. Because of Tarski's theorem, this is impossible. Hence there must exist set-theoretical statements, even provable ones, which are said to be true in first-order models of axiomatic set theory but whose Skolem functions do not all exist. Hence there are provable sentences in axiomatic set theory that are false in accordance with our ordinary conceptions of set-theoretical truth. Such counter-intuitive propositions have been known to exist, but they have been blamed on the peculiarities of very large sets. It is argued here that this explanation is not correct and that there are intuitively false theorems not involving very large sets. Hence the provability or unprovability of a set-theoretical statement, e.g. of the continuum hypothesis (CH) in axiomatic set theory is not necessarily relevant to the truth of CH. (shrink)

We analyze the expressive resources of \ logic that do not stem from Henkin quantification. When one restricts attention to regular \ sentences, this amounts to the study of the fragment of \ logic which is individuated by the game-theoretical property of action recall. We prove that the fragment of prenex AR sentences can express all existential second-order properties. We then show that the same can be achieved in the non-prenex fragment of AR, by using “signalling by disjunction” (...) instead of Henkin or signalling patterns. We also study irregular IF logic and analyze its correspondence to regular IF logic. By using new methods, we prove that the game-theoretical property of knowledge memory is a first-order syntactical constraint also for irregular sentences, and we identify another new first-order fragment. Finally we discover that irregular prefixes behave quite differently in finite and infinite models. In particular, we show that, over infinite structures, every irregular prefix is equivalent to a regular one; and we present an irregular prefix which is second order on finite models but collapses to a first-order prefix on infinite models. (shrink)

Let us assume that you are entrusted by UNESCO with an important task. You are asked to devise a universal logical language, a Begriffsschrift in Frege's sense, which is to serve the purposes of science, business and everyday life. What requirements should such a “conceptual notation” satisfy? There are undoubtedly many relevant desiderata, but here I am focusing on one unmistakable one. In order to be a viable lingua universalis, your language must in any case be capable of representing any (...) possible configuration of dependence and independence between different variables. For if such a configuration is possible in principle, there is no guarantee that it might not one day show up among the natural, human or social phenomena we have to study.But how are dependencies and independencies between variables expressed in our familiar logical notation? Every logician worth his or her truth-table knows the answer. Dependencies between two variables are expressed by dependencies between the quantifiers to which they are bound. For instance, inthe variable y depends on x, while inz depends on x but not on y, while u depends on both x and y.But how is the dependence of a quantifier on another one expressed in familiar logical languages? Obviously by occurring in its scope, indicated by the pair of parentheses following it. But the nesting of scopes is a transitive and antisymmetrical relation which allows branching only in one direction. Hence other kinds of structures of dependence and independence between variables are not representable in the received logical notation. Such previously inexpressible structures form the subject matter of what has been referred to as independence-friendly logic. (shrink)

Dependence is a common phenomenon, wherever one looks: ecological systems, astronomy, human history, stock markets - but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first order logic. Here the syntax and semantics of dependence logic are studied, dependence (...) logic is given an alternative game theoretic semantics, and results about its complexity are proven. This is a graduate textbook suitable for a special course in logic in mathematics, philosophy and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers, with a basic knowledge of logic, interested in new phenomena in logic. (shrink)

Independence Friendly Logic, introduced by Hintikka, is a logic in which a quantifier can be marked for being independent of other quantifiers. Dependence logic, introduced by Väänänen, is a logic with the complementary approach: for a quantifier it can be indicated on which quantifiers it depends. These logics are claimed to be useful for many phenomena, for instance natural language semantics. In this contribution we will compare these two logics by investigating their application in (...) a compositional analysis of the de dicto - de re ambiguity in natural language. It will be argued that Independence Friendly logic is suitable, whereas Dependence Logic is not. (shrink)

Inspired by Hintikka’s ideas on constructivism, we are going to ‘effectivize’ the game-theoretic semantics for independence-friendly first-order logic, but in a somewhat different way than he did in the monograph ‘The Principles of Mathematics Revisited’. First we show that Nelson’s realizability interpretation—which extends the famous Kleene’s realizability interpretation by adding ‘strong negation’—restricted to the implication-free first-order formulas can be viewed as an effective version of GTS for FOL. Then we propose a realizability interpretation for IF-FOL, inspired by (...) the so-called ‘trump semantics’ which was discovered by Hodges, and show that this trump realizability interpretation can be viewed as an effective version of GTS for IF-FOL. Finally we prove that the trump realizability interpretation for IF-FOL appropriately generalises Nelson’s restricted realizability interpretation for the implication-free first-order formulas. (shrink)

A dichotomy result of Sevenster (2014) [29] completely classified the quantifier prefixes of regular Independence-Friendly (IF) logic according to the patterns of quantifier dependence they contain. On one hand, prefixes that contain “Henkin” or “signalling” patterns were shown to characterize fragments of IF logic that capture NP-complete problems; all the remaining prefixes were shown instead to be essentially first-order. In the present paper we develop the machinery which is needed in order to extend the results of (...) Sevenster to non-prenex, regular IF sentences. This involves shifting attention from quantifier prefixes to a (rather general) class of syntactical tree prefixes. We partially classify the fragments of regular IF logic that are thus determined by syntactical trees; in particular, a) we identify four classes of tree prefixes that are neither signaling nor Henkin, and yet express NP-complete problems and other second-order concepts; and b) we give more general criteria for checking the first-orderness of an IF sentence. (shrink)

Independence‐Friendly logic introduced by Hintikka and Sandu studies patterns of dependence and independence of quantifiers which exceed those found in ordinary first‐order logic. The present survey focuses on the game‐theoretical interpretation of IF‐logic, including connections to solution concepts in classical game theory, but we shall also present its compositional interpretation together with its connections to notions of dependence and dependence between terms.

The working assumption of this paper is that noncommuting variables are irreducibly interdependent. The logic of such dependence relations is the author's independence-friendly (IF) logic, extended by adding to it sentence-initial contradictory negation ¬ over and above the dual (strong) negation ∼. Then in a Hilbert space ∼ turns out to express orthocomplementation. This can be extended to any logical space, which makes it possible to define the dimension of a logical space. The received Birkhoff and (...) von Neumann "quantum logic" can be interpreted by taking their "disjunction" to be ¬(∼A & ∼ B). Their logic can thus be mapped into a Boolean structure to which an additional operator ∼ has been added. (shrink)

In recent work, semantic games of independence-friendly logic were studied in strategic form in terms of Nash equilibria. The class of strategic games of independence-friendly logic is contained in the class of win-loss, zero-sum two-player games. In this note we draw on the theory of linear programming to develop tools to analyze the value of such games. We give two applications of these tools to independence-friendly logic under the so-called equilibrium semantics.

1. Two kinds of logic. To a first approximation there are two main kinds of pursuit in logic. The first is the traditional one going back two millennia, concerned with characterizing the logically valid inferences. The second is the one that emerged most systematically only in the twentieth century, concerned with the semantics of logical operations. In the view of modern, model-theoretical eyes, the first requires the second, but not vice-versa. According to Tarski’s generally accepted account of logical (...) consequence, inference from some statements as hypotheses to a statement as conclusion is logically valid if the truth of the hypotheses ensures the truth of the conclusion, in a way that depends only on the form of the statements involved, not on their content. Interpreted model-theoretically this means that every model of the hypotheses is a model of the conclusion. However, there is an ambiguity in Tarski’s explication, as he himself emphasized, since for the specification of form one needs to determine what are the logical notions. Once those are isolated and their semantical roles are settled, one can see how the truth of a statement is composed from the truth of its basic parts, in whatever way those are specified. The problem of what are the logical notions is an unsettled and controversial one. In the classical truthfunctional perspective, proposals range from those of first-order logic to generalized quantifiers to second and higher-order quantifiers to infinitary languages and beyond. Many of these stronger semantical notions have been treated in the volume Model Theoretic Logics. In a series of singular, thought-provoking publications in recent years, Jaakko Hintikka has vigorously promoted consideration of an extension of first-order logic called IF logic, along with claims that its adoption promises to have revolutionary consequences. (shrink)

Nous introduisons une extension aux points fixes de la logique IF (faite pour l’indépendance) de Hintikka et Sandu. Nous donnons des résultats sur sa complexité et son pouvoir expressif. Nous la relions aux jeux de parité à information imparfaite, et nous montrons une application à la définition d’un mu-calcul modal fait pour l’indépendance.

Nous introduisons une extension aux points fixes de la logique IF (faite pour l’indépendance) de Hintikka et Sandu. Nous donnons des résultats sur sa complexité et son pouvoir expressif. Nous la relions aux jeux de parité à information imparfaite, et nous montrons une application à la définition d’un mu-calcul modal fait pour l’indépendance.

In this paper we consider an independence-friendly modal logic, IFML. It follows from results in the literature that qua expressive power, IFML is a fragment of second-order existential logic, , that cannot be translated into first-order logic. It is also known that IFML lacks the tree structure property. We show that IFML has the , a weaker version of the tree structure property, and that its satisfiability problem is solvable in 2NEXP. This implies that this (...) paper reveals a new decidable fragment of . We also show that IFML becomes undecidable if we add the identity symbol to its vocabulary by means of a reduction from the tiling problem. (shrink)

IFG logic is a variant of the independence-friendly logic of Hintikka and Sandu. We answer the question: “Which IFG-formulas are equivalent to ordinary first-order formulas?” We use the answer to prove the ordinary cylindric set algebra over a structure can be embedded into a reduct of the IFG-cylindric set algebra over the structure.

We study the expressive power of independence-friendly quantifier prefixes composed of universal$\left$, existential$\left$, and majority quantifiers$\left$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of$\forall x$,$\exists x$, and Mx. (...) In unison, our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard. (shrink)

In the literature on logics of imperfect information it is often stated, incorrectly, that the Game-Theoretical Semantics of Independence-Friendly quantifiers captures the idea that the players of semantical games are forced to make some moves without knowledge of the moves of other players. We survey here the alternative semantics for IF logic that have been suggested in order to enforce this “epistemic reading” of sentences. We introduce some new proposals, and a more general logical language which distinguishes (...) between “independence from actions” and “independence from strategies”. New semantics for IF logic can be obtained by choosing embeddings of the set of IF sentences into this larger language. We compare all the semantics proposed and their purported game-theoretical justifications, and disprove a few claims that have been made in the literature. (shrink)

What is mathematics about? Does the subject-matter of mathematics exist independently of the mind or are they mental constructions? How do we know mathematics? Is mathematical knowledge logical knowledge? And how is mathematics applied to the material world? In this introduction to the philosophy of mathematics, Michele Friend examines these and other ontological and epistemological problems raised by the content and practice of mathematics. Aimed at a readership with limited proficiency in mathematics but with some experience of formal logic (...) it seeks to strike a balance between conceptual accessibility and correct representation of the issues. Friend examines the standard theories of mathematics - Platonism, realism, logicism, formalism, constructivism and structuralism - as well as some less standard theories such as psychologism, fictionalism and Meinongian philosophy of mathematics. In each case Friend explains what characterises the position and where the divisions between them lie, including some of the arguments in favour and against each. This book also explores particular questions that occupy present-day philosophers and mathematicians such as the problem of infinity, mathematical intuition and the relationship, if any, between the philosophy of mathematics and the practice of mathematics. Taking in the canonical ideas of Aristotle, Kant, Frege and Whitehead and Russell as well as the challenging and innovative work of recent philosophers like Benacerraf, Hellman, Maddy and Shapiro, Friend provides a balanced and accessible introduction suitable for upper-level undergraduate courses and the non-specialist. (shrink)

In this paper it is argued that Hintikka's game theoreticalsemantics for Independence Friendly logic does not formalize theintuitions about independent choices; it rather is aformalization of imperfect information. Furthermore it is shownthat the logic has several remarkable properties (e.g.,renaming of bound variables is not allowed). An alternativesemantics is proposed which formalizes intuitions aboutindependence.

We study the expressive power of open formulas of dependence logic introduced in Väänänen [Dependence logic (Vol. 70 of London Mathematical Society Student Texts), 2007]. In particular, we answer a question raised by Wilfrid Hodges: how to characterize the sets of teams definable by means of identity only in dependence logic, or equivalently in independence friendly logic.

The initial goal of the present paper is to reveal a mistake committed by Hintikka in a recent paper on the foundations of mathematics. His claim that independence-friendly logic is the real logic of mathematics is supported in that article by an argument relying on uniformity concepts taken from real analysis. I show that the central point of his argument is a simple logical mistake. Second and more generally, I conclude, based on the previous remarks and (...) on another standard fact of IFL, that first-order logic can adequately express uniformity concepts in real analysis, whereas IFL cannot. This not only radically contradicts Hintikka’s particular claim in that article, but also undermines his whole enterprise of founding mathematics on his logic system. (shrink)

Logic and humour tend to be mutually exclusive topics. Humour plays off ambiguity, while classical logic falters over it. Formalizing puns is therefore impossible, since puns have ambiguous meanings for their components. However, I will use Independence-Friendly logic to formally encode the multiple meanings within a pun. This will show a general strategy of how to logically represent ambiguity and reveals humour as an untapped source of novel logical structure.

In this article we investigate the family of independence-friendly (IF) logics in the equality-free setting, concentrating on questions related to expressive power. Various natural equality-free fragments of logics in this family translate into existential second-order logic with prenex quantification of function symbols only and with the first-order parts of formulae equality-free. We study this fragment of existential second-order logic. Our principal technical result is that over finite models with a vocabulary consisting of unary relation symbols only, (...) this fragment of second-order logic is weaker in expressive power than first-order logic (with equality). Results about the fragment could turn out useful for example in the study of independence-friendly modal logics. In addition to proving results of a technical nature, we address issues related to a perspective from which IF logic is regarded as a specification framework for games, and also discuss the general significance of understanding fragments of second-order logic in investigations related to non-classical logics. (shrink)

It has been argued that a combination of game-theoretic semantics and independence-friendly (IF) languages can provide a novel approach to the conceptual foundations of mathematics and the sciences. I introduce and motivate an IF first-order modal language endowed with a game-theoretic semantics of perfect information. The resulting interpretive independence-friendly logic (IIF) allows to formulate some basic model-theoretic notions that are inexpressible in the ordinary quantified modal logic. Moreover, I argue that some key concepts of (...) Kripke’s new theory of reference are adequately modeled within IIF. Finally, I compare the logic IIF to David Lewis' counterpart theory, drawing some morals concerning the interrelation between metaphysical and semantic issues in possible-world semantics. (shrink)

The hybrid logic and the independence friendly modal logic IFML are compared for their expressive powers. We introduce a logic IFML c having a non-standard syntax and a compositional semantics; in terms of this logic a syntactic fragment of IFML is singled out, denoted IFML c . (In the Appendix it is shown that the game-theoretic semantics of IFML c coincides with the compositional semantics of IFML c .) The hybrid logic is proven (...) to be strictly more expressive than IFML c . By contrast, and the full IFML are shown to be incomparable for their expressive powers. Building on earlier research (Tulenheimo and Sevenster 2006), a PSPACE -decidable fragment of the undecidable logic is disclosed. This fragment is not translatable into the hybrid logic and has not been studied previously in connection with hybrid logics. In the Appendix IFML c is shown to lack the property of ‘quasi-positionality’ but proven to enjoy the weaker property of ‘ bounded quasi-positionality’. The latter fact provides from the IFML internal perspective an account of what makes the compositional semantics of IFML c possible. (shrink)

Hintikka and Sandu’s independence-friendly logic is a conservative extension of first-order logic that allows one to consider semantic games with imperfect information. In the present article, we first show how several variants of the Monty Hall problem can be modeled as semantic games for IF sentences. In the process, we extend IF logic to include semantic games with chance moves and dub this extension stochastic IF logic. Finally, we use stochastic IF logic to (...) analyze the Sleeping Beauty problem, leading to the conclusion that the thirders are correct while identifying the main error in the halfers’ argument. (shrink)

We analyze the behaviour of declarations of independence between existential quantifiers in quantifier prefixes of Independence-Friendly (IF) sentences; we give a syntactical criterion to decide whether a sentence beginning with such prefix exists, such that its truth values may be affected by removal of the declaration of independence. We extend the result also to equilibrium semantics values for undetermined IF sentences.

As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players – they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the informational dependencies between variables in a game. More precisely, dependency graphs play two roles. First, when we say that variable x depends on variable y, then (...) we mean that when a strategy assigns a value to variable x, it can be informed by the value that has been assigned to y. Second, and as a consequence of the first property, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs implicitly define a partial ordering of the run-time events in a game: if x is dependent on y, then the assignment of a value to y must precede the assignment of a value to x; if x and y are independent, however, then we can say nothing about the ordering of assignments to these variables—the assignments may occur concurrently. We refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly logic. (shrink)

The main tool of the arithmetization and logization of analysis in the history of nineteenth century mathematics was an informal logic of quantifiers in the guise of the “epsilon–delta” technique. Mathematicians slowly worked out the problems encountered in using it, but logicians from Frege on did not understand it let alone formalize it, and instead used an unnecessarily poor logic of quantifiers, viz. the traditional, first-order logic. This logic does not e.g. allow the definition and study (...) of mathematicians’ uniformity concepts important in analysis. Mathematicians’ stronger logic was rediscovered around 1990 as the form of independence-friendly logic which hence is not a new logic nor a further development of ordinary first-order logic but a richer version of it. (shrink)

The theory of existential graphs, which Peirce ultimately divided into four quadrants , is a rich method of analysis in the philosophy of logic. Its $$\upbeta $$ β -part boasts a diagrammatic theory of quantification, which by 1902 Peirce had used in the logical analysis of natural-language expressions such as complex donkey-type anaphora, quantificational patterns describing new mathematical concepts, and cognitive information processing. In the $$\upbeta $$ β -quadrant, he came close to inventing independence-friendly logic, the (...) idea of which he found indispensable in fulfilling the tasks –. (shrink)

The semantics of the independence friendly logic of Hintikka and Sandu is usually defined via a game of imperfect information. We give a definition in terms of a game of perfect information. We also give an Ehrenfeucht-Fraïssé game adequate for this logic and use it to define a Distributive Normal Form for independence friendly logic.

Let us assume that you are entrusted by UNESCO with an important task. You are asked to devise a universal logical language, a Begriffsschrift in Frege's sense, which is to serve the purposes of science, business and everyday life. What requirements should such a “conceptual notation” satisfy? There are undoubtedly many relevant desiderata, but here I am focusing on one unmistakable one. In order to be a viable lingua universalis, your language must in any case be capable of representing any (...) possible configuration of dependence and independence between different variables. For if such a configuration is possible in principle, there is no guarantee that it might not one day show up among the natural, human or social phenomena we have to study.But how are dependencies and independencies between variables expressed in our familiar logical notation? Every logician worth his or her truth-table knows the answer. Dependencies between two variables are expressed by dependencies between the quantifiers to which they are bound. For instance, inthe variable y depends on x, while inz depends on x but not on y, while u depends on both x and y.But how is the dependence of a quantifier on another one expressed in familiar logical languages? Obviously by occurring in its scope, indicated by the pair of parentheses following it. But the nesting of scopes is a transitive and antisymmetrical relation which allows branching only in one direction. Hence other kinds of structures of dependence and independence between variables are not representable in the received logical notation. Such previously inexpressible structures form the subject matter of what has been referred to as independence-friendly logic. (shrink)

The paper proposes a novel solution to the problem of scope posed by natural language indefinites that captures both the difference in scopal freedom between indefinites and bona fide quantifiers and the syntactic sensitivity that the scope of indefinites does nevertheless exhibit. Following the main insight of choice functional approaches, we connect the special scopal properties of indefinites to the fact that their semantics can be stated in terms of choosing a suitable witness. This is in contrast to bona fide (...) quantifiers, the semantics of which crucially involves relations between sets of entities. We provide empirical arguments that this insight should not be captured by adding choice/Skolem functions to classical first-order logic, but in a semantics that follows Independence-Friendly Logic, in which scopal relations involving existentials are part of the recursive definition of truth and satisfaction. These scopal relations are resolved automatically as part of the interpretation of existentials. Additional support for this approach is provided by dependent indefinites, a cross-linguistically common class of special indefinites that can be straightforwardly analyzed in our semantic framework. (shrink)

Typical applications of Hintikka’s game-theoretical semantics give rise to semantic attributes—truth, falsity—expressible in the $\Sigma^{1}_{1}$-fragment of second-order logic. Actually a much more general notion of semantic attribute is motivated by strategic considerations. When identifying such a generalization, the notion of classical negation plays a crucial role. We study two languages, $L_{1}$ and $L_{2}$, in both of which two negation signs are available: $\rightharpoondown $ and $\sim$. The latter is the usual GTS negation which transposes the players’ roles, while the (...) former will be interpreted via the notion of mode. Logic $L_{1}$ extends independence-friendly logic; $\rightharpoondown $ behaves as classical negation in $L_{1}$. Logic $L_{2}$ extends $L_{1}$, and it is shown to capture the $\Sigma^{2}_{1}$-fragment of third-order logic. Consequently the classical negation remains inexpressible in $L_{2}$. (shrink)

It is argued that the goal of Hilbert's program was to prove the model-theoretical consistency of different axiom systems. This Hilbert proposed to do by proving the deductive consistency of the relevant systems. In the extended independence-friendly logic there is a complete proof method for the contradictory negations of independence-friendly sentences, so the existence of a single proposition that is not disprovable from arithmetic axioms can be shown formally in the extended independence-friendly (...) class='Hi'>logic. It can also be proved by means of independence-friendly logic that proof-theoretical consistency of a sentence S implies the existence of a model in which S is not false. Hence the consistency of the axioms of arithmetic in the sense of being not-false in a model can be proved. (shrink)

We introduce generalized quantifiers, as defined in Tarskian semantics by Mostowski and Lindström, in logics whose semantics is based on teams instead of assignments, e.g., IF-logic and Dependence logic. Both the monotone and the non-monotone case is considered. It is argued that to handle quantifier scope dependencies of generalized quantifiers in a satisfying way the dependence atom in Dependence logic is not well suited and that the multivalued dependence atom is a better choice. This atom is in (...) fact definably equivalent to the independence atom recently introduced by Väänänen and Grädel. (shrink)

This dissertation examines several of the problems that Hilbert discovered in the foundations of mathematics, from a metalogical perspective. The problems manifest themselves in four different aspects of Hilbert’s views: (i) Hilbert’s axiomatic approach to the foundations of mathematics; (ii) His response to criticisms of set theory; (iii) His response to intuitionist criticisms of classical mathematics; (iv) Hilbert’s contribution to the specification of the role of logical inference in mathematical reasoning. This dissertation argues that Hilbert’s axiomatic approach was guided primarily (...) by model theoretical concerns. Accordingly, the ultimate aim of his consistency program was to prove the model-theoretical consistency of mathematical theories. It turns out that for the purpose of carrying out such consistency proofs, a suitable modification of the ordinary first-order logic is needed. To effect this modification, independence-friendly logic is needed as the appropriate conceptual framework. It is then shown how the model theoretical consistency of arithmetic can be proved by using IF logic as its basic logic. Hilbert’s other problems, manifesting themselves as aspects (ii), (iii), and (iv)—most notably the problem of the status of the axiom of choice, the problem of the role of the law of excluded middle, and the problem of giving an elementary account of quantification—can likewise be approached by using the resources of IF logic. It is shown that by means of IF logic one can carry out Hilbertian solutions to all these problems. The two major results concerning aspects (ii), (iii) and (iv) are the following: (a) The axiom of choice is a logical principle; (b) The law of excluded middle divides metamathematical methods into elementary and non-elementary ones. It is argued that these results show that IF logic helps to vindicate Hilbert’s nominalist philosophy of mathematics. On the basis of an elementary approach to logic, which enriches the expressive resources of ordinary first-order logic, this dissertation shows how the different problems that Hilbert discovered in the foundations of mathematics can be solved. (shrink)

In the present paper we confront Martin- Löf’s analysis of the axiom of choice with J. Hintikka’s standing on this axiom. Hintikka claims that his game theoretical semantics for Independence Friendly Logic justifies Zermelo’s axiom of choice in a first-order way perfectly acceptable for the constructivists. In fact, Martin- Löf’s results lead to the following considerations:Hintikka preferred version of the axiom of choice is indeed acceptable for the constructivists and its meaning does not involve higher order (...) class='Hi'>logic.However, the version acceptable for constructivists is based on an intensional take on functions. Extensionality is the heart of the classical understanding of Zermelo’s axiom and this is the real reason behind the constructivist rejection of it.More generally, dependence and independence features that motivate IF-Logic, can be formulated within the frame of constructive type theory without paying the price of a system that is neither axiomatizable nor has an underlying theory of inference – logic is about inference after all.We conclude pointing out that recent developments in dialogical logic show that the CTT approach to meaning in general and to the axiom of choice in particular is very natural to game theoretical approaches where metalogical features are explicitly displayed at the object language-level. Thus, in some way, this vindicates, albeit in quite of a different manner, Hintikka’s plea for the fruitfulness of game-theoretical semantics in the context of the foundations of mathematics. (shrink)

In the present paper we confront Martin- Löf’s analysis of the axiom of choice with J. Hintikka’s standing on this axiom. Hintikka claims that his game theoretical semantics for Independence Friendly Logic justifies Zermelo’s axiom of choice in a first-order way perfectly acceptable for the constructivists. In fact, Martin- Löf’s results lead to the following considerations:Hintikka preferred version of the axiom of choice is indeed acceptable for the constructivists and its meaning does not involve higher order (...) class='Hi'>logic.However, the version acceptable for constructivists is based on an intensional take on functions. Extensionality is the heart of the classical understanding of Zermelo’s axiom and this is the real reason behind the constructivist rejection of it.More generally, dependence and independence features that motivate IF-Logic, can be formulated within the frame of constructive type theory without paying the price of a system that is neither axiomatizable nor has an underlying theory of inference – logic is about inference after all.We conclude pointing out that recent developments in dialogical logic show that the CTT approach to meaning in general and to the axiom of choice in particular is very natural to game theoretical approaches where metalogical features are explicitly displayed at the object language-level. Thus, in some way, this vindicates, albeit in quite of a different manner, Hintikka’s plea for the fruitfulness of game-theoretical semantics in the context of the foundations of mathematics. (shrink)

Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional (...) logics and study its properties, by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline. (shrink)

We take a fresh look at the logics of informational dependence and independence of Hintikka and Sandu and Väänänen, and their compositional semantics due to Hodges. We show how Hodges’ semantics can be seen as a special case of a general construction, which provides a context for a useful completeness theorem with respect to a wider class of models. We shed some new light on each aspect of the logic. We show that the natural propositional logic carried (...) by the semantics is the logic of Bunched Implications due to Pym and O’Hearn, which combines intuitionistic and multiplicative connectives. This introduces several new connectives not previously considered in logics of informational dependence, but which we show play a very natural rôle, most notably intuitionistic implication. As regards the quantifiers, we show that their interpretation in the Hodges semantics is forced, in that they are the image under the general construction of the usual Tarski semantics; this implies that they are adjoints to substitution, and hence uniquely determined. As for the dependence predicate, we show that this is definable from a simpler predicate, of constancy or dependence on nothing. This makes essential use of the intuitionistic implication. The Armstrong axioms for functional dependence are then recovered as a standard set of axioms for intuitionistic implication. We also prove a full abstraction result in the style of Hodges, in which the intuitionistic implication plays a very natural rôle. (shrink)