The Journal of Symbolic Logic Volume 00, Number 0, XXX 0000

ON REVISION OPERATORS

P.D.WELCH

Abstract. We look at various notions of a class of definability operations that generalise inductive operations, and are characterised as “revision operations”. More particularly we: (i) characterise the revision theoretically definable subsets of a countable acceptable structure; (ii) show that the categorical truth set of Belnap and Gupta’s theory of truth over arithmetic using fully varied revision sequences yields a complete Π_{3}^{1} set of integers; (iii) the set of stably categorical sentences using their revision operator ψ is similarly Π_{3}^{1} and which is complete in Gödel’s universe of constructible sets L; (iv) give an alternative account of a theory of truth - realistic variance that simplifies full variance, whilst at the same time arriving at Kripkean fixed points.

[...] no statement is immune to revision. W. V. O. Quine, From a Logical Point of View, p 43.

§1. Introduction. This paper concerns itself with some rather general forms of definability based on certain kinds of operator Φ : P(ℕ) ⟶ P(ℕ). Unlike the more familiar forms of inductive definability where Φ is restricted to be given by some positive arithmetic formula, and hence be monotone, we shall not even restrict Φ to be progressive (that is s ⊆ Φ(s).) However we do think of Φ as an operator that is repeatedly applied to an initial starting set s_{0} (which will not necessarily be the empty set).

A natural question then is what should be done at limit stages if we wish to repeat this process transfinitely. For monotone inductive definitions (or simply progressive ones) there is only one natural proposal, as α < β ⟶ Φ^{α}(s) ⊆ Φ^{β}(s) we take unions at limit ordinal stages λ. At the level of generality mentioned so far it is not obvious that there should be any natural operation, and something will have to be devised as a limit rule Γ.

If this is to be at all a fruitful approach there will have to be restrictions in order that the concept is not just hopelessly general. Interestingly there are already several examples

\begin{matrix}c \\ ◯ \end{matrix} 0000, Association for Symbolic Logic

0022-4812/00/0000-0000/$00.00

Received by the editors December 30, 2002- final version.

We should like to thank the Mathematics Department of UC Berkeley for its hospitality during the period when this research was conducted, and to the Institut für Formale Logik in Vienna for a Gastprofessur where this paper was finally written.

Keywords: revision theory, definability theory, admissibility theory, descriptive set theory. AMS Classifications: 03A05,03D70,03E15,03F35

in the literature of such processes that one can classify as falling under this scheme, and which have arisen in unconnected fields.

A primary example version of this kind of definability has been worked out by Belnap and Gupta in their book [9]. Their theory of “circular definitions” based on “revision sequences” (whence the title of this paper) derives from their earlier account of a theory of truth where the Tarskian biconditionals are treated as being definitional of truth. Unlike the Kripkean theory of truth which provides a monotonic operator building up a set of truths and of falsehoods for a partially defined T predicate, they assume a total (and so inconsistent) extension of the T predicate over, for example, ℕ the structure of arithmetic, which is then revised according to the Tarskian biconditionals. Latterly, they have sought to embed this in the aforementioned more general theory of circular definitions, which involve repeatedly revising the extension of some predicate and seeing which objects fall finally under the resulting extension no matter which starting hypothesis is used for its initial extension (or even which limit rule).

A further example (and was our own starting point) is afforded by the Infinite Time Turing Machines of [10]. A Turing machine acts on its tape, which via coding we view as a set of integers, continually “revising” in simple steps the tapes contents. If we adopt the formalism of [10], and suppose at limit stages of time λ that the value of a cell is the limsup of its previous values for α < λ, we have thus a “limit rule”. Such conceptual devices can “compute” surprisingly complicated sets.

Löwe first pointed out the similarity between Herzberger style revision sequences and Infinite Time Turing Machines in [15]. We wish to express our thanks to him here for his correspondence on these issues. In [15] he made the suggestion that a machine theoretic approach could help throw a new light on the various limit rules in Belnap and Gupta’s definability theory. Whilst ultimately it is our viewpoint that it is Gödel’s constructible hierarchy L that underlies both these phenomenon, (and that in the final analysis the choice of limit rule for Belnap and Gupta’s theory qua a theory of definability, is almost irrelevant as the proof of Theorem 2.1 shows), it was his suggestion that led us to look at revision theoretic definitions. (We shall discuss later more precisely this connection, see Comment 3 below.) At this point we should also like to thank J. Burgess and D.A.Martin for some helpful comments on these topics, and in particular V. McGee for both illuminating conversations and correspondence as we were learning the revision theory of truth, and to A. Gupta for some extensive correspondence replying to our queries.

Belnap and Gupta, having formulated a general theory of circular definitions in [9] really are interested there in discussing truth, and we are unaware of any attempt in the literature to delineate what the class of definitions it is that they are defining. A primary motivation for us was to discover what this was, and a description is given at Theorem 2.2 below.

Kripkean theory of truth \overrightarrow{an example of} Monotone inductive definition ⟶ Analysis of Π_{1}^{1} & positive elementary definitions ⟷ The next admissible set The above schematic diagram illustrates the relationship between Kripke’s theory of truth, [14], using either of the Kleene 3-valued truth table schemes, or the van Fraassen supervaluation scheme, and the corresponding definability theory. Our original purpose had been to discover the corresponding relationships for the Gupta-Belnap theory, and thus find out the solutions for ‘?’ and ‘??’ below.

Gupta- Belnap theory of truth \overrightarrow{an example of} Revision Theoretic definability scheme ⟶  ?  ⟷  ??

Briefly, the Gupta-Belnap theory raises the level of definability to Π_{2}^{1}, ‘?’ thus being filled by an analysis of the Gupta-Belnap definitions and Π_{2}^{1}; and ‘??’ by the companion structure of the “next stable set” - rather than the next admissible set at the Π_{1}^{1}-level. We were unaware of the paper of Burgess [3] at the time, which would have indicated what the answer might be. Burgess showed that the “stable truth set” (using Belnap’s Limit Rule) over arithmetic was a complete Π_{2}^{1} set. This can be obtained as a corollary to Theorem 2.1, where we show that the revision theoretically definable reals are precisely the Π_{2}^{1} reals. We had previously shown a corresponding result that the set of indices of total infinite time turing computable functions formed a complete Π_{2}^{1} set of integers. It also turned out that such machines are formally equivalent to the Herzberger Revision sequences of [12], [11].

There is thus an analogy with the theory of monotone inductive definitions over an acceptable structure (in the sense of Moschovakis [17]) and the next admissible set, and the theory of revision theoretic definability and the “next stable set” 𝕊_{M} over a structure M with a suitable coding scheme. The latter theory forms the first part of the paper in §2. There one observes that the revision theoretically definable subsets of M are those that are Π_{1}(𝕊_{M}). There is also an unfortunate disanalogy: Π_{1}^{1} forms a Spector class, whilst Π_{2}^{1} does not. Later sections visit various other aspects of Belnap and Gupta’s theory of truth: in §3 we look at their notion of fully varied sequences which in fact essentially requires Π_{3}^{1} notions: we show that the stable truth set over arithmetic is Π_{3}^{1}-hard. The motivation for this variety of revision theory seems to be that it allows certain “Gupta-puzzle”-like sets of sentences to be appropriately classified in all such revision sequences. §4 is devoted to our simplified version of full variance, which we dub “realistic variance”, and which seems to achieve the same effect. It thus seems to us to have the advantages of full variance, but (i) it is simpler (it results in a stable truth set that is “only” Π_{2}^{1}-hard) and (ii) each revision sequence results in a stability pair set that is a Kripkean fixed point for the van Fraassen supervaluation scheme. Thus realistic variance can be considered an intermediate theory between full variance and the standard theory, or, as a stepping stone on the way to the notion of algorithmic variance alluded to below. The notion of stable categoricity (cf. [9] 6D.9) derived from arguments concerning strengthened liar paradoxes is seen in §5 to also lead to complicated sets: the stable categorical sentences form a Π_{3}^{1} set, and at least in L, are a Π_{3}^{1}-hard set.

The results here are those announced in the first five sections of [21]. A further example of revision operator is suggested in the final section of that paper: making an “algorithmic” choice of a revision rule. Such a revision operator leads on individual sequences to sets at a simpler level of definability, and a theory of truth based on single processes, much as Kripke’s. We leave discussion of this to [20]. We have made no attempt to discuss the implications philosophical or otherwise, of the results here for the theory of truth based on revision sequences (we leave this for [20] also), but use this opportunity to separate away from that discussion the mathematical proofs that are perhaps somewhat more technical than usual in papers on the semantical theories of truth. That the proofs do involve technical mathematics is a concomitant of the assertions in the theorems: revision theories of truth, of necessity, are complicated. We make some comments on this, but largely pass no judgement here on what that implies.

1.1. The general setting. We shall attempt to make the discussion as self-contained as possible; however we shall refer the reader to the relevant sections of [2](II.5), or [6] (II.1) for the basic definition of the Gödel constructible hierarchy L_{α}. We shall not use much of admissibility theory, but we shall be generalising the theory of monotone inductive definitions, and for these the books of [2] (Ch.VI) and [17] can be consulted. For κ an infinite cardinal, H_{κ} is the class of sets of hereditary cardinality less than κ: that is, those sets x whose transitive closure, T C(x), satisfies cardT C(x) < κ; HC denotes H_{ω_{1}}, the class of hereditarily countable sets. We identify ℕ with ω.

Let :.P(ω) ⟶ P(ω) be an operator (frequently referred to in the sequel as a “revision operator” since we regard δ as “revising” the objects in its domain). Let Lim denote the class of limit ordinals. Let Γ : ^{Lim}P(ω) ⟶ PP(ω) be a function defined on limit length sequences of subsets of ω. In the following definition, ∞ is to be taken, at least initially, as some appropriate uncountable cardinal, or even sometimes as On the class of all ordinals.

Definition 1.1. A revision sequence based on δ, Γ is a sequence ⟨s_{α} | α < ∞⟩ with:

(i) ∀α s_{α} ⊆ ω; (ii) ∀α ∈ On s_{α+1} = (.s_{α}); (iii) ∀λ ∈ On, Lim(λ), s_{λ} ∈ Γ(⟨s_{α} | α < λ⟩).

