In this paper, we investigate the existence of a Friedberg numbering in fragments of Peano Arithmetic and initial segments of Gödel's constructible hierarchy Lα, where α is Σ1 admissible. We prove that

(1) Over P− + BΣ2, the existence of a Friedberg numbering is equivalent to IΣ2, and

(2) For Lα, there is a Friedberg numbering if and only if the tame Σ2 projectum of α equals the Σ2 cofinality of α.

We investigate the geometry of forking for SU-rank 2 elements in supersimple ω-categorical theories and prove stable forking and some structural properties for such elements. We extend this analysis to the case of SU-rank 3 elements.

Let Pp, Pd, and N be the intuitionistic systems of prepositional calculus, predicate calculus, and elementary arithmetic, respectively, described in [3].

Kleene [4] introduces a metamathematical predicate Γ ∣ A for each of the systems Pp, Pd, and N, where Γ ranges over finite sequences of wffs, and A ranges over wffs, of that system. In the case of N, if Γ is consistent, then ‘ Γ ∣ A’ is essentially the result of deleting all references to recursive functions from the metamathematical predicate ‘A is realizable-(Γ ⊦)’ described in [3], pp. 502–503.

Through use of this predicate, Kleene [4] obtains elegant constructive proofs of the following results for N:

Metatheorem 0.1. If B ∨ C is a closed theorem of N, then ⊦ B or ⊦ C.

Metatheorem 0.2. If (∃a)D(a) is a closed theorem of N, then there is a numeral n such that ⊦D(n).

Metatheorem 0.3. If A is a closed wff of N, then A ∣ A is a necessary and sufficient condition that, for all closed B, C, (∃a)D(a) inN:

(0.3.1) ⊦ A ⊃ B ∨ C implies ⊦ A ⊃ B or ⊦A ⊃ C

and

(0.3.2) ⊦A ⊃ (∃)D(a) implies there is a numeral n such that ⊦ A ⊃ D(n).

I characterise various model-theoretic properties of types, in complete theories of modules, in terms of the algebraic structure of pure-injective modules. More specifically, I consider the generalised RK-order, and the relation of domination between types, orthogonality of types, and regular types. It will be seen that, essentially, it is the stationary types over pure-injective models which bear the algebraic structural information.

For background in the model theory of modules, see [4], [5], [13], [17], [19], and for the model-theoretic background [10], [11], [12], [18]. More specific references will be given in the text. I summarise some principal definitions and results below. First, though, let me describe the main results.

Throughout this paper, R will be a ring with 1; the language will be that for (right R-) modules. All types will be complete types in a complete theory, T, of R-modules. The notation is reserved for an extremely saturated model of T, inside which all “small” situations may be found. Thus, sets of parameters are just subsets of , and all models will be elementary substructures of . A positive primitive, or pp, formula is one which is equivalent to a formula of the form

with the rij ∈ R.

Suppose that p and q are 1-types over a pure-injective model M.

We consider the version of Pure Inductive Logic which obtains for the language with equality and a single unary function symbol giving a complete characterization of the probability functions on this language which satisfy Constant Exchangeability.

I prove a version of Schanuel's conjecture for Weierstrass equations in differential fields, answering a question of Zilber, and show that the linear independence condition in the statement cannot be relaxed.

Assuming 2ℵ0 = ℵ1 and 2ℵ1 = ℵ2, we build a partial order that forces the existence of a well-order of H(ω2) lightface definable over ⟨H(ω1), ∈⟩ and that preserves cardinal exponentiation and cofinalities.

A theory T is said to be categorical in power κ iff T has a model of power κ and any two models of power κ are isomorphic.

It was conjectured by Morley [4] that if T is a theory in a language with κ > ω symbols and T is categorical in power κ, then T has a model of power < κ. The aim of this paper is to prove the following theorem.

Theorem A. Let κ be a regular cardinal such that ω < κ < 2ω. Let T be a theory in a language with κ symbols such that T is categorical in power κ. Then:

