We give a survey of current research on Gödel’s incompleteness theorems from the following three aspects: classifications of different proofs of Gödel’s incompleteness theorems, the limit of the applicability of Gödel’s first incompleteness theorem, and the limit of the applicability of Gödel’s second incompleteness theorem.

Following our [6], though with somewhat different methods here, further variants of Goodstein sequences are introduced in terms of parameterized Ackermann–Péter functions. Each of the sequences is shown to terminate, and the proof-theoretic strengths of these facts are calibrated by means of ordinal assignments, yielding independence results for a range of theories: PRA, PA, $\Sigma ^1_1$ -DC $_0$ , ATR $_0$ , up to ID $_1$ . The key is the so-called “Hardy hierarchy” of proof-theoretic bounding finctions, providing a uniform method for associating Goodstein-type sequences with parameterized normal form representations of positive integers.

We prove that the modal logic of a crowded locally compact generalized ordered space is $\textsf {S4}$ . This provides a version of the McKinsey–Tarski theorem for generalized ordered spaces. We then utilize this theorem to axiomatize the modal logic of an arbitrary locally compact generalized ordered space.

The present thesis lies at the interface of logic and linguistics; its object of study are control sentences with overt pronouns in Romance languages (European and Brazilian Portuguese, Italian and Spanish). This is a topic that has received considerably more attention on the part of linguists, especially in recent years, than from logicians. Perhaps for this reason, much remains to be understood about these linguistic structures and their underlying logical properties. This thesis seeks to fill the lacunas in the literature or at least take steps in this direction by way of addressing a number of issues that have so far been under-explored. To this end, we put forward two key questions, one linguistic and the other logical. These are, respectively, (1) What is the syntactic status of the surface pronoun? and (2) What are the available mechanisms to reuse semantic resources in a contraction-free logical grammar? Accordingly, the thesis is divided into two parts: generative linguistics and categorial grammar. Part I starts by reviewing the recent discussion within the generative literature on infinitive clauses with overt subjects, paying detailed attention to the main accounts in the field. Part II does the same on the logical grammar front, addressing in particular the issues of control and of anaphoric pronouns. Ultimately, the leading accounts from both camps will be found wanting. The closing chapter of each of Part I and Part II will thus put forward alternative candidates, that we contend are more successful than their predecessors. More specifically, in Part I, we offer a linguistic account along the lines of Landau’s T/Agr theory of control. In Part II, we present two alternative categorial accounts: one based on Combinatory Categorial Grammar, the other on Type-Logical Grammar. Each of these accounts offers an improved, more fine-grained perspective on control infinitives featuring overt pronominal subjects. Finally, we include an Appendix in which our type-logical proposal is implemented in a categorial parser/theorem-prover.

Abstract prepared by María Inés Corbalán.

E-mail: [email protected]

URL: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331697

The purpose of this thesis is to develop a paraconsistent Model Theory. The basis for such a theory was launched by Walter Carnielli, Marcelo Esteban Coniglio, Rodrigo Podiack, and Tarcísio Rodrigues in the article ‘On the Way to a Wider Model Theory: Completeness Theorems for First-Order Logics of Formal Inconsistency’ [The Review of Symbolic Logic, vol. 7 (2014)].

Naturally, a complete theory cannot be fully developed in a single work. Indeed, the goal of this work is to show that a paraconsistent Model Theory is a sound and worthy possibility. The pursuit of this goal is divided in three tasks: The first one is to give the theory a philosophical meaning. The second one is to transpose as many results from the classical theory to the new one as possible. The third one is to show an application of the theory to practical science.

The response to the first task is a Paraconsistent Reasoning System. The start point is that paraconsistency is an epistemological concept. The pursuit of a deeper understanding of the phenomenon of paraconsistency from this point of view leads to a reasoning system based on the Logics of Formal Inconsistency. Models are regarded as states of knowledge and the concept of isomorphism is reformulated so as to give raise to a new concept that preserves a portion of the whole knowledge of each state. Based on this, a notion of refinement is created which may occur from inside or from outside the state.

