We show that for every c.e. degree a > 0 there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets S there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of S. Then we show that if α ∈ ω ∪ {ω} then for any α-c.e. degree a > 0 there exists an intrinsically α-c.e. relation on the domain of a computable structure whose degree spectrum {0, a}. All of these results also hold for m-degree spectra of relations.

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable degree, but not 0. Since our argument requires the technique of permitting below a set, we include a detailed explantion of the mechanics and intuition behind this type of permitting.

Working in Z + KP, we give a new proof that the class of hereditarily finite sets cannot be proved to be a set in Zermelo set theory, extend the method to establish other failures of replacement, and exhibit a formula Φ(λ, a) such that for any sequence ⟨Aλ ∣ λ a limit ordinal⟩ where for each λ. Aλ ⊆ λ2, there is a supertransitive inner model of Zermelo containing all ordinals in which for every λAλ = {a ∣ Φ(λ, a)}.

A first-order sentence is quasi-modal if its class of models is closed under the modal validity preserving constructions of disjoint unions, inner substructures and bounded epimorphic images.

It is shown that all members of the proper class of canonical structures of a modal logic Λ have the same quasi-modal first-order theory ΨΛ. The models of this theory determine a modal logic Λe which is the largest sublogic of Λ to be determined by an elementary class. The canonical structures of Λe also have ΨΛ as their quasi-modal theory.

In addition there is a largest sublogic Λe of Λ that is determined by its canonical structures, and again the canonical structures of Λe have ΨΛ are their quasi-modal theory. Thus . Finally, we show that all finite structures validating Λ are models of ΨΛ, and that if Λ is determined by its finite structures, then ΨΛ is equal to the quasi-modal theory of these structures.

In this paper, we show by a proof-theoretical argument that in a logic without structural rules, that is in noncommutative linear logic with exponentials, every formula A for which exchange rules (and weakening and contraction as well) are admissible is provably equivalent to? A. This property shows that the expressive power of “noncommutative exponentials” is much more important than that of “commutative exponentials”.

We introduce an implication-with-possible-exceptions and define validity of rules-with-possible-exceptions by means of the topological notion of a full subset. Our implication-with-possible-exceptions characterises the preferential consequence relation as axiomatized by Kraus, Lehmann and Magidor [Kraus, Lehmann, and Magidor, 1990]. The resulting inference relation is non-monotonic. On the other hand, modus ponens and the rule of monotony, as well as all other laws of classical propositional logic, are valid-up-to-possible exceptions. As a consequence, the rules of classical propositional logic do not determine the meaning of deducibility and inference as implication-without-exceptions.

We will study several weak axiom systems that use the Subtraction and Division primitives (rather than Addition and Multiplication) to formally encode the theorems of Arithmetic. Provided such axiom systems do not recognize Multiplication as a total function, we will show that it is feasible for them to verify their Semantic Tableaux, Herbrand, and Cut-Free consistencies. If our axiom systems additionally do not recognize Addition as a total function, they will be capable of recognizing the consistency of their Hilbert-style deductive proofs. Our axiom systems will not be strong enough to recognize their Canonical Reflection principle, but they will be capable of recognizing an approximation of it, called the “Tangibility Reflection Principle”. We will also prove some new versions of the Second Incompleteness Theorem stating essentially that it is not possible to extend our exceptions to the Incompleteness Theorem much further.

In this paper, constructions of free ordered algebras on one generator are given that correspond to some one-variable fragments of affine propositional classical logic and their extensions with n-contraction (n ≥ 2). Moreover, embeddings of the already known infinite free structures into the algebras introduced below are furnished with; thus, solving along the respective cardinality problems.

It is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for Γ0. Let T be the set-theoretic ordinal notation system for Γ0 and Ttree the tree ordinal representation for Γ0. It is shown in this paper that (Gα)α∈T matches up with the class of functions which are elementary recursive in the Ackermann function as does (by folklore). By thinning out terms in which the addition function symbol occurs we single out subsystems T* ⊆ T and Ttree* ⊆ Ttree (both of order type not exceeding ε0) and prove that still matches up with but now consists of elementary recursive functions only. We discuss the relationship between these results and the Γ0-based termination proof for the standard rewrite system for the Ackermann function.

In this paper, two theorems concerning measurable limits of strong cardinals and supercompactness are proven. This generalizes earlier work, both individual and joint with Shelah.

