We show that Intuitionistic Open Induction iop is not closed under the rule DNS(Ǝ1). This is established by constructing a Kripke model of iop + ¬Ly(2y > x), where Ly(2y > x) is universally quantified on x. On the other hand, we prove that iop is equivalent with the intuitionistic theory axiomatized by PA− plus the scheme of weak ¬¬ LNP for open formulas, where universal quantification on the parameters precedes double negation. We also show that for any open formula φ(y) having only y free. (PA−)i ⊢ Lyφ(y). We observe that the theories iop, i∀1 and iΠ1 are closed under Friedman's translation by negated formulas and so under VR and IP. We include some remarks on the classical worlds in Kripke models of iop.

If M is a countable transitive model of , then for every real x there is a unique shortest iteration j: M → N with x ∈ N, or none at all.

This paper develops the very basic notions of analysis in a weak second-order theory of arithmetic BTFA whose provably total functions are the polynomial time computable functions. We formalize within BTFA the real number system and the notion of a continuous real function of a real variable. The theory BTFA is able to prove the intermediate value theorem, wherefore it follows that the system of real numbers is a real closed ordered field. In the last section of the paper, we show how to interpret the theory BTFA in Robinson's theory of arithmetic Q. This fact entails that the elementary theory of the real closed ordered fields is interpretable in Q.

Given any field K, there is a function field F/K in one variable containing definable transcendental over K, i.e., elements in F / K first-order definable in the language of fields with parameters from K. Hence, the model-theoretic and the field-theoretic relative algebraic closure of K in F do not coincide. E.g., if K is finite, the model-theoretic algebraic closure of K in the rational function field K(t) is K(t).

For the proof, diophantine ∅-definability ofK in F is established for any function field F/K in one variable, provided K is large, or K× /(K×)n is finite for some integer n > 1 coprime to char K.

A classical quantified modal logic is used to define a “feasible” arithmetic whose provably total functions are exactly the polynomial-time computable functions. Informally, one understands ⃞∝ as “∝ is feasibly demonstrable”.

differs from a system that is as powerful as Peano Arithmetic only by the restriction of induction to ontic (i.e., ⃞-free) formulas. Thus, is defined without any reference to bounding terms, and admitting induction over formulas having arbitrarily many alternations of unbounded quantifiers. The system also uses only a very small set of initial functions.

To obtain the characterization, one extends the Curry-Howard isomorphism to include modal operations. This leads to a realizability translation based on recent results in higher-type ramified recursion. The fact that induction formulas are not restricted in their logical complexity, allows one to use the Friedman A translation directly.

The development also leads us to propose a new Frege rule, the “Modal Extension” rule: if ⊢ ∝ a then ⊢ A↔ ∝ for new symbol A.

The study of pseudo-algebraically closed fields (henceforth called PAC) started with the work of J. Ax on finite and pseudo-finite fields [1]. He showed that the infinite models of the theory of finite fields are exactly the perfect PAC fields with absolute Galois group isomorphic to , and gave elementary invariants for their first order theory, thereby proving the decidability of the theory of finite fields. Ax's results were then extended to a larger class of PAC fields by M. Jarden and U. Kiehne [21], and Jarden [19]. The final word on theories of PAC fields was given by G. Cherlin, L. van den Dries and A. Macintyre [10], see also results by Ju. Ershov [13], [14]. Let K be a PAC field. Then the elementary theory of K is entirely determined by the following data:

• The isomorphism type of the field of absolute numbers of K (the subfield of K of elements algebraic over the prime field).

• The degree of imperfection of K.

• The first-order theory, in a suitable ω-sorted language, of the inverse system of Galois groups al(L/K) where L runs over all finite Galois extensions of K.

They also showed that the theory of PAC fields is undecidable, by showing that any graph can be encoded in the absolute Galois group of some PAC field. It turns out that the absolute Galois group controls much of the behaviour of the PAC fields. I will give below some examples illustrating this phenomenon.

We show that the “effective cardinality” of the collection of sets is strictly bigger than the effective cardinality of the . The phrase effective cardinality is vague but can be made exact in the usual ways. For instance:

Theorem 1.1. Assume ADL(ℝ)Then in L(ℝ) there is no injection

.

A few years ago Tony Martin showed a similar result, establishing the non-existence of an injection from to for m sufficiently larger than n. His method did not seem to work for m = n + 1.

