This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (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)

In this paper we consider truth as a vague predicate and inquire into the relation between truth and definite truth. We use some tools from modal logic to clarify this distinction, as done in McGee . Finally, we consider the question whether some of the results given by McGee can be transferred to the case in which the underlying logic is stronger than first-order logic. The result will be seen to be negative.

We establish a general hierarchy theorem for quantifier classes in the infinitary logic L∞ωωon finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure.This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. This proves a conjecture of (...) Immerman.We also separate the expressive power of several extensions of Datalog, giving new insight in the fine structure of stratified Datalog. (shrink)

Branching quantifiers were first introduced by L. Henkin in his 1959 paper ‘Some Remarks on Infmitely Long Formulas’. By ‘branching quantifiers’ Henkin meant a new, non-linearly structured quantiiier-prefix whose discovery was triggered by the problem of interpreting infinitistic formulas of a certain form} The branching (or partially-ordered) quantifier-prefix is, however, not essentially infinitistic, and the issues it raises have largely been discussed in the literature in the context of finitistic logic, as they will be here. Our discussion transcends, however, the (...) resources of standard lst-order languages and we will consider the new form in the context of 1st-order logic with 1- and 2-place ‘Mostowskian` generalized quantifiers.2.. (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)

This paper introduces a new Ehrenfeucht‐Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai‐Fagin game to the case when there are several alternating (coloring) moves played in different models. The game allows Duplicator to delay her choices of the models till (practically) the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in (...) Ehrenfeucht‐Fraïssé type games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F1n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H1n gives some new separation results on the class of finite models among various F1n on one hand and between F1n and H1n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game (in a sense) solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

The Bounds of Logic presents a new philosophical theory of the scope and nature of logic based on critical analysis of the principles underlying modern Tarskian logic and inspired by mathematical and linguistic development. Extracting central philosophical ideas from Tarski’s early work in semantics, Sher questions whether these are fully realized by the standard first-order system. The answer lays the foundation for a new, broader conception of logic. By generally characterizing logical terms, Sher establishes a fundamental result in semantics. Her (...) development of the notion of logicality for quantifiers and her work on branching are of great importance for linguistics. Sher outlines the boundaries of the new logic and points out some of the philosophical ramifications of the new view of logic for such issues as the logicist thesis, ontological commitment, the role of mathematics in logic, and the metaphysical underpinning of logic. She proposes a constructive definition of logical terms, reexamines and extends the notion of branching quantification, and discusses various linguistic issues and applications. (shrink)

This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating moves played in different models. The game allows Duplicator to delay her choices of the models till the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in Ehrenfeucht-Fraïssé type (...) games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F1n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H1n gives some new separation results on the class of finite models among various F1n on one hand and between F1n and H1n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round. (shrink)

Adding branching quantification to a first-order language increases the expressive power of the language,without adding to its ontology. The present paper is a defense of this claim against Quine (1970) and Patton (1991).

In this paper, we introduce a logic based on team semantics, called $\mathbf {FOT} $, whose expressive power is elementary, i.e., coincides with first-order logic both on the level of sentences and (possibly open) formulas, and we also show that a sublogic of $\mathbf {FOT} $, called $\mathbf {FOT}^{\downarrow } $, captures exactly downward closed elementary (or first-order) team properties. We axiomatize completely the logic $\mathbf {FOT} $, and also extend the known partial axiomatization of dependence logic to dependence logic (...) enriched with the logical constants in $\mathbf {FOT}^{\downarrow } $. (shrink)

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)

In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu [9] under the header of independence-friendly languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of the (...) game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics. (shrink)

This volume presents mathematical game theory as an interface between logic and philosophy.

In this paper I examine a cluster of concepts relevant to the methodology of truth theories: 'informative definition', 'recursive method', 'semantic structure', 'logical form', 'compositionality', etc. The interrelations between these concepts, I will try to show, are more intricate and multi-dimensional than commonly assumed.

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)

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)

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and the latter is (...) the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

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)

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)

We define a logic capable of expressing dependence of a variable on designated variables only. Thus has similar goals to the Henkin quantifiers of [4] and the independence friendly logic of [6] that it much resembles. The logic achieves these goals by realizing the desired dependence declarations of variables on the level of atomic formulas. By [3] and [17], ability to limit dependence relations between variables leads to existential second order expressive power. Our avoids some difficulties arising in the original (...) independence friendly logic from coupling the dependence declarations with existential quantifiers. As is the case with independence friendly logic, truth of is definable inside . We give such a definition for in the spirit of [11] and [2] and [1]. (shrink)

We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L*∅ is of degree 0’. We show that the same holds also for some weaker logics like L ∅(Hω) and L ∅(Eω). We show that each logic of the form (...) L ∅ (k)(Q), with the number of variables restricted to k, is decidable. Nevertheless – following the argument of M. Mostowski from [Mos89] – for each reasonable set theory no concrete algorithm can provably decide L (k) (Q), for some (Q). We improve also some results related to undecidability and expressibility for logics L(H4) and L(F2) of Krynicki and M. Mostowski from [KM92]. (shrink)

We show that for any pair $\phi$ and $\psi$ of contradictory formulas of dependence logic there is a formula $\theta$ of the same logic such that $\phi\equiv\theta$ and $\psi\equiv\neg\theta$. This generalizes a result of Burgess.

We investigate the expressive power of fragments of first-order logic that are defined in terms of prefixes. The main result establishes a strict hierarchy among these fragments over the signature consisting of a single binary relation. It implies that for each prefix p, there is a sentence in prenex normal form with prefix p, over a single binary relation, such that for all sentences θ in prenex normal form, if θ is equivalent to , then p can be embedded in (...) the prefix of θ. This strengthens a theorem of Walkoe. (shrink)

Henkin quantifiers have been introduced in Henkin (1961). Walkoe (1970) studied basic model-theoretical properties of an extension $L_{*}^{1}$ (H) of ordinary first-order languages in which every sentence is a first-order sentence prefixed with a Henkin quantifier. In this paper we consider a generalization of Walkoe's languages: we close $L_{*}^{1}$ (H) with respect to Boolean operations, and obtain the language L¹(H). At the next level, we consider an extension $L_{*}^{2}$ (H) of L¹(H) in which every sentence is an L¹(H)-sentence prefixed with (...) a Henkin quantifier. We repeat this construction to infinity. Using the (un)definability of truth - in - N for these languages, we show that this hierarchy does not collapse. In addition, we compare some of the present results to the ones obtained by Kripke (1975), McGee (1991), and Hintikka (1996). (shrink)

Independence-friendly logic is a conservative extension of first-order logic that has the same expressive power as existential second-order logic. We attempt to algebraize IF logic in the same spirit as cylindric algebra. We define independence-friendly cylindric set algebras and investigate to what extent they satisfy the axioms of cylindric algebra. We ask whether the equational theory of IF algebras is finitely axiomatizable, and prove two partial results. First, every IF algebra over a structure is an expansion of a Kleene algebra. (...) Moreover, the class of such Kleene algebras generates the variety of all Kleene algebras. Second, every one-dimensional IF algebra over a structure is an expansion of a monadic Kleene algebra. However, the class of such monadic Kleene algebras does not generate the variety of all monadic Kleene algebras. (shrink)

Intuitionistic dependence logic was introduced by Abramsky and Väänänen [1] as a variant of dependence logic under a general construction of Hodges’ (trump) team semantics. It was proven that there is a translation from intuitionistic dependence logic sentences into second order logic sentences. In this paper, we prove that the other direction is also true, therefore intuitionistic dependence logic is equivalent to second order logic on the level of sentences.

That the result of flipping quantifiers and negating what comes after, applied to branching-quantifier sentences, is not equivalent to the negation of the original has been known for as long as such sentences have been studied. It is here pointed out that this syntactic operation fails in the strongest possible sense to correspond to any operation on classes of models.

§1. The mission of axiomatic set theory. What is set theory needed for in the foundations of mathematics? Why cannot we transact whatever foundational business we have to transact in terms of our ordinary logic without resorting to set theory? There are many possible answers, but most of them are likely to be variations of the same theme. The core area of ordinary logic is by a fairly common consent the received first-order logic. Why cannot it take care of itself? (...) What is it that it cannot do? A large part of every answer is probably that first-order logic cannot handle its own model theory and other metatheory. For instance, a first-order language does not allow the codification of the most important semantical concept, viz. the notion of truth, for that language in that language itself, as shown already in Tarski. In view of such negative results it is generally thought that one of the most important missions of set theory is to provide the wherewithal for a model theory of logic. For instance Gregory H. Moore asserts in his encyclopedia article “Logic and set theory” thatSet theory influenced logic, both through its semantics, by expanding the possible models of various theories and by the formal definition of a model; and through its syntax, by allowing for logical languages in which formulas can be infinite in length or in which the number of symbols is uncountable. (shrink)

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.

We shall introduce in this paper a language whose formulas will be interpreted by games of imperfect information. Such games will be defined in the same way as the games for first-order formulas except that the players do not have complete information of the earlier course of the game. Some simple logical properties of these games will be stated together with the relation of such games of imperfect information to higher-order logic. Finally, a set of applications will be outlined.

In this paper we show that first-order languages extended with partially ordered connectives and partially ordered quantifiers define, under a certain interpretation, their own truth-predicate. The interpretation in question is in terms of games of imperfect information. This result is compared with those of Kripke and Feferman.

Jaakko Hintikka points out the power of Skolem functions to affect both what there is and what we know. There is a tension in his presupposition that these functions actually extend the realm of logic. He claims to have resolved the tension by “reconstructing constructivism” along epistemological lines, instead of by a typical ontological construction; however, after the collapse of the distinction between first and second order, that resolution is not entirely satisfactory. Still, it does throw light on the conceptual (...) analysis Hintikka proposes. (shrink)

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)

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)

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)

Krynicki, M. and M. Mostowski, Decidability problems in languages with Henkin quantifiers, Annals of Pure and Applied Logic 58 149–172.We consider the language L with all Henkin quantifiers Hn defined as follows: Hnx1…xny1…yn φ iff f1…fnx1. ..xn φ, ...,fn). We show that the theory of equality in L is undecidable. The proof of this result goes by interpretation of the word problem for semigroups.Henkin quantifiers are strictly related to the function quantifiers Fn defined as follows: Fnx1…xny1…yn φ iff fx1…xn φ,...,f). (...) In contrast with the first result we show that the theory of equality with all quantifiers Fn is decidable.We also consider decidability problems for other theories in languages L and L. (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 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)