We present a self‐contained analysis of some reduction games, which characterise various natural subclasses of the first Baire class of functions ranging from and into 0‐dimensional Polish spaces. We prove that these games are determined, without using Martin's Borel determinacy, and give precise descriptions of the winning strategies for Player I. As an application of this analysis, we get a new proof of the Baire's lemma on pointwise convergence.

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding complete functions. (...) We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (shrink)

Turing machines define polynomial time on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time ? Earlier, one of us conjectured a negative answer. The problem motivated a quest for stronger and stronger (...) PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines . The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime. (shrink)

We explore a non-classical, universal set theory, based on a purely 'structural' conception of sets. A set is a transfinite process of unfolding of an arbitrary binary structure, with identity of sets given by the observational equivalence between such processes. We formalize these notions using infinitary modal logic, which provides partial descriptions for set structures up to observational equivalence. We describe the comprehension and topological properties of the resulting set-theory, and we use it to give non-classical solutions to classical paradoxes, (...) to prove fixed-point theorems that relate recursion and corecursion, to formalize 'super-large', reflexive categories and 'super-large' circular modes, and to provide 'natural' solutions for domain equations. (shrink)

Beginning from some passages by Vācaspati Miśra and Bhāskararāya Makhin discussing the relationship between a crown and the gold of which it is made, this paper investigates the complex underlying connections among difference, non-difference, coreferentiality, and qualification qua relations. Methodologically, philological care is paired with formal logical analysis on the basis of ‘Navya-Nyāya Formal Language’ premises and an axiomatic set theory-based approach. This study is intended as the first step of a broader investigation dedicated to analysing causation and transformation in (...) non-difference. (shrink)

The present paper is a continuation of a previous one by the same title, the content of which faced the issue concerning the relations of coreference and qualification in compliance with the Navya-Nyāya theoretical framework, although prompted by the Advaita-Vedānta enquiry regarding non-difference. In a complementary manner, by means of a formal analysis of equivalence, equality, and identity, this section closes the loop by assessing the extent to which non-difference, the main issue here, cannot be reduced to any of the (...) former. The following sections of this study will focus on the assessment of the eventual possibility of causation and transformation in non-difference. (shrink)

In 1887–1894, Richard Dedekind explored a number of ideas within the project of placing mappings at the very center of pure mathematics. We review two such initiatives: the introduction in 1894 of groups into Galois theory intrinsically via field automorphisms, and a new attempt to define the continuum via maps from ℕ to ℕ in 1891. These represented the culmination of Dedekind’s efforts to reconceive pure mathematics within a theory of sets and maps and throw new light onto the nature (...) of his structuralism and its specificity in relation to the work of other mathematicians. (shrink)

In this article the problem of unification of mathematical theories is discussed. We argue, that specific problems arise here, which are quite different than the problems in the case of empirical sciences. In particular, the notion of unification depends on the philosophical standpoint. We give an analysis of the notion of unification from the point of view of formalism, Gödel's platonism and Quine's realism. In particular we show, that the concept of “having the same object of study” should be made (...) precise in the case of mathematical theories. In the appendix we give a working proposal of a certain understanding of this notion. (shrink)

A lattice L is coordinatizable, if it is isomorphic to the lattice L of principal right ideals of some von Neumann regular ring R. This forces L to be complemented modular. All known sufficient conditions for coordinatizability, due first to von Neumann, then to Jónsson, are first-order. Nevertheless, we prove that coordinatizability of lattices is not first-order, by finding a non-coordinatizable lattice K with a coordinatizable countable elementary extension L. This solves a 1960 problem of Jónsson. We also prove that (...) there is no [Formula: see text] statement equivalent to coordinatizability. Furthermore, the class of coordinatizable lattices is not closed under countable directed unions; this solves another problem of Jónsson from 1962. (shrink)

We present the notion of finite high-order Gowers games, and prove a statement parallel to Gowers's Combinatorial Lemma for these games. We derive ‘quantitative’ versions of the original Gowers Combinatorial Lemma and of Gowers's Dichotomy, which place them in the context of the recently introduced infinite dimensional asymptotic theory for Banach spaces.

