In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem (...) in this context. (shrink)

One of the problems in economics that economists have devoted a considerable amount of attention in prevalent years has been to ensure consistency in the models they employ. Assuming markets to be generally in some state of equilibrium, it is asked under what circumstances such equilibrium is possible. The fundamental mathematical tools used to address this concern are fixed point theorems: the conditions under which sets of assumptions have a solution. This book gives the reader access to (...) the mathematical techniques involved and goes on to apply fixed point theorems to proving the existence of equilibria for economics and for co-operative and noncooperative games. Special emphasis is given to economics and games in cases where the preferences of agents may not be transitive. The author presents topical proofs of old results in order to further clarify the results. He also proposes fresh results, notably in the last chapter, that refer to the core of a game without transitivity. This book will be useful as a text or reference work for mathematical economists and graduate and advanced undergraduate students. (shrink)

We prove an analogue of the fixed-point theorem for the case of definably amenable groups.

The semantic paradoxes are associated with self-reference or referential circularity. However, there are infinitary versions of the paradoxes, such as Yablo's paradox, that do not involve this form of circularity. It remains an open question what relations of reference between collections of sentences afford the structure necessary for paradoxicality -- these are the so-called "dangerous" directed graphs. Building on Rabern, et. al (2013) we reformulate this problem in terms of fixed points of certain functions, thereby boiling it down to (...) get a purely mathematical problem. (shrink)

We prove a definable analogue to Brouwer's Fixed Point Theorem for o-minimal structures of real closed field expansions: A continuous definable function mapping from the unit simplex into itself admits a fixed point, even though the underlying space is not necessarily topologically complete. Our proof is direct and elementary; it uses a triangulation technique for o-minimal functions, with an application of Sperner's Lemma.

Within the technical frame supplied by the algebraic variety of diagonalizable algebras, defined by R. Magari in [2], we prove the following: Let T be any first-order theory with a predicate Pr satisfying the canonical derivability conditions, including Löb's property. Then any formula in T built up from the propositional variables $q,p_{1},...,p_{n}$ , using logical connectives and the predicate Pr, has the same "fixed-points" relative to q (that is, formulas $\psi (p_{1},...,p_{n})$ for which for all $p_{1},...,p_{n}\vdash _{T}\phi (\psi (p_{1},...,p_{n}),p_{1},...,p_{n})\leftrightarrow (...) \psi (p_{1},...,p_{n})$ ) of a formula $\phi ^{\ast}$ of the same kind, obtained from φ in an effective way. Moreover, such $\phi ^{\ast}$ is provably equivalent to the formula obtained from φ substituting with $\phi ^{\ast}$ itself all the occurrences of q which are under Pr. In the particular case where q is always under Pr in φ, $\phi ^{\ast}$ is the unique (up to provable equivalence) "fixed-point" of φ. Since this result is proved only assuming Pr to be canonical, it can be deduced that Löb's property is, in a sense, equivalent to Gödel's diagonalization lemma. All the results are proved more generally in the intuitionistic case. (shrink)

The new concept of lambda calculi with monotone inductive types is introduced byhelp of motivations drawn from Tarski's fixed-point theorem (in preorder theory) andinitial algebras and initial recursive algebras from category theory. They are intendedto serve as formalisms for studying iteration and primitive recursion ongeneral inductively given structures. Special accent is put on the behaviour ofthe rewrite rules motivated by the categorical approach, most notably on thequestion of strong normalization (i.e., the impossibility of an infinitesequence of successive rewrite (...) steps). It is shown that this key propertyhinges on the concrete formulation. The canonical system of monotone inductivetypes, where monotonicity is expressed by a monotonicity witness beinga term expressing monotonicity through its type, enjoys strong normalizationshown by an embedding into the traditional system of non-interleavingpositive inductive types which, however, has to be enriched by the parametricpolymorphism of system F. Restrictions to iteration on monotone inductive typesalready embed into system F alone, hence clearly displaying the differencebetween iteration and primitive recursion with respect to algorithms despitethe fact that, classically, recursion is only a concept derived from iteration. (shrink)

