Characterizability in Belief Revision

1 Introduction

How to incorporate changes into a knowledge base is a fundamental problem of AI, referred to as the problem of belief change. The main approach to belief change is the AGM approach pioneered by [Alchourr´on, G¨ardenfors, and Makinson, 1985]. There is a large variety of results characterizing classes of belief change operators in terms of rationality postulates [Hansson, 1999].

Are there cases where no characterization can be given?

In view of the many positive results, it seems natural to ask this question. Non-axiomatizability and undefinability questions are much studied in mathematical logic and similar issues were also considered in modal logic [Blackburn, de Rijke, and Venema, 2001] and dynamic epistemic logic [van Ditmarsch, van der Hoek, and Kooi, 2007].

Having tools to prove non-characterizability could be useful when one tries to understand the properties of a class of revision operators. While the standard presentations of belief change start with a set of postulates and then find a matching class of revision operators, there may be situations when a class of revision operators comes first. This may happen, for example, when one considers a class of revision operators which is a natural variant of previously considered ones, such as belief bases instead of belief sets. Also, one may introduce a class of efficiently computable revision operators for practical purposes. In these cases one may inquire what are the properties of the given class of revision operators? For instance, does it form a "nice" class, which can be characterized by postulates?

∗Partially supported by NSF grant CCF-0916708

Proving non-characterizability presupposes a formal definition of a postulate. However, as noted in the survey [Ferm´e and Hansson, 2011]

"theories of belief change developed in the AGM tradition are not logics in a strict sense, but rather informal axiomatic theories of belief change. Instead of characterizing the models of belief and belief change in a formalized object language, the AGM approach uses a natural language (ordinary mathematical English) to characterize the mathematical structures under study."

As far as we know, the first result on characterizability for belief revision was given by [Schlechta, 2004] in the framework of distance semantics [Lehmann, Magidor, and Schlechta, 2001]. This work was extended by [Ben-Naim, 2006].

In this paper, we provide a formal framework for studying characterizability based on the approach of [Katsuno and Mendelzon, 1991]. A revision operator ∗ is considered to assign a revised knowledge base K ∗ϕ to every knowledge base K and every revising formula ϕ. However, the results remain valid if one considers ∗ to act on a fixed knowledge base K and an arbitrary revising formula ϕ. We are not discussing iterated revision here, so there is no interaction between the revisions of different knowledge bases. Katsuno and Mendelzon prove the following results:

1. There is a finite set of postulates such that a revision operator satisfies these postulates iff there is a faithful total preorder representing it with minimization.
2. There is a finite set of postulates such that a revision operator satisfies these postulates iff there is a faithful partial preorder representing it with minimization.
3. There is a finite set of postulates such that a revision operator satisfies these postulates iff there is a faithful poset representing it with minimization.

Part a) is a finite version of Grove's characterization of the AGM postulates in terms of systems of spheres [Grove, 1988]. Part b) is about a more general class of operators and the postulates characterizing it are different from a). The postulates in c) turns out to be the same as in b), i.e., every operator satisfying the postulates in b) can already be represented by a faithful poset.

We consider the following general question. Let R be a family of partial preorders. Is there a finite set of postulates such that a revision operator satisfies these postulates iff there is a faithful partial preorder from R representing it with minimization? The general setup is illustrated below 1 .

This problem corresponds to situations when the partial preorders over the possible worlds are known to satisfy certain properties, and the question is what additional properties of the revision operators are entailed by this extra information. For example, total orders mean that any two models can be compared. Bounded height means that the length of any chain of comparable models is bounded; thus, in a sense, our ability to rank models is limited. Another interesting class (not considered in this paper) is that of orders of bounded dimension [Trotter, 1992]. Here the assumption is that the comparison between two models is determined by a bounded number of underlying criteria, each represented by a total order, and a model is preferred to another if it is preferred according to each criterion.

Our goal is to "characterize postulate characterizability". This is achieved for families of partial orders by showing that the answer to the question is positive iff the family is definable by a ∀MSOmin sentence, which is a special kind of monadic second-order sentence. Interestingly, ∀MSOmin definability turns out to be incomparable to first-order definability. We use the characterization to give several examples of characterizable and non-characterizable classes of revision operators. The negative results are proved using a "forgetful" version of the Ajtai-Fagin variant of Ehrenfeucht-Fra¨ıss´e games [Ajtai and Fagin, 1990; Libkin, 2004].