The author proved in his Ph.D. Thesis [W. Veldman, Investigations in intuitionistic hierarchy theory, Ph.D. Thesis, Katholieke Universiteit Nijmegen, 1981] that, in intuitionistic analysis, the positively Borel subsets of Baire space form a genuinely growing hierarchy: every level of the hierarchy contains sets that do not occur at any lower level. It follows from this result that there are natural examples of analytic and also of co-analytic sets that are not positively Borel. It turns out, however, that, in intuitionistic analysis, (...) one may give surprisingly different and, in some sense, much more simple examples of analytic and co-analytic sets that fail to be positively Borel. In the paper, two such examples are given. In proving them correct, one obtains new proofs of the Borel Hierarchy Theorem. Brouwer’s Continuity Principle plays a crucial role in arguments. (shrink)

It is proved that the forcing apparatus can be built and set to work in ZFCA (=ZFC minus foundation plus the antifoundation axiom AFA). The key tools for this construction are greatest fixed points of continuous operators (a method sometimes referred to as “corecursion”). As an application it is shown that the generic extensions of standard models of ZFCA are models of ZFCA again.

In this paper, we explore some of the consequences of Martin’s Conjecture on degree invariant Borel maps. These include the strongest conceivable ergodicity result for the Turing equivalence relation with respect to the filter on the degrees generated by the cones, as well as the statement that the complexity of a weakly universal countable Borel equivalence relation always concentrates on a null set.

The standard theory of logic programming is not applicable to Prolog programs even not to pure code. Modifying the theory to take account of reality more is the motivation of this article. For this purpose we introduce the ℓ-completion and the inductive extension of a logic program. Both are first-order theories in a language with operators for success, failure and termination of goals. The ℓ-completion of a logic program is a sound and complete axiomatization of the Prolog depth-first search under (...) certain natural conditions; the inductive extension of the ℓ-completion is a suitable theory for proving termination and equivalence of pure Prolog programs with negation. (shrink)

We introduce 0• as a sharp for an inner model with a proper class of strong cardinals. We prove the existence of the core model K in the theory “ does not exist”. Combined with work of Woodin, Steel, and earlier work of the author, this provides the last step for determining the exact consistency strength of the assumption in the statement of the 12th Delfino problem pp. 221–224)).

This paper studies homogeneously Suslin (hom) sets of reals in tame mice. The following results are established: In 0 ¶ the hom sets are precisely the [Symbol] sets. In M n every hom set is correctly [Symbol] and (δ + 1)-universally Baire where ä is the least Woodin. In M u every hom set is <λ-hom, where λ is the supremum of the Woodins.

Should weak forms of the axiom of choice really be accepted within constructive mathematics? A critical view of the Brouwer-Heyting-Kolmogorov interpretation, accompanied by the intention to include nondeterministic algorithms, leads us to subscribe to Richman's appeal for dropping countable choice. As an alternative interpretation of intuitionistic logic, we propose to renew dialogue semantics.

En este artículo se examinan algunas implicaciones del naturalismo matemático de P. Maddy como una concepción filosófica que permite superar las dificultades del ficcionalismo y el realismo fisicalista en matemáticas. Aparte de esto, la mayor virtud de tal concepción parece ser que resuelve el problema que plantea para la aplicabilidad de la matemática el no asumir la tesis de indispensabilidad de Quine sin comprometerse con su holismo confirmacional. A continuación, sobre la base de dificultades intrínsecas al programa de Maddy, exploramos (...) un camino naturalista mejor motivado, el enfoque cognitivista corporeizado, y sugerimos que él permite explicar de manera adecuada la postulación de ciertos cardinales grandes, en particular, la aceptación de conjuntos no-construibles. (shrink)

We discuss the principles for a primitive, object-linguistic notion of consequence proposed by ) that yield a version of Curry’s paradox. We propose and study several strategies to weaken these principles and overcome paradox: all these strategies are based on the intuition that the object-linguistic consequence predicate internalizes whichever meta-linguistic notion of consequence we accept in the first place. To these solutions will correspond different conceptions of consequence. In one possible reading of these principles, they give rise to a notion (...) of logical consequence: we study the corresponding theory of validity by showing that it is conservative over a wide range of base theories: this result is achieved via a well-behaved form of local reduction. The theory of logical consequence is based on a restriction of the introduction rule for the consequence predicate. To unrestrictedly maintain this principle, we develop a conception of object-linguistic consequence, which we call grounded consequence, that displays a restriction of the structural rule of reflexivity. This construction is obtained by generalizing Saul Kripke’s inductive theory of truth. Grounded validity will be shown to satisfy several desirable principles for a naïve, self-applicable notion of consequence. (shrink)