In this paper, we investigate the logical strength of two types of fixed point theorems in the context of reverse mathematics. One is concerned with extensions of the Banach contraction principle. Among theorems in this type, we mainly show that the Caristi fixed point theorem is equivalent to math formula over math formula. The other is dedicated to topological fixed point theorems such as the Brouwer fixed point theorem. We (...) introduce some variants of the Fan-Browder fixed point theorem and the Kakutani fixed point theorem, which we call math formula and math formula, respectively. Then we show that math formula is equivalent to math formula and math formula is equivalent to math formula, over math formula. In addition, we also study the application of the Fan-Browder fixed point theorem to game systems. (shrink)

We consider so‐called extremal numberings that form the greatest or minimal degrees under the reducibility of all A‐computable numberings of a given family of subsets of, where A is an arbitrary oracle. Such numberings are very common in the literature and they are called universal and minimal A‐computable numberings, respectively. The main question of this paper is when a universal or a minimal A‐computable numbering satisfies the Recursion Theorem (with parameters). First we prove that the Turing degree of a set (...) A is hyperimmune if and only if every universal A‐computable numbering satisfies the Recursion Theorem. Next we prove that any universal A‐computable numbering satisfies the Recursion Theorem with parameters if A computes a non‐computable c.e. set. We also consider the property of precompleteness of universal numberings, which in turn is closely related to the Recursion Theorem. Ershov proved that a numbering is precomplete if and only if it satisfies the Recursion Theorem with parameters for partial computable functions. In this paper, we show that for a given A‐computable numbering, in the general case, the Recursion Theorem with parameters for total computable functions is not equivalent to the precompleteness of the numbering, even if it is universal. Finally we prove that if A is high, then any infinite A‐computable family has a minimal A‐computable numbering that satisfies the Recursion Theorem. (shrink)

Political theorists study the attributes of desirable social-moral states of affairs. Schaefer (forthcoming) aims to show that "static political theory" of this kind rests on shaky foundations. His argument revolves around an application of an abstruse mathematical theorem -- Kakutani's fixed point theorem -- to the social-moral domain. We show that Schaefer has misunderstood the implications of this theorem for political theory. Theorists who wish to study the attributes of social-moral states of affairs should carry on, safe in (...) the knowledge that Kakutani's theorem poses no threat to this enterprise. (shrink)

We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice (...) is complete for dimension greater than or equal to two in the sense that it is computably equivalent to Weak Kőnig’s Lemma. While we can present two independent proofs for dimension three and upward that are either based on a simple geometric construction or a combinatorial argument, the proof for dimension two is based on a more involved inverse limit construction. The connected choice operation in dimension one is known to be equivalent to the Intermediate Value Theorem; we prove that this problem is not idempotent in contrast to the case of dimension two and upward. We also prove that Lipschitz continuity with Lipschitz constants strictly larger than one does not simplify finding fixed points. Finally, we prove that finding a connectedness component of a closed subset of the Euclidean unit cube of any dimension greater than or equal to one is equivalent to Weak Kőnig’s Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes. (shrink)

In this paper, we introduce the notion of S ∗ p -partial metric spaces which is a generalization of S-metric spaces and partial-metric spaces. Also, we give some of the topological properties that are important in knowing the convergence of the sequences and Cauchy sequence. Finally, we study a new common fixed point theorems in this spaces.

Two examples of Galois connections and their dual forms are considered. One of them is applied to formulate a criterion when a given subset of a complete lattice forms a complete lattice. The second, closely related to the first, is used to prove in a short way the Knaster-Tarski’s fixed point theorem.

Anti-naturalistic critics of Unity of Science have often tried to establish a fundamental difference between social and physical science on the grounds that research in the social field (unlike physical research) seems to interfere with the original situations so as to make accurate predictions impossible. A 'social' prediction may, e.g., itself influence the course of events so that the prediction proves false. H. A. Simon has dealt with such effects of predictions in a well-known article. Drawing on a mathematical theorem, (...) Brouwer's so-called fixed-point theorem, he claims to prove that reactions to published predictions can be accounted for so that appropriately adjusted predictions can avoid being self-destructive. The present article is an attempt to show that Simon's use of the Brouwer theorem is misplaced, and that his proof does not parry the anti-naturalistic argument. Indeed, the burden of his proof is not really of a mathematical, but, it is argued, of a 'protosociological' kind. In conclusion, the article points to the fundamental inadequacy of a frame of reference which makes the 'interference' or 'reaction' effects due to people's having access to social knowledge appear strange or eccentric: as some kind of marginal irregularity causing trouble in the philosophy of (social) science. (shrink)