In Sections 2-7 of the paper we set up the framework for the discussion of characterizability and provide the tools used in the second part of the paper. Sections 8-10 define the classes of revision operators considered, and prove the results on characterizability, resp., non-characterizability. Section 11 contains a diagram summarizing the relationships between characterizability and logical definability. Due to lack of space, proofs are outlined only or omitted.

1 As discussed later on, the mapping from posets to operators is a bijection, unlike in the general case of partial preorders. Therefore we restrict ourselves to posets in this paper.

2 Preliminaries

We consider propositional logic knowledge bases K over a fixed finite set of variables. We write Kn to indicate that K is over n variables. A knowledge base is represented by a single formula 2 . Truth assignments (or interpretations, models, possible worlds) are assignments of truth values to the variables. The set of truth assignments satisfying a formula ϕ is denoted by |ϕ|. Given a set A of truth assignments, 〈A〉 is some formula ϕ such that |ϕ| = A.

Given a knowledge base K, a belief revision operator ∗ assigns a formula K∗ϕ to every formula ϕ. Here ϕ is called the revising formula, and K ∗ ϕ is called the revised knowledge base.

A partial preorder is R = (X,≤), where X is a finite ground set and ≤ is a reflexive, transitive binary relation. A poset (or partial order) is, in addition, antisymmetric. Elements a and b are comparable if a ≤ b or b ≤ a holds. Otherwise they are incomparable. The comparability graph of R is the undirected graph over X such that for any pair of vertices (a, b) is an edge iff a ≤ b or b ≤ a. Elements a and b in a partial preorder are twins, denoted by a ≈ b, if a ≤ b and b ≤ a. An element a is minimal if there is no b such that b < a, where b < a iff b ≤ a but a ̸≤ b. If X′ ⊆ X then a is minimal in X′ if a ∈ X′ and there is no b ∈ X′ such that b < a. The set of minimal elements of X′ is denoted by min≤X′ , or simply minX′ if ≤ is clear from the context.

Partial preorders will be used to represent preferences over truth assignments, with truth assignments satisfying the knowledge base being most preferred 3 . This assumes that partial preorders considered have a special structure, referred to as regularity in this paper.

Definition 2.1. (Regular partial preorders) A partial preorder is regular if

1. every minimal element is smaller than any non-minimal element and

2. the number of elements is a power of 2.

The first assumption means that every truth assignment satisfying the knowledge base is preferred to every truth assignment not satisfying it. This is a standard assumption in belief change theory. The second assumption is made because the number of truth assignments is always a power of two, and we identify the elements of the partial preorder with truth assignments. From the point of view of partial preorders these are mild technical assumptions which do not have an essential effect on definability. An example of a non-regular partial preorder is the 4-element poset with a < b, c < d and no other comparability. Condition 1 is satisfied, for example, if there is a unique minimal element.

The following is one of the standard representations of an epistemic state, i.e., a knowledge base with additional epistemic information used in the belief change operations.

2 We note that because of finiteness this representation corresponds to the belief set framework. Computational complexity issues are not discussed here thus the details of the representation are irrelevant.

3 Following standard usage, a ≤ b is taken to mean that a is preferred to b.

Definition 2.2. (Faithful partial preorder) A faithful partial preorder for a knowledge base Kn is a pair F = (R, t), where R = (X, ≤) is a regular partial preorder and t : X → {0, 1}n is a bijection between the elements of X and truth assignments, such that a ∈ X is minimal iff t(a) satisfies Kn.

In the standard definition the partial preorder is defined over the set of truth assignments. For our discussion it is more convenient to separate the partial preorder and the labeling of its elements by truth assignments. Similar distinctions are made in modal logic as well [Blackburn, de Rijke, and Venema, 2001].

3 Revision UsingMinimization

One of the basic approaches to belief change is to perform minimization using epistemic states represented by faithful partial preorders.

Definition 3.1. (Revision using minimization) The revision operator ∗F for K, determined by a faithful partial preorder F for K, using minimization is