We analyze the degree-structure induced by large reducibilities under the Axiom of Determinacy. This generalizes the analysis of Borel reducibilities given in Alessandro Andretta and Donald A. Martin [1], Luca Motto Ros [6] and Luca Motto Ros. [5] e.g. to the projective levels.

We develop a variant of Least Fixed Point logic based on First Orderlogic with a relaxed version of guarded quantification. We develop aGame Theoretic Semantics of this logic, and find that under reasonableconditions, guarding quantification does not reduce the expressibilityof Least Fixed Point logic. But we also find that the guarded version ofa least fixed point algorithm may have a greater time complexity thanthe unguarded version, by a linear factor.

We extend a theorem of Barwise and Nadel describing the relationship between approximations of canonical Scott sentences and admissible sets to the case of orbit equivalence relations induced on an arbitrary Polish space by a Polish group action.

There are two main ways in which the notion of mereological fusion is usually defined in the current literature in mereology which have been labelled ‘Leśniewski fusion’ and ‘Goodman fusion’. It is well-known that, with Minimal Mereology as the background theory, every Leśniewski fusion also qualifies as a Goodman fusion. However, the converse does not hold unless stronger mereological principles are assumed. In this paper I will discuss how the gap between the two notions can be filled, focussing in particular (...) on two specific sets of principles that appear to be of particular philosophical interest. The first way to make the two notions equivalent can be used to shed some interesting light on the kind of intuition both notions seem to articulate. The second shows the importance of a little-known mereological principle which I will call ‘Mild Supplementation’. As I will show, the mereology obtained by adding Mild Supplementation to Minimal Mereology occupies an interesting position in the landscape of theories that are stronger than Minimal Mereology but weaker than what Achille Varzi and Roberto Casati have labelled ‘Extensional Mereology’. (shrink)

We study the relationship between least and inflationary fixed-point logic. In 1986, Gurevich and Shelah proved that in the restriction to finite structures, the two logics have the same expressive power. On infinite structures however, the question whether there is a formula in IFP not equivalent to any LFP-formula was left open.In this paper, we answer the question negatively, i.e. we show that the two logics are equally expressive on arbitrary structures. We give a syntactic translation of IFP-formulae to LFP-formulae (...) such that the two formulae are equivalent on all structures.As a consequence of the proof we establish a close correspondence between the LFP-alternation hierarchy and the IFP-nesting depth hierarchy. We also show that the alternation hierarchy for IFP collapses to the first level, i.e. the complement of any inflationary fixed point is itself an inflationary fixed point. (shrink)

§1. I will start with a quick definition of descriptive set theory: It is the study of the structure of definable sets and functions in separable completely metrizable spaces. Such spaces are usually called Polish spaces. Typical examples are ℝn, ℂn, Hilbert space and more generally all separable Banach spaces, the Cantor space 2ℕ, the Baire space ℕℕ, the infinite symmetric group S∞, the unitary group, the group of measure preserving transformations of the unit interval, etc.In this theory sets are (...) classified in hierarchies according to the complexity of their definitions and the structure of sets in each level of these hierarchies is systematically analyzed. In the beginning we have the Borel sets in Polish spaces, obtained by starting with the open sets and closing under the operations of complementation and countable unions, and the corresponding Borel hierarchy. After this come the projective sets, obtained by starting with the Borel sets and closing under the operations of complementation and projection, and the corresponding projective hierarchy.There are also transfinite extensions of the projective hierarchy and even much more complex definable sets studied in descriptive set theory, but I will restrict myself here to Borel and projective sets, in fact just those at the first level of the projective hierarchy, i.e., the Borel (), analytic () and coanalytic () sets. (shrink)

Gupta-Belnap-style circular definitions use all real numbers as possible starting points of revision sequences. In that sense they are boldface definitions. We discuss lightface versions of circular definitions and boldface versions of inductive definitions.