In order to respond to the second task, two important classical results, namely the Omitting Types Theorem and Craig’s Interpolation Theorem are shown to hold in the new system and it is also shown that, if classical results in general are to hold in a paraconsistent system, then such a system should be in essence how it was developed here.

Finally, the response to the third task is a proposal of what a Paraconsistent Logic Programming may be. For that, the basis for a paraconsistent PROLOG is settled in the light of the ideas developed so far.

Abstract prepared by Bruno Costa Coscarelli.

E-mail: [email protected]

URL: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331697

This thesis is concerned with the expansions of algebraic structures and their fit in Shelah’s classification landscape.

The first part deals with the expansion of a theory by a random predicate for a substructure model of a reduct of the theory. Let T be a theory in a language $\mathcal {L}$ . Let $T_0$ be a reduct of T. Let $\mathcal {L}_S = \mathcal {L}\cup \{S\}$ , for S a new unary predicate symbol, and $T_S$ be the $\mathcal {L}_S$ -theory that axiomatises the following structures: $(\mathscr {M},\mathscr {M}_0)$ consist of a model $\mathscr {M}$ of T and S is a predicate for a model $\mathscr {M}_0$ of $T_0$ which is a substructure of $\mathscr {M}$ . We present a setting for the existence of a model-companion $TS$ of $T_S$ . As a consequence, we obtain the existence of the model-companion of the following theories, for $p>0$ a prime number:

• • $\mathrm {ACF}_p$ , $\mathrm {SCF}_{e,p}$ , $\mathrm {Psf}_p$ , $\mathrm {ACFA}_p$ , $\mathrm {ACVF}_{p,p}$ in appropriate languages expanded by arbitrarily many predicates for additive subgroups;

• • $\mathrm {ACF}_p$ , $\mathrm {ACF}_0$ in the language of rings expanded by a single predicate for a multiplicative subgroup;

• • $\mathrm {PAC}_p$ -fields, in an appropriate language expanded by arbitrarily many predicates for additive subgroups.

$TS$

$TS$

$TS$

$\mathrm {NSOP}_{1}$

Configuration $T_0\subseteq T$	Generic expansion $TS$
$T_0 = T$	Preserves stability
$T_0\subseteq T$	Preserves $\mathrm {NSOP}_{1}$
$T_0 = \emptyset $	Preserves simplicity

In particular, this construction produces new examples of $\mathrm {NSOP}_{1}$ not simple theories, and we study in depth a particular example: the expansion of an algebraically closed field of positive characteristic by a generic additive subgroup. We give a full description of imaginaries, forking, and Kim-forking in this example.

The second part studies expansions of the group of integers by p-adic valuations. We prove quantifier elimination in a natural language and compute the dp-rank of these expansions: it equals the number of independent p-adic valuations considered. Thus, the expansion of the integers by one p-adic valuation is a new dp-minimal expansion of the group of integers. Finally, we prove that the latter expansion does not admit intermediate structures: any definable set in the expansion is either definable in the group structure or is able to “reconstruct” the valuation using only the group operation.

Abstract prepared by Christian d’Elbée.

E-mail: [email protected]

URL: https://choum.net/~chris/page_perso

Necessitism, Contingentism, and Theory Equivalence is a dissertation on issues in higher-order modal metaphysics. Consider a modal higher-order language with identity in which the universal quantifier is interpreted as expressing (unrestricted) universal quantification and the necessity operator is interpreted as expressing metaphysical necessity. The main question addressed in the dissertation concerns the correct theory formulated in this language. A different question that also takes centre stage in the dissertation is what it takes for theories to be equivalent.

The whole dissertation consists of an extended argument in defence of the (joint) truth of two seemingly inconsistent higher-order modal theories, specifically:

1. 1. Plantingan Moderate Contingentism, a theory based on Plantinga’s [1] modal metaphysics that is committed to, among other things, the contingent being of some individuals and the necessary being of all possible higher-order entities;

2. 2. Williamsonian Thorough Necessitism, a theory advocated by Williamson [3] which is committed to, among other things, the necessary being of every possible individual as well as of every possible higher-order entity.

