We settle a number of questions concerning definability in first order logic with an extra predicate symbol ranging over semi-linear sets. We give new results both on the positive and negative side: we show that in first-order logic one cannot query a semi-linear set as to whether or not it contains a line, or whether or not it contains the line segment between two given points. However, we show that some of these queries become definable if one makes small restrictions on the semi-linear sets considered.

Let P be the set of prime numbers. Theorem 1 of [1] shows that the linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,P〉 and therefore that the first-order theory of this structure is undecidable. Let m be any fixed natural number >2, let R be the set of natural numbers <m which are prime to m, and let r be any fixed element of R. The set

is infinite (Dirichlet). Theorem 1 of [1] can be improved as follows:

Proposition. The linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,Pm,r〉 and therefore that the first-order theory of this structure is undecidable.

Proof. We follow [1] with the following new ingredients. Let k be the number of elements of R, i.e. k = ϕ(m) where ϕ is Euler's totient function. Since k is even, the polynomial g(n) = nk + n satisfies g(0) = g(−1) = 0, so (by Lemma 1 of [1]) it follows from the linear case of (H) that there are natural numbers al (l ϵ ω) such that al+g(0), al+g(1),…, al+g(l) are consecutive primes. Since R is finite, we may assume that all the al's have the same residue t in R, so that al+g(i) ≡ t+1+i (mod m) for i ϵ R. This implies that the function t+1+i (reduced mod m) gives a permutation of R, so we can find s ϵ R such that al+g(s) ≡ r (mod m). Consider the polynomial h(n) = g(s + mn) and let bl = as+ml. Then bl + h(0), bl + h(1),…, bl + h(l) are elements of Pm,r. They are not necessarily consecutive elements of Pm,r, but they are separated by a fixed number of elements of Pm,r. This implies that {h(n) ∣ n ϵ ω} is definable in 〈ω,+,Pm,r〉(by adapting the proof of Theorem 1 of [1]), and the result follows.

Validity in recursive structures was investigated by several authors. Kreisel [10] has shown that there exists a consistent sentence of classical predicate calculus (CPC) that does not possess a recursive model. The sentence is a conjunction of the axioms of a variant of Bernays set theory, including the axiom of infinity. The language contains additional constants besides ϵ. Later Kreisel [2] and Mostowski [3] presented a sentence (not possessing recursive models) which was a conjunction of axioms of a variant of Bernays set theory without the axiom of infinity but still with additional constants besides ϵ. Later Mostowski [4] improved the result by giving a sentence which can be demonstrated in Heyting arithmetic to be consistent and to have no recursive models. Rabin [6] obtained a simple proof that some sentence of set theory with the single nonlogical constant ϵ does not have any recursively enumerable models.

More generally, Mostowski [5] has shown that the set of all sentences valid in all RE models is not arithmetical and Vaught [1] improved this result by showing that it holds for a language of one binary relation. In fact, Vaught gives· a way of translating n-place relations to 2-place ones that preserves the RE characteristic of the model. For further results pertaining to recursive models see Vaught [1].

The work [11] deals with questions of first-order definability in algebraic function fields. In particular, it exhibits new cases in which the field of constant functions is definable, and it investigates the phenomenon of definable transcendental elements. We fix some of its proofs and make additional observations concerning definable closure in these fields.

Assume T is a small superstable theory. We introduce the notion of a flat Morley sequence, which is a counterpart of the notion of an infinite Morley sequence in a type p, in case when p is a complete type over a finite set of parameters. We show that for any flat Morley sequence Q there is a model M of T which is τ-atomic over {Q}. When additionally T has few countable models and is 1-based, we prove that within M there is an infinite Morley sequence I, with I ⊂ dcl(Q), such that M is prime over I.

A grafted frame is a new kind of frame which combines a modal frame and some relevance frames. A grafted model consists of a grafted frame and a truth-value assignment. In this paper, the grafted frame and the grafted model are constructed and used to show the completeness of S1. The implications of S1-completeness are discussed.

A grafted frame does not combine two kinds of frames simply by putting relations defined in the components together. That is, the resulting grafted frame is not in the form of <W,R,R′>, or more generally, in the form of <W, R, R′,R″>,…>, which consists of a non-empty set with several relations defined on it.1 Rather, it resembles the construction of fibering proposed by D. M. Gabbay and M. Finger (see [4] and [3]). On a grafted frame, some modal worlds, which belong to the initial modal frame, are attached by some relevance frames.

However, these two semantics have important differences. Consider the combined semantics involving semantics of relevance logic and modal logic. A fibred model and a grafted model proposed in this paper differ in the following respects. First, a fibred model is constructed from a class of modal models and a class of relevance models. A grafted model consists of a grafted frame and a truth-value assignment, where the grafted frame is constructed from a modal frame and some relevance frames, and the assignment is a union of a modal truth-value assignment VM and some relevance truth-value assignments VR. VM (VR) defined in this paper is not the same as the assignment contained in a modal (relevance) model. Second, in a fibred model each relevance world is associated (or fibred) with a modal model and each modal world with a relevance model.2 To be the grafted frame on which a grafted model is based, it is enough to have some modal worlds attached by some relevance frames. Moreover, no relevance world is associated with a modal frame in the grafted frame. Third, fibred models are intended to provide an appropriate semantics to combined logics. Grafted frames and grafted models are inspired to characterize S1, which, containing only one modality □, is not a combined logic. It is shown in this paper that S1 is sort of a meta-logic of the intersection of S0.4 and F, where S0.4, a new system proposed in this paper, is in turn a meta-logic of the relevance logic.

The lambda calculus was conceived by Church, and to some extent by Curry (see [1] and [2]), as a general theory of functions, more precisely as a formalization of two basic functional concepts: application and abstraction. This claim to universality was impossible to maintain, for it soon became apparent that functions in the calculus are required to have properties which are by no means universal. Self-application is certainly a very special feature, but more relevant from our point of view is the existence of fixed points, which is definitely a nonuniversal property of functions. This situation was not ignored, but was considered rather as a form of inconsistency very much related to the paradoxes of set theory (for example, see the discussion of the paradoxical combinator in [2]).

More recently, the lambda calculus has been studied by people in computer science, and as a result the algorithmic nature of the system has been more explicitly recognized. Eventually, the right approach was taken by D. Scott (see [4] and [5]) who restricted the objects of the calculus to continuous functionals over complete lattices, which can be combined in structures where application and abstraction are properly interpreted. It soon became clear that complete lattices were not necessary, and more general structures were introduced. On the other hand the requirement of continuity was essential for the construction, and has remained a basic feature. It is one of the purposes of this paper to show that in the general situation continuity can be replaced by monotonicity.

The work of Scott was extended by Wadsworth [6], who gave a precise formulation of the operational semantics, and proved the equivalence to Scott's interpretation.