Examples:(i) A monotone inductive definition over ℕ via some positive arithmetical formula. (ii) An arithmetic quasi-inductive definition (Burgess [3]). (iii) Various other forms of non-monotonic inductive definitions. (See for example [18]) (iv) Sequences of computations of Infinite Time Turing Machines ([10]).

(v) Revision sequences of Belnap-Gupta. (vi) Iteration of the Shoenfield Limit lemma along Kleene’s O (Clote [5]).

In each of these examples ((i) being the most important and familiar) various processes are defined which have some clearly defined starting point and the process produces some object of interest.

We shall for the most part be interested in revision sequences with Δ_{2}^{1} definable operators δ, and with a limit rule Γ which is Δ_{1}(HC, ∈)-definable. (When single valued Γ - that is ran(Γ) consists only of singleton sets - it will have essentially a Δ_{2}^{1} graph in codes for wellorders.) In such a case a countable length revision sequence will then simply be Δ_{1}(⟨HC, ∈⟩). All the examples will satisfy some coherency condition on Γ.

Definition 1.2. The local set of stabilities at λ is defined as follows.

(i) For Lim(λ) or λ = ∞, s_{<λ}^{+} =_{df} {n | ∃β < λ∀α(β ≤ α < λ ⟶ n ∈ s_{α})}. s_{<λ}^{−} is defined analogously with “n ∉ s_{α}” replacing “n ∈ s_{α}.” (ii) We set s_{<λ} =_{df} (s_{<λ}^{+}, s_{<λ}^{−}).

We shall use the notation s⃗ ↾ λ for λ ≤ ∞ for the restriction of the sequence s⃗ to λ: s⃗ ↾ λ =_{df} ⟨s_{α} | α < λ⟩. Then, with this notation, s⃗ ↾ λ_{<∞} = s_{<λ}.

Definition 1.3. (Coherence) s coheres with s⃗ = ⟨s_{α} | α < λ⟩ (for λ a limit ordinal or ∞) if s ∩ s_{<λ}^{−} = Ø and s ⊇ s_{<λ}^{+}.

We shall (with one exception in §5) always assume that

(i) Γ is coherent, in that for any limit λ < lh(s⃗)

∀s ∈ Γ(⟨s_{α} | α < λ⟩)(s is coherent with s_{<λ});

(ii) “t ∈ Γ(s⃗ ↾ λ)” is Δ_{1}(HC, ∈)-definable.

Definition 1.4. (The stabilization pair of a sequence) Let s⃗ be a revision sequence.

(i) Let σ(s⃗) = the least limit ordinal σ < lh(s⃗) so that

(a) s_{<σ(s⃗)} = s_{<∞}; (b) ∀t ≥ σ s_{<σ} ⊆ s_{<τ} .

(ii) σ(s⃗) is called the stabilization point and s = (s_{<∞)}^{+}, s_{<∞}^{−}) the stabilization pair, of s⃗.

Note: (i) A closure argument shows that stabilization points and pairs must exist for any revision sequence if lh(s⃗) = ∞ is On or is a cardinal of uncountable cofinality: {α < lh(s⃗) | s_{<α} = s_{<∞}} is then closed and unbounded in lh(s⃗).

The following lemma is straightforward:

Lemma 1.1. Let s⃗ be a revision sequence, and let σ(s⃗) its stabilization point. Then there is a revision sequence t⃗ of countable length, with t_{<∞} = s_{<∞}, and s_{σ(s⃗)} = t_{σ(t⃗)}.

Proof: By Löwenheim-Skolem. Q.E.D.

§2. Revision Theories of Truth and Definability. We discuss the particular examples of limit rules of revision sequences arising from Revision Theories of truth.

Example (1) Herzberger Limit Rule, Γ_{H} (see [12],[11]). Γ_{H} is single valued and takes as s_{λ} the smallest s coherent with s_{<λ} for all λ < lh(s⃗). In some sense this is a “minimal” policy, only those integers in s_{<λ}^{+} can be taken as in s_{λ}. Example (2) Gupta Rule, Γ_{G} is also single valued: Γ_{G} is defined by s_{λ} = s_{<λ}^{+} ∪ s_{0}\s_{<λ}^{−}. The idea here is that we refer back to our original “hypothesis” h = s_{0} to fill in for the ambiguous values in ω\(s_{<λ}^{+} ∪ s_{<λ}^{−}). Example (3) Belnap Rule, Γ_{B}. An example of a multi-valued limit operator: Γ_{B} = {s | s coheres with s_{<λ}}. The Belnap rule thus places the least possible restriction on the choice at lmit stages, only coherence must be adhered to.

Originally these arose in discussions of notions of limit stage operators (called “bootstrapping policies”) specifying how a sequence might be built from δ_{τ}, the Tarskian truth operator, at successor stages.

Corresponding to these rules are notions of definability. [9] expand their original revision theory of truth to cover a theory of circular definitions.

We consider the example of arithmetic and the structure of natural numbers ℕ augmented with a predicate symbol ṡ. Let Φ(v_{0}) be a formula with one free variable in this language. Let δ_{Φ} be defined by

δ_{Φ}(s) = {n | ⟨ℕ, s⟩ ⊨ Φ(ṅ)}.

Definition 2.1. z ⊆ ℕ is S_{Γ}^{∗}-definable for some limit operator Γ, and some revision rule δ_{Φ} as above if

z = ⋂{ s_{<∞}^{+} | s⃗ = ⟨s_{α} | α < ∞⟩ is a revision sequence based on δ_{Φ}, Γ }.

Note that we could have specified the length lh(s⃗) of the revision sequence in the above definition to be always ω_{1}. Lemma 1.1 shows that we can find by Löwenheim-Skolem a countable revision sequence t⃗ of length τ with the same stability set as one of length On (or any regular uncountable cardinal). Suppose then t⃗ arises in this way. Set τ′ = σ(t⃗), t = t_{<τ′} = t_{<τ}, and then t occurs cofinally as the local stability set below τ. Then we may simply append repeatedly ω_{1} times the segment t⃗ ↾ [τ′, τ) to obtain an appropriate revision sequence of length ω_{1} with the same stability set of s⃗ and of t⃗.

The above notion is based on an earlier theory of truth suggested by Belnap. In their text they treat more of the following definition.