Part of the case for these theories’ joint truth relies on defences of the following metaphysical theses: (i) Thorough Serious Actualism, the thesis that no things could have been related while being nothing, and (ii) Higher-Order Necessitism, the thesis that necessarily, every higher-order entity is necessarily something. It is shown that Thorough Serious Actualism and Higher-Order Necessitism are both implicit commitments of very weak logical theories. The defence of Higher-Order Necessitism constitutes a powerful challenge to Stalnaker’s [2] Thorough Contingentism, a theory committed to, among other things, the view that there could have been some individuals as well as some entities of any higher-order that could have been nothing.

In the dissertation it is argued that Plantingan Moderate Contingentism and Williamsonian Thorough Necessitism are in fact equivalent, even if they appear to be jointly inconsistent. The case for this claim relies on the Synonymy account, a novel account of theory equivalence developed and defended in the dissertation. According to this account, theories are equivalent just in case they have the same commitments and conception of logical space.

By way of defending the Synonymy account’s adequacy, the account is applied to the debate between noneists, proponents of the view that some things do not exist, and Quineans, proponents of the view that to exist just is to be some thing. The Synonymy account is shown to afford a more nuanced and better understanding of that debate by revealing that what noneists and Quineans are really disagreeing about is what expressive resources are available to appropriately describe the world.

By coupling a metatheoretical result with tools from the philosophy of language, it is argued that Plantingan Moderate Contingentism and Williamsonian Thorough Necessitism are synonymous theories, and so, by the lights of the Synonymy account, equivalent. Given the defence of their extant commitments made in the dissertation, it is concluded that Plantingan Moderate Contingentism and Williamsonian Thorough Necessitism are both correct. A corollary of this result is that the dispute between Plantingans and Williamsonians is, in an important sense, merely verbal. For if two theories are equivalent, then they “require the same of the world for their truth.”

Thus, the results of the dissertation reveal that if one speaks as a Plantingan while advocating Plantingan Moderate Contingentism, or as a Williamsonian while advocating Williamsonian Thorough Necessitism, then one will not go wrong. Notwithstanding, one will still go wrong if one speaks as a Plantingan while advocating Williamsonian Thorough Necessitism, or as a Williamsonian while advocating Plantingan Moderate Contingentism.

On the basis of a conception of the individual constants and predicates of second-order modal languages as strongly Millian, i.e., as having actually existing entities as their semantic values, in the appendix are presented second-order modal logics consistent with Stalnaker’s Thorough Contingentism. Furthermore, it is shown there that these logics are strong enough for applications of higher-order modal logic in mathematics, a result that constitutes a reply to an argument to the contrary by Williamson [3]. Finally, these logics are proven to be complete relative to particular “thoroughly contingentist” classes of models.

This dissertation is highly motivated by d.r.e. Nondensity Theorem, which is interesting in two perspectives. One is that it contrasts Sacks Density Theorem, and hence shows that the structures of r.e. degrees and d.r.e. degrees are different. The other is to investigate what other properties a maximal degree can have.

In Chapter 1, we briefly review the backgrounds of Recursion Theory which motivate the topics of this dissertation.

In Chapter 2, we introduce the notion of $(m,n)$ -cupping degree. It is closely related to the notion of maximal d.r.e. degree. In fact, a $(2,2)$ -cupping degree is maximal d.r.e. degree. We then prove that there exists an isolated $(2,\omega )$ -cupping degree by combining strategies for maximality and isolation with some efforts.

Chapter 3 is part of a joint project with Steffen Lempp, Yiqun Liu, Keng Meng Ng, Cheng Peng, and Guohua Wu. In this chapter, we prove that any finite boolean algebra can be embedded into d.r.e. degrees as a final segment. We examine the proof of d.r.e. Nondensity Theorem and make developments to the technique to make it work for our theorem. The goal of the project is to see what lattice can be embedded into d.r.e. degrees as a final segment, as we observe that the technique has potential be developed further to produce other interesting results.

Abstract prepared by Yong Liu.

E-mail: [email protected]