Thus the revised knowledge base is satisfied by the minimal satisfying truth assignments of the revising formula. Faithfulness implies that if the revising formula is consistent with the knowledge base then the revised knowledge base is the conjunction of the knowledge base and the revising formula.

The definition is illustrated in the figure below. Let n = 2 and the knowledge base be K = x1 ∧ x2. Then F1, F2 and F3 are faithful partial preorders for K. The double line in F3 indicates that t-1 (01) and t-1 (00) are twins. Consider the revising formula ϕ = ¯x1. Elements belonging to t-1 (|ϕ|) are shown as black dots and the elements of min≤ t-1 (|ϕ|) are in ovals. Then it holds that

K ∗F1 ϕ = ¯x1 ∧ x2 and K ∗F2 ϕ =K ∗F3 ϕ = ¯x1.

Note that the regular partial preorders underlying F1 and F2 are posets, the first one is total and the second one is not. The revision operator ∗F1 satisfies the postulate "if K and ϕ are inconsistent then |K ∗ϕ| is a singleton". The revision operator ∗F2 does not satisfy the postulate. Also, note that the regular partial preorders underlying F2 and F3 are not isomorphic, but the corresponding revision operators are identical. The difference between revision operators determined by partial preorders and posets, indicated by this example, can be formulated as follows.

Definition 3.2. A revision operator ∗ is poset-based if it is of the form ∗F for some faithful poset F.

Lemma 3.3. a) There are non-isomorphic regular partial pre-orders R1 and R2 such that there are faithful partial preorders F1 = (R1, t1) and F2 = (R2, t2) with ∗F1 = ∗F2 .

b) Let K be a knowledge base, and ∗ be a poset-based revision operator. Then there is a unique faithful poset F such that ∗ = ∗F .

4 Postulates and Characterizability

Consider the AGM postulate

Here K, K ∗ϕ and ϕ can be considered as unary predicates over the set of truth assignments, and thus the above postulate can be rewritten as

Postulates refer to a fixed knowledge base K, and are implicitly universally quantified over formula symbols such as ϕ. They express general requirements that are supposed to hold for all revising formulas. Our proposed definition generalizes this example. This definition is one possibility to formalize the notion of a postulate, It seems natural and covers most postulates considered for belief revision operators (but see the remark after the definition). In order to emphasize that this is just one, though hopefully basic, notion, we refer to such postulates as basic.

Definition 4.1. (Basic postulate) A basic postulate P is a first-order sentence with unary predicate symbols K, ϕ1, . . . , ϕℓ and K ∗ µ1, . . . ,K ∗ µm, where µ1, . . . , µm are Boolean combinations of ϕ1, . . . , ϕℓ.

A revision operator satisfies a basic postulate for a knowledge base K if the basic postulate holds for all ϕ1, . . . , ϕℓ, with the variables ranging over the set of sets of truth assignments.

Allowing for Boolean combinations as arguments to the belief revision operator is necessary as many postulates use such constructs. For example, the AGM postulates refer to K ∗ (ϕ ∧ ψ). Definition 4.1 covers most postulates in [Katsuno and Mendelzon, 1991] and in Section 7.3 of [Hansson, 1999]. The postulate of relevance seems to be an example which is not covered by this definition. Using terminology to be introduced later on, its standard definition is still monadic second-order but it contains a quantifier alternation.

The definition of characterizability applies to revision operators within the partial preorder minimization framework. Classes of revision operators can be defined by specifying a class of partial preorders.

Definition 4.2. (R-revision operator) Let R be a family of regular partial preorders. Let K be a knowledge base and ∗ be a revision operator for K. Then ∗ is an R-revision operator iff there is a faithful partial preorder F = (R, t) for K with R ∈ R, representing ∗ using minimization.

Lemma 3.3 shows that there is a bijection between posetbased revision operators and the posets generating them, while this is not always the case for revision operators generated by partial preorders. Therefore, in the rest of the paper we restrict the discussion to posets for simplicity.

Definition 4.3. (Characterization, characterizability) Let R be a family of regular posets. A finite set of basic postulates P characterizes R-revision operators if for every knowledge base K and every poset-based revision operator ∗ for K the following holds: ∗ satisfies the basic postulates in P iff ∗ is an R-revision operator.