A theory of the transfinite Tarskian hierarchy of languages is outlined and compared to a notion of partial truth by Kripke. It is shown that the hierarchy can be embedded into Kripke's minimal fixed point model. From this results on the expressive power of both approaches are obtained.

Within the traditional Hilbert space formalism of quantum mechanics, it is not possible to describe a particle as possessing, simultaneously, a sharp position value and a sharp momentum value. Is it possible, though, to describe a particle as possessing just a sharp position value (or just a sharp momentum value)? Some, such as Teller, have thought that the answer to this question is No - that the status of individual continuous quantities is very different in quantum mechanics than in classical (...) mechanics. On the contrary, I shall show that the same subtle issues arise with respect to continuous quantities in classical and quantum mechanics; and that it is, after all, possible to describe a particle as possessing a sharp position value without altering the standard formalism of quantum mechanics. (shrink)

It was questions about points on the real line that initiated the study of set theory. Points paved the way to point sets and these to ever more abstract sets. And there was more: Reflection on structural properties of point sets not only initiated the study of ordinary sets; it also supplied blueprints for defining extra-ordinary, “large” sets, transcending those provided by standard set theory. In return, the existence of such large sets turned out critical to settling open conjectures about (...) point sets.How to explain such action at a distance between the very large and the rather small? Rather than having an air of magic, could these results rest on deep structural similarities between the two superficially distant species of sets?In this essay I dissect one group of such two-way results. Their linchpin is the notion of measure.§1. Vitali's impossibility result. Our starting point is a problem in measure theory regarding the notion of “Lebesgue measure.” Before presenting the problem, I would like to review the notion of Lebesgue measure. Rather than listing its main properties, I would like to show how Lebesgue measure is born out of an attempt to generalize the notion of the length of an interval to arbitrary sets of reals. One tries to approximate arbitrary sets of reals by intervals, in the hope that the lengths of the intervals will induce a measure on these sets. (shrink)

This paper presents an approach to truth and the Liar paradox which combines elements of context dependence and hierarchy. This approach is developed formally, using the techniques of model theory in admissible sets. Special attention is paid to showing how starting with some ideas about context drawn from linguistics and philosophy of language, we can see the Liar sentence to be context dependent. Once this context dependence is properly understood, it is argued, a hierarchical structure emerges which is neither ad (...) hoc nor unnatural. (shrink)

We study Lebesgue and Atsuji spaces within subsystems of second order arithmetic. The former spaces are those such that every open covering has a Lebesgue number, while the latter are those such that every continuous function defined on them is uniformly continuous. The main results we obtain are the following: the statement “every compact space is Lebesgue” is equivalent to $\hbox{\sf WKL}_0$ ; the statements “every perfect Lebesgue space is compact” and “every perfect Atsuji space is compact” are equivalent to (...) $\hbox{\sf ACA}_0$ ; the statement “every Lebesgue space is Atsuji” is provable in $\hbox{\sf RCA}_0$ ; the statement “every Atsuji space is Lebesgue” is provable in $\hbox{\sf ACA}_0$ . We also prove that the statement “the distance from a closed set is a continuous function” is equivalent to $\Pi^1_1\hbox{-\sf CA}_0$. (shrink)

I discuss Steinhart’s argument against Benacerraf’s famous multiple-reductions argument to the effect that numbers cannot be sets. Steinhart offers a mathematical argument according to which there is only one series of sets to which the natural numbers can be reduced, and thus attacks Benacerraf’s assumption that there are multiple reductions of numbers to sets. I will argue that Steinhart’s argument is problematic and should not be accepted.

