The Order of Reflection
J. P. Aguilera


[2010]03D60, 03E45 (Primary); 03D40, 03E10.

Institute of Discrete Mathematics and Geometry, Vienna University of Technology. Wiedner Hauptstraße 8–10, 1040 Vienna, Austria.
aguilera@logic.at

The Order of Reflection
    J. P. Aguilera
    December 30, 2023
=======================


Extending Aanderaa's classical result that π^1_1 < σ^1_1, we determine the order between any two patterns of iterated Σ^1_1- and Π^1_1-reflection on ordinals. We show that this linear reflection order is a prewellordering of length ω^ω.
This requires considering the relationship between linear and some non-linear reflection patterns, such as σ^1_1∧π^1_1, the pattern of simultaneous Σ^1_1- and Π^1_1-reflection.


The proofs involve linking the lengths of α-recursive wellorderings to various forms of stability and reflection properties satisfied by ordinals α within standard and non-standard models of set theory.






§ INTRODUCTION

Let L_α denote the αth level of Gödel's constructible hierarchy, given by L_0 = ∅, L_α+1 = all sets definable over L_α with parameters, and L_η = ⋃_α<η L_α at limit stages. In α-recursion theory, one lifts the usual notion of “computation” over the natural numbers (or, equivalently, over L_ω) to L_α, for sufficiently closed α. As became evident from early work by Kreisel, Kripke, Platek, Sacks, Takeuti, and others (see e.g., Simpson <cit.>), facts about recursion on L_α can be translated into facts about recursion on L_ω in various ways. In particular, the termination of simple inductive definitions of sets of natural numbers is deeply connected with the reflecting structure of L (see e.g., Cenzer <cit.> or Aczel and Richter <cit.>). The purpose of this article is to study the order in which various reflecting properties given in terms of iterated Σ^1_1- and Π^1_1-reflection first occur in the constructible hierarchy.


A formula in the language of set theory is Σ^1_1 if it contains only existential second-order quantifiers (i.e., ranging over classes) followed by arbitrary first-order quantifiers.
An ordinal α is said to be Σ^1_1-reflecting Σ^1_1-reflecting if whenever ϕ is a Σ^1_1 formula in the language of set theory and a_1,, a_n are finitely many elements of L_α, then

    L_αϕ(a_1,, a_n)  implies ∃β<α (a_1,, a_n ∈ L_β∧ L_βϕ(a_1,, a_n)).

Given a class of ordinals X, an ordinal α is said to be Σ^1_1-reflecting on X if one can additionally demand that the ordinal β above belong to X. 
The least Σ^1_1-reflecting ordinal is denoted by σ^1_1, and π^1_1 is defined dually. 

An ordinal α is said to be β-stable if L_α is a Σ_1-elementary substructure of L_β; in symbols: stability

    L_α≺_1 L_β.

Given an ordinal α, write α^+ for the smallest admissible ordinal greater than α. 
Aczel and Richter <cit.> showed that π^1_1 ≠σ^1_1 and that a countable ordinal α is Π^1_1-reflecting if, and only if, it is α^+-stable.
Afterwards, Aanderaa <cit.> showed that π^1_1 < σ^1_1. Gostanian <cit.> showed that σ^1_1 is smaller than the least α which is (α^++1)-reflecting; in fact, he showed that any α which is both (α^++1)-stable and locally countable is also Σ^1_1-reflecting. Later Gostanian and Hrbacek <cit.> employed Gostanian's method to give a new proof of Aanderaa's theorem. A third, apparently folklore proof appears in Simpson <cit.>. Aanderaa's theorem is also an immediate consequence of Proposition <ref> below, although the proof of Proposition <ref> has a similar flavor to the argument in Simpson <cit.>.

Let us now generalize the definitions of σ^1_1 and π^1_1 as follows:

The notion of a reflection pattern is given inductively: the empty set is a reflection pattern; if s and t are reflection patterns, then so too are s∧ t, σ^1_1(s), and π^1_1(s).

We write σ^1_1 for σ^1_1(∅) and π^1_1 for π^1_1(∅). σ^1_1


A reflection pattern is linear if it contains no conjunctions, and non-linear otherwise.



An ordinal is said to be σ^1_1(∅)-reflecting if it is Σ^1_1-reflecting; it is said to be π^1_1(∅)-reflecting if it is Π^1_1-reflecting.
Let s and t be reflection patterns. Inductively, an ordinal α is said to be σ^1_1(s)-reflecting if it reflects Σ^1_1 statements onto s-reflecting ordinals; it is said to be π^1_1(s)-reflecting if it reflects Π^1_1 statements onto s-reflecting ordinals; it is said to be s∧ t-reflecting if it is both s-reflecting and t-reflecting.

We may alternate between uppercase Σ and Π and lowercase σ and π in speaking about patterns of reflection.

The ordering problem is: given two reflection patterns s and t, determine whether the least s-reflecting ordinal is smaller than the least t-reflecting ordinal.
We will identify a pattern s with the least s-reflecting ordinal. Thus, instances of the ordering problem are e.g., determining whether

    σ^1_1(σ^1_1) <σ^1_1(π^1_1(σ^1_1∧π^1_1))

or whether

    π^1_1(σ^1_1) < π^1_1(σ^1_1) ∧π^1_1(π^1_1).

Other related problems emerge. For instance, one may ask whether σ^1_1(σ^1_1) is the least Σ^1_1-reflecting ordinal which is also a  limit of Σ^1_1-reflecting ordinals.
(Incidentally, the answer to all three questions is “no.”) 

In this article, we solve the ordering problem for linear patterns of reflection: we exhibit a way of assigning ordinals to linear patterns in a way that respects their ordering; in particular, we show:


The linear order of reflection is a prewellordering of length ω^ω.


The proof requires analyzing the structure of the non-linear, or full, reflection order, to a certain extent. We shall see that all reflection patterns are witnessed for the first time by ordinals between the least α which is α^+-stable and the least α which is (α^++1)-stable. In addition, we show:


The linear reflection order is cofinal in the full reflection order.


This raises the question of whether the full reflection order also has length ω^ω. This turns out to be false:


The patterns π^1_1, σ^1_1, σ^1_1∧π^1_1, and σ^1_1(σ^1_1) have ranks 1, ω, ω^2, and ω^ω in the reflection order, respectively.


In the course of proving these theorems, we find various easier results which we believe to be of independent interest; these are labelled “propositions.”






  
Theorem The length of the linear reflection order is ω^ω. In the full reflection order, the reflection patterns π^1_1, σ^1_1, σ^1_1∧π^1_1, and σ^1_1(σ^1_1) have ranks 1, ω, ω^2, and ω^ω, respectively. The linear patterns are cofinal in the reflection order. All reflection patterns are first witnessed by ordinals between the least α which is α^+-stable, and the least α which is (α^++1)-stable.





  
Outline The article is divided into seven sections. In Section <ref>, we study connections between the degree of stability of an ordinal σ and the lengths of σ-recursive wellorderings. In Section <ref>, we prove various reflection transfer results, of the form “if σ is s-reflecting, then it is also t-reflecting.” As an application thereof, we show, in Section <ref>, that the rank of the pattern σ^1_1(σ^1_1) in the reflection order is ω^ω, and, in Section <ref>, that the length of the conjunction-free part of the reflection order is also ω^ω. We finish in Section <ref> with some remarks on the length of the reflection order and its generalizations.





  
Convention Even if not mentioned explicitly, every ordinal in this article is assumed to be both countable and locally countable (i.e., for all β <α, there is a surjection from ω to β in L_α). These are the hypotheses for the theorems of Gostanian and Aczel-Richter mentioned above, respectively.  locally countable







§ STABILITY AND GANDY ORDINALS

For an admissible ordinal α, write δ_α

    δ_α = sup{δ: δ is the length of an α-recursive wellordering of a subset of α},

where a subset of α is said to be α-recursive α-recursive if it is Δ_1-definable over L_α with parameters. The value of δ_α remains unchanged if one replaces “α-recursive” by “α-r.e.” in the definition. For every admissible α, δ_α is easily seen to be a limit and e.g., additively indecomposable.
We always have δ_α≤α^+; an ordinal α is Gandy if δ_α = α^+. Gostanian <cit.> showed that σ^1_1 is the smallest ordinal which is not Gandy. In fact, he showed that a locally countable ordinal is not Gandy if, and only if, it is Σ^1_1-reflecting. Abramson and Sacks <cit.> showed that (ℵ_ω^L)^+ is Gandy, so not every Gandy ordinal is locally countable.


Since we know what the degree of stability of π^1_1 is (viz. (π^1_1)^+),
a possible first question is that of the degree of stability of σ^1_1. 


σ^1_1 is not (δ_σ^1_1+1)-stable.

Let δ = δ_σ^1_1. 
Since δ<(σ^1_1)^+, it is not admissible. As we observed before, δ is a limit ordinal; thus, the failure of admissibility must be due to an instance of collection. Choose some Δ_0 formula ψ such that for some a⃗∈ L_δ, L_δψ(a⃗)-collection.
To see that σ^1_1 is not (δ+1)-stable, consider the formula ϕ in the language of set theory asserting that there are sets A, B such that:


  *  A and B are transitive sets satisfying V=L, A is admissible, A ∈ B, and there is a⃗∈ B such that B does not satisfy ψ(a⃗)-collection;

  *  for each (∩ A)-recursive linear ordering R ∈ B, either there is an infinite descending sequence b through R with b∈ A, or there is an ordinal β∈ B and an isomorphism f ∈ B from R to β;

  *  for each β∈ B, there is an (∩ A)-recursive linear ordering R ∈ B and an isomorphism f ∈ B from R to β.