We formulate and prove a combinatorial property assuming AD + V = L(ℝ). As a consequence, we show that every regular κ which is either a Suslin cardinal or the successor of a Suslin cardinal is -supercompact. In particular, all the projective ordinals are -supercompact.

We show that all the projective ordinals are supercompact through their supremum and a ways beyond.

We can use the compositional semantics of Hodges [9] to show that any compositional semantics for logics of imperfect information must obey certain constraints on the number of semantically inequivalent formulas. As a corollary, there is no compositional semantics for the ‘independence-friendly’ logic of Hintikka and Sandu (henceforth IF) in which the interpretation in a structure A of each 1 -ary formula is a subset of the domain of A (Corollary 6.2 below proves this and more). After a fashion, this rescues a claim of Hintikka and provides the proof which he lacked:

… there is no realistic hope of formulating compositional truth-conditions for [sentences of IF], even though I have not given a strict impossibility proof to that effect.

(Hintikka [6] page 110ff.) One curious spinoff is that there is a structure of cardinality 6 on which the logic of Hintikka and Sandu gives nearly eight million inequivalent formulas in one free variable (which is more than the population of Finland).

We thank the referee for a sensible change of notation, and Joel Berman and Stan Burris for bringing us up to date with the computation of Dedekind's function (see section 4). Our own calculations, utterly trivial by comparison, were done with Maple V.

The paper Hodges [9] (cf. [10]) gave a compositional semantics for a language with some devices of imperfect information. The language was complicated, because it allowed imperfect information both at quantifiers and at conjunctions and disjunctions.

The satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations.

It is shown that FO2 over ordered, respectively wellordered. domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems is essentially the same as for plain unconstrained FO2. namely non-deterministic exponential time.

In contrast FO2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings. wellorderings. or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO2 and computation tree logic CTL.

If K is a field of finite Morley rank, then for any parameter set A ⊆ Keq the prime model over A is equal to the model-theoretic algebraic closure of A. A field of finite Morley rank eliminates imaginaries. Simlar results hold for minimal groups of finite Morley rank with infinite acl(∅).

The Mycielski ideal is defined to consist of all sets A ⊆ ℕk such that {f ↾ X : f ∈ A} ≠ Xk for all . It will be shown that the covering numbers for these ideals are all equal. However, the covering numbers of the closely associated Rosłanowski ideals will be shown to be consistently different.

We point out that the theory of difference fields with algebraically closed fixed field has no model companion.

The Alperin-Goldschmidt Fusion Theorem [1, 5], when combined with pushing up [7], was a useful tool in the classification of the finite simple groups. Similar theorems are needed in the study of simple groups of finite Morley rank, in the even type case (that is, when the Sylow 2-subgroups are of bounded exponent, as in algebraic groups over fields of characteristic 2). In that context a body of results relating to fusion of 2-elements and the structure of 2-local subgroups is needed: pushing up, and the classification of groups with strongly or weakly embedded subgroups, or have strongly closed abelian subgroups (c.f, [2]). Two theorems of Alperin-Goldschmidt type are proved here. Both are needed in applications.

The following is an exact analog of the Alperin-Goldschmidt Fusion Theorem for groups of finite Morley rank, in the case of 2-elements:

Theorem 1.1. Let G be a group of finite Morley rank, and P a Sylow 2-subgroup of G. If A, B ⊆ P are conjugate in G, then there are subgroups Hi ≤ Pand elementsxi ∈ N(Hi) for 1 ≤ i ≤ n, and an elementy ∈ N(P), such that for all i:

1. Hi is a tame intersection of two Sylow 2-subgroups;

2. CP(Hi) ≤ Hi;

3. N(Hi)/Hiis 2-isolated

and

(a)

(b) .

The following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one degrees? Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and therefore do not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integer as for example nineteen, but it is never an even finite number.

In spite of the analogies between ℚp and which became evident through the work of Ax and Kochen, an adaptation of the complete recursive axiom system given by them for ℚp, to the case of does not render a complete axiom system. We show the independence of elementary properties which express the action of additive polynomials as maps on . We formulate an elementary property expressing this action and show that it holds for all maximal valued fields. We also derive an example of a rather simple immediate valued function field over a henselian defectless ground field which is not a henselian rational function field. This example is of special interest in connection with the open problem of local uniformization in positive characteristic.