Martin’s conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states that every function which is above the identity is eventually equal to a transfinite iterate of the jump. If true, it would provide an explanation for the unique role of the Turing jump in computability theory and rule out many types of constructions on the Turing degrees.

In this thesis, we will introduce a few tools which we use to prove several cases of Martin’s conjecture. It turns out that both these tools and these results on Martin’s conjecture have some interesting consequences both for Martin’s conjecture and for a few related topics.

The main tool that we introduce is a basis theorem for perfect sets, improving a theorem due to Groszek and Slaman. We also introduce a general framework for proving certain special cases of Martin’s conjecture which unifies a few pre-existing proofs. We will use these tools to prove three main results about Martin’s conjecture: that it holds for regressive functions on the hyperarithmetic degrees (answering a question of Slaman and Steel), that part 1 holds for order preserving functions on the Turing degrees, and that part 1 holds for a class of functions that we introduce, called measure preserving functions.

This last result has several interesting consequences for the study of Martin’s conjecture. In particular, it shows that part 1 of Martin’s conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. This suggests several possible strategies for working on part 1 of Martin’s conjecture, which we will discuss.

The basis theorem that we use to prove these results also has some applications outside of Martin’s conjecture. We will use it to prove a few theorems related to Sacks’ question about whether it is provable in $\mathsf {ZFC}$ that every locally countable partial order of size continuum embeds into the Turing degrees. We will show that in a certain extension of $\mathsf {ZF}$ (which is incompatible with $\mathsf {ZFC}$ ), this holds for all partial orders of height two, but not for all partial orders of height three. Our proof also yields an analogous result for Borel partial orders and Borel embeddings in $\mathsf {ZF}$ , which shows that the Borel version of Sacks’ question has a negative answer.

We will end the thesis with a list of open questions related to Martin’s conjecture, which we hope will stimulate further research.

Abstract prepared by Patrick Lutz.

E-mail: [email protected]

There are many computational problems which are generally “easy” to solve but have certain rare examples which are much more difficult to solve. One approach to studying these problems is to ignore the difficult edge cases. Asymptotic computability is one of the formal tools that uses this approach to study these problems. Asymptotically computable sets can be thought of as almost computable sets, however every set is computationally equivalent to an almost computable set. Intrinsic density was introduced as a way to get around this unsettling fact, and which will be our main focus.

Of particular interest for the first half of this dissertation are the intrinsically small sets, the sets of intrinsic density $0$ . While the bulk of the existing work concerning intrinsic density was focused on these sets, there were still many questions left unanswered. The first half of this dissertation answers some of these questions. We proved some useful closure properties for the intrinsically small sets and applied them to prove separations for the intrinsic variants of asymptotic computability. We also completely separated hyperimmunity and intrinsic smallness in the Turing degrees and resolved some open questions regarding the relativization of intrinsic density.

For the second half of this dissertation, we turned our attention to the study of intermediate intrinsic density. We developed a calculus using noncomputable coding operations to construct examples of sets with intermediate intrinsic density. For almost all $r\in (0,1)$ , this construction yielded the first known example of a set with intrinsic density r which cannot compute a set random with respect to the r-Bernoulli measure. Motivated by the fact that intrinsic density coincides with the notion of injection stochasticity, we applied these techniques to study the structure of the more well-known notion of MWC-stochasticity.

Abstract prepared by Justin Miller.

E-mail: [email protected]

URL: https://curate.nd.edu/show/6t053f4938w

In this thesis, we study Turing degrees in the context of classical recursion theory. What we are interested in is the partially ordered structures $\mathcal {D}_{\alpha }$ for ordinals $\alpha <\omega ^2$ and $\mathcal {D}_{a}$ for notations $a\in \mathcal {O}$ with $|a|_{o}\geq \omega ^2$ .

