Kreisel’s conjecture is the statement: if, for all $n\in \mathbb {N}$ , $\mathop {\text {PA}} \nolimits \vdash _{k \text { steps}} \varphi (\overline {n})$ , then $\mathop {\text {PA}} \nolimits \vdash \forall x.\varphi (x)$ . For a theory of arithmetic T, given a recursive function h, $T \vdash _{\leq h} \varphi $ holds if there is a proof of $\varphi $ in T whose code is at most $h(\#\varphi )$ . This notion depends on the underlying coding. ${P}^h_T(x)$ is a predicate for $\vdash _{\leq h}$ in T. It is shown that there exist a sentence $\varphi $ and a total recursive function h such that $T\vdash _{\leq h}\mathop {\text {Pr}} \nolimits _T(\ulcorner \mathop {\text {Pr}} \nolimits _T(\ulcorner \varphi \urcorner )\rightarrow \varphi \urcorner )$ , but , where $\mathop {\text {Pr}} \nolimits _T$ stands for the standard provability predicate in T. This statement is related to a conjecture by Montagna. Also variants and weakenings of Kreisel’s conjecture are studied. By the use of reflexion principles, one can obtain a theory $T^h_\Gamma $ that extends T such that a version of Kreisel’s conjecture holds: given a recursive function h and $\varphi (x)$ a $\Gamma $ -formula (where $\Gamma $ is an arbitrarily fixed class of formulas) such that, for all $n\in \mathbb {N}$ , $T\vdash _{\leq h} \varphi (\overline {n})$ , then $T^h_\Gamma \vdash \forall x.\varphi (x)$ . Derivability conditions are studied for a theory to satisfy the following implication: if , then $T\vdash \forall x.\varphi (x)$ . This corresponds to an arithmetization of Kreisel’s conjecture. It is shown that, for certain theories, there exists a function h such that $\vdash _{k \text { steps}}\ \subseteq\ \vdash _{\leq h}$ .

The symmetries between points and lines in planar projective geometry and between points and planes in solid projective geometry are striking features of these geometries that were extensively discussed during the nineteenth century under the labels “duality” or “reciprocity.” The aims of this article are, first, to provide a systematic analysis of duality from a modern point of view, and, second, based on this, to give a historical overview of how discussions about duality evolved during the nineteenth century. Specifically, we want to see in which ways geometers’ preoccupation with duality was shaped by developments that lead to modern logic towards the end of the nineteenth century, and how these developments in turn might have been influenced by reflections on duality.

We ask, when is a property of a model a logical property? According to the so-called Tarski–Sher criterion this is the case when the property is preserved by isomorphisms. We relate this to model-theoretic characteristics of abstract logics in which the model class is definable. This results in a graded concept of logicality in the terminology of Sagi [46]. We investigate which characteristics of logics, such as variants of the Löwenheim–Skolem theorem, Completeness theorem, and absoluteness, are relevant from the logicality point of view, continuing earlier work by Bonnay, Feferman, and Sagi. We suggest that a logic is the more logical the closer it is to first order logic. We also offer a refinement of the result of McGee that logical properties of models can be expressed in $L_{\infty \infty }$ if the expression is allowed to depend on the cardinality of the model, based on replacing $L_{\infty \infty }$ by a “tamer” logic.

This is a short expository account of the regularity lemma for stable graphs proved by the authors, with some comments on the model theoretic context, written for a general logical audience.

Ackermann’s function can be expressed using an iterative algorithm, which essentially takes the form of a term rewriting system. Although the termination of this algorithm is far from obvious, its equivalence to the traditional recursive formulation—and therefore its totality—has a simple proof in Isabelle/HOL. This is a small example of formalising mathematics using a proof assistant, with a focus on the treatment of difficult recursions.

The following bare-bones story introduces the idea of a cumulative hierarchy of pure sets: ‘Sets are arranged in stages. Every set is found at some stage. At any stage S: for any sets found before S, we find a set whose members are exactly those sets. We find nothing else at S’. Surprisingly, this story already guarantees that the sets are arranged in well-ordered levels, and suffices for quasi-categoricity. I show this by presenting Level Theory, a simplification of set theories due to Scott, Montague, Derrick, and Potter.

Potentialists think that the concept of set is importantly modal. Using tensed language as a heuristic, the following bare-bones story introduces the idea of a potential hierarchy of sets: ‘Always: for any sets that existed, there is a set whose members are exactly those sets; there are no other sets’. Surprisingly, this story already guarantees well-foundedness and persistence. Moreover, if we assume that time is linear, the ensuing modal set theory is almost definitionally equivalent with non-modal set theories; specifically, with Level Theory, as developed in Part 1.

This paper was read by Michael Dummett at Leiden University on September 26, 1992 at the invitation by Göran Sundholm to address the topic mentioned in the title. Dummett’s lecture was part of a workshop, Meaning Theory and Intuitionism, with 12 invited speakers over three days. After the workshop, Dummett gave a copy of the manuscript to Sundholm together with permission to publish it. At the time, nothing came of the publication plans, nor did Dummett publish it in any other form. The text has remained virtually unknown, and apart from a lecture of Per Martin-Löf, also at Leiden, on the same topic (published in this journal), it has received no scholarly attention. We are indebted to Dummett’s literary executor, Professor Ian Rumfitt, of All Souls College, Oxford, who after nearly three decades confirmed the earlier permission to publish.

Göran Sundholm

Ansten Klev

This lecture was given by Per Martin-Löf at Leiden University on August 25, 2001 at the invitation by Göran Sundholm to address the topic mentioned in the title and to reflect on Dummett’s earlier effort of almost a decade before (published in this journal). The lecture was part of a three-day conference on Gottlob Frege. Sundholm arranged for the lecture to be recorded and commissioned Bjørn Jespersen to make a transcript. The information in footnote 1, which Sundholm provided, has been independently confirmed by Thomas Ricketts in an email to the author. The present version has been edited by Ansten Klev. Following the displayed text (Int-id) there is a lacuna in the original transcript corresponding to a pause in the recording when the tape was changed. The continuous text of the present version is the result of a few additions to the original transcript suggested by Klev and agreed to by the author.

We prove that the category of Nachbin’s compact ordered spaces and order-preserving continuous maps between them is dually equivalent to a variety of algebras, with operations of at most countable arity. Furthermore, we observe that the countable bound on the arity is the best possible: the category of compact ordered spaces is not dually equivalent to any variety of finitary algebras. Indeed, the following stronger results hold: the category of compact ordered spaces is not dually equivalent to (i) any finitely accessible category, (ii) any first-order definable class of structures, and (iii) any class of finitary algebras closed under products and subalgebras. An explicit equational axiomatisation of the dual of the category of compact ordered spaces is obtained; in fact, we provide a finite one, meaning that our description uses only finitely many function symbols and finitely many equational axioms. In preparation for the latter result, we establish a generalisation of a celebrated theorem by Mundici: our result—whose proof is independent of Mundici’s theorem—asserts that the category of unital commutative distributive lattice-ordered monoids is equivalent to the category of what we call MV-monoidal algebras.

Abstract taken directly from the thesis.

E-mail: [email protected]

URL: https://air.unimi.it/retrieve/handle/2434/812809/1698986/phd_unimi_R11882.pdf

We describe an organizing framework for the study of infinitary combinatorics. This framework is Čech cohomology. It describes ZFC principles distinguishing among the ordinals of the form $\omega _n$ . More precisely, this framework correlates each $\omega _n$ with an $(n+1)$ -dimensional generalization of Todorcevic’s walks technique, and begins to account for that technique’s “unreasonable effectiveness” on $\omega _1$ .

We show in contrast that on higher cardinals $\kappa $ , the existence of these principles is frequently independent of the ZFC axioms. Finally, we detail implications of these phenomena for the computation of strong homology groups and higher derived limits, deriving independence results in algebraic topology and homological algebra, respectively, in the process.

Abstract prepared by Jeffrey Bergfalk.

E-mail: [email protected]

In this work we present some new contributions towards two different directions in the study of modal logic. First we employ tense logics to provide a temporal interpretation of intuitionistic quantifiers as “always in the future” and “sometime in the past.” This is achieved by modifying the Gödel translation and resolves an asymmetry between the standard interpretation of intuitionistic quantifiers.

Then we generalize the classic Gelfand–Naimark–Stone duality between compact Hausdorff spaces and uniformly complete bounded archimedean $\ell $ -algebras to a duality encompassing compact Hausdorff spaces with continuous relations. This leads to the notion of modal operators on bounded archimedean $\ell $ -algebras and in particular on rings of continuous real-valued functions on compact Hausdorff spaces. This new duality is also a generalization of the classic Jónsson-Tarski duality in modal logic.

Abstract taken directly from the thesis.

E-mail: [email protected]

URL: https://www.proquest.com/openview/5d284dbfb954383da9364149fa312b6f/1?pq-origsite=gscholar&cbl=18750&diss=y

This thesis is at the intersection of dynamics, probability and model theory. It focuses on a specialization of the notion of amenability: unique ergodicity.

Let G be a Polish group, i.e., a topological group whose topology is separable and completely metrizable. We call a G-flow the action of G on a compact space. A G-flow is said to be minimal if every orbit is dense.

A famous theorem of Ellis states that any Polish group G admits a unique universal minimal flow that we denote ${\mathrm {M}}(G)$ . This means that for any minimal G-flow X there is a surjective G-map from ${\mathrm {M}}(G)$ to X. G is said to be amenable if every G-flow admits an invariant probability measure, and uniquely ergodic if every minimal flow admits a unique invariant probability measure.

The notion of unique ergodicity relating to a group was introduced by Angel, Kechris and Lyons. They also ask the following question which is the main focus of the thesis: Let G be an amenable Polish group with metrizable universal minimal flow, is G uniquely ergodic?

Note that unique ergodicity is an interesting notion only for relatively large groups, as it is proved in the last chapter of this thesis that locally compact non compact Polish groups are never uniquely ergodic. This result is joint work with Andy Zucker.

The thesis includes proofs of unique ergodicity of groups with interesting universal minimal flows, namely the automorphism group of the semigeneric directed graph and the automorphism group of the $2$ -graph.

It also includes a theorem stating that under some hypothesis on a $\omega $ -categorical structure M, the logic action of ${\mathrm {Aut}}(M)$ on ${\mathrm {LO}}(M)$ , the compact space of linear orders on M, is uniquely ergodic. This implies unique ergodicity for the group if its universal minimal flow happens to be the space of linear orderings. It can also be used to prove non-amenability of some groups for which the action of ${\mathrm {Aut}}(M)$ on ${\mathrm {LO}}(M)$ is not minimal. This result is joint work with Todor Tsankov.

Finally, the thesis also presents a proof that under the assumption that the universal minimal flows involved are metrizable, unique ergodicity is stable under group extensions. This result is joint work with Andy Zucker.

Abstract prepared by Colin Jahel.

E-mail: [email protected]

URL: http://math.univ-lyon1.fr/~jahel/doc/These.pdf

Given a finite lattice L that can be embedded in the recursively enumerable (r.e.) Turing degrees $\langle \mathcal {R}_{\mathrm {T}},\leq _{\mathrm {T}}\rangle $ , we do not in general know how to characterize the degrees $\mathbf {d}\in \mathcal {R}_{\mathrm {T}}$ below which L can be bounded. The important characterizations known are of the $L_7$ and $M_3$ lattices, where the lattices are bounded below $\mathbf {d}$ if and only if $\mathbf {d}$ contains sets of “fickleness” $>\omega $ and $\geq \omega ^\omega $ respectively. We work towards finding a lattice that characterizes the levels above $\omega ^2$ , the first non-trivial level after $\omega $ . We introduced a lattice-theoretic property called “ $3$ -directness” to describe lattices that are no “wider” or “taller” than $L_7$ and $M_3$ . We exhaust the 3-direct lattices L, but they turn out to also characterize the $>\omega $ or $\geq \omega ^\omega $ levels, if L is not already embeddable below all non-zero r.e. degrees. We also considered upper semilattices (USLs) by removing the bottom meet(s) of some 3-direct lattices, but the removals did not change the levels characterized. This leads us to conjecture that a USL characterizes the same r.e. degrees as the lattice on which the USL is based. We discovered three 3-direct lattices besides $M_3$ that also characterize the $\geq \omega ^\omega $ -levels. Our search for a $>\omega ^2$ -candidate therefore involves the lattice-theoretic problem of finding lattices that do not contain any of the four $\geq \omega ^\omega $ -lattices as sublattices.

Abstract prepared by Liling Ko.

E-mail: [email protected]

URL: http://sites.nd.edu/liling-ko/

An exponential $\exp $ on an ordered field $(K,+,-,\cdot ,0,1,<)$ is an order-preserving isomorphism from the ordered additive group $(K,+,0,<)$ to the ordered multiplicative group of positive elements $(K^{>0},\cdot ,1,<)$ . The structure $(K,+,-,\cdot ,0,1,<,\exp )$ is then called an ordered exponential field (cf. [6]). A linearly ordered structure $(M,<,\ldots )$ is called o-minimal if every parametrically definable subset of M is a finite union of points and open intervals of M.

The main subject of this thesis is the algebraic and model theoretic examination of o-minimal exponential fields $(K,+,-,\cdot ,0,1,<,\exp )$ whose exponential satisfies the differential equation $\exp ' = \exp $ with initial condition $\exp (0) = 1$ . This study is mainly motivated by the Transfer Conjecture, which states as follows:

Any o-minimal exponential field $(K,+,-,\cdot ,0,1,<,\exp )$ whose exponential satisfies the differential equation $\exp ' = \exp $ with initial condition $\exp (0)=1$ is elementarily equivalent to $\mathbb {R}_{\exp }$ .

Here, $\mathbb {R}_{\exp }$ denotes the real exponential field $(\mathbb {R},+,-,\cdot ,0,1,<,\exp )$ , where $\exp $ denotes the standard exponential $x \mapsto \mathrm {e}^x$ on $\mathbb {R}$ . Moreover, elementary equivalence means that any first-order sentence in the language $\mathcal {L}_{\exp } = \{+,-,\cdot ,0,1, <,\exp \}$ holds for $(K,+,-,\cdot ,0,1,<,\exp )$ if and only if it holds for $\mathbb {R}_{\exp }$ .

The Transfer Conjecture, and thus the study of o-minimal exponential fields, is of particular interest in the light of the decidability of $\mathbb {R}_{\exp }$ . To the date, it is not known if $\mathbb {R}_{\exp }$ is decidable, i.e., whether there exists a procedure determining for a given first-order $\mathcal {L}_{\exp }$ -sentence whether it is true or false in $\mathbb {R}_{\exp }$ . However, under the assumption of Schanuel’s Conjecture—a famous open conjecture from Transcendental Number Theory—a decision procedure for $\mathbb {R}_{\exp }$ exists (cf. [7]). Also a positive answer to the Transfer Conjecture would result in the decidability of $\mathbb {R}_{\exp }$ (cf. [1]). Thus, we study o-minimal exponential fields with regard to the Transfer Conjecture, Schanuel’s Conjecture, and the decidability question of $\mathbb {R}_{\exp }$ .

Overall, we shed light on the valuation theoretic invariants of o-minimal exponential fields—the residue field and the value group—with additional induced structure. Moreover, we explore elementary substructures and extensions of o-minimal exponential fields to the maximal ends—the smallest elementary substructures being prime models and the maximal elementary extensions being contained in the surreal numbers. Further, we draw connections to models of Peano Arithmetic, integer parts, density in real closure, definable Henselian valuations, and strongly NIP ordered fields.

Parts of this thesis were published in [2–5].

Abstract prepared by Lothar Sebastian Krapp

E-mail: [email protected]

URL: https://d-nb.info/1202012558/34

This thesis aims to develop a domain-independent system for repairing faulty Datalog-like theories by combining three existing techniques: abduction, belief revision, and conceptual change. Accordingly, the proposed system is named the ABC repair system (ABC). Given an observed assertion and a current theory, abduction adds axioms, which explain that observation by making the corresponding assertion derivable from the expanded theory. Belief revision incorporates a new piece of information which conflicts with the input theory by deleting old axioms. Conceptual change uses the reformation algorithm for blocking unwanted proofs or unblocking wanted proofs. The former two techniques change an axiom as a whole, while reformation changes the language in which the theory is written. These three techniques are complementary. But they have not previously been combined into one system. We are working on aligning these three techniques in ABC, which is capable of repairing logical theories with better result than each individual technique alone. In addition, ABC extends abduction and belief revision to operate on preconditions: the former deletes preconditions from rules, and the latter adds preconditions to rules. Datalog is used as the underlying logic of theories in this thesis, but the proposed system has the potential to be adapted to theories in other logics.

Abstract prepared by Xue Li by taking directly from the thesis.

E-mail: [email protected]

The dissertation introduces new sequent-calculi for free first- and second-order logic, and a hyper-sequent calculus for modal logics K, D, T, B, S4, and S5; to attain the calculi for the stronger modal logics, only external structural rules need to be added to the calculus for K, while operational and internal structural rules remain the same. Completeness and cut-elimination are proved for all calculi presented.

Philosophically, the dissertation develops an inferentialist, or proof-theoretic, theory of meaning. It takes as a starting point that the sense of a sentence is determined by the rules governing its use. In particular, there are two features of the use of a sentence that jointly determine its sense, the conditions under which it is coherent to assert that sentence and the conditions under which it is coherent to deny that sentence. The dissertation develops a theory of quantification as marking coherent ways a language can be expanded and modality as the means by which we can reflect on the norms governing the assertion and denial conditions of our language. If the view of quantification that is argued for is correct, then there is no tension between second-order quantification and nominalism. In particular, the ontological commitments one can incur through the use of a quantifier depend wholly on the ontological commitments one can incur through the use of atomic sentences. The dissertation concludes by applying the developed theory of meaning to the metaphysical issue of necessitism and contingentism. Two objections to a logic of contingentism are raised and addressed. The resulting logic is shown to meet all the requirement that the dissertation lays out for a theory of meaning for quantifiers and modal operators.

Abstract prepared by Andrew Parisi

E-mail: [email protected]

URL: https://opencommons.uconn.edu/dissertations/1480/

We devise imperative programming languages for verified real number computation where real numbers are provided as abstract data types such that the users of the languages can express real number computation by considering real numbers as abstract mathematical entities. Unlike other common approaches toward real number computation, based on an algebraic model that lacks implementability or transcendental computation, or finite-precision approximation such as using double precision computation that lacks a formal foundation, our languages are devised based on computable analysis, a foundation of rigorous computation over continuous data. Consequently, the users of the language can easily program real number computation and reason about the behaviours of their programs, relying on their mathematical knowledge of real numbers without worrying about artificial roundoff errors. As the languages are imperative, we adopt precondition–postcondition-style program specification and Hoare-style program verification methodologies. Consequently, the users of the language can easily program a computation over real numbers, specify the expected behaviour of the program, including termination, and prove the correctness of the specification. Furthermore, we suggest extending the languages with other interesting continuous data, such as matrices, continuous real functions, et cetera.

Abstract taken directly from the thesis.

E-mail: [email protected]

URL: https://sewonpark.com/thesis