We present an infinite-game characterization of the well-founded semantics for function-free logic programs with negation. Our game is a simple generalization of the standard game for negation-less logic programs introduced by van Emden [M.H. van Emden, Quantitative deduction and its fixpoint theory, Journal of Logic Programming 3 37–53] in which two players, the Believer and the Doubter, compete by trying to prove a query. The standard game is equivalent to the minimum Herbrand model semantics of logic programming in the sense (...) that a query succeeds in the minimum model semantics iff the Believer has a winning strategy for the game which begins with the Doubter doubting this query. The game for programs with negation that we propose follows the same rules as the standard one, except that the players swap roles every time the play “passes through” negation. We start our investigation by establishing the determinacy of the new game by using some classical tools from the theory of infinite-games. Our determinacy result immediately provides a novel and purely game-theoretic characterization of the semantics of negation in logic programming. We proceed to establish the connections of the game semantics to the existing semantic approaches for logic programming with negation. For this purpose, we first define a refined version of the game that uses degrees of winning and losing for the two players. We then demonstrate that this refined game corresponds exactly to the infinite-valued minimum model semantics of negation [P. Rondogiannis,W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 441–467]. This immediately implies that the unrefined game is equivalent to the well-founded semantics. (shrink)

Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs (or on any class of countable structures consisting of the models of a sentence of L ω ₁ ω ) is far from complete (see [5, 2]). In (...) this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence relations which are complete under Borel reducibility, but in fact any analytic equivalence relation is Borel equivalent to such a relation. This result and the techniques introduced answer questions raised in [5] about the comparison between isomorphism and bi-embeddability. Finally, as in [5] our results apply not only to classes of countable structures defined by sentences of ω ₁ ω , but also to discrete metric or ultrametric Polish spaces, compact metrizable topological spaces and separable Banach spaces, with various notions of embeddability appropriate for these classes, as well as to actions of Polish monoids. (shrink)

We prove that if V = L then there is a $\Pi _{1}^{1}$ maximal orthogonal (i.e., mutually singular) set of measures on Cantor space. This provides a natural counterpoint to the well-known theorem of Preiss and Rataj [16] that no analytic set of measures can be maximal orthogonal.

Locally finite omega languages were introduced by Ressayre [Formal languages defined by the underlying structure of their words. J Symb Log 53(4):1009–1026, 1988]. These languages are defined by local sentences and extend ω-languages accepted by Büchi automata or defined by monadic second order sentences. We investigate their topological complexity. All locally finite ω-languages are analytic sets, the class LOC ω of locally finite ω-languages meets all finite levels of the Borel hierarchy and there exist some locally finite ω-languages which are (...) Borel sets of infinite rank or even analytic but non-Borel sets. This gives partial answers to questions of Simonnet (Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris 7, March 1992) and of Duparc et al. [Computer science and the fine structure of Borel sets. Theor Comput Sci 257(1–2):85–105, 2001]. (shrink)

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 1-counter Büchi automata is equivalent to the determinacy of analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge ofω-languages accepted by 1-counter Büchi automata is equivalent to the analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automatonand a (...) Büchi automatonsuch that: There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge gameW,L()); There exists a model of ZFC in which the Wadge gameW,L()) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge gameW,L()). (shrink)

Set theory deals with the most fundamental existence questions in mathematics—questions which affect other areas of mathematics, from the real numbers to structures of all kinds, but which are posed as dealing with the existence of sets. Especially noteworthy are principles establishing the existence of some infinite sets, the so-called “arbitrary sets.” This paper is devoted to an analysis of the motivating goal of studying arbitrary sets, usually referred to under the labels of quasi-combinatorialism or combinatorial maximality. After explaining what (...) is meant by definability and by “arbitrariness,” a first historical part discusses the strong motives why set theory was conceived as a theory of arbitrary sets, emphasizing connections with analysis and particularly with the continuum of real numbers. Judged from this perspective, the axiom of choice stands out as a most central and natural set-theoretic principle (in the sense of quasi-combinatorialism). A second part starts by considering the potential mismatch between the formal systems of mathematics and their motivating conceptions, and proceeds to offer an elementary discussion of how far the Zermelo—Fraenkel system goes in laying out principles that capture the idea of “arbitrary sets”. We argue that the theory is rather poor in this respect. (shrink)

Results of Sierpiski and others have shown that certain finite-dimensional product sets can be written as unions of subsets, each of which is ‘narrow’ in a corresponding direction; that is, each line in that direction intersects the subset in a small set. For example, if the set ω × ω is partitioned into two pieces along the diagonal, then one piece meets every horizontal line in a finite set, and the other piece meets each vertical line in a finite set. (...) Such partitions or coverings can exist only when the sets forming the product are of limited size.This paper considers such coverings for products of infinitely many sets . In this case, a covering of the product by narrow sets, one for each coordinate direction, will exist no matter how large the factor sets are. But if one restricts the sets used in the covering , then the existence of narrow coverings is related to a number of large cardinal properties: partition cardinals, the free subset problem, nonregular ultrafilters, and so on.One result given here is a relative consistency proof for a hypothesis used by S. Mrówka to produce a counterexample in the dimension theory of metric spaces. (shrink)