(a) T has a model of power < κ.

(b) T is categorical in all powers μ ≥ κ.

Let be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n−1 satisfies certain simple conditions on its growth rate, then for every , the probability that σ holds for the random graph on n vertices converges. In fact, if p(n) = n−α, α > 1, then the probability is either smaller than for some d > 0, or it is asymptotic to cn−d for some c > 0, d ≥ 0. Results on the difficulty of computing the asymptotic probability are given.

Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable antichain. Our hardest result is that there is an infinite computable weakly stable poset with no infinite chains or antichains. On the other hand, it is easily seen that every infinite computable stable poset contains an infinite computable chain or an infinite antichain. In Reverse Mathematics, we show that SCAC, the principle that every infinite stable poset contains an infinite chain or antichain, is equivalent over RCA0 to WSAC, the corresponding principle for weakly stable posets.

$ISP$ cannot hold at the first or second successor of a singular strong limit of countable cofinality; on the other hand, we force a failure of “strong ${\rm{SCH}}$” across a cardinal where $ITP$ holds. We also show that $ITP$ does not imply that there are stationary many internally unbounded models.

We exhibit a construction which produces for every Turing machine T with two halting states μ0 and μ−1, an algebra B(T) (finite and of finite type) with the property that the variety generated by B(T) is residually large if T halts in state μ−1, while if T halts in state μ0 then this variety is residually bounded by a finite cardinal.

The present note outlines an answer to a question listed as open in our recent survey article [1], familiarity with which is assumed.

Let Γ be the class of all X ⊆ ω such that X is reducible to for some some arithmetical and some positive with Y ⊆ p(Y) for all Y.

Glivenko’s theorem states that an arbitrary propositional formula is classically provable if and only if its double negation is intuitionistically provable. The result does not extend to full first-order predicate logic, but does extend to first-order predicate logic without the universal quantifier. A recent paper by Zdanowski shows that Glivenko’s theorem also holds for second-order propositional logic without the universal quantifier. We prove that Glivenko’s theorem extends to some versions of simple type theory without the universal quantifier. Moreover, we prove that Kuroda’s negative translation, which is known to embed classical first-order logic into intuitionistic first-order logic, extends to the same versions of simple type theory. We also prove that the Glivenko property fails for simple type theory once a weak form of functional extensionality is included.

We consider only computable languages, and countable structures, with universe a subset of ω, which we think of as a set of constants. We identify sentences with their Gödel numbers. Thus, for a structure , the complete (elementary) diagram, Dc(), and the atomic diagram, D(), are subsets of ω. We classify formulas as usual. A formula is both Σ0 and Π0 if it is open. For n > 0, a formula, in prenex normal form, is Σn, or Πn, if it has n blocks of like quantifiers, beginning with ∃, or ∀. For a formula θ, in prenex normal form, we let neg(θ) denote the dual formula that is logically equivalent to ¬θ—if θ is Σn, then neg(θ) is Πn, and vice versa.

A notion of complexity for an arbitrary structure was defined in the book of Poizat Les petits cailloux (1995): we can define P and NP problems over a differential field K. Using the Witness Theorem of Blum et al., we prove the P-stability of the theory of differential fields: a P problem over a differential field K is still P when restricts to a sub-differential field k of K. As a consequence, if P = NP over some differentially closed field K, then P = NP over any differentially closed field and over any algebraically closed field.

Fix a language extending the language of ordered fields by at least one new predicate or function symbol. Call an L-structure R pseudo-o-minimal if it is (elementarily equivalent to) an ultraproduct of o-minimal structures. We show that for any recursive list of L-sentences , there is a real closed field satisfying which is not pseudo-o-minimal. This shows that the theory To−min consisting of those -sentences true in all o-minimal -structures, also called the theory of o-minimality (for L), is not recursively axiomatizable. And, in particular, there are locally o-minimal, definably complete expansions of real closed fields which are not pseudo-o-minimal.