In this paper I argue that it’s impossible for there to be a single universal theory of meaning for a language. First, I will consider some minimal expressiveness requirements a language must meet to be able to express semantic claims. Then I will argue that in order to have a single unified theory of meaning, these expressiveness requirements must be satisfied by a language which the semantic theory itself applies to. That is, we would need a language which can express (...) its own meaning. It has been well-known since Tarski that theories of meaning whose central notion is truth can’t be expressed in a language which they apply to. Here, I develop Quine’s formulation of the Liar Paradox in grammatical terms and use this to extend Tarski’s result to all theories of meaning. This general version of the paradox can be formalised as a special case of the Lawvere Fixed-Point Theorem applied to a categorial grammar. Taken together with the initial arguments, I infer that a universal theory of meaning is impossible and conclude the paper with a brief discussion on what alternatives are available. (shrink)

The problem of Uniqueness and Explicit Definability of Fixed Points for Interpretability Logic is considered. It turns out that Uniqueness is an immediate corollary of a theorem of Smoryński.

We clarify the respective roles fixed points, diagonalization, and self- reference play in proofs of Gödel’s first incompleteness theorem.

This manuscript investigates fixed point of single-valued Hardy-Roger’s type F -contraction globally as well as locally in a convex b -metric space. The paper, using generalized Mann’s iteration, iterates fixed point of the abovementioned contraction; however, the third axiom of the F -contraction is removed, and thus the mapping F is relaxed. An important approach used in the article is, though a subset closed ball of a complete convex b -metric space is not necessarily complete, the (...) convergence of the Cauchy sequence is confirmed in the subset closed ball. The results further lead us to some important corollaries, and examples are produced in support of our main theorems. The paper most importantly presents application of our results in finding solution to the integral equations. (shrink)

The problem of Uniqueness and Explicit Definability of Fixed Points for Interpretability Logic is considered. It turns out that Uniqueness is an immediate corollary of a theorem of Smoryski.

The paper presents a survey of author's results on definable fixed points in modal, temporal, and intuitionistic propositional logics. The well-known Fixed Point Theorem considers the modalized case, but here we investigate the positive case. We give a classification of fixed point theorems, describe some classes of models with definable least fixed points of positive operators, special positive operators, and give some examples of undefinable least fixed points. Some other interesting phenomena are (...) discovered – definability by formulas that do not preserve positivity of parameters and definability by finite sets of formulas. We also consider negative operators, graded modalities, construct undefinable inflationary fixed points, and put some problems. (shrink)

Slides for the first tutorial on Gödel's incompleteness theorems, held at UniLog 5 Summer School, Istanbul, June 24, 2015.

To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by Bernardi-Montagna in [5]. With that interpretation in mind, a system LR of modal propositional logic is axiomatized, a modal completeness theorem is established for LR and, after that, a uniform arithmetical completeness theorem with respect to PA is obtained for LR.

We present a quite simple proof of the fixed point theorem for GL. We also use this proof to show that Sambin's algorithm yields a fixed point.

It is well known that, in Peano arithmetic, there exists a formula Theor (x) which numerates the set of theorems. By Gödel's and Löb's results, we have that Theor (˹p˺) ≡ p implies p is a theorem ∼Theor (˹p˺) ≡ p implies p is provably equivalent to Theor (˹0 = 1˺). Therefore, the considered "equations" admit, up to provable equivalence, only one solution. In this paper we prove (Corollary 1) that, in general, if P (x) is an arbitrary formula (...) built from Theor (x), then the fixed-point of P (x) (which exists by the diagonalization lemma) is unique up to provable equivalence. This result is settled referring to the concept of diagonalizable algebra (see Introduction). (shrink)