The family of R-revision operators is characterizable if there is a finite set of basic postulates characterizing Rrevision operators.

5 min-formulas and Translation

We define a translation of basic postulates as defined in Definition 4.1 into sentences over an extension of the first-order language of posets. The language of posets contains the binary relation symbol ≤ and equality.

The translated sentences also contain additional unary predicate symbols A1, . . . , Aℓ. These correspond to propositional formulas ϕ1, . . . , ϕℓ occurring in the basic postulates. We introduce some notation for the translations.

Definition 5.1. (Hat) Given a Boolean combination µ of ϕ1, . . . , ϕℓ, we denote by ˆµ the first-order formula obtained by replacing the ϕ's with A's.

For instance, for µ(x) = ϕ1(x), one has ˆµ(x) = A1(x), and for µ(x) = ϕ1(x) ∧ ϕ2(x), one has ˆµ(x) = A1(x) ∧ A2(x).

Given a formula ν over the language ≤, A1, . . . , Aℓ with a single free variable x we write minν≤ for a formula expressing that x is a minimal element satisfying ν, i.e.,

When ≤ is clear from the context it is omitted as a subscript. Minimal elements in the poset are defined by

We need the special cases when the formula ν is a Boolean combination of the unary predicates A1, . . . , Aℓ.

Definition 5.2. (min-formula) Amin-formula over the unary predicate symbols A1, . . . ,Aℓ is a first-order formula built from the Ais and formulas of the form minν≤(x), where the ν's are arbitrary Boolean combinations of the Ais.

Now we can define the translation of a basic postulate.

Definition 5.3. (Translation) The translation τ(P) of a basic postulate P is the min-sentence obtained from P by replacing

1. every occurrence of K(x) with min(x),
2. every occurrence of ϕi(x) and µi(x) with their "hat" versions and
3. every occurrence of K ∗ µi with min ˆ µi (x).

Note that Part 2 in the definition is redundant as the definition for ϕi is a special case of the definition for µi. The translation of a basic postulate is a first-order sentence over the predicate symbols ≤, A1, . . . , Aℓ. It is based on the observation that the definition of revision by minimization (Definition 3.1) uses the underlying poset in a restricted manner, by simply taking the minimal elements of the revising formula.

Example 5.4. (Translation of basic postulate (2)) Applying Definition 5.3 we get the min-sentence

The following is a direct consequence of the definitions, as τ is a simple syntactic transformation.

Proposition 5.5. The mapping τ is a bijection between basic postulates containing revising formulas ϕ1, . . . , ϕℓ and minsentences over unary predicates A1, . . . , Aℓ.

In order to interpret min-formulas let us introduce the following.

Definition 5.6. (ℓ-extension) Let R = (X,≤) be a partial preorder. An ℓ-extension of R is a structure

where A1, . . . , Aℓ are unary relations 4 .

Given K, ϕ1, . . . , ϕℓ and a faithful partial preorder F for K, the (ϕ1, . . . , ϕℓ)-extension of F is determined in the standard way, by interpreting the unary predicate symbols A1, . . . ,Ak by Ai(a) = ϕi(t(a)). We recall that a distinction is made between an element a of the poset, and the truth assignment t(a) assigned to that element. Again, the following proposition is a direct consequence of the definitions.

Proposition 5.7. Let K be a knowledge base, F = (R, t) be a faithful partial preorder for K and let ∗F be the revision operator determined by F using minimization. Let ϕ1, . . . , ϕℓ be propositional formulas and P be a basic postulate. Then P is satisfied by ∗F for ϕ1, . . . , ϕℓ iff the (ϕ1, . . . , ϕℓ)-extension of F satisfies τ(P).

6 ∀MSOmin -definability

In the next two sections we develop the concepts and tools for the logical characterization of postulate characterizability using finite model theory [Ebbinghaus and Flum, 2006; Libkin, 2004].

As propositional logic formulas occurring in the basic postulates are implicitly universally quantified and such formulas are translated into subsets of the partial preorders, it is natural to consider universal monadic second-order logic.

A universal monadic second-order (∀MSO) sentence is of the form