The dissertation is motivated by the $\Sigma _{1}$ -elementary substructure problem: Can one structure in the following structures $\mathcal {R}\subsetneqq \mathcal {D}_{2}\subsetneqq \dots \subsetneqq \mathcal {D}_{\omega }\subsetneqq \mathcal {D}_{\omega +1}\subsetneqq \dots \subsetneqq \mathcal {D(\leq \textbf {0}')}$ be a $\Sigma _{1}$ -elementary substructure of another? For finite levels of the Ershov hierarchy, Cai, Shore, and Slaman [Journal of Mathematical Logic, vol. 12 (2012), p. 1250005] showed that $\mathcal {D}_{n}\npreceq _{1}\mathcal {D}_{m}$ for any $n < m$ . We consider the problem for transfinite levels of the Ershov hierarchy and show that $\mathcal {D}_{\omega }\npreceq _{1}\mathcal {D}_{\omega +1}$ . The techniques in Chapters 2 and 3 are motivated by two remarkable theorems, Sacks Density Theorem and the d.r.e. Nondensity Theorem.

In Chapter 1, we first briefly review the background of the research areas involved in this thesis, and then review some basic definitions and classical theorems. We also summarize our results in Chapter 2 to Chapter 4. In Chapter 2, we show that for any $\omega $ -r.e. set D and r.e. set B with $D<_{T}B$ , there is an $\omega +1$ -r.e. set A such that $D<_{T}A<_{T}B$ . In Chapter 3, we show that for some notation a with $|a|_{o}=\omega ^{2}$ , there is an incomplete $\omega +1$ -r.e. set A such that there are no a-r.e. sets U with $A<_{T}U<_{T}K$ . In Chapter 4, we generalize above results to higher levels (up to $\varepsilon _{0}$ ). We investigate Lachlan sets and minimal degrees on transfinite levels and show that for any notation a, there exists a $\Delta ^{0}_{2}$ -set A such that A is of minimal degree and $A\not \equiv _T U$ for all a-r.e. sets U.

Abstract prepared by Cheng Peng.

E-mail: [email protected]

The dissertation under comment is a contribution to the area of Set Theory concerned with the interactions between the method of Forcing and the so-called Large Cardinal axioms.

The dissertation is divided into two thematic blocks. In Block I we analyze the large-cardinal hierarchy between the first supercompact cardinal and Vopěnka’s Principle (Part I). In turn, Block II is devoted to the investigation of some problems arising from Singular Cardinal Combinatorics (Part II and Part III).

We commence Part I by investigating the Identity Crisis phenomenon in the region comprised between the first supercompact cardinal and Vopěnka’s Principle. As a result, we generalize Magidor’s classical theorems [2] to this higher region of the large-cardinal hierarchy. Also, our analysis allows to settle all the questions that were left open in [1]. Finally, we conclude Part I by presenting a general theory of preservation of $C^{(n)}$ -extendible cardinals under class forcing iterations. From this analysis we derive several applications. For instance, our arguments are used to show that an extendible cardinal is consistent with “ $(\lambda ^{+\omega })^{\mathrm {HOD}}<\lambda ^+$ , for every regular cardinal $\lambda $ .” In particular, if Woodin’s HOD Conjecture holds, and therefore it is provable in ZFC + “There exists an extendible cardinal” that above the first extendible cardinal every singular cardinal $\lambda $ is singular in HOD and $(\lambda ^+)^{\textrm {{HOD}}}=\lambda ^+$ , there may still be no agreement at all between V and HOD about successors of regular cardinals.

In Part II and Part III we analyse the relationship between the Singular Cardinal Hypothesis (SCH) with other relevant combinatorial principles at the level of successors of singular cardinals. Two of these are the Tree Property and the Reflection of Stationary sets, which are central in Infinite Combinatorics.

Specifically, Part II is devoted to prove the consistency of the Tree Property at both $\kappa ^+$ and $\kappa ^{++}$ , whenever $\kappa $ is a strong limit singular cardinal witnessing an arbitrary failure of the SCH. This generalizes the main result of [3] in two senses: it allows arbitrary cofinalities for $\kappa $ and arbitrary failures for the SCH.

In the last part of the dissertation (Part III) we introduce the notion of $\Sigma $ -Prikry forcing. This new concept allows an abstract and uniform approach to the theory of Prikry-type forcings and encompasses several classical examples of Prikry-type forcing notions, such as the classical Prikry forcing, the Gitik-Sharon poset, or the Extender Based Prikry forcing, among many others.

Our motivation in this part of the dissertation is to prove an iteration theorem at the level of the successor of a singular cardinal. Specifically, we aim for a theorem asserting that every $\kappa ^{++}$ -length iteration with support of size $\leq \kappa $ has the $\kappa ^{++}$ -cc, provided the iterates belong to a relevant class of $\kappa ^{++}$ -cc forcings. While there are a myriad of works on this vein for regular cardinals, this contrasts with the dearth of investigations in the parallel context of singular cardinals. Our main contribution is the proof that such a result is available whenever the class of forcings under consideration is the family of $\Sigma $ -Prikry forcings. Finally, and as an application, we prove that it is consistent—modulo large cardinals—the existence of a strong limit cardinal $\kappa $ with countable cofinality such that $\mathrm {SCH}_\kappa $ fails and every finite family of stationary subsets of $\kappa ^+$ reflects simultaneously.

In this thesis, we study transfer principles in the context of certain Henselian valued fields, namely Henselian valued fields of equicharacteristic $0$ , algebraically closed valued fields, algebraically maximal Kaplansky valued fields, and unramified mixed characteristic Henselian valued fields with perfect residue field. First, we compute the burden of such a valued field in terms of the burden of its value group and its residue field. The burden is a cardinal related to the model theoretic complexity and a notion of dimension associated to $\text {NTP}_2$ theories. We show, for instance, that the Hahn field $\mathbb {F}_p^{\text {alg}}((\mathbb {Z}[1/p]))$ is inp-minimal (of burden 1), and that the ring of Witt vectors $W(\mathbb {F}_p^{\text {alg}})$ over $\mathbb {F}_p^{\text {alg}}$ is not strong (of burden $\omega $ ). This result extends previous work by Chernikov and Simon and realizes an important step toward the classification of Henselian valued fields of finite burden. Second, we show a transfer principle for the property that all types realized in a given elementary extension are definable. It can be written as follows: a valued field as above is stably embedded in an elementary extension if and only if its value group is stably embedded in the corresponding extension of value groups, its residue field is stably embedded in the corresponding extension of residue fields, and the extension of valued fields satisfies a certain algebraic condition. We show, for instance, that all types over the power series field $\mathbb {R}((t))$ are definable. Similarly, all types over the quotient field of $W(\mathbb {F}_p^{\text {alg}})$ are definable. This extends previous work of Cubides and Delon and of Cubides and Ye.

These distinct results use a common approach, which has been developed recently. It consists of establishing first a reduction to an intermediate structure called the leading term structure, or $\operatorname {\mathrm {RV}}$ -sort, and then of reducing to the value group and residue field. This leads us to develop similar reduction principles in the context of pure short exact sequences of abelian groups.

Abstract prepared by Pierre Touchard.

E-mail: [email protected]

URL: https://miami.uni-muenster.de/Record/a612cf73-0a2f-42c4-b1e4-7d28934138a9

The thesis pseudofinite structures and counting dimensions is about the model theory of pseudofinite structures with the focus on groups and fields. The aim is to deepen our understanding of how pseudofinite counting dimensions can interact with the algebraic properties of underlying structures and how we could classify certain classes of structures according to their counting dimensions. Our approach is by studying examples. We treat three classes of structures: The first one is the class of H-structures, which are generic expansions of existing structures. We give an explicit construction of pseudofinite H-structures as ultraproducts of finite structures. The second one is the class of finite difference fields. We study properties of coarse pseudofinite dimension in this class, show that it is definable and integer-valued and build a partial connection between this dimension and transformal transcendence degree. The third example is the class of pseudofinite primitive permutation groups. We generalise Hrushovski’s classical classification theorem for stable permutation groups acting on a strongly minimal set to the case where there exists an abstract notion of dimension, which includes both the classical model theoretic ranks and pseudofinite counting dimensions. In this thesis, we also generalise Schlichting’s theorem for groups to the case of approximate subgroups with a notion of commensurability.

Abstract prepared by Tingxiang Zou.

E-mail: [email protected]

URL: https://tel.archives-ouvertes.fr/tel-02283810/document