Minimal predicates P satisfying a given first-order description ϕ(P) occur widely in mathematical logic and computer science. We give an explicit first-order syntax for special first-order 'PIA conditions' ϕ(P) which quarantees unique existence of such minimal predicates. Our main technical result is a preservation theorem showing PIA-conditions to be expressively complete for all those first-order formulas that are preserved under a natural model-theoretic operation of 'predicate intersection'. Next, we show how iterated predicate minimization on PIA-conditions yields a language MIN(FO) equal (...) in expressive power to LFP(FO), first-order logic closed under smallest fixed-points for monotone operations. As a concrete illustration of these notions, we show how our sort of predicate minimization extends the usual frame correspondence theory of modal logic, leading to a proper hierarchy of modal axioms: first-order-definable, first-order fixed-point definable, and beyond. (shrink)

Minimal predicates P satisfying a given first-order description φ(P) occur widely in mathematical logic and computer science. We give an explicit first-order syntax for special first-order ‘PIA conditions’ φ(P) which guarantees unique existence of such minimal predicates. Our main technical result is a preservation theorem showing PIA-conditions to be expressively complete for all those first-order formulas that are preserved under a natural model-theoretic operation of ‘predicate intersection’. Next, we show how iterated predicate minimization on PIA-conditions yields a language MIN(FO) equal (...) in expressive power to LFP(FO), first-order logic closed under smallest fixed-points for monotone operations. As a concrete illustration of these notions, we show how our sort of predicate minimization extends the usual frame correspondence theory of modal logic, leading to a proper hierarchy of modal axioms: first-order-definable, first-order fixed-point definable, and beyond. (shrink)

This article is written for both the general mathematican and the specialist in mathematical logic. No prior knowledge of metamathematics, recursion theory or combinatory logic is presupposed, although this paper deals with quite general abstractions of standard results in those three areas. Our purpose is to show how some apparently diverse results in these areas can be derived from a common construction. In Section 1 we consider five classical fixed point arguments (or rather, generalizations of them) which we (...) present as problems that the reader might enjoy trying to solve. Solutions are given at the end of the section. In Section 2 we show how all these solutions can be obtained as special cases of a single fixed point theorem. In Section 3 we consider another generalization of the five fixed point results of Section 1 and show that this is of the same strength as that of Section 2. In Section 4 we show some curious strengthenings of results of Section 3 which we believe to be of some interest on their own accounts. (shrink)

Let T be Kripke–Platek set theory with infinity extended by the axiom (Beta) plus the schema that claims that every set-bounded Σ-definable monotone operator from the collection of all sets to Pow(a) for some set a has a fixed point. Then T proves that every such operator has a least fixed point. This result is obtained by following the proof of an analogous result for von Neumann–Bernays–Gödel set theory in an earlier work by Sato, with some (...) minor modifications. (shrink)

To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by Bernardi-Montagna in [5]. With that interpretation in mind, a system LR of modal propositional logic is axiomatized, a modal completeness theorem is established for LR and, after that, a uniform arithmetical (Solovay-type) completeness theorem with respect to PA is obtained for LR.

Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.

An algebraic proof is presented for the finite strong standard completeness of the Involutive Uninorm Logic with Fixed Point ($${{\mathbf {IUL}}^{fp}}$$ IUL fp ). It may provide a first step towards settling the standard completeness problem for the Involutive Uninorm Logic ($${\mathbf {IUL}}$$ IUL, posed in G. Metcalfe, F. Montagna. (J Symb Log 72:834–864, 2007)) in an algebraic manner. The result is proved via an embedding theorem which is based on the structural description of the class of odd (...) involutive FL$$_e$$ e -chains which have finitely many positive idempotent elements. (shrink)

This paper investigates the stochastically exponential stability of reaction-diffusion impulsive stochastic cellular neural networks. The reaction-diffusion pulse stochastic system model characterizes the complexity of practical engineering and brings about mathematical difficulties, too. However, the difficulties have been overcome by constructing a new contraction mapping and an appropriate distance on a product space which is guaranteed to be a complete space. This is the first time to employ the fixed point theorem to derive the stability criterion of reaction-diffusion impulsive (...) stochastic CNN with distributed time delays. Finally, an example is provided to illustrate the effectiveness of the proposed methods. (shrink)