where A1, . . . , Aℓ range over unary predicates (or subsets) of the universe, and Ψ is a first-order sentence using the unary predicate symbols A1, . . . ,Aℓ in addition to the original language (in our case ≤ and equality). An existential secondorder (∃MSO) sentence is of the form Φ = ∃A1, . . . , AℓΨ.

4 With an abuse of notation, we use the same notation for a predicate symbol and its interpretation over a structure, assuming that the structure is clear from the context.

As noted in the previous section, translations of basic postulates, such as (4), have special structure. They only refer to the underlying order relation ≤ in a restricted manner, only inside a min ˆµ≤-formula. Thus we are using only a fragment of universal monadic second-order logic, defined as follows. The definition of ∃MSOmin sentences is analogous.

Definition 6.1. (∀MSOmin sentence) A ∀MSOmin sentence is a universal second order sentence where Ψ is a minsentence.

For example, universally quantifying in (4) over the second-order variable A1 we get the ∀MSOmin sentence

Thus from the formal rewriting of the AGM postulate (1) as (2), we arrive at (6) through the intermediate step (4). Each step is a simple, invertible syntactic transformation.

Definition 6.2. (∀MSOmin -definability) A family R of regular posets is ∀MSOmin -definable if there is a ∀MSOmin sentence Φ such that for every regular poset R it holds that R ∈ R iff R satisfies Φ.

The logical characterization of basic postulate characterizability can now be stated.

Theorem 6.3. Let R be a family of regular posets. The family of R-revision operators is characterizable iff the family R is ∀MSOmin -definable.

This theorem reduces questions about characterizability to questions about ∀MSOmin -definability. The next section develops tools from finite model theory for proving undefinability.

7 Games

The q-round first-order Ehrenfeucht - Fra¨ıss´e game over two relational structures is played by two players, Spoiler and Duplicator. In each round Spoiler picks one of the structures and an element of that structure. Duplicator responds by picking an element in the other structure. After q rounds Duplicator wins if the mapping, assigning elements picked in the same round to each other, yields isomorphic substructures. Otherwise Spoiler wins. A basic result is that a class of structures is first-order definable iff there is a q such that if the q-round game is played on two structures, one belonging to the class and the other not, then Spoiler has a winning strategy.

In the following definitions we use ∃MSOmin instead of ∀MSOmin for convenience; ∃MSOmin -definability of a class is the same as ∀MSOmin -definability of its complement. First we discuss ∃MSO, and then its min-version. The first-order Ehrenfeucht - Fra¨ıss´e game has a variant corresponding to ∃MSO definability. A modified version, which is easier to use for proving undefinability, is defined in [Ajtai and Fagin, 1990]. Let R be a class of structures.

Definition 7.1. ((R, ℓ, q)-∃MSO Ajtai-Fagin game) Given a class R of structures and parameters ℓ and q, the (R, ℓ, q)- ∃MSO Ajtai-Fagin game is played as follows:

1. Duplicator picks a structure R1 ∈ R,
2. Spoiler picks ℓ subsets A1, . . . , Aℓ of the universe of R1,
3. Duplicator picks a structure R2 ̸∈ R and subsets B1, . . . ,Bℓ of the universe of R2,
4. Spoiler andDuplicator play a q-round first-order Ehrenfeucht - Fra¨ıss´e game on the structures extended with the subsets (i.e., unary relations) selected.

The connection between ∃-definability and the Ajtai-Fagin game is as follows.

Theorem 7.2. [Ajtai and Fagin, 1990] A class R is ∃MSOdefinable iff there are ℓ, q such that Spoiler has a winning strategy in the (R, ℓ, q)-∃MSO Ajtai-Fagin game.

We introduce now a further modification of the Ajtai-Fagin game, defined for partial orders only. We refer to this game as the Katsuno-Mendelzon (KM) game. First let us introduce the notion of a variant.

Let A1, . . . ,Aℓ be unary predicate symbols. There are L = 22ℓ logically inequivalent Boolean combinations µ of A1, . . . ,Aℓ. Let us pick unary predicate symbols M1, . . . ,ML representing them.

Definition 7.3. (ℓ-min-variant) Let R = (X,≤) be a partial order. An ℓ-min-variant of R is a structure