Let X be a Polish space and a separable compact subset of the first Baire class on X. For every sequence dense in , the descriptive set-theoretic properties of the set are analyzed. It is shown that if is not first countable, then is -complete. This can also happen even if is a pre-metric compactum of degree at most two, in the sense of S. Todorčević. However, if is of degree exactly two, then is always Borel. A deep result of (...) G. Debs implies that contains a Borel cofinal set and this gives a tree-representation of . We show that classical ordinal assignments of Baire-1 functions are actually -ranks on . We also provide an example of a Ramsey-null subset A of for which there does not exist a Borel set BA such that the difference BA is Ramsey-null. (shrink)

Contemporary philosophical accounts of the applicability of mathematics in physical sciences and the empirical world are based on formalized relations between the mathematical structures and the physical systems they are supposed to represent within the models. Such relations were constructed both to ensure an adequate representation and to allow a justification of the validity of the mathematical models as means of scientific inference. This article puts in evidence the various circularities (logical, epistemic, and of definition) that are present in these (...) formal constructions and discusses them as an argument for the alternative semantic and propositional-structure accounts of the applicability of mathematics. (shrink)

Game-theoretic solution concepts describe sets of strategy profiles that are optimal for all players in some plausible sense. Such sets are often found by recursive algorithms like iterated removal of strictly dominated strategies in strategic games, or backward induction in extensive games. Standard logical analyses of solution sets use assumptions about players in fixed epistemic models for a given game, such as mutual knowledge of rationality. In this paper, we propose a different perspective, analyzing solution algorithms as processes of learning (...) which change game models. Thus, strategic equilibrium gets linked to fixed-points of operations of repeated announcement of suitable epistemic statements. This dynamic stance provides a new look at the current interface of games, logic, and computation. (shrink)

This dissertation addresses a variety of foundational issues pertaining to the notion of algorithm employed in mathematics and computer science. In these settings, an algorithm is taken to be an effective mathematical procedure for solving a previously stated mathematical problem. Procedures of this sort comprise the notional subject matter of the subfield of computer science known as algorithmic analysis. In this context, algorithms are referred to via proper names of which computational properties are directly predicated )). Moreover, many formal results (...) are traditionally stated by explicitly quantifying over algorithms. These observations motivate the view that algorithms are themselves abstract mathematical objects -- a view I refer to as algorithmic realism. The status of this view is clearly related to that of Church's Thesis -- i.e. the claim that a function is computable by an algorithm just in case it is partial recursive. But whereas Church's Thesis is widely accepted on the basis of several well-known mathematical analyses of algorithmic computability, there is presently no consensus on how we can uniformly identify individual algorithms with mathematical objects. In the first chapter of this work, I attempt to illustrate the theoretical significance of algorithmic realism. I suggest that this view is not only of foundational significance to computer science, but also worth highlighting due to the role algorithms play in the fixation of mathematical knowledge and their relationship to intensional entities such as propositions and properties. Chapter Two presents a formal framework for reducing computational discourse to mathematical discourse modeled on contemporary discussion of mathematical nominalism. Chapter Three is centered on a case study intended to illustrate the technical exigencies involved with defending algorithmic realism. Chapter Four explores various ways in which algorithms might be identified with models of computation. And finally, Chapter Five argues that no such identification can uniformly satisfy all statements of algorithmic identity and non-identity affirmed by computational practice. I suggest that the technical crux of algorithmic realism lies in the necessity of reducing recursive specifications of algorithms to iterative models of computation in a manner which preserves algorithmic identity. (shrink)

The formalist philosophy of mathematics (in its purest, most extreme version) is widely regarded as a “discredited position”. This pure and extreme version of formalism is called by some authors “game formalism”, because it is alleged to represent mathematics as a meaningless game with strings of symbols. Nevertheless, I would like to draw attention to some arguments in favour of game formalism as an appropriate philosophy of real mathematics. For the most part, these arguments have not yet been used or (...) were neglected in past discussions. (shrink)