This present paper gives level by level calculations for the projective hierarchy, but it too falls short of a complete analysis, in as much as it leaves the position of the effective cardinals in the Wadge degrees largely obscure. At the low levels it takes some time for any new cardinals to appear. Whenever Γ1, Γ2 are non-trivial Wadge degrees strictly included in one has

.

Any model of ZFC + GCH has a generic extension (made with a poset of size ℵ2) in which the following hold: there exists a-well ordering of the reals, The proof consists in iterating posets designed to change at will the guessing properties of ladder systems on ω1. Therefore, the study of such ladders is a main concern of this article.

We use a new version of the Definability Theorem of Beth in order to unify classical theorems of Yuri Matiyasevich and Jan Denef in one structural statement. We give similar forms for other important definability results from Arithmetic and Number Theory.

We consider separably closed fields of characteristic p > 0 and fixed imperfection degree as modules over a skew polynomial ring. We axiomatize the corresponding theory and we show that it is complete and that it admits quantifier elimination in the usual module language augmented with additive functions which are the analog of the p-component functions.

We give a characterization of the cofinality of the strong measure zero ideal under the continuum hypothesis and prove that we can force it to a value less than the power of the continuum.

In the study of categories whose morphisms display a behaviour similar to that of partial functions, the concept of morphism domain is, obviously, central. In this paper an operation defined on morphisms describes those properties which are related to morphisms being regarded as abstractions of partial functions. This operation allows us to characterise the morphism domains directly, and gives rise to an algebra defined by a simple set of identities. No product-like categorical structures are needed therefore. We also develop the construction of topologies together with the notion of continuous morphism, in order to test the effectiveness of this approach. It is interesting to see how much of the computational character of the morphisms is translated into continuity.

An interpolation theorem holds for many standard modal logics, but first order S5 is a prominent example of a logic for which it fails. In this paper it is shown that a first order S5 interpolation theorem can be proved provided the logic is extended to contain propositional quantifiers. A proper statement of the result involves some subtleties, but this is the essence of it.

After presenting a general setting in which to look at forcing axioms, we give a hierarchy of generalized bounded forcing axioms that correspond level by level, in consistency strength, with the members of a natural hierarchy of large cardinals below a Mahlo. We give a general construction of models of generalized bounded forcing axioms. Then we consider the bounded forcing axiom for a class of partially ordered sets Γ1 such that, letting Γ0 be the class of all stationary-set-preserving partially ordered sets, one can prove the following:

(a) Γ0 ⊆ Γ1,

(b) Γ0 = Γ1 if and only if NSω1 is ℵ1-dense.

(c) If P ∉ Γ1, then BFA({P}) fails.

We call the bounded forcing axiom for Γ1Maximal Bounded Forcing Axiom (MBFA). Finally we prove MBFA consistent relative to the consistency of an inaccessible Σ2-correct cardinal which is a limit of strongly compact cardinals.

We show that if p is a real type which is almost internal in a formula φ in a simple theory, then there is a type p′ interalgebraic with a finite tuple of realizations of p, which is generated over φ. Moreover, the group of elementary permutations of p′ over all realizations of φ is type-definable.

We investigate small theories of Boolean ordered o-minimal structures. We prove that such theories are ℵ0-categorical. We give a complete characterization of their models up to bi-interpretability of the language. We investigate types over finite sets, formulas and the notions of definable and algebraic closure.

We study the relationships between definitions of compactness in topological spaces and the roll the axiom of choice plays in these relationships.

Let K and K′ be two elliptic fields with complex multiplication over an algebraically closed field k of characteristic 0. non k-isomorphic, and let C and C′ be two curves with respectively K and K′ as function fields. We prove that if the endomorphism rings of the curves are not isomorphic then K and K′ are not elementarily equivalent in the language of fields expanded with a constant symbol (the modular invariant). This theorem is an analogue of a theorem from David A. Pierce in the language of k-algebras.

It is shown that there exists a low2 Harrington non-splitting base — that is, a low2 computably enumerable (c.e.) degree a such that for any c.e. degrees x, y, if 0′ = x ∨ y, then either 0′ = x ∨ a or 0′ = y ∨ a. Contrary to prior expectations, the standard Harrington non-splitting construction is incompatible with the low2-ness requirements to be satisfied, and the proof given involves new techniques with potentially wider application.

Let T be a model-complete theory that eliminates the quantifier ∃∞x For T we construct a theory T+ such that any element in a model of T+ determines a model of T. We show that T+ has a model companion T1. We can iterate the construction. The produced theories are investigated.