Notice that ϕ is a Σ_1 formula, since the only unbounded quantifier is the one on B. Moreover, it does not hold in L_σ^1_1, for the sets A and B would need to be of the form L_α and L_β, with α<β<σ^1_1. Conditions (<ref>) and  (<ref>) together imply that β = δ_α, but Gostanian's characterization of σ^1_1 then implies β = α^+, contradicting condition (<ref>). Finally, it does hold in L_δ+1, as witnessed by A = L_σ^1_1 and B = L_δ. To see that (<ref>) holds, recall a theorem of Gostanian <cit.> by which if α is Σ^1_1-reflecting, then every α-recursive linear ordering  which is not a wellordering has an infinite descending sequence in L_α. Thus, every σ^1_1-recursive linear ordering R either has an infinite descending sequence in L_σ^1_1, or else is isomorphic to some ordinal β<δ. One can construct an isomorphism witnessing this by transfinite recursion: at stage γ<β, one has defined f↾γ and sets f(γ) equal to the R-least element not in the range of f↾γ. Since this process takes β-many stages and R ∈ L_σ^1_1+1, such an isomorphism belongs to L_σ^1_1 + δ. Since δ is additively indecomposable, it belongs to L_δ. The proof that (<ref>) holds is similar.


The proof of Proposition <ref> shows:

Suppose σ is Σ^1_1-reflecting and (δ_σ+1)-stable. Then, it is a limit of Σ^1_1-reflecting ordinals.


One cannot improve the conclusion of Proposition <ref>—every Σ^1_1-reflecting ordinal is stable to the supremum of its recursive wellorderings:

Suppose σ is Σ^1_1-reflecting. Then σ is δ_σ-stable.

Since δ is a limit ordinal, it suffices to consider arbitrary γ<δ and show that

    L_σ≺_1 L_γ.

Let a ∈ L_σ and ϕ be a Σ_1-formula such that
L_γϕ(a).
Without loss of generality, assume that a is an ordinal.
Let R be a σ-recursive wellordering of length γ. In particular, R is σ-r.e., so there is a Σ_1 formula ψ,  such that for all x,y ∈ L_σ, 

    xRy ↔ L_σψ(x,y).

Let us assume for notational simplicity that ψ is defined without parameters.
Given an ordinal σ', let R_σ' be the binary relation given by

    xR_σ' y ↔ L_σ'ψ(x,y).

Since ψ is Σ_1, we have R_σ'⊂ R_τ whenever σ'≤τ≤σ. In particular, R_σ' is wellfounded for all σ'<σ.

Because L_γϕ(a), there is a subset A of L_σ such that


  * A codes a model (M, E) of + V = L;

  * M has a largest admissible ordinal τ and (τ, E) is isomorphic to (σ, ∈);

  * there is an ordinal β of M and a function f ∈ M which is an isomorphism between R_τ^M (i.e., R_τ computed within M) and β, and L_β^Mϕ(a).

The existence of such an A can be expressed by a set-theoretic Σ^1_1 formula over L_σ with parameter a (as well as any other parameters involved in the definition of R).