where R′ = (X,≤,A1, . . . ,Aℓ) is an ℓ-extension of R, and M1, . . . ,ML are the interpretations of the formulas minν≤(x), for Boolean combinations ν of the Ais.

Note that R′′ is a structure with unary predicates only, the relation ≤ is not included, it is "forgotten" 5 (but ≤ is used in order to determine the Mis). So R′′ is not an extension of R: therefore it is referred to as a variant.

Definition 7.4. ((R, ℓ, q)-∃MSOmin game, or KatsunoMendelzon game) Given a class R of posets and parameters ℓ and q, the (R, ℓ, q)-∃MSOmin game is played by Spoiler and Duplicator as follows:

1. Duplicator picks a poset R1 = (X1, ≤1) in R,
2. Spoiler picks ℓ subsets A1, . . . ,Aℓ of X1,
3. Duplicator picks a poset R2 = (X2, ≤2) ̸∈ R and subsets B1, . . . , Bℓ of X2,
4. Form the ℓ-min-variant R′′ 1 of R1 determined by the ℓextension R′1 = (X1,≤1,A1, . . . ,Aℓ), and the ℓ-minvariant R′′ 2 of R2 determined by the ℓ-extension R′2 = (X2, ≤2, B1, . . . , Bℓ),
5. Spoiler andDuplicator play a q-round first-order Ehrenfeucht - Fra¨ıss´e game on R′′ 1 and R′′ 2 .

Theorem 7.5. A class R of posets is ∃MSOmin -definable iff there are ℓ and q such that Spoiler wins the (R, ℓ, q) - ∃MSOmin game.

5 This is the "forgetful property" of the game, mentioned in the introduction.

For non-characterizability we use the following corollary. The formulation takes into account that the theorem holds for general posets, but we are only interested in regular posets.

Corollary 7.6. Let R be a class of regular posets. Assume that for every ℓ and q, Duplicator has a winning strategy in the (R, ℓ, q) - ∃MSOmin game such that the posets R2 are also regular. Then R is not ∃MSOmin -definable.

8 Classes of Posets

A chain (resp., antichain) is a set of pairwise comparable (resp., incomparable) elements. The height (resp., width) of a poset is size of a largest chain (resp., antichain). A poset is total (aka linear) if it has width 1. A poset is connected (resp., disconnected) if its comparability graph is connected (resp., disconnected).

As for technical reasons we deal with regular posets in this paper, we use somewhat modified notions, by disregarding the minimal elements of the poset. The reason is that for our purposes the contribution of the minimal elements is not essential, as they relate to the other elements in a trivial way, but they may interfere with the structure of the remaining elements. For example, minimal elements are always incomparable, thus if minimal elements are included then a poset for a knowledge base of more than one truth assignment cannot be total.

The r-height (resp. r-width) of a regular poset is the height (resp., width) of the poset obtained by removing the minimal elements. A regular poset is r-total ( resp., r-connected, rdisconnected) if the poset obtained by removing the minimal elements is total (resp., connected, disconnected).

We denote by H≤k the class of regular posets with r-height at most k. The classes H≥k,H<k,H>k,H=k are defined similarly. For width we use the notations W≤k,W≥k,W<k,W>k. The class of r-total (resp., rconnected, r-disconnected) regular posets is denoted by T (resp., C, D).

9 Characterizable Classes

The characterizability results of this section are proved by showing that a given class of posets is ∀MSOmin -definable, or that its complement is ∃MSOmin -definable. It may happen that the standard definition of a class is not suitable for such a definition, but it can be replaced by an equivalent definition which is suitable. As a first example of characterizability we give a basic postulate characterizing revision operators obtained from r-total regular posets.

Theorem 9.1. The class of T -revision operators is characterized by the basic postulate

The standard definition of totality is that any two elements are comparable. With the modification to consider only nonminimal elements, this becomes the statement that any two non-minimal elements are comparable. This is not suitable for our purposes, as min-formulas cannot talk directly about comparability. An equivalent formulation in the language of min-formulas is that every nonempty set of non-minimal elements has a unique minimal element, expressed by (7).

When is it possible to find such a rewriting? We give examples of both kinds of answers. The positive results are summarized in the following two theorems.

Theorem 9.2. 1. For every k, the class of H≤k-revision operators is characterizable.