Here, I first prove that certain families of k-valued clones have the Gupta-Belnap fixed-point property. This essentially means that all propositional languages that are interpreted with operators belonging to those clones are such that any net of self-referential sentences in the language can be consistently evaluated. I then focus on two four-valued generalisations of the Kleene propositional operators that generalise the strong and weak Kleene operators: Belnap’s clone and Fitting’s clone, respectively. I apply the theorems from the (...) initial part of the paper to analyse the fixed-point property of Belnap’s and Fitting’s clones when some special operators that reflect the semantics are added. The conclusion of the paper is that Fitting’s clone is better suited than Belnap’s to provide self-referential languages with highly expressive resources. (shrink)

This paper studies a propositional logic which is obtained by interpreting implication as formal provability. It is also the logic of finite irreflexive Kripke Models.A Kripke Model completeness theorem is given and several completeness theorems for interpretations into Provability Logic and Peano Arithmetic.

Given a simple non-trivial finite-dimensional Lie algebra L, fields $K_i$ and Chevalley groups $L(K_i)$ , we first prove that $\Pi_{\mathcal{U}} L(K_i)$ is isomorphic to $L(\Pi_{\mathcal{U}}K_i)$ . Then we consider the case of Chevalley groups of twisted type ${}^n\!L$ . We obtain a result analogous to the previous one. Given perfect fields $K_i$ having the property that any element is either a square or the opposite of a square and Chevalley groups ${}^n\!L(K_i)$ , then $\pu{}^n\!L(K_i)$ is isomorphic to ${}^n\!L(\pu K_i)$ . (...) We apply our results to prove the decidability of the set of sentences true in almost all finite groups of the form L(K) where K is a finite field and L a fixed untwisted Chevalley type. (shrink)

This paper introduces Agreement Theorems to dynamic-epistemic logic. We show first that common belief of posteriors is sufficient for agreement in epistemic-plausibility models, under common and well-founded priors. We do not restrict ourselves to the finite case, showing that in countable structures the results hold if and only if the underlying plausibility ordering is well-founded. We then show that neither well-foundedness nor common priors are expressible in the language commonly used to describe and reason about epistemic-plausibility models. The static (...) agreement result is, however, finitely derivable in an extended modal logic. We provide the full derivation. We finally consider dynamic agreement results. We show they have a counterpart in epistemic-plausibility models, and provide a new form of agreements via public announcements. (shrink)

We consider the reduct to the module language of certain theories of fields with a non surjective endomorphism. We show in some cases the existence of a model companion. We apply our results for axiomatizing the reduct to the theory of modules of non principal ultraproducts of separably closed fields of fixed but non zero imperfection degree.

We consider first-order theories of topological fields admitting a model-completion and their expansion to differential fields . We give a criterion under which the expansion still admits a model-completion which we axiomatize. It generalizes previous results due to M. Singer for ordered differential fields and of C. Michaux for valued differential fields. As a corollary, we show a transfer result for the NIP property. We also give a geometrical axiomatization of that model-completion. Then, for certain differential valued fields, we extend (...) the positive answer of Hilbert’s seventeenth problem and we prove an Ax–Kochen–Ershov theorem. Similarly, we consider first-order theories of topological fields admitting a model-companion and their expansion to differential fields, and under a similar criterion as before, we show that the expansion still admits a model-companion. This last result can be compared with those of M. Tressl: on one hand we are only dealing with a single derivation whereas he is dealing with several, on the other hand we are not restricting ourselves to definable expansions of the ring language, taking advantage of our topological context. We apply our results to fields endowed with several valuations. (shrink)

This Element takes a deep dive into Gödel's 1931 paper giving the first presentation of the Incompleteness Theorems, opening up completely passages in it that might possibly puzzle the student, such as the mysterious footnote 48a. It considers the main ingredients of Gödel's proof: arithmetization, strong representability, and the Fixed Point Theorem in a layered fashion, returning to their various aspects: semantic, syntactic, computational, philosophical and mathematical, as the topic arises. It samples some of the most important (...) proofs of the Incompleteness Theorems, e.g. due to Kuratowski, Smullyan and Robinson, as well as newer proofs, also of other independent statements, due to H. Friedman, Weiermann and Paris-Harrington. It examines the question whether the incompleteness of e.g. Peano Arithmetic gives immediately the undecidability of the Entscheidungsproblem, as Kripke has recently argued. It considers set-theoretical incompleteness, and finally considers some of the philosophical consequences considered in the literature. (shrink)