By Σ^1_1-reflection, there is some σ'<σ and some A_σ'⊂ L_σ' such that a ∈ L_σ' and


  *  A_σ' codes a model (N, F) of + V = L;

  *  N has a largest admissible ordinal η and (η, F) is isomorphic to (σ',∈);

  *  there is an ordinal b of N and a function g ∈ N which is an isomorphism between R_η^N  and b, and L_b^Nϕ(a).

Here and for the rest of our lives, let us identify the wellfounded part of N with its transitive collapse.
Condition (<ref>)  implies that L_σ'∈ N.
By (<ref>), there is an ordinal b of N and an isomorphism g ∈ N from R_σ' to b. 
Because R_σ'⊂ R, it is wellfounded, and so b really is an ordinal. Now, L_bϕ(a), and N has no admissible ordinals above σ', so b<(σ')^+<σ. Since ϕ is Σ_1, we conclude that L_σϕ(a), as was to be shown.


We have shown that σ^1_1 is δ_σ^1_1-stable and not (δ_σ^1_1+1)-stable. 
The proof of Proposition <ref> illustrates how one derives consequences of an ordinal being Σ^1_1-reflecting. We shall carry out many similar arguments in the future, perhaps omitting some of the details that show up repeatedly.
We note the following consequence of Proposition <ref>:


There is a Σ^1_1-sentence ϕ such that for every countable, locally countable σ, L_σϕ if, and only if, σ is Σ^1_1-reflecting or Π^1_1-reflecting.

Let ϕ be the sentence that asserts the existence of some A⊂ L_σ coding a model (M,E) of + V = L containing σ and such that 

    M  L_σ≺_1 L_δ_σ.

Clearly, every Π^1_1-reflecting ordinal satisfies this sentence, as does every Σ^1_1-reflecting ordinal, by Proposition <ref>. 

Suppose that L_σϕ, as witnessed by (M,E). Suppose moreover that σ is not Σ^1_1-reflecting, so that δ_σ = σ^+ by Gostanian's characterization. 
Since σ∈ M, a well-known theorem of F. Ville Ville's Theorem (see e.g., Barwise <cit.> for a proof) implies that L_σ^+⊂ M. 
Given an arbitrary β<σ^+, we then have β∈ M and β< δ_σ^M, for otherwise δ_σ^M<σ^+, which is impossible, since any σ-recursive wellordering of a subset of σ of length δ_σ^M would belong to M.
By choice of M,

    M  L_σ≺_1 L_δ_σ,

and so M L_σ≺_1 L_β. However, being Σ_1-elementary is absolute, so we really do have L_σ≺_1 L_β and, since β was arbitrary, we have L_σ≺_1 L_σ^+, so σ is Π^1_1-reflecting.


An immediate consequence is Aanderaa's classical result:

π^1_1<σ^1_1.


Corollary <ref> holds in a strong form:
 
σ^1_1 reflects Σ^1_1 sentences on Π^1_1-reflecting ordinals.

Let ϕ be the sentence from Proposition <ref>. Then, if ψ is another Σ^1_1 sentence, so is the conjunction ϕ∧ψ.
Corollary <ref> is not new; it also follows from the proof of Corollary <ref> written down in Simpson <cit.>. Our method for analyzing the reflection order is to prove results akin to Corollary <ref>. Now that we know the degree of stability of σ^1_1, it is natural to ask what the least ordinal α which is (δ_α+1)-stable is. We shall eventually see that it is rather small and in fact smaller than the successor of σ^1_1 in the reflection order. We finish this section with some related results that will not be used in future sections.



Suppose σ is locally countable and Σ^1_1-reflecting on Σ^1_1-reflecting ordinals. Then σ is (δ_σ+1)-stable.

This is similar to the proof of Proposition <ref>. Again, it is easy to see that δ is a limit. Let γ = δ_σ+1 and a ∈ L_σ be such that L_γϕ(a), for some Σ_1 formula ϕ. Let ψ be the Σ^1_1 formula expressing that σ is locally countable and there is a set A⊂ L_σ coding a model (M,E) of + V = L with σ∈ M and such that

    M“L_δ_σ+1ϕ(a).”

Then L_σψ. By hypothesis, there is a Σ^1_1-reflecting τ<σ such that L_τψ. Thus, τ is locally countable and there is a model (M,E) of + V = L with τ∈ M and such that

    M“L_δ_τ+1ϕ(a).”

By Ville's theorem, L_τ^+⊂ M and, since τ is Σ^1_1-reflecting, δ_τ < τ^+. Hence, M computes δ_τ and δ_τ+1 correctly and so we really have L_δ_τ+1ϕ(a). Since ϕ is Σ_1, we conclude L_σϕ(a), as desired.


The preceding proof shows that if σ is as in Proposition <ref>, then σ is (δ_σ+2)-stable, (δ_σ)^ω-stable, etc. It shows that if f is a function on ordinals which is uniformly Σ_1-definable (with parameters in L_σ) on e.g., multiplicatively indecomposable levels of L containing all parameters, then σ is f(δ_σ)-stable.


We denote by σ^1,ℓ_1 the least Σ^1_1-reflecting ordinal which is a limit of Σ^1_1-reflecting ordinals.



σ^1,ℓ_1 is smaller than the least α which is (δ_α+1)-stable.

Let α be as in the statement. We claim that α is Σ^1_1-reflecting. Otherwise, δ_α = α^+, and so α is (α^++1)-stable. But surely α is locally countable, and thus Σ^1_1-reflecting, by Gostanian's result mentioned in the introduction.
Thus, α is Σ^1_1-reflecting. By Corollary <ref>, α is a limit of Σ^1_1-reflecting ordinals. However, this is expressible in L_α; thus, the proof of Proposition <ref> shows that α is a limit of ordinals which are both Σ^1_1-reflecting and limits of Σ^1_1-reflecting ordinals.


As a consequence, we obtain a negative answer to one of the questions posed in the introduction. 


σ^1,ℓ_1 does not reflect Σ^1_1 statements onto Σ^1_1-reflecting ordinals.


We state without proof a result implying that σ^1,ℓ_1<π^1_1(σ^1_1). Its proof is similar to that of the more powerful Theorem <ref> below.


For every α<π^1_1(σ^1_1), there is some σ<π^1_1(σ^1_1) which is both Σ^1_1-reflecting and (δ_σ+α)-stable. 


Figure <ref> summarizes the relationships between the ordinals considered so far. We shall also see that 

    π^1_1(σ^1_1) < σ^1_1(σ^1_1).















§ REFLECTION TRANSFER THEOREMS
 
In this section, we will present some results on the transfer of reflection properties, i.e., results of the form

    if σ is s-reflecting, then it is t-reflecting,

where s and t are reflection patterns. Recall our convention that every ordinal considered is countable and locally countable. 
In order to study the reflection order, we focus on ordinals that are small enough. This is not necessary, but will simplify arguments.

We say that α is  subreflecting if for no β≤α do we have L_β“for every reflection pattern n, (σ^1_1)^n exists.”[Replace arbitrary reflection patterns by those of the form (σ^1_1)^n.]

Below, we will prove that the sequence 

    (σ^1_1, σ^1_1(σ^1_1), σ^1_1(σ^1_1(σ^1_1)), )

is cofinal in the reflection order.
Thus, α is subreflecting if, and only if, it is smaller than some reflection ordinal; but the definition given above is more useful, as it is absolute to initial segments of L without strong closure properties. 
The first five reflection transfer results we present are rather elementary:

Let s be a reflection pattern and σ be an ordinal.


  * If σ is Σ^1_1(σ^1_1(s))-reflecting, then σ is Σ^1_1(s)-reflecting.

  * If σ is Π^1_1(π^1_1(s))-reflecting, then σ is Π^1_1(s)-reflecting.


If σ is Σ^1_1(σ^1_1(s))-reflecting and L_σ satisfies a Σ^1_1 sentence ϕ, then, by definition, there is a Σ^1_1(s)-reflecting τ<σ such that L_τϕ. By Σ^1_1(s)-reflection, there is an s-reflecting η<τ such that L_τϕ. Hence, σ is Σ^1_1(s)-reflecting. The argument for Π^1_1(π^1_1(s))-reflection is similar.



Let s and t be reflection patterns and σ be an ordinal.


  *  If σ is σ^1_1(s)∧π^1_1(t)-reflecting, then it is π^1_1(σ^1_1(s)∧ t)-reflecting.

  *  If σ is σ^1_1(s)∧π^1_1(t)-reflecting, then it is σ^1_1(s∧π^1_1(t))-reflecting.

  *  If σ is σ^1_1(s)-reflecting, then it is σ^1_1(s∧π^1_1)-reflecting.


Recall that if an ordinal σ is s-reflecting, for any nontrivial reflection pattern s, then it is recursively inaccessible and, in fact, a limit of recursively inaccessible ordinals. (<ref>) then follows from the simple observation that being Σ^1_1(s)-reflecting is expressible by a Π^1_1 sentence ψ. Thus, if σ is σ^1_1(s)∧π^1_1(t)-reflecting and satisfies some Π^1_1-sentence ϕ, then the conjunction ϕ∧ψ is also Π^1_1, and any ordinal satisfying it must be Σ^1_1(s)-reflecting.

(<ref>) is similar. For (<ref>), there are two cases: if σ is Π^1_1-reflecting, then the result follows from (<ref>). If σ is not Π^1_1-reflecting, it is not σ^+-stable.
Hence, there is a least γ<σ^+ such that σ is not γ-stable, i.e., there is a Σ_1-formula ψ and some parameter α<σ such that L_γψ(α), but L_σψ(α).  The remainder of the proof is an adaptation of the proof of Corollary <ref> presented in Simpson <cit.>:

Let ϕ be the Σ^1_1-statement expressing that there is a model (M,E) of + V = L end-extending L_σ+1 such that for some γ' ∈ M with γ'<σ^+M, L_γ'^Mψ(α) and, moreover, if γ' is least such, then M“σ is (<γ')-stable.” Then L_σϕ. By choice of σ, there is an s-reflecting ordinal τ<σ such that L_τϕ. 
This means that there is a model (M,E) of + V = L end-extending L_τ+1 such that for some γ'∈ M with γ' < τ^+M, L^M_γ'ψ(α) and, for the least such γ', we have M“τ is (<γ')-stable.”. Since ψ is Σ_1 and L_σψ(α), γ' must belong to the illfounded part of M. So τ is s-reflecting and, as in the proof of Proposition <ref>, τ is Π^1_1-reflecting. By taking conjunctions as before, one sees that every Σ^1_1 satisfied by L_σ is satisfied by some (s∧π^1_1)-reflecting τ<σ, as was to be shown.


 
We claim that

    σ^1_1(π^1_1(σ^1_1)) < σ^1_1(σ^1_1).

To see this, notice that Lemma <ref>(<ref>) and  <ref>(<ref>) imply that

    σ^1_1∧π^1_1 = σ^1_1∧π^1_1(σ^1_1) = σ^1_1(π^1_1(σ^1_1))∧π^1_1 = σ^1_1∧π^1_1(σ^1_1(π^1_1(σ^1_1)))

and thus that

    σ^1_1(π^1_1(σ^1_1)) < σ^1_1∧π^1_1.

On the other hand, Lemma <ref>(<ref>) implies that

    σ^1_1(σ^1_1) = σ^1_1(σ^1_1∧π^1_1),

and so

    σ^1_1(π^1_1(σ^1_1)) < σ^1_1∧π^1_1 < σ^1_1(σ^1_1),

as claimed. 
A natural question is whether one can strengthen π^1_1 in the statement of Lemma <ref>(<ref>) and, in particular, whether σ^1_1 is σ^1_1(π^1_1(π^1_1))-reflecting. 
By generalizing the proof of Lemma <ref>(<ref>), we see that the answer is “yes.”

 
Let s be a reflection pattern. An ordinal α is β-stable on s if whenever L_β satisfies a Σ_1 sentence ϕ(L_α) with additional parameters in L_α, there is an s-reflecting γ<α such that L_γ^+ϕ(L_γ). stability!on a reflection pattern

We caution the reader that an ordinal α being β-stable on ∅ is not the same as it being β-stable, for the first definition allows L_α as a parameter. We do have the following:


Let s be a reflection pattern. The following are equivalent:


  * α is α^+-stable on s;

  * α is Π^1_1(s)-reflecting.


We omit the proof of Lemma <ref>, which is a simple adaptation of Aczel and Richter's characterization of Π^1_1-reflection.


Let s be a reflection pattern.
Suppose σ is σ^1_1(s)-reflecting.  Then, it is σ^1_1(s∧π^1_1(s))-reflecting.

The conclusion of the theorem follows from Lemma <ref> if σ is π^1_1(s)-reflecting, so we may assume that it is not. 

Since σ is not π^1_1(s)-reflecting, it is not σ^+-stable on s, so there is a least β<σ^+ and a Σ_1-formula ∃ x ϕ(y,x) such that L_β∃ x ϕ(L_σ,x) and whenever γ<σ and γ is s-reflecting, then L_γ^+∃ x ϕ(L_γ,x). Let ψ be the formula expressing that there is a model M of + V = L such that


  * M contains σ.

  * M “∃ x ϕ(L_σ,x) and, letting γ be least such that Mϕ(L_σ,a) for some a ∈ L_γ, σ is <γ-stable on s.”

By reflection, there is τ<σ with L_τψ, as witnessed by some model N which end-extends L_τ^+. Since σ is σ^1_1(s)-reflecting, we may assume that τ is s-reflecting.
Let γ be N-least such that N∃ x∈ L_γ ϕ(L_τ,x). Then, we cannot have γ < τ^+, for otherwise τ is an s-reflecting ordinal such that L_τ^+∃ x ϕ(L_τ,x), contradicting the choice of ϕ. Thus, γ belongs to the illfounded part of N and, in N, τ is <γ-stable on s. Since τ is recursively inaccessible (this can be assumed also if s = ∅), N is correct about s-reflection below τ, so an argument as before shows that τ is τ^+-stable on s and thus Π^1_1(s)-reflecting.



By repeatedly applying Theorem <ref>, we obtain

    σ^1_1 = σ^1_1(π^1_1) = σ^1_1(π^1_1(π^1_1)) = σ^1_1(π^1_1(π^1_1(π^1_1))) =  ….

This implies the sequence 
of inequalities 

    π^1_1 < π^1_1(π^1_1) < π^1_1(π^1_1(π^1_1)) < … < σ^1_1,

which strengthens Corollary <ref>. 


The following strengthening of Proposition <ref> is proved similarly:

Suppose σ is Σ^1_1(s)-reflecting. Then, it is δ_σ-stable on s.

Let θ(L_σ) be a Σ_1 sentence with parameters in L_σ, say, of the form ∃ x θ_0(x,L_σ). Let η<δ_σ and b ∈ L_η be such that L_δ_σθ_0(b,L_σ). Since η<δ_σ, there is a σ-recursive wellorder R of length η. Let ψ be the sentence asserting the existence of a model M of  such that[ is the extension of  by an axiom asserting that every set is contained in an admissible set.]


  * M end-extends L_σ+1;

  * in M, R is isomorphic to an ordinal η_0 and there is b_0 ∈ L_η_0^M such that L_η_0^M θ_0(b_0,L_σ).

Then L_σψ. Moreover, ψ is Σ^1_1 so, by reflection, there is an s-reflecting τ<σ such that L_τψ, as witnessed by some model N which end-extends L_τ^+. Now, in N, L_τ^+^Nθ_0(b_0, L_τ) for some b_0 ∈ L^N_η_0, where η_0 is some N-ordinal isomorphic to R_τ. However, R_τ⊂ R, since R is σ-recursive, and θ_0 is Σ_0, so we really have L_τ^+θ(L_τ), as desired.


The following theorem, although perhaps odd-looking at first, is crucial for our analysis of the reflection order.


Let s be a reflection pattern.
Suppose σ is Π^1_1(σ^1_1(s))-reflecting but not Σ^1_1-reflecting. Then σ is Π^1_1(s)-reflecting.

Suppose σ is Π^1_1-reflecting on Σ^1_1(s)-reflecting ordinals but not Σ^1_1-reflecting.
Let ψ be the statement expressing that whenever (M,E) is an end-extension of L_σ+1 satisfying , then M“σ is not Σ^1_1(s)-reflecting.” This sentence is Π^1_1 and thus cannot be satisfied by L_σ, for otherwise it would be reflected to a Σ^1_1(s)-reflecting ordinal. But clearly L_α cannot satisfy ψ if α is Σ^1_1(s)-reflecting.

Thus, L_σψ, so there is a model M of  end-extending L_σ+1 such that

    M“σ is Σ^1_1(s)-reflecting.”


For ordinals τ<σ, whether τ is t-reflecting is computed correctly by, say, τ^++, and thus too by M, for any reflection pattern t. By Lemma <ref> applied within M, 

    M“σ is δ_σ-stable on s.”


Let ϕ be a Π^1_1 statement, and a ∈ L_σ be a parameter such that L_σϕ(a). By Barwise-Gandy-Moschovakis <cit.>, there is a Σ_1 formula ϕ^* such that for all admissible α with a ∈ L_α, L_αϕ(a) if, and only if, L_α^+ϕ^*(a,L_α); thus, L_σ^+ϕ^*(a,L_σ). Let b ∈ L_σ^+ be a witness for ϕ^* and let γ<σ^+ be large enough so that b ∈ L_γ. Since σ is not Σ^1_1-reflecting (in the real world), δ_σ = σ^+, and thus

    γ < δ_σ^M.

Since ϕ^* is Σ_1,

    M“L_δ_σϕ^*(a,L_σ),”

so by the δ_σ-stability of σ on s within M, there is an s-reflecting τ<σ such that 

    M“L_τ^+ϕ^*(a,L_τ).”

Since τ^+ < σ, we really do have 

    L_τ^+ϕ^*(a,L_τ),

and so L_τϕ(a). This completes the proof of the theorem.



The assumption that σ is not Σ^1_1-reflecting cannot be removed from the statement of Theorem <ref>. To see this, let s be the trivial pattern. By Lemma <ref>(<ref>), σ^1_1∧π^1_1 is Π^1_1(σ^1_1)-reflecting. However, σ^1_1∧π^1_1 is not Π^1_1(π^1_1)-reflecting, for being Σ^1_1-reflecting is expressible by a Π^1_1-formula, and thus every ordinal which is (σ^1_1∧π^1_1(π^1_1))-reflecting is also
π^1_1(σ^1_1∧π^1_1)-reflecting and, in particular, a limit of (σ^1_1∧π^1_1)-reflecting ordinals.


One cannot improve the statement of Theorem <ref> to conclude that σ is Π^1_1(σ^1_1(s)∧ s)-reflecting, for let s = π^1_1. Then, π^1_1(σ^1_1(π^1_1)) = π^1_1(σ^1_1) by Lemma <ref>(<ref>). However, as in Example <ref>,

    π^1_1(σ^1_1) < σ^1_1(π^1_1(σ^1_1)) < σ^1_1∧π^1_1.

This is in contrast to Theorem <ref>.


Let s be a reflection pattern and suppose σ is subreflecting and Σ^1_1(s)-reflecting. Then,


  * σ is Σ^1_1(π^1_1(s))-reflecting; moreover,

  * if s is of the form π^1_1(t), or even a conjunction of words of the form π^1_1(t), then σ is σ^1_1(π^1_1(s)∧ s)-reflecting.


The theorem requires two separate arguments: one in case σ is Π^1_1-reflecting, and one in case it is not. Suppose first that σ is Π^1_1-reflecting, so 

    σ is (σ^1_1(s)∧π^1_1)-reflecting.

Applying Lemma <ref> twice, 
one sees that σ is t-reflecting, where

    t = σ^1_1(s∧π^1_1(σ^1_1(s)))∧π^1_1(σ^1_1(s))).

In particular,

    σ is σ^1_1(s∧π^1_1(σ^1_1(s)))-reflecting.

Now, suppose that σ is not t_0-reflecting, where 

    t_0 = σ^1_1(s∧π^1_1(σ^1_1(s))∧σ^1_1),

i.e., suppose that there is a Σ^1_1 sentence ψ_0 satisfied by L_σ, but not by any L_τ such that τ<σ and τ is (s∧π^1_1(σ^1_1(s))∧σ^1_1)-reflecting. Then, by taking its conjunction with ψ_0, any Σ^1_1 sentence satisfied by L_σ can be seen to be satisfied by some L_τ such that τ<σ and τ is (s∧π^1_1(σ^1_1(s)))-reflecting, but not Σ^1_1-reflecting. By Theorem <ref>, any such τ is π^1_1(s∧π^1_1)-reflecting and, in particular, π^1_1(s)-reflecting; thus (s∧π^1_1(s))-reflecting. 
This implies that σ is σ^1_1(π^1_1(s)∧ s)-reflecting, as desired. Note that this case can only occur if s is a conjunction of words of the form π^1_1(t), hence the two clauses in the statement of the theorem.

Suppose, on the contrary, that σ is in fact t_0-reflecting. Now, an application of Lemma <ref> shows that σ is t_0'-reflecting, where 

    t_0' = σ^1_1(s∧π^1_1(σ^1_1(s))∧σ^1_1(π^1_1(σ^1_1(s)))).

In particular,

    σ is σ^1_1(σ^1_1(π^1_1
    (σ^1_1(s))))-reflecting.

There are now two cases, according as σ is t_1-reflecting or not, where

    t_1 = σ^1_1(σ^1_1(π^1_1
    (σ^1_1(s))∧σ^1_1)).

If it is not, then an argument as before, making use Theorem <ref>, shows that σ is σ^1_1(σ^1_1(π^1_1(s)))-reflecting, and thus σ^1_1(π^1_1(s))-reflecting, by Lemma <ref>. If σ is in fact t_1-reflecting, then, by Lemma <ref>, it must also be t_1'-reflecting, where

    t_1' = σ^1_1(σ^1_1(π^1_1
    (σ^1_1(s))∧σ^1_1(π^1_1(σ_1^1(s))))),

and in particular,

    σ is σ^1_1(σ^1_1(σ^1_1
    (π^1_1
    (σ^1_1(s)))))-reflecting.

and one proceeds according as σ is t_2-reflecting or not, where t_2 is defined in the natural way, following this pattern.
Because σ is subreflecting, this process must end after finitely many steps, so there is a natural number m∈ℕ such that

    σ is (σ^1_1)^m(π^1_1(s))-reflecting.

It then follows from Lemma <ref> that σ is σ^1_1(π^1_1(s))-reflecting. Now, suppose additionally that s is a conjunction of words of the form π^1_1(t). Then, being s-reflecting is expressible by a Σ^1_1 sentence,
so that equation (<ref>) can be replaced by the stronger

    σ is σ^1_1(s∧σ^1_1(π^1_1
    (σ^1_1(s))))-reflecting,

which implies

    σ is σ^1_1(σ^1_1(s∧π^1_1
    (σ^1_1(s))))-reflecting.

Similarly, equation (<ref>) can be replaced by the stronger

    σ is σ^1_1(s∧σ^1_1(σ^1_1
    (π^1_1
    (σ^1_1(s)))))-reflecting,

which implies

    σ is σ^1_1(σ^1_1(σ^1_1
    (s∧π^1_1
    (σ^1_1(s)))))-reflecting.

The argument shows that there is a natural number m∈ℕ such that

    σ is (σ^1_1)^m(s∧π^1_1(s))-reflecting.

As above, this implies that σ is σ^1_1(s∧π^1_1(s))-reflecting. This proves the theorem in case σ is Π^1_1-reflecting.


It remains to prove that if a subreflecting ordinal σ is Σ^1_1(s)-reflecting but not Π^1_1-reflecting, then it is Σ^1_1(π^1_1(s))-reflecting.
Since σ is not Π^1_1-reflecting, it is not σ^+-stable.
Let γ<σ^+ be least such that for some a ∈ L_γ+1 and some Σ_1 formula χ, with parameters in L_σ, we have L_σ^+χ(a) but L_σ∃ x χ(x). 

Let ψ be the sentence asserting the existence of a model M of  such that 


  * M end-extends L_σ+1;

  * M “∃ x χ(x) and, letting β be least such that ∃ x ∈ L_β+1 χ(x), σ is β-stable”;

  * M “whenever L_δ_σ satisfies a Σ_1 sentence θ(L_σ) with parameters in L_σ, there is some s-reflecting τ<σ such that L_τ^+θ(L_τ).”

We first show that L_σψ. The second clause of ψ follows from the choice of χ, so we only need to verify the last one. Let θ(L_σ) be a Σ_1 sentence with parameters in L_σ, say, of the form ∃ x θ_0(x,L_σ). Let η<δ_σ and b ∈ L_η be such that L_δ_σθ_0(b,L_σ). Since η<δ_σ, there is a σ-recursive wellorder R of length η. Let ψ' be the sentence asserting the existence of a model M of  such that


  * M end-extends L_σ+1;

  * M“σ^+ exists”;

  * in M, R is isomorphic to an ordinal η_0 and there is b_0 ∈ L_η_0^M such that L_η_0^M θ_0(b_0,L_σ).

Then L_σψ'. Moreover, ψ' is Σ^1_1 so, by reflection, there is an s-reflecting τ<σ such that L_τψ', as witnessed by some model N which end-extends L_τ^+. Now, in N, L_τ^+^Nθ_0(b_0, L_τ) for some b_0 ∈ L^N_η_0, where η_0 is some N-ordinal isomorphic to R_τ. However, R_τ⊂ R, since R is σ-recursive, and θ_0 is Σ_0, so we really have L_τ^+θ(L_τ). Hence, L_σψ, as claimed. 

Since ψ is Σ^1_1, then, by reflection, some τ<σ such that L_τψ, as witnessed by some model N which end-extends L_τ^+. Now, N “∃ x χ(x) and, letting β be least such that ∃ x ∈ L_β+1 χ(x), τ is β-stable.” Since the witness for χ cannot belong to L_σ by assumption, it must belong to the illfounded part of N. Since N“τ is β-stable,” it follows that τ is τ^+-stable and hence Π^1_1-reflecting.

Now, we may assume that τ is not Σ^1_1-reflecting, for otherwise τ itself reflects ψ, and so there is some τ'<τ which is not Σ^1_1-reflecting and such that L_τ'ψ. We claim that τ is Π^1_1(s)-reflecting. By taking conjunctions as before, this finishes the proof.

To see that τ is Π^1_1(s)-reflecting, suppose that ϕ is a Σ_1-formula with parameters in L_τ. By choice of ψ, N “whenever L_δ_τ satisfies a Σ_1 sentence θ(L_τ) with parameters in L_τ, there is some s-reflecting β<τ such that L_β^+θ(L_β).”
Since ϕ is Σ_1 and N end-extends L_τ^+, we have L_b^Nϕ(L_τ), for any b in the illfounded part of N. Since τ is not Σ^1_1-reflecting, δ_τ^N belongs to the illfounded part of N, so—in particular—L_δ_τ^Nϕ(L_τ). Hence, there is some β<τ such that all relevant parameters belong to L_β,
and

    N“β is s-reflecting and L_β^+ϕ(L_β).”

Since τ is Π^1_1-reflecting, it is a limit of recursively inaccessible ordinals, so N is correct about s-reflection and β^+<τ.
It follows that β really is an s-reflecting ordinal such that L_β^+ϕ(L_β). Thus, τ is Π^1_1(s)-reflecting and 
σ is Σ^1_1(π^1_1(s))-reflecting, as was to be shown.

Now, suppose in addition that s is a conjunction of words of the form π^1_1(t), so that being s-reflecting is expressible by a Σ^1_1 sentence. Then, the ordinal τ above can be assumed to be s-reflecting. The argument shows that it is π^1_1(s)-reflecting; thus (s∧π^1_1(s))-reflecting.
This completes the proof of the theorem.



By combining Theorems <ref> and <ref>, one sees that 

    π^1_1(σ^1_1) = π^1_1(σ^1_1) ∧π^1_1(π^1_1) = π^1_1(σ^1_1) ∧π^1_1(π^1_1(π^1_1)) =

Since we have seen that these reflection patterns are all smaller than σ^1_1(σ^1_1) and σ^1_1∧π^1_1, it follows that  σ^1_1 and π^1_1(σ^1_1) have order-types ω and ω+1 in the reflection order, respectively.


Let us present a proof of the inequality

    π^1_1(σ^1_1∧π^1_1(σ^1_1∧π^1_1)) < σ^1_1(σ^1_1).

First, apply Theorem <ref> to see that

    σ^1_1(σ^1_1) = σ^1_1(σ^1_1∧π^1_1(π^1_1)).

Then, apply Lemma <ref> to see that 

    σ^1_1∧π^1_1(π^1_1) = σ^1_1∧π^1_1(σ^1_1∧π^1_1),
 
so that

    σ^1_1(σ^1_1∧π^1_1(π^1_1)) = σ^1_1(σ^1_1∧π^1_1(σ^1_1∧π^1_1)).

Finally, by Theorem <ref>, every σ^1_1(σ^1_1∧π^1_1(σ^1_1∧π^1_1))-reflecting ordinal is also σ^1_1(π^1_1(σ^1_1∧π^1_1(σ^1_1∧π^1_1)))-reflecting,
so that σ^1_1(σ^1_1) is a limit of π^1_1(σ^1_1∧π^1_1(σ^1_1∧π^1_1))-reflecting ordinals. 

We finish this section with a final reflection transfer theorem.
It is a strengthening of Theorem <ref> which clarifies the hypothesis on σ not being Σ^1_1-reflecting. We state it separately, however, since the proof is longer and the result is not used afterwards.


Suppose σ is π^1_1(σ^1_1(t∧π^1_1(s)))-reflecting. Then, one of the following holds:


  * σ is π^1_1(s)-reflecting; or

  * σ is σ^1_1(t∧π^1_1(s))-reflecting.


Suppose σ is π^1_1(σ^1_1(t∧π^1_1(s)))-reflecting but not π^1_1(s)-reflecting. Let θ be a Σ^1_1 sentence with parameters in L_σ such that

    L_σθ;

we need to find a (t∧π^1_1(s))-reflecting τ<σ such that

    L_τθ.

By Barwise-Gandy-Moschovakis <cit.>, Barwise-Gandy-Moschovakis there is a Π_1 formula θ^*(a) such that for every admissible α containing the parameters of θ, L_αθ if, and only if, L_α^+θ^*(L_α).
In particular, 

    L_σ^+θ^*(L_σ).


Since σ is not π^1_1(s)-reflecting, there is a least β<σ^+ such that σ is not β-stable on s. Because θ^* is Π_1,

    L_βθ^*(L_σ).

Let ϕ be the sentence asserting the non-existence of a model M of + V = L end-extending L_σ+1 in which σ is σ^1_1(t∧π^1_1(s))-reflecting. This is a Π^1_1 sentence and thus cannot be satisfied by any π^1_1(σ^1_1(t∧π^1_1(s)))-reflecting ordinal and, in particular, by σ. Thus, there is a model M of + V = L end-extending L_σ+1 and such that

    M“σ is σ^1_1(t∧π^1_1(s))-reflecting.”

Let χ be the sentence asserting the existence of a model N of + V = L such that


  * N contains σ;

  * in N, letting β be least such that σ is not β-stable on s, we have

    N“L_βθ^*(L_σ).”


Since β <σ^+ and M must end-extend L_σ^+, β∈ M and M is correct about β being the least ordinal at which σ fails to be stable on s.
Thus, we have

    M“L_σχ,”

as witnessed, say, by L^M_σ^+. Within M, σ is σ^1_1(t∧π^1_1(s))-reflecting and thus there is some τ<σ such that, 

    M“L_τχ,”

and so we really do have 

    L_τχ.

Moreover, M is correct about reflection below σ, so we may assume that τ is (t∧π^1_1(s))-reflecting. By the definition of χ, there is
a model N of + V = L such that


  * N contains τ;

  * in N, letting γ be least such that τ is not γ-stable on s, we have

    N“L_βθ^*(L_τ).”

 
Since τ is π^1_1(s)-reflecting, it is τ^+-stable on s, and thus γ cannot be a true ordinal smaller than τ^+. By Ville's Theorem, N must end-extend L_τ^+. Because θ^* is Π_1, it follows that

    L_τ^+θ^*(L_τ),

and thus, that

    L_τθ,

as was to be shown.





§ PATTERNS BELOW Σ^1_1(Σ^1_1)

In this section, we describe the reflection order below σ^1_1(σ^1_1). The remaining sections do not depend on this one, so the reader who so desires should feel free to skip ahead. To ease notation, we shall omit subscripts and superscripts and simply write σ for σ^1_1 and π for π^1_1. We shall also sometimes omit parentheses; thus, e.g., we will write

    σ∧πσ

instead of

    σ^1_1∧π^1_1(σ^1_1).

We will also express concatenation by direct juxtaposition, so that e.g., if s = σ∧π, then

    ss = σ∧π(σ∧π).

We remind the reader one last time of our convention on all ordinals being countable and locally countable.
 The following notation will be useful:

Let s and t be reflection patterns. We write s ≡ t if for every  ordinal α, α is s-reflecting if, and only if, it is t-reflecting.


Let k ∈ℕ and s be a reflection pattern.
We write c^k_0s = s; inductively,

    c_n+1^ks = σ∧π^kσπ c^k_ns.

We write c^k_n for c^k_ns, where s is the empty pattern.

We remark that, in particular, c^0_n = (σπ)^n.


For every n,k ∈ℕ and every reflection pattern s, every (σ∧π^k+1s)-reflecting ordinal is (π c^k_ns)-reflecting.

We first show by induction  on n that

    σ∧π^k+1≡σ∧π c^k_n.

Suppose that every (σ∧π^k+1)-reflecting ordinal is (π c^k_n)-reflecting, i.e., that

    σ∧π^k+1≡σ∧π c^k_n ≡σ∧π (c^k_n∧π^k).

After some applications of Lemma <ref>, we have

    σ∧π c^k_n
       ≡σπ c^k_n ∧π c^k_n
       ≡σπ c^k_n ∧π^k+1
       ≡σπ c^k_n ∧π^k+1σπ c^k_n
       ≡σ∧π^k+1σπ c^k_n
       ≡σ∧π(π^kσπ c^k_n)
       ≡σ∧π(σ∧π^kσπ c^k_n)
       ≡σ∧π c^k_n+1,

as desired. The argument given also shows that every every (σ∧π^k+1s)-reflecting ordinal is (σ∧π c^k_ns)-reflecting, although it does not prove the converse (which, incidentally, is not true).



For every n,k ∈ℕ, every l≤ k, and every reflection pattern s, every (σ∧π^k+1s)-reflecting ordinal is (π^k+1σπ c^l_ns)-reflecting.

Suppose α is (σ∧π^k+1s)-reflecting. By Lemma <ref>, 

    α is π c^k_n+1s-reflecting.

By definition,

    π c^k_n+1s ≡π(σ∧π^kσπ c^k_n s);

in particular,

    α is π^k+1σπ c^k_ns-reflecting.

We may thus apply Lemma <ref> n times to see that every c^k_n s-reflecting ordinal is also c^l_n-reflecting, from which the result follows.



Suppose m_0, m_1, , m_l are natural numbers all smaller than k. Then, for any reflection pattern s,

    c^k_1s ≡ c^k_1c^m_0_1 c^m_l_1σπ s.


We prove it for the case l = 0; the general case is similar.
Letting m = m_0, we have 

    c^k_1c^m_1s 
       ≡σ∧π^kσπ(σ∧π^mσπ s)
       ≡σ∧π^kσπ(σ∧π^ms)
       ≡σ∧π^kσπ(σπ^ms∧π^ms).

By Lemma <ref>, every (σ∧π^kσπ s)-reflecting ordinal is (σ∧π^kc^m_1σπ s)-reflecting. Conversely, if an ordinal is (σ∧π^kc^m_1s)-reflecting, then, by the equation above, it is

    σ∧π^kσπ(σπ^mσπ s∧π^mσπ s)-reflecting,

and thus 

    σ∧π^kσπσπ^mσπ s-reflecting.

If so, then by Theorem <ref>, it is

    σ∧π^kσπ s-reflecting,

as desired.

For every k ∈ℕ, every n_0,, n_k ∈ℕ, and every reflection pattern s, every (σ∧π^k+1s)-reflecting ordinal is (π^k+1σπ c^0_n_0c^1_n_1… c^k_n_ks)-reflecting.

This follows from applying Corollary <ref> repeatedly.



A reflection pattern is in 2-normal form if it is of the form

    π^nc^0_n_0c^1_n_1… c^k_n_k,

for some natural numbers k, n_0,n_1,, n_k. If w is the reflection pattern above, we define 2-normal form

    o(w) = ω^k+1· n_k + ω^k· n_k-1 + … + ω· n_0 + n.


For now, we shall simply refer to patterns in 2-normal form as being in normal form.
We shall see that patterns in normal form have very nice properties.


Suppose s is a reflection pattern in normal form. Then, every σσ-reflecting ordinal is σ(s)-reflecting. Contraction Lemma

By Theorem <ref>, any such ordinal is σ(σ∧π^k)-reflecting for any k. The lemma now follows from Lemma <ref>.


We also have the following “contraction” lemma, which will be crucial:

Suppose s is a reflection pattern. Then, every σπσπ s-reflecting ordinal is σπ s-reflecting.

Suppose α is σπσπ s-reflecting. By an argument as in Lemma <ref>, applying Lemma <ref>, for every Σ^1_1-sentence ϕ satisfied by L_α, one can find some πσπ s-reflecting β <α such that L_βϕ and β is not Σ^1_1-reflecting.  By Theorem <ref>, β is ππ s-reflecting. By Lemma <ref>, β is π s-reflecting, as desired.



Suppose π t and π s are reflection patterns in normal form such that o(π t) ≤ o(π s). Then, every (π s)-reflecting ordinal is either (π t)-reflecting or σ-reflecting.

Let 

    π t = π^nc^0_n_0c^1_n_1… c^k_n_k,

and 

    π s = π^mc^0_m_0c^1_m_1… c^l_m_l,

where n and m are nonzero. Without loss of generality, we assume that n_k and m_l are also nonzero. It follows that k ≤ l.
Suppose that o(π t) < o(π s). It will be convenient, for illustrative purposes, to consider the case that k < l first. If so, it suffices to show that every π(σ∧π^l)-reflecting ordinal which is not σ-reflecting is (π t)-reflecting, for then the result follows from Theorem <ref>. By Lemma <ref>, every π(σ∧π^l)-reflecting ordinal is

    π(σ∧π^l σπ c^0_n_0c^1_n_1… c^k_n_k)-reflecting.

By Lemma <ref>, every such ordinal is 

    π(σπ^l c^0_n_0c^1_n_1… c^k_n_k)-reflecting,
 
and, by Theorem <ref> or Lemma <ref>, according as n ≤ l or l ≤ n, it is

    π(σπ^n c^0_n_0c^1_n_1… c^k_n_k)-reflecting,
 
so that, if it is not σ-reflecting, then it is 

    π(π^n c^0_n_0c^1_n_1… c^k_n_k)-reflecting,
 
by Theorem <ref>, i.e., π(t)-reflecting.

The general case is similar: let i≤ k be greatest such that n_i < m_i and notice that

    c_m_i^i = c_m_i-n_i^ic_n_i^i.

Thus, 

    π t = π^nc^0_n_0c^1_n_1… c^i-1_n_i-1t',

where t' = c^i_n_i… c^k_n_k; and

    π s = π^mc^0_m_0c^1_m_1… c_m_i-n_i^it'.

It suffices to show that every π(σ∧π^iσπ t')-reflecting ordinal which is not σ-reflecting is (π t)-reflecting, for then the result follows from Theorem <ref>. 
Lemma <ref> (with σπ t' being the s in the statement) shows that every such ordinal is

    π(σ∧π^iσπ c^0_n_0c^1_n_1… c^i-1_n_i-1σπ t')-reflecting.

As before, by Lemma <ref>, every such ordinal is  

    π(σπ^iσπ c^0_n_0c^1_n_1… c^i-1_n_i-1σπ t')-reflecting.

By Theorem <ref> and Lemma <ref>, every such ordinal is

    π(σπ^nσπ c^0_n_0c^1_n_1… c^i-1_n_i-1σπ t')-reflecting.

By contraction (Lemma <ref>), it is

    π(σπ^nσπ c^0_n_0c^1_n_1… c^i-1_n_i-1t')-reflecting,

and by an argument like the one for Lemma <ref>, it is 

    π(σπ^n c^0_n_0c^1_n_1… c^i-1_n_i-1t')-reflecting,

so that if it is not σ-reflecting, then it is

    π(π^n c^0_n_0c^1_n_1… c^i-1_n_i-1t')-reflecting,

by Theorem <ref>, as desired.



Suppose t is a reflection pattern in normal form. Then σ∧ t is equivalent to a reflection pattern in normal form.

Put t = π^kc^0_m_0c^1_m_1… c^l_m_l. The lemma is immediate unless k ≠ 0 and there is some least i ≤ l such that m_i ≠ 0. Thus, 

    t 
       = π^kc^i_m_ic^i+1_m_i+1… c^l_m_l
       = π^k(σ∧π^i σπ c^i_m_i-1c^i+1_m_i+1… c^l_m_l).

Let

    s = c^k+i_m_k+ic^k+ i+1_m_k+i+1… c^l_m_l,

so that 

    t = π^k(σ∧π^i σπ c^i_m_i-1c^i+1_m_i+1… c^k+i-1_m_k + i-1s).
 
If all the indicated m_j are zero, then the result follows easily; otherwise, by Lemma <ref> and Lemma <ref>,

    t = π^k(σ∧π^i σπ c^i_m_i-1c^i+1_m_i+1… c^k + i-1_m_k + i-1σπ s).
 
By Lemma <ref>,

    σ∧ t 
       = σ∧π^k(σ∧π^i σπ c^i_m_i-1c^i+1_m_i+1… c^k+i-1_m_k+i-1σπ s)
       = σ∧π^k(π^i σπ c^i_m_i-1c^i+1_m_i+1… c^k+i-1_m_k+i-1σπ s)
       = σ∧π^k+iσπ c^i_m_i-1c^i+1_m_i+1… c^k+i-1_m_k+i-1σπ s)

By Lemma <ref> on the one hand and Lemma <ref> and Lemma <ref> on the other,

    σ∧π^k+iσπ s ≡σ∧ t,

but the reflection pattern on the left-hand side is readily seen to be equivalent to one in normal form.



Let s be a reflection pattern in which the string σσ does not occur. Then, it is equivalent to a reflection pattern in 2-normal form.

This is proved by induction on the construction of s. Clearly, if s is equivalent to a reflection pattern in normal form, then so too is π s. We only need consider the string σ s in the case that s is of the form

    π^mc^0_m_0c^1_m_1… c^l_m_l,

where m is nonzero.
Then, it is easy to see that

    σπ^mc^0_m_0c^1_m_1… c^l_m_l   = σπ c^0_m_0c^1_m_1… c^l_m_l
       = c^0_m_0+1c^1_m_1… c^l_m_l.

Now, let s be as above, and let

    t = π^nc^0_n_0c^1_n_1… c^l_n_l.

We need to show that s∧ t is equivalent to a reflection pattern in normal form.
If both n and m are nonzero, then the result follows from Lemma <ref>; so suppose that one of m and n is zero, so that

    s∧ t = σ∧ s ∧ t.

Write n = n_-1 and m = m_-1 and 
let i and j be least such that n_i and m_j are nonzero, respectively. There are four cases to consider. The first one is that in which both i and j are equal to 0. Then, there are reflection patterns u and v, both in normal form, such that

    t = σπ u

and 

    s = σπ v.

Suppose without loss of generality that o(π u) < o(π v). 
By Lemma <ref>, every (π v)-reflecting ordinal which is not σ-reflecting is (π u)-reflecting. Thus, every s-reflecting ordinal is either t-reflecting or σσ-reflecting, in which case it is also t-reflecting by Lemma <ref>. 

The second case is that in which i = 0 but j ≠ 0. Then, there are reflection patterns u and v, both in normal form, such that

    t = σπ u

and 

    σ∧ s = σ∧π^m_jσπ v.

By direct computation,

    s ∧ t 
       ≡σπ u ∧π^m_jσπ v
       ≡σ(π u∧π^m_jσπ v) ∧π^m_jσπ v
       ≡σ(π u∧π^m_jσπ v) ∧π^m_j(σ(π u∧π^m_jσπ v)∧σπ v)
       ≡σ∧π^m_j(σ(π u∧π^m_jσπ v)∧σπ v).

Now, it is easily seen that

    π^m_jσ(π u∧π^m_jσπ v)
       ≡π^m_jσ(π u∧π^m_jσπ v ∧πσπ v)
       ≡π^m_j(σ(π u∧π^m_jσπ v)∧σπσπ v ) 
       ≡π^m_j(σ(π u∧π^m_jσπ v)∧σπ v ),

where the last equivalence follows from Lemma <ref>,
and so

    s∧ t ≡σ∧π^m_jσ(π u∧π^m_jσπ v).

Since each of π u and π^m_jσπ v is a reflection pattern in normal form, Lemma <ref> implies that their conjunction is equivalent to one of π u and π^m_jσπ v in this context.  Let us denote this conjunct by w. Then, by an argument as before,

    s ∧ t
       ≡σ∧π^m_jσ w.

Since w is in normal form and of the form π w', so too is π^m_jσ w, so the result follows from Lemma <ref>. The case in which i ≠ 0 and j = 0 is analogous.

The remaining case is that in which both i and j are nonzero. Suppose without loss of generality that n_i < m_j
By replacing n_i and m_j by larger numbers if necessary (this might need to be done in the case i = -1 and m_0 = 0—a situation similar to the one in Lemma <ref>) we may assume that there are reflection patterns u and v such that

    σ∧ t = σ∧π^n_iσπ u

and 

    σ∧ s = σ∧π^m_jσπ v.

Then, we have

    σ∧ s ∧ t 
       ≡σ∧π^n_iσπ u∧π^m_jσπ v
       ≡σ(π^n_iσπ u∧π^m_jσπ v)∧π^n_iσπ u∧π^m_jσπ v
       ≡σ∧π^n_iσπ u∧π^m_j(σ(π^n_iσπ u∧π^m_jσπ v)∧σπ v).

By contraction,

    σ∧π^m_jσπ^n_iσπ u
       ≡σ∧π^m_jσπσπ u
       ≡σ∧π^m_jσπ u,

so, because n_i<m_j, it follows that every ordinal which is 

    (σ∧π^m_jσπ^n_iσπ u)-reflecting
 
is also  

    (σ∧π^n_iσπ u)-reflecting.

Similarly, we have

    σ∧π^m_jσπ^m_jσπ v
       ≡σ∧π^m_j(σπ^m_jσπ v∧σπσπ v)
       ≡σ∧π^m_j(σπ^m_jσπ v∧σπ v)

and so every ordinal which is (σ∧π^m_jσπ^m_jσπ v)-reflecting is also 

    (σ∧π^m_j(σπ^m_jσπ v∧σπ v))-reflecting.

From these two observations, we see that

    σ∧ s ∧ t
       ≡σ∧π^n_iσπ u∧π^m_j(σ(π^n_iσπ u∧π^m_jσπ v)∧σπ v)
       ≡σ∧π^m_jσ(π^n_iσπ u∧π^m_jσπ v).

Since both m_j and n_i are nonzero, Lemma <ref> implies that in this context the conjunction 

    π^n_iσπ u∧π^m_jσπ v

is equivalent to one of π^n_iσπ u or π^m_jσπ v. Denote this conjunct by w. Then, w is in normal form. Since w begins with the symbol π, π^m_jσ w is also equivalent to a pattern in normal form. The result then follows from Lemma <ref>. This proves the theorem.



σσ has order-type ω^ω in the reflection order.

By Theorem <ref>, every reflection pattern in which the string σσ does not occur is equivalent to one in σσ-normal form. By Lemma <ref>, this implies that σσ is strictly bigger than each reflection pattern in which the string σσ does not occur. Conversely, if a reflection pattern does contain the string σσ, then naturally, it cannot be strictly smaller than σσ. An easy induction using Lemma <ref> shows that, for reflection patterns u and v in 2-normal form, u < v if, and only if, o(u) < o(v), so the result follows.


§ LINEAR PATTERNS

Our first result in this section concerns the length of the linear reflection order; its proof induces a simple algorithm for comparing two arbitrary linear reflection patterns.


The length of the linear fragment of the reflection order is ω^ω.

Let us employ the simplified notation from the previous section.
Recursively, we assign ordinals to reflection patterns without conjunction: we assign the ordinal ω^n to the pattern

    σ^n.

In particular, the ordinal 1 is assigned to the empty pattern. If s and t are patterns to which ordinals o(s) and o(t) have been assigned, we assign the ordinal 

    o(s) + o(t)

to the pattern

    t π s.

Note that if n < m, then, on the one hand,

    α + ω^n + ω^m = α + ω^m,

while, on the other,

    σ^mπ s
       ≡σ^m-nσ^n π s
       ≡σ^m-n(σ^n π s ∧π)    by Lemma <ref>(<ref>)
       ≡σ^m-n(σ^nπ s ∧πσ^n π s)    by Lemma <ref>(<ref>)
       ≡σ^m-n(σ^n(π s ∧πσ^n π s) ∧πσ^nπ s)    by Lemma <ref>(<ref>)
       ≡σ^m(π s ∧πσ^n π s) 
       ≡σ^m π s ∧σ^mπσ^n π s.

Thus, every σ^m π s-reflecting ordinal is also σ^m πσ^n π s-reflecting when n < m; the converse is also true, by Lemma <ref> and Theorem <ref> (cf. the argument of Lemma <ref> on p. LemmaContractionWords). It follows that this assignment of ordinals is well-defined. By Lemma <ref> and Theorem <ref>, we have

    σπ^n σ≡σπ^mσ

for any pair of nonzero numbers n and m, so every conjunction-free reflection pattern is equivalent to one to which an ordinal has been assigned. It should be clear by now that, for conjunction-free reflection patterns, s < t if, and only if, o(s) < o(t), which completes the proof.


The second result of this section is that the linear patterns are cofinal in the reflection order.


The sequence {(σ^1_1)^n:n∈ℕ} is cofinal in the reflection order.

To prove the theorem, we shall prove by induction on the construction of a reflection pattern s that if s contains no occurrence of σ^n+1, then every σ(σ^n ∧ t)-reflecting ordinal is also σ(σ^n∧ t ∧ s)-reflecting, for every reflection pattern t (cf. Lemma <ref> on p. LemmaSigmaSigmaUniversal). We may assume that n ≠ 0, for otherwise the conclusion follows from Theorem <ref>.
Note that the case that s is a conjunction is immediate from the induction hypothesis and the case that s is of the form π s' is also immediate from the induction hypothesis and Theorem <ref>, thus, we suppose that s is of the form σ s'. The pattern s' might be a conjunction, say,

    s' = s_0∧ s_1 ∧…∧ s_k ∧ r_0 ∧ r_1 ∧…∧ r_l,

where each s_i is of the form σ^m_is_i' for some m_i < n and some s_i' which is a conjunction of patterns of the form π s^*, and each r_i is of the form π r_i'. Instead of proving that every σ(σ^n∧ t)-reflecting ordinal is σ(σ^n∧ t ∧σ s')-reflecting, we shall prove the stronger fact that it is

    σ(σ^n∧ t ∧σ(σ^n-1(s_0'∧ s_1'∧…∧ s_k')∧ r_0∧ r_1 ∧…∧ r_l))-reflecting.

By the induction hypothesis applied to s', and the fact that each of s'_i and

    r :=  r_0 ∧ r_1 ∧…∧ r_l

is a conjunction of patterns of the form π s^*, we obtain:

    σ(σ^n∧ t)
       ≡σ(σ^n∧ t∧ s_0' ∧…∧ s_k' ∧ r)
       ≡σ(σ^n∧ t∧σ^n∧ s_0' ∧…∧ s_k' ∧ r)
       ≡σ(σ^n∧ t∧σ(σ^n-1∧ s_0' ∧…∧ s_k' ∧ r))
       ≡σ(σ^n∧ t∧σ(σ^n-1(s_0' ∧…∧ s_k') ∧ r)),

where the last two equivalences follow from Lemma <ref>. This completes the proof of the theorem.





§ CO-STABILITY

Let us temporarily go back to our original notation with parentheses and subscripts.
By Lemma <ref>,
if s < σ^1_1(σ^1_1), then we additionally obtain the stronger fact that σ^1_1(σ^1_1) is σ^1_1(s)-reflecting. 
One may wonder if this phenomenon obtains in general. We will see that it does not. In particular, σ^1_1(π^1_1(σ^1_1(σ^1_1))) is not σ^1_1(σ^1_1)-reflecting, and, consequently,

    σ^1_1(σ^1_1) < σ^1_1(π^1_1(σ^1_1(σ^1_1))) < σ^1_1(π^1_1(σ^1_1(σ^1_1))) ∧σ^1_1(σ^1_1).

The proof, however, will lead to a third reflection transfer theorem which has the unintuitive consequence that

    σ^1_1(π^1_1(σ^1_1(σ^1_1))) ∧σ^1_1(σ^1_1) = σ^1_1(σ^1_1(π^1_1(σ^1_1(σ^1_1))))

The central notion for this is that of co-stability. co-stability

An ordinal σ is δ_σ-costable if for every Π_1 formula ϕ with parameters in L_σ, if L_δ_σϕ(L_σ), then there is α<σ such that L_α^+ϕ(L_α). 
Let s be a reflection pattern. We say σ is δ_σ-costable on s if moreover α can be chosen to be s-reflecting.


The same way that π^1_1 can be characterized as the least σ which is δ_σ-stable, σ^1_1 can be characterized as the least σ which is δ_σ-costable. More generally:

Let s be a reflection pattern and σ be an ordinal. Then,


  * If σ is δ_σ-costable on s, then it is Σ^1_1(s)-reflecting.

  * If s is a (possibly empty) conjunction of reflection patterns of the form π^1_1(t) and σ is Σ^1_1(s)-reflecting, then it is δ_σ-costable on s.
 

The first item is immediate from the definition.
For the second, suppose σ is Σ^1_1(s)-reflecting.
Let ϕ be a Π_1 formula with parameters in L_σ such that L_δ_σϕ(L_σ). Let ψ be the sentence asserting the existence of a model M of + V = L such that


  * M contains σ;

  * L^M_δ_σϕ(L_σ).

By reflection, let σ_0<σ be an s-reflecting ordinal such that L_σ_0ψ. If σ_0 is Σ^1_1-reflecting, then it is (σ^1_1∧ s)-reflecting and thus σ^1_1(s)-reflecting, by Lemma <ref> and the assumption on s. Choose an s-reflecting σ_1<σ_0 such that L_σ_1ψ. After finitely many steps, one arrives at some s-reflecting σ_n which is not Σ^1_1-reflecting and such that L_σ_nψ, as witnessed by some model N. Since σ_n is not Σ^1_1-reflecting, δ_σ_n = σ_n^+, so δ_σ_n^N is greater than every β<σ_n^+. Since ϕ was chosen to be Π_1, it follows that L_σ_n^+ϕ(L_σ), as desired.


If one could remove the restriction on s in the statement of Proposition <ref>, then σ^1_1(σ^1_1) would be the least ordinal σ which is δ_σ-costable on Σ^1_1-reflecting ordinals.
Proposition <ref> below shows that this is false.
 
σ^1_1(σ^1_1) is not the least ordinal α which is δ_α-costable on Σ^1_1-reflecting ordinals.

The main point is that being δ_σ-costable on s is expressible over  L_δ_σ using L_σ as a parameter (see the proof of Proposition <ref>). Let σ = σ^1_1(σ^1_1) and suppose towards a contradiction that σ is indeed the least ordinal α which is δ_α-costable on Σ^1_1-reflecting ordinals; then L_δ_σ+1 satisfies the statement expressing that there is an admissible α such that δ_α exists and is not admissible and α is δ_α-costable on Σ^1_1-reflecting ordinals. By Proposition <ref>, σ is (δ_σ+1)-stable and thus a limit of ordinals α which are δ_α-costable on Σ^1_1-reflecting ordinals—a contradiction.



Let s be a reflection pattern of the form π^1_1(t). Then, the least σ^1_1(s)-reflecting ordinal is not σ^1_1(σ^1_1)-reflecting.

We shall not prove Proposition <ref>, as it is a consequence of Theorem <ref> below.


The inequality stated at the beginning of the section now follows: clearly σ^1_1(π^1_1(σ^1_1(σ^1_1))) is a limit of σ^1_1(σ^1_1)-reflecting ordinals and thus 

    σ^1_1(σ^1_1) < σ^1_1(π^1_1(σ^1_1(σ^1_1))).

By Proposition <ref> applied to t = π^1_1(σ^1_1(σ^1_1)), the ordinal σ^1_1(π^1_1(σ^1_1(σ^1_1))) is not σ^1_1(σ^1_1)-reflecting, and thus

    σ^1_1(π^1_1(σ^1_1(σ^1_1))) < σ^1_1(π^1_1(σ^1_1(σ^1_1))) ∧σ^1_1(σ^1_1).

In particular, we have

    σ^1_1(π^1_1(σ^1_1(σ^1_1))) ≠σ^1_1(π^1_1(σ^1_1(σ^1_1))) ∧σ^1_1(σ^1_1).

This is in contrast to the fact that 

    σ^1_1(π^1_1(σ^1_1(σ^1_1))) = σ^1_1(π^1_1(σ^1_1(π^1_1(σ^1_1(σ^1_1))))) ∧σ^1_1(π^1_1(σ^1_1(σ^1_1))).

by Lemma <ref>.


We now state and prove the third reflection transfer theorem:

Let s be a reflection pattern.
Suppose σ is σ^1_1(π^1_1(s))-reflecting and σ^1_1(σ^1_1∧ t)-reflecting. Then, it is 

    σ^1_1(σ^1_1(π^1_1(s))∧ t )-reflecting.
 

Put r = π^1_1(s). Let σ be an ordinal which is σ^1_1(π^1_1(s))-reflecting and also σ^1_1(σ^1_1∧ t)-reflecting.
By Proposition <ref>, σ is δ_σ-costable on r. Let ψ be the sentence asserting the existence of a model M of + V = L such that


  * M contains σ;

  * In M, σ is δ_σ-costable on t.

By σ^1_1(σ^1_1∧ t)-reflection, there is a (σ^1_1∧ t)-reflecting ordinal τ<σ such that L_τψ, as witnessed by some model N. Thus, in N, τ is δ_τ-costable on r. However, since τ is Σ^1_1-reflecting,  δ_τ < τ^+. It follows that δ_τ∈ N, so N is correct about the δ_τ-costability on r of τ. Hence, τ really is δ_τ-costable on r. By Proposition <ref>, it is Σ^1_1(r)-reflecting. Therefore, τ is Σ^1_1(r)-reflecting and t-reflecting, so σ is as desired.


Repeated applications of Theorem <ref> yield:

Let s be a reflection pattern. Suppose σ is σ^1_1(π^1_1(s))-reflecting and σ^1_1((σ^1_1)^n∧ t)-reflecting. Then, it is 

    σ^1_1((σ^1_1)^n(π^1_1(s))∧ t )-reflecting.
 


We finish this section with a final reflection transfer theorem stated as a  dichotomy. It is a strengthening of Theorem <ref> which clarifies the hypothesis on σ not being Σ^1_1-reflecting. 


Suppose σ is π^1_1(σ^1_1(t∧π^1_1(s)))-reflecting. Then, one of the following holds:


  * σ is π^1_1(s)-reflecting; or

  * σ is σ^1_1(t∧π^1_1(s))-reflecting.


Suppose σ is π^1_1(σ^1_1(t∧π^1_1(s)))-reflecting but not π^1_1(s)-reflecting. Let θ be a Σ^1_1 sentence with parameters in L_σ such that

    L_σθ;

we need to find a (t∧π^1_1(s))-reflecting τ<σ such that

    L_τθ.

By Barwise-Gandy-Moschovakis <cit.>, Barwise-Gandy-Moschovakis there is a Π_1 formula θ^*(a) such that for every admissible α containing the parameters of θ, L_αθ if, and only if, L_α^+θ^*(L_α).
In particular, 

    L_σ^+θ^*(L_σ).


Since σ is not π^1_1(s)-reflecting, there is a least β<σ^+ such that σ is not β-stable on s. Because θ^* is Π_1,

    L_βθ^*(L_σ).

Let ϕ be the sentence asserting the non-existence of a model M of + V = L end-extending L_σ+1 in which σ is σ^1_1(t∧π^1_1(s))-reflecting. This is a Π^1_1 sentence and thus cannot be satisfied by any π^1_1(σ^1_1(t∧π^1_1(s)))-reflecting ordinal and, in particular, by σ. Thus, there is a model M of + V = L end-extending L_σ+1 and such that

    M“σ is σ^1_1(t∧π^1_1(s))-reflecting.”

Let χ be the sentence asserting the existence of a model N of + V = L such that


  * N contains σ;

  * in N, letting β be least such that σ is not β-stable on s, we have

    N“L_βθ^*(L_σ).”


Since β <σ^+ and M must end-extend L_σ^+, β∈ M and M is correct about β being the least ordinal at which σ fails to be stable on s.
Thus, we have

    M“L_σχ,”

as witnessed, say, by L^M_σ^+. Within M, σ is σ^1_1(t∧π^1_1(s))-reflecting and thus there is some τ<σ such that, 

    M“L_τχ,”

and so we really do have 

    L_τχ.

Moreover, M is correct about reflection below σ, so we may assume that τ is (t∧π^1_1(s))-reflecting. By the definition of χ, there is
a model N of + V = L such that


  * N contains τ;

  * in N, letting γ be least such that σ is not γ-stable on s, we have

    N“L_βθ^*(L_τ).”

 
Since τ is π^1_1(s)-reflecting, it is τ^+-stable on s, and thus γ cannot be a true ordinal smaller than τ^+. By Ville's Theorem, N must end-extend L_τ^+. Because θ^* is Π_1, it follows that

    L_τ^+θ^*(L_τ),

and thus, that

    L_τθ,

as was to be shown.




§ CONCLUDING REMARKS

We have not given any bounds on the length of the reflection order. Let us say something about this:
 
Let s be a reflection pattern and suppose α is a countable, locally countable ordinal such that

    L_α≺_1 L_α^++1.

Then, α is s-reflecting.

Since 

    L_α≺_1 L_α^+,

it follows that α is π^1_1-reflecting. By Gostanian's theorem <cit.> mentioned in the introduction, α is σ^1_1-reflecting. Inductively, suppose it is

    (σ^1_1)^n-reflecting

and let ψ be a Σ^1_1 sentence such that

    L_αψ.

Choose a Π_1 sentence ψ^* such that for all admissible β containing all relevent parameters,

    L_βψ

if, and only if,

    L_β^+ψ^*(L_β),

so that, in particular,

    L_α^+ψ^*(L_α).

Then, from the point of view of L_α^++1, there are admissible sets L_α and L_α^+ such that


  * α is (σ^1_1)^n-reflecting, i.e., for every Π_1 sentence ϕ^*, if L_α^+ϕ^*(L_α), then there is a (σ^1_1)^n-1-reflecting β<α such that L_β^+ϕ^*(L_β). (The quantification over ϕ^* is bounded.)

  * L_α^+ψ^*(L_α).

Thus, by stability, there are admissible sets L_β and L_β^+ in L_α such that β is (σ^1_1)^n-reflecting and L_β^+ψ^*(L_β). Hence, α is (σ^1_1)^n+1-reflecting. Therefore, a simple induction on the construction of a reflection pattern s, using the proofs of Theorem <ref> and Theorem <ref> shows that α is s-reflecting.


The length of the reflection order is thus at most the least ordinal α such that

    L_α≺_1 L_α+1.

Moreover, surely each inequality between reflection patterns is provable in any theory that proves the existence of the corresponding ordinals. This suggests strongly that the length of the reflection order is smaller than the proof-theoretic ordinal of the subsystem ^1_2-CA_0 of analysis and in fact smaller than the ordinal described in Rathjen <cit.>, though we do not have a proof of this. The reader may consult <cit.> for an example of a chain of length ε_0 in the reflection order.

An interesting question is that of the structure of the “higher” reflection order, defined in terms of iterated Π^1_n and Σ^1_n-reflection and conjunctions. The situation there is very different and involves set-theoretic considerations; it will be the subject of a forthcoming article.


abbrv


