We show that the problem of deciding if a finite set of closed terms in normal form is a basis is recursively unsolvable. The restricted problem concerning one element sets is still recursively unsolvable. MSC: 03B40, 03D35.

It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best possible in (...) various senses. (shrink)

Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of computability.

A very simple many-valued predicate calculus is presented; a completeness theorem is proved and the arithmetical complexity of some notions concerning provability is determined.

§1. The mission of axiomatic set theory. What is set theory needed for in the foundations of mathematics? Why cannot we transact whatever foundational business we have to transact in terms of our ordinary logic without resorting to set theory? There are many possible answers, but most of them are likely to be variations of the same theme. The core area of ordinary logic is by a fairly common consent the received first-order logic. Why cannot it take care of itself? (...) What is it that it cannot do? A large part of every answer is probably that first-order logic cannot handle its own model theory and other metatheory. For instance, a first-order language does not allow the codification of the most important semantical concept, viz. the notion of truth, for that language in that language itself, as shown already in Tarski. In view of such negative results it is generally thought that one of the most important missions of set theory is to provide the wherewithal for a model theory of logic. For instance Gregory H. Moore asserts in his encyclopedia article “Logic and set theory” thatSet theory influenced logic, both through its semantics, by expanding the possible models of various theories and by the formal definition of a model; and through its syntax, by allowing for logical languages in which formulas can be infinite in length or in which the number of symbols is uncountable. (shrink)

We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.

It will be shown that in the lattice of recursively enumerable sets one can define elementarily with parameters a structure isomorphic to (∑ 0 4 , ∑ 0 3 ), i.e. isomorphic to the lattice of ∑ 0 4 sets together with a unary predicate selecting out exactly the ∑ 0 3 sets.

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the (...) theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers. (shrink)

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like (...) manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper. (shrink)

R. Shore proved that every recursively enumerable set can be split into two nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ϵ of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two effectively nowhere simple sets, and r. e. sets which can be split into (...) two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* is effectively isomorphic to ϵ*, and that there is a nowhere simple set A such that L* is not effectively isomorphic to ϵ*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L* effectively isomorphic to ϵ*. (shrink)

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

If □ is conceived as an operator, i.e., an expression that gives applied to a formula another formula, the expressive power of the language is severely restricted when compared to a language where □ is conceived as a predicate, i.e., an expression that yields a formula if it is applied to a term. This consideration favours the predicate approach. The predicate view, however, is threatened mainly by two problems: Some obvious predicate systems are inconsistent, and possible-worlds semantics for predicates of (...) sentences has not been developed very far. By introducing possible-worlds semantics for the language of arithmetic plus the unary predicate □, we tackle both problems. Given a frame (W, R) consisting of a set W of worlds and a binary relation R on W, we investigate whether we can interpret □ at every world in such a way that □ $\ulcorner A \ulcorner$ holds at a world ᵆ ∊ W if and only if A holds at every world $\upsilon$ ∊ W such that ᵆR $\upsilon$ . The arithmetical vocabulary is interpreted by the standard model at every world. Several 'paradoxes' (like Montague's Theorem, Gödel's Second Incompleteness Theorem, McGee's Theorem on the ω-inconsistency of certain truth theories, etc.) show that many frames, e.g., reflexive frames, do not allow for such an interpretation. We present sufficient and necessary conditions for the existence of a suitable interpretation of □ at any world. Sound and complete semi-formal systems, corresponding to the modal systems K and K4, for the class of all possible-worlds models for predicates and all transitive possible-worlds models are presented. We apply our account also to nonstandard models of arithmetic and other languages than the language of arithmetic. (shrink)

We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is Π 1 1 complete. Adding one unary predicate is enough to get Π 1 1 hardness, while adding more predicates (of any arity) does not make the complexity any worse.

In philosophical logic necessity is usually conceived as a sentential operator rather than as a predicate. An intensional sentential operator does not allow one to express quantified statements such as 'There are necessary a posteriori propositions' or 'All laws of physics are necessary' in first-order logic in a straightforward way, while they are readily formalized if necessity is formalized by a predicate. Replacing the operator conception of necessity by the predicate conception, however, causes various problems and forces one to reject (...) many philosophical accounts involving necessity that are based on the use of operator modal logic. We argue that the expressive power of the predicate account can be restored if a truth predicate is added to the language of first-order modal logic, because the predicate 'is necessary' can then be replaced by 'is necessarily true'. We prove a result showing that this substitution is technically feasible. To this end we provide partial possible-worlds semantics for the language with a predicate of necessity and perform the reduction of necessities to necessary truths. The technique applies also to many other intensional notions that have been analysed by means of modal operators. (shrink)

By theword problemfor some class of algebraic structures we mean the problem of determining, given a finite setEof equations between words and an additional equationx=y, whetherx=ymust hold in all structures satisfying each member ofE. In 1947 Post [P] showed the word problem for semigroups to be undecidable. This result was strengthened in 1950 by Turing, who showed the word problem to be undecidable forcancellation semigroups,i.e. semigroups satisfying thecancellation propertyNovikov [N] eventually showed the word problem for groups to be undecidable.In 1966 (...) Gurevich [G] showed the word problem to be undecidable forfinitesemigroups. However, this result on finite structures has not been extended to cancellation semigroups or groups; indeed it is easy to see that a finite cancellation semigroup is a group, so both questions are the same. We do not here settle the word problem for finite groups, but we do show that the word problem is undecidable for finite semigroups with zero satisfying an approximation to the cancellation property. (shrink)