Algebraic combinatorics in bounded induction

Algebraic combinatorics in bounded induction Joaquín Borrego-Díaz Departamento de Ciencias de la Computación e Inteligencia Artificial, E.T.S. Ingeniería Informática, Universidad de Sevilla, Avda. Reina Mercedes s.n., 41012, Sevilla, Spain a b s t r a c t Keywords: Bounded induction Stone-Čech compactification Ramsey theorem Peano Arithmetic In this paper, new methods for analyzing models of weak subsystems of Peano Arithmetic are proposed. The focus will be on the study of algebro-combinatoric properties of certain definable cuts. Their relationship with segments that satisfy more induction, with those limited by the standard powers/roots of an element, and also with definable sets in Bounded Induction is studied. As a consequence, some considerations on the Π1-interpretability of IΔ0 in weak theories, as well as some alternative axiomatizations, are reviewed. Some of the results of the paper are obtained by immersing Bounded Induction models in its Stone-Cech Compactification, once it is endowed with a topology. Contents 1. Introduction ....................................................................... 2 1.1. Motivation.................................................................... 4 1.2. Aim of the paper ............................................................... 7 1.3. Structure of the paper............................................................ 7 2. Preliminaries and some starting results..................................................... 7 2.1. Subsystems of IΔ0.............................................................. 7 2.2. Open induction and subsystems..................................................... 8 2.3. Exponentiation and segments determined by (standard) powers or integer roots.................... 9 2.4. Algebra on Stone-Čech compactification of a (discrete) semigroup ............................. 10 3. Part I: maximal segments, kernels and gaps.................................................. 11 3.1. Definability of kernels............................................................ 13 3.2. Collapse of kernels and interpretability ................................................ 16 3.3. Arithmetic of gaps and segments .................................................... 18 4. Part II: algebraic combinatorics in IEk..................................................... 21 4.1. Combinatorics in gaps............................................................ 21 2 4.2. FP and FS-sets within gaps........................................................ 22 4.3. Combinatorics in presence of weak overspill on N......................................... 24 5. Closing remarks..................................................................... 26 Acknowledgements ....................................................................... 28 References ............................................................................. 28 1. Introduction A significant amount of the research corpus on (models of) classic subsystems of Peano Arithmetic (PA) is primarily focused on achieving two types of goals. A first type refers to studying how powerful a theory (e.g. fragment of PA) is for supporting the results of elementary number theory. A second one is devoted to obtaining independence results for (open) central problems to Complexity Theory [16]. The first objective is usually focused on theories weaker than IΣ1, because that theory is already enough to develop a large part of Number Theory. A frontier for such an analysis is Parikh’s theory IΔ0(the theory of bounded induction), where several problems are related to its power for developing number theory remains open, some of these being related to open problems in Complexity Theory. Its “frontier” nature is because a large number of these questions can be solved if IΔ0is extended with an axiom that ensures that a certain total function grows faster than any polynomial function. For example, the exponential function. Please let us recall that according to a celebrated result of R. Parikh this kind of functions are not definable in IΔ0(cf. [22], Th. V.1.4): Result 1.1. Every provably recursive function in IΔ0is bounded by a polynomial. Concerning the second research line (the searching for independence results), the situation is similar. For example, in strong fragments, a classical approach to solve this type of problems is based on showing the existence, in any model of the subsystem, of an initial segment (or final extension), that is a model of a stronger theory. This technique is useful to separate theories [40], as well as for connecting model-theoretic and complexity issues (see e.g. the survey [38]). In the same way as in the first research topic, when one works with fragments of PA, almost all positive results are also limited to proper extensions of IΔ0(such as IΣn+1 or BΣn+1). The scenario substantially changes when the theories {IEn}n∈ω(fragments of IΔ0defined like IΣnbut using bounded quantifiers instead) are considered. It is not known if this hierarchy is strict. In fact there are relatively very few results about the relationship between IEkand IEk+1 (k≥1). In stronger subsystems, global coding tools are used to prove results, but this type of functions are not definable in Bounded Induction by Result 1.1, so they can not be used (in particular, arithmetization). We could affirm that one of the reasons for this situation is that the relationship of these theories with classes of computational complexity is not so evident to be able to translate problems between both fields. Let us consider, for example, the case of the class of provably recursive theories on IEn. In general, a useful approach to studying fragments of PA is to consider, given a Ttheory, the class R(T)of provably recursive functions in Tand to study, for example, the existence of initial segments that are closed under that class of functions in (some) Arithmetic models (see [9]for a refinement of up to IE1). However, the approach could be not useful here in our framework, because {R(IEn)}n<ω collapses. Proposition 1.2. R(IΔ0) =R(PA−). Proof. (taken from [4]) Assume that fis provably recursive in IEnby the formula ∃zθ(x, y, z), with θ∈Ek. Then there is a Π1–sentence ∀uψ(u) (suppose ψ∈En+1), such that PA−+∀uψ(u) ∀x∃!y∃zθ(x, y, z). Then PA−∀uψ(u)→∀x∃v∃y,z < vϕ(x, y, z, v) 3 where ϕ ∈Ek+1 is ϕ(x, y, z, v):=θ(x, y, z)∧∀y1,y 2,z 1,z 2<v(θ(x, y1,z 1)∧θ(x, y2,z 2)→y1=y2) Therefore, PA−∀x∃v∃u(¬ψ(u)∨∃y,z < vϕ(x, y, z, v)) By 1.1, there is p(x) ∈N[x]that bounds v, u. Hence the Emax{n+3,k+1}–formula γ(x, y, z)≡∃v<p(x)⎧ ⎪ ⎨ ⎪ ⎩ ∀u≤p(x)ψ(u)∧ϕ(x, y, z, v)∧y<v∧z<v ∨ ∃u≤p(x)¬ψ(u)∧y=0 represents the standard graph of fand PA−∀x∃!y∃zγ(x, y, z).  A plausible way to attack the problem of the possible collapse of {IEn}n∈ω(or, for instance, whether IE1IE2) is to find intermediate alternative axiom schemes to facilitate the analysis. Due to the essentially different behavior of the recursive function classes in Bounded Induction, one option might be to design schemes that describe algebraic properties or properties about, for example, the order <over N. This idea has been used frequently in the strong fragments. In [36] Kreuzer and Yokoyama show interesting intermediate schemes between IΣ1and IΣ2of different nature, which are equivalent if IΣ1is considered as the base theory, and which are equivalent in turn to the well-foundedness of ωω. Among the published works on IEn, some of them deserve to be highlighted. There are refinements of proven facts for IΣn(for instance the existence in nonstandard models of IE1of a nonstandard initial segment model of PA [29,42]), studies of algebraic nature (see e.g. [5,43]for IE0and [44]for IE1) and other studies about alternative axiomatizations [3,15]. Whether IΔ0is finitely axiomatizable -or whether {IEn}n<ω collapsesis the most important open problem in the field, connected with the P=NP? problem (cf. [7,22]). A noticeable result about the theories IEnshall be used in this paper (due to Paris and Dimitracopoulos [14], that is proved by using a formalization of truth definition for En-formulas): Result 1.3. For all nthere is a Π1-sentence σnsuch that IΔ0σnIEn Please, let us note that the Result 1.3 implies that, if {IEn}ncollapses then IΔ0is finitely axiomatizable. Result 1.3 has been used by R. Kaye for studying models of IE1[29]. The above result is useful for our purposes because the reciprocal one -i.e., looking for a property that, added to IEna theory equivalent to IΔ0can be obtainedis more difficult to study in general, because it is possible that adding to IE1a numerical property (or for example Ramsey type scheme) stronger theories than the IΔ0itself are obtained. Two examples would be [10](numerical property) and [8] (Ramsey type scheme). In the first paper, P. D’Aquino described the difference between IE1and IΔ0+exp employing a property of number theory: IE1+PIΔ0+exp where Pis an axiom that states that every Pell equation has a solution. In the second one, C. Cornaros studied the strength of weak forms of the Regularity Principle in the presence of IE1, proving that a Bounded Weak Regularity Principle on E1formulas is equivalent -over IE1-to IΔ0+exp. 4 In general, to investigate the relationship between the theorems in PA (or IΔ0) and those of PA−it is common to focus on the inductive formula(s) necessary to demonstrate the corresponding theorem. Definition 1.4. A formula ϕ(x)is called inductive if PA−ϕ(0) and PA−∀x(ϕ(x) →ϕ(x + 1)). The analysis for the inductive formulas is interesting by itself, as well as the study of their behavior in a model [23]. An interesting result for this paper is the following (in Section 3.2 variants of the result using a fixed inductive formula will be studied). Theorem 1.5. (Wilkie-Paris, see [50]) Let ϕ(x)be a bounded formula. The following conditions are equivalent: 1. IΔ0+exp∀xϕ(x) 2. There exists an inductive formula ψsuch that PA−∀x(ψ(x) →ϕ(x)) 1.1. Motivation The underlying general hypothesis that guides this work is that to advance in the study of (very weak) subsystems of bounded induction it could be interesting to explore the design and use of new tools that exploit properties of natural numbers that are essentially different in nature from those of classical fragments. For example, techniques from other research fields that are not traditionally related to the study of arithmetic models (such as the topology of semigroups), thus changing the point of view with which the models are analyzed. The working hypothesis is relevant when the interest is on theories that extend very weak theories: IE1 0, the extension of PA−allowing Euclidean division; and RIE1 0, that extends it assuring the existence of integer roots. Therefore, we will work with the absence of definable functions of rapid growth (that is, asymptotically faster than any polynomial) which obstructs us from using global arithmetization techniques (that are useful to reproduce classical demonstrations). Concerning the selection of algebraic properties that may be interesting and how to use them, let us consider the paradigmatic case of the set of prime numbers. It is unknown whether IΔ0demonstrates its infinitude. Thus, whilst we cannot assume that this set is unbounded in a IΔ0model, some combinatorial properties associated with its infinity in the standard model can be studied. For example, a very interesting combinatorial property of such a set is that it contains arbitrarily long arithmetic progressions (a celebrated result of Green and Tao [47], see also [19]). We intend to approach the study of properties of this type using some results of the Ramsey type. In general terms, Ramsey type theorems state that if the universe to be studied is divided into a series of parts, then at least one of them enjoys a particular property (commonly associated with a certain kind of regularity). In the finite case, Ramsey’s theory refers to how large the set of parts must be to ensure that the property is satisfied, while in the infinite case the properties focus on detecting a certain regularity in one of those parts. Unlike the seminal result -Ramsey’s theoremthese properties can now be studied with non-standard methods (see e.g. [26]). A well-known example on that line is Schur’s theorem: given n >0, for any prime number plarge enough there is a non-trivial solution of xn+yn=zn(mod p). A nice proof is based on the fact that there are three monochromatic elements in a certain Npartition (a Ramsey property). Although there are studies of the peculiarities about Ramsey Theorem on theories weaker than IΣ1(see for example [52]), in general, these are focused on theories stronger than IΔ0. We are concerned with two general questions. On the one hand, are these types of combinatorial properties on infinite sets (actually, a suitable version) provable in Bounded Induction, independently of the ignorance about the provability of their infinitude? On the other hand, if it is possible to demonstrate a 5 Fig. 1. Compactification of the model augmented with Δ0-definable sets without first element. result of (algebro-)combinatorial regularity of that type, what is the relationship between its corresponding axiomatization as an axiom scheme and IΔ0itself? It should be noted that the results of a combinatorial nature had already been obtained. To quote a recent one, the work of C. Cornaros [8]on the principle of regularity for bounded formulas. The principle of regularity states that if the elements of an infinite set are colored with a finite palette then there is a monochromatic infinite subset. Regularity might be seen as a result of Ramsey type. To simplify the handling of these types of sets and their properties we will approach the question in a dual (although equivalent) way. Instead of working with combinatorial properties of bounded inductive sets in a model of weak arithmetic, we will work with nonempty sets without the first element instead (i.e., the corresponding minimization principle fails). Combinatorial properties of that nature (those showing remarkable algebraic regularities in certain infinite sets) can be attacked by working on an extension of the model that enables us to work within a richer structure. A widely used choice in the case of Nis its Stone-Čech compactification, βN, which has proved to be an extremely useful structure for rewriting properties of Combinatorial Number Theory in another algebraic (topological) ones about βN. Typically, it can be rewritten in terms of the existence of a specific ultrafilter (or a point in another type of compactification). Next, the corresponding property on βNcan be addressed using very powerful techniques (see the surveys [2,13,24], or the recent example [45] where the author analyzes of the mentioned set of prime numbers from that perspective). Our interest in βN(or βM being Ma model of weak arithmetic) lies in the fact that there are strong relationships between the infinite sets in Nand elements (ultrafilters) in βN(as expected for the construction of this one). Infinite sets of Ninduce open neighbors in βNthat contains non-principal ultrafilters with interesting properties. The selection of a suitable ultrafilter will allow to establish the Ramsey type discussed findings. Continuing with the idea, a model M|=PA−can be viewed as an ordered semigroup, thus it is susceptible to being studied algebraically. If the model is endowed with a topology (for example the discrete one), results and techniques developed for topological semigroups can be used. The potential application would not be interesting if, additionally, if one does not work on an adequate compactification of the structure, in order to obtain a richer topology than the discrete one, with interesting properties as βM. We think that we have in that way a certain useful analogy between this kind of compactness and saturation in models of Arithmetic. Both properties allow assuring the existence of a certain element if an adequate approximation to it (a sequence in the compact case or a finitely satisfiable type in the case of saturation) can be obtained. We are particularly interested in that relationship for the special case of Stone-Čech compactification βM. More precisely, the classic construction of βNhas inspired us the following framework (shown in Fig. 1). In more detail, a model of Arithmetic Mis extended to a structure M[Gk] where the Δ0-definable sets without minimum are also elements; they will be interpreted in a similar way to Henkin’s cuts. The notion of cut induces a definable equivalence relationship ∼between that sets (two sets are equivalent if they induce the same cut), switching from that mode to working with equivalency classes [ϕ]. 6 The set M[Gk]is endowed with the Hausdorff topology generated by the basis: {{a}} if a∈Mand {(a, b)⊆M[Gk]:M|=a<ϕ<b}if [ϕ]/∈M (Please, let us note that M[Gk] under the equivalence relation ∼is the so-called Kolmogorov quotient of this topology.) With that topology the set Mis dense in M[Gk]. Since βM is the biggest compactification of M, there is a projection π:βM → M[Gk] between βM and any right-topological semigroup compactification of M[Gk]we select (cf. th. 21.4 of [24]). Since πM=IdMis an homomorphism between dense sets (βM is endowed with the semigroup structure that it will be described in Sect. 2.4), then πis also homomorphism (cf. th. 4.22 of [24]). The construction is interesting basically because the sets without the first element become elements of the structure, thus we are going to be able to draw information from those sets by studying (subsets of) the semigroup Sϕ:= π−1({[ϕ]}), when [ϕ]is an idempotent element in M[Gk]. Then some well-known results about βM as compact right topological semigroup can be applied. Although the reference to  M[Gk]can be omitted throughout the paper by defining the subsemigroups only in terms of βM (as we do in fact below), we believe that the semigroup Sϕhas interest itself, as it will be commented in the closing remarks of this paper. Specifically, we are interested in translating a basic property of Nrelated to the existence of relative primes in a set (i.e., elements of the set that can not be decomposed as a product of numbers from the set itself). Given A =∅, let S(A)be the set of its lower bounds, S(A)={x:∀b∈A(x<b)} Given two sets A, B, it will be said that they define the same cut, A ∼SB, if S(A) =S(B). Let A∗be the set of its relative composite elements, A∗:= (A·A)∩A={x∈A:∃b, c ∈A(x=b·c)} A basic property of Nis that if 0, 1 /∈A, then A∗SA. It is not hard to prove that IΔ0is enough to prove that fact for any Δ0-definable set. However, the reciprocal (namely if that property characterizes IΔ0), is somewhat more complicated. We must justify that we can limit ourselves to validate the principle of minimization for sets with adequate internal arithmetic structure to be able to apply that property. In general terms, in this paper alternative axiomatizations of bounded induction theories are obtained through schemes that describe the following property, for any non-empty Δ0-definable set: A∼SA∗⇒{0,1}∩A=∅() The necessary combinatorial properties will be demonstrated by analyzing some appropriate ultrafilters of the set Sϕdescribed above. If we focus on the idea of exploiting the algebraic properties of the compactification βM, it is important to note that the behavior of the operations (which are extensions that of M) is very different from the original ones. For example, in [25] Hindman, Maleki and Strauss shown that if aand bbe distinct positive integers, then the equation u +a ·p =v+b ·phas no trivial solutions with u, v∈βNand p ∈βN\N(in that paper the abelian groups where the corresponding equation holds in their corresponding Stone-Čech compactifications are characterized). However, other interesting relationships have been proven (see e.g. the 7 survey [24]). More details of this issue -once formalizedwill be shown in the subsection 2.4. On the other hand, other results do establish a certain transfer of properties (for example that of [39]), although in general, it is not obtained straightforwardly. For example, for any sufficiently strong theory of arithmetic, the set of Diophantine equations provably unsolvable in the theory is algorithmically undecidable, as a consequence of the MRDP theorem. In contrast, in [27]the author proves the decidability of Diophantine equations provably unsolvable in Robinson’s arithmetic Q. In that paper, the author axiomatizes the universal fragment of Q itself. 1.2. Aim of the paper Driven by the above motivations, some methods for analyzing fragments of Bounded Induction, which are not refinements of those used for classic fragments (those that were applied to IΣnor BΣn) are presented. The proposal is developed in two stages. In the first part, several results about Δ0-definable sets will be established. The model will be submerged in a more complex structure in the second part (the aforementioned Stone-Čech compactification), where techniques related to algebraic combinatorics will be applied, taking into account the Δ0-definability of the sets involved in the study. 1.3. Structure of the paper As we discussed, the paper has a differentiated structure in two related parts. The first part is dedicated to the analysis of segments and cuts in weak induction models, to provide these sets with an algebraic structure (semi-group). In the second part, the construction will be used to submerge the model in a topological structure (compact topological semigroup) where results of a very powerful combinatorial nature are available. When applied, it will provide information on the structure of the model as well as alternative axiomatizations of weak induction. Specifically, the content of the paper is as follows. Section 2is devoted to listing the main elements and results used in the paper. Next, it is studied the so-called T-kernel, the biggest initial segment of a model of a weak theory which is a model of T, when T=IE n, studying its approximation by means algebraic initial segments as well as its definability (Sect. 3). Section 4presents how to show the maximal character of IΔ0 as possible Π1–interpretable theory in RIE1 0(3.18). The second part of the paper starts presenting an algebraic (sec. 5) and topological (sec. 4) treatment, including Ramsey theoretic arguments, of the upper neighborhood of a bounded definable set without the first element. This study allows to give alternative axiomatizations of IΔ0representing the property () described above, as well as to state combinatorial regularities near to the kernel. 2. Preliminaries and some starting results In this section, a number of notions and results to be used throughout the paper will be introduced. Specifically, some results on IΔ0, IEk(k≥1), and IE0=IOpen. Also, two types of initial segments are defined, and finally, a brief introduction on βM (being Ma semigroup) will be shown, focusing on its algebraic and topological features. 2.1. Subsystems of IΔ0 The language of the Arithmetic is L ={+, ·, <, 0, 1}. Quantifications like ∃x(x <t ∧ϕ)or ∀x(x <t →ϕ) (denoted by ∃x <tϕand ∀x <tϕ) are called bounded. 8 The set Δ0is the set of bounded formulas (which have only bounded quantifiers, respectively). Similar to the definitions of the classical fragments in Peano Arithmetic PA, the classes En, Unare defined according to the alternation of (bounded) quantifiers: E0(=U0) is the class of open formulas, En+1 := {∃x1<t 1···∃xm<t mϕ | ϕ ∈Un}, and Un+1 := {∀x1<t 1···∀xp<t pϕ | ϕ ∈En} (with tiL–terms). Therefore Δ0=E ω=kEk. The (finite) theory PA−has as models the nonnegative part of discretely ordered rings. The paper will work on the well–known Induction (I), Least element (L) and Collection (B) schemas, and the theories EΓ = PA−+{Eϕ|ϕ∈Γ} where E =I, L, Band Γ =E n, Un(see [30]and [51]). It is unknown whether {IEn}n<ω collapses. Only partial results are known. Among them, the following ones: •IE 0≡LE0, IE0IE1([43]). •IE 0plus the full collection scheme does not prove IE1[3]. •IE n+1 ⇐⇒ LUn=⇒IEn⇐⇒ IUn⇐⇒ LEn(n ≥1; see [28,51]). Another useful scheme for the paper is the following one: Gψ(x):=∀v<x[∃u<xψ(u,v)→∃u<x(ψ(u,v)∧∀w<u¬ψ(w,v))]. It is easy to see that PA−+{∀uGψ(u):ψ∈Ek} is an alternative axiomatization of IEk. 2.2. Open induction and subsystems If models of IE0are considered, then a large number of results about their algebraic nature can be proved. A seminal paper on this topic was [43], where J. C. Shepherdson shows the following (recursive) nonstandard model NX|=IE 0. Let Kbe the field of real algebraic numbers and Xan indeterminate. The universe of NXis the set of polynomials {apXp/q +···+a1X1/q +a0:ap,...,a 1∈K, ap>0,a 0∈Z,p∈N,q∈N∗}, the addition and multiplication are naturally defined, and the order “<” is interpreted as: P(X) <Q(X)if the leader coefficient of Q(X) −P(X)is >0. Shepherdson’s construction will be generalized (in the first part of the paper) to some kind of extensions and models. The most direct one is to replicate it to obtain, given any M|=IE 0, an end-extension M⊂e MX|=IE 0(The model thus constructed will be called Shepherdson’s extension of M). An algebraic characterization of IE0(also proved in [43]) is the following: Result 2.1. The models of IE0are those models of PA−that are the integer part of their real algebraic closure. 9 See [21]for other analogous results that provide algebraic theories equivalent to various fragments of IE0. Please note also that Shepherdson’s algebraic construction produces a recursive model if a recursive one is extended. Thus it is not useful to build (extensions of) of models of IE1, due to Tennenbaum phenomena in IE1: Result 2.2. There are no recursive nonstandard models of IE1[51]. Shepherdson’s work illustrates how the construction of real closed fields can be related to obtaining adequate extensions of the fraction field of an arithmetic model [12]. See also the more recent paper [46], where Tanaka and Tsuboi present a new construction of real closed fields using an elementary extension of an ordered field that has an integer part that satisfies PA. It is also interesting to review the relationship obtained by D’Aquino, Knight and Strachencko in [11], where it is shown that the real closure of a model IΣ4 is recursively saturated, thus establishing a relationship between a model-theoretic property of (ordered) fields and classical induction schemes on Arithmetic. Alternatively, it is possible to study the inverse path, that is, to analyze the real closed fields that admit an integer part whose non-negative part is a model of PA (see [6]). Throughout the paper, two remarkable subsystems of IE0are considered, which will be used as base theories. The theory IE1 0augments PA−with the induction scheme for open formulas whose atomic subformulas are linear inequalities. The theory is equivalent to PA−+{∃u(vu ≤x<v(u+1))} (i.e. PA−plus Euclidean division), and it is strictly weaker than IE0. The theory of integer roots, RIE1 0:= IE1 0+{∃u(uk≤x<u k+1):k<ω} is also weaker than IE0. Moreover, the extension IE1 0⊂RIE1 0is proper (all these results can be found in [5]). 2.3. Exponentiation and segments determined by (standard) powers or integer roots Let us suppose PA−⊆Tand N|=T. A function f:ωn→ωis provably recursive in Tif there is θ(x, y, z) ∈Δ0such that ∃zθ(x, y, z) defines the graph of fand T∀x∃!y∃zθ(x, y, z). Such functions have been characterized for strong fragments (cf. [22]). According to Result 1.1 the function (x, y) → xyis not provably recursive in IΔ0, although there is a bounded formula η(x, y, z) ∈Δ0that represents this function in IΔ0and such that the basic properties are provable in IΔ0(see e.g. [20]). To simplify the following notation is introduced: xy=zwill mean η(x, y, z), and exp is the sentence ∀x∀y∃z(xy=z). Remark 2.3. Throughout the paper, kewill be an integer such that IEkeproves the basic properties of xy=zas well as the weak overspill principle for Um+1–formulas, for some msuch that xy=z∈Em. Two kinds of segments are used in this paper. The segment determined by standard powers of a ∈M|= PA−is aω:= {b∈M:∃n<ω(b<a n)} It is straightforward to prove that 16 Proof. Let us assume otherwise, that there exists ϕ(x, u) ∈E0and a ∈M(IE0)such that ϕ(x, a) defines M(IE0). Let KMbe the real closure of M(by Result 2.1 Mis not integer part of KM, because M|=IE 0), and Kthe real closure of M(IE0)within KM. Since M(IE0)is a whole part of their actual closure, it verifies that K|=∀x∃y(x≥0→y≤x<y+1∧ϕ(y,a)) (∗) By model completeness of the theory of real closed fields, K≺KM, so KMsatisfies (∗). Then M(IE0) would be an integer part in KM, which is a contradiction.  3.2. Collapse of kernels and interpretability Once the definability of the kernels has been examined, the next concern to be studied is about two related questions. The first one asks whether there exists a model with internal structure like Shepherdson’s model (that is, k–high and k-short for every k) but for infinite and different kernels, (that would imply that IΔ0is not finitely axiomatizable). It will be seen that there is no such model under some assumptions (Corollary 3.15): in an ω-high and ω-short model the hierarchy of kernels {M(IEk)}k<ω collapses. Please note that this fact does not imply that {IEn}ncollapses, nor that IΔ0is finitely axiomatizable modulo IE0, but it suggests the second question: Open Problem 3.12. Is IΔ0a theory Π1-interpretable in IE0? The aim will be to demonstrate on that issue that IΔ0has certain maximal status as possible Π1–interpretable theory on RIE1 0. In what follows it will be used the index keintroduced in Remark 2.3. Firstly it is going to be related to the collapse of {IEn}n<ω with a problem on Δ0-elementary extensions: Theorem 3.13. Suppose that every model of IEkehas a Δ0–elementary extension model of RIE1 0, which is ω–high and ω–short. Then {IEk}k<ω collapses. Proof. Let us see that IEkeIΔ0, being keany index satisfying the features required in Remark 2.3. All one needs to do is prove that if N|=IE kethen N|=IΔ 0. Let Nbe such a model, and let M|=RIE 1 0be a Δ0–elementary extension of Nwhich is ω–high and ω–short. Claim: M(IEke) =M(IΔ0). Proof of the claim: Assume that there is a ∈M(IEke) \M(IΔ0). Let b ∈M(IΔ0)and ψ(u)≡∀x<u∃z<a(bx=z∧zx<a). It holds that M(IEke) |=ψ(n)for each n ∈ω. By weak Um+1–overspill, there is δ∈M(IΔ0) \ωsuch that M|=ψ(δ). Consider now the model of PA−: I={d∈M:∃α∈δ1 ω(d<b α)} It is straightforward to prove that I|=PA−and bωI⊆a1 ω(M(IΔ0)is nonstandard, so δ1 ω=ω because the model is ω-high). Therefore, bω=M(IΔ0), so Mis ω–long. Contradiction.  The claim, together with the fact that N⊆M(IEke) =M(IΔ0), implies that for each a ∈Nand ϕ(x) ∈Δ0it has N|=G ϕ(a) (because M|=G ϕ(a)). Therefore, N|=IΔ 0. 17 Notice that in the demonstration of Theorem 3.13, the following result has been demonstrated, which we believe to be of interest in itself. Corollary 3.14. Let M|=RIE 1 0be such that M(IΔ0) =a1 ω=bω=Nfor some a, b ∈M. Then M(IEk) = M(IΔ0)for some k. An interesting question about the special status of IE1in the hierarchy {IEn}n, is whether Corollary 3.14 is true for k=1, since for k=0does not hold. Let us note that, by Theorem 3.13, there is not M|=IE 0 with a stratification like Shepherdson’s model for infinite kernels. Corollary 3.15. There is k≥1such that for each ω–high M|=RIE 1 0with M(IΔ0)nonstandard, one of the following conditions is true: 1. M(IEk) =M(IΔ0). 2. Mis ω–long. Proof. Similar to that of 3.13, taking k=ke. Please note that Corollary 3.15 is already independent of the question of whether {IEn}n<ω collapses. The plausible collapse of IEk-kernels suggests that IΔ0may be Π1-interpretable in a class of models of RIE1 0 (recall that if IEkIΔ0then IΔ0is finitely axiomatizable). This issue will be examined below. Definition 3.16. A Π1–formula Φ(u)interprets IΔ0in a theory Tif Φ defines an initial segment which is a model of IΔ0, that is: •T Φ(0) ∧∀x, y(x ≤y∧Φ(y) →Φ(x)). •T ∀x, y(Φ(x) ∧Φ(y) →Φ(x ·y) ∧Φ(x +1) ∧Φ(x +y)). •For each ψ∈Δ0, T ∀x(Φ(x) →Gψ(x)) (hence T +∀uΦ(u) IΔ0). See [49]for some results about interpretability of theories in models of IΔ0. The following result can be useful to analyze the question of whether IΔ0is Π1-interpretable in RIE1 0. (Please let us compare the next theorem with Th. 5.26 in chap. V of [22], as well as their proofs): Theorem 3.17. Let Tbe a theory such that RIE1 0⊆T ⊆IΔ0and M|=T. Assume that Φ(u)is a Π1–formula defining a proper initial segment closed by multiplication in M. Then M(IΔ0) |=∀xΦ(x). Proof. Assume Φ(u) ≡∀xψ(x, u), with ψ∈Δ0, and let N=M(∀uΦ(u)). If M(IΔ0) ⊆N, the result holds. Suppose that N⊆M(IΔ0). Let Mbe a Σ1–recursively saturated elementary extension of M, and N=M(∀uΦ(u)). Then N⊆M(IΔ0). Let γ(u) ≡∀x, y<uψ(x, y). We claim that M|=γ(0) ∧∀u(γ(u)→γ(u+1)) If a ∈Mis such that M|=γ(a), then a1 ω⊆N(because a1 ω|=∀uΦ(u)). By Σ1–recursive saturation, it can to conclude that a1 ω=N. Thus, a ∈N, hence a +1 ∈N. Therefore, M|=γ(a +1). By induction on γ(u), M(IΔ0) |=∀uγ(u). This implies that N=M(IΔ0) (because M(IΔ0) \N⊆ N(M, IΔ0) \N).  18 The section will be completed by demonstrating a necessary and sufficient condition on the Π1- interpretability of IΔ0in RIE1 0which is consequence of above theorem. Corollary 3.18. The following conditions are equivalent: 1. IΔ0is finitely axiomatizable modulo RIE1 0. 2. There exists an extension of IΔ0which is Π1–interpretable in RIE1 0. Proof. (1) =⇒(2): If IΔ0≡RIE1 0+∀uΦ(u), let Φ(x)≡Φ(x)∧∀u(u<x→Φ(u)) ∧∀u<x∀v<xΦ(u·v). Since M|=RIE 1 0it must be M(∀uΦ(u)) ⊆M(∀uΦ(u)) ⊆M(IΔ0) then the formula Φ(x) interprets an extension of IΔ0in RIE1 0. (2) =⇒(1): Let Φ(x)the Π1-interpretation of an extension Tof IΔ0. If M|=RIE 1 0, then M(∀uΦ(u)) ⊆M(IΔ0) and, reasoning as in Theorem 3.17, it follows that the IΔ0-kernel is defined by Φ(u)in every model of RIE1 0. Therefore RIE1 0+∀uΦ(u)≡IΔ0 3.3. Arithmetic of gaps and segments Several technical results about an extension of the model, where the gaps are considered as elements, are described in this section. A convenient way to do this is to consider them as if they were done with Henkin’s cuts. This section, will introduce how arithmetic is in that extended model (see [32,33]for a study with a broader perspective of the idea). On the topology induced by cuts, in the case of PA there are studies on its behavior (see e.g. [31] where indicators are used). Definition 3.19. Let ϕ(x, a)and ψ(x,  b)be L(M)–formulas. It is said that ϕ(x, a)and ψ(x,  b)define the same gap, M|=ψ∼ϕ, if M|=∀u∀v(u<ϕ<v↔u<ψ<v) Clearly, ‘∼’ is an equivalence relation. It will be denoted by [ϕ]the equivalence class of ϕ. Whilst it is understood that the definitions in this section are intended for gaps, note that they are also suitable for Δ0-definable sets with a first element, by identifying each a ∈Mwith [ϕa] where ϕa(x) := a ≤x. Thus, If M|=(μx)ϕ(x)=athen M|=a∼ϕ For convenience it will be written [a]or simply ainstead of [ϕa]. Given X⊆M, it is defined Gk(M,X):={[ϕ]:ϕis a Ek-gap with parameters in X} 19 and it will be written Gk(M)if X=M. It is possible to extend the order <Mto Gk(M, X)as follows: M|=ϕ<ψif and only if M|=∃x(ϕ(x)∧x<ψ) The segment determined by a formula ϕis defined as S(ϕ):={a∈M:M|=a<ϕ} A useful simplification is to work only with coinitial gaps. A formula ϕ(x)is coinitial if S(ϕ) agree with ¬ϕ(M). It is obvious that every gap is equivalent to a coinitial gap. Please note that if XS(ϕ), then the formula ϕ <ψis Δ0. It is also defined (ϕ, b):={x:M|=ϕ<x∧x<b} Let ϕ, ψ∈G k(M, X), with 1 ≤k≤ω. The addition and the product of two gaps are defined as (ϕ∗ψ)(x):=∃u, v ≤x(ϕ(u)∧ψ(v)∧x=u∗v)(∗∈{+,·}) Note that trivially M|=ϕa∗ϕb∼ϕa∗b It is easy to see that both operations are well defined on equivalence classes, extending that of operations in Mas well as that they are associative and commutative (1 ≤k≤ω). Therefore two semi-group structures are available for endowing Gk(M, X). We are interested in the idempotent gaps. Definition 3.20. Let ∗ ∈{+, ·}. A gap ϕ ∈G k(M, X)isidempotent with respect to ∗(briefly, is an id(∗)-gap) if M|=ϕ ∗ϕ ∼ϕ. That is, [ϕ]is an idempotent element in the semigroup (Gk(M, X), ∗). It will be denoted by I∗ k(M, X) the set of idempotents for ∗and parameters in X(if X=Mit will be written I∗ k(M)). It is easy to write a formula Idemp∗(ϕ) expressing that ϕis a id(∗)–gap in PA−. In the case of the theory RIE1 0, the following formula can be used: Idemp•(ϕ)≡∀x, y(x<ϕ∧y<ϕ→x·y<ϕ) and, in IE1 0, Idemp+(ϕ)is equivalent to a similar formula, due to the following result: Proposition 3.21. Let M|=PA−and let ϕ ∈Δ0. 1. If M|=IE 1 0, ϕis an id(+)–gap if and only if S(ϕ)is closed by +. 2. If M|=RIE 1 0then ϕis an id(·)–gap if and only if S(ϕ) |=PA −. This fact is not true for models of IE1 0 in general. Proof. Proof of (2): Assume ϕ(x)is idempotent and a, b ∈S(ϕ)such that M|=ϕ <a ·b. Then there exists csuch that M|=ϕ(c) ∧c <a ·b. Let d, e ∈Msuch that M|=ϕ(d)∧ϕ(e)∧d·e<c Then one of {d, e}is less than one of {a, b}; suppose d <afor example. Thus ϕ <a, a contradiction. 20 Conversely, suppose that ϕ(x)and a ∈Msuch that M|=ϕ <a. If S(ϕ) |=PA −, then M|=ϕ <√a. Therefore there exists c ∈Msuch that M|=ϕ(c) ∧c <√a. Thus M|=(ϕ·ϕ)(c2)∧c2<a The proof of (1) is similar, replacing ·by +, and √aby a 2. Finally it will show that 3.21.(2) fails for a model of IE1 0: Let M1|=IE 1 0the model defined in Theorem 3.8.(2), and ϕ(u) ≡X≤u2. It holds that S(ϕ) |=PA −and (ϕ·ϕ)(u)≡∃u1u2<u(X≤u2 1∧X≤u2 2∧u=u1·u2). Since it is verified that M1|=(ϕ ·ϕ)(u) →u >Xand M1|=ϕ(X), then M1|=ϕ <ϕ ·ϕ. The following result, essentially due to J. Paris [41], shows that it is possible to restrict ourselves to idempotent gaps. Theorem 3.22. Let M|=PA−. 1. If M|=IE 1 0, M|=IΔ 0if and only if Mhas no bounded id(+)–gap. 2. If M|=RIE 1 0, M|=IΔ 0if and only if Mhas no bounded id(·)-gap. The proof of 3.22.(1) is based in the scheme I+ ϕ:= ϕ(0) ∧ϕ(1) ∧∀x, y(ϕ(x)∧ϕ(y)→ϕ(x+y)) →∀xϕ(x) It verifies that IΔ0≡I+Δ0([41], lemma 2). The fact 3.22.(2) is proved like th. 3 of [41](using for example the set {2a:M|=∃y2a=y} instead of the enumeration of the roots of the equation x2+y2−2axy −1 =0). Corollary 3.23. If M|=RIE 1 0is k-high, then M(IEk)is Δ0-definable. Proof. Suppose that a1 ω=M(IEk). Since aω|=IE k, by 3.22 there exists ϕ ∈Ekan id(·)-gap such that M(IEk)<ϕ<a ω By 3.21 it has S(ϕ) |=PA −. Therefore the only possibility is that S(ϕ) =M(IEk). Thus the formula ψ(x)≡x<ϕ defines M(IEk).  Using Corollary 3.23 it is possible to improve Theorem 3.10: Corollary 3.24. If there exists M|=RIE 1 0with M(IEk)not Δ0-definable, then IEkIΔ0. Proof. If Mwere such a model, then it would be k-low by the previous corollary. So, by Theorem 3.10 it follows that IEkIΔ0. 21 A key property of I∗ k(M)is that it is a subsemigroup itself. The result below is proved like Proposition 3.21. Proposition 3.25. Let [ϕ], [ψ] ∈I∗ k(M), and M|=IE 1 0if ∗ =+, or M|=RIE 1 0if ∗ =·. Then [ϕ]∗[ψ]=max{[ψ],[ϕ]}∗∈{+,·} Above result contrasts with an old unsolved question on βNthat clearly exposes the complexity of arithmetic in βN: Are there p, q, r, s ∈βN∗such that p +q=r·s? ([48], Chapter 7, Question 39. See also [1]for other similar problems). Both operations present similar properties under the proper base theory (IE1or RIE1 0), so only the results for the product will be demonstrated. We only enunciate the corresponding ones for the addition. Consider the structure (M[Gk], +, ·, ≤)whose universe is the set of equivalence classes of Ek-definable sets (identifying the element awith ϕa), and the symbols are interpreted as before. Note that M[Gk] |=PA − in general, because M[Gk] |=∃x(x =x +1)when M|=IE k(by Proposition 3.25). In fact, the relationship between M[Gk]and Mcan be determined by relativizing the formulas to Mvia the natural map ϕ → ϕ that relativizes to elements xsuch that x =x +1. Since Gk(M)is defined in M[Gk]by the formula ‘x =x +1’, then for every L(M)-sentence ϕ, M|=ϕif and only if M[Gk]|=ϕ On the other hand, since N⊂eM[Gk], it is verified that M[Gk] |=Σ 1(N) (the true Σ1-sentences in N). In general, in IEk-models, if Th(M[Gk]) x =x +1then M|=IE k+1. 4. Part II: algebraic combinatorics in IEk The results of the first part will now allow us to both enunciate and prove properties in weak induction models that relate combinatorial properties and sets without a first element (gaps). The task will then be carried out concerning the existence of relative composite numbers in some sets, following the idea described in the introduction. 4.1. Combinatorics in gaps The previous section has provided two semigroup structures on M[Gk]. Therefore, one is in a position to apply the (combinatorial) results on topological semigroups to the new structures, to later describe the results in terms of the starting model M. The next aim is to state several combinatorial properties about the upper neighborhood of an idempotent gap (that is, intervals like (ϕ, a)) in the semigroup (M[Gk], ∗)(∗ ∈{+, ·}), formalizing the idea about prime numbers relative to a set that was described in the introduction. For the study it is convenient to split the interval (ϕ, ∞)into ϕ(M)and its complement within the same interval: Definition 4.1. Let ϕ(x)be an Ek-gap. The complement of ϕis the formula ϕ(x) := ¬ϕ(x) ∧ϕ <x. The definition of composite number related to a set (relative composite number) would be defined as follows: Definition 4.2. Let ϕ ∈Ekand M|=PA −. An element a ∈Mis ϕ-composite with respect to ∗ ∈{+, ·} if M|=ϕcomp∗(a), where ϕcomp∗(x):=ϕ(x)∧∃u1,u 2≤x(x=u1∗u2∧ϕ(u1)∧ϕ(u2)) 22 That is ϕcomp∗(M)=(ϕ(M)∗ϕ(M)) ∩ϕ(M) The translation of arithmetical properties (e.g. prime, irreducible elements) to Stone-Čech compactification is not direct and it raises very interesting questions [45]. Please observe that, in general, M|=ϕcomp∗∼ϕ∗ϕ If 0, 1 /∈ϕ(M)and ϕ(M)has a first element, then the set ϕcomp∗(M)is not coinitial with ϕ(nor ϕ)- composite elements, because the first element of ϕ(M)does not satisfy ϕcomp∗, that is, is a prime relative. Analogously with ϕcomp∗. Therefore, the following translation of the arithmetical property () discussed in the introduction is satisfied. Proposition 4.3. Assume M|=IE 1 0and ϕis an L(M)–formula. Then M|=¬ϕ(0) ∧¬ϕ(1) ∧∃xϕ(x)→(Lϕ→ϕcomp∗>ϕ∧(ϕ)comp∗>ϕ)(∗∗) Proof. Trivial.  Please observe that for proving the reciprocal of Proposition 4.3 (namely, if Mverifies A SA∗for any nontrivial Δ0-definable set A, then is a model of IΔ0) can not be straightforwardly proved. The existence of relative composite elements arbitrarily close to the gap needs to be demonstrated (actually it is just needed to state this feature for idempotent Δ0-gaps). The property can be demonstrated by showing that ϕ(M) satisfies some Ramsey type regularity for a certain kind of gap ϕ. 4.2. FP and FS-sets within gaps The regularity feature required to prove the reciprocal of Proposition 4.3 is stated in Theorem 4.4, which is a version of the finite sums theorem (Theorem 4.4). Its proof is inspired by that of Galvin-Glatzer’s proof of the classic result on FP-sets, namely by exploiting the algebraic structure of βM. Specifically, it is shown that given ϕa gap, this or its complement contains FP-sets arbitrarily close to [ϕ]. Theorem 4.4. Let M|=IE 1 0+¬IEk, and let ϕbe an idempotent Ek-gap with respect to ·. Then there exists ψ∈{ϕ, ϕ}such that ψ(M) ∩(ψ, c)is a FP-set for arbitrarily c >ϕ. Proof. Consider the closed (hence compact) nonempty set in βM (recall that, in the Stone-Čech compactification, Adenotes the closure of the set A ⊆Min βM) Hϕ:=  ϕ<a {b:M|=ϕ<b∧b<a} We claim that Claim Hϕis a subsemigroup of βM. Proof of the Claim: It is necessary to prove that p ·q∈Hϕfor any p, q∈Hϕ. That is, that (ϕ, a) ∈p ·q, for all a >ϕ; or equivalently, {x:{y:x·y∈(ϕ, a)}∈q}∈p Write x−1(ϕ, a) ={y:x ·y∈(ϕ, a)}. Let us observe that x−1(ϕ, a) ∈qif and only if ϕ <a x: 23 If ϕ <a x, then (ϕ, a x) ∈qhence x−1(ϕ, a) ∈q. Otherwise a x <ϕ, then (ϕ, a)∩x−1(ϕ, a)=∅ hence x−1(ϕ, a) /∈q. Therefore, it is sufficient to show {x:ϕ<a x} ∈ p Since the set is convex and p ∈Hϕ, the condition above is equivalent to the existence of x >ϕsuch that ϕ <a x. Let us see that such an element exists: Since M|=ϕ ∼ϕ ·ϕ, there is d <asuch that M|=(ϕ·ϕ)(d)∧d<a so M|=ϕ(d1) ∧ϕ(d2) ∧d1·d2=dfor some d1, d2. If x =d1, then a x >d x =d2and M|=d2>ϕ, because M|=ϕ(d2). end of claim proof According to Result 2.4, it is known that Hϕcontains an idempotent element p. Given c >ϕ, since {(ϕ, c)∩ϕ(M),(ϕ, c)∩ϕ(M)} is a partition of (ϕ, c) ∈p, there is ψ∈{ϕ, ϕ}such that ψ(M)∩(ψ,c)∈p hence this set is a FP-set. It only remains to prove that the choice of ψis valid for any element c>ϕ, (that we can suppose c<c). That fact is true, because necessarily (ϕ, c) ∩ψ(M) ∈p(otherwise we would have (ϕ, c) ∩ψ(M) ∈p, but this set would disjoint with ψ(M) ∩(ϕ, c), that is not possible).  Please observe that it is easy to see that π:βM →M[G]of Fig. 1verifies π[Hϕ]={[ϕ]}, as well as the converse of the above result: If ϕ(M)contains FP-sets arbitrarily near the gap, then it is an id(·)-gap. Without any essential modification, a similar result would be obtained for id(+)-gaps can be proved: Theorem 4.5. Let M|=IE 1 0+¬IEk, and let ϕ(x) ∈Ekbe an id(+)-gap. There is ψ∈{ϕ, ϕ}such that ψ(M) contains a FS-set arbitrarily near the gap; that is, for any c >ϕ, ψ(M) ∩(ψ, c)is a FP-set. A consequence of the above theorems was remarked above (directly provable by Theorem 4.4, by using Theorem 3.22): Corollary 4.6. Suppose that ϕbe a Δ0-formula in the language L(M)such that M|=Idemp∗(ϕ)∧¬ϕ(0) ∧¬ϕ(1) and M|=IE 1 0if ∗ =+or M|=RIE 1 0if ∗ =·. If M|=¬Lϕ, then M|=ϕcomp∗∼ϕ∨(ϕ)comp∗∼ϕ. 24 Fig. 3. Existence of arbitrary large powers in gaps (Theorem 4.10). Therefore, by instantiating the result into a scheme that reflects that property alternative axiomatizations of IΔ0are available. The following corollary shows an axiomatic characterization of IΔ0using only the arithmetic properties that have been introduced: an idempotent set that is coinitial with its relative composite numbers contains either 0or 1. Corollary 4.7. The following theories are equivalent to IΔ0: RIE1 0+{∃xϕ(x)∧Idemp•(ϕ)∧(ϕcomp·∼ϕ∨(ϕ)comp·∼ϕ)→(ϕ(0) ∨ϕ(1))}ϕ∈Δ0 IE1 0+{∃xϕ(x)∧Idemp+(ϕ)∧(ϕcomp+∼ϕ∨(ϕ)comp+∼ϕ)→(ϕ(0) ∨ϕ(1))}ϕ∈Δ0 Exploiting the ideas introduced in this subsection, richer combinatorial properties can be proved if we allow the model to fulfill basic additional properties, such as overspill for its standard part. 4.3. Combinatorics in presence of weak overspill on N This section will show some results from semi-group properties Hϕ(introduced in Theorem 4.4) for models which satisfies a weak form of overspill (see [15]): Definition 4.8. Let M|=PA −and Γa class of formulas. It is said that Mhas overspill Γon N, M|= N−O(Γ), if for all ϕ(x, u) ∈Γ, c ∈Mand β>ω, if ∀n∈ω∃m>n[M|=ϕ(m,c)] then there is δ<βnonstandard such that M|=ϕ(δ, c). This is a weak notion of overspill; any Δ0-recursively saturated model of PA−has N−O(Δ0). Nevertheless, sometimes it is a good substitute for Δ0-recursive saturation; for example 3.8.(2) is true for models of IEke+N−O(Δ0), thus several results of Fig. 2could be refined for these kinds of models. Theorem 4.10 will show that, in models satisfying N−O(Γ), the regularity property can be refined by replacing the FP-sets with (standard) powers of an element. This will allow another alternative axiom of IΔ0using the formula exp (Corollary 4.14). Definition 4.9. A set A ⊆M|=PA−is said to be dense for standard powers if ∀c∀n∈ω[[0,c]∩A=∅=⇒∃a<c∃m>n(a, am∈A)] In the following theorem the density for standard powers for gaps (Fig. 3) is stated: Theorem 4.10. Let M|=RIE 1 0+¬IEk, and ϕ(x) ∈Ekbe an id(·)-gap. Then there exists ψ∈{ϕ, ϕ}such that ψ(M)is dense in standard powers. Proof. The function f(x) := x2has a continuous extension βf :βM →βM. That function has not any fixed point in βM \{0, 1}by Result 2.6. 25 Since f[(ϕ, √b)] ⊆(ϕ, b), it follows that (ϕ, b) ∈βf(p), for all p ∈Hϕand b >ϕ, so it defines the restriction βf Hϕ:Hϕ→Hϕ Therefore it can be considered the dynamic system: (Hϕ,{(βf)n}n∈ω+) on the compact space Hϕ(ω+=ω\{0}). By Result 2.7 there exist p ∈Hϕand r∈β(ω+)such that (βf)r(p) =p. That means that for all A ∈pthat is, for all Aneighborhood of p {n∈ω+:(βf)n(p)∈A}∈r. Since (βf)n=β(fn)and fn[A] ∈β(fn)(p), it follows that {n∈ω+:fn[A]∩A=∅} ∈ r. Since ris not principal (because 0, 1 /∈Hϕ), ∀n∃m>n[fm[A]∩A=∅](†) Let ψ∈{ϕ, ϕ}such that the set A =ψ(M) ∩(ϕ, c) belongs in p. Then, by (†), ∀n∃m>nsuch that M|=∃x<c[ψ(x)∧ψ(x2m)] (x2mdenotes the term x (2m) ··· x). Finally observe that the choice of ψis true for all c >ϕ(like in 4.4).  We will use again the index ke(see 2.3) to show, in models of IEke+N-O(Ek), a nonlinear relation near the gap. Definition 4.11. A set A ⊆M|=PA−is said to be dense for powers if ∀c[0,c]∩A=∅=⇒∃a∈A∃δ>ω(a, aδ∈A) Corollary 4.12. Under the conditions of Theorem 4.10, if M|=IE ke+N-O(Ek), then there is ψ∈{ϕ, ϕ} such that ψ(M)is dense for powers. Proof. Let k>k eLet xy=zbe the formula defined in Sect. 2. It has that, for all n ∈ω, IEkex(n) ···x=y→xn=y By 4.10, we have that for all n ∈ωthere is m >nsuch that M|=∃x, y < c(xm=y∧ψ(x)∧ψ(y)) Since the formula is Ek(1 ≤ke≤k), by applying N−O(Ek), the result is concluded.  Corollary 4.13. If M|=IE ke+¬IEk+N−O(Ek), then Mis k-low.