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

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.

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

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.

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 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 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]

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.

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]