pith. sign in

arxiv: 1907.01224 · v1 · pith:EFLX4FOQnew · submitted 2019-07-02 · 💻 cs.AI

Elementary Iterated Revision and the Levi Identity

Jake Chandler , Richard Booth This is my paper

Pith reviewed 2026-05-25 11:24 UTC · model grok-4.3

classification 💻 cs.AI
keywords iterated belief revisionLevi identityHarper identityelementary operatorsnatural revisionrestrained revisionlexicographic revisioncontraction
0
0 comments X

The pith

For elementary iterated revision operators, Nayak's Levi Identity extension equates to postulates treating contraction by negation as mild revision by the sentence, and with Harper constraints this identifies rational revision with natural.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines how to extend the Levi Identity, which defines revision in terms of contraction, to iterated belief change. It restricts attention to the three elementary operators: natural, restrained, and lexicographic. Under mild assumptions on contraction, it establishes that Nayak's proposal for the extension is equivalent to a new set of postulates that treat contraction by the negation of A as mild revision by A. These postulates are shown to jointly amount to a pair of constraints on extending the Harper Identity. Endorsing both the Levi and Harper suggestions yields an identification of rational revision with natural revision.

Core claim

The central claim is that, for elementary revision operators and under mild assumptions regarding contraction, Nayak's proposal is equivalent to a new set of postulates formalising the claim that contraction by ¬A should be considered to be a kind of 'mild' revision by A. These in turn jointly amount to the conjunction of a pair of constraints on the extension of the Harper Identity. Endorsing both suggestions yields an identification of rational revision with natural revision.

What carries the argument

The Levi Identity (LI) extended to iterated belief change for elementary operators, with its equivalence to mild-revision postulates and Harper Identity constraints.

If this is right

  • Nayak's proposal for extending the Levi Identity is equivalent to the mild revision postulates for elementary operators under the mild contraction assumptions.
  • The mild revision postulates jointly amount to the conjunction of two constraints on the extension of the Harper Identity.
  • Endorsing both the Levi extension proposal and the Harper constraints identifies rational revision with natural revision.
  • The three classic iterated revision operators receive a collective characterisation as elementary operators.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The results suggest that iterated contraction and revision may interdefine more tightly than previously separated in dynamic belief models.
  • If the mild revision view generalises beyond the three operators, it could offer a route to deriving revision properties directly from contraction without full reduction.
  • Testing the mild revision postulates against concrete belief change scenarios outside the elementary class would check whether the identification result is special to natural revision.

Load-bearing premise

The analysis restricts itself to the three elementary iterated revision operators and invokes mild assumptions regarding contraction; the equivalences collapse if those assumptions fail for the operators in question.

What would settle it

A counterexample in which, for one of the three elementary operators, Nayak's proposal fails to satisfy the mild revision postulates under the invoked contraction assumptions would falsify the claimed equivalence.

Figures

Figures reproduced from arXiv: 1907.01224 by Jake Chandler, Richard Booth.

Figure 1
Figure 1. Figure 1: Elementary revision by A. The boxes represent states and associated TPOs. The lower case letters, which represent worlds, are arranged in such a way that the lower the letter, the lower the corresponding world in the relevant ordering. The columns group worlds according to the sentences that they validate. So, for example, in the initial ordering, we have w ≺ y ≺ x ∼ z, with y, z ∈ [[A]] and x, w ∈ [[¬A]] … view at source ↗
read the original abstract

Recent work has considered the problem of extending to the case of iterated belief change the so-called `Harper Identity' (HI), which defines single-shot contraction in terms of single-shot revision. The present paper considers the prospects of providing a similar extension of the Levi Identity (LI), in which the direction of definition runs the other way. We restrict our attention here to the three classic iterated revision operators--natural, restrained and lexicographic, for which we provide here the first collective characterisation in the literature, under the appellation of `elementary' operators. We consider two prima facie plausible ways of extending (LI). The first proposal involves the use of the rational closure operator to offer a `reductive' account of iterated revision in terms of iterated contraction. The second, which doesn't commit to reductionism, was put forward some years ago by Nayak et al. We establish that, for elementary revision operators and under mild assumptions regarding contraction, Nayak's proposal is equivalent to a new set of postulates formalising the claim that contraction by $\neg A$ should be considered to be a kind of `mild' revision by $A$. We then show that these, in turn, under slightly weaker assumptions, jointly amount to the conjunction of a pair of constraints on the extension of (HI) that were recently proposed in the literature. Finally, we consider the consequences of endorsing both suggestions and show that this would yield an identification of rational revision with natural revision. We close the paper by discussing the general prospects for defining iterated revision in terms of iterated contraction.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper offers the first collective characterization of the three classic iterated revision operators (natural, restrained, lexicographic) as 'elementary' operators. It examines two extensions of the Levi Identity to the iterated case: a reductive account via rational closure and Nayak et al.'s non-reductive proposal. Under mild assumptions on contraction, it proves Nayak's proposal equivalent to new postulates treating contraction by ¬A as a form of mild revision by A; these postulates are in turn equivalent (under slightly weaker assumptions) to a pair of constraints on extensions of the Harper Identity. Endorsing both proposals is shown to identify rational revision with natural revision. The paper closes with general remarks on defining iterated revision via iterated contraction.

Significance. If the equivalences hold under the stated assumptions, the work supplies a unified perspective on iterated belief change that connects revision-based and contraction-based approaches and yields a concrete identification of rational revision with natural revision. The collective characterization of elementary operators is a clear contribution to the literature. The results are conditional on explicitly qualified assumptions, which limits their immediate scope but also makes the claims falsifiable by checking those assumptions against the three operators.

major comments (2)
  1. [sections presenting the equivalence theorems and the final identification] The central chain of equivalences (Nayak proposal ≡ mild-revision postulates ≡ HI-extension constraints) and the final identification of rational with natural revision are all conditioned on 'mild assumptions regarding contraction.' The manuscript states these assumptions but does not verify that they hold for natural, restrained, and lexicographic revision (the operators characterized collectively in the section on elementary operators). Without this verification, the claimed equivalences do not apply to the operators under discussion and the identification does not follow.
  2. [section on elementary operators and the equivalence sections] The collective characterization of elementary operators is used to ground all subsequent results, yet the paper does not show that the three operators satisfy the contraction assumptions invoked for the Levi-Identity extensions. This leaves open whether the equivalences are operator-specific or hold only under additional restrictions not stated in the characterization.
minor comments (2)
  1. The paper would benefit from an explicit definition or boxed statement of the 'mild assumptions regarding contraction' so readers can immediately check their applicability to the three operators.
  2. Notation for the iterated operators and the new postulates could be made more uniform across sections to ease comparison of the equivalence proofs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive report and for identifying the need to link the elementary-operator characterization more explicitly to the contraction assumptions. We address each major comment below and will incorporate the requested verifications in the revised manuscript.

read point-by-point responses

  1. Referee: The central chain of equivalences (Nayak proposal ≡ mild-revision postulates ≡ HI-extension constraints) and the final identification of rational with natural revision are all conditioned on 'mild assumptions regarding contraction.' The manuscript states these assumptions but does not verify that they hold for natural, restrained, and lexicographic revision (the operators characterized collectively in the section on elementary operators). Without this verification, the claimed equivalences do not apply to the operators under discussion and the identification does not follow.

    Authors: We agree that the equivalences and the identification of rational with natural revision are conditional on the mild contraction assumptions, and that the manuscript does not explicitly verify these assumptions for the three elementary operators. In the revision we will add a dedicated lemma (or appendix) that confirms natural, restrained and lexicographic revision each satisfy the stated contraction assumptions, using only the properties already established in the collective characterization of elementary operators. This will make the applicability of the results to the three operators fully explicit. revision: yes

  2. Referee: The collective characterization of elementary operators is used to ground all subsequent results, yet the paper does not show that the three operators satisfy the contraction assumptions invoked for the Levi-Identity extensions. This leaves open whether the equivalences are operator-specific or hold only under additional restrictions not stated in the characterization.

    Authors: The definition of elementary operators was chosen precisely because it encodes the properties needed for the subsequent Levi-Identity results. Nevertheless, the referee is correct that an explicit check is required to close the gap. The revision will therefore include a short proof that each of the three classic operators meets the contraction assumptions, thereby showing that no further operator-specific restrictions are needed beyond the elementary characterization itself. revision: yes

Circularity Check

0 steps flagged

No significant circularity; equivalences are conditional logical derivations

full rationale

The paper offers a collective characterisation of three iterated revision operators as 'elementary' and proves equivalences between Nayak's proposal, a new set of postulates on mild revision, and constraints on HI extensions, all explicitly conditioned on 'mild assumptions regarding contraction.' These steps consist of postulate formulations and equivalence proofs in standard AGM-style belief revision theory. No derivation reduces by the paper's own equations to a fitted parameter, self-referential definition, or unverified self-citation chain; the assumptions are stated as external conditions rather than smuggled in by construction. The work is self-contained against external benchmarks in the form of logical entailment checks, yielding independent content in the proofs themselves.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only; the paper operates entirely within the standard AGM framework for belief revision and contraction. No free parameters, new entities, or ad-hoc axioms are mentioned.

axioms (1)
  • standard math Standard AGM postulates for single-shot revision and contraction
    The entire discussion of iterated extensions presupposes the classical AGM setting for the base operators.

pith-pipeline@v0.9.0 · 5802 in / 1384 out tokens · 27744 ms · 2026-05-25T11:24:36.587269+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Journal of Symbolic Logic 50(2), 510–530 (1985)

    Alchourr ´on, C.E., G¨ardenfors, P., Makinson, D.: On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic 50(2), 510–530 (1985)

    work page 1985

  2. [2]

    Journal of Applied Non-Classical Logics 11(1-2), 35–58 (2001)

    Booth, R.: The lexicographic closure as a revision process. Journal of Applied Non-Classical Logics 11(1-2), 35–58 (2001)

    work page 2001

  3. [3]

    In: Proc

    Booth, R., Chandler, J.: Extending the Harper Identity to iterated belief change. In: Proc. IJCAI 2016. pp. 987–993 (2016)

    work page 2016

  4. [4]

    Booth, R., Chandler, J.: The irreducibility of iterated to single revision. J. Philosophical Logic 46(4), 405–418 (2017)

    work page 2017

  5. [5]

    In: Proc

    Booth, R., Chandler, J.: On strengthening the logic of iterated belief revision: Proper ordinal interval operators. In: Proc. KR 2018. pp. 210–219 (2018)

    work page 2018

  6. [6]

    Journal of Artificial Intelligence Research 26(1), 127–151 (2006)

    Booth, R., Meyer, T.: Admissible and restrained revision. Journal of Artificial Intelligence Research 26(1), 127–151 (2006)

    work page 2006

  7. [7]

    Journal of Philosophical Logic pp

    Booth, R., Meyer, T.: How to revise a total preorder. Journal of Philosophical Logic pp. 1–46 (2011)

    work page 2011

  8. [8]

    Journal of Philo- sophical Logic 25(3), 263–305 (1996)

    Boutilier, C.: Iterated revision and minimal change of conditional beliefs. Journal of Philo- sophical Logic 25(3), 263–305 (1996)

    work page 1996

  9. [9]

    Journal of Philosophical Logic 37(5), 501–520 (2008)

    Chopra, S., Ghose, A., Meyer, T., Wong, K.S.: Iterated belief change and the Recovery ax- iom. Journal of Philosophical Logic 37(5), 501–520 (2008)

    work page 2008

  10. [10]

    Artificial Intelligence 89(1), 1–29 (1997)

    Darwiche, A., Pearl, J.: On the logic of iterated belief revision. Artificial Intelligence 89(1), 1–29 (1997)

    work page 1997

  11. [11]

    Journal of the Brazilian Computer Society 24(1), 8 (Jul 2018)

    Ferm ´e, E., Wassermann, R.: On the logic of theory change: Iteration of expansion. Journal of the Brazilian Computer Society 24(1), 8 (Jul 2018)

    work page 2018

  12. [12]

    Erkenntnis 49(1), 21–56 (1998)

    Glaister, S.M.: Symmetry and belief revision. Erkenntnis 49(1), 21–56 (1998)

    work page 1998

  13. [13]

    In: Proc

    Goldszmidt, M., Morris, P.H., Pearl, J.: A maximum entropy approach to nonmonotonic reasoning. In: Proc. AAAI 1990. pp. 646–652 (1990)

    work page 1990

  14. [14]

    Journal of Philosophical Logic 17(2), 157– 170 (1988)

    Grove, A.: Two modellings for theory change. Journal of Philosophical Logic 17(2), 157– 170 (1988)

    work page 1988

  15. [15]

    In: PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association

    Harper, W.L.: Rational conceptual change. In: PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association. pp. 462–494. JSTOR (1976)

    work page 1976

  16. [16]

    Artificial Intelligence52(3), 263–294 (1991)

    Katsuno, H., Mendelzon, A.O.: Propositional knowledge base revision and minimal change. Artificial Intelligence52(3), 263–294 (1991)

    work page 1991

  17. [17]

    In: Scalable Uncertainty Management

    Konieczny, S., Pino P ´erez, R.: On iterated contraction: Syntactic characterization, represen- tation theorem and limitations of the levi identity. In: Scalable Uncertainty Management. pp. 348–362 (2017)

    work page 2017

  18. [18]

    Lehmann, D.: Another perspective on default reasoning. Ann. Math. Artif. Intell 15, 61–82 (1992)

    work page 1992

  19. [19]

    Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artificial intel- ligence 55(1), 1–60 (1992)

    work page 1992

  20. [20]

    Synthese 34(4), 423–455 (1977)

    Levi, I.: Subjunctives, dispositions and chances. Synthese 34(4), 423–455 (1977)

    work page 1977

  21. [21]

    In: Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics, 7.-12

    Nayak, A.C., Goebel, R., Orgun, M.A., Pham, T.: Iterated belief change and the Levi Identity. In: Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics, 7.-12. August 2005 (2005)

    work page 2005

  22. [22]

    Artificial Intelli- gence 146(2), 193–228 (2003)

    Nayak, A.C., Pagnucco, M., Peppas, P.: Dynamic belief revision operators. Artificial Intelli- gence 146(2), 193–228 (2003)

    work page 2003

  23. [23]

    In: Towards Mathematical Philosophy, pp

    Rott, H.: Shifting priorities: Simple representations for twenty-seven iterated theory change operators. In: Towards Mathematical Philosophy, pp. 269–296. Springer (2009)

    work page 2009

  24. [24]

    Segerberg, K.: Irrevocable belief revision in dynamic doxastic logic. Notre Dame Journal of Formal Logic 39(3), 287–306 (1998) Elementary Iterated Revision and the Levi Identity 13 Appendix Proposition 1 Given (C1∗ ≼)–(C4∗ ≼), (IIAI ∗ ≼) is equivalent to the conjunction of: (β1∗ ≼) Ifx̸∈ min(≼Ψ, [ [C] ]),x≺A y, andy ≼Ψ∗A x, theny ≼Ψ∗C x (β2∗ ≼) Ifx̸∈ min(...

    work page 1998