Definition 2.2. z ⊆ ℕ is S_{Γ}^{#}-definable for some limit operator Γ, and some revision rule δ_{Φ} as above if

z = ⋂{ s_{<∞}^{#+} | s⃗ = ⟨s_{α} | α < ∞⟩ is a revision sequence based on δ_{Φ}, Γ }.

where

s_{<∞}^{#+} =_{df} {k | ∃m < ω∀n < ω∀β > σ(s⃗)(n > m ⟶ k ∈ s_{β+n})}

The point of this latter definition is that it allows one to talk of “near stability”: it is not that k must belong to every sufficiently large s_{β}: it is allowed to waver finitely often at and after limit levels s_{λ}, but only for a fixed number m of stages. We refer the reader to [9] 5.D.

Note Kremer ([13]) gives explicitly a set of definitions D, giving rise to a revision rule δ_{D} so that discrete linear orders with a first element have extensions of a current hypothesis that are isomorphic to ℕ - so we choose to work over models of ℕ.

The question arises, what kinds of reals are S_{Γ}^{∗} or S_{Γ}^{#} definable, and how do they depend on Γ? (see [15].)

Antonelli ([1]) gives explicit revision theoretic definitions for each of the complete Σ_{n}^{0} sets, i.e. for each level of the arithmetic hierarchy. Kremer (§8 op.cit.) gives an argument of Gupta showing that this result can be extended to the inductive sets:

(i) Inductively definable subsets of ℕ are S_{Γ_{B}}^{#} and S_{Γ_{B}}^{∗}-definable.

But also Kremer shows that:

(ii) For any Π_{2}^{1} set of integers X, there is a finite set of positive definitions D so that X is recursively embeddable into ⊨_{i}^{D} - the set of sentences valid on D in S_{i}, where S_{i} is the semantic theory associated to truth-at-the-first-fixed-point of the positive inductive definitions D.

As he shows that S^{∗} and S^{#} extend S_{i}, it follows that the complexity of ⊨_{∗}^{D} and ⊨_{#}^{D} are also Π_{2}^{1}.

We show that strong definability extends throughout Δ_{2}^{1} regardless of the choice of Limit Rule Γ_{H}, Γ_{G}, Γ_{B}.

Theorem 2.1. Let S be S_{Γ}^{#} or S_{Γ}^{∗};

(i) Let Γ be any limit rule whatsoever; let z be any Π_{2}^{1} real. then z is S_{Γ}-definable. Hence any Δ_{2}^{1}-definable real is S_{Γ}-, co-S_{Γ}-definable. (ii) Let Γ be any Δ_{1}(HC, ∈)-definable limit rule (this includes any of Γ_{H}, Γ_{G}, Γ_{B}).

(a) The class of S_{Γ}-definable reals is precisely that of the Π_{2}^{1} reals; (b) the class of Δ_{2}^{1}-definable reals coincides with the class of S_{Γ}-, co-S_{Γ}-definable reals.

Remark: The S_{Γ}-, co-S_{Γ}-definable reals (for Γ ∈ Δ_{1}(HC, ∈), e.g. Γ ∈ {Γ_{H}, Γ_{G}, Γ_{B}}) are thus the reals of the first transitive stable set, 𝕊_{ℕ}, over the structure ℕ.

Definition 2.3. Let M = ⟨M, R, … ⟩ be any structure. Define:

𝕊_{M} =_{df} L_{σ_{1}^{M}}(⟨M, R, … ⟩)

where the latter is the first level of the relative L-hierarchy built over M, using elements of M as urelemente, wuth the property that 𝕊_{M} ≺_{Σ_{1}} V.

Thus 𝕊_{M} is correct about Σ_{1} facts true in V of M. Note that as 𝕊_{M} is an admissible structure, Δ_{1}(𝕊_{M}) subsets of M are in 𝕊_{M}. The notion of acceptability in the next theorem is that of Moschovakis [17].

Theorem 2.2. Let S be S_{Γ}^{#} or S_{Γ}^{∗}; let M be a countable acceptable structure.

(i) Let Γ be any limit rule whatsoever; let z be any Π_{1}(𝕊_{M}) subset of M. Then z is S_{Γ}-definable. Hence any Δ_{1}(𝕊_{M})-definable subset is S_{Γ}-, co-S_{Γ}-definable. (ii) let Γ be any Δ_{1}^{(HC,∈)}({M})-definable limit rule (this includes any of Γ_{H}, Γ_{G}, Γ_{B}). The class of S_{Γ}-definable subsets of M is precisely that of the Π_{1}(𝕊_{M}) sets; the class of Δ_{1}(𝕊_{M})-definable sets coincides with the class of S_{Γ}-, co-S_{Γ}-definable subsets of M.

For Γ ∈ {Γ_{H}, Γ_{G}, Γ_{B}} then, P(ω) ∩ 𝕊_{ℕ} is precisely the class of S_{Γ}-, co-S_{Γ} sets of integers. In fact, by Levy-Shoenfield, it is thus the reals of the smallest model of Δ_{2}^{1}- Comprehension that is Σ_{2}^{1}-correct, that, any Σ_{2}^{1} formula about real parameters from the model is true, if and only if it is true in the model.

Remark: 𝕊_{ℕ} has domain that of L_{σ} where σ is the first stable ordinal. Note that many first order structures M will have 𝕊_{M} the same. For example 𝕊_{ℕ} will have the same domain as 𝕊_{A} where A is the least β-model of analysis.

The import of part (ii) of either theorem is that the choice of revision rule Γ ∈ { Γ_{H}, Γ_{G}, Γ_{B}}, or semantic scheme S^{#} , S^{∗} is immaterial, when calculating the class of definable subsets of the structure.

By way of analogy with admissibility theory and the hyperelementary sets over a structure, we view revision theoretic definability as building up for us the domain of 𝕊_{M} over M. Just as the inductive/co-inductive sets over M yield the hyperelementary sets of the “next admissible set” over M, so the S_{Γ}-, co-S_{Γ}-definable sets yield the domain of the “next stable set over M”. The following diagram is supposed to be reminiscent of the analogous one from [2], p.43, of the “next admissible set” over M.

𝕊_{M} M

• 𝕊_{M} =_{df} L_{σ_{1}^{M}}[M] and is Π_{2}^{1}-

absolute.

σM 1 • X ⊆ M is S_{Γ}-definable over M ⟺ X is Π_{1}(𝕊_{M}).

• X ∈ 𝕊_{M} ∩ P(M) ⟺ X is both S_{Γ}- and co-S_{Γ}-definable over M.

Figure 1. 𝕊_{M}: the next stable set over M

We content ourselves with proving Theorem 2.1 as the route to extending such a theory to acceptable structures has been charted in [17]; indeed one could strengthen Theorem 2.2 by requiring only that M have a strongly definable coding scheme.

Proof: of Theorem 2.1. We let S = S^{∗}. (The proof for S^{#} is immediate from what follows.) We describe informally an arithmetically definable operation δ : P(ω) ⟶ P(ω) so that δ(s) = {n | ⟨ℕ, s⟩ ⊨ Φ(n, ẋ)} for some Φ. It would be an invidious task to explicitly give all the coding required, but give only the important steps; we leave it to the reader to provide the actual details.

Let B_{0} = Π_{1}-T h(L_{ω_{1}}) - that is the complete Π_{1} ( - in the language L_{{ ˙∈, ˙=}}) theory of ⟨L_{ω_{1}}, ∈⟩. It is well known that B_{0} is a complete Π_{2}^{1} set. Without loss of generality we shall assume that this theory is coded by even integers. Say 2n ∈ B_{0} ⟺ ⟨L_{ω_{1}}, ∈⟩ ⊨ ψ_{2n} where ⟨ψ_{2k} | 2k < ω⟩ is a recursive enumeration of the Π_{1}-sentences. Note we may assume we have also a recursive enumeration ⟨φ_{2k} | 2k < ω⟩ of the Σ_{1} sentences, with a recursive g : Evens ⟶ Evens so that φ_{g(k)} is logically equivalent to ¬ψ_{k}. If A_{0} = g“Evens\B_{0}, then A_{0} is recognizable as, essentially, a code for Σ_{1} truth over L_{ω_{1}}. Let s ⊆ ℕ. Steps 1 - 3 below describe the transition, or revision step, δ(s) = s′.

Step 1 of δ: look at s ∩ Evens and ask of A = {g(2k) | 2k ∉ s ∩ Evens}, whether

A = ⟨ω, E_{A}⟩ ⊨ “V = L”

In other words, if elements 2n, 2m of A code parameter free Σ_{1} terms t_{n}, t_{m}, and if the ∈-relation E_{A} is defined by ⟨m, n⟩ ∈ E_{A} ⟷ ⌜t_{m} ∈ t_{n}⌝ ∈ A, then we ask if ⟨ω, E_{A}⟩ is an ω-model of “∀x∃α ∈ On x ∈ L_{α}.”

If the answer is YES to this question the procedure goes to Step 2.

If NO then it sets s′ = ℕ and EXITS. Otherwise:

Step 2.

If s ∩ Odds ≠ Ø then it proceeds to Step 3. If s ∩ Odds = Ø then it “writes” a copy of the field of the linear ordering isomorphic to the A-ordinals on to the Odds. To say something specific, it defines a set of odd integers coding this field: {2k + 1|2k ∈ A codes a term t_{k} ∧ A ⊨ “t_{k} ∈ On”}. Then it proceeds to:

Step 3i) The process checks that every odd integer in the current s arises indeed from the Field(E_{A} ↾ On^{A}) (which remains coded on the Evens): if not then it sets s′ = ℕ and EXITS. Step 3ii) It looks for the A-least ordinal in this Odd copy of Field(E_{A} ↾ On^{A}), by comparing the contents of the Odds with E_{A}. If it succeeds in finding it, let us suppose it is t_{k_{0}}, it then erases 2k_{0} + 1 from this copy. It thus sets s′ = (s ∩ Evens) ∪ (s ∩ Odds\{2k_{0} + 1}) and EXITS. Suppose it failed to find such a least ordinal. Then this is because the ordering written is illfounded, indeed has no minimal element even (note it is not empty). It sets s′ = ℕ and EXITS.

This completes the description of the successor operation s →= s′.

Remark: s ∩ Evens is left untouched. We let the reader verify the following Claim.

Claim 1 There is an arithmetic formula Φ so that δ_{Φ}(s) = s′ in the above sense. Q.E.D.

At limit stages we are free to apply any Γ limit rule whatsoever. (Note that once the initial “write” at Step 2 of the Field(E_{A}), integers are only removed in the transition from s_{α} to s_{α+1} = δ(s_{α}), or else s_{α+1} = ℕ. Consequently at limit stages of length less than the ordertype of the wellfounded part of E^{A} all integers are either stably in or stably out. Therefore the choice of limit rule is not relevant at these stages, as we have no call to appeal to it.

But we claim it is not relevant at any limit stage.

Claim 2 Let s⃗ be any revision sequence based on δ_{Φ} and any limit rule Γ. Then one of two kinds of sets of stabilities occur: either (i) s_{<∞}^{+} = ℕ or (ii) s_{0} = s_{<∞}^{+} is Π_{1}- T h(L_{μ}) for some ordinal μ < ω_{1}.

Proof: The point is that in “most” cases we have to default to setting s_{α+1} = ℕ. This happens if a) s_{0}∩ Evens does not code correctly an ω-model of ”V = L”; if b) the process discovers an instance of illfoundedness in the Field(E_{A}); or if c) s_{0} ∩ Odds ≠ Ø but is also not a subfield of Field(E_{A}). (Note the first stage at which we would need to appeal to a limit rule to assign values, is when we have a good s_{0} passing the test affirmatively at Stage 1, and whose ordering is wellfounded, and we have cycled through the whole verification process (a multiple of) ω times; then and only then can the bootstrapper/limit rule write something (and then only to the subset of those odds with 2k + 1 ∈ F ield(E_{A})); it can at best thus only write in a set of odd integers that essentially code a sub-ordering of E_{A}. In any case it is impossible for the limit rule to write an ill-founded ordering to Field(E_{A}) = s_{λ} ∩ Odds\(s_{<λ}^{+} ∪ s_{<λ}^{−}), since at this stage we have established that E_{A} contains no illfounded-suborderings!

If we do not default to s_{α} = ℕ (in which case (i) of the claim is thereby ruled out) the only possibility is for the process to repeat successfully: but this only works if s_{0} ∩ Evens codes a suitable Π_{1}-Theory of some wellfounded countable model of V = L. Such a model is isomorphic to some L_{μ} for a limit μ < ω_{1}. As s_{0} ∩ Evens is untouched by the revision process, whereas no odd integers are stably in s_{α} throughout, we conclude that s_{<∞}^{+} = s_{0} ∩ Evens.

Q.E.D.(Claim 2)

Claim 3 B_{0} is S_{Γ}^{∗}-definable.

Proof: We need to show:

B_{0} = ⋂{s_{<∞}^{+} | s⃗ = ⟨s_{α} | α < ∞⟩ is a revision sequence based on Γ, δ_{Φ}}

(⟶) If n ∈ B_{0}, then ∀μ < ω_{1} L_{μ} ⊨ ψ_{n}, and so for all s_{0}, if A = g“Evens\s_{0} codes a wellfounded ω-model A satisfying V = L, then A ⊨ ψ_{n}. This direction then follows from Claim 2.

(⇐). If n ∉ B_{0}, then for some least limit μ < σ L_{μ} ⊨ ¬ψ_{n}. By the leastness of μ one may show that cofinally in μ new Σ_{1} sentences become true. In particular, L_{μ} is the Σ_{1}-Skolem Hull inside itself of the integers. (Thus every element of L_{μ} is given by some Σ_{1} term.) Hence, setting A = g“Evens\s_{0}, A = ⟨ω, E_{A}⟩ ≅ L_{μ}. Let h = s_{0} code the Π_{1} theory of L_{μ}. (Thus s_{0} ∩ Odds = Ø and we have a clean start.) As E_{A} is wellfounded, the process successfully recycles and s_{0} = s_{<∞}^{+}. But n ∉ s_{0}.

Q.E.D.(Claim 3)

If the complete Π_{2}^{1} set of integers is S-definable, then it is easy to modify the above to obtain the same for any other Π_{2}^{1} set z, as any set of this type can be obtained as a recursive preimage of the complete one. If u is any Δ_{2}^{1} set of integers, then u is both Π_{2}^{1} and co-Π_{2}^{1}. Q.E.D.(Theorem 2.1)

By suitably encoding the operator δ_{Φ} into the Tarskian operator δ_{τ}, this method yields a previous result of Burgess [2] that for the language of arithmetic with a T -predicate symbol, the stable truth set over the standard model of arithmetic, using the Belnap Rule Γ_{B}, forms a complete Π_{2}^{1} set.

Comment 1: It would seem then that the Gupta-Belnap theories of truth T^{#} and T^{∗} whilst absolutely defined over the natural numbers ℕ, if one considers the truth sets themselves, it is not hard to ask questions that are sensitive to the axioms of set theory, or equivalently, to the model of set theory one may be working in. For example one can consider T_{0} = T_{ℕ}^{∗} (the latter the T^{∗} truth set over ℕ); T_{k+1} = T_{⟨ℕ,T_{k}⟩}^{∗} for k < ω. One proceeds fairly quickly to the equivalent questions concerning truth sets bounding all the T_{k}. Since each T_{k+1} is essentially a code of the Δ_{2}^{1} jump of T_{k}, one has the variations on the questions concerning minimal upper bounds in the Δ_{2}^{1} degrees, which have different answers depending if V = L or not ... see [7]. Thus as a theory of truth it must yield to the inevitable fact that answers to simple questions concerning truth sets are just not absolute. The author had made this observation (which was subsequently discussed in [16]) before turning to fully varied sequences and the notion of stable categoricity [9] 6D. Here it transpired that the problem is even more acute: when considering truth sets for fully varied sequences (see §3 below) the set of integers coding the truth set over ℕ is itself not absolute between different models of set theory. The phenomenon occurs again (Theorem 5.1) when considering the notion of stable categoricity (concerning which the T_{k} sequence mentioned above could now be considered as the first ω steps of a putative “categoricity operator sequence”). Revision theory must accommodate itself to this lack of absoluteness.

Comment 2: In view of Comment 1, it might throw extra ammunition into the debate as to what revision theories of truth actually are. However as a theory of definability revision theoretic definability seems unexceptionable: it yields the next stable set over a structure. But sensitive questions in the definition of which limit rule to choose are simply overwhelmed by the outer universal quantifier: it allows all possible hypotheses (and hence in the above proof all possible wellfounded relations) to be considered. Although one ostensibly has the potential for quantifying over the power set of the integers by using the Belnap Rule Γ_{B} at limit stages, what Theorems 2.1 and 2.2 also imply is that this is not the point: it is the outer universal quantifier that inevitably raises this complexity to the level of Π_{2}^{1}.

Comment 3: Löwe has raised the suggestion that Infinite Time Turing Machines (ITTMs) may help with sorting out some of these questions. Indeed in [15] Theorem 4.1 he shows explicitly how the action of a revision sequence s⃗ = ⟨s_{α} | α < β⟩ constructed according to the Herzberger minimal rule Γ_{H}, with successor revision step given by some arithmetic δ_{Φ}, with Infinite Time Writable length β, can be modelled on a certain ITTM M_{Φ,β}. Conversely, inputting s_{0} into M_{Φ,β}, the machine will ‘eventually write’ the whole sequence s⃗ to its output tape. (‘Eventually write’ has a technical meaning here: that (a code for) the sequence will eventually be residing on the output tape of such a machine if it is allowed to run for long enough - although the machine process itself may not halt.) In fact the restriction on the lengths of the sequences s⃗ being writable is not necessary here. One can also devise a machine program that runs on input h = s_{0}, and if h is recurrent according to S_{Γ_{H}} and δ_{Φ}, will halt with h on its output tape. This answers one question from [15]: how large can Refl_{Φ,Γ}(h) (essentially the length of the period between h’s occurrence and its reappearance in a revision sequence) be? For Γ = Γ_{H} (or Γ = Γ_{G}), and for any arithmetic Φ, (indeed for a broad class of revision operations δ, and limit rules) it is less than λ^{h} - the supremum of the lengths of time of any halting computation, with 0 on the input tape, with oracle h. With this in mind one can write a “program” that halts precisely on the reappearance of recurrent hypotheses h. But in fact, conversely, one can view any sequence of ITTM computations with input y as some sort of “slow moving” Herzberger revision sequence using the Tarskian revision operator δτ over the structure of arithmetic augmented by a predicate for y: ⟨ℕ, … y⟩: one simply has to code into a suitable diagonalising formula the specification of the machine program.

Comment 4: Similar considerations to that of the theorem show that if L is the language of Arithmetic (or any recursive language that has acceptable models), then V_{L}^{∗} (and V_{L}^{#}) have complexity also precisely that of a complete Π_{2}^{1} set. (Problem 32 of [13]).

Comment 5: We saw in Theorem 2.1 that essentially any reasonable limit rule Γ would define for us the same class of reals. We can generalise this in another direction: we do not even need a theory of circular totally defined definitions in order to do this: instead of requiring that at each stage hypotheses are assumed for the extensions of the predicates being defined that are total, that is totally specify both the extension and the anti-extension of the predicate, it is possible to develop a theory of circular definitions of partial hypotheses, where we have some information as to what is in the extension of a predicate G, and what is not. An attractive feature of such a theory is that it dispenses entirely with limit rules Γ: we should only take the local stability pair set as giving us the current extension and anti-extension: those values that had alternated cofinally in the limit ordinal would then simply be undefined at the limit stage. We should thus have truth-value gaps. We should perform our revisions δ_{Φ} for some formula Φ as before but using some suitable 3-valued logic. However it turns out that exactly the same set of z ⊆ |M| would be definable as the intersection of all stable (partial) extensions arising in this way: namely the same Π_{1}(𝕊_{M})-sets as before.

(To make this plausible, consider the process of the proof of Theorem 2.1: under a regimen as just outlined (using say Kleene’s Strong 3-valued logic), this can be simply taken over. The process will review a “good” hypothesis that contains a true Π_{1} theory in the same way. As mentioned above after Claim 1, no appeal is made to any particular limit rule. In short the set B_{0} will still be definable here. For the converse direction, one may argue that no new sets can be defined. Such kinds of revision sequences based on partial extension/anti-extensions can be constructed using a defining formula Φ in a suitable language containing a predicate symbol Ẋ, which can be partially interpreted as (X^{+}, X^{−}), just as is done using a partially interpreted Ṫ symbol. It is simply that we are not restricting our starting hypotheses to be sound for the operator δ_{Φ} (as is done in the Kripkean theory when one wants to build up to a fixed point using δ_{τ}). It is a straightforward matter to see that such revision sequences can be simulated, for example, on ITTM’s. The latters’ action can in turn be coded into Herzberger revision sequences via some formula Φ′ - which can be effectively determined from Φ. (See the last sentence of Comment 3 above.))

This shows that as a theory of definitions the Belnap and Gupta theory is not of necessity tied to revising totally defined hypotheses: the same class of definable sets arises in the way just described. Again, it is the power of the “outer quantifier” that allows all this to happen.

§3. Fully varied sequences. We consider Yaqūb sequences [22] and the fully varied (fv) sequences of Chapuis [4]. Both authors are only considering sequences formed using the revision function τ - the evaluation of sentences containing a T -predicate, based on the Tarskian biconditionals. We generalise this to arbitrary arithmetic revision operators δ_{Φ}, before specialising it again at Corollary 3.5.

Definition 3.1. A revision sequence (based on a revision rule δ) s⃗ = ⟨s_{α} | α < ∞⟩ is fully varied (fv) if any real r ⊆ ω that is coherent with the whole sequence s⃗, has actually been applied as a bootstrapper to assign values cofinally in ∞.

Remark: In general then a fv-sequence must have length at least 𝔠 = 2^{ℵ_{0}}, that of the continuum - at least prima facie - although it is easy to see by a Löwenheim-Skolem argument, that proper initial segments of sequences determine the set of stabilities; moreover for any fv-sequence s⃗ there is another fv-sequence r⃗ with the same set of stabilities, that in fact is determined by a countable initial segment of r⃗, as follows.

Note: If s⃗ is fv, then as s_{<∞}^{+} is trivially coherent with s_{<∞},{α < lh(s⃗) | s_{α} = s_{<∞}^{+}} is cofinal in lh(s⃗).

Then the stabilization point of a revision sequence is destined to repeat cofinally with the positive truth values those of the stably true integers of the whole sequence.

Lemma 3.1. If s⃗ is fv, σ = σ(s⃗) and t⃗ any revision sequence (not necessarily fv) with t⃗ ↾ σ = s⃗ ↾ σ, then for any limit τ ≥ σ t_{<τ} ⊇ s_{<τ} ⊇ s_{<σ}.

Proof: The second containment follows from the definition of σ. Suppose for a contradiction the first fails, and let τ = γ + ω be the least limit ordinal greater than σ for which this fails, for some limit γ. By induction t_{<γ} ⊇ s_{<γ}, and consequently t_{γ} is coherent with s_{<σ} = s_{<∞}. As s⃗ is fv, t_{γ} = s_{δ} for cofinally many δ > σ. But then s_{δ+ω} = t_{<τ} ⊇ s_{<σ}. Contradiction! Q.E.D.

Corollary 3.2. If s⃗, t⃗ are as above, then s_{<∞} ⊆ t_{<∞}.

For later use we make the definition:

Definition 3.2. Let S denote the class of static pairs; where s = (s^{+}, s^{−}), a disjoint pair, is static iff for all revision sequences t⃗(t_{0} coherent with s ⟶ t_{<∞} ⊇ s). (ii) s ∈ S is “maximal static pair” if no t ∈ S properly contains s,

Thus if s⃗ is fv, and σ is its stabilization point, then the last lemma implies that s_{<σ} ∈ S. Note also that if τ > σ and s_{<τ} ⊈ s_{<σ} then s_{<τ} is not static: because there is a later η > τ with s_{<η} = s_{<σ}. Note: (i) “s ∈ S” can be expressed as a Π_{1}^{1}(δ) predicate: s ∈ S ⟷ ∀t(t ⊇ s ⟶ δ(t) ⊇ s). (ii) Being a maximal static pair similarly is Π_{2}^{1}(δ).

Lemma 3.3. s is a stabilization pair of a fv-revision sequence using a revision operator δ iff s is maximally static.

Proof: Let s⃗ be fv, and s = (s_{<σ}^{+}, s_{<σ}^{−}) its stabilization pair. s is clearly in S, but must also be maximal: if t ∈ S with t ⊇ s then t^{+} occurs on the s⃗ sequence cofinally. But so does s_{<σ}^{+}. Hence we must have s = t. Conversely if s ∈ S is maximal, consider any s⃗ fully varied with s_{0} = s^{+}. Note that we must have s = s_{<σ(s⃗)}. Q.E.D.

Yaqūb has a different definition of revision sequence to enforce variability of limit rule assignments. He makes an implicit use of the Axiom of Choice to wellorder the continuum, and his sequences are (at best) members of H_{𝔠^{++}}. We omit his definition. But it is a result of Chapuis and Gupta ([4] Theorem 3.1, proven for the Tarskian revision rule τ (but which works in this more general setting) that if s is the stabilization pair of a fully varied sequence, then there is a a Yaqūb sequence, with s as its stabilization pair..

We consider then the set of integers that are stably in all fv-sequences. The analogy with S_{Γ}^{∗} is:

Definition 3.3. (i) z ∈ S̃^{∗} iff there is an arithmetic Φ so that:

z = ⋂{s_{<∞}^{+} | s⃗ = ⟨s_{α} | α < ∞⟩ is a fv- revision sequence based on δ_{Φ}}

(ii) For a particular operator δ (not necessarily arithmetic) by S̃_{δ}^{∗} we mean that particular z determined as in (i) but by using δ for δ_{Φ}.

Remark: In (i) above, the very same class S̃^{∗} will result if we restrict δ_{Φ} with Φ varying over just recursive operations, or widen it to all functions δ ∈ Δ_{2}^{1}. We have not given the # form of the definition, as it turns out that the same classes are definable with either formulation.

It looks, again prima facie, that S̃^{∗} is Π_{1}(H_{𝔠^{+}}) definable. But it is simpler than that.

Theorem 3.4. (i) For any operator δ, every z ∈ S̃_{δ}^{∗} is a Π_{3}^{1}(δ) set of integers. (ii) Conversely: S̃^{∗} contains a complete Π_{3}^{1} set of integers.

If we specialise the result to the Tarskian rule τ for partially defined truth predicates we obtain:

Corollary 3.5. Let Ṽ_{ℕ} be the truth set over the standard model of arithmetic, using T̃, the theory of truth for fully varied revision sequences. (That is

Ṽ_{ℕ} = ⋂{s_{<∞}^{+} | s⃗ = ⟨s_{α} | α < ∞⟩ is a fv revision sequence based on δ_{τ}}.)

Then Ṽ_{ℕ} can be construed as a complete Π_{3}^{1} set.

Proof: of theorem (for S̃^{∗}):

(i) Given an arithmetic operator δ_{Φ} it is straightforward to write out the corresponding z ∈ S̃^{∗} in a Π_{3}^{1} way. (See the (≥_{1}) direction below.) We concentrate on the converse (ii): Let T be a complete Π_{3}^{1} set of integers. We can think of T as represented by k ∈ T ⟺ ∀x∃y∀z∀nR(x, y, z, n, k) for some recursive R.

Lemma 3.6. There is an arithmetic Φ so that T ≡_{1} S̃_{δ_{Φ}}^{∗}.

Proof: Again we informally describe a revision operator δ_{Φ} : P(ω) ⟶ P(ω) so that k ∈ T iff for all fv-sequences s⃗, f(k) is stably true in s⃗ (i.e. f(k) ∈ s_{<∞}^{+}), for some total (1-1) recursive f. This will show T ≤_{1} S̃_{δ_{Φ}}^{∗}.

We recursively split up ω into infinitely many infinite blocks B_{k} = {m | r(m) ∈ {k} × ω} where r : ω ↔ ω × ω is some recursive bijection. We reserve the blocks B_{3k}, B_{3k+1}, B_{3k+2} for “thinking about” whether k ∈ T. For any s ∈ P(ω) we view it ambiguously as a function in 2^{ω} and write interchangeably “t ∈ s” or “s(t) = 1.” Given an s = s_{α} ∈ P(ω), we split it recursively into infinitely many other subsets as follows:

m ∈ x_{k} ⟷ ∃t ∈ s (r(t) = ⟨3k, m + 1⟩) m ∈ y_{k} ⟷ ∃t ∈ s (r(t) = ⟨3k + 1, m⟩) m ∈ z_{k} ⟷ ∃t ∈ s (r(t) = ⟨3k + 2, m⟩)

Step 1 We ask: Q. Does ∀nR(x_{k}, y_{k}, z_{k}, n, k) hold?

If NO:

(i) we ‘reverse’ all the digits of z_{k}, or in other words ensure that it is replaced by its complement in forming s_{α+1}. (So, by “reversing” we mean the obvious thing: if r(t) = ⟨3k + 2, m⟩ then t is either removed from, or put into, s_{α} to form s_{α+1} depending on whether m was, or was not, in z_{k} . Thus we shall have, for such t, t ∈ s_{α} ⟺ t ∉ s_{α+1}.)

(ii) We write a “0” in ⟨3k, 0⟩, (that is, ensure that s_{α+1}(t) = 0 where r(t) = ⟨3k, 0⟩), and similarly “reverse” all the digits of y_{k}.

We then go back to the beginning of Step 1.

If YES, we proceed to Step 2.

One must bear in mind that Q is actually infinitely many questions, one for each k.

Step 2

(i) We ensure that a “1” is written in ⟨3k, 0⟩ (i.e. change s, if need be, so that now s(t) = 1, where r(t) = ⟨3k, 0⟩). (ii) We reverse all the digits of z_{k}, and return to Step 1.

This completes the part of the revision process for dealing with k. Of course here we are performing the argument simultaneously as one step for all k, as an arithmetic revision. Claims 1 and 2 below will show that the (1-1) total recursive function f defined by f(k) = s(r^{−1}(⟨3k, 0⟩)) witnesses that T ≤_{1} S̃_{δ_{Φ}}^{∗}.

Claim 1 Suppose s⃗ is a fv-revision sequence. If k ∈ T then s(r^{−1}(⟨3k, 0⟩)) stabilizes on 1.

Proof: Note that from the start of s⃗, for each k, x_{k} is unvaried. The process searches for a y_{k} so that the answer to Q is YES for all z_{k}. If at any stage z_{k} fails to be suitable it is “erased” by reversing all its digits; if this happens cofinally in some limit stage, the values of B_{3k+2} can receive input by the limit rule assignment, and a new z_{k} inspected. We set ⟨3k, 0⟩ according to the answer to Q. If the answer is NO here, it is because we have not yet found a correct y for y_{k}. So we ensured that y_{k} was erased by reversing all of its digits. Because the sequence s⃗ is fully varied, at some stage, if k ∈ T, there will be a y_{k} read in that will work for all z_{k}. From this point on ⟨3k, 0⟩ stabilizes at 1.

Q.E.D.(Claim 1)

Claim 2 If k ∉ T then there is a fv-revision sequence s⃗ so that s(r^{−1}(⟨3k, 0⟩)) does not stabilize on 1.

Proof: If k ∉ T pick x = x_{k} so that

∀y∃z∃n¬R(x_{k}, y, z, n, k) (∗)

Let s⃗ be any fv-sequence with m ∈ x_{k} ⟷ s_{0}(r^{−1}(⟨3k, m + 1⟩)) = 1 (i.e. with our choice of x_{k} written to the appropriate block of the starting hypothesis). Then whatever y_{k} may appear at any stage, however long it lasts on B_{3k+1}, as s⃗ is fv, some z_{k} will be read in witnessing (∗), and thus that s(r^{−1}(⟨3k, 0⟩)) = 0, at some stage.

Further this value of 0 will occur cofinally often in lh(s⃗) if it is truly fully varied. Q.E.D.(Claim 2 and (≤_{1}))

(≥_{1}) We shall just show that for any revision operator δ “n ∈ S̃_{δ}^{∗}” is Π_{3}^{1}(δ). Thus for our arithmetic δ_{Φ}, this is simply Π_{3}^{1} and so is (1 − 1)-reducible to T. Let S be the class of static pairs arising from sequences built according to the revision rule δ. The result follows from:

n ∈ S̃_{δ}^{∗} ⟷ ∀s(s ∈ S ∧ s maximal ⟶ n ∈ s^{+})

by appealing to Lemma 3.3, and the Note (ii) on maximally static pairs immediately preceding it.

Q.E.D.(Lemma & Theorem) .

§4. Realistically Varied Sequences. The following notion of “realistic variance” is supposed to capture some of the advantages of full variance from the last section, without the increase of complexity involved. There is motivation and some discussion of this notion in [21].

Definition 4.1. A revision sequence s⃗ is realistically varied if for all limit l < ∞ s_{λ} is chosen as a coherent extension of s in the following fashion: let s = (s_{<λ}^{+}, s_{<λ}^{−}) be the local pair of stabilities at λ.

(i) Either s_{λ} is recursive in s or in some s_{α} for an α < λ, and s_{λ} has not been used as an application of the limit rule cofinally in λ; (ii) Or, if at stage λ there is no s_{λ} that satisfies clause (i), then s_{λ} may be chosen arbitrarily.

The maxim here is “use the simple ones first” when it comes to formulating limit rules Γ. Note that this takes the form of a local definition and does not have the global nature of the fully varied sequences.

Theorem 4.1. (i) If s⃗ is a realistically varied revision sequence, and if we let s_{<∞} = t = (t^{+}, t^{−}) be the final stability pair set then any s that coheres with t, and is recursive in t, has been used cofinally often in lh(s⃗). (ii) t forms a Kripkean fixed point for the supervaluation jump. (iii) The truth set (over ℕ) for the set of all stably true sentences (quantifying over all realistically varied revision sequences), is complete Π_{2}^{1}.

Proof: Let s, t, s⃗ be as hypothesised. (i) holds by a simple pressing down argument: Let C be the closed and unbounded in ∞ class of points μ where s_{<μ} = t (such exists by the Note (i) following Def.1.4). If s were a counterexample, we should have that on a stationary class, E ⊆ C, of limit ordinals below ∞ either some other fixed s′ ≤_{T} t has been used, or some fixed s′ ≤_{T} s_{γ} has been used for some constant γ. However, considering γ ∈ E which is also a limit point of E, either alternative contradicts the specification of realistically varied. We turn to (ii).

We first prove this under the working assumption that (i) holds for any s with “recursive in t” replaced by “hyperarithmetic in t”, and then show how to reduce this to recursive.

We shall let j_{vF} denote the jump operator for the (regular) van Fraassen supervaluational scheme.

Claim (1): Let u = (u^{+}, u^{−}) =_{df} j_{vF} (t). Then u = t.

Proof: By definition of j_{vF} we have:

u = ( ⋂_{\overline{u}∩t^{−}=Ø^{\overline{u}⊇t^{+}}} j_{T} (⟨ℕ, \overline{u}⟩), ⋂_{\overline{u}∩t^{−}=Ø^{\overline{u}⊇t^{+}}} ℕ\j_{T} (⟨ℕ, \overline{u}⟩))

(Here j_{T} (⟨ℕ, \overline{u}⟩) denotes the set of (codes of) true sentences over ⟨ℕ, \overline{u}⟩ with the T predicate symbol interpreted as \overline{u}.) Essentially “φ ∈ u^{+}” and “φ ∈ u^{−}” are both Π_{1}^{1}. For example, if ∃\overline{u} ⊇ t^{+}, \overline{u} ∩ t^{−} = Ø with ⟨ℕ, \overline{u}⟩ ⊭ φ we can find such a \overline{u} hyperarithmetic in t. [Look at the tree of attempts to assign “true” to some set of sentences \overline{t} ⊇ t^{+}, with \overline{t} ∩ t^{−} = Ø, with the additional property of having ⟨ℕ, \overline{t}⟩ ⊨ ¬φ. This tree is hyperarithmetic in t, has a branch in V if φ ∉ u^{+}, and thus by absoluteness has a branch hyperarithmetic in t.]

Consequently to calculate u it is only necessary to take that intersection above over \overline{u} that are hyperarithmetic in t. Using our working assumption, we may further assume, without loss of generality, that all such \overline{u} appear cofinally below any α in a closed and unbounded class C_{1} ⊆ C. It is then routine to check for such α ∈ C_{1}, t_{<α} = t = j_{vF} (t). Q.E.D.(1)

We turn now to the necessary reduction of the hyperarithmetic case to the recursive one. We need to show that any s that coheres with, and is hyperarithmetic in t, has in fact appeared cofinally in ∞, for then we can appeal to the argument just given.

By the definition of realistically varied, again by a closure argument, there is a cub D ⊆ C so that for any μ ∈ D, any r ≤_{T} t, or r ≤_{T} s_{α} for an α < μ, has been used cofinally in μ.

Idea: To find a recursive subset A of ω\(t^{+} ∪ t^{−}) in which to code a copy of t^{+}, and where we may calculate (copies of) the following sets of integers. (There seem to be many ways of doing this, with the same effect: we just want to guarantee that sufficiently complicated sets do after all, appear sufficiently often, and the following is just one method.) We choose (uniformly for all reals t) an index e for the e’th function recursive in t that is a code for a linear ordering, which has a wellfounded initial segment of length ω_{1ck}^{t} - the least ordinal not recursive in t. (The existence of such an index e is demonstrated in [8].) We may then set t^{1} = t^{+} ⊕ t^{+}′, t^{2} = t^{1} ∩ t^{1}′, … t^{α+1} = t^{α} ∩ t^{α}′ … t^{λ} = ∩_{α<λ}t^{α} (where x′ denotes the Turing jump of x ⊆ ω) repeating the Turing jump operation along the linear ordering, taking intersections at limits. At some point we discover that the linear ordering is not a wellordering, and we simply abort our process at that stage. We now appeal to the fact that any set v ⊆ ω which is hyperarithmetic in t is actually recursive in some t^{α} (for an α < ω_{1ck}^{t}) arising along one of these wellorderings (see [19] Exercise 16.93). As each t^{α} will be coded onto some recursive subset of ω at some stage β, by some stage μ ∈ D we shall have used any possible limit rule value recursive in it unboundedly in μ. The argument of Claim (1) will then yield the full result of (ii).

We now look at the routine details of embedding an arithmetic operator δ into the operations of the δ_{τ} operator. We follow Burgess’ ([2] p678) notation and method here. Let T be the truth predicate symbol of the language, we assume a coding of the language, and adopt the convention that \overline{n} is the numeral for the number n; we let #φ be the number that codes φ, and let ‘φ’ be its numeral. We assume that ℕ is enriched with a symbol for each primitive recursive function. We let Sub(u, v) be the substitution function, for the code number resulting when the term with number v is substituted for the term, or into the formula, numbered u. If ‘k ∈ δ(X)’ is defined by the arithmetic formula Ψ(k, X) we let ψ(k, x) be the formula obyained by translation from Ψ by replacing each atomic instance of ‘k ∈ X’ by T (\overline{Sub}(x, k)). By appealing to the Diagonal Lemma, we may find a formula φ(k) such that φ[\overline{n}] ‘says’ that ψ[\overline{n}, ‘φ(k)’].

We intend to describe an arithmetical operator, η, and then use the above translation of the defining formula for ‘k ∈ η(X)’. If the defining formula is Ψ(k, X), and ψ_{0}(k, x) is this translate, we shall consider

ψ(k, x) ⟺ ψ_{0}(k, x) ∨ [∀v¬T (\overline{Sub}(x, v)) ∧ k = \overline{⟨\overline{0}, m⟩} ∧ T (m)].

Our particular diagonalising formula of ψ then reads:

φ[\overline{n}] ⟺ ψ_{0}[\overline{n}, ‘φ(k)’] ∨ [∀v¬T (\overline{Sub}(‘φ(k)’, v)) ∧ \overline{n} = \overline{⟨\overline{0}, \overline{m}⟩} ∧ T (\overline{m})].

Interpreted this is to mean that n is in the current revision η(X), or else if we are at a stage γ with X = Ø (as it will be for cofinally many γ < ∞) then we intend to put into X the codes of all pairs ⟨0, m⟩ of zero, with codes m of all sentences currently assigned ‘True’ at stage γ, i.e. those elements of s_{γ}. This set will be the starting point of a ‘sub-revision’ of our arithmetic operator η.

We describe the stages of the operation η, and leave it again to the reader to verify that everything can be arithmetically coded.

Definition 4.2. E_{i} =_{df} {⟨i, k⟩ | k ∈ ω}

If E_{1} ∩ X = Ø then we set η(X) = X ∪ {⟨1, ⟨k, l⟩⟩ | {e}^{X}(⟨k, l⟩) ↓= 1}.

If E_{1} ∩ X ≠ Ø and E_{1} ∩ X contains a code of a linear ordering L of ω, then if k is the L-least integer so that E_{k+2} ∩ X = Ø and either:

Case (1) if k is the L-successor of j, and W_{j} =_{df} {m|⟨j + 2, m⟩ ∈ X}, we set y_{k} = W_{j} ∩ W′_{j} (where W′_{j} is the Turing jump of W_{j}).

Case (2) if k is an L-limit then we set

y_{k} = ⋂_{jLk} W_{j}.

In Cases (1) & (2) we set η(X) = X ∪ {⟨k + 2, m⟩ | m ∈ y_{k}}.

If E_{1} ∩ X ≠ Ø but does not code a linear ordering, or if there is no such k as in the two cases above, then set η(X) = Ø.

If we set

η^{0}(X) = X; η^{α+1}(X) = η(η^{α}(X))
η^{<l}(X) = lim inf_{α→λ} η^{α}(X) if Lim(λ).

η^{λ}(X) = η(η^{<λ}(X))

then:

Lemma 4.2. ∀X ∃α η^{α}(X) = Ø.

Proof: Even in the “best case scenario” when X ⊆ E_{0}, the successive operation of η adds more Turing jumps to the sets E_{k+2} along the wellfounded part of the linear ordering L given by {e}^{X}. For limit points λ of the operation then, we have that membership in the sets η^{α}(X) (for α < λ) is stable below λ (elements are only put in.) The only time elements are removed is to set η^{α+1}(X) = Ø. This will eventually happen at stage α = ω_{1ck}^{X} when we encounter the first instance of illfoundedness along {e}^{X}. In other scenarios, it is easy to see at some point one of the clauses will be unfulfilled and we default to the empty set. Q.E.D.

If Ψ(k, X) is this arithmetical formula describing k ∈ η(X) and we “translate” the formula using the method above, and if we assume X is input as s_{γ} say, with

X = {⟨0, n⟩ | n ∈ s_{γ}},

it will not affect us here what choice of s_{λ} is made for limit λ ∈ (γ, ω_{1ck}^{s_{γ}}] as such s_{λ} must cohere with s_{<λ}, and hence will respect the placing of elements into η^{α}(X) for α < λ.

Lemma 4.3. With X, s_{γ} as above, η^{α}(X) ≤_{T} s_{γ+α+1} for α < ω_{1ck}^{s_{γ}}.

Proof: By induction on α. For α ≥ 0, η^{α}(X) = \{n | #φ[\overline{n}] ∈ s_{γ+α+1}\}.

Q.E.D.

Lemma 4.4. With X, s_{γ} as above, if y is hyperarithmetic in s_{γ} then ∃α < ω_{1ck}^{s_{γ}} (y ≤_{T} s_{γ+α}).

Proof: By Shoenfield (see Rogers, [19] Exercise 16.93) every y ⊆ ω hyperarithmetic in X is Turing recursive in some z_{k} for a k < ω_{1ck}^{X} where z_{0} = X; z_{β+1} = z_{β} ∩ z′_{β} and z_{λ} = ∩_{α<λ}z_{α} (for Lim(λ)). Q.E.D.

But for unboundedly many γ ∈ D, we have that s_{γ} = s_{<γ}^{+} = t^{+} (that is the liminf rule was used at these stages). Hence for such γ we have ∀p ∈ ω Sub(‘φ(k)’, p) ∉ s_{γ} = t^{+}. But then by definition of ψ and φ every y hyperarithmetic in s_{γ} = t^{+} is recursive in some s_{β} for a β ≥ γ. Hence every possible hyperarithmetic in t limit rule has been used unboundely often. As indicated at the “Idea” stage above, this completes the proof of (ii) of the Theorem. The proof of (iii) is just as for the truth set using any of the limit rules Γ_{B} etc. Q.E.D.(Theorem 4.1)

Comment 6: The proof of 4.1(ii) uses only the property shown to hold of realistically varied sequences in (i). Thus we could have taken 4.1(i) as the defining property of realistically varied and obtained the same results. We have chosen to define the notion as we have done to emphasise its non-globalarity.

§5. Categoricity. Belnap and Gupta consider an augmented language to that (here) of arithmetic, L′, containing a new predicate symbol K̇ to be interpreted as the current hypothesis concerning the categorical (or stably true) sentences. The basic model of arithmetic is enlarged to a model ℕ^{1} =_{df} ⟨ℕ, T, K⟩ with the displayed predicates being the obvious interpretation. They wish to consider revisions of a hypothesis concerning now what will ultimately be the set of stably true sentences, K, in exactly the same way that revisions were used to create new approximations to truth. One thus takes a hypothesis concerning the categorical sentences, call it K = k_{0}, and uses this extension in the expanded model above. One then finds the stably true sentences relative to the new model in the new language, keeping the extension of K̇ fixed as we perform the revision process on extensions of Ṫ until we have the stably true sentences with this language. The latter yields a new set of sentences as a revised hypothesis for ψ_{ℕ}(k_{0}) = k_{1}.

Definition 5.1. ψ_{ℕ}(k) = {n|n is the gn of a sentence ofL′ that is stably true under the revision process for Ṫ, over the expanded model ℕ^{1}}.

For k⃗ a revision sequence based on ψ_{ℕ} and, say the limit rule Γ_{B}, let k̃_{∞}^{+} be the set of integers almost stably in k⃗, according to the definition of Gupta & Belnap 6D.9.

Thus the set we are interested in is:

z = ⋂{ k̃_{<∞}^{+} | k⃗ = ⟨k_{α} | α < ∞⟩ is a revision sequence based on ψ_{ℕ}, S_{Γ_{B}}^{#} }.

In the above, using ψ_{ℕ}^{n} for the n-fold iteration of the function ψ_{ℕ}:

k̃_{<∞}^{+} =_{df} {m | ∃ recurrent k so that m ∈ ψ_{ℕ}^{n}(k)}.

The authors are attempting to capture the notion of almost stability, that is those m that are almost in k_{<∞}^{+}: they only fail to be in this because they may not be in k_{λ} for a limit λ, and for a finite number of revisions thereafter but there is a fixed n so that for all n ≤ n′ < ω m ∈ k_{λ+n′} for any recurrent k_{λ}. (We make no attempt to justify this definition but refer the reader to [9] 6D.)

We have also chosen just to take the set of stable truths as opposed to the stability set (of all stable truths and falsehoods) but this makes no difference as far as the complexity computation below is concerned: the stable falsehoods are anyway also a complete Π_{2}^{1}- set, thus together they form again such a set.

We shall call the set z above the stably categorical set. We then have the following theorem:

Theorem 5.1. (i) The stably categorical (over ℕ) set of sentences form a Π_{3}^{1} set. (ii) In Gödel’s constructible universe L, this set is (recursively isomorphic to) a complete Π_{3}^{1} set.

Proof: We have seen how for ⟨ℕ, T, … ⟩ the set of sentences stably in T over all revision sequences is a Π_{2}^{1} complete set. We are essentially then trying to calculate the set of all sentences that are stably categorical in the categoricity operator ψ_{ℕ} as a revision operator. We thus have here an operator that has a Π_{2}^{1} description.

It is easy to compute the complexity of the above definition of z as Π_{3}^{1}, using the fact that the graph of ψ_{ℕ} is Δ_{3}^{1}. It is then (1-1) reducible to the complete Π_{3}^{1} set P, say. The hard part is to show that P ≤_{1} z.

Definition 5.2. For x ⊆ ω let σ_{1}^{x} be the least x-stable ordinal. That is, σ_{1}^{x} is the least σ so that L_{σ}[x] ≺_{Σ_{1}} V.

Thus σ_{1}^{x} is On∩𝕊_{⟨ℕ,x⟩} in our earlier notation, and we shall abbreviate the latter structure as 𝕊_{x} =_{df} ⟨L_{σ_{1}^{x}}[x], ∈, x⟩. We have shown that the Π_{1}-Theory of 𝕊_{x} is recursively isomorphic to the set of categorically true sentences of ⟨ℕ, x⟩. Let us call this Π_{1}- theory T_{x}. Then T_{x} is definable over 𝕊_{x} and so is a set in L_{σ_{1}^{x}+1}[x]. We shall consider it coded in a recursive way, as a set of integers uniformly in x.

Definition 5.3. ψ(x) =_{df} T_{x}

Then via this coding, the set z defined above is then recursively isomorphic to the set defined in the same way with ψ replacing ψ_{ℕ}.

Definition 5.4. C =_{df} {α < ω_{1}^{L} | L_{α} ≺_{Σ_{1}} L_{ω_{1}}}.

Then C is the set of countable Σ_{1}-stable ordinals. It is well known that adding the predicate C gives the effect of a Σ_{1}-mastercode. Namely:

Fact 5.1. In L, Π_{n+1}(⟨L_{ω_{1}}, ∈⟩) relations are precisely those that are Π_{n}(⟨L_{ω_{1}}, ∈, C⟩).

By Levy-Shoenfield, then, if we assume V = L, Π_{3}^{1} relations are Π_{2}⟨L_{ω_{1}}, ∈⟩) and so Π_{1}(⟨L_{ω_{1}}, ∈, C⟩).

Definition 5.5. For a constructible set x ∈ L we let ρ_{L}(x) be its L-rank. That is ρ_{L}(x) =_{df} the least α so that x ∈ L_{α+1}.

Now let x = k_{0} be a hypothesis concerning the categorical sentences of ℕ, that is an initial starting hypothesis for a revision sequence using ψ. We let k_{ν} = k_{ν}(x) be the set of integers arising at the ν’th stage of this process - we are thus using the letters k_{ν} rather than s_{ν} to represent the revisions of the categorical hypothesis x.

From our discussion above we see that the rank of k_{ν+1} in the L[k_{ν}]-hierarchy, is just σ_{1}^{k_{ν}}.

Lemma 5.2. (i) If k_{ν} ∈ L then ρ_{L}(k_{ν+1}) = σ_{1}^{k_{ν}}. (ii) For any x ∈ L, σ_{1}^{x} is the least element of C > ρ_{L}(x). Hence if V = L, any ψ-revision sequence satisfies: ∀ν σ_{1}^{k_{ν}} < σ_{1}^{k_{ν+1}}.

Proof: (i) If k_{ν} ∈ L then so is k_{ν+1} by Shoenfield’s Absoluteness theorem, and is Π_{1}(⟨L_{σ_{1}^{kν}} [k_{ν}]⟩). As k_{ν+1} is a complete Π_{1} theory of this model, it is not a member of

L_{σ_{1}^{kν}} [k_{ν}]. Hence ρ_{L}(k_{ν+1}) ≥ σ_{1}^{k_{ν}}.

In L, every set of integers x has ρ_{L}(x) less than σ_{1}^{x} by Σ_{1}-elementarity applied to “∃ξ x ∈ L_{ξ}”. In particular ρ_{L}(k_{ν}) < σ_{1}^{k_{ν}}. Since for any y ∈ L, L_{σ_{1}^{y}}[y] = L_{σ_{1}^{y}}, by applying this to k_{ν}, we have that k_{ν+1} ∈ L_{σ_{1}^{kν} +1}. Hence ρ_{L}(k_{ν+1}) ≤ σ_{1}^{k_{ν}} also. This proves (i), and (ii) is straightforward, using the definition of C and x ∈ L ⟶ L_{σ_{1}^{x}}[x] = L_{σ_{1}^{x}}. Q.E.D.

Assume for the rest of the proof that V = L.

However, now, no such equality as in (i) of the last lemma is true in general for limit λ: we may have (and in fact in many places, must have) ρ_{L}(k_{λ}) < sup_{ν<λ}{σ_{1}^{k_{ν}} }.

Lemma 5.3. There is a (1-1) recursive f : ω ⟶ ω, so that for all x = k_{0}, and for all γ

τ ∈ Π_{2}-Th(L_{ρ(k_{γ}(x)}) ⟷ f(τ) ∈ k_{γ+1}(x).

Proof: Fix an x = k_{0} and for brevity set k_{γ} = k_{γ}(x) etc. Recall that we are identifying k_{γ+1} as the the complete Π_{2}^{1 k_{γ}} set of integers which is recursively isomorphic to Π_{1}-Th(𝕊_{k_{γ}}).

Claim “r = ρ(k_{γ})”, “l = L_{ρ(k_{γ})}”, and “S = Π_{2}-Th(L_{ρ(k_{γ})})” are all Δ_{1}(𝕊_{k_{γ}}).

Proof: of Claim. In general “u = L_{v}” is Δ_{1} over any transitive rudimentary closed model. Hence it suffices to observe:

r = ρ(k_{γ}) ⟷

∀y(y = L_{r+1} ⟶ k_{γ} ∈ L_{r+1}\L_{r}) ⟷ ∃y(y = L_{r+1} ∧ k_{γ} ∈ L_{r+1}\L_{r}).

The other statements are then immediate. This is all uniform in γ and independent of the choice of x. Hence (assuming there is a sensible coding of languages by integers) there is (1-1) recursive f with τ ∈ Π_{2}-Th(L_{ρ(k_{γ})}) ⟺ f(τ) ∈ Π_{1}-Th(𝕊_{k_{γ}}) ≡ k_{γ+1}.

Q.E.D.

Let S_{γ} =_{df} Π_{2}-Th(L_{ρ(k_{γ})}); let T_{γ} =_{df} Π_{1}-Th(L_{σ_{1}^{kγ}} [k_{γ}]). In the notation of the last lemma then there is a fixed (1-1) recursive f : ω ⟶ ω so that for any revision sequence k⃗, and for all γ S_{γ} = f^{−1}”T_{γ}.

Let Ω be least so that L_{Ω} ≺_{Σ_{2}} L_{ω_{1}}. Then as we are assuming V = L, we may identify a complete Π_{3}^{1}-set, P, say, with the complete Π_{2}-theory of ⟨L_{ω_{1}}, ∈⟩, which is thus Π_{2}-definable over ⟨L_{Ω}, ∈⟩.

We shall have:

(1) P = ⋂_{α∈C} Π_{2}-Th(L_{α}) = ⋂_{α∈C∩Ω} Π_{2}-Th(L_{α}) = ⋂_{x∈ℝ∩L_{Ω}} Π_{2}-Th(L_{σ_{1}^{x}}).

The first equality holds by definition of C (note for α ∈ C, Π_{2} sentences are downwards absolute from L_{ω_{1}} down to L_{α}), the second by that of Ω, and the third by 5.2 that σ_{1}^{x} ∈ C for any x ∈ L_{ω_{1}}, and the fact that it suffices to take the middle intersection over all successor elements of C ∩ Ω only.

We note that by the leastness of Ω in its definition, unboundedly below it there are new Σ_{2} facts becoming true: that is for unboundedly many σ < σ′ ∈ C ∩ Ω, Π_{2}- Th(L_{σ}) ⊋ Π_{2}-Th(L_{σ′}) ⊋ Π_{2}-Th(L_{ω_{1}}).

We intend to show:

Claim P ≤_{1} z via the recursive function f.

First suppose that τ ∉ P. We shall define a revision sequence k⃗ with f(τ) not in its ‘almost stability’ set. As τ ∉ P there is a least α_{0} ∈ C ∪ {0} so that if α ∈ C is least greater than α_{0}, we have that τ ∈ Π_{2}-T h(L_{α_{0}})\Π_{2}-T h(L_{α}). Let k_{0} = x where x ⊆ ω codes α_{0}; to be specific, pick x ∈ W O, ||x|| = α_{0}, of least L-rank; then ρ_{L}(x) < α. (Let x = ω if α_{0} = 0.)

(2) There is a revision sequence k⃗ so that ∀δ∃γ > δ ρ_{L}(k_{γ}) > α_{0}.

This then implies, as σ_{1}^{k_{γ}} = ρ_{L}(k_{γ+1}) ∈ C, together with our supposition that L_{α} ⊨ ¬τ, that for all such γ, f(τ) ∉ k_{γ+2}. Then f(τ) ∉ z as required.

Proof: k_{γ} is defined by induction on γ. k_{0} = x is already defined, and for all δ k_{δ+1} = ψ(k_{δ}). Then ρ_{L}(k_{δ+1}) = σ_{1}^{k_{δ}} > ρ_{L}(k_{δ}). Suppose then k_{γ} is defined for all γ < λ and consider the local stability pair set at λ, (k_{<λ}^{+}, k_{<λ}^{−}). Suppose that k^{0} =_{df} k_{<λ}^{0} = ω\(k_{<λ}^{+} ∪ k_{<λ}^{−}) is finite, or that ρ_{L}(k_{<λ}^{+}) ≥ α_{0}, then set k_{λ} = k_{<λ}^{+} (thus we use the liminf rule for such a λ). Otherwise, we shall “fill in” k^{0} with a suitably complicated set of integers A ⊆ k^{0} so that, setting k_{λ} = k_{<λ}^{+} ∪ A, we shall have ρ_{L}(k_{λ+1}) > ρ_{L}(k_{λ}) ≥ α_{0}. We are thus describing an application of a Belnap style ruling at this limit stage, to ensure a sufficiently complicated set. To be specific, let ρ^{0} =_{df} ρ_{L}(k^{0}). It is easy to see that ρ^{0} < α_{0} also.

Let g : k^{0} ⟷ ω be an order preserving bijection recursive in k^{0}. Let A = g^{−1}”x (where x ∈ W O coded α_{0}). There is thus a wellorder of rank α_{0} ∈ C recursive in k^{0} and A. As any element of C is an admissible ordinal, any such wellorder, and thus A itself, must have L-rank ≥ α_{0}. We then set k_{λ} = k_{<λ}^{+} ∪ A. Then check easily that ρ_{L}(k_{λ}) ≥ α_{0}.

This completes the construction of k⃗. The final point to check before claiming that (2) is proven is that for arbitrarily large λ we do in fact have that k_{<λ}^{0} is infinite, and thus we have an opportunity to “fill in” with an appropriate A to raise ranks, if needed. But this is immediate for any revision sequence based on ψ (or any non-trivial revision rule):

(3) ∀γ ∃λ > γ Lim(λ) ∧ k_{<λ}^{0} is infinite.

Proof: Suppose not, and that γ_{0} is such that for all limit λ > γ_{0} k_{<λ}^{0} were finite. But then it is easy to see that this implies that there is \overline{γ} with ∀δ > \overline{γ}, k_{δ} only differs finitely from k\overline{γ}. But this is absurd, as, e.g., k_{δ+1} is the complete Π_{2}^{1,k_{δ}} set of integers.

Q.E.D.(3) & (2)

We now suppose that τ ∈ P. We claim that f(τ) is in the “almost stability” set of any revision sequence k⃗, i.e., f(τ) ∈ z. Suppose for a contradiction k⃗ is a ψ_{ℕ}-revision sequence, and k = k_{β} is a cofinally recurrent hypothesis such that ∀m ∈ ω∃p ∈ ω(m ≤ p ∧ f(τ) ∉ k_{β+p}). But this implies that for some n ≥ 1 there is σ = ρ_{L}(k_{β+n}) ∈ C (recalling that any ρ_{L}(k_{δ+1}) is in C), with τ ∉ Π_{2}-Th(L_{ρ_{L}(k_{β+n})}). However τ is in P, hence τ ∈ Π_{2}-Th(L_{σ}) for any σ ∈ C. Contradiction!

We thus have a (1-1) recursive function f witnessing that P ≤_{1} z.

Q.E.D.(Theorem 5.1)

Conjecture: The theorem is true using the Herzberger Rule Γ_{H} everywhere rather then the Belnap Rule Γ_{B}.

We leave this as an open problem: if true the proof then becomes significantly more complicated, as we have to argue about the ranks ρ_{L}(k_{λ}) without having the advantage of artificially raising them by using the trick above. Similarly we should be surprised if the theorem were not true if S^{∗} replaced S^{#} in the above. As the purpose of this section is to demonstrate the complexity of the sets involved in this concept, we satisfy ourselves with the version based on the official definition of categoricity in [9] above.

REFERENCES

[1] G.A. Antonelli, A revision-theoretic analysis of the arithmetical hierarchy, Notre Dame Journal of Formal Logic, vol. 35 (1994), pp. 204–208.

[2] K.J. Barwise, Admissible sets and structures, Perspectives in Mathematical Logic, Springer Verlag, 1975.

[3] J.P. Burgess, The truth is never simple, Journal for Symbolic Logic, vol. 51 (1986), no. 3, pp. 663– 681.

[4] A. Chapuis, Alternate revision theories of truth, Journal of Philosophical Logic, vol. 25 (1996), pp. 399–423.

[5] P. Clote, A generalization of the limit lemma and clopen games, this Journal, vol. 51 (1986), no. 2, pp. 273 – 291.

[6] K. Devlin, Constructibility, Perspectives in Mathematical Logic, Springer, Berlin, Heidelberg, 1984.

[7] H. Friedman, Minimality in the Δ_{2}^{1}-degrees, Fundamenta Mathematicae, vol. 81 (1974), pp. 183– 192.

[8] R.O. Gandy, On a proof of Mostowski’s conjecture, Bulletin de l’Academie Polonaise des Sciences (série des sciences mathématique, astronomique et physique), vol. 8 (1960), pp. 571–575.

[9] A. Gupta and N. Belnap, The revision theory of truth, M.I.T. Press, Cambridge, 1993.

[10] J. D. Hamkins and A. Lewis, Infinite time Turing machines, this Journal, vol. 65 (2000), no. 2, pp. 567–604.

[11] H.G. Herzberger, Naive semantics and the Liar paradox, Journal of Philosophy, vol. 79 (1982), pp. 479–497.

[12] , Notes on naive semantics, Journal of Philosophical Logic, vol. 11 (1982), pp. 61–102.

[13] P. Kremer, The Gupta-Belnap systems S^{#} and S^{∗} are not axiomatisable, Notre Dame Journal of Formal Logic, vol. 34 (1993), pp. 583–596.

[14] S. Kripke, Outline of a theory of truth, Journal of Philosophy, vol. 72 (1975), pp. 690–716.

[15] B. Löwe, Revision sequences and computers with an infinite amount of time, Journal of Logic and Computation, vol. 11 (2001), pp. 25–40.

[16] B. Löwe and P.D. Welch, Set-theoretic absoluteness and the revision theory of truth, Studia Logica, vol. 68 (2001), no. 1, pp. 21 – 41.

[17] Y. Moschovakis, Elementary induction on abstract structures, Studies in Logic series, vol. 77, North-Holland, Amsterdam, 1974.

[18] , On non-monotone inductive definitions, Fundamenta Mathematicae, vol. 82 (1974), pp. 39–83.

[19] H. Rogers, Recursive function theory, Higher Mathematics, McGraw, 1967.

[20] P.D. Welch, On an algorithmic theory of truth, in preparation.

[21] , On Gupta-Belnap revision theories of truth, Kripkean fixed points and the next stable set, The Bulletin of Symbolic Logic, vol. 7 (2001), no. 3, pp. 345–360.

[22] A. Yaqūb, The liar speaks the truth. a defense of the revision theory of truth, O.U.P, New York,

DEPT. OF MATHEMATICS,

UNIVERSITY OF BRISTOL.

BRISTOL BS8 1TW, ENGLAND. and

GRADUATE SCHOOL OF SCIENCE & TECHNOLOGY, KOBE UNIVERSITY,

ROKKO-DAI, NADA-KU KOBE 657, JAPAN.

E-mail: p.welch@bristol.ac.uk

Current address: Mathematischesinstitut der Universität Bonn,, Beringstr. 6, D-53115 Bonn,, Germany.