1. For every k, the class of H≥k-revision operators is characterizable.
2. For every k, the class of W≤k-revision operators is characterizable.

We outline the proof of Part 2 by showing that H<k is ∃MSOmin -definable. A regular poset has height less than k iff there are sets A1, . . . ,Ak-1 such that the Ais form a partition of the set of non-minimal elements, and each Ai is an antichain. This definition starts with existential second-order monadic quantifiers, thus the second-order quantifier structure is of the right form. The standard description of a set Ai being an antichain is that there are no comparable pairs in Ai. However, min-definability cannot directly express comparability. An attempt to circumvent this would be to say that a and b are comparable iff the set of minimal elements of the set {a, b} is a singleton. This would require a second-order quantifier to follow a first-order one, which is also not possible. The solution is given by the observation that Ai is an antichain iff it is equal to the set of its minimal elements, i.e., Ai = minAi.

One case where a replacement of the standard definition by a ∀MSOmin -sentence cannot be found is having width at least k: the classes W≥k are turn out to be not ∀MSOmin -definable, even though they are first-order definable. Connectedness and disconnectedness are also not ∀MSOmin - definable. These results are presented in the next section.

On the other hand, connected posets of bounded height turn out to be ∀MSOmin -definable. This is an example of an ∀MSOmin -definable class which is not first-order.

Theorem 9.3. For every k, the class of C ∩ H≤k-revision operators is characterizable.

10 Non-characterizable Classes

The negative results are based on Theorem 6.3 and Corollary 7.6, by constructing winning strategies for the Duplicator. We first consider the class of W≥2-revision operators, i.e., the class of revision operators obtained from regular posets which are not r-total. As non r-total regular posets form a simple and natural first-order definable class, the noncharacterizability of the corresponding class of revision operators might be considered somewhat surprising.

Theorem 10.1. The class of W≥2-revision operators is not characterizable.

We outline the proof. Given ℓ and q, we have to describe a winning strategy of the Duplicator in the (R, ℓ, q) - ∃MSOmin game for the class of regular posets not inW≥2, i.e., for the class T of r-total regular posets.

The poset R1 = (X1, ≤1) picked in step 1. will be a chain on N elements, for some power of 2 to be determined later. Assume that Spoiler picks ℓ subsets A1, . . . , Aℓ. For any element a ∈ X1 we associate a bit-vector with components indicating which subsets Ai a belongs to, and for every Boolean combination ν of the Ais, whether a is minimal among elements belonging to ν. These bit-vectors form a coloring of X1 with L = 2ℓ+22ℓ colors. As there is at most one element which is minimal in a Boolean combination, there are at least N - 22ℓ elements which are never minimal. If N - 22ℓ > L then there are at least two never-minimal elements of the same color. Duplicator then forms R2 by picking such an element a, splitting it into two incomparable elements a and b, and deleting another element c from the same color class. The sets Bi are the same as the Ais, with the exception of b replacing c. The ℓ-min-variants R∗ 1 and R∗ 2 are isomorphic and thus Duplicator can win the first-order game in Step 5.

The non-characterizability of W≥k-revision operators follows similarly. We have seen in Theorem 9.3 that the class of revision operators generated by connected regular posets of bounded height is characterizable. On the other hand, the full class of revision operators generated by connected regular posets turns out to be non-characterizable. This shows another limitation of ∀MSOmin -definability, as connected posets are ∀MSO-definable. Finally, the class of revision operators generated by disconnected regular posets is not even ∀MSO-definable.

Theorem 10.2. The classes of C-revision operators and Drevision operators are not characterizable.

11 Summary

The results on classes of revision operators are summarized in the figure below. Characterizable classes (denoted by ∀MSOmin in the figure) turn out be a proper subset of universal monadic second-order definable classes, incomparable with first-order definable classes. The discussion of some details of the diagram (such as C ∩ H≤k not being first-order definable) is omitted due to lack of space.

Characterizable Non-characterizable

1. Height ≤ k, height ≥ k
2. Width ≥ k
3. Width ≤ k
4. Connected
5. Connected and height ≤ k 6. Disconnected

In future work we plan to extend the results of this paper to partial preorders and also to contraction operators. Further questions include characterizability for other types of epistemic information, and for iterated revision.