Reset reproduction of CMU Computer Science report CMU-CS-83-125 (only pagination differs). Versions of 1982 and 1983 differ only slightly. Revised and abbreviated version published in Fundamenta Informaticae, V. 20, Nos. 1–3 (1994), pp. 35–73. Reprinted July 1994. Reprinting \begin{matrix}c \\ ◯ \end{matrix} Copyright 1982, 1983, 1994 by Jon Doyle. Current address: MIT Laboratory for Computer Science, Cambridge, Massachusetts.

Some Theories of Reasoned Assumptions

An essay in rational psychology

Jon Doyle

Department of Computer Science Carnegie-Mellon University Pittsburgh, Pennsylvania 15213

December 12, 1982 Revised May 12, 1983 \begin{matrix}c \\ ◯ \end{matrix} Copyright 1982, 1983 by Jon Doyle

This research was supported by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 3597, monitored by the Air Force Avionics Laboratory under Contract F33615-81-K-1539. The views and conclusions contained in this document are those of the author, and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the Government of the United States of America.

Abstract

We examine several formulations of the common practice of jumping to conclusions when actions demand decisions but solid knowledge fails. This practice permeates artificial intelligence, where systems assume many conclusions automatically as defaults simply because the questions they decide are known to occur frequently, and where other assumptions are formulated and adopted only when ignorance stalls action. After developing the motivations and general nature of these inferences, we introduce a formal basis for describing them. This formulation allows separate introduction of the several ideas involved, and so facilitates characterization of some important combinations and some previous proposals. Initial results are proved about these theories, including the aptness of the formal notions with respect to the intuitive motivations. Benefits of this formulation include an indication of the ways notions from logic and metamathematics can enter into psychologies without subscribing to all of logic or metamathematics, an indication of the importance of conservation of mental states in the description of psychologies, and formal and intuitive relations between the approach of reasoned assumptions and its popular alternatives, deductivism and Bayesianism.

Acknowledgments

My debts, obvious and hidden, are many. As always, Joseph Schatz helped more than I can say. Jon Barwise, Johannes Brahms, Jaime Carbonell, Johan de Kleer, Merrick Furst, Clark Glymour, Jussi Ketonen, Robert Laddaga, David McAllester, John McCarthy, Drew Mc-Dermott, Marvin Minsky, Robert Moore, Allen Newell, Joann Ordille, Raymond Reiter, Dana Scott, Robert Stalnaker, Gerald Sussman, Peter Szolovits, and Richmond Thomason all helped in different ways. Jan Zubkoff graciously did the initial typing. The Computer Science department of Carnegie-Mellon University greatly aided my writing.

Note to the Reader

To keep this paper to a reasonable length, I assume some mathematical sophistication and acquaintance. Passage of time will, I hope, permit a more relaxed and thorough development. The symbols used are collected and glossed at the end of the paper. The headings Definition, Theorem, Corollary, Lemma, and Conjecture serve their usual purposes, and are numbered in a single sequence. Some proofs have been omitted. The heading Question often indicates an issue calling for proper formulation rather than a simple answer.

Analysis of Contents

Section Page

Abstract i Acknowledgments i Note to the Reader i Analysis of Contents ii Meditation vi Dedication vii

I. Introduction

1.  The problem of understanding artificial intelligence mathematically.  1

2.

Task of the present work. Summarizing, extending, and reformulating theories of reasoned assumptions.

1

II. A Problem, an Approach, and a Solution

3.  The problem of ignorant action. Sources of ignorance.  2
4.  The approach of jumping to conclusions. The will to believe.  2

5.

Guiding decisions to believe. Ratiocinative rules of anti-agnosticism, sequencing, and defeasibility.

3

6.

The question of interpretation of ratiocinative rules. Maximizing ratiocinative utility, conflicting preferences, and defeasible reasons.

3

7.

Origins of ratiocinative rules of thumb. Probability, typicality, safety, and pragmatic utility.

5

8.

The problem of revising mistaken assumptions. The role of conservatism of mental states in psychology.

5

III. Formal Theories of Reasoned Assumptions

9.

Aim of the formalization. Agents and their admissible states characterized by constitutive assumptions.

7

10.  The underlying decomposition of mental states.  7

11.

Interpreting state components as state-specifications. Reasons and componentadmissible states.

7

12.  General restrictions and the space of admissible states.  8

Extensions, component-admissible extensions, and admissible extensions of states. Autological agents.

8

14.  “Psycho-logic:” psychological entailment and arguability.  9
15.  Strict arguability and minimal psychological entailment.  9

16.

Other psychological inferential relationships and the special case of logically structured states.

10

17.  Sum and product constructions of agents.  11

Elemental Theories

18.  The simple reasons theory. Definition, examples, results, and ignorance.  12
19.  Defeasible reasons.  20
20.  Expressive limitations of simple reasons. Denials and contradictions.  21

Logical Theories

21.

The prevalence of logically structured representational systems in artificial intelligence.

24

22.  Agents with deductively closed states. Abstract deducibility relations.  24
23.  Invertible reasons: a recurrent but fatally flawed interpretation of reasons.  29
24.  Expressing reasons in logical languages. The linguistic reasons theory.  30

Attitudinal Theories

25.  Logical structure and psychological attitudes distinguished.  33
26.  Embedding mental attitudes in the simple reasons theory.  33

27.

Purely attitudinal states, ratiocinative intentions, and ratiocinative desires. Aptness of the semantics.

33

28.

Phrasing propositional attitudes in a linguistic reasons theory. Deductively closed beliefs, self-omniscience, and the incoherence of their combination.

35

Evolutionary Theories

29.  Reasoned and unreasoned state changes. Conservation of state.  37
30.  Decomposing state changes into kernel specifications and admissible transitions.  37
31.  Strict, conservative, and strictly conservative agents.  37

32.  Some examples of evolution in simple reasons agents.  39
33.  Summarizing the foregoing. Some results and questions.  40
34.  Trajectory space and familiar psychological questions.  42
35.  Unreasoned state changes and backtracking.  42
36.  Catastrophes and backtracking.  43

Probabilistic Theories

37.

Probabilistic constructions from reasoned assumptions. Methodological and theoretical benefits.

45

38.  Probabilities on elements from probabilities on states and their interpretation.  45
39.  Probability measures. Laplace’s assumption and specificity.  45

40.

State component “probabilities” via extents. Conditional and a posteriori extents distinguished.

46

41.  Examples. Carnap’s theory of probability.  47
42.  Generalization to element-dependent measures.  49
43.  Agent evolution recast as evolution of density functions.  49

44.

The case of logically structured states. Reconstruction of Bayesianism and fuzzy logic. Problems about completeness. Interpreting extents as strengths. Methodological implications of reasoned assumptions.

51

IV. Related Theories of Reasoned Assumptions

45.

Using the theoretical framework for description and classification as well as for development.

54

46.

RMS, the reason maintenance system. Finitely grounded simple reasons, contradictions, and non-chronological backtracking.

54

47.  Reiter’s logic of default reasoning, a relative of the linguistic reasons theory.  55
48.  McAllester’s logic of propositional deduction.  56

49.

The non-monotonic logic of McDermott and Doyle. Extensions by McDermott and Gabbay and their problems. Moore’s solution. Stallman’s insights and conception.

57

50.  Minsky’s K-line theory of memory.  60
51.  McCarthy’s circumscription.  61

V. Conclusion

52.  Summary of the preceding. Topics not discussed.  66
53.  Interpretation of this work. The enterprise of rational psychology.  66

References 67 Table of symbols 72

Meditation

Ging heut morgens übers Feld, Tau noch auf den Gräsern hing; Sprach zu mir der lustge Fink: ,,Ei, du! Gelt? Guten Morgen! Ei gelt? Du! Wird’s nicht eine schöne Welt? schöne Welt!? Zink! Zink! schön und flink! Wie mir doch die Welt gefällt¡‘

Auch die Glockenblum am Feld Hat mir lustig, guter Ding Mit dem Glöckchen kling, kling, Ihren Morgengruss geschellt: ,,Wird’s nicht eine schöne Welt? schöne Welt!? Kling! Kling! Schönes Ding! Wie mir doch die Welt gefällt! Hei—a¡‘

Und da fing im Sonnenschein Gleich die Welt zu funkeln an; Alles, alles, Ton und Farbe gewann in Sonnenschein! Blum und Vogel, gross und klein! Guten Tag, guten Tag! Ist’s nicht eine schöne Welt? Ei du! Gelt? Schöne Welt!?

Nun fängt auch mein Glück wohl an?! Nein! Nein! Das ich mein, mir nimmer blühen kann!

G. Mahler, Lieder eines fahrenden Gesellen

L’adoration de la terre; Le sacrifice

I. Stravinsky, Le Sacre du Printemps

Ich will nur dir zu Ehren leben, Mein Heiland, gib mir Kraft und Mut, Dass es mein Herz recht eifrig tut. Stärke mich, deine Gnade würdiglich und mit Danken zu erheben.

J. S. Bach, Weihnachts-Oratorium for Norma Charlotte Schleif Miller

and in memory of

Henry Aloysius Miller,

Meta Augusta Wilhelmina Frederica Enters Doyle,

and Lawrence Henry Doyle

I. Introduction

§1. Recently, increasing attention has been directed toward problems of providing mathematical formulations and semantics for some of the inferential systems developed in informal, practical terms within artificial intelligence. The mathematical approach has seldom been popular, for except in rare cases like the treatise of Minsky and Papert on perceptrons,^{1} mathematical formulations have lacked force, have seemed mere importation of formalism without true understanding of the important problems to be addressed. Artificial intelligence has long been a field for formulation, where ubiquitous problems have defied stable statements.^{2} In this setting it is natural that outsiders experience difficulties in looking for important problems, since the set changes with every observation! Fortunately, circumstances change, and the field has begun to develop its own mathematical formulations of some of these recognized but poorly articulated problems. These formulations may not yet be as comprehensive or compelling as those underlying the exact sciences, but they easily support optimism for more satisfying replacements in the near future.

§2. Our subject here is a reexamination of several proposals concerning the mathematical formulation of certain non-deductive inference patterns common in artificial intelligence. Artificial intelligence systems draw many logically peculiar conclusions, and the question has been raised of whether there are coherent patterns among and justifications for these conclusions. Traditionally the nature of these non-deductive inferences has been hidden behind the slogan “heuristic,” but realization of the widespread use of particular patterns has prompted their formulation and explication as important problems for the field. With the works of McDermott, Reiter, McCarthy and others advances have been made, but deficiencies in understanding persist. Motivationally, these efforts articulate some of the intuitions underlying the field’s practice, but apparently not well enough to communicate these intuitions and their significance to some inside and many outside the field. Formally, these proposals exhibit some similiarities so that they all seem to approximate a single answer to a single problem, but they differ widely in detail, and no exact characterization of their differences or individual powers has been given. My purpose here is to pursue of the common project of these proposals by summarizing and extending the motivations underlying the subject inference patterns. I present a common mathematical basis in which I analyze, compare, and extend the previous proposals. Hopefully this effort will benefit several audiences: artificial intelligence theoreticians and practitioners interested in better understanding their systems of study, mathematicians and philosophers interested in the formalization and motivations of these novel inferential systems, and theoretical computer scientists interested in computational questions arising in artificial intelligence.

Briefly, the problem is to formulate the common practice of jumping to conclusions when actions demand decisions but solid knowledge fails. This practice permeates artificial intelligence systems, where some assumptions are formulated and adopted only when ignorance stalls action, and where other conclusions are automatically assumed as defaults simply because the questions they decide are known to occur frequently.

1[Minsky and Papert 1969]

2Compare [Minsky 1962].

II. A Problem, an Approach, and a Solution

§3. Life calls for action, and to act we must decide what to do in ignorance of our true circumstances, capabilities, and their consequences. We may decide using information about the consequences of our actions in our circumstances, but are our imagined circumstances our actual ones? Will the actions we perform be the ones we attempt? Will unforeseen interferences prevent the expected consequences?

The skeptical challenge to the possibility of accurate knowledge of the world has never taken lives; neither does it halt work in artificial intelligence. One does the best one can. To do so, however, one must be able to admit and correct one’s errors, and this consideration influences the design of artificial agents as well as the conduct of life. But in artificial intelligence, incompleteness of information looms larger than inaccuracy. Certainly to admit error requires one to judge oneself ignorant in the past, but in principle, as in politics, it still allows one to maintain an opinion on every subject and to assert correctness of all one’s current opinions. Nevertheless, there are several severe obstacles to designing agents whose information about the world is complete, even if inaccurate. The first obstacle is that apparently accurate complete axiomatizations of the world may not exist. As in arithmetic, we may be able to state our basic premises, prove their incompleteness, and convince ourselves that any completion we attempt will involve inconsistencies. Since we expect error anyway, this need not be a strong deterrent, but it does suggest that completion for its own sake is unwarranted. The second obstacle, one far more serious, is the feasibility of using complete information even if we attain it. Present-day computation is recursive computation, and an undecidable complete axiomatization is no better than an incomplete axiomatization. Worse still, even decidable theories may be intractable, for short theorems may have very long shortest proofs, and answering single questions may involve exploring very many potential proofs. Since time will not stand still while the agent attempts to compute the answers it needs, theoretical completeness of the agent’s information can be a practical fraud.^{3} The third obstacle is simple unavailability of complete axiomatizations of the world. Even looking to the sciences, one finds searches for new laws to fill old gaps, and artificial intelligence has spawned an entire discipline devoted simply to elicting all the facts about the world employed by experts but unseen in the literature. It seems methodologically unwise to postpone work on artificial intelligence until science completes its inquiry, unless one does not want artificial agents at all.

§4. If we accept the challenge of acting without complete information, we must adopt some approach which allows both cognizance of incompletenesses and means for overcoming them. To act without awareness of one’s clear limitations is blind stupidity, yet ignorance need not paralyze either. One approach out of several possible approaches has dominated work in artificial intelligence, and this is the practice of jumping to conclusions. Many of the beliefs assumed by default or for heuristic value in mechanized agents are cases of what William James called the “will to believe.”^{4} James was, like Pascal before him,^{5} concerned primarily with questions of momentous, eternal import rather than the questions of mundane, temporal expediency common in routine thought and action, but the idea is the same. One judges, either at the moment or in advance, that it is better to adopt a stance on some issue and risk error than to take no stance at all. The position taken need not be precedential, for along with recognition of the possibility of error, we may also recognize that other or later circumstances raising similar questions may be decided differently. In Tukey’s phrase, we often decide to act for the time being as if something were the case, rather than simply deciding something is the case.^{6} But precedential or not, the approach of adopting stances carries with it a commitment to correcting mistakes when they come to light. As James puts it, we might resolve to Believe Truth! and to Shun Error!, but the preceding suggests the latter resolve is best realized as conscientious correction rather than intellectual cowardice.

3The importance of computational feasibility in artificial intelligence is easily underestimated. See [Minsky 1963], [Minsky and Papert 1969], [Minsky 1975, appendix], [Rabin 1974] and [Garey and Johnson 1979] for illuminating discussions of this issue.

4[James 1897]

5[Pascal 1662]

6[Tukey 1960]

The approach of jumping to conclusions finds many followers in artificial intelligence, but in other disciplines studying intelligent action other approaches attract the most attention. Of these, the most influential is subjective Bayesian decision theory.^{7} There is much to be said about this alternative, but now is not our time to do so. For the moment, our task is laying out the motivations, nature, and formalizations of jumping to conclusions as it is practiced in artificial intelligence. Later we adduce some connections of this approach with subjective Bayesian decision theory which may illuminate their respective computational conveniences and difficulties.

§5. Once we decide to face the problem of incomplete information by deliberately adopting stances when necessary, we must also face subsidiary problems: how can we tell when we should jump to conclusions, and which ones we should settle on? Once again, the practice of artificial intelligence supplies an approach to these problems, although possibly not the only or best one. This approach uses ratiocinative rules of thumb to guide the adoption of assumptions. These rules state which sorts of circumstances call for making assumptions, which assumption to try first, and when and how to revise one’s opinion to other assumptions. That is, ratiocinative rules of thumb serve three functions: to enforce anti-agnosticism when appropriate, to indicate a sequence in which alternatives should be tried, and to recognize circumstances which might call into question one or more of the alternatives. These rules are often embodied as general or schematic “defaults” used in drawing conclusions, rules tolerant of exceptions in that specific conclusions are defeasible on a case-by-case basis without affecting the operation of the general rule itself.^{8} For example, one might decide to believe that ordinarily, every bird can fly. This decision might be carried out by a ratiocinative rule of thumb which infers of each individual bird considered that it can fly. This rule would continue to make such assumptions about newly considered birds even after particular flightless birds are recognized and their corresponding assumptions abandoned.

§6. Ratiocinative rules of thumb form an approach, but in the absence of precise criteria for their application and interpretation are not themselves a solution to the problem of adopting assumptions. These rules guide inferences, but are not inference rules in the usual logical sense, since questions of soundness do not enter into the discussion. The point of the rules is, after all, to be unsound, to draw conclusions not strictly entailed by their grounds. We propose a solution based on interpreting these rules of thumb as expressions of ratiocinative desires, regarding actions of jumping to conclusions as actions satisfying the ratiocinative desires. In these terms we can cast the anti-agnostic, sequencing, and defeasibility functions of ratiocinative rules of thumb as components of the following “syllogism.”

7See, for example, [Savage 1972], [Levi 1967], and [Luce and Raiffa 1957].

8Widespread use of the term “default” follows Minsky’s influential discussion in [Minsky 1975]. [Reiter 1978] identifies a variety of appearances of this notion in the practice of artificial intelligence.

I am in circumstances A.

When I am in circumstances A, I prefer being decided about Q to being undecided about Q.

When I am in circumstances A and am undecided about Q, I prefer adopting stand C to adopting stand B.

Therefore, I should adopt stand C.

We combine and abbreviate the two implicative components of such syllogisms in rules written as

A \\ B ∥− C,

rules read as “A without B gives C” and informally interpreted as “if A obtains, and B does not, then adopt C.” These rules are called reasons for their conclusions, and the conclusions drawn are called reasoned assumptions. This terminology diverges somewhat from standard usage, in which one calls the premises of the inference the reasons for the conclusion. We always refer to the premises as premises, hypotheses, antecedents, presuppositions, etc., and reserve the term reason for the inference step that connects premises with conclusions. We do not insist on particular forms for what may enter into these rules; as well as logical statements of conditions, other sorts of mental components can be accommodated, as detailed in the following formal treatment.

We base our interpretations of these encapsulated syllogisms on maximization of the utility of mental states. Utility maximization has, with some justification, gained a bad name as a descriptive theory of human behavior, but our purpose here is supplying normative theories where none exist, rather than attempting to accommodate logic to the behavior of some species of agent. Indeed, as we see later, many of the maximizations of interest are all small, independent, local decisions, easily implemented and suffering from few of the difficulties arising in the more comprehensive maximizations of subjective Bayesian decision theory. As is familiar from classical decision theory, there may be several distinct interpretations of maximal utility. Moreover, ratiocinative rules of thumb can conflict on cases. We hold all desires to be incomparable without“higher-level” desires which recommend satisfying one ratiocinative desire before another. This means we seek ways to live with conflicts rather than insist on their resolution, and that maximixing utility involves maximizing the set of ratiocinative desires satisfied by mental states. For example, suppose we choose to employ the two general rules

∀x [Republican(x) \\ Pacifist(x) ∥− ¬Pacifist(x)]

and ∀x [Quaker(x) \\ ¬Pacifist(x) ∥− Pacifist(x)] .

The first of these says that Republicans should be assumed to be non-pacifists unless known to be pacifists. The second says that Quakers should be assumed to be pacifists unless known to be otherwise. When we learn that Richard Nixon is both Republican and Quaker, we can instantiate these general rules to the specific cases

Republican(Nixon) \\ Pacifist(Nixon) ∥− ¬Pacifist(Nixon)

and Quaker(Nixon) \\ ¬Pacifist(Nixon) ∥− Pacifist(Nixon).

We cannot honor both preferences at once, so if we look to satisfy as many preferences as possible, we find two alternative coherent sets of assumptions: believing Nixon a Republican Quaker pacifist, and believing him a Republican Quaker non-pacifist. Thus in accord with the interpretation of reasons as desires, we adopt a stand by picking one of these coherent sets as our set of assumptions or beliefs.

Some might find it more reasonable to suspend judgement in cases of conflicting preferences, but under our interpretation that is a poor solution to the difficulty. In adopting these reasons, we have stated our preferences, and with no further information it is needlessly irrational to forgo all satisfactions simply because a trade-off is involved. If the decision were between consuming equally attractive donuts and bagels when there is money to purchase only one, few would counsel starvation. Nevertheless, behind the apparent questionableness of the above decisions lies an important point. Just as we may wish to state rules about when not to be agostic, we may also wish to state rules about when to be agnostic, and these may refer to otherwise conflicting preferences like those in the example. Toward this end we introduce the notion of defeasible reasons. Defeasible reasons allow inferences that can be defeated as a whole, rather than by simply challenging one of the particular presuppositions of the inference. One can encode defeasible reasons in reasons of the above form by introducing explicitly self-referential presuppositions (e.g. R = “A \\ B or R defeated ∥− C′′), but it is more elegant to simply interpret all reasons as containing a uniform presupposition of lack of challenges. With this modification to the interpretation, we can continue to base the interpretation on utility maximization while permitting rules of agnosticism.

§7. This solution to the problem of adopting assumptions raises but does not address several subsidary problems. The first of these concerns the origins and justifications of those ratiocinative rules of thumb with which we choose to endow an agent or which an agent adopts of its own accord. There are several motivations for certain sorts of rules of thumb that immediately suggest themselves, and there may be more as well. The first motivation is the classical notion of statistical likelihood, where we might choose a rule of thumb because it calls for adopting the likeliest alternative. Another motivation is typicality, in which reasons specify the typical conclusion. Typicality might be the same as statistical likelihood, but there are ways of viewing it as a different notion. Another consideration in adopting a rule of thumb is the safety of error and ease of correction, that is, whether disastrous consequences follow from errors, and if not, whether the undesired consequences can be simply remedied. Finally, the weakest motivation is simple pragmatic utility, which often goes by the name of heuristic in artificial intelligence. In this case, one might adopt a ratiocinative rule of thumb simply because one is more successful by doing so.

We propose no procedure for adopting ratiocinative rules of thumb, except for those which are themselves reasoned assumptions. Instead, we separate the issues of formulating, motivating, and adopting ratiocinative rules of thumb from the issue of interpreting them once adopted. The questions of formulation and motivation of these rules of thumb arise in other terms in the study of induction, learning, and philosophy of science, and we defer discussion to that literature.^{9}

§8. A second subsidiary problem raised by adopting assumptions is that of how to revise mistaken assumptions, of how to honor the commitment to correcting errors as they are discovered. Freshly perceived information can contradict previous beliefs, deductive inferences can bring hidden inconsistencies to light, and one sometimes decides to abandon or avoid certain attitudes because they prove embarrassing or endanger mental stability. While some humans seem happy to hide their conflicting attitudes from themselves, some consciously endure their conflicts, and some die, the usual response to this problem is to give something up, either the new information or previous attitudes, in everyday life as well as in philosophy and artificial intelligence. But prudence counsels care in abandoning one’s attitudes. Their acquisition takes time and effort, and they should not be abandoned needlessly. This conservative stance has been taken repeatedly in philosophy and in artificial intelligence. Quine christens it the “maxim of minimum mutilation,” that is, when changes are necessary, one makes as small a change as possible.^{10} Less articulately, artificial intelligence practice exhibits this principle in many forms, with systems of differing levels of sophistication employing varying degrees of minimality and effectiveness in revising their attitudes. We pursue this idea as the notion of conservation of mental state, where conservation is equivalent in all but connotation to minimal mutilation. (I prefer the term conservatism to minimal mutilation, for I would rather be called a conservative or non-conservative than a mutilator of any degree.) Thus we view acceptable revisions of mental states to be the changes that in one way or other remedy the difficulty while preserving as much of the previous state as possible. We develop this topic formally in its own right elsewhere, as it appears many techniques from the practice of artificial intelligence can be conveniently described in these terms, with many concrete measures of “amount of change” characterizing the various practical systems. One class of systems, the so-called reason maintenance systems, minimizes the set of changed reasoned assumptions (see §46), but investigation of more refined measures is just beginning.

9See [Minsky 1963], [Goodman 1973], [Quine and Ullian 1978], [Dacey 1978], and [Levi 1980].

10[Quine 1970]

III. Formal Theories of Reasoned Assumptions

§9. This chapter formalizes the intuitive notions, approaches, and solutions of the preceding. The principal problem in specifying interpretations of reasons is how they may be aggregated in spite of conflicts, and we formalize this as the problem of defining the admissible states of the agent holding the reasons. These admissible states constitute the “coherent” sets of interdependent reasoned assumptions sanctioned by the agent’s reasons. Our method in formalization is to construct the set of admissible states from various assumptions about the constitution of the agent. Different theories of reasoned assumptions arise through the different constitutive assumptions we make (not to be confused with the reasoned assumptions made by the agent) about the agent’s composition, the interpretation of individual reasons, and the aggregation of reasons and assumptions. Our first theories concern only the static side of the agent, but later we consider further constitutive assumptions about conservatism of the agent’s state changes, and so arrive at evolutionary theories of reasoned assumptions.

§10. We first suppose that there is a domain D of formal or structural elements such that each possible mental state of the agent can be decomposed into elements of D. Since we are concerned only with the structure of states vis-à-vis reasoned assumptions, we make no suppositions about the specific composition of D. Examples of domains from artificial intelligence include the set of all sentences in some logical language, the set of all LISP data-structures (S-expressions), and the set of all “mental agents” in Minsky and Papert’s society of mind.^{11} As the latter example shows, we do not require that D has grammatical structure or is completely representational, and as the former examples show, “languages of thought” are acceptable as well. The set of admissible states S̸ is thus a subset of the set of all sets of mental components: in other words, S̸ ⊆ P D.

§11. Though we need make no suppositions about the nature of the arbitrary mental component, our second constitutive assumption is that some mental components can be interpreted as reasons, as specifications for the composition of the states in which the components occur. Formally, we assume an interpretation function I : D → P P D which indicates the sets of components each component sanctions, so that a set S ⊆ D satisfies its component specifications just in case S ∈ I(d) for each d ∈ S. We define the class of component-admissible sets Q ⊆ P D to be those sets satisfying all their components, that is,

Q = {S ⊆ D | S ∈ ⋂_{d∈S} I(d)}.

Formalizing the notion of reasons as state specifications in this way involves several simplifications. First, rather than distinguish only some state components as reasons and leave the rest uninterpreted, we interpret every state component and give each non-reason d ∈ D the trivial interpretation I(d) = P D that sanctions all potential states. Second, we interpret reasons as predicates of all sets of components rather than only as predicates of the admissible states, that is, to be subsets of P D rather than subsets of S̸. This simplification is innocuous since we can always take the interpretation of every element to exclude all inadmissible sets. Third, we take the interpretation of components to be independent of the state containing the component. While the theories examined in this paper can all be captured within this limitation, we elsewhere consider ideas from artificial intelligence better suited by state-dependent interpretations which replace I : D → P P D with I′ : D × P D → P P D and Q with Q′ = {S ⊆ D | S ⋂_{d∈S} I′(d, S)}. Finally, our fourth simplification is that each state component embodies at most one reason. The extension to multiple reasons is trivial, since conjoined specifications are interpreted by intersecting their interpretations.

11[Minsky 1980]

§12. Our third constitutive assumption is that all admissible states are component-admissible but that certain combinations of state components can never occur in admissible states even if they occur in some component-admissible states, or formally, that we can stipulate the set of admissible states S̸ to be some subset of Q, i.e. S̸ ⊆ Q. For example, if components are sentences of a logical language, we might require every admissible state to be deductively closed or to be consistent, even if none of its component sentences express non-trivial reasons. We introduce such general restrictions on the set of admissible states because interpreted components alone cannot express all interesting restrictions. Actually, nonemptiness of admissible states is the only restriction inexpressible by components alone, for though ∅ is always component-admissible (it having no elements to rule otherwise), we can always replace I by I′, defined so that for all d ∈ D, I′(d) = S̸, in which case Q = S̸ ∪ {∅}.

In many cases of interest, as in the examples of deductive closure, consistency, and nonemptiness above, it is possible to decompose the specification of S̸ into the component restrictions and a general restriction on all sets. That is, one way of specifying S̸ ⊆ Q is to stipulate a general restriction on states R ⊆ P D and define

S̸ = Q ∩ R = {S ∈ R | S ∈ ⋂_{d∈S} I(d)}.

Since S̸ ⊆ Q, we can always take R = S̸ when there is no independently interesting definition of R. If S̸ = R, then the component interpretations add nothing to the general restriction. In particular, this circumstance holds whenever all component interpretations are trivial. On the other hand, if R = P D, then there are no general restrictions, and any restrictions on admissible states must be explicit in the states themselves. This circumstance recalls the current efforts in artificial intelligence towards constructing completely “self-descriptive” machines.^{12} In the theories to follow, we will define S̸ either directly or in terms of R as convenient.

§13. While the notion of admissible state captures an idea of states which specify their own structure, it says nothing about any form of inference. We introduce the idea of admissible extension as a formalization of the sets of conclusions or reasoned assumptions permitted within the structure of the agent’s states. Just as the specification of admissible states involved both “local” (I) and “global” (S̸ or R) restrictions, so also does the definition of admissible extension.

If S ⊆ D we define Exts(S), the set of extensions of or states extending S, to be the admissible states including S as a subset, or formally,

Exts(S) = {E ∈ S̸ | S ⊆ E}.

If E ∈ Exts(S), we also write S < E. Extensions are defined in the same way for all theories of reasoned assumptions.

Just as the “psycho-logic” of mental states interprets (via I) each state component as a restriction on the states in which it can occur, we also interpret components as restrictions on the ways they can be derived or occur in admissible extensions. That is, we assume a function J : D × P D → P P D that interprets each state component to find the extensions it sanctions for various sets of components. We define QExts(S), the component-admissible extensions of a set S ⊆ D, by

QExts(S) = {E ∈ Exts(S) | E ∈ ⋂_{d∈E} J (d, S)}.

That is, E is a component-admissible extension of S just in case each element of E approves (via J) of the way it occurs in E relative to S. The admissible extensions AExts(S) are stipulated as a subset of the component-admissible extensions, or formally, AExts(S) ⊆ QExts(S) ⊆ Exts(S). If E ∈ AExts(S), we also write S <· E.

12[Minsky 1965], [Doyle 1980], [Weyhrauch 1980], [Frisch and Allen 1982], [Smith 1982]

Putting all these definitions together, we say that each choice of (D, I, S̸, J , <·) (or alternatively, each choice of (D, I, R, J , <·)) describes the states and inferential structure of an autological agent. This appelation is meant to recall the ways the agent’s constituents talk about their roles in the “logic” of the agent’s states.

§14. Merely having structures for admissible states and admissible extensions does not in itself support use of the term “logic,” but we introduce a notion of psychological entailment to excuse this abuse of standard terminology. Let (D, I, S̸, J , <·) describe an autological agent. If A, B, S ⊆ D, we say that A psychologically entails B in S (within the agent’s psychology), written A ∥=_{S} B, iff B ⊆ E whenever A ⊆ E and E ∈ AExts(S).

(14.1) Theorem. A ∥=_{S} B for every A, B ⊆ D iff AExts(S) = ∅ or AExts(S) = {D}.

Proof. Clearly, if AExts(S) is ∅ or {D}, then A ∥=_{S} B for every A, B ⊆ D, so suppose A ∥=_{S} B for every A, B ⊆ D and AExts(S) ≠ ∅. Let E ∈ AExts(S). Then by hypothesis, ∅ ∥=_{S} D, and since ∅ ⊆ E, we must have D ⊆ E, hence D = E.

A more specific notion plays a prominent role in the subsequent development where we say that d ∈ D is inevitable in S to mean that d ∈ E whenever E ∈ AExts(S), that ∅ ∥=_{S} {d}.

We introduced the notion of admissible extension to capture the notion of inference within the agent’s psychology, but unfortunately, the correspondence between inference and entailment so important in mathematical logic does not obtain in the general psychology. We say that B is arguable from A in S, written A |∼_{S} B, iff there is some E ∈ AExts(S ∪ A) such that B ⊆ E.

(14.2) Theorem. If A |∼_{S} B for every A, B ⊆ D, then S <· D.

Proof. Suppose A |∼_{S} B for every A, B ⊆ D. Then in particular, ∅ |∼_{S} D, so there is some E ∈ AExts(S) such that D ⊆ E, hence D = E and S <· D.

We say that d ∈ D is arguable in S iff there is some E ∈ AExts(S) such that d ∈ E, in other words, ∅ |∼_{S} {d}.

(14.3) Corollary. If A ⊆ S, then A ∥=_{S} B iff ∅ ∥=_{S} B, and A |∼_{S} B iff ∅ |∼_{S} B.

The divergence between arguability and inevitability is seen more clearly in the particular subsequent theories. Indeed, the point of theories of reasoned assumptions is to set out the coherent sets of assumptions sanctioned by some set of reasons, and when there are several possible coherent sets of assumptions one has A |∼_{S} B but not A ∥=_{S} B, a reflection of the intended “unsoundness” of this sort of psychological inference.

§15. Even among the “unsound” conclusions sanctioned as reasoned assumptions, some conclusions are more sound than others. If E, E′ ∈ AExts(S) are such that E is a proper subset of E′, then those conclusions in E′ but not in E are, in a sense, less sound than need be. Expedience might force jumping to conclusions, but it need not force profligacy. To avoid unnecessary unsoundness, we introduce the notion of strict arguability, arguability in minimal admissible extensions.

(15.1) Definition. If X is a set of sets, the minimization of X, μX, is given by μX = {x ∈ X | ∀y ∈ X y ⊆ x ⊃ x ⊆ y}. If f is a set function f : X → P Y, then the minimization of f is a function μf : X → P Y such that for each x ∈ X

(μf)(x) = μ(f(x)) = {y ∈ f(x) | ∀y′ ∈ f(x) y′ ⊆ y ⊃ y ⊆ y′}.

Take care to note that μ finds the minimal elements of sets, not the minimums of sets, so that μf(x) = ∅ if f(x) = ∅. Note also that μX can be empty even when X is not if X contains an infinite descending chain of sets. This will not happen in most of the theories we consider. One set function is AExts : P D → P S̸, and its minimization under set inclusion, written μAExts, is defined for all S ⊆ D by

μAExts(S) = {E ∈ AExts(S) | ∀E′ ∈ AExts(S) E′ ⊆ E ⊃ E ⊆ E′}.

While this definition of minimization is specific to set inclusion, we elsewhere treat these ideas in a more general setting by replacing set inclusion with more specific notions of relative information content. In that treatment, μ means minimization with respect to a quasi-order ⊑ on P D refined by ⊆, that is, an order ⊑ such that x ⊑ y implies x ⊆ y but not necessarily vice versa.

With the definition of minimization, we say that B is strictly arguable from A in S, written Aμ |∼_{S} B, iff there is some E ∈ μAExts(S ∪A) such that B ⊆ E. In this way, strict arguability corresponds to arguability with as few assumptions as possible. Note that if μAExts = AExts the two versions of arguability coincide.

Corresponding to the notion of strict arguability in an agent, we also have the notion of minimal psychological entailment, psychological entailment in minimal admissible extensions. Specifically, we say A minimally psychologically entails B in S, written Aμ ∥=_{S} B, iff B ⊆ E whenever A ⊆ E and E ∈ μAExts(S). Since μAExts(S) ⊆ AExts(S), it is clear that Aμ∥=_{S} B whenever A ∥=_{S} B. Unlike strict arguability, minimal psychological entailment does not play a significant role in the following theories of reasoned assumptions. It is discussed in more detail in §51 along with the logical notion of circumscription.

§16. Several other inferential relationships are also worth naming. Let d, e ∈ D and S ⊆ D. We say d and e are cotenable in S if there is some E ∈ AExts(S) such that d, e ∈ E, or put another way, if ∅ |∼_{S} {d, e}. We say S is coherent if AExts(S) ≠ ∅, and is incoherent otherwise. We say that d is assumable in S if S ∪ {d} is coherent, and realizable in S if some S′ ⊃ S ∪ {d} is coherent. Clearly, S is coherent iff ∅ |∼_{S} S, d is assumable iff {d} |∼_{S} {d}, and d is realizable iff for some A ⊆ D, A ∪ {d} |∼_{S} {d}. It is also easy to see that if d and e are cotenable in S, each is arguable in S; that if S is coherent and d is inevitable in S, d is arguable in S; that if S is coherent and both d and e are inevitable in S, d and e are cotenable in S; and that if S is coherent and A, B ⊆ S, then A |∼_{S} B.

If D has the structure of the set of sentences of an ordinary logical language, there is a 1-1 function ¬ : D → D taking elements to negations. For this important special class of domains, we introduce the following terms. We say d is doubtless in S iff ¬d is not arguable in S. Similarly, d is conceivable in S iff ¬d is not inevitable in S. Arguability and doubtlessness are thus dual notions, as are inevitability and conceivability. We say d is decided by S iff for every E ∈ AExts(S) either d ∈ E or ¬d ∈ E, and that S is ambivalent about d iff d is not decided by S. We say S is arguably consistent if there is some E ∈ AExts(S) such that for every d ∈ D, either d ∉ E or ¬d ∉ E, and arguably inconsistent if for some d and E, d, ¬d ∈ E ∈ AExts(S). We say S is inevitably consistent (or simply consistent) if S is coherent and for every E ∈ AExts(S) and d ∈ D, either d ∉ E or ¬d ∉ E. S is inevitably inconsistent if S is coherent but there is some d such that for every E ∈ AExts(S), d ∈ E and ¬d ∈ E. It is clear that if S is consistent, S is arguably consistent; that if d and ¬d are cotenable in S, S is inconsistent; that if d is doubtless in S yet decided by S, d is inevitable in S; and that if d is inevitable in S and e is arguable in S, d and e are cotenable in S. Note that these notions are weaker than the usual notions of consistency, for we have made no assumptions about iterated negations, that is we allow d ∈ S but ¬¬d ∉ S. If D has the structure of the Lindenbaum algebra of sentences of a logical language, then ¬¬ is the identity. In this case it is clear that d is decided by S iff ¬d is decided by S, and that S is ambivalent about d iff ¬d is not decided by S. We pursue these more familiar notions later under the topic Logical theories.

§17. As is usual with formal systems, we can construct bigger autological agents out of smaller ones. Two basic constructions are sum and product agents. Let (D_{1}, I_{1}, S̸_{1}, J_{1}, <·_{1}) and (D_{2}, I_{2}, S̸_{2}, J_{2}, <·_{2}) describe two autological agents. The sum of these is an agent (D, I, S̸, J , <·) such that

(1) D = D_{1} ∪ D_{2},

(2) I(d) = {S ⊆ D | d ∈ D_{1} ⊃[S ∩ D_{1} ∈ I_{1}(d)] ∧ d ∈ D_{2} ⊃[S ∩ D_{2} ∈ I_{2}(d)]}

(3) S̸ = {S ⊆ D | S ∩ D_{1} ∈ S̸_{1} ∧ S ∩ D_{2} ∈ S̸_{2}}

(4) J (d, S) = {E | d ∈ D_{1} ⊃[E ∩ D_{1} ∈ J_{1}(d, S ∩ D_{1})] ∧ d ∈ D_{2} ⊃[E ∩ D_{2} ∈ J_{2}(d, S ∩ D_{2})]}

(5) <· = {(S, S′) | S ∩ D_{1} <·_{1} S′ ∩ D_{1} ∧ S ∩ D_{2} <·_{2} S′ ∩ D_{2}}.

The product of the two agents is an agent such that (1) D = D_{1} × D_{2},

(2) I((d_{1}, d_{2})) = {S ⊆ D | ∃S_{1} ∈ I_{1}(d_{1}) ∃S_{2} ∈ I_{2}(d_{2}) S = S_{1} × S_{2}},

(3) S̸ = {S ⊆ D | ∃S_{1} ∈ S̸_{1} ∃S_{2} ∈ S̸_{2} S = S_{1} × S_{2}},

(4) J ((d_{1}, d_{2}), S) = {E | ∃S_{1}, E_{1} ⊆ D_{1} ∃S_{2}, E_{2} ⊆ D_{2} S = S_{1} × S_{2} ∧ E = E_{1} × E_{2} ∧

E_{1} ∈ J_{1}(d_{1}, S_{1}) ∧ E_{2} ∈ J_{2}(d_{2}, S_{2})},

(5) <· = {(S, S′) | ∃S_{1}, S′_{1} ⊆ D_{1} ∃S_{2}, S′_{2} ⊆ D_{2} S = S_{1} × S_{2} ∧ S′ = S′_{1} × S′_{2} ∧

S_{1} <·_{1} S_{2} ∧ S′_{1} <·_{2} S′_{2}}.

The sum construction appears quite frequently in artificial intelligence systems, which often divide into independent databases operating with different inferential schemes.

Elemental theories

§18. The first theory of reasoned assumptions we consider is the theory of simple reasons. Simple reasons are so named because they involve what seem to be the weakest useful notion of reason, one on which all the following theories elaborate. This theory makes no assumptions about D, has no general restrictions on states, and interprets all components as (possibly trivial) “simple reasons,” in contrast to the “defeasible reasons” defined in the next section. We split the definition into two parts due to some intervening subsidiary definitions.

(18.1) Definition (Simple Reasons I). An agent’s use of simple reasons is characterized by (D, I, S̸, J), where

(i) D is a set,

(ii) For each d ∈ D, there are sets A, B, C ⊆ D such that

I(d) = A \\ B ∥− C = {S ⊆ D | A ⊆ S ⊆ B^{c} ⊃ C ⊆ S},

(iii) S̸ = Q,

(iv) For each d ∈ D and S ⊆ D,

J (d, S) = {E | d ∈ E ⊃[d ∈ S ∨ ∃e ∈ E ∃A, B, C ⊆ D
I(e) = A \\ B ∥− C ∧ A ⊆ E ⊆ B^{c} ∧ d ∈ C]}.

Recalling our earlier notation, we abbreviate the subsets of P D corresponding to reason interpretations as expressions of the form A \\ B ∥− C, where A, B, C ⊆ D. The definition of I interprets reasons so that the “conclusions” C must be held if the “antecedents” A are held and none of the “qualifiers” B are held. Note that expressions like A \\ B ∥− C are part of the metalanguage in which we discuss the agent. The agent’s language of thought, if any, need not express reasons in the same way. The notation A \\ B ∥− C also allows us to speak of the “same” reason even when we extend D to a larger domain, since if A, B, C ⊆ D and D ⊆ D′, we also have A, B, C ⊆ D′. This property greatly simplifies mechanizations of agents based on simple reasons expressed in this way, since the domain of state components can be extended indefinitely without necessitating changes in previously expressed reasons. Finally, observe that the expression ∅ \\ ∅ ∥− ∅ means the trivial interpretation, the set P D.

(18.2) Definition. A reason with interpretation A \\ B ∥− C is said to be valid in S iff its antecedent conditions hold, that is, iff A ⊆ S ⊆ B^{c}.

In this way, component-admissible extensions are those extensions which locally appear “grounded” since each of the elements is in the initial set or is a conclusion of a valid reason. We base the general restriction giving admissible extensions on a notion of globally grounded extensions.

(18.3) Definition. A finite reason is an element d ∈ D such that there are finite subsets A, B, C ⊆ D with I(d) = A \\ B ∥− C.

(18.4) Definition. E is a (finitely) grounded extension of S iff S < E and for each e ∈ E there is a (finite) grounding set G ⊆ E and a well-ordering <_{G} of G such that e ∈ G and whenever d ∈ G, either (1) d ∈ S or (2) there is some (finite) reason f ∈ G and sets A, B, C ⊆ D such that I(f) = A \\ B ∥− C, A ⊆ G, E ⊆ B^{c}, d ∈ C, and A <_{G} f <_{G} d. For each S ⊆ D, GExts(S) denotes the set of grounded extensions of S, and FGExts(S) the set of finitely grounded extensions of S.

(18.5) Corollary. If E is a grounded extension of S, e ∈ E, G is a grounding set of e, and d ≤_{G} e, then {g ∈ G | g ≤_{G} d} is a grounding set for d in E, as is G itself.

Grounding sets bear a remarkable similarity to open neighborhoods in a topological space, but I have not been able to make them into such since the intersection of two grounding sets need not be a grounding set.

(18.6) Corollary. FGExts ⊆ GExts.

(18.7) Theorem. GExts ⊆ QExts.

Proof. The claim is just that grounded extensions also appear locally grounded. Suppose E ∈ GExts(S) and e ∈ E. Then if e ∉ S, there is a grounding set G for e. But since e ∈ G and e ∉ S, there is a valid reason supporting e in G, and hence in E as well.

(18.8) Definition (Simple Reasons II). Grounded, finitely grounded, and locally grounded simple reasons agents are characterized respectively by AExts = GExts, AExts = FGExts, and AExts = QExts.

For the sake of simplicity and practical relevance we normally discuss finitely grounded simple reasons agents, take AExts = FGExts, and explicitly state whenever we consider general grounded or locally grounded agents.

Examples. We adopt the convention that if ¬ : D → D and A ⊆ D we write ¬A to mean {¬a | a ∈ A}, and if S ⊆ D, we write I^{∗}(S) to mean {I(d) | d ∈ S}. In all the examples, we usually assume A, B, C, D and their negations to be subsets of D composed of trivially interpreted elements, so if a ∈ A, then I(a) = I(¬a) = ∅ \\ ∅ ∥− ∅. Comments, if any, follow the example to which they refer.

(18.9) I^{∗}(S) = {∅ \\ ∅ ∥− ∅}, AExts(S) = {S} If S has only trivially interpreted elements, it is its own admissible extension.

(18.10) I^{∗}(S) = {∅ \\ ∅ ∥− A}, AExts(S) = {S ∪ A} This sort of reason can be viewed as setting out unqualified premises.

(18.11) I^{∗}(S) = {A \\ ∅ ∥− A}, AExts(S) = {S} Note that S ∪ A is a component-admissible extension of S, but neither a grounded component-admissible extension of S, nor a minimal component-admissible extension of S, nor a minimal extension of S.

(18.12) I^{∗}(S) = {∅ \\ ¬A ∥− A}, AExts(S) = {S ∪ A} This sort of reason is commonly called a normal default; a “default” since it sanctions an inference in which one draws a conclusion because one has no valid reason for drawing the opposite conclusion, and “normal” since this sort of default is so commonly useful in artificial intelligence. Note that S ∪ ¬A is also a minimal extension of S, but is not component-admissible.

(18.13) I^{∗}(S) = {∅ \\ A ∥− A}, AExts(S) = ∅ Note that while S ∪ A is an admissible state, moreover a minimal extension of S, it is not componentadmissible.

(18.14) I^{∗}(A) = {∅ \\ C ∥− B}, I^{∗}(B) = {∅ \\ ∅ ∥− ∅}, I^{∗}(C) = {∅ \\ ∅ ∥− D}, I^{∗}(D) = {∅ \\ ∅ ∥− C}

AExts(A) = {A ∪ B}

Note that A ∪ C ∪ D is a minimal component-admissible extension of A, but not a grounded extension of A.

(18.15) I^{∗}(S) = {∅ \\ ¬A ∥− A, ∅ \\ A ∥− ¬A}, AExts(S) = {S ∪ A, S ∪ ¬A} This example exhibits the multiple admissible extensions of the motivating examples of §6.

(18.16) I^{∗}(S) = {∅ \\ A ∥− A, ∅ \\ ∅ ∥− A}, AExts(S) = {S ∪ A} In contrast to 18.13, the second reason supports A regardless of the incoherence of the first reason.

(18.17) I^{∗}(S) = {∅ \\ A ∥− A, ∅ \\ ∅ ∥− ¬A}, AExts(S) = ∅ Since we have provided no connection between the interpretations of A and ¬A, this example has the same basic structure as 18.13.

(18.18) I^{∗}(S) = {∅ \\ ∅ ∥− A, ∅ \\ ∅ ∥− ¬A}, AExts(S) = {S ∪ A ∪ ¬A} Since the agent has not been given logical structure, we draw no further conclusions from this inconsistent extension.

(18.19) I^{∗}(S) = {∅ \\ ¬A ∥− A, ∅ \\ ¬B ∥− B, A \\ ∅ ∥− ¬B, B \\ ∅ ∥− ¬A},

AExts(S) = {S ∪ A ∪ ¬B, S ∪ ¬A ∪ B}

(18.20) I^{∗}(S) = {∅ \\ ¬A ∥− A, ∅ \\ ¬B ∥− B, ∅ \\ ¬C ∥− C, A \\ ∅ ∥− ¬B, B \\ ∅ ∥− ¬C, C \\ ∅ ∥− ¬A},

AExts(S) = ∅

(18.21) I^{∗}(S) = {∅ \\ ¬A ∥− A, ∅ \\ ¬B ∥− B, ∅ \\ ¬C ∥− C, ∅ \\ ¬D ∥− D, A \\ ∅ ∥− ¬B, B \\ ∅ ∥− ¬C, C \\ ∅ ∥− ¬D, D \\ ∅ ∥− ¬A},

AExts(S) = {S ∪ A ∪ ¬B ∪ C ∪ ¬D, S ∪ ¬A ∪ B ∪ ¬C ∪ D}

Note how the parity of these cycles (even in 18.19 and 18.21, odd in 18.20) affects the existence of admissible extensions.

(18.22) I^{∗}(S) = {∅ \\ B ∥− A, ∅ \\ ∅ ∥− ¬A}, AExts(S) = {S ∪ A ∪ ¬A} Note that contrary conclusions cannot “push backwards” through reasons to support qualifiers.

(18.23) Suppose {d_{i}}_{i=0}^{∞} is a set of distinct elements of D such that for each i ≥ 0, I(d_{i}) = ∅ \\ ∅ ∥− {d_{i+1}}. Then AExts({d_{i}}) = {{d_{j} | j ≥ i}}. Even though each set {d_{i}} is finite, its admissible extension is infinite.

(18.24) Let D = {d_{i}}_{i=0}^{∞} and D = D ⊕{e, f}, where for each i ≥ 0, I(d_{i}) = ∅ \\ ∅ ∥− {d_{i+1}}, and where I(e) = D \\ ∅ ∥− {f} and I(f) = ∅ \\ ∅ ∥− ∅. Let S = {d_{0}, e}. Then GExts(S) = {D}, but FGExts(S) = ∅ since no finite argument for f exists.

I apologize for several little white lies among these examples. These stem from the alternative expressions that some reason interpretations allow. For example, the expression A \\ ∅ ∥− A means the same set as does ∅ \\ ∅ ∥− ∅, namely P D. Further, the expression ∅ \\ A ∥− A means the same as does ∅ \\ ∅ ∥− A. Thus it is wrong to call {∅ \\ A ∥− A} incoherent yet to call {∅ \\ ∅ ∥− A} coherent. We expressed the examples as simply as possible for the sake of comprehension, but these difficulties can always be avoided by slightly more complex statements of examples. For example, if I(a) = ∅ \\ {b} ∥− {c}, I(b) = I(c) = ∅ \\ ∅ ∥− ∅, and I(d) = {c} \\ ∅ ∥− {b}, then the set {a, d} is incoherent, while {a, d, c} is coherent.

In spite of their simplicity and practical significance, very little is known about the properties of simple reason agents. The few results which follow are merely indicative of the questions that remain to be answered. We first examine some alternate characterizations of the notion of admissible extension.

(18.25) Definition. Let S, E ⊆ D. Then ⟨Λ_{α}⟩ (α an ordinal), the levels from S in E, are defined for all ordinals by

Λ_{0}(S, E) = S,

Λ_{α+1}(S, E) = Λ_{α} ∪ ⋃{C ⊆ D | ∃e ∈ Λ_{α}(S, E) ∃A, B ⊆ D
I(e) = A \\ B ∥− C ∧ A ⊆ Λ_{α}(S, E) ∧ E ⊆ B^{c}},

and for limit ordinals λ,

Λ_{λ}(S, E) = ⋃_{α<λ} Λ_{α}(S, E).

We also define Λ(S, E) = ⋃_{α} Λ_{α}(S, E) to be the sum of all levels. When no confusion is possible, we sometimes abbreviate Λ_{α}(S, E) by Λ_{α} and Λ(S, E) by Λ.

(18.26) Corollary. If α ≤ β, then S ⊆ Λ_{α}(S, E) ⊆ Λ_{β}(S, E) ⊆ Λ(S, E).

(18.27) Corollary. If Λ_{α}(S, E) = Λ_{α+1}(S, E), then Λ_{α}(S, E) = Λ(S, E).

(18.28) Theorem. If α is the cardinal number |D| + 1, then Λ(S, E) = Λ_{α}(S, E).

Proof. Since D has fewer than α elements, it must be that for some β + 1 ≤ α no new element is introduced in Λ_{β+1}, in other words, Λ_{β} = Λ_{β+1}. But then Λ_{β} = Λ, and since Λ_{β} ⊆ Λ_{α} ⊆ Λ, we have Λ = Λ_{α}.

(18.29) Definition. If e ∈ Λ(S, E), the rank of e in Λ(S, E) is the least ordinal α such that e ∈ Λ_{α}(S, E). If A ⊆ Λ(S, E), the rank of A in Λ(S, E) is the least ordinal not less than the rank of any element of A.

(18.30) Lemma. If S < E, then Λ(S, E) ⊆ E.

Proof. Let S < E. Clearly Λ_{0} ⊆ E, so assume Λ_{β} ⊆ E for each β < α. If α is a limit ordinal, then by definition Λ_{α} ⊆ E. If α is a successor ordinal, say α = β + 1, let e ∈ Λ_{α}. If e ∈ S, then e ∈ E, and if e ∉ S there is a d ∈ Λ_{β} with I(d) = A \\ B ∥− C, A ⊆ Λ_{β}, E ⊆ B^{c}, and e ∈ C. Since E is admissible, this means C ⊆ E, so e ∈ E, hence Λ_{α} ⊆ E. Thus Λ ⊆ E.

(18.31) Theorem (Stratification). If E ∈ GExts(S) then Λ(S, E) = E.

Proof. Suppose E ∈ GExts(S). Since S < E, by the preceding lemma we have Λ ⊆ E. To see that E ⊆ Λ, suppose e ∈ E. Since E is a grounded extension of S, there is a grounding set G ⊆ E for e from S in E. We show G ⊆ Λ by <_{G}-induction. Let f ∈ G have no predecessors in <_{G}. Clearly f is the minimum of G, and by definition of G, we must have f ∈ S, hence f ∈ Λ. Now suppose that f ∈ G and for each d <_{G} f, either d ∈ S or there is a grounding subargument G′ ⊆ G for d. If f ∈ S, then f ∈ Λ, and if f ∉ S, there is a d ∈ G such that I(d) = A \\ B ∥− C, A <_{G} d <_{G} f, E ⊆ B^{c}, and f ∈ C. By the inductive hypothesis, A ⊆ Λ and d ∈ Λ, so there is some ordinal α such that A ⊆ Λ_{α} and d ∈ Λ_{α}. But then by construction C ⊆ Λ_{α+1}, so f ∈ Λ. Hence E ⊆ Λ, so E = Λ(S, E).

(18.32) Corollary. If E ∈ GExts(S) and α = |E| + 1, then E = Λ_{α}(S, E).

(18.33) Corollary. If E ∈ GExts(S) and α is its rank, then E = Λ_{α}(S, E).

(18.34) Corollary. If E ∈ FGExts(S), then E = Λ_{ω}(S, E).

Proof. Let E ∈ FGExts(S) and e ∈ E. Since e has a finite grounding set G, the rank of e is at most |G|, hence e ∈ Λ_{ω}(S, E). Thus E ⊆ Λ_{ω}(S, E), so by Lemma 18.30, E = Λ_{ω}(S, E).

(18.35) Theorem (Fixed Point). If E = Λ(S, E), then E ∈ GExts(S).

Proof. Suppose Λ = E. Since S ⊆ Λ, S ⊆ E. Let e ∈ E with I(e) = A \\ B ∥− C, and suppose A ⊆ E. Then there is an ordinal α such that e ∈ Λ_{α} and A ⊆ Λ_{α}, so by construction if E ⊆ B^{c} as well, then C ⊆ Λ_{α+1} ⊆ E. Thus E is admissible. We prove E is a grounded extension of S by induction on rank. Specifically, we prove that each element of E has a rank-preserving grounding set, a set G ⊆ E such that rank(a) ≤ rank(b) whenever a ≤_{G} b. Let e ∈ E have rank α. If α = 0, then e ∈ S and we are done since {e} is a rank-preserving grounding argument for e from S in E. Now assume that α > 0 and all elements of rank less than α have rank-preserving grounding arguments. By construction, there is some β < α and d ∈ Λ_{β} such that I(d) = A \\ B ∥− C, A ⊆ Λ_{β}, E ⊆ B^{c}, and e ∈ C. Then by inductive hypothesis each element of {d} ∪ A has a rank-preserving grounding argument, so merge these arguments preserving rank-order, and add e to the end, so producing a rank-preserving grounding argument for e. Thus E ∈ GExts(S).

(18.36) Corollary. E ∈ GExts(S) iff E = Λ(S, E).

(18.37) Theorem. If every reason in D is finite, then E ∈ FGExts(S) iff E = Λ_{ω}(S, E).

Proof. Suppose every reason in D is finite. By Corollary 18.34, we need only show that Λ_{ω} = E implies E ∈ FGExts(S). Suppose Λ_{ω} = E. We first show Λ_{ω} = Λ. Suppose, by way of contradiction, that Λ ≠ Λ_{ω}. Then there must be a least ordinal α ≥ ω such that for some e ∈ D, e ∈ Λ_{α+1} − Λ_{α}. Since α is minimal, Λ_{ω} = Λ_{α}, for otherwise Λ_{ω} = Λ_{ω+1} and hence Λ_{ω} = Λ. By construction, there is some f ∈ Λ_{α}, I(f) = A \\ B ∥− C, A ⊆ Λ_{α}, E ⊆ B^{c}, and e ∈ C. Since A is finite, this means the rank of A is also finite. Thus there is some β < ω such that A ⊆ Λ_{β} and f ∈ Λ_{β}, so e ∈ Λ_{β+1} ⊆ Λ_{ω}, a contradiction. Thus Λ = Λ_{ω}, and since Λ_{ω} = E, by Theorem 18.35 E is a grounded extension of S. We see that E is finitely grounded by induction on rank. Clearly, if e ∈ Λ_{0}, then e ∈ S, hence {e} is a rank-preserving grounding set. Now suppose the rank of e is α + 1 < ω. Then by construction there is some f ∈ Λ_{α} with I(f) = A \\ B ∥− C, A ⊆ Λ_{α}, E ⊆ B^{c}, and e ∈ C. By inductive hypothesis, each of f and A have finite rank-preserving grounding sets, so merge these preserving rank-order, add e to the end, and the result is a finite rank-preserving grounding order for e.

(18.38) Question. For each simple reasons agent, can one characterize those sets which have no admissible extensions? Unique admissible extensions? Multiple admissible extensions? Finitely many admissible extensions? Infinitely many admissible extensions? Only finite admissible extensions? Only infinite admissible extensions? Or, turning the order around, can one characterize simple reasons agents in which all sets are coherent or have finite or unique admissible extensions?

(18.39) Theorem (Grounded Minimality). GExts ⊆ μQExts.

Proof. GExts ⊆ QExts by Theorem 18.7, so suppose E ∈ GExts(S), E′ ∈ QExts(S), and E′ ⊆ E. We first show Λ(S, E) ⊆ Λ(S, E′) by induction. Clearly Λ_{0}(S, E) ⊆ Λ_{0}(S, E′) since each equals S. Assume Λ_{β}(S, E) ⊆ Λ_{β}(S, E′) for each β < α. If α is a limit ordinal, then by definition Λ_{α}(S, E′) ⊆ Λ_{α}(S, E). If α is a successor ordinal, say α = β + 1, let e ∈ Λ_{α}(S, E). If e ∈ S, then e ∈ E′, and if e ∉ S there is a d ∈ Λ_{β}(S, E) with I(d) = A \\ B ∥− C, A ⊆ Λ_{β}(S, E), E ⊆ B^{c}, and e ∈ C. But since E′ ⊆ E ⊆ B^{c}, this means e ∈ Λ_{α}(S, E′). Hence Λ(S, E) ⊆ Λ(S, E′). But by Theorem 18.31 and Lemma 18.30, E = Λ(S, E) ⊆ Λ(S, E′) ⊆ E′.

(18.40) Corollary. GExts = μGExts and FGExts = μFGExts.

(18.41) Corollary. If S <· D, then AExts(S) = {D}.

Proof. Suppose S <· D. Now if E ∈ AExts(S), then E ⊆ D, and since AExts = μAExts by the previous corollary, this means E = D.

(18.42) Corollary. If S <· D, then A ∥=_{S} B for every A, B ⊆ D.

(18.43) Corollary. If A |∼_{S} B for every A, B ⊆ D, then A ∥=_{S} B for every A, B ⊆ D.

Note that the converse does not hold if S is incoherent.

(18.44) Theorem (Trivial Coherence). A trivially interpreted set is its own admissible extension.

Proof. Suppose S ⊆ D, and for all d ∈ S, I(d) = P D. Then S is admissible, and it is clearly finitely grounded, so AExts(S) = {S}.

(18.45) Definition. A monotonic reason is an element d ∈ D such that for some A, C ⊆ D, I(d) = A \\ ∅ ∥− C.

“Monotonic” is used because extensions of a state cannot invalidate such a reason, so that the set of conclusions added by the reason is monotone nondecreasing with enlargements of the state. Note that all trivially interpreted state components are finite and monotonic.

(18.46) Theorem (Monotonic Coherence). If D contains only monotonic reasons, every subset of D has a unique grounded extension.

Proof. Suppose all reasons are monotonic, and let S ⊆ D. Consider E = Λ(S, ∅). Since all reasons are monotonic, Λ(S, ∅) = Λ(S, X) for each X ⊆ D. In particular, E = Λ(S, ∅) = Λ(S, E), so by Theorem 18.35 E ∈ GExts(S). Now if E′ ∈ GExts(S), then E′ = Λ(S, E′) = E by the previous observation, so GExts(S) = {E}.

(18.47) Corollary. If D contains only finite monotonic reasons, every subset of D has a unique finitely grounded extension.

As Example 18.24 shows, we cannot drop the finiteness restriction unless we allow infinite grounded arguments.

(18.48) Definition. Suppose S ⊆ D and d ∈ D. The set S mentions d iff for some e ∈ S, I(e) = A \\ B ∥− C and d ∈ A ∪ B ∪ C. Two sets A, B ⊆ D have disjoint mention sets iff A mentions no b ∈ B and B mentions no a ∈ A. A subset A ⊆ S is an isolated subset of S iff A and S − A have disjoint mention sets.

Note that S and ∅ are isolated subsets of S.

(18.49) Theorem (Disjoint Sum). Suppose ⟨S_{i}⟩_{i=0}^{n} and ⟨Ê_{i}⟩_{i=0}^{n} (n ≤ ∞) are sequences such that for all i, 0 ≤ i ≤ n, S_{i} ⊆ D and Ê_{i} = AExts(S_{i}). Suppose further that for all i, j, if 0 ≤ i ≠ j ≤ n, then each E ∈ Ê_{i} and E′ ∈ Ê_{j} have disjoint mention sets. Then

AExts(⋃_{i=0}^{n} S_{i}) = { ⋃_{k=0}^{n} E^{k} | ⟨E^{k}⟩_{k=0}^{n} ∈ ∏_{i=0}^{n} Ê_{i}}.

Proof. Let E = ⋃_{k} E^{k} for some ⟨E^{k}⟩ ∈ Π_{i}Ê_{i}. We first check the admissibility of E. Let e ∈ E. If e is trivially interpreted, then E ∈ I(e), and if e has a nontrivial interpretation, then e ∈ E^{l} for some l. Now E^{l} ∈ I(e) by hypothesis, and since the other parts of E are not mentioned by E^{l}, they also satisfy e, hence E is admissible. Now if e ∉ ⋃_{i} S_{i}, then it is in some E^{l}. By hypothesis, e has a finite grounding argument in E^{l}, and since it does not mention the rest of E, this same argument grounds e in E. Hence E is a finitely grounded extension of S, so E ∈ AExts(⋃_{i} S_{i}). Now suppose E ∈ AExts(⋃_{i} S_{i}), and consider E ∩ ⋃ Ê_{i}. No element in this set mentions any other in ⋃ Ê_{j} for j ≠ i, so it must be that E ∩ ⋃ Ê_{i} ∈ AExts(S).

(18.50) Corollary. S ⊆ D is incoherent if S has an incoherent isolated subset.

Proof. Suppose A ⊆ S ⊆ D, A is isolated in S, and AExts(A) = ∅. Then AExts(A)×AExts(S −A) = ∅, so by the disjoint sum theorem, AExts(S) = ∅.

(18.51) Corollary. Suppose S = ⋃_{i} S_{i}, where for each i, AExts(S_{i}) = {E_{i}}, and if j ≠ i, E_{i} and E_{j} have disjoint mention sets. Then AExts(S) = {⋃_{i} E_{i}}.

Proof. Since each S_{i} has a unique extension, there is only one sequence in the product of the extension sets, so the claim follows by the disjoint sum theorem.

(18.52) Corollary. Suppose S = ⋃_{i} S_{i} and if j ≠ i, E_{i} and E_{j} have disjoint mention sets. Then |AExts(S)| > 1 if for some i, |AExts(S_{i})| > 1.

Proof. Suppose S_{i} has several admissible extensions. Then the product of the extension sets contains several sequences. The unions of these sequences cannot be identical, since by the disjointness of mention sets this would mean the supposedly distinct extensions of S_{i} were identical. Thus by the disjoint sum theorem, the union of the sets has several admissible extensions.

(18.53) Corollary. S is coherent iff every isolated subset of S is coherent.

(18.54) Corollary. S has a unique extension iff every isolated subset of S has a unique extension.

(18.55) Definition. A set S ⊆ D is called simple iff S has no isolated subsets other than itself and ∅.

For example, if D = {a}, then D is simple, and if D = {a, b} where both elements have trivial interpretations, then D is not simple, since each of {a} and {b} is.

(18.56) Lemma. There are incoherent simple sets.

Proof. As before, if I(a) = ∅ \\ {b} ∥− {c}, I(b) = I(c) = ∅ \\ ∅ ∥− ∅, and I(d) = {c} \\ ∅ ∥− {b}, then {a, d} is simple but incoherent.

(18.57) Theorem. For each n ∈ N there is a simple set S ⊆ D with |AExts(S)| = n.

Proof. If n = 0, the simple set must be incoherent, and the preceding lemma applies. If n > 0, let D and E be two disjoint sets with |D| = |E| = n, D = {d_{i}}_{i=1}^{n} and E = {e_{i}}_{i=1}^{n}. For each i, 1 ≤ i ≤ n, let I(d_{i}) = ∅ \\ E − {e_{i}} ∥− {e_{i}} and I(e_{i}) = ∅ \\ ∅ ∥− ∅. Then each d_{i} mentions E, so D is simple. But clearly, AExts(D) = {D ∪ {e_{i}} | 1 ≤ i ≤ n}. Hence |AExts(D)| = n.

Rather than pursue this structure theory further here, we merely mention the possibility of deriving sufficient conditions on coherence from McDermott’s termination theorem for RMS.^{13} (RMS is an artificial intelligence system for maintaining a database by means of reasons. It is discussed in §46.)

By a finite agent we mean one with finite domain D. Necessarily, all reasons of a finite agent are finite as well. Suppose for the time being that (D, I) characterizes a simple reasons agent and |D| = n < ω. We then have |I| = O(n^{2}), and the following results.

(18.58) Theorem. Is S ∈ S̸? can be computed in time O(n^{2}).

Proof. Checking the interpretation of each element of S requires O(n) steps, and S can have up to n elements.

(18.59) Theorem. Is E ∈ Exts(S)? can be computed in time O(n^{2}).

Proof. Checking E ⊃ S requires O(|E| + |S|) = O(n) steps, and checking admissibility of E requires O(n^{2}) steps as above.

(18.60) Theorem. Is E ∈ QExts(S)? can be computed in time O(n^{2}).

Proof. Checking E ∈ Exts(S) requires O(n^{2}) steps, as above. We can check component-admissibility of E at the same time by marking the consequences of each valid reason encountered in checking the admissibility of E, and when done scanning E to see if all unmarked elements are in S. This is also O(n^{2}).

(18.61) Theorem. Is E ∈ FGExts(S)? can be computed in time O(n^{3}).

Proof. Consider the following algorithm.

1. Λ_{0} ← S, i ← 0

2. While Λ_{i} ≠ Λ_{i−1} do
3. i ← i + 1
4. Λ_{i} ← Λ_{i−1}
5. For each e ∈ Λ_{i−1} do
6. I(e) = A \\ B ∥− C
7. If A ⊆ Λ_{i−1} and E ⊆ B^{c} then Λ_{i} ← Λ_{i} ∪ C.
8. Return E =?Λ_{i}.

The algorithm clearly answers E ∈ FGExts(S), since by Corollary 18.36 E ∈ FGExts(S) iff E = Λ, and Λ_{i} = Λ whenever Λ_{i} = Λ_{i+1}. Steps 1, 4, 6, 7 and 8 cost O(n). The iteration of step 5 may run O(n) times, so the cost of 5-7 is O(n^{2}). Now note that since |D| = n, the loop of step 2 can run at most n + 1 times, so the total cost is O(n) + O(n) · (O(n) + O(n^{2})) = O(n^{3}).

(18.62) Theorem. Find E ∈ Exts(S)! is in P, Find E ∈ QExts(S)! and Find E ∈ FGExts(S)! are in NP, and Count Exts(S)!, Count QExts(S)!, and Count FGExts(S)! are in #P.

Proof. D ∈ Exts(S) for every S (as we observe later in Theorem 20.1), so finding an extension is trivial. The other five problems may all be computed by guessing sets E ⊆ D and accepting iff the desired condition is true, all deterministic polynomial computations from the above theorems.

13[Charniak, Riesbeck, and McDermott 1980]

(18.63) Conjecture. Find E ∈ QExts(S)! is NP-complete.

(18.64) Question. Is Find E ∈ FGExts(S)? NP-complete?

(18.65) Theorem. Is E ∈ μExts(S)?, Is E ∈ μQExts(S)?, and Is μQExts(S) = ∅? are in co-NP.

Proof. We see E ∉ μExts(S) is in NP by first checking E ∈ Exts(S) deterministically as above, then guessing a proper subset E′ of E, checking if it is in Exts(S) as well, and accepting if either E ∉ Exts(S) or E′ ∈ Exts(S). The case of E ∈ μQExts(S) is the same except for testing E, E′ ∈ QExts(S). For the last question, we guess E ⊃ S, check if E ∈ QExts(S), and accepting if so, since μQExts(S) will be nonempty iff QExts(S) is empty.

(18.66) Conjecture. The following problems are NP-hard: Is E ∈ μExts(S)?, Is E ∈ μQExts(S)?, Is μQExts(S) = ∅?, and Find E ∈ μQExts(S)!

The development of efficient algorithms for deciding these questions is still the subject of study. The most studied question is that of constructing an admissible extension of a set if one exists. This is one of the tasks of RMS and its relatives. The hard case of course is when no admissible extension exists. The known algorithms typically discover this by exhaustive failure. If a suitably mechanizable characterization of coherence was known, more efficient algorithms might be possible.

(18.67) Question. Are there interesting classes of simple reasons agents for which construction of admissible extensions is tractable?

We now drop the supposition that D is finite and replace it with the notion of a finite “virtual” domain with respect to some subset of D.

(18.68) Definition. The universe U(S) of a set S is the smallest set containing S and containing the mention sets of each of its elements, that is, S ⊆ U(S) and if d ∈ U(S) and I(d) = A \\ B ∥− C, then A, B, C ⊆ U(S).

Note that if D is finite, then every S ⊆ D has a finite universe; that if S has a finite universe, then all reasons in S are finite; and that two sets with disjoint universes have disjoint mention sets, though the converse need not be true.

(18.69) Conjecture. Is U(S) finite? for finite S is undecidable.

(18.70) Lemma. If E ∈ FGExts(S), then E ⊆ U(S).

Proof. Let E ∈ FGExts(S). Then E = Λ_{ω}(S, E), and we prove Λ_{ω} ⊆ U(S) by induction. Since Λ_{0} = S, Λ_{0} ⊆ U(S), so suppose Λ_{α} ⊆ U(S) and consider Λ_{α+1}. Any e ∈ Λ_{α+1} − Λ_{α} is supported, and hence mentioned by a valid reason in Λ_{α}, so Λ_{α+1} ⊆ U(S) too. Thus Λ_{ω} = E ⊆ U(S).

(18.71) Theorem. If S has a finite universe, then admissible extensions of S are decidable.

Proof. Compute U(S), check E ⊆ U(S), and check E ∈ FGExts(S) by the earlier methods for finite D.

(18.72) Corollary. If S ∪ {d} has a finite universe, then both the arguability and inevitability of d in S are decidable.

(18.73) Theorem. If D is recursively enumerable and the set of nontrivial reasons in D has a finite universe, then the finite admissible states are recursively enumerable.

Proof. Let U be the universe of the set of all nontrivial reasons. By the previous methods the admissible states S ⊆ U are enumerable. Also, all finite subsets of D − U are enumerable, so we can by composition enumerate the sets S ∪ U, where S ⊆ U, S ∈ S̸, and U ⊆ D − U, and so exhaust the finite elements of S̸.

§19. Our second theory of reasoned assumptions modifies the simple reasons theory by interpreting state components as defeasible reasons. To do this, we suppose a function Defeated : D → D and interpret the element Defeated(d) to mean the reason d has been defeated and cannot support conclusions. This is achieved by trivializing the interpretation of d in the presence of Defeated(d), specifically, for each d ∈ D having

I(d) ⊃ {S ⊆ D | Defeated(d) ∈ S}.

In effect, we interpret d in different ways depending on whether the state containing it also contains Defeated(d) or not.

(19.1) Definition. Defeasible reasons agents are characterized by the following additions to the requirements on simple reasons agents:

(i) There is a 1-1 function Defeated : D → D,

(ii) For each d ∈ D if I(d) = A \\ B ∥− C, then Defeated(d) ∈ B.

Thus if I(d) = A \\ B^{+} ∥− C, where B^{+} = B ∪ {Defeated(d)}, we have by simple rewriting

A ⊆ S ⊆ (B^{+})^{c} ⊃ C ⊆ S iff [A ⊆ S ⊆ B^{c} ∧ Defeated(d) ∉ S] ⊃ C ⊆ S
iff Defeated(d) ∉ S ⊃[A ⊆ S ⊆ B^{c} ⊃ C ⊆ S],

which is the desired condition of triviality.

Examples. We adopt the convention of eliding most mentions of Defeated elements in reasons by use of a superscript ^{+} to refer to the appropriate element. We omit for brevity most previous examples, since they are basically unchanged by the introduction of defeasible reasons.

(19.2) I^{∗}(S) = {∅ \\ ∅^{+} ∥− A},  AExts(S) = {S ∪ A}  (as before)
(19.3) I^{∗}(S) = {∅ \\ ¬A^{+} ∥− A},  AExts(S) = {S ∪ A}  (as before)
(19.4) I^{∗}(S) = {∅ \\ ∅^{+} ∥− A, ∅ \\ ∅^{+} ∥− ¬A},  AExts(S) = {S ∪ A ∪ ¬A}  (as before)

(19.5) S = {a, b}, I(a) = ∅ \\ ∅^{+} ∥− A, I(b) = ∅ \\ ∅^{+} ∥− {Defeated(a)},

AExts(S) = {S ∪ {Defeated(a)}}

Note how the challenge defeats the otherwise valid reason.

(19.6) S = {a, b, c}, I(a) = ∅ \\ ∅^{+} ∥− A, I(b) = ∅ \\ ∅^{+} ∥− {Defeated(a)}, I(c) = ∅ \\ ∅^{+} ∥− {Defeated(b)}

AExts(S) = {S ∪ A ∪ {Defeated(b)}}

Here the first challenge is defeated by the second, so the initial reason’s conclusions are unaffected.

As one might suspect, the innocuous reinterpretation of reasons lets us extend any simple reasons theory to a defeasible reasons theory without important changes of meaning.

(19.7) Theorem (Defeasible Embedding). Suppose that D and I characterize a simple reasons agent. Then there is a defeasible reasons agent (D′, I′) such that D ⊆ D′ and if S ⊆ D, the admissible extensions of S in (D, I) are exactly the admissible extensions of S in (D′, I′).

Proof. Let (D, I) describe a simple reasons agent. We define the desired defeasible reasons agent (D′, I′) as follows. Let D′ = D_{1}⊕D_{2}, where D = D_{1} = D_{2}. We always say d ∈ D to mean d ∈ D_{1}, and write the corresponding element of D_{2} as d′. If d ∈ D and I(d) = A \\ B ∥− C, define I′(d) = A \\ B ∪{d′} ∥− C. If d′ ∈ D′, define I′(d′) = ∅ \\ {d} ∥− ∅ (the trivial interpretation). Now suppose S ⊆ D and E ⊆ D′. We claim E ∈ AExts(S) iff E ∈ AExts′(S). First, suppose E ∈ AExts(S). Then E ⊆ D and E ∩ D_{2} = ∅, so for each d ∈ E, E ∈ I′(d), hence E ∈ S̸. But clearly all grounding arguments in D then translate directly into grounding arguments in D′, so E ∈ AExts′(S). Second, suppose instead that E ∈ AExts′(S). Clearly d′ cannot occur in E unless d′ ∈ S, which is not the case, so E ∩ D_{2} = ∅. Because of this, I′(d) = I(d) for each d ∈ E, so E ∈ S̸, and every grounding argument in E translates directly into a grounding argument in D, so E ∈ AExts(S).

(19.8) Theorem (Monotone Embedding). Suppose (D, I) characterizes a simple reasons agent, and that ⟨S_{i}⟩_{i=0}^{n} (n ≤ ω) is a sequence of subsets of D. Then there is a defeasible reasons agent (D′, I′) and a sequence ⟨S′_{i}⟩_{i=0}^{n} of monotone nondecreasing subsets of D′ such that for each i there is a 1-1 correspondence f between the admissible extensions of S_{i} and S′_{i} such that E = f(E) ∩ D whenever S_{i} <· E.

Proof. Suppose (D, I) characterizes a simple reasons agent, and that ⟨S_{i}⟩_{i=0}^{n} (n ≤ ω) is a sequence of subsets of D. We define the desired defeasible reasons agent (D′, I′) as follows. Let D′ = D ⊕(D ×(ω +1)). We use the elements (d, n) for finite n to encode the addition or removal of the element d as follows.

For each d ∈ D, Defeated(d) = (d, ω), Defeated((d, ω)) = d, and for each k ∈ N, Defeated((d, 2k)) = (d, 2k + 1), and Defeated((d, 2k + 1)) = (d, 2k).

For each d ∈ D, if I(d) = A \\ B ∥− C, then I′(d) = A \\ B∪{(d, ω)} ∥− C. Also, I′((d, ω)) = ∅ \\ {d} ∥− ∅ (the trivial interpretation), I′((d, 0)) = ∅ \\ {(d, 1)} ∥− {d}, and for each k ∈ N, I′((d, 2k + 1)) = ∅ \\ {(d, 2k)} ∥− ∅ and I′((d, 2k + 2)) = ∅ \\ {(d, 2k + 3)} ∥− {(d, 2k + 1)}.

Let S′_{0} = S_{0} × {0}, and if 0 < i ≤ n, let S′_{i+1} = S′_{i} ∪ {(d, 2k + 2) | d ∈ S_{i} △ S_{i+1} ∧ k = max{j | (d, 2j) ∈ S′_{i}}}. Obviously, the sequence ⟨S′_{i}⟩_{i=0}^{n} is nondecreasing, and for each i, S′_{i} ∩ D = ∅. We claim for each i, 0 ≤ i ≤ n, |AExts(S_{i})| = |AExts′(S′_{i})|. Clearly, no elements of D ×{ω} can ever occur in admissible extensions of S′_{i} since no reasons have them as conclusions. Now the element (d, 0) will be defeated iff the last change with respect to d was its removal, so if S_{i} contains d, (d, 0) will be undefeated in every extension of S′_{i}, and so include d. These elements then reproduce the extensions of the original set. Since the elements of D mention no elements of D × (ω + 1), if E ∈ AExts′(S′_{i}), then E ∩ D ∈ AExts(S_{i}).

§20. While the ideas of simple and defeasible reasons play important roles in the practice of artificial intelligence, they have important limitations in the sorts of state specifications they can express. The most obvious of these is the inability to exclude any state component from admissible states.

(20.1) Theorem. D is admissible in the simple reasons theory.

Proof. For all d ∈ D, there are sets A, B, C ⊆ D such that I(d) = A \\ B ∥− C, and for all sets A, B, C ⊆ D, C ⊆ D, and hence A ⊆ D ⊆ B^{c} ⊃ C ⊆ D, is always true.

Noting this obvious inexpressiveness, it is natural to ask exactly which state spaces S̸ are expressible in the simple reasons theory. As we noted before, the empty set cannot be excluded.

(20.2) Theorem. ∅ is admissible in the simple reasons theory.

Beyond such trivialities, the expressive capabilities of the simple reasons theory are largely unknown. Yet if we return to the unrestricted theory, we have clearer expressive powers.

(20.3) Theorem. Let S̸ ⊆ P D. Then I can be chosen so that Q = S̸ ∪ {∅}.

Proof. Define I so that for each d ∈ D, I(d) = S̸.

Since the general theory has unlimited but practically unusable expressive capabilities, while the simple reasons theory is somewhat inexpressive in spite of its demonstrated practical utility, we look for additions to the simple reasons theory which increase the expressive capabilities in useful ways. The most obvious candidate addition is the notion of denial.

(20.4) Definition. An agent’s use of simple reasons and denials is characterized exactly as in the simple reasons theory, except that D = D^{+} ⊕ D^{−}, where for each d ∈ D^{+} there are sets A, B, C ⊆ D such that

I(d) = A \\ B ∥− C = {S ⊆ D | A ⊆ S ⊆ B^{c} ⊃ C ⊆ S},

and for each d ∈ D^{−} there is some (necessarily unique) e ∈ D such that

I(d) = {S ⊆ D | e ∉ S}.

Note that this theory is just like the simple reasons theory except that some state components, the denials, can rule out the presence of specific elements. To make this ability uniform, we need only assume the existence of a 1-1 function ¬ : D → D^{−} such that for each d ∈ D, I(¬d) = {S ⊆ D | d ∉ S}. This augmentation of the theory adds expressive power, but again we have no characterization of exactly which state spaces are so expressible.

(20.5) Theorem. If D is infinite, then not every state space can be attained with only finite reasons and denials.

Proof. If |D| = ω, then the number of possible finite reasons is ω, as is the number of possible denials. Hence the number of possible interpretation functions is (ω + ω)^{ω} = ω^{ω}. But the number of possible state spaces is 2^{2^{ω}}, and ω^{ω} < 2^{2^{ω}}.

One should not confuse the nature or uses of denials with the qualifiers of simple reasons or the defeaters of defeasible reasons. Their natures differ in that the former sort of element absolutely rules out some conclusion from appearing in any admissible extension, while the latter sorts of elements permit the reasons’s conclusions to appear if supported by other reasons. The uses of these notions differ as well. Inclusion of a denial in a set rules out some element with no recourse, and for “no reason” other than the denial itself. In contrast, the other notions permit reasoned retraction of assumptions, defeating an assumption for a reason, and possibly later restoring the assumption if the defeating reason itself is defeated.

One special case to consider is when the agent admits self-denials or contradictions. Such are elements denying themselves, and are necessarily inadmissible, since I(d) = {S ⊆ D | d ∉ S}. Such elements are useful in practice, as we see later.

(20.6) Theorem. Every agent using simple reasons and denials can be realized within an agent using only simple reasons and a single self-denial.

Proof. Suppose D = D^{+} ⊕ D^{−} and I characterize an agent’s use of simple reasons and denials. Let ⊥ be some object not in D. Let D′ = D ∪ {⊥}. Define I′ for each d ∈ D′ by

(1) I′(⊥) = ∅,

(2) If d ∈ D^{+}, then I′(d) = I(d),
(3) If d ∈ D^{−} and I(d) = {S ⊆ D | e ∉ S}, then I′(d) = {e} \\ ∅ ∥− {⊥}.

Let S̸ and S̸′ be the respective sets of admissible states. We claim S̸ = S̸′. Clearly, ⊥ ∉ S for each S ∈ S̸′, so both S̸ and S̸′ are subsets of P D. Suppose d ∈ D^{+}. Then by definition, I(d) ⊆ I′(d). Suppose d ∈ D^{−} is a denial of e ∈ D. Then I′(d) = {e} \\ ∅ ∥− {⊥} = {S ⊆ D | e ∈ S ⊃ ⊥ ∈ S} = I(d) ∪ {S ⊆ D′ | ⊥ ∈ S} ⊃ I(d). Thus if d ∈ D, I(d) ⊆ I′(d), and if S ⊆ D, ⋂_{d∈S} I(d) ⊆ ⋂_{d∈S} I′(d), so S ∈ S̸ only if S ∈ S̸′. Suppose S ∈ S̸′. Then ⊥ ∉ S, so if S ∈ I′(d), S ∈ I(d), hence S ∈ S̸.

(20.7) Theorem. Let S̸ ⊆ P D, ⊥ ∉ D, and D′ = D ∪ {⊥}. Then S̸ ∪ {∅} is realizable as the set of admissible states employing simple reasons D and contradiction ⊥ if a distinct representative can be chosen from each set in P D − S̸ − {∅}.

Proof. If S ∈ P D − S̸ − {∅}, let R(S) ∈ S be the selected distinct representative. Define I so that I(d) = P D if d is not one of the representatives, and I(d) = S \\ D − S ∥− {⊥} if d = R(S). We claim S ⊆ D is admissible iff S ∈ S̸ ∪ {∅}. Now I(R(S)) = P D′ − {S}, since S ⊆ X ⊆ (D − S)^{c} ⊃ ⊥ ∈ X is false only when X = S. Thus S is inadmissible, since R(S) ∈ S ∉ I(R(S)), so S is inadmissible whenever S ∉ S̸ ∪ {∅}. Now ∅ is admissible as usual, so suppose d ∈ S ∈ S̸. If d is not a selected representative of any set, S ∈ I(d) by definition. But if d = R(S′), then S ≠ S′, so S ∈ I(d). Hence in either case, S ∈ I(d), so S is admissible.

Unfortunately, the complete expressivity of the theory of simple reasons with a contradiction is useless in practice, since the system of distinct representative of the nontrivial inadmissible states is little more than a list of all the inadmissible states, and that is about as useful as the list of all admissible states used in the interpretations of Theorem 20.3.

(20.8) Theorem. If d is a denial, but not a self-denial, then {d} is admissible.

Proof. Suppose I(d) = {S ⊆ D | e ∉ S} and e ≠ d. Then {d} ∈ I(d), so {d} is admissible.

Note that if d is a denial of e, and e a denial of d, then any element c such that I(c) = ∅ \\ ∅ ∥− C with d, e ∈ C is effectively a self-denial.

Logical theories

§21. The theories of simple and defeasible reasons capture the essence of reasoned assumptions, yet are quite general since little restriction was placed on the nature of possible state components. Indeed, though it would divert us too much here, one can develop these theories as theories of reasons invariant under arbitrary bijections of domains. Since the structure of a logical language need not be preserved under arbitrary automorphisms, we see that the general theories are more widely applicable than ones formulated in terms of logical languages. But logical languages play an important role in artificial intelligence, since most mechanized agents constructed to date are explicitly representational, so we continue the development of our theories by examining the special case of representational domains. By representational we mean domains isomorphic with logical languages, that is, systems invariant under all bijections which preserve the logical structure of state components. Since we allow arbitrary re-representation, we may choose a particular logical language as our reference language for the purpose of setting out the special logical theories of reasoned assumptions. This we do shortly, but first we treat an important non-linguistic notion that also enters into logical systems.

§22. The theory of reasoned assumptions with deductively closed states adds to the simple reasons theory the constitutive assumption that all states be closed with respect to a “deducibility” relation and that admissible extensions allow “deductions” in grounding arguments as well as valid reasons. The notion of deducibility we employ is more abstract than the familiar one of deducibility in logic.

(22.1) Definition. A deducibility relation in D is a relation ⊢ on P D × P D satisfying (i) A ⊢ A (reflexivity) (ii) If A ⊆ B and A ⊢ C, then B ⊢ C (monotonicity) (iii) If A ⊢ B and A ⊢ C, then A ⊢ B ∪ C (additivity) (iv) If A ⊢ B and B ⊢ C, then A ⊢ C (transitivity)

(v) If A ⊢ {e}, then C ⊢ {e} for some finite C ⊆ A. (compactness)

We say S ⊆ D is deductively closed if B ⊆ S whenever A ⊆ S and A ⊢ B.

Agents whose admissible states must be deductively closed can be thought of as agents which regularly perform some inferences automatically in addition to the inferences involved in making reasoned assumptions, whose problematic character sometimes demands less automatic, more deliberate consideration. By defining deductive closure at this level of abstraction, we allow a wide range of deducibility relations which we can use to characterize a variety of agents with limited automatic inferencing powers. For example, if we take ⊢ to be ⊃, so that A ⊢ B iff A ⊃ B, then all sets are “deductively closed,” and we have again the simple reasons theory. This corresponds to an agent with no (automatic) inferential resources at all. Even without logical structure for D, the theory of data-types can be cast in terms of deducibility relations.^{14} In these theories, sets of components represent partial data-structures, and deductive closure amounts to filling in missing but implied “fields” to further complete the data-structure. If D has the structure of an ordinary logical language, we might define A ⊢ B to hold whenever for each b ∈ B, either b ∈ A or b is a ground instance of some a ∈ A. In this case, the deductive closure of a set of wffs is just the wffs plus all their ground instances. This corresponds to agents who can automatically instantiate formulas but not combine them. One can go on like this in many ways, for instance capturing agents who can automatically apply Modus Ponens but not instantiate schema or universal statements.

(22.2) Theorem. D is deductively closed.

Proof. Suppose A ⊆ D and A ⊢ B. Then by definition B ⊆ D, so D is deductively closed.

14[Scott 1982]

(22.3) Lemma. If every S ∈ Ŝ is deductively closed, then ⋂ Ŝ is deductively closed.

Proof. Suppose A ⊆ ⋂ Ŝ and A ⊢ B. Then for every S ∈ Ŝ, A ⊆ S, and since S is deductively closed, B ⊆ S. But then B ⊆ ⋂ Ŝ.

(22.4) Definition. Th(S), the deductive closure of S ⊆ D, is given by

Th(S) = ⋂{S′ | S ⊆ S′ and S′ deductively closed}.

The elements of Th(∅), if any, are called tautologies.

(22.5) Corollary. Th(S) is the smallest deductively closed superset of S.

(22.6) Theorem. If A ⊆ B ⊆ D, then (i) Th(A) ⊆ Th(B), and (ii) Th(Th(A)) = Th(A), and (iii) A is deductively closed iff A = Th(A).

Proof. (i) Since A ⊆ B ⊆ Th(B), Th(B) is a deductively closed superset of A, so by definition, Th(A) ⊆ Th(B).

(ii) Since every set is its own superset, and since Th(A) is deductively closed, by definition we have Th(Th(A)) ⊆ Th(A). But also by definition we have Th(A) ⊆ Th(Th(A)), so Th(A) = Th(Th(A)).

(iii) (if) Immediate since Th(A) is deductively closed. (only if) Since A is its own superset, Th(A) ⊆ A. But A ⊆ Th(A), so A = Th(A).

We also introduce interdeducibility equivalence classes into D by defining [ ] : D → P D for all d ∈ D so that

[d] = {e ∈ D | {d} ⊢ {e} ∧ {e} ⊢ {d}}.

Here we write [d] instead of [ ](d). When D has logical structure, the ranges of [ ] are called Lindenbaum algebras.

(22.7) Definition. E is a (finitely) grounded extension of S iff S < E and for each e ∈ E there is a (finite) grounding set G ⊆ E and a well-ordering <_{G} of G such that e ∈ G and whenever d ∈ G, either (1) d ∈ S or (2) there is some (finite) reason f ∈ G and sets A, B, C ⊆ D such that I(f) = A \\ B ∥− C, A ⊆ G, E ⊆ B^{c}, d ∈ C, and A <_{G} f <_{G} d, or (3) there is some (finite) set A ⊆ G such that A <_{G} d and A ⊢ {d}. For each S ⊆ D, GExts(S) is the set of grounded extensions of S, and FGExts(S) is the set of finitely grounded extensions of S.

Note that this definition of groundedness differs from the earlier definition only by allowing grounding sets to include deductive arguments as well as “axioms” and valid reasons. Indeed, the definition is exactly the same as before if we choose ⊢ to mean ⊃, so this notion extends the earlier one.

(22.8) Definition. An agent’s use of finitely grounded simple reasons in deductively closed states is characterized by the axioms for simple reasons agents with the following modifications:

(i) ⊢ is a deducibility relation in D (ii) R = {S ⊆ D | S = Th(S)} (iii) For each d ∈ D and S ⊆ D,

J (d, S) = {E | d ∈ S ∨ E − {d} ⊢ {d} ∨ ∃e ∈ E ∃A, B, C ⊆ D
I(e) = A \\ B ∥− C ∧ d ∈ C ∧ A ⊆ E ⊆ B^{c}}.

Again, this definition extends that of simple reasons agents, for if ⊢ is ⊃, then R = P D and E −{d} ⊬ {d}, reducing J to the earlier definition.

(22.9) Theorem. GExts ⊆ QExts.

Proof. Suppose E ∈ GExts(S) and e ∈ E has grounding set G. Then by the definition of finite grounding sets, either e ∈ S, or there is an A ⊆ G such that e ∉ A and A ⊢ {e}, hence E − {e} ⊢ {e}, or some valid reason in E supports e.

(22.10) Definition. Let S, E ⊆ D. Then ⟨Λ_{α}⟩ (α an ordinal), the levels from S in E, are defined for all ordinals by

Λ_{0}(S, E) = S,

Λ_{α+1}(S, E) = Th(Λ_{α}) ∪ ⋃{C ⊆ D | ∃e ∈ Λ_{α}(S, E) ∃A, B ⊆ D
I(e) = A \\ B ∥− C ∧ A ⊆ Λ_{α}(S, E) ∧ E ⊆ B^{c}},

and for limit ordinals λ,

Λ_{λ}(S, E) = ⋃_{α<λ} Λ_{α}(S, E).

We define Λ(S, E) = ⋃_{α} Λ_{α}(S, E) to be the sum of all levels.

Note how the levels of a deductively closed agent include the deductive closures of the preceding levels of inference via valid reasons. Not surprisingly, we can extend the previous results for simple reasons agents to the deductively closed case. The reader is invited to skip to Corollary 22.29 while we perform this chore.

(22.11) Corollary. If α ≤ β, then S ⊆ Λ_{α}(S, E) ⊆ Λ_{β}(S, E) ⊆ Λ(S, E).

(22.12) Corollary. If Λ_{α}(S, E) = Λ_{α+1}(S, E), then Λ_{α}(S, E) = Λ(S, E).

(22.13) Theorem. If α is the cardinal number |D| + 1, then Λ(S, E) = Λ_{α}(S, E).

Proof. Since D has fewer than α elements, it must be that for some β + 1 ≤ α no new element is introduced in Λ_{β+1}, in other words, Λ_{β} = Λ_{β+1}. But then Λ_{β} = Λ, and since Λ_{β} ⊆ Λ_{α} ⊆ Λ, we have Λ = Λ_{α}.

(22.14) Definition. If e ∈ Λ(S, E), the rank of e in Λ(S, E) is the least ordinal α such that e ∈ Λ_{α}(S, E). If A ⊆ Λ(S, E), the rank of A in Λ(S, E) is the least ordinal not less than the rank of any element of A.

(22.15) Lemma. For every S, E ⊆ D, Λ(S, E) = Th(Λ(S, E)).

Proof. Suppose A ⊆ Λ. A has rank, say α, so if A ⊢ B, then B ⊆ Λ_{α+1} ⊆ Λ.

(22.16) Lemma. If S < E, then Λ(S, E) ⊆ E.

Proof. Let S < E. Clearly Λ_{0} ⊆ E, so assume Λ_{β} ⊆ E for each β < α. If α is a limit ordinal, then by definition Λ_{α} ⊆ E. If α is a successor ordinal, say α = β + 1, let e ∈ Λ_{α}. If e ∈ S, then e ∈ E, so suppose e ∉ S. If e ∈ Th(Λ_{β}), then e ∈ E since E is deductively closed. If e ∉ Th(Λ_{β}) there is a d ∈ Λ_{β} with I(d) = A \\ B ∥− C, A ⊆ Λ_{β}, E ⊆ B^{c}, and e ∈ C. Since E is admissible, this means C ⊆ E, so e ∈ E. Hence Λ_{α} ⊆ E, so Λ ⊆ E.

(22.17) Theorem (Stratification). If E ∈ GExts(S) then Λ(S, E) = E.

Proof. Since S < E, by the preceding lemma we have Λ ⊆ E. To see that E ⊆ Λ, suppose e ∈ E. Since E is a grounded extension of S, there is a grounding set G ⊆ E for e from S in E. We show G ⊆ Λ by <_{G}-induction. Let f ∈ G have no predecessors in <_{G}. Clearly f is the minimum of G, and by definition of G, we must have f ∈ S, hence f ∈ Λ. Now suppose that f ∈ G and for each d <_{G} f, either d ∈ S or there is a grounding subargument G′ ⊆ G for d. If f ∈ S, then f ∈ Λ. If {g ∈ G | g <_{G} f} ⊢ {f}, then f ∈ Λ since Λ is deductively closed. Otherwise there is a d ∈ G such that I(d) = A \\ B ∥− C, A <_{G} d <_{G} f, E ⊆ B^{c}, and f ∈ C. By the inductive hypothesis, A ⊆ Λ and d ∈ Λ, so there is some ordinal α such that A ⊆ Λ_{α} and d ∈ Λ_{α}. But then by construction C ⊆ Λ_{α+1}, so f ∈ Λ. Hence E ⊆ Λ, so E = Λ.

(22.18) Corollary. If E ∈ GExts(S) and α = |E| + 1, then E = Λ_{α}(S, E).

(22.19) Corollary. If E ∈ GExts(S) and α is its rank, then E = Λ_{α}(S, E).

(22.20) Corollary. If E ∈ FGExts(S), then E = Λ_{ω}(S, E).

(22.21) Theorem (Fixed Point). If E = Λ(S, E), then E ∈ GExts(S).

Proof. Suppose Λ = E. Since S ⊆ Λ, S ⊆ E. Let e ∈ E with I(e) = A \\ B ∥− C, and suppose A ⊆ E. Then there is an ordinal α such that e ∈ Λ_{α} and A ⊆ Λ_{α}, so by construction if E ⊆ B^{c} as well, then C ⊆ Λ_{α+1} ⊆ E. Similarly, if A ⊢ B, A ⊆ Λ, and A has rank α, then B ⊆ Λ_{α+1} ⊆ Λ. Thus E is admissible. We prove E is a grounded extension of S by induction on rank. Specifically, we prove that each element of E has a rank-preserving grounding set, a set G ⊆ E such that rank(a) ≤ rank(b) whenever a ≤_{G} b. Let e ∈ E have rank α. If α = 0, then e ∈ S and we are done since {e} is a rank-preserving grounding argument for e from S in E. Now assume that α > 0 and all elements of rank less than α have rank-preserving grounding arguments. Necessarily, α is a successor ordinal, since no elements are introduced at limit ordinals, so suppose α = β + 1. If e ∈ Th(Λ_{β}), then there is some G ⊆ Λ_{β} such that G ⊢ {e}, and otherwise there is some d ∈ Λ_{β} such that I(d) = A \\ B ∥− C, A ⊆ Λ_{β}, E ⊆ B^{c}, and e ∈ C. Then by inductive hypothesis each element of G or {d} ∪ A has a rank-preserving grounding argument, so merge these arguments preserving rank-order, and add e to the end, so producing a rank-preserving grounding argument for e. Thus E ∈ GExts(S).

(22.22) Corollary. E ∈ GExts(S) iff E = Λ(S, E).

(22.23) Theorem. If every reason in D is finite, then E ∈ FGExts(S) iff E = Λ_{ω}(S, E).

Proof. Suppose every reason in D is finite. By Corollary 22.20, we need only show that Λ_{ω} = E implies E ∈ FGExts(S). Suppose Λ_{ω} = E. We first show Λ_{ω} = Λ. Suppose, by way of contradiction, that Λ ≠ Λ_{ω}. Then there must be a least ordinal α ≥ ω such that for some e ∈ D, e ∈ Λ_{α+1} − Λ_{α}. Since α is minimal, Λ_{ω} = Λ_{α}, for otherwise Λ_{ω} = Λ_{ω+1} and hence Λ_{ω} = Λ. If e ∈ Th(Λ_{ω}) then there is some G ⊆ Λ_{ω} such that G ⊢ {e}. Since ⊢ is compact, there is a finite G′ ⊆ G such that G′ ⊢ {e}. But then the rank of G′ is finite, say β, so e ∈ Λ_{β+1}, a contradiction. If e ∉ Th(Λ_{ω}), then by construction, there is some f ∈ Λ_{ω}, I(f) = A \\ B ∥− C, A ⊆ Λ_{ω}, E ⊆ B^{c}, and e ∈ C. Since A is finite, this means the rank of A is also finite. Thus there is some β < ω such that A ⊆ Λ_{β} and f ∈ Λ_{β}, so e ∈ Λ_{β+1} ⊆ Λ_{ω}, a contradiction. Thus Λ = Λ_{ω}, and since Λ_{ω} = E, by Theorem 22.21 E is a grounded extension of S. We see that E is finitely grounded by induction on rank. Clearly, if e ∈ Λ_{0}, then e ∈ S, hence {e} is a rank-preserving grounding set. Now suppose the rank of e is α + 1 < ω. If e ∈ Th(Λ_{α}), then there is a finite G ⊆ Λ_{α} such that G ⊢ {e}. If e ∉ Th(Λ_{α}), then by construction there is some f ∈ Λ_{α} with I(f) = A \\ B ∥− C, A ⊆ Λ_{α}, E ⊆ B^{c}, and e ∈ C. By inductive hypothesis, each of G or f ∪ A have finite rank-preserving grounding sets, so merge these preserving rank-order, add e to the end, and the result is a finite rank-preserving grounding order for e.

(22.24) Theorem (Grounded Minimality). GExts ⊆ μQExts.

Proof. GExts ⊆ QExts by Theorem 22.9, so suppose E ∈ GExts(S), E′ ∈ QExts(S), and E′ ⊆ E. We first show Λ(S, E) ⊆ Λ(S, E′) by induction. Clearly Λ_{0}(S, E) ⊆ Λ_{0}(S, E′) since each equals S. Assume Λ_{β}(S, E) ⊆ Λ_{β}(S, E′) for each β < α. If α is a limit ordinal, then by definition Λ_{α}(S, E′) ⊆ Λ_{α}(S, E). If α is a successor ordinal, say α = β + 1, let e ∈ Λ_{α}(S, E). If e ∈ S or e ∈ Th(Λ_{β}(S, E)), then e ∈ E′, and otherwise there is a d ∈ Λ_{β}(S, E) with I(d) = A \\ B ∥− C, A ⊆ Λ_{β}(S, E), E ⊆ B^{c}, and e ∈ C. But since E′ ⊆ E ⊆ B^{c}, this means e ∈ Λ_{α}(S, E′). Hence Λ(S, E) ⊆ Λ(S, E′). But by Theorem 22.17 and Lemma 22.16, E = Λ(S, E) ⊆ Λ(S, E′) ⊆ E′.

(22.25) Corollary. GExts = μGExts and FGExts = μFGExts.

(22.26) Corollary. If S <· D, then AExts(S) = {D}.

(22.27) Corollary. If S <· D, then A ∥=_{S} B for every A, B ⊆ D.

(22.28) Corollary. If A |∼_{S} B for every A, B ⊆ D, then A ∥=_{S} B for every A, B ⊆ D.

(22.29) Corollary. Let d, e ∈ D be such that Th({d, e}) = D. Then if both are cotenable in S, everything is arguable, that is ∅ |∼_{S} B for every B ⊆ D, and if both are inevitable in S, then everything is inevitable, in fact A ∥=_{S} B for every A, B ⊆ D.

Proof. If S <· E and d, e ∈ E, then E = D, so by definition ∅ |∼_{S} B for every B ⊆ D. If S is incoherent, everything is inevitable by Theorem 14.1, and if S is coherent and both d and e are inevitable, they are cotenable, so AExts(S) = {D} and again Theorem 14.1 applies.

This result holds special interest later when, in logical language domains, we consider state components p, ¬p such that Th({p, ¬p}) = D.

(22.30) Definition. The deductive reduction (D′, I′, ⊢′) of a deductively closed agent (D, I, ⊢) is an agent such that (1) D′ = D, (2) for each d ∈ D, if I(d) = A \\ ∅ ∥− C, then I′(d) = P D, otherwise I′(d) = I(d), and (3) ⊢′ is the least deductive closure relation on D such that (a) A ⊢′ B whenever A ⊢ B, and (b) for each d ∈ D, if I(d) = A \\ ∅ ∥− C, then {d} ∪ A ⊢′ C.

(22.31) Theorem. If (D, I′, ⊢′) is the deductive reduction of (D, I, ⊢), then S̸′ = S̸, J′ = J, and AExts′ = AExts.

Proof. First note by definition that I′ ⊃ I and Th′ ⊃ Th, so Q′ ⊃ Q and R′ ⊆ R.

(S̸′ = S̸) Suppose S ∈ S̸′. Then S ∈ R′, so S ∈ R. Now if d ∈ S is non-monotonic, then S ∈ I(d) by definition, and if I(d) = A \\ ∅ ∥− C and A ⊆ S, then C ⊆ S by deductive closure, so S ∈ I(d). Thus S ∈ Q, hence S ∈ S̸. Now suppose S ∈ S̸. Then S ∈ Q, so S ∈ Q′. Clearly S ⊆ Th′(S), yet if A ⊢′ B and A ⊆ S, then A ⊢′ B is generated by some deductions in ⊢ and some reasons. But since S ∈ Q, these reasons must be satisfied, and produce the necessary conclusions, so B ⊆ S as well. Thus S ∈ R′, so S ∈ S̸′.

(J′ = J) By the preceding, Exts = Exts′, so let d ∈ D and S, E ⊆ D. If d ∈ S, then E satisfies both J (d, S) and J′(d, S), so suppose d ∉ S. First, if E ∈ J (d, S), and if E − {d} ⊢ {d}, then E −{d} ⊢′ {d}, and if E −{d} ⊬′ {d}, then there is an e ∈ E, I(e) = A \\ B ∥− C, A ⊆ E ⊆ B^{c} and d ∈ C. If B ≠ ∅, this e satisfies J′(d, S) too, and if B = ∅, then E − {d} ⊢′ {d}. Hence E ∈ J′(d, S). Second, suppose E ∈ J′(d, S). If some valid reason supports d in E, it also does so for J (d, S). If no valid reason supports d in E, then E − {d} ⊢′ {d}. In this case, if E − {d} ⊬ {d}, there is a monotonic reason which supports d for J (d, S). Hence E ∈ J (d, S), and J′ = J.

(AExts′ = AExts) By the preceding, QExts′ = QExts. First suppose E ∈ FGExts(S). Then each d ∈ E has a grounding argument G, which is also a grounding argument in the deductive reduction under reinterpretation of the steps. Thus E ∈ F GExts′(S). Second, suppose E ∈ FGExts′(S). Then each d ∈ E has a grounding argument G. But the steps of G can each be reinterpreted as several steps in the unreduced agent, so G is also a grounding argument there. Thus E ∈ FGExts(S), so AExts′ = AExts.

(22.32) Corollary (Non-Monotonic Inconsistency is Semi-Classical (Reiter)). If A |∼_{S} B for every A, B ⊆ D, then Th′(S) = D in the deductive reduction of the agent.

Proof. Suppose A |∼_{S} B for every A, B ⊆ D. By Theorem 14.2 this means S <· D, hence AExts(S) = {D}. By the previous theorem, AExts′(S) = {D}, so D ∈ FGExts(S). Since no non-monotonic reasons can be valid in D, by the definition of groundedness and the transitivity of deducibility, this means S ⊢′ {d} for each d ∈ D, hence D = Th′(S).

§23. The invertible reasons theory is an augmentation of the deductively closed simple reasons theory in which all state components have negations, and in which contradicted conclusions can be passed backwards through reasons to contradict antecedents or raise qualifications. Intuitively, this theory recalls a logical structure for reasons in which A \\ B ∥− C really means A ∧ ¬B ⊃ C, so that when asserting ¬C, ¬A ∨ B can be inferred. Of course, A \\ B ∥− C cannot really be A ∧ ¬B ⊃ C, for then the normal default ∅ \\ ¬C ∥− C becomes ¬C ⊃ C. This is equivalent to simply C, so that under this rewriting defaults are pure axioms rather than rules which may or may not introduce reasoned assumptions. We escape this absolute triviality by making the notion of admissible extension more complex, allowing individual reasons to be used in different ways in different circumstances. Instead of at most contributing its conclusions C, a reason A \\ B ∥− C in this theory can also be used to infer elements of ¬A or B on occasion. Unfortunately, as we shall see soon, even this more involved reading of invertible reasons trivializes theories of reasoned assumptions, albeit in a different way.

(23.1) Definition. An agent’s use of invertible reasons is characterized by (D, I, R, J , <·) together with relations ¬ and ⊢ such that

(i) D is a set,

(ii) ¬ : D → D is 1-1,

(iii) ⊢ is a deducibility relation such that for each d ∈ D, [d] = [¬¬d],

(iv) For each d ∈ D, there are sets A, B, C ⊆ D such that

I(d) = A \\ B ∥− C = {S ⊆ D | A ⊆ S ⊆ B^{c} ⊃ C ⊆ S}

(v) R = {S ⊆ D | S = Th(S)}, (vi) For each d ∈ D and S ⊆ D,

J (d, S) = {E | d ∈ S ∨ E − {d} ⊢ {d} ∨ ∃e ∈ E ∃A, B, C ⊆ D
I(e) = A \\ B ∥− C ∧
[(d ∈ C ∧ A ⊆ E ⊆ B^{c}) ∨

(d ∈ B ∧ A ⊆ E ∧ E ∩ B = {d} ∧ E ∩ ¬C ≠ ∅) ∨ (d = ¬d′ ∈ ¬A ∧ A − E = {d} ∧ E ⊆ B^{c} ∧ E ∩ ¬C ≠ ∅)]}

(vii) AExts = FGExts, where E ∈ FGExts(S) iff S < E and for each e ∈ E there is a

finite grounding set G ⊆ E well-ordered by <_{G} such that e ∈ G and whenever d ∈ G, either (1) d ∈ S, or (2) there is some f ∈ G and A, B, C ⊆ D such that f <_{G} d, I(f) = A \\ B ∥− C and either (a) d ∈ C, A ⊆ G, A <_{G} d, and E ⊆ B^{c}, or (b) d ∈ B, A ⊆ G, A <_{G} d, E ∩ B = {d}, and for some c ∈ C, both ¬c ∈ G and ¬c <_{G} d, or (c) d = ¬d′ ∈ ¬A, A − E = {d′}, (A − E) <_{G} d, E ⊆ B^{c}, and for some c ∈ C, both ¬c ∈ G and ¬c <_{G} d, or (3) there is some A <_{G} d such that A ⊢ {d}.

The definition of groundedness means that every element in an admissible extension of S must either be an element of S itself, follow deductively from other elements of the admissible extension, or contribute to the satisfaction of some reason in the admissible extension, where the satisfaction of the reason and the circumstances of the other elements it mentions necessitate introducing the element in order to make the appropriate condition true or false. Unfortunately, invertibility guts the notion that reasons express preferences about what assumptions to make, leaving only statements of anti-agnosticism.

(23.2) Theorem. If I(a) = {∅ \\ {¬b} ∥− {b}} and I(b) = ∅ \\ ∅ ∥− ∅, then AExts({a}) = {Th({a, b}), Th({a, ¬b})}.

Proof. Each of these sets is clearly an extension of {a}, with Th({a, b}) an admissible extension as usual. Th({a, ¬b}) is also a finitely grounded extension, since ¬b has the sequence ⟨a, ¬b⟩ which satisfies condition (2)(b) of the definition.

.

(23.3) Conjecture (Invertible Triviality). In the theory of invertible reasons, AExts = μExts.

§24. We now finally specialize the theory to one involving a logical language in the linguistic reasons theory. Where previously we have not cared how state components express reasons, the idea of the linguistic reasons theory is to express reasons in logical syntax. Since reasons refer to sets of state components, some of which may be other reasons, we must choose the language so that formulas may refer to sets of other formulas. The techniques for accomplishing this are well known, if tedious. It is sufficient for our purposes to restrict all sets of formulas to explicit presentations, to only finite sets, and no quantification over sets or the arguments of \\ ∥− allowed. (One can, of course, allow such quantification and thus make the language at least weak second order.) In summary, we take the language L to contain the \\ ∥− symbol and to be a metalanguage of itself using the quasi-quote notation ⌈ ⌉ for naming formulas and finite sets of formulas. A prime use of these expressions are in stating schematic or quantified reasons, for example

∀x [⌈{p(x)}⌉ \\ ⌈{q(x)}⌉ ∥− ⌈{r(x)}⌉] .

Here an expression like ⌈{p(x)}⌉ represents an open term built up out of the name-constructing functions and the free variable x. For readability, we omit most explicit uses of quasi-quotes in the following since their use should be clear.

(24.1) Definition. An agent’s use of linguistic reasons is characterized by the axioms for simple reasons in deductively closed states, where

(i) D is the set of sentences of a language L as above, (ii) ⊢ is ordinary deducibility (iii) For each d ∈ D,

I(d) = \{ \begin{matrix}\{S ⊆ D | A ⊆ S ⊆ B^{c} ⊃ C ⊆ S\} & if d is closed and d = ⌈A⌉ \\ ⌈B⌉ ∥− ⌈C⌉; \\ P D & otherwise. \end{matrix}

Since states are deductively closed sets of sentences and universally quantified formulas imply all their closed instances, quantified reasons are interpreted as shorthand for all their closed instances. Note that local groundedness becomes trivial in this theory. Because [d] = [¬¬d], if S is a deductively closed set of sentences, S − {d} ⊢ {d} for each d ∈ S, so QExts = Exts.

Examples. In addition to our earlier conventions, we assume that P and Q are ordinary closed wffs of L.

(24.2) S = {∅ \\ {¬P } ∥− {P }}, AExts(S) = {Th(S ∪ {P })}

(24.3) S = {∅ \\ {P } ∥− {P }}, AExts(S) = ∅

(24.4) S = {∅ \\ {¬P } ∥− {P }, ∅ \\ {P } ∥− {¬P }},

AExts(S) = {Th(S ∪ {P }), Th(S ∪ {¬P })}

(24.5) S = {∅ \\ {¬P } ∥− {P }, ∅ \\ {¬Q} ∥− {Q}, ¬(P ∧ Q)},

AExts(S) = {Th(S ∪ {P }), Th(S ∪ {Q})}

(24.6) S = {∅ \\ A ∥− {P }, ∅ \\ B ∥− {Q}, ¬(P ∧ Q)}, AExts(S) = ∅ (24.7) S = {∀n ∈ N [∅ \\ {¬p(n)} ∥− {p(n)}], ∀n ∈ N p(n + 1) ⊃ ¬p(n)},

AExts(S) = {Th(S ∪ {p(n) | n = 2m}), Th(S ∪ {p(n) | n = 2m + 1})}

(24.8) S = {∀n ∈ N [∅ \\ {¬p(n)} ∥− {p(n)}],

∀n > 0 p(n) ⊃ ∃m < n ¬p(m), ∀n > 0 ¬p(n) ⊃ ∃m < n p(m)},

This has an uncountable number of admissible extensions, one for each pattern of alternating p-ness and ¬p-ness. That is, for every sequence of positive integers n_{1}, n_{2}, n_{3}, … there is one admissible extension that contains

p(0), …, p(n_{1} − 1), ¬p(n_{1}), …, ¬p(n_{1} + n_{2} − 1), p(n_{1} + n_{2}), …

and another admissible extension that contains the negations of all of these.

(24.9) S = {∃x p(x), ∀x[∅ \\ {p(x)} ∥− {¬p(x)}} This has a different admissible extension for each equivalence class [p(t)] for closed terms t, namely

Th(S ∪ {p(t)} ∪ {¬p(t′) | t′ a closed term and [p(t′)] ≠ [p(t)]}),

as well as an extension

Th(S ∪ {¬p(t) | t a closed term}),

in which the p-object has no name in the language.

(24.10) S = {∃x p(x), ∀x[∅ \\ {p(x)} ∥− {¬p(x)}, ∀x(x = a ∨ x = b)}

AExts(S) = {Th(S ∪ {p(a), ¬p(b)}), Th(S ∪ {¬p(a), p(b)})}

(24.11) S = {∀n ∈ N [{lot(n + 1)} \\ {¬lot(n)} ∥− {lot(n)}], ∀n ∈ N [{¬lot(n)} \\ {lot(n + 1)} ∥− {¬lot(n + 1)}],

∀n ∈ N [lot(n) ⊃ lot(n + 1)],
¬lot(0), lot(3)}
AExts(S) = {Th(S ∪ {lot(1), lot(2), … }),
Th(S ∪ {¬lot(1), lot(2), … }),
Th(S ∪ {¬lot(1), ¬lot(2), lot(3), … })}

The first axiom says that if n + 1 is a lot, presumably so is n. The second says if n is few, presumably so is n + 1. The third says that more than a lot is also a lot. Note that there is a distinct admissible extension for each choice of the boundary between a few and a lot.

(24.12) Corollary (Non-Monotonic Inconsistency is Semi-Classical). If S is inconsistent and contains no nontrivial monotonic reasons, S is classically inconsistent, that is, Th(S) = L.

Proof. This just restates Corollary 22.32 for the case of a deductively reduced linguistic reasons agent.

(24.13) Definition. A normal reason is an element d ∈ D such that for some A, C ⊆ D, I(d) = A \\ ¬C ∥− C.

(24.14) Theorem (Orthogonality of Extensions (Reiter)). If E, F ∈ AExts(S) contain only normal reasons and E ≠ F, then E ∪ F is inconsistent.

Proof. Suppose E, F ∈ AExts(S) contain only normal reasons, and that E ≠ F. Now E = Λ_{ω}(S, E), F = Λ_{ω}(S, F), and Λ_{0}(S, E) = Λ_{0}(S, F) = S, so there must be a least α ≥ 0 such that Λ_{α+1}(S, E) ≠ Λ_{α+1}(S, F) while Λ_{α}(S, E) = Λ_{α}(S, F). Without loss of generality, suppose e ∈ Λ_{α+1}(S, E) − Λ_{α+1}(S, F). Then there is a d ∈ Λ_{α} such that I(d) = A \\ ¬C ∥− C, A ⊆ Λ_{α}, E ⊆ (¬C)^{c}, and e ∈ C. In fact, C ⊆ E. But since e ∉ Λ_{α+1}(S, F), there is some ¬f ∈ ¬C with ¬f ∈ F. Thus f ∈ E and ¬f ∈ F, so E ∪ F is inconsistent.

(24.15) Theorem (Normal Reasons (Reiter)). If L is restricted so that all reasons are normal, then every S ⊆ L is coherent.

Proof. Suppose every reason is normal. If Th(S) = L, then S <· L, so suppose Th(S) ≠ L. We construct an extension E. Let E_{0} = S, and for i ≥ 0, let T_{i} be a maximal set of closed wffs such that (1)

E_{i} ∪ T_{i} is consistent, and (2) if u ∈ T_{i}, then for some e ∈ E_{i}, I(e) = A \\ ¬C ∥− C, u ∈ C, C ⊆ T_{i}, and A ⊆ E_{i}. Define E_{i+1} = Th(E_{i}) ∪ T_{i}, and E = ⋃_{i=0}^{∞} E_{i}. We prove that for each i ≥ 0, E_{i} = Λ_{i}(S, E), hence Λ_{ω}(S, E) = E, and S <· E.

Clearly, E_{0} = Λ_{0} = S, so assume E_{i} = Λ_{i}. We claim E_{i+1} = Λ_{i+1}.

(E_{i+1} ⊆ Λ_{i+1}) Let e ∈ E_{i+1}. If e ∈ Th(E_{i}), then e ∈ Λ_{i+1}, and if e ∉ Th(E_{i}) there is some f ∈ E_{i}, I(f) = A \\ ¬C ∥− C, A ⊆ E_{i}, f ∈ C, and C ⊆ T_{i}. But since E_{i+1} ⊆ E is consistent, E ⊆ (¬C)^{c}, hence C ⊆ Λ_{i+1}, so e ∈ E_{i+1}.

(Λ_{i+1} ⊆ E_{i+1}) Let e ∈ Λ_{i+1}. If e ∈ Th(Λ_{i}), then e ∈ E_{i+1}, and if e ∉ Th(Λ_{i}) then there is an f ∈ Λ_{i}, I(f) = A \\ ¬C ∥− C, A ⊆ Λ_{i}, E ⊆ (¬C)^{c}, C ⊆ Λ_{i+1}, and e ∈ C. Now if e ∉ E_{i+1}, by the maximality of T_{i} we know E_{i} ∪ T_{i} ∪ {e} is inconsistent, so Th(E_{i}) ∪ T_{i} ∪ {e} is inconsistent, so E_{i+1} ∪ {e} is inconsistent. But since E_{i+1} ⊆ E, this means E ∪ {e} is inconsistent. Since clearly E = Th(E), we must have ¬e ∈ E, contradicting E ⊆ (¬C)^{c}. Hence e ∈ E_{i+1}, so Λ_{i+1} ⊆ E_{i+1}. Thus Λ_{i+1} = E_{i+1} and S <· E.

Results are also known concerning the decidability of coherence, arguability, and inevitability in the linguistic reasons theory, but they are less satisfying than those of the simple reasons theory. Where previously a finite universe ensured computability, the connection inherent in this theory between arguability and logical consistency puts most problems beyond the bounds of recursiveness.

(24.16) Theorem (Reiter). ⋃ AExts(S) is not recursively enumerable in S.

(24.17) Corollary. Coherence is not decidable.

(24.18) Theorem (Church). Consistency is not decidable.

For some special cases, such as finite sentential and monadic sets, arguability and inevitability appear decidable. But rather than continue this topic here, we refer to the discussions in [Reiter 1980], [Mc-Dermott and Doyle 1980], and [Davis 1980].

Attitudinal theories

§25. In the previous theories of reasoned assumptions, there was no commitment to what state components signified, other than reasons. Elements of the domain were not in themselves any familiar psychological organization, but merely the components from which to build mental states. As building blocks, the statements of logical languages can be used to encode versions of beliefs, desires, and other common psychological notions, but they are not beliefs or desires by themselves without further constitutive assumptions. It is tempting, of course, to phrase attitudinal theories directly in terms of logical theories, for attitudes are often taken to be attitudes towards propositions, and languages are the usual way of expressing propositions. However, such direct phrasing can hide fundamental ideas about attitudes among masses of particular linguistic details. To seek clarity, we temporarily retreat from logical theories, and work back up to logical forms after starting once again with the simple reasons theory.

§26. Pick an attitudinal ontology for a psychology, and we can cast its elements directly in the simple reasons theory. In the following, we assume for simplicity that the agent’s attitudes divide into three classes: beliefs (Bel), desires (Des), and intentions (Int). We also assume each particular attitude among these classes is a possible state component, that is, Bel, Des, Int ⊆ D. This leaves open the possibility that D may contain non-attitudinal components. For example, we can take the set of reasons (Rsn) to be outside the sets of attitudes. In such a formulation, we make explicit in reasons the connections between the agent’s attitudes, but we need not assign special import to the attitudes themselves. That is, we might assume that I(a) = P D for each a ∈ Bel ∪ Des ∪ Int. Of course, in an ecological theory of the agent we would wish to interpret these attitudes substantively, so that beliefs, say, indicate sets of possible worlds in which they are true. But here our concern is with narrow theories of the agent, and we can ignore all substantive interpretations except those of reasons.

§27. Rather than resting content with the simple attitudinal theory, we can define further theories of reasoned assumptions by stipulating that states are composed exclusively of attitudes. In terms of the sets we introduced earlier, we assume D = Bel ⊕ Des ⊕ Int. But since reasons are state components, that is, Rsn ⊆ D, we must also say how reasons appear among the attitudes. Our initial motivations and formulations of reasons suggest two possibilities, namely Rsn ⊆ Int and Rsn ⊆ Des. (The possibility Rsn ⊆ Bel is not considered because our theories take reasons to be prescriptive, rather than merely descriptive.) Reasons act as specifications to be satisfied by states containing them, and such definite specifications might be thought of as intentions of the agent about its own construction. Taking Rsn ⊆ Int produces what we can call the ratiocinative intention theory of reasoned assumptions. In this theory, we assume that if the agent has a state at all, it has satisfied all the intentions concerning that state expressed in that state, although we do not require that in achieving that state it satisfied earlier intentions about what to do. We produce yet another theory, that of ratiocinative desires, by assuming Rsn ⊆ Des. In this theory, we interpret reasons not as definite specifications for mental states, but as preferences for states satisfying certain conditions over states not satisfying those conditions. Here we take preferences to be desires to attain one alternative in every situation presenting a specified set of alternatives. How do we take such desires to be satisfied? Consider states in which as many ratiocinative desires are satisfied as possible, that is, states in which changes that would satisfy some unsatisfied desire would result in failures to satisfy some currently satisfied desire. (Notions much like this are familiar in economics as Pareto optimality, but pursuit of this connection here would digress too far.) It turns out that these states of maximal utility are exactly the admissible states as we have defined them. We see this formally as follows.

(27.1) Definition. A set S ⊆ D is satisfaction optimal iff for each d ∈ S, if S ∉ I(d) then for each S′ ∈ I(d) there is some d′ ∈ S with S ∈ I(d′) but S′ ∉ I(d′).

(27.2) Theorem. If S is admissible, S is satisfaction optimal.

Proof. Trivially, since if S is admissible, there are no elements d ∈ S such that S ∉ I(d).

(27.3) Theorem. There is an inadmissible satisfaction optimal set.

Proof. Let D = {d, e}, S = {d}, I(d) = {S}, and I(e) = {D}. Then D is inadmissible because d ∈ D ∉ I(d). But D is satisfaction optimal since d is the only unsatisfied element in D, S is the only set in I(d), and e ∈ D, D ∈ I(e), and S ∉ I(e).

(27.4) Theorem. In the simple reasons theory, if S is satisfaction optimal, S is admissible.

Proof. We prove the contrapositive. Suppose S ⊆ D is inadmissible, that is, for some d ∈ D, d ∈ S ∉ I(d). Now by Theorem 20.1, D ∈ I(d), but for all e ∈ S, D ∈ I(e) as well, so S is not satisfaction optimal.

(27.5) Corollary. In the simple reasons theory, sets are admissible iff they are satisfaction optimal.

(27.6) Question. Can interesting parts of the general theory be developed in terms of satisfaction optimality rather than admissibility as we have defined it? Or is the simple reasons theory the weakest theory of any interest?

Another notion within the simple reasons theory similar to satisfaction optimality is validity optimality. This stems from a focus on ratiocinative desires which manage to make their objective inferences instead of on the mere satisfaction of specifications by either success or disqualification. We first recall the definition of validity.

(27.7) Definition. An element d ∈ S is valid in S iff I(d) = A \\ B ∥− C and A ⊆ S ⊆ B^{c}. Otherwise, d is invalid in S. We write V (d) to mean the set of all S ⊆ D such that d is valid in S. We write V(S) to mean the set of all d ∈ S such that d is valid in S, and V̄(S) to mean S − V(S), the set of all d invalid in S.

Note that even invalid elements can be satisfied.

(27.8) Definition. A set S is validity optimal in Ŝ ⊆ P D iff for each d ∈ D, if S′ ∈ Ŝ validates d but S does not, then there is some e valid in S but not valid in S′. Alternatively, S is validity optimal in Ŝ iff for each d ∈ S, if S ∉ V (d) then for each S′ ∈ V (d) ∩ Ŝ there is some d′ ∈ S with S ∈ V (d) but S′ ∉ V (d′).

(27.9) Corollary. If Ŝ_{1} ⊃ Ŝ_{2} and S is validity optimal in Ŝ_{1}, then S is validity optimal in Ŝ_{2}.

(27.10) Theorem. There are admissible sets not validity optimal in S̸.

Proof. Let D = {d}, and I(d) = P D. Then both ∅ and D are admissible, D validates d, but ∅ validates no element not in D, so ∅ is not validity optimal in S̸.

(27.11) Theorem. There are inadmissible sets validity optimal in P D.

Proof. Let D = {d, e}, I(d) = ∅ \\ {d} ∥− {e}, and I(e) = ∅ \\ {e} ∥− {d}. Then S̸ = {∅, D} ≠ P D, but every set in P D is validity optimal, since no set validates any element.

Our intuition is that validity optimality captures the fundamentals of the orthogonality of admissible extensions of a set, of what appears in the linguistic reasons theory as inconsistency of alternative admissible extensions of sets of normal defaults. That is, this notion shows we can sensibly speak of psychological incompatibility without requiring notions of logical inconsistency.

(27.12) Theorem. In the simple reasons theory, if S <· E, then E is validity optimal in AExts(S).

Proof. Suppose, by way of contradiction, that E ∈ AExts(S) and that there is E′ ∈ AExts(S) such that d is valid in E′ but not valid in E, yet no e valid in E is not valid in E′. That is, there is a d ∈ E′, d valid in E and either d ∉ E or d invalid in E′, and V(E) ⊆ V(E′). The element d shows E ≠ E′, so by the minimality of E and E′ among QExts(S), E − E′ ≠ ∅. Let e ∈ E − E′. Since S ⊆ E′, e ∉ S. But since E ∈ QExts(S), there must be some f ∈ E, f valid in E, and e a consequence of f. But then f is valid in E′ as well, so e ∈ E′, a contradiction. Thus E must be validity optimal in AExts(S).

(27.13) Question. If E is validity optimal in AExts(S), is E ∈ AExts(S)?

(27.14) Definition. A set S is strongly validity optimal in Ŝ ⊆ P D iff for each d ∈ D, if S′ ∈ Ŝ validates d while S invalidates d, then there is some e valid in S but invalid in S′; in other words, if V(S′) ∩ V̄(S) ≠ ∅, then V̄(S′) ∩ V(S) ≠ ∅.

(27.15) Corollary. If S is strongly validity optimal in Ŝ, then S is validity optimal in Ŝ.

(27.16) Theorem. If S <· E in a finite simple reasons agent, then E is strongly validity optimal in AExts(S).

Proof. Suppose S <· E in a finite simple reasons agent and E is not strongly validity optimal. Then there is E′ ∈ AExts(S) and d ∈ E such that d is valid in E′ but invalid in E, and if e is valid in E, then either e ∉ E′ or e is valid in E′ as well. The differing properties of d show E ≠ E′, so by the minimality of E and E′ in QExts(S), E − E′ ≠ ∅. Now E = Λ_{ω}(S, E), E′ = Λ_{ω}(S, E′), and S = Λ_{0}(S, E) = Λ_{0}(S, E′), so there is a least α ≥ 0 such that Λ_{α+1}(S, E) ≠ Λ_{α+1}(S, E′) but Λ_{α}(S, E) = Λ_{α}(S, E′). Without loss of generality, suppose e ∈ Λ_{α+1}(S, E) − Λ_{α+1}(S, E′). Then there is some f ∈ Λ_{α} with I(f) = A \\ B ∥− C, A ⊆ Λ_{α}, E ⊆ B^{c}, and e ∈ C. Since e ∉ Λ_{α+1}(S, E′), there must be some g ∈ E′ ∩ B, so f is invalid in E′. This contradicts the previous conclusion that since f is valid in E, either f ∉ E′ or f is valid in E′. Hence E must be strongly validity optimal in AExts(S).

§28. As promised, we now consider propositional attitude theories of reasoned assumptions. To do this, we simply take the linguistic reasons theory and assume among the unary predicates of its language are symbols Bel, Des, and Int. Thus the classes Bel, Des, and Int are the ground wffs of the form, respectively, Bel(·), Des(·), and Int(·). The content of these attitudes is expressed by naming formulas of the language, for instance Bel(⌈2 + 2 = 4⌉). The theories of ratiocinative intentions and desires can then be had by only allowing reasons to occur as intentions or desires, respectively, as Int(⌈A \\ B ∥− C⌉) or Des(⌈A \\ B ∥− C⌉). That is, we now count expressions of the form A \\ B ∥− C as terms rather than as formulas, so that no sentence has the form A \\ B ∥− C. To make up for this we interpret these particular sorts of intentions and desires specially, respectively by

I(Int(⌈A \\ B ∥− C⌉)) = {S ⊆ D | A ⊆ S ⊆ B^{c} ⊃ C ⊆ S}
I(Des(⌈A \\ B ∥− C⌉)) = {S ⊆ D | A ⊆ S ⊆ B^{c} ⊃ C ⊆ S}.

With these encodings, we can consider three new theories. The first is the deductively closed beliefs theory, in which we require the set of believed formulas to be closed under the deducibility relation ⊢. That is, we take

R = {S ⊆ D | S = Th(S) ∧ ∃S′ ⊆ D [S′ = Th(S′) ∧ ∀d ∈ D [d ∈ S′ ≡ Bel(⌈d⌉) ∈ S]]}.

The second theory involving propositional attitudes is the self-omniscient theory, in which we assume the agent has complete and correct beliefs about its own attitudes. That is, we take

R = {S ⊆ D | S = Th(S) ∧ ∀d ∈ D [d ∈ S ≡ Bel(⌈d⌉) ∈ S ∧ d ∉ S ≡ ¬Bel(⌈d⌉) ∈ S]}.

Naturally, if S ∈ R is nonempty, it is infinite, containing reflection upon reflection of its own contents.

The third theory involving propositional attitudes combines these two into the deductively selfomniscient theory. Unfortunately, if ⊢ is the ordinary deducibility relation of logic, the theory is inconsistent, that is, there are no agents whose states satisfy all these requirements. Proving this here would digress too far from our main concerns. Montague proves it in some generality, and Thomason discusses its significance for attempts to define notions of “semantic competence” of agents, notions corresponding to those of “grammatical competence” common in linguistics.^{15}

15[Montague 1963], [Thomason 1979]

Evolutionary theories

§29. Our initial discussion of problems of acting with incomplete information focussed on adopting and abandoning assumptions, but the preceding sections made little mention of such activities. Rather, the task was to set out the admissible states of the agent, so that actions in which the agent changes its state may be better understood. With a wide assortment of structures for states now available, we return to the question of state changes and actions.

The notion of reasoned assumptions was developed to treat reasoned adoption and reasoned abandonment of assumptions. In reasoned adoption of assumptions, the agent acts to adopt a new assumption by adding a reason to its state whose conclusion is the new assumption and whose antecedents and qualifiers may indicate the considerations involved in the decision to adopt the assumption. But just adding a reason to an admissible state will not in general yield another admissible state, so we must find some other way of effecting the change. To do this, we interpret the new reason as the agent’s partial specification of its next state. We may not wish to accept just any new state satisfying the reason, for such might abandon all of the previous state. If not, we can employ the idea of conservation and require that the new state should be an admissible state satisfying the new specification, one as “close” as possible to the previous state. Similarly, in reasoned abandonment of assumptions, the agent acts to rid itself of some unwanted assumption. This can be done either by removing from the state the reason supporting the assumption, or by adding to the state a new reason which defeats the assumption. But as before, the removal of a reason from an admissible state may not yield another admissible state, so we again may employ conservation in moving to a new admissible state which satisfies the new reason.

However useful might be reasoned adoption and abandonment of assumptions, one cannot always escape the need for forced or unreasoned adoption and abandonment of state components. The notion of forced adoption of state components might be used as a very crude way of viewing some effects of non-mental parts of a human on its state of mind, for example changes made by the perceptual and motor systems. Other effects, such as physiological changes in the body which affect the nervous system, seem ill-suited to this view, and require some other means of formulation, conceivably that of state-dependent interpretations, although I suspect other ideas are necessary as well. We do not explicitly treat forced adoption or abandonment of assumptions in this paper. On the other hand, forced changes of assumptions have a long history in artificial intelligence as the technique of backtracking, and we give a straightforward treatment of them later.

§30. Let (D, I, S̸, J , <·) describe an agent and let E be a set of “environments.” We suppose the basis for the agent’s state changes to be described by a “kernel” transition function ∂ : S̸ × E → P D which for each admissible state and environment yields the (partial) specifications for the next state. The role of this kernel as specifications for the next state is ensured by requiring the next state to be an extension of the kernel, since extensions of a set satisfy all the specifications represented by that set. In fact, we require Δ(S, e), the admissible transitions from S in e, to lie among the admissible extensions of the kernel, that is, Δ(S, e) ⊆ AExts(∂(S, e)). As with the notions of admissible states and admissible extensions, we capture different agents by stipulating Δ as different restrictions of AExts ∘ ∂. However, while the earlier sorts of restrictions separated into local and global restrictions, here we only treat global restrictions on transitions, as formalization of interesting local restrictions involves other notions beyond the scope of this paper.

§31. Of possible sorts of global restrictions on admissible transitions, three occupy our attention in the following: those of strictness, of conservatism, and of their combination, strict conservatism. In spite of such labels, these notions have nothing to do with New Englanders.

Strictness we have seen previously in the form of strict arguability. In a strict agent, Δ = μAExts ∘∂. As usual, this is just AExts ∘∂ if the previous theories are used to supply AExts, since in those μAExts = AExts. Strictness requires that successor states stay as close as possible to the specifications of the kernel, giving up any part of the previous state not derivable from the kernel alone. This sort of agent captures the operation of RMS quite well, as explained in §46, in which the agent maintains a set of fundamental or kernel reasons, and regularly reconstructs the complete state when this kernel is modified by additions or emendations.

Where strictness requires successor states to be as close as possible to the kernel specifications, conservatism requires successor states to approximate their predecessors as closely as possible. Of course, different notions of approximation are of interest in different circumstances, so we require only certain abstract properties of approximation comparisons to define conservatism. We express approximation comparisons in terms of a relation ⪯ on transitions, a quasi-order whose minimal elements include the null transitions. That is, we read (S_{1}, S_{2}) ⪯ (S_{3}, S_{4}) as saying that the transition from S_{1} to S_{2} is not larger than the transition from S_{3} to S_{4}, and insist ⪯ be reflexive, transitive, and order no transition properly smaller than a null transition. Formally, ⪯ is a relation on (S̸ × S̸) × (S̸ × S̸) such that for all admissible states,

(i) (S, S′) ⪯ (S, S′),
(ii) If (S_{1}, S′_{1}) ⪯ (S_{2}, S′_{2}) and (S_{2}, S′_{2}) ⪯ (S_{3}, S′_{3}), then (S_{1}, S′_{1}) ⪯ (S_{3}, S′_{3}),
(iii) (S, S) ⪯ (S, S′),
(iv) (S′, S′) ⪯ (S, S′).

We define the admissible transitions of conservative agents in terms of ⪯-minimal transitions. In analogy with μ, we use the operator ν (“nearest”) to indicate transition minimization. If S ∈ S̸ and X ⊆ S̸, we define

ν(S, X) = {x ∈ X | ∀y ∈ X (S, y) ⪯ (S, x) ⊃(S, x) ⪯ (S, y)},

and abuse the notation by writing νf as shorthand for λS.ν(S, f(S)), so that Δ = νAExts ∘ ∂ means that Δ(S, e) = ν(S, AExts(∂(S, e))) for each S ∈ S̸ and e ∈ E. As with μ, ν(S, X) = ∅ if X = ∅, so ν(S, AExts(∂(S, e))) = ∅ if AExts(∂(S, e)) = ∅.

Several comments on this definition are in order. First, we only require ⪯ to be a quasi-order rather than a partial order. That is, we do not stipulate antisymmetry, so that x ⪯ y and y ⪯ x need not imply x = y. This is made clear in the examples to follow. Second, as in partial orders, it can happen that both x ⪯̸ y and y ⪯̸ x. In our usage, if AExts(∂(S, e)) contains two incomparable states but no common smaller state, then Δ(S, e) will contain both states, and the system (S̸, E, Δ) will be nondeterministic. This too is illustrated below. Third, minimal mutilation has been formalized in the philosophical study of counterfactual conditionals using the notion of comparative similarity relations on states.^{16} Here we note only that every order ⪯ on transitions induces a (not necessarily interesting) comparative similarity relation on S̸, and vice versa. Read X {≺ \atop Z} Y as “X is as close to Z as is Y.” The connection between these relations then obtains by defining

(S_{1}, S_{2}) ⪯ (S_{3}, S_{4}) iff S_{1} = S_{3} and S_{2} {≺ \atop S_{1}} S_{4} or S_{2} = S_{4} and S_{1} {≺ \atop S_{2}} S_{3}.

Conservative agents need not pass along sets of fundamental reasons in ∂, but can instead simply specify changes and let the ⪯-minimization conserve as much of the previous state as possible. In agents whose admissible extensions are not strict, for example locally grounded agents (AExts = QExts), this can lead to retention of mutually supportive but ungrounded complexes of elements in the successor state. Indeed, many discussions of belief revision in the philosophical literature propose versions of conservative agents, as do proponents of the deductivist approach to artificial intelligence. In this approach, D is the set of sentences of a first-order logical language, S̸ is the set of all deductively closed and consistent sets of sentences, and admissible extensions are just minimal extensions (and so just deductive closures if consistent), that is, AExts = μExts. Here ∂ produces “inputs” to or observations by the agent, new sentences possibly contradicting current beliefs, and Δ moves the agent to some extension of ∂(S, e) as close as possible (by some measure) to S, for example, to Th(A ∪ ∂(S, e)) for some maximal subset A of S consistent with ∂(S, e).

16See [Lewis 1973], [Turner 1981].

Finally, one can combine the notions of strictness and conservatism into strict conservatism. Here we define the admissible transitions by Δ = νμAExts ∘∂. This sort of agent moves to admissible extensions of the kernel which first are closest to the kernel, and second are closest to the preceding state.

Each of these sorts of agents calls for study, as they may be appropriate for different applications. Systems doing more or less thorough analysis of domains small in comparison to the whole world (such as electronic circuit analysis and other expert tasks) might always require strictness, or better yet, strict conservatism. Systems whose focus ranges over the whole world (general agents and natural language users) probably have too many uncertain interrelated assumptions to think of any subset as “the axioms,” and so must settle for simple conservatism in spite of the logical faux pas this sometimes entails in those special cases in which the axioms are distinguished. These restrictions might be combined in other ways as well. Artificial intelligence systems often divide into many small subsystems. One might organize the agent so that each small subsystem is strictly conservative, while the large collection as a whole is merely conservative.

§32. Let us look at an example of a strictly conservative agent. For simplicity, we assume E = {e} and omit all mention of this constant environment. We begin with an agent described by the simple reasons theory, and want some notion of relative size of transitions. Since states are sets of state components, perhaps the simplest indication of the amount of change involved in going from state S_{1} to state S_{2} is the symmetric difference S_{1} △ S_{2} = (S_{1} − S_{2}) ∪ (S_{2} − S_{1}) = (S_{1} ∪ S_{2}) − (S_{1} ∩ S_{2}). The set S_{1} − S_{2} reveals how much of the initial state is lost in the new state, and the set S_{2} − S_{1}, shows how much of the new state is gained relative to the old. Together these sets indicate the degree of conservation (or lack of it) involved in the change. Thus one way of comparing two transitions is to define (S_{1}, S_{2}) ⪯ (S_{3}, S_{4}) iff S_{1} △ S_{2} ⊆ S_{3} △ S_{4}. Since the symmetric difference of any set with itself is empty, and since ⊆ is a quasi-order on sets with ∅ as its minimum element, this definition yields the required properties of ⪯.

Now suppose the agent starts in the empty state S_{0} = ∅ and ∂(S_{0}) = {∅ \\ A ∥− B, ∅ \\ C ∥− D}. Properly speaking, of course, this is I^{∗}(∂(S_{0})), but we drop the interpretation notation without confusion here. ∂(S_{0}) has a single admissible extension, so S_{1} = ∂(S_{0}) ∪ B ∪ D, the conservation condition being satisfied trivially. Suppose next that ∂(S_{1}) = ∂(S_{0}) ∪ {∅ \\ B ∥− A, ∅ \\ D ∥− C}. By itself, this kernel is very ambiguous, with the four admissible extensions ∂(S_{1})+A∪C, A∪D, B ∪C, B ∪D. But of these, one is closest to S_{1}, namely S_{2} = ∂(S_{1})∪B ∪D. Next, suppose ∂(S_{2}) = ∂(S_{1})∪{∅ \\ E ∥− C}. Now the kernel has only two admissible extensions, namely ∂(S_{2})+A∪C, B∪C. But of these, again one is closer to S_{2} than the other, so S_{3} = ∂(S_{2})∪B ∪C. Finally, suppose ∂(S_{3}) = ∂(S_{2})∪{∅ \\ F ∥− G, ∅ \\ G ∥− F }. There are now again four admissible extensions of the kernel, ∂(S_{3})+A∪C ∪F, A∪C ∪G, B ∪C ∪F, B ∪C ∪G, and of these, two are incomparable nearest neighbors of S_{3}, namely ∂(S_{3}) ∪ B ∪ C ∪ F and ∂(S_{3}) ∪ B ∪ C ∪ G. Thus Δ(S_{3}) contains both of these states.

If this agent were merely strict, rather than strictly conservative, the admissible transitions would be different. For instance, S_{1} would remain the same, since it is the only admissible extension of ∂(S_{0}), but S_{2} could be any of the four admissible extensions of ∂(S_{1}), since the transition is not required to be ⪯-minimal.

To exhibit the difference between conservative and strictly conservative agents, suppose that S = {a, b, c, d, e}, where I(a) = {c} \\ ∅ ∥− {d}, I(b) = {d} \\ ∅ ∥− {c}, I(c) = I(d) = ∅ \\ ∅ ∥− ∅, and I(e) = ∅ \\ ∅ ∥− {c}. According to the simple reasons theory, S is admissible, and is an admissible extension of its subset {a, b, e}. Now suppose ∂(S) = {a, b}. This has two component-admissible extensions in S, namely {a, b} and {a, b, c, d}. Since the former is grounded, it is the only admissible extension of ∂(S) in the strict simple reasons theory. However, the latter extension is closer to S, and so would be chosen by the symmetric difference relation if admissible extensions were not required to be grounded.

Besides this notion of closeness based on symmetric difference, there are many others that are more appropriate in other circumstances. For example, one might define one transition smaller than another if the components conserved in the first include those conserved in the second, that is (S_{1}, S_{2}) ⪯ (S_{3}, S_{4}) iff S_{1} ∩S_{2} ⊃ S_{3} ∩S_{4}. Or instead of considering sets, one might use their cardinalities, as in (S_{1}, S_{2}) ⪯ (S_{3}, S_{4}) iff |S_{1} △ S_{2}| ≤ |S_{3} △ S_{4}|. There are many other possibilities for closeness relations based on tolerances, topologies, metrics, and measures, but we cannot treat these here.^{17}

§33. Let us summarize the discussion.

(33.1) Definition. Plain, strict, conservative, and strictly conservative agents are characterized by (D, I, S̸, J , <·) as before, together with a set of environments E, a kernel transition function ∂ : S̸ × E → P D, and an admissible transition table Δ : S̸ × E → P S̸ such that for each S ∈ S̸ and e ∈ E, Δ(S, e) ⊆ AExts(∂(S, e)). In a plain agent, Δ = AExts ∘ ∂; in a strict agent, Δ = μAExts ∘ ∂; in a conservative agent, Δ = νAExts ∘∂, where ν is minimization with respect to a quasi-order ⪯ on transitions whose minima include the null transitions; and in a strictly conservative agent, Δ = νμAExts ∘ ∂.

(33.2) Corollary. If AExts = μAExts, plain agents are strict, and conservative agents are strictly conservative.

(33.3) Question. Are there interesting cases in which strictness and conservation interact, for example (1) S ⊆ S′, S′′ and (S, S′) ⪯ (S, S′′) implies S′ ⊆ S′′, or (2) S ⊆ S′, S′′ and S′ ⊆ S′′ implies (S, S′) ⪯ (S, S′′)? What can be concluded about monotone kernel agents, that is, agents in which ∂(S_{t}, e_{t}) ⊆ ∂(S_{t+1}, e_{t+1}) at every successive step (as suggested in the monotone embedding theorem)?

The question of computational complexity is particularly vexing, for while much work has been done on practical systems that seem to revise simple reasons states in acceptable times, the precise actions and costs of these algorithms are not yet known.^{18} The principal practical difficulty to be investigated is whether the two sorts of minimization can be efficiently mechanized separately and in combination. RMS and its relatives operate as finitely grounded, hence strict, agents, and they attempt to approximate conservation. On the other hand, the strictness of RMS was in part a reaction to earlier, more purely conservative systems which did not observe the prudence of strict inference needed in some axiomatic systems, so it may be that conservative agents are efficiently mechanizable as well. I suspect that some strictly conservative agents have acceptably efficient mechanizations, but I have no algorithms or proofs to offer.

In general, however, it appears that strict conservatism may be more difficult to realize than either strictness or conservatism separately. Let us again suppose the agent finite, that (S_{1}, S_{2}) ⪯ (S_{3}, S_{4}) is deterministically computable in time polynomial in the sizes of the states involved, as is the case for the symmetric difference comparison. We again assume and ignore a constant environment, and suppose that ∂(S) is deterministically computable in time polynomial in the size of S.

(33.4) Theorem. If (S̸, Δ) is a plain simple reasons agent, then Is E ∈ Δ(S)? is in P.

Proof. First compute ∂(S), and check, as before, E ∈ QExts(∂(S)) or E ∈ FGExts(∂(S)), depending on whether the agent is locally grounded or finitely grounded. Each of these steps is in P, so their combinations are also.

17See [Quine 1953], [Rescher 1964], and [Gärdenfors 1980].

18See [Doyle 1979], [Stallman and Sussman 1977], [London 1978], [McAllester 1980], [Charniak, Riesbeck, and McDermott 1980], [Thompson 1979], [Martins 1983], [Goodwin 1982], and [McDermott 1982b].

(33.5) Theorem. If (S̸, Δ) is a strict finitely grounded simple reasons agent, then Is E ∈ Δ(S)? is in P.

Proof. Since μFGExts = FGExts, the previous theorem applies.

(33.6) Theorem. If (S̸, Δ) is a strict locally grounded simple reasons agent, then Is E ∈ Δ(S)? is in co-NP.

Proof. This is just the question Is E ∈ μQExts(∂(S))? Since ∂ is in P, by Theorem 18.65 these strict extensions are in co-NP.

(33.7) Theorem. If (S̸, Δ) is a conservative simple reasons agent, then Is E ∈ Δ(S)? is in co-NP.

Proof. We see Is E ∉ Δ(S)? is in NP for locally (resp. finitely) grounded agents as follows. First compute ∂(S), and accept if E ∉ QExts(∂(S)) (resp. E ∉ FGExts(∂(S))). If E ∈ QExts(∂(S)) (resp. E ∈ FGExts(∂(S))), pick E′ ∈ QExts(∂(S)) (resp. E′ ∈ FGExts(∂(S))) and accept if (S, E′) ⪯ (S, E) but (S, E) ⪯̸ (S, E′).

(33.8) Theorem. If (S̸, Δ) is a strictly conservative finitely grounded simple reason agent, then Is E ∈ Δ(S)? is in co-NP.

Proof. Since μFGExts = FGExts, the previous theorem applies.

(33.9) Theorem. If (S̸, Δ) is a strictly conservative locally grounded simple reasons agent, then Is E ∈ Δ(S)? is in Π_{2}^{p}.

Proof. By putting the previous proofs together, we see that E ∉ ν(S, μQExts(∂(S))) is in NP given verifications, each co-NP, of E ∈ μQExts(∂(S)).

(33.10) Conjecture. If (S̸, Δ) is a conservative simple reasons agent, then Is E ∈ Δ(S)? is NPhard.

(33.11) Question. Are there interesting conservation notions which are efficiently and incrementally computable? That is, if symmetric difference conservation means intractability, are there less stringent notions which admit good algorithms? Is the “standard reason enumeration” technique employed in RMS a good approximation to symmetric difference?

Also deserving attention are special cases of these agents and approximate algorithms. Most practical systems, for example, base their claims of efficiency by requiring that only coherent sets are manipulated. I have grown increasingly suspicious of such restrictions of attention, but the question deserves proper treatment. Even if the complexity of strictly conservative agents is demonstrably intractable, there may still be approximate algorithms of reasonable efficiency. Since the whole practice of reasoned assumption-making is based on correcting errors, we can afford in practice to be tolerant of occasional imprudences in jumping to conclusions. Unfortunately, one cannot hope to measure degrees of approximate correctness in terms of the number of poor assumptions in a state, since just one mistakenly included assumption can have arbitrarily many uncontroversial but mistaken consequences. Instead, one must look to the relative frequencies of correctly to incorrectly computed extensions among the entire set of such computations, that is, one must treat the question of approximation as a question about probabilistic algorithms.

Not only have complexity questions remained unstudied, but even the appropriate complexity measures still require proper formulation. The usual measures of time and space on a RASP are of course important, but so are some specific natural measures. One can ask how many state components are reconsidered or examined in the transition process. This is simply expressed in terms of the sum of the sizes of the mention sets of all elements against which the state is checked. When reasons are represented as graph structures, as in existing mechanizations, this measure corresponds to the number of edges traversed by the algorithm. In addition to average and worst-case measures, the complexity relative to the number of elements changed also holds interest. Folklore has it that any algorithm must be arbitrarily bad with respect to this measure, in that one can choose transitions requiring unbounded numbers of element reappraisals, but which lead to only a bounded number of changes.

§34. We now turn from individual transitions to the global perspective of trajectory spaces. The trajectories of an agent are finite or infinite sequences of admissible states that observe the transition table; formally, sequences ⟨S_{i}⟩_{i=0}^{n} (n ≤ ω) such that S_{i} ∈ S̸ if 0 ≤ i ≤ n, and if i + 1 ≤ n, then S_{i+1} ∈ Δ(S_{i}, e) for some e ∈ E. The trajectory space T (S̸, E, Δ) is the set of all trajectories of the agent (S̸, E, Δ). This for simplicity assumes the world obeys no laws other than the agent’s transition table. In the general case, we must consider the agent as part of an isolated system, with the world having admissible states S̸_{W} ⊆ S̸ × E, and a given trajectory space T_{W} ⊆ (S̸_{W}^{∗}). In this case, the agent’s trajectory space will be the projection of T_{W} onto S̸^{∗}, onto a subset of T (S̸, E, Δ). We employ the notation T; T′ to mean concatenation of two trajectories, so that if T = ⟨S_{0}, …, S_{m}⟩ and T′ = ⟨S′_{0}, …, S′_{n}⟩, then T; T′ = ⟨S_{0}, …, S_{m}, S′_{0}, …, S′_{n}⟩. Of course, T need not be closed under concatenation. If S ∈ S̸, we write S; T and T; S to mean, respectively, ⟨S⟩; T and T; ⟨S⟩.

Many standard questions about dynamical systems arise here, such as reachability, the existence of trajectories connecting two states; the existence of limit sets or attractors to which all trajectories from some neighborhood eventually lead; the existence of cycles (closed trajectories); the existence of limit cycles; stability of limits; the complexity of computations; and more. At the moment, results are lacking concerning most of these questions, so we cannot treat them further here. But these questions call out for study, since some of them are intimately tied up with familiar psychological questions. For example, if one’s trajectories are defined by some sort of learning or searching procedure, then the existence and reachability of limit sets corresponds to the learnability of certain concepts or skills, or to the solvability of certain goals. This is all familiar from popular treatments of hill-climbing, where the learning or searching procedure is a gradient vector field on the state space. Furthermore, the complexity or length of trajectories to these limits might shed light on power laws or laws of diminishing returns, since diminishing returns indicate the existence of limit states unreachable by finite trajectories, and power laws are just particular shapes for curves of diminishing returns. The structure of trajectory space T (S̸, E, Δ) is also closely connected with the structure of the state space S̸, since many of the questions previously addressed about assumability and realizability can be cast directly as questions about reachability by monotone kernel trajectories. Trajectory space also serves as a model for various modal or temporal logics concerned with the evolution of properties of elements or states (arguability, coherence, etc.). We must forgo discussion of most of these topics. In the following, we treat only two of the topics connected with the global viewpoint: the connections between catastrophes and backtracking, and the construction of “subjective probabilities” from trajectory space.

§35. The preceding development has focussed on reasoned changes of state, in which the agent decides what shape its next state should take, specifies those qualities via ∂, and then solves the specifications in one way or other to move to a new state in Δ. But unless we ensure that all transition specifications have admissible solutions, it can happen that there are no potential successors in Δ. The incoherence of ∂(S, e) may be accidental, or it may be deliberate. For example, if ∂ includes a contradiction in the specifications for the next state after S, it ensures Δ(S, e) = ∅. In this use, the contradiction acts as an admission that “I can’t go on like this!” But how should we take such accidents and admissions? As natural death and suicide? While those are possibilities, another is to take these incompetences of Δ as occasions for other sorts of state changes. We treat the former possibilities elsewhere, and pursue the latter here. We add to our store of constitutive assumptions for characterizing agents by introducing the extended transition table E : T (S̸, E, Δ) × E → P S̸, which we require to agree with Δ whenever Δ is nonsingular, that is, for every trajectory T ∈ T (S̸, E, Δ), if T = T′; S and Δ(S, e) ≠ ∅, then E(T, e) = Δ(S, e) . With this new constitutive assumption, agents are characterized by choices of (D, I, S̸, J , <· , E, ∂, Δ, E).

The most trivial choices for E are E(T; S, e) = Δ(S, e), in which case T (S̸, E, E) = T (S̸, E, Δ) and there is not much to say, and E(T; S, e) = S̸ if Δ(S, e) = ∅, in which case the agent executes a random walk through trajectory space when it is not following Δ. Some more interesting choices for E involve the traditional notion of backtracking. Backtracking originated as a means for outwitting pursuers. One travelled leaving an obvious trail until a stream or other natural trail-obscuring obstacle was reached. One then carefully walked backwards over the path just travelled, placing feet in the footsteps just left, until one reached a point at which one could take off in a new direction, leaving the actual trail chosen to be unobvious when compared with the false trail. This technique was adopted in artificial intelligence to elude the hounds of failure, by keeping track of the choice points encountered during a search of a space, and upon failure of one search path, resuming the search with one of the alternate paths indicated in the choice points. We reproduce this idea formally as follows, where we for simplicity assume an isolated agent. Let T = ⟨S_{i}⟩_{i=0}^{n} (n ≤ ω) represent the trajectory of the agent, where S_{i} is the state at instant i. We define Alt(T, i+1), the alternatives in T at instant i+1, by Alt(T, i+1) = Δ(S_{i})−{S_{i+1}} if Δ(S_{i}) ≠ ∅. These then are the states that could have been pursued but were not. We get two backtracking regimes by assuming the agent falls back to any or the closest alternative state when necessary, that is, by defining E(T; S) to be Δ(S) whenever Δ(S) ≠ ∅, and to be Alt(T, k) or νAlt(T, k) otherwise, where k = max{j < i | Alt(T, j) ≠ ∅}. Call these chronological backtracking and conservative chronological backtracking. Conservative non-chronological backtracking (also known as “dependency directed” backtracking) arises by taking E(T; S) at singular points to be ν ⋃_{j<i} Alt(T, j). These definitions are simpler than those commonly employed since they do not remove explored paths from the set of alternatives.

To return to the example of §32, suppose S_{4} = ∂(S_{3}) ∪ B ∪ C ∪ F. We then have Alt(⟨S_{0}, S_{1}⟩) = Alt(⟨S_{0}, S_{1}, S_{2}⟩) = Alt(⟨S_{0}, S_{1}, S_{2}, S_{3}⟩) = ∅ and Alt(⟨S_{0}, S_{1}, S_{2}, S_{3}, S_{4}⟩) = ∂(S_{3}) ∪ B ∪ C ∪ G.

§36. One way of understanding the nature of backtracking is in terms of the notion of catastrophe. (The following remarks are more suggesive than substantive at present. I hope to justify them rigorously elsewhere.) For our purposes here, a catastrophe is a “discontinuous” jump in a trajectory. Each time Δ is multi-valued, we have the possibility of trajectory space branching into two “sheets.” Actually, not all multi-valued occurrences of Δ need produce bifurcations in trajectory space if the alternatives are all reachable from each other by ordinary trajectories. But a “true” bifurcation is introduced if the resulting states are mutually unreachable in T (S̸, E, Δ). If an ordinary trajectory comes up to the edge of one of these sheets, the only way to proceed is by means of a jump to a state on another sheet, a “discontinous” change in the sense that the ordinary transition table provides no direction, which one might interpret as lack of a “derivative” with which the agent might predict its possible actions. There are many ways of embedding the ordinary trajectory space in larger spaces that have no discontinuities, and we have seen a few of these in the extended transition table E. If the agent is conservative, it might jump to one of the closest points on the other sheets. Alternatively, it might jump to a point corresponding to an alternative future, a point at the same time but on a different sheet among those bypassed along the actual trajectory. One might call this “sidetracking” instead of “backtracking.” In any event, rules for continuing all trajectories beyond singularities have the effect of pasting all the edges in trajectory space back into the space. This results in a complex shape for the enlarged trajectory space, just as pasting all the edges of a sheet of paper together in the right way produces a sphere, a torus, or a Klein bottle, surfaces with no edges.

The most important quality of a catastrophe in a psychology is that, from the agent’s point of view, it “just happens.” While we may design agents to suffer catastrophes in certain ways, the actions involving the agent’s own deliberation and choice are all captured by ∂ and Δ, and changes not involving those are beyond its powers. Of course, an agent may deliberately place itself in a position where, it knows, a catastrophe is inevitable, so as to chance some action not normally doable, just as one might lead one’s self into the depths of despair, thinking that either death or a jump to some redeeming faith are the only possible paths, in spite of calm inability to believe. This difference in the quality of these sorts of actions has never admitted clear articulation in artificial intelligence before. In my own work on RMS, I always thought that the two processes of reason maintenance and backtracking were different, but could not say why. McAllester developed ways of mechanizing them with a uniform procedure, and I thought that wrong. Instead, I was wrong, in that however one best mechanizes the two processes, by two mechanisms or by one, the processes still are different as far as the agent is concerned. Before, I had no clear way of distinguishing the agent and its actions from its realization and the changes that happen to it. The distinction between these processes lies in the former realm, McAllester’s unification in the latter.

Probabilistic theories

§37. With exact characterizations of theories of reasoned assumptions and their revision, we can connect artificial intelligence treatments of uncertainty with standard probabilistic treatments. These connections divide into two parts, one static, one dynamic. Just as theories of reasoned assumptions divide into characterizations of the set of admissible states and characterization of the temporal evolution of the agent’s state, probabilistic theories divide into characterizations of particular states as probability distributions and characterization of the effects of actions as the evolution of the agent’s probability distribution. We treat both parts below.

Drawing theoretical connections between these two approaches to uncertainty is not simply an abstract mathematical exercise. Instead, these connections yield two valuable benefits. The first benefit is the possibility of justifying the claimed methodological superiority of the artificial intelligence treatment over standard probabilistic treatments. Several authors in artificial intelligence have explained their abandoning probability theory in terms of the unpleasantly large amounts of information and computation required to apply the probabilistic theories.^{19} With exact connections between the formal theories, we can begin to justify (or refute) these intuitions rigorously with the methods of computational complexity. The second benefit is that probability theory, whatever its computational disadvantages, offers certain sorts of information often useful but not present in the preceding theories of reasoned assumptions. In particular, probability theory allows one to summarize one’s uncertainty about some question with a simple description, a number, and to compare degrees of uncertainty by comparing these numbers. The exact connection between the two theories permits us to recover degrees of certainty when desired even if we base the structure and action of systems on reasoned assumptions.

§38. The basic idea underlying the connection between reasoned assumptions and degrees of certainty is to make the degree of certainty of some state component e with respect to a set S of reasons depend on how e appears in admissible extensions of S. There is no distinguished way of defining this dependence, but instead a variety of possible measures. For example, one might ask how likely is e to occur in a randomly selected admissible extension, or how many arguments there are for e, or how many assumptions e depends on, etc. Each of these captures different intuitions about the meaning of “degree of certainty,” and may be preferred in different circumstances.

These measures may be motivated in two ways. In the first, we view the nondeterministic theories of reasoned assumptions presented earlier as incomplete specifications of deterministic agents, whose indeterminism we interpret probabilistically in terms of how likely our incomplete specifications are to predict the actual behavior among the predicted possible behaviors. Alternatively, we can treat these measures as specifications for probabilistic algorithms.^{20} The problem of acting prudently is too difficult or even impossible to solve exactly, so the agent makes a series of random choices (of admissible assumptions rather than numbers) and then decides what to do by exact means. These random choices may lead to error, so the task of the agent is to constrain the range of possible sets of choices (by using ratiocinative rules of thumb) so that the expected probability of success is high. This latter view seems well-suited to the mechanization of artificial agents.

§39. Perhaps the simplest way of measuring how the agent holds some state component is to assign a weight to each state the agent might be in, a weight representing how likely the agent is to be in that state, and then to sum the weights of all states containing the element. That is, if w(S) is the weight of state S, then the measure of how e occurs in Ŝ ⊆ S̸ is just

19See [Szolovits 1978], [Doyle 1983b], and the discussion below.

20[Rabin 1976]

∑_{S∈Ŝ} w(S).

Weight functions like this are ordinarily expressed as measure functions on sets of states, as non-negative, additive functions m : P S̸ → R, where w(S) = m({S}). Nonnegative, as usual means that m(Ŝ) ≥ 0 for every Ŝ ⊆ S̸, and additive means that for every Ŝ, Ŝ′ ⊆ S̸, we have m(Ŝ∪Ŝ′) = m(Ŝ)+m(Ŝ′)−m(Ŝ∩Ŝ′). Actually, technical complications make this definition adequate only for the case of finite S̸, but that is enough for most of our purposes. Later we comment on interesting cases of infinite S̸.

For example, one natural measure function is the counting measure m† that gives every state equal weight, i.e. m†(Ŝ) = |Ŝ|. This measure corresponds to making Laplace’s assumption, that every possible state of the agent is equally likely to occur. With this measure, the degree of certainty of a state component in a set of admissible extensions is just the percentage of them in which it appears.

Another natural measure function is the specificity measure m^{∗} that weights states by how “specific” they are, namely m^{∗}({S}) = 2^{−|S|}. One way of looking at this measure is to think of states as partial descriptions of all the sets of components extending them, and to weight states proportionally to the number of possible supersets. From this point of view, we would define m^{∗}′({S}) = 2^{|D|−|S|}. This, of course, simply multiplies all of the specificity weights by the constant 2^{|D|}, and so changes none of the comparative relations between weights of states.

Yet another measure function is the selection measure m^{!} that weights states as selections of

elements from the domain, namely m^{!}(\{S\}) = \binom{|D|}{|S|}^{−1}. We make no important use of this measure in the following.

§40. For each theory of reasoned assumptions and measure function m, we define the “degree of certainty.”

(40.1) Definition. Let Ŝ \ A = {S ∈ Ŝ | A ⊆ S} for Ŝ ⊆ S̸. Then the extent E(A, S) of a set A ⊆ D relative to a set S ⊆ D is given by

E(A, S) = m(AExts(S) \ A)/m(AExts(S)),

where E(A, S) = 1 whenever AExts(S) = 0.

Thus the extent of a state component e is just the relative measure E({e}, S) of those admissible extensions containing e.

(40.2) Corollary. If A ⊆ D is not arguable in S, then E(A, S) = 0, and if A is inevitable in S, then E(A, S) = 1.

(40.3) Definition. If S is coherent, d, e ∈ D, and E({d}, S) > 0, then CE(e | d, S), the conditional extent of e given d in S, is

CE(e | d, S) = E({d, e}, S)/E({d}, S)
= m(AExts(S) \ {d, e})/m(AExts(S) \ {d}).

I am not sure what approach to take for incoherent S. If S is coherent but E({d}, S) = 0, the situation here has analogies to the situation in Bayesian probability theory that motivates so-called Popper functions, but I leave treatment of that case to future studies as well.

(40.4) Theorem (Bayes). If {d_{i}}_{i=0}^{n} is a subset of D such that exactly one d_{i} occurs in every admissible extension of S, then

CE(d_{i} | e, S) = \frac{CE(e | d_{i}, S) · E(\{d_{i}\}, S)}{∑_{j=0}^{n} CE(e | d_{j}, S) · E(\{d_{j}\}, S)}.

(40.5) Corollary. If at most one d_{i} occurs in every admissible extension of S, then

CE(d_{i} | e, S) ≤ \frac{CE(e | d_{i}, S) · E(\{d_{i}\}, S)}{∑_{j=0}^{n} CE(e | d_{j}, S) · E(\{d_{j}\}, S)}.

Linguistic reasons agents are of special interest here, for their formulation involves many of the same assumptions as does subjective Bayesian decision theory. Because state components have logical form in this theory, we can examine the relations between extents of components with related forms.

(40.6) Theorem. Let S ⊆ D. Then (i) If S is not inevitably consistent, then for each x ∈ D, E(x, S) = 1, (ii) S is inevitably consistent iff for each x ∈ D, E(x, S) + E(¬x, S) ≤ 1, (iii) For each x, y ∈ D, E(x ∧ y, S) ≤ E(x, S) + E(y, S), (iv) For each x, y ∈ D, if x ⊃ y is inevitable, then E(x, S) ≤ E(y, S), and (v) If S ≠ {D}, then for each x, y ∈ D, E(x, S) ≥ E(x ∧ y, S) + E(x ∧ ¬y, S).

Proof. Let S ⊆ D and Ŝ = AExts(S). (i) If S is incoherent, then E(x, S) = 1 by definition, and if S is inevitably inconsistent, Ŝ = {D}, so again E(x, S) = 1 for every x ∈ D. (ii) follows immediately from this last observation. (iii) Since {x ∧ y} is interdeducible with {x, y}, Ŝ \ {x ∧ y} ⊆ Ŝ \ {x} ∪ Ŝ \ {y}. (iv) If Ŝ = ∅, the claim follows trivially. If Ŝ ≠ ∅, then Ŝ \ {x} ⊆ Ŝ \ {y} since {x, x ⊃ y} ⊢ {y}. (v) If Ŝ ≠ {D} then each S ∈ Ŝ is consistent. Since {x, z} and {x ∧ z} are interdeducible, we must have Ŝ \ {x, y} ∩ Ŝ \ {x, ¬y} = ∅. Since Ŝ ≠ ∅, the claim follows.

Since arguability is different from assumability, we introduce a parallel notion to conditional extents, namely a posteriori extents.

(40.7) Definition. Let d, e ∈ D and S ⊆ D. If S ∪ {e} is coherent, then AE(d | e, S), the a posteriori extent of d given e in Ŝ, is

AE(d | e, S) = E({d}, S ∪ {e}).

Unfortunately, I do not know how to treat the case of incoherent S ∪ {e}. There also seems to be no general way to relate conditional and a posteriori extents. This weakness of the theory is to be expected from the complexity of the ways in which the sets of admissible extensions may change under the addition of new information. Stronger theories may be possible for restricted sorts of agents, but by and large these are unexplored.

§41. Let us examine some examples to see how these measures differ. We work within a simple reasons agent with D = {c_{1}, ¬c_{1}, c_{2}, ¬c_{2}, r_{1}, r_{2}, r_{3}, r_{4}, r_{5}, r_{6}}, where I(c_{1}) = I(¬c_{1}) = I(c_{2}) = I(¬c_{2}) = P D, and where I(r_{1}) = ∅ \\ {¬c_{1}} ∥− {c_{1}}, I(r_{2}) = ∅ \\ {c_{1}} ∥− {¬c_{1}}, I(r_{3}) = {c_{1}} \\ {¬c_{2}} ∥− {c_{2}}, I(r_{4}) = {c_{1}} \\ {c_{2}} ∥− {¬c_{2}}, I(r_{5}) = ∅ \\ {¬c_{2}} ∥− {c_{2}}, and I(r_{6}) = ∅ \\ {c_{2}} ∥− {¬c_{2}}.

Let S = {r_{1}, r_{2}, r_{3}, r_{4}} and S′ = {r_{1}, r_{2}, r_{5}, r_{6}}. Then S has three admissible extensions
E_{1} = S ∪ {¬c_{1}},
E_{2} = S ∪ {c_{1}, c_{2}},
E_{3} = S ∪ {c_{1}, ¬c_{2}},

and S′ has four admissible extensions

F_{1} = S′ ∪ {c_{1}, c_{2}},
F_{2} = S′ ∪ {c_{1}, ¬c_{2}},
F_{3} = S′ ∪ {¬c_{1}, c_{2}},
F_{4} = S′ ∪ {¬c_{1}, ¬c_{2}}.

We then have the following extents and conditional extents.

\begin{matrix}E(x, S) & m† & m^{∗} & m^{!} \\ c_{1} & 2/3 & 1/2 & .70+ \\ ¬c_{1} & 1/3 & 1/2 & .29+ \\ c_{2} & 1/3 & 1/4 & .35+ \\ ¬c_{2} & 1/3 & 1/4 & .35+ \\ r_{1} & 1 & 1 & 1 \\ r_{5} & 0 & 0 & 0 \end{matrix}

\begin{matrix}E(x, S′) & m† & m^{∗} & m^{!} \\ c_{1} & 1/2 & 1/2 & 1/2 \\ ¬c_{1} & 1/2 & 1/2 & 1/2 \\ c_{2} & 1/2 & 1/2 & 1/2 \\ ¬c_{2} & 1/2 & 1/2 & 1/2 \\ r_{1} & 0 & 0 & 0 \\ r_{5} & 1 & 1 & 1 \end{matrix}

In the following, entries represent (m†, m^{∗}).

CE(x | y, S) = \begin{matrix}x\y & c_{1} & ¬c_{1} & c_{2} & ¬c_{2} & r_{1} \\ c_{1} & (1, 1) & (0, 0) & (1, 1) & (1, 1) & (2/3, 1/2) \\ ¬c_{1} & (0, 0) & (1, 1) & (0, 0) & (0, 0) & (1/3, 1/2) \\ c_{2} & (1/2, 1/2) & (0, 0) & (1, 1) & (0, 0) & (1/3, 1/4) \\ ¬c_{2} & (1/2, 1/2) & (1, 1) & (0, 0) & (1, 1) & (1/3, 1/4) \\ r_{1} & (1, 1) & (1, 1) & (1, 1) & (1, 1) & (1, 1) \\ r_{5} & (0, 0) & (0, 0) & (0, 0) & (0, 0) & (0, 0) \end{matrix}

Constructions similar to the above were first proposed by Carnap in his theory of probability as “degrees of entailment.”^{21} While the ideas are similar, there are important differences between the two approaches. Let D = {a, ¬a, b¬b, r, ¬r}, S = {a, r}, and define I(a) = I(¬a) = I(b) = I(¬b) = P D, I(r) = {a} \\ {¬r} ∥− {b}, and I(¬r) = ∅ \\ {b} ∥− {¬b}. In this case, S has the sole admissible extension {a, r, b}, so all extents and conditional extents are either 1 or 0, no matter which measure function is chosen. But let us consider a posteriori extents. Here we have the table, again independent of choice of measure function,

21[Carnap 1950], [Kyburg 1970]

x E(x, S) AE(x | y, S) : a ¬a b ¬b r ¬r
a  1  1 1 1 1 1 1
¬a  0  0 1 0 0 0 0
b  1  1 1 1 1 1 0
¬b  0  0 0 0 1 0 1
r  1  1 1 1 1 1 1
¬r  0  0 0 0 0 0 1

Note here that while E(b, S) = 1 and E(¬b, S) = 0, we have AE(b | ¬r, S) = 0 and AE(¬b | ¬r, S) = 1, so accepting ¬r involves “learning” ¬b and “unlearning” b, no matter which of the measure functions we use. This ability to learn and unlearn things is quite different from the standard sorts of learning theories studied by Carnap, and even in common cases, the differences in what objects are measured permits “inductive learning” with any of our measure functions, something not true of Carnap’s theories. Unfortunately, we cannot pursue this topic here.

§42. One extension to the above constructions is to allow measures of how a state component appears in the admissible extensions of a set of reasons to depend on the element as well as on the admissible extensions. For example, if we want to weight components by how many arguments warrant their presence in a state, we cannot use a pure measure on states, for that would treat every element in the same way. To permit the wider class of measures of “certainty,” we allow measure functions m_{A} dependent on subsets A of D, subject to the additivity requirement that if A, B ⊆ D and Ŝ ⊆ S̸, then

m_{A∪B}(Ŝ) = m_{A}(Ŝ) + m_{B}(Ŝ) − m_{A∩B}(Ŝ).

In effect, we replace measure functions on P S̸ by measure functions on P D × P S̸. Thus we might define a simplistic argument counting measure by m_{{e}}({S}) = |{d ∈ S | d is a valid reason for e in S}|.

§43. With probabilistic constructions on sets of reasons, we can recast the description of the agent’s evolution in time in terms of these constructions. To make the new constructions easier to grasp, we first treat the ahistorical, isolated system (S̸, Δ) and then extend the construction to history-dependent, non-isolated systems (S̸, E, E).

The basic idea of the probabilistic treatment of an agent’s state-evolution is to view the “nondeterministic” transition table Δ instead as an incomplete specification of a probabilistic transition table. For example, under a Laplacian assumption, we could take each transition S′ ∈ Δ(S) to be equally likely among the possible transitions from S. Alternatively, we could assume transitions to simple states are more likely than transitions to more complex states. In fact, each measure function m on P S̸ such that m(S̸) > 0 gives rise to a probabilistic interpretation of Δ by defining the probability of moving from S ∈ S̸ to S′ ∈ Δ(S) to be m({S′})/m(Δ(S)). (For the time being, we assume that Δ(S) is nonempty for every S ∈ S̸.) This interpretation recalls the relation between the standard and many-worlds interpretations of quantum mechanics, but we cannot pursue that here.^{22}

With assumptions about transition probabilities captured in measure functions, we can describe the temporal evolution of an agent (S̸, Δ) in terms of the probability that the agent will be in state S at time t. We assume initial probabilities of being in a state for time t = 0, and then apply the transition probabilities to determine the probabilities for times t > 0. The instantaneous functions assigning probabilities to states are called density functions, and are simply measure functions f on P S̸ such that f(S̸) = 1, that is, functions that say that the agent must be in some state. As above, every nontrivial measure function m such that m(S̸) > 0 induces a density function by defining f(X) = m(X)/m(S̸). Thus beginning with an “initial state function,” for example

22[de Witt and Graham 1973], [van Frassen 1980]

f_{0}(X) = \{ \begin{matrix}0 & S_{0} ∉ X \\ 1 & S_{0} ∈ X \end{matrix} ,

we look to calculate the sequence of density functions ⟨f_{0}, f_{1}, f_{2}, … ⟩ describing the evolution of the system (S̸, Δ) with respect to m.

Note first that the set of all density functions on S̸ is a convex set. That is, if f_{1} and f_{2} are density functions, and if w_{1} + w_{2} = 1, then w_{1}f_{1} + w_{2}f_{2} is a density function as well.

Successive density functions for a system are computed by combining the probability that the system is in a particular state with the probability of moving from that state to specific other states. We add up the probabilities of reaching a state, and we have the new density function. Formally, we define f_{t+1} for each S ∈ S̸ by

f_{t+1}(\{S\}) = ∑_{x∈S̸} f_{t}(\{x\}) · \frac{m(Δ(x) ∩ \{S\})}{m(Δ(x))}.

The resulting function f_{t+1} is a density function since by induction ∑_{x∈S̸} f_{t}({x}) = 1 and f_{t+1} is the convex combination of density functions g_{x}({S}) = m(Δ(x) ∩ {S})/m(Δ(x)).

As in the instantaneous case considered previously, we can extract “degrees of belief” from the successive density functions by defining, for A ⊆ D, c_{t}(A) = f_{t}(S̸ \ A) as the probability that the system is in a state containing the components A. As before, these projections of state probabilities onto components need not be unitary, since in a linguistic reasons agent we might have c_{t}({d}) + c_{t}({¬d}) < 1.

We extend this construction to the case of nonisolated, possibly singular, extended transition tables as follows. Let (S̸, E, E) describe the agent. In the general case, transition probabilities may depend upon the full history of the agent, and we represent some of these with a measure function F on T ×E ×T , interpreting F ({T }, {e}, {T′}) as the probability of moving to trajectory T′ given the previous trajectory T and environment e. Ideally, we would get F by projecting probability measures on the world’s transitions in (S̸_{W})^{∗} × (S̸_{W})^{∗}, but we do not treat that most general case here. We assume F is normalized so that

∑_{S∈E(T,e)} F ({T }, {e}, T; S) = 1

for every T ∈ T and e ∈ E, thus making the probabilistic interpretation possible. We construct a sequence of density functions f_{t} on E^{∗}×T from the transition probabilities so that f_{t}(ê, T) represents the probability of the agent having traversed trajectory T in response to the sequence of environments ê ∈ E^{∗}. The initial density function f_{0} is given, and we define f_{t+1} so that

f_{t+1}(ê; e, T) = ∑_{T′∈T} f_{t}(ê, T′) · F (T′, e, T).

These density functions on T can be projected onto S̸ to give the probabilities of the agent being in specific states by defining ϕ_{t}(ê, S) for every t, ê, S to be

ϕ_{t}(ê, S) = ∑_{T;S∈T} f_{t}(ê, T; S)

.

§44. Many researchers in artificial intelligence have abandoned the direct use of probabilistic representations on the basis of several intuitions. Briefly, they are (1) One usually has only fragments of information about a few questions. Coming up with a complete matrix of conditional probabilities for all questions is not feasible, while incrementally formulating rules of thumb for generalities, exceptions, etc., is quite feasible. Much of the work in “knowledge acquisition” focusses on elicting and subsequently editing rules of thumb, though sometimes with “certainty factors” whose close values are recognized to be meaningless.

(2) One usually has only a few known goals or desires, augmented occasionally by problem-oriented reasoning, rather than a complete utility function. (3) It is easier to work by adding and removing individual statements from a database or subdatabase than to continually recompute probability distributions. (4) When errors of information are revealed, or when new sorts of events are formulated, one must completely revise one’s system of conditional probabilities. But these revisions must be based on some qualitative considerations, to which the numerical probabilities are merely fit. (See [Doyle 1983b] for another discussion of these.) These intuitions can be summarized by saying that the usual Bayesian approach, while a fine system for formulations of decisions post hoc, or for mechanization of thoroughly explored, stable, narrow decisions, is both informationally and computationally infeasible in broad, changing systems. Bayesianism simply says nothing about the problems of incrementally formulating systems of probabilities, which are the main practical difficulties facilitated by the artificial intelligence approach. If these prejudices are justified, then the constructions presented previously offer the consolation that even if one abandons probabilities in direct use, one can always recover them when necessary, that artificial intelligence practice is not contradicting the Bayesians so much as being forced to work with less.

These intuitions would likely profit from formal exploration. For instance, Bayesians are familiar with the notion of qualitative probabilities. Indeed, the foundations of statistics develops axioms for these qualitative probabilities, and one shows that any consistent set of qualitative probabilities can be fit with a compatible system of numerical probabilities. One proves this fit unique given assumptions about the fineness and topological completeness of the qualitiative probabilities. The artificial intelligence approach in effect concentrates on these qualitative probabilities, abandoning a priori fineness and topological completeness assumptions.

More concretely, if we consider linguistic reason agents, we see the primary difference between the theory of subjective probability and the theory of extents turns on the question of completeness. For Bayesians, subjective probabilities are unitary, that is, the subjective probabilities of x and ¬x sum to 1 for each x. In contrast, in the present theory some admissible extensions of S may contain neither x nor ¬x, so that E(x, S) + E(¬x, S) < 1. The theories could be brought into agreement if we required completeness of extensions, that is, added to R the requirement that for each d ∈ D and S ∈ S̸, either d ∈ S or ¬d ∈ S. But this is a very peculiar requirement, for two reasons. First, the whole point of reasoned assumptions is to be able to complete one’s set of beliefs with respect to some question when necessary, taking lack of information and incompleteness as normal. Requiring completeness of extensions is not in direct conflict with this motivation, but it does mean replacing every ordinary extension with the set of all possible completions of the extension. Second, it seems unwise to attempt to rule out paradoxical sentences at the outset. We can think about and phrase the Liar paradox, and some reasonable artificial agents should share our ability. But the character of paradoxical sentences is that neither they nor their negations may be part of a consistent theory, so if we want interesting languages of thought, we cannot accept the Bayesian requirement of completeness.

Bayesianism stems from important motivations, but overidealizes. While the above constructions indicate the naturalness and importance of the idea of strength of beliefs and other attitudes, it also casts doubts upon the Bayesian identification of degree of belief with subjective probability. The measure of degree of belief via extents is a perfectly good probability measure, but the projection of this measure onto the logical structure of states is not in general a probability measure without the specious axiom of completeness. As in quantum theory, the projected measure represents a lattice of possible events, and only represents a boolean lattice in the special case of complete states.^{23}

23[Birkhoff 1967], [Beltrametti and Cassinelli 1981]

Of course, the Bayesian might respond that our constructions do not capture subjective probabilities, but simply lower bounds on subjective probabilities, as in the Dempster/Shafer theory of evidence.^{24} While this reply does not address the difficulties posed by paradoxical sentences, it may offer a way of reconciling the views, but we cannot pursue that here.^{25} Instead, we observe that whatever the attractions of the stronger Bayesian theory for more competent agents, in computationally realized agents, the “lower bounds” offered by our construction may be the only reasonable choices for “degrees of belief.” We see this in two ways. The first is that extents arise naturally as the end result of the operation of probabilistic algorithms, and in this way are not so much computational approximations to ideal quantities as objective events observed by the agent (even though the events are part of the agent itself). The second point is that the dynamical form of extents, densities, arise naturally in consideration of revision of state, for example in backtracking. At singularities in a trajectory continued by means of plain chronological backtracking, the possible successors are just the successors of the previous state not taken. That is, if T = T′; S and Δ(S) = ∅, then E(T) = E(T′) − {S}. In this case, densities in E(T) are approximately extents in the kernel of E(T′), and correspond to the resilience of state components, to the relative ease with which they may be avoided in successor states. If some density is large, most successors will contain the component in question, so it is difficult to avoid. Indeed, we can adopt this view at every point of a trajectory, singular or not, by considering imaginary discontinuities, by asking how the agent would have to view things were the current view forbidden. In this way, densities in E(T) can always be taken as the resilience of state components. This interpretation of densities is particularly appealing since it applies to all components of mental states uniformly. For example, in attitudinal theories it provides measures not only of degrees of belief but of strength of desire and firmness of intent. Pursuit of this interpretation leads to an interesting non-Bayesian decision theory, but that is beyond the scope of this paper.

If consideration of extents in trajectories provides motivations for some of the concerns of subjective Bayesian probability theory, it also helps understand Zadeh’s notion of fuzzy sets and concepts.^{26} Statements like “Sue is tall” are considered vague because “tall” is not a well-defined concept; there are many heights Sue could reach and be thought tall. Zadeh formalizes this notion by introducing a spectrum of truth-values for the sentence, a spectrum derived from a spectrum of tallness-values. One might instead develop a theory of fuzzy concepts in terms of extents. Rather than simply assuming tallness spectra, one could formulate exact theories of tallness and simply look to see what distribution these entail for particular statements. For example, one might require exact theories of tallness to specify exact intervals of height, and given this restriction look to the admissible extensions of the statement “Sue is tall.” If there are many intervals saying one height is tall and fewer intervals saying another height is tall, then the first height will be “more tall” than the second. Example 24.11 can be read as a formal example of this idea in terms of the concept “is a lot.” In that example, 0 is definitely not a lot (lot to degree 0), each n ≥ 3 is definitely a lot (lot to degree 1), while 1 and 2 have intermediate values: 2 is twice as much a lot as is 1 (lot to degree \frac{2}{3} versus degree \frac{1}{3}).

If one approach is to have advantages over the other in practice, the advantages may depend far more on practical utility than on theoretical elegance. The two most important questions are how difficult it is to obtain the information required by each approach, and how costly are the computations involved. As [Doyle 1983b] mentions, the Bayesian informational requirements are severe because one needs vast amounts of information, few bits of which are easily had from experts. The needed information may be had much more easily in the form of ratiocinative rules of thumb. But complementing this, the probabilistic constructions facilitate the use of information acquired as rules of thumb, since they permit comparison of relative strengths or certainties of state components. Since these measures reflect the overall structure of the set of admissible extensions of some kernel, they may be useful in summarizing that structure in lieu of analytical characterization of its branchings, alternatives, etc. Unfortunately, practical exploitation of these possibilities demands efficient algorithms for computing admissible extensions according to specified measure functions. At present, algorithms for this purpose are completely unstudied. Systems like RMS make arbitrary choices in constructing admissible extensions, and while several authors have suggested making these choices depend on properties of the forseen resulting extensions, there is no known way of deriving the resulting measure on states from these intra-algorithmic choices, nor any known recipe for finding an appropriate algorithm when the final measure is specified. The mix of techniques used in practice will depend on the relative facilities and computabilities of the Bayesian and reasoned assumptions approaches. Reasoned assumptions facilitate some important operations, and Bayesianism facilitates others. Can one relate the total cost of working within one approach to the total cost of the other?

24[Shafer 1976]

25See [Lewis 1980].

26[Zadeh 1975]

IV. Related Theories of Reasoned Assumptions

§45. The previous chapter included both development of a theoretical framework for describing theories of reasoned assumptions as well as some first steps toward a mathematical development of the framework itself. The value of such a framework, if any, must begin with the power to clearly describe specific theories, rather than with the possibility of a mathematical theory based on the framework, although once the grounds of the theory are secured, mathematical analysis can reveal hidden structure. We have seen how the framework eased the introduction of the several constitutive ideas presented previously. In the following sections we further exercise these concepts by using them to analyze and summarize a variety of systems in artificial intelligence touching on notions related to reasoned assumptions. Unfortunately, since several of these systems have never been exactly formulated or described in the literature, or have been described only in terms of the behavior of a set of complex procedures, we cannot always rigorously justify our analyses. Instead, one of the benefits of the current approach is that it may allow authors to precisely specify the intended structure and behavior of their artificial intelligence systems, whether before, during, or after development of the systems.

§46. The first analysis concerns RMS, a program developed by the present author, but standing among several related programs in historical order.^{27} The purpose of RMS (“reason maintenance system;” originally in the literature as TMS, “truth maintenance system”) is to record and revise a set of database entries, carrying out these activities at the behest of a substantive program. RMS performs these duties by recording and analyzing reasons or justifications for database entries in terms of other entries.

As a good first approximation, we can characterize RMS in terms of finitely grounded simple reasons and contradictions, strict transitions, an approximation to symmetric difference conservatism, and non-chronological backtracking. We justify these in turn as best we can. See [Doyle 1983c] for a short, self-contained characterization of RMS.

The reasons or justifications of RMS are exactly of the form of finite simple reasons with singleton conclusions, that is, A \\ B ∥− {c}. In RMS, the first set of elements is called the inlist, the second the outlist, and the sole element of the third the conclusion. In RMS, as in the simple reasons theory, the nature of the domain from which state components are drawn is left unspecified. RMS assigns a name to each domain component as it is presented to the system, and subsequently operates solely in terms of the internal name. Usually, these internal names are state components with trivial interpretations, but some of these may instead be designated contradictions with the empty interpretation. The only other state components are the reasons proper, which have the usual interpretation.

RMS constructs database states to be finitely grounded extensions of the current set of reasons exactly as in the simple reasons theory.

RMS revises the current state to assimilate new reasons added to the current set of reasons. It does this by temporarily removing from the state all components which might be affected by the new reasons, and by then adding back in as many as possible when valid reasons can be found among those left for components in limbo. Unfortunately, I know not how to exactly characterize the actual performance of RMS. It clearly realizes strict transitions because of the finite groundedness ensured by the remove-and-restore algorithm. The intent of the program also appears to be to construct a minimal perturbation with respect to symmetric difference conservatism. The principal predecessor of RMS would completely rederive the entire state following every subtractive kernel modification.^{28} To avoid this, its successors employed “incremental” recomputation of just that state subset directly affected by the changes. Unfortunately, this does not mean RMS actually realizes symmetric difference conservatism, since its aim was never mathematically formulated, and its procedure makes on-the-fly choices that were hoped to approximate the above relations. Its approximations may in fact be good, since it always examines reasons for a particular conclusion in the same order, and so may reconstruct a previous extension subset if it had not really been affected by the perturbation, but the procedures are complex enough to make this difficult to verify, and I bet there are counterexamples. It may be possible to correctly minimize the symmetric difference by recording the previous statuses of state components and attempting to reproduce them whenever choosing some partial revision, but that remains to be explored. RMS is an excellent example of a program suffering from ill-articulated and possibly ill-realized aims, in spite of conscientious care and labor in its design.

27[Doyle 1979], [Doyle 1980]

28[Stallman and Sussman 1977]

RMS employs non-chronological backtracking to avoid pursuing any state containing a contradiction. RMS backtracks by finding an alternative extension of its current state; precisely, by finding a likely perturbation and letting the ordinary revision procedures assimilate the perturbation. Unfortunately, here too I have no simple exact characterization of the process actually realized by RMS. Moreover, contradictions are not absolute, in that if RMS cannot find any alternative extension without the contradiction element (specifically, if it cannot be removed by additions to the current set of reasons), RMS simply proceeds in a state still containing the contradiction. Another difference is that while RMS recognizes and treats incoherence due to contradictions, RMS blindly fails to operate when the set of reasons is otherwise incoherent.

RMS also interprets some of its records as “conditional-proof justifications.” These are counterfactual justifications, as in “I believe P because I would derive a contradiction were I to believe ¬P.” These justifications can be formalized in terms of comparative similarity relations on states. We interpret a conditional-proof justification (A \\ B ∥− C) ∥− D by saying that D must be in S if C ⊆ S′ for every S′ ∈ S̸ such that A ⊆ S′ ⊆ B^{c} and S′ is as similar as possible to S under the chosen notion of similarity of states. Formalized in this way, conditional-proof justifications are “oracles,” involving difficult computational problems that RMS avoided by means of a complex half-measure. In any event, there are very interesting connections to be explored between the comparative similarity relations one might use in interpreting conditional-proof justifications and the comparative similarity relations derived from conservation relations. Understanding these connections might aid the correct and efficient mechanization of conditional-proof justifications.

§47. While our characterization of RMS suffered in accuracy due to the program’s inarticulate development, our next application is much clearer. This is the logic of default reasoning as proposed by Reiter, which turns out to be related to the linguistic reasons theory.^{29} In the logic of default reasoning, states are composed of two sorts of elements: logical formulas, and defaults. Formally, D = D_{1} ⊕ D_{2}, where D_{1} is the set of closed wffs of a first-order logical language L, D_{2} is another set, and ⊢ is the ordinary deducibility relation on L. The elements of D_{1} are called statements, the elements of D_{2} defaults. All statements are trivially interpreted, and all defaults are interpreted as special sorts of simple reasons involving only statements, specifically, if d ∈ D_{1}, I(d) = P D, and if d ∈ D_{2}, there are (possibly open) wffs a, c ∈ L, B ⊆ L, such that

I(d) = {a} \\ ¬B ∥− {c} = ⋂_{σ∈Σ}{S ⊆ D | σa ∈ S ⊆ (¬σB)^{c} ⊃ σc ∈ S},

where σ ranges over the set Σ of all substitutions of closed terms for free variables. We write _{1}S and _{2}S to mean S ∩ D_{1} and S ∩ D_{2} respectively. The only general restriction on states is that their statements be deductively closed, that is,

R = {S ⊆ D | _{1}S = Th(_{1}S)}.

As before, AExts = FGExts where for every d ∈ D and S ⊆ D,

J (d, S) = {E | d ∈ E ⊃ [d ∈ S ∨ E − {d} ⊢ {d} ∨

29[Reiter 1980], [Reiter and Criscuolo 1981]

∃e ∈ _{2}E∃σ ∈ Σ I(e) = {a} \\ ¬B ∥− {c}
∧ σa ∈ E ⊆ (¬σB)^{c} ∧ d = σc]}.

(47.1) Definition. The Reiter-extensions of S ⊆ D are sets E ⊆ D_{1} such that Γ_{S}(E) = E, where for each X ⊆ D_{1}, Γ_{S}(X) is the smallest set satisfying

(1) _{1}S ⊆ Γ_{S}(X)

(2) Th(Γ_{S}(X)) = Γ_{S}(X)

(3) For each d ∈ _{2}S and σ ∈ Σ, if I(d) = {a} \\ B ∥− {c}, σa ∈ Γ_{S}(X), and ¬σB∩X = ∅,

then σc ∈ Γ_{S}(X).

This definition rephrases in our language the definition of “extensions” given by Reiter. The equivalence of this notion with our notion of admissible extension is seen as follows.

(47.2) Theorem. S <· E iff _{2}S = _{2}E and _{1}E = Γ_{S}(_{1}E).

Proof. (only if) Let S <· E. Clearly, if e ∈ _{2}E, then e ∈ S, since there are no reasons in D which support any elements of D_{2}. Since S ⊆ E, this means _{2}S = _{2}E. Now note that E satisfies conditions (1)- (3) of the definition of Γ_{S}, so Γ_{S}(_{1}E) ⊆ E, hence Γ_{S}(_{1}E) ⊆ _{1}E. Next, since each element in D_{1} is trivially interpreted, _{2}E ∪ Γ_{S}(_{1}E) ∈ QExts(S). But by the minimality of E among QExts(S), E ⊆ _{2}E ∪ Γ_{S}(_{1}E), hence _{1}E = Γ_{S}(_{1}E). (if) Suppose _{2}S = _{2}E and _{1}E = Γ_{S}(_{1}E). Since each element of D is trivially interpreted, this means E ∈ QExts(S), so Λ_{ω}(S, E) ⊆ E. Now Λ_{ω}(S, E) satisfies (1)-(3) of the definition of Γ_{S}, so E ⊆ Λ_{ω}(S, E), hence E = Λ_{ω}(S, E) and S <· E.

Note that in the logic of defaults, statements of the object language may not refer to defaults, while no such restriction is present in the theory of linguistic reasons.

§48. The next example is the logic of propositional deduction as cast by McAllester in his TMS.^{30} The principal motivation for this logic is the view that a reason A \\ B ∥− C really means A ∧ ¬B ⊃ C, and that all sources for reasoned assumptions lie outside the ordinary logical system. This motivation is captured as follows as a special case of our formalization of Reiter’s logic of defaults. As before, let L be a first-order logical language, and D = D_{1} ⊕ D_{2}, where D_{1} = D_{2} is the set of closed wffs of L. If d ∈ L, we write _{1}d for its occurrence in D_{1} and _{2}d for its occurrence in D_{2}, and as before, we write _{1}S and _{2}S to mean S ∩ D_{1} and S ∩ D_{2} respectively. The elements of D_{1} are called statements, the elements of D_{2} defaults. If 1d ∈ D_{1}, I(_{1}d) = P D, and if _{2}d ∈ D_{2}, I(_{2}d) = ∅ \\ {¬_{1}d} ∥− {_{1}d} = {S ⊆ D | ¬_{1}d ∉ S ⊃_{1}d ∈ S}. In this special case of the logic of defaults, we have for each d ∈ D and S ⊆ D,

J (d, S) = {E | d ∈ E ⊃[d ∈ S ∨ E − {d} ⊢ {d} ∨ d ∈ D_{1} ∧ [_{2}d ∈ _{2}E ∧ ¬d ∉ E]}.

This logic weakens the logic for default reasoning by removing all power of discussing assumptions and their motivations from the states themselves.

While this simple logical system may reflect McAllester’s intent for the logic of propositional deduction, he actually proposes a specific deductively weaker system, a modal logic of sorts. In that system, D_{1} is the set of ground formulas of a first-order language extended with a modality True and D_{2} is the set of all formulas of the form True(p) or ¬True(p), where p is a ground formula of the non-modal first-order language. The idea is that reasons A \\ B ∥− C are translated as True(A) ∧ ¬True(B) ⊃ True(C), and this is carried out as follows. In contrast to the preceding, we now define admissible states to be sets of formulas closed under a complex set of inference rules, rules which together combine to produce something less than ordinary deducibility. Everything except deducibility is defined as before, and we define ⊢ to be the deducibility relation generated by the following abbreviations (explained immediately below).

30[McAllester 1980]

1. ⊖True(p ∨ q) ⊙ True(p) ⊙ True(q)

2. ⊖True(p) ⊙ True(p ∨ q)

3. ⊖True(q) ⊙ True(p ∨ q)

4. True(p ∧ q) ⊙ ⊖True(p) ⊙ ⊖True(q)

5. ⊖True(p ∧ q) ⊙ True(p)

6. ⊖True(p ∧ q) ⊙ True(q)

7. ⊖True(p ⊃ q) ⊙ ⊖True(p) ⊙ True(q)

8. True(p ⊃ q) ⊙ True(p)

9. True(p ⊃ q) ⊙ ⊖True(q)

10. True(¬p) ⊙ True(p)

11. ⊖True(¬p) ⊙ ⊖True(p)

Here ⊖ and ⊙ are “meta-negation’ and “meta-disjunction.” Each of the above statements abbreviates several inference rules corresponding to the logical structure of the meta-formula. For example, #7 above actually stands for the three rules

7.a True(p ⊃ q), True(p) ⊢ True(q)

7.b True(p), ¬True(q) ⊢ ¬True(p ⊃ q)
7.c True(p ⊃ q), ¬True(q) ⊢ ¬True(p)

Note the weakness of this ⊢ compared with ordinary deducibility, in that True(p ⊃ q), True(¬p ⊃ q) ⊬ True(p). As with RMS, the exact conservation relation realized by McAllester’s TMS is not clear, but seems related to the symmetric difference relation defined previously. Otherwise, the accuracy of this characterization of the weak logic of propositional deduction is easy to verify, as the above formulas merely paraphrase the definitions and explanations given by McAllester, where we write True(p) and ¬True(p) for his (p.true) and (p.false).

§49. Our next example restates non-monotonic logic, one of the first formal treatments of reasoned assumptions. Non-monotonic logic is based on the idea of phrasing rules for making assumptions in terms of logical consistency of assumptions with other beliefs. This idea traces back to McCarthy and Hayes, who introduce but never develop modalities Normally, Consistent, and Probably for use in the rule Normally(p), Consistent(p) ⊢ Probably(p).^{31} Later, McDermott and the present author developed the idea by providing a formal theory involving statements of the form p ∧ Mq ⊃ r, where M here is a modality intuitively interpreted as logical consistency with other beliefs, that is, Mp means ¬p is not a consequence of current beliefs.^{32} Since then there have been other developments by McDermott, Stallman, Gabbay, and Moore. We discuss these below as well.

We cast the initial non-monotonic logic as follows. Let D be the set of sentences in a first-order language extended by the unary modality M. We let ⊢ stand for ordinary deducibility, and define

R = {S ⊆ D | S = Th(S) ∧ ∀d ∈ D [¬d ∈ S ∨ Md ∈ S]}.

We make no nontrivial interpretations of elements of D, so S̸ = R. For each d ∈ D and S ⊆ D we define

J (d, S) = {E | d ∈ E ⊃[d ∈ S ∨ E − {d} ⊢ {d} ∨ ∃e ∈ D¬e ∉ E ∧ d = Me]}.

Finally, we let AExts = FGExts, where E ∈ FGExts(S) iff for each e ∈ E there is a finite set G ⊆ E and a well-ordering <_{G} of G such that e ∈ G and whenever d ∈ G, either d ∈ S or there is a set A <_{G} d with A ⊢ {d} or d = Mf for some f ∈ E^{c}.

(49.1) Theorem. S <· E iff E = Th(S ∪ {Md | ¬d ∉ E}).

31[McCarthy and Hayes 1969]

32[McDermott and Doyle 1980]

Proof. (only if) Assume S <· E. By the admissibility of E, {Md | ¬d ∉ E} ⊆ E, since S < E, S ⊆ E, and since E = Th(E), Th(S∪{Md | ¬d ∉ E}) ⊆ E. But if e ∈ E, then every grounding set G for e contains a proof of e from S ∪ {Md | ¬d ∉ E}, so E ⊆ Th(S ∪ {Md | ¬d ∉ E}, hence E = Th(S ∪ {Md | ¬d ∉ E}). (if) Suppose E = Th(S ∪ {Md | ¬d ∉ E}). Clearly E ∈ QExts(S). Furthermore, if e ∈ E, every proof of e from S ∪ {Md | ¬d ∉ E} is a grounding set for e in E, hence E ∈ FGExts(S).

Thus a simpler characterization of the admissible extensions of S is as the fixed points of deductively closing S together with all the “assumptions” of consistency not ruled out in the admissible extension. This characterization also shows the equivalence of our definition with that of McDermott and Doyle, since this fixed-point formula is exactly their definition.

(49.2) Corollary. AExts = μAExts.

Proof. Suppose S <· E, S <· E′, and E ⊆ E′. Let A = {Md | ¬d ∉ E} and A′ = {Md | ¬d ∉ E′}. Since E ⊆ E′, A ⊃ A′, so by the monotonicity of Th, E′ = Th(S ∪ A′) ⊆ Th(S ∪ A) = E. Hence E = E′.

Unfortunately, this logic is too weak, in that it does not enforce the intuitive interpretation of M as consistency. For example, the set of axioms {¬P, MP } is perfectly consistent in this logic, and its sole admissible extension contains no pair of contrary sentences. We can strengthen the theory to capture the intent by adding interpretations for each d ∈ D of I(Md) = {S ⊆ D | ¬d ∉ S ≡ S = D}. With this added requirement, we remove from S̸ all elements of R presenting an incoherent but not inconsistent notion of consistency for M, but lose the simple characterization of admissible extensions given in Theorem 49.1.

Examples. Here we use the strengthened logic.

(49.3) S = {MP ⊃ P }, AExts(S) = {Th({MP ⊃ P, P } ∪ {MP, … })}

(49.4) S = {MP, ¬P }, AExts(S) = ∅

(49.5) S = {¬P, M(P ∧ Q)}, AExts(S) = ∅

(49.6) S = {MP ⊃ Q, ¬Q}, AExts(S) = ∅

(49.7) Definition. A set S ⊆ D has default form if every formula in S is either non-modal or has only non-iterated occurrences of M in the form p ∧ Mq_{1} ∧ … ∧ Mq_{n} ⊃ r, for some non-modal formulas p, q_{1}, … q_{n}, r.

(49.8) Theorem. If S has default form and S <· E, then for each d ∈ D, Md ∈ E iff ¬d ∉ E.

Proof. Suppose S has default form and S <· E. By the admissibility of E, Md ∈ E if ¬d ∉ E, so suppose Md ∈ E. Then Md must have a proof from S ∪ {Me | ¬e ∉ E}. But since Md is not in default form, Md ∉ S, and similarly, Md cannot appear as a conclusion of Modus Ponens in such a grounding argument, hence Md must be an assumption, that is, ¬d ∉ E.

Unfortunately, a default form set S can be incoherent even if its natural translation S′ in the linguistic reasons theory is coherent. Reiter’s example is the set S containing just

\begin{matrix}p_{1} ∧ Mq_{1} ⊃ q_{1} & p_{2} ∧ Mq_{2} ⊃ q_{2} & p_{3} ∧ Mq_{3} ⊃ q_{3} \\ q_{1} ⊃ p_{2} & q_{2} ⊃ p_{3} & q_{3} ⊃ p_{1} \\ q_{1} ⊃ ¬q_{2} & q_{2} ⊃ ¬q_{3} & q_{3} ⊃ ¬q_{1}. \end{matrix}

The translation of this, S′, is a set of normal defaults, and so is coherent by Theorem 24.15 with extension Th(S′). But S itself is incoherent. To see this, suppose S <· E. If Mq_{1}, Mq_{2}, Mq_{3} ∉ E, then ¬q_{1}, ¬q_{2}, ¬q_{3} ∈ E, but these must be ungrounded, hence at least one assumption must be in E. E cannot contain two or more of these assumptions, since each rules out the previous one: for instance, if ¬q_{1} ∉ E, then Mq_{1} ∈ E, hence p_{1} ⊃ q_{1} ∈ E, hence ¬q_{3} ⊃ q_{1} ∈ E, hence ¬q_{3} ∈ E. But E cannot contain just one of these assumptions either, since one does not rule out both of the other two, thus allowing a second. Therefore S cannot be coherent.

While the unwanted admissible states can be removed from the original non-monotonic logic by the surgical addition of nontrivial interpretations for modal statements, the surgery leaves an ugly scar, in that we no longer have a simple characterization of the resulting states. Fortunately, Moore has discovered a better solution, which, simply stated, defines admissible extensions of S as sets E such that

E = Th(S ∪ {Md | ¬d ∉ E} ∪ {¬M¬d | d ∈ E}).

(See [Moore 1983].) This definition remedies the weaknesses of the original non-monotonic logic while retaining a simple characterization of admissible extensions. We reproduce this idea by redefining the general restriction R so that

R = {S ⊆ D | S = Th(S) ∧ ∀d ∈ D[d ∈ S ≡ ¬M¬d ∈ S ∧ d ∉ S ≡ M¬d ∈ S]}

and by redefining J so that for each d ∈ D and S ⊆ D,

J (d, S) = {E | d ∈ E ⊃[d ∈ S ∨ E − {d} ⊢ {d}
∨ ∃e ∈ D d = Me ∧ ¬e ∉ E
∨ ∃e ∈ E d = ¬M¬e]},

with the corresponding redefinition of FGExts. If we read ¬M¬ as “in” and M¬ as “out,” we see that Moore’s requirement is to make admissible states omniscient about their contents, in that every admissible state S completely encodes the “in” and “out” sets, since S = {e | ¬M¬e ∈ S} and S^{c} = {e | M¬e ∈ S}. Moore suggests renaming non-monotonic logic as “autoepistemic logic” to recognize this sort of selfomniscience.

Other approaches were taken towards remedying the weaknesses of the initial non-monotonic logic, but they introduced other problems and so are less attractive than Moore’s solution. McDermott tried strengthening the weak logic by adding axiom schema and inference rules for M similar to those seen in classical modal logic.^{33} He considered systems corresponding to the modal logics K, T, S4, and S5, which employ the inference rules

MP : p, p ⊃ q ⊢ q

Nec : p ⊢ Lp

(here L abbreviates ¬M¬) and the axiom schema

Taut :  L(t)  for all tautologies t
K :  L(p ⊃ q) ⊃(Lp ⊃ Lq)
T :  Lp ⊃ p
S4 :  Lp ⊃ LLp
S5 :  Mp ⊃ LMp

The resulting system including Nec, Taut, and K allows inference of MP from M(P ∧ Q), something not possible in the weak logic, and these additions make MP and ¬P inconsistent. But the incoherence of {MP, ¬P } in the weak logic is seen as a lack of self-omniscience, so T, S4, and S5 are added in one at a time to give the logic a description of its own sense of provability. No convenient characterization of the power of the systems of non-monotonic T and S4 are known, and unfortunately in the extreme case, these additions trivialize the logic by making all reasons invertible in non-monotonic S5. That is, in the system with Nec, Taut, K, T, S4, and S5 we can conduct the following proof:

33[McDermott 1982a]

1. MP ⊃ P  hypothesis
2. L(MP ⊃ P)  Nec, 1
3. LMP ⊃ LP  K, 2, MP
4. L¬P ⊃ ¬P  T
5. P ⊃ MP  4, tautologies
6. P ⊃ LMP  5, S5, MP
7. P ⊃ LP  6, 3, MP
8. P ⊃ ¬M¬P  7, rewriting
9. M¬P ⊃ ¬P  8, tautologies

Because of this, we cannot use the axiom MP ⊃ P to express a preference that P should be adopted before ¬P, since from this statement we can infer M¬P ⊃ ¬P, the opposite “preference.” In fact, the motivations for the additional axioms seems to be to allow the logic to invert all of its reasoning by allowing the discussion of proof steps within the language, and as we saw earlier, theories of invertible reasons are bound to be trivial (an observation only made following McDermott’s work).

Yet another approach toward strengthening the weak logic was explored by Gabbay.^{34} Rather than add in axioms specifically to remedy weaknesses, as in the modal logic extensions, Gabbay began with models for intuitionistic predicate calculus. In these models, the set of beliefs is viewed as a set of theorems monotone nondecreasing in number with the passing of time. At each temporal instant in such models, MP is interpreted to mean “it is consistent at this instant to assume that P is true.” While these models permit a motivated development of natural axioms and inference rules, they unfortunately trivialize the logic, for MP ⊃ P is semantically equivalent with intuitionistic ¬P ∨ P. Because of this equivalence, stating a “reason” like MP ⊃ P does not express any preference, but only requires that every model of the axioms begin with one of P or ¬P being held true, without saying which one.

Realizing the inadequacies of the modal logic extensions of the weak non-monotonic logic, and discerning the need for non-invertible reasons that express preferences, Stallman proposed an extension of non-monotonic S5 which employs a unary modality, S, interpreted as “should be a theorem” in contrast to L’s reading as “is a theorem.”^{35} All of the inference rules and axiom schema of non-monotonic S5 are assumed, as is the new inference rule Sp ⊢ p. This allows expression of defaults as statements of the form Mp ⊃ Sp.

It is unfortunate that Stallman’s thoughts have remained unpublished, for they are very insightful. The present author developed his ideas about ratiocinative desires as expressed in the attitudinal theories of reasoned assumptions above by the fortuitous simultaneity of his attempts to express the logic of reasoned deliberation in non-monotonic logic and his attempts to understand the varieties and possible improvements of non-monotonic logics, during which he realized the possibility of identifying the “should” modality of Stallman’s logic with the notions of ratiocinative intentions or desires. This identification led naturally to the idea that the formal constructions of non-monotonic logic might be plausibly motivated in decision-theoretic terms.

§50. To back away from this preoccupation with logically structured agents, we consider some elements of Minsky’s K-line theory of memory.^{36} Unfortunately, his theory involves many ideas beyond those we formalize, so our presentation is meager compared with his. One does not do justice to Minsky’s conceptions to suppose the following representative of more than the simplest elements of his theory.

For Minsky, the mind is composed of a set of “mental agents.” Each mental agent can be either active or inactive, and states of mind are simply sets of active mental agents. We can identify the set of mental agents with the domain D of the agent, and consider sets S ∈ S̸ to be the admissible sets of active mental agents.

34[Gabbay 1982]

35[Stallman 1981]

36[Minsky 1980]

The two specific sorts of mental agents we formalize here are K-lines and cross-exclusion networks. K-lines are mental agents that, when activated, cause the activation of some set of other mental agents. We formalize this by interpreting K-line agents as monotonic simple reasons. Specifically, for each K-line KL there is some set A ⊆ D such that I(KL) = ∅ \\ ∅ ∥− A.

A purely monotonic agent is not terribly interesting, and one source of non-monotonicity in this theory is that of cross-exclusion networks. These are sets of mental agents which are mutually inhibitory. Further, cross-exclusion networks facilitate “conflict resolution” by disabling or ignoring all members if two or more manage to become active despite their mutual inhibitions. This disabling allows activation of “higher-level” mental agents which can consider and resolve the conflict. We might formalize this by letting CXN be the mental agent representing a cross-exclusion network, D = {d_{i}}_{i=1}^{n} the set of mutually inhibiting members, E = {e_{i}}_{i=1}^{n} the indicators of which competitor wins out, and ¬CXN a mental agent representing the existence of an externally forced conflict. To get the desired behavior, we define I(CXN) = ∅ \\ {¬CXN} ∥− D, I(d_{i}) = ∅ \\ E − {e_{i}} ∥− {e_{i}} for each i, and assume the existence of a “watchdog” WD such that I(WD) = {S ⊆ D | [∃i ≠ j ≤ n e_{i}, e_{j} ∈ S] ⊃ ¬CXN ∈ S}. This interpretation of WD cannot be expressed as a single simple reason, although it can be expressed as a set of n(n − 1) simple reasons.

Finally, states of mind persist until changes are forced by inputs. It is impossible to treat persistence in detail without first formalizing many parts of the theory too involved to discuss here, but we point out that persistence is closely related to conservation, and its formal treatment may well take the form of transition comparison relations for use by a conservative agent.

§51. Our final subject among theories related to reasoned assumptions is McCarthy’s notion of circumscription.^{37} Circumscription has figured prominently in discussions of non-monotonic reasoning, for like theories of reasoned assumptions, it formalizes certain patterns of unsound inferences important in artificial intelligence. Unfortunately, previous discussions have never proved successful at satisfactorily relating the two notions, in spite of their common motivations and superficially similar formal treatments. This section attempts an explanation of this failure of understanding. We first present a description of circumscription in its own terms, as formulated by McCarthy. This is prelude to our main conclusion, that when closely examined, the notions of circumscription and reasoned assumption are almost entirely unrelated, both conceptually and formally. This need not be an unhappy conclusion, if one enjoys richness in one’s subjects of study. We conclude the section by sketching some practical and theoretical aspects of agents in which the two notions are combined.

The idea of circumscription is that for each predicate occurring in a set of sentences in a logical language, one can construct an axiom schema which states that the only truths involving that predicate are those which follow from the original set of sentences alone. Put another way, the circumscription of some predicate states those conclusions which hold in all minimal models of the original set of sentences. For example, if the set of sentences states solely that red and blue are colors, circumscribing the sentences with respect to the predicate “color” produces a theory in which yellow is not a color. Since the sentences do not mention yellow, there are models of those sentences in which yellow is not a color. Some of those are models in which red and blue are the only colors, so one of the conclusions in the circumscription of the sentences is that yellow is not a color, indeed, that red and blue are the only colors. This sort of inference is non-monotonic because if the original sentences are augmented with the statement that yellow too is a color, the color-circumscription of the augmented set no longer contains the conclusion that yellow is not a color.

(51.1) Definition. Let A be a sentence (or conjunction of sentences) in a first-order language containing a predicate symbol P (x̄) = P (x_{1}, …, x_{n}). Write A(Φ) for the result of replacing all occurrences of P in A by the predicate expression Φ. Then Circ(P, A), the circumscription of P in A(P), is the sentence schema

37[McCarthy 1980], [Davis 1980]

A(Φ) ∧ ∀x̄.(Φ(x̄) ⊃ P (x̄)) ⊃ ∀x̄.(P (x̄) ⊃ Φ(x̄)).

We write A μ⊢_{P} q iff q ∈ Th({Circ(P, A)}).

McCarthy observes that this definition can be extended to circumscriptions on two or more predicates simultaneously.

To illustrate this formalization, suppose we know only one red-haired person, our friend Jane. If we see someone looking like Jane in the crude sense of merely being red-haired, we might, via circumscription, assume that that person is Jane, she being the only person we know fitting that description. This inference is non-monotonic, of course, since if we now learn that Jane has an identical twin sister Joan, we can no longer conclude that anyone who looks like Jane is Jane. Expressed formally in terms of McCarthy’s circumscription, this example might be translated as follows. We start with the set of axioms A = {red-haired(Jane)} and circumscribe on the predicate “red-haired.” The circumscription of this predicate in A is the axiom schema

Φ(Jane) ∧ ∀x(Φ(x) ⊃ red-haired(x)) ⊃ ∀x(red-haired(x) ⊃ Φ(x)).

If we now substitute our only known instance of a red-haired person into this schema, that is, if we substitute the formula x = Jane for Φ(x), we get

Jane = Jane ∧ ∀x(x = Jane ⊃ red-haired(x)) ⊃ ∀x(red-haired(x) ⊃ x = Jane).

The first two parts of this formula are true, and simplifying it leaves the resulting assumption or “default” ∀x(red-haired(x) ⊃ x = Jane) which we can apply to any new person that looks like Jane (is red-haired). Yet this inference is non-monotonic, in that if we add the new axiom red-haired(Joan) to A, we can no longer draw any such identifying conclusion. At best, we can infer via another application of circumscription the less specific conclusion ∀x(red-haired(x) ⊃[x = Jane ∨ x = Joan]).

(51.2) Definition. Let M(A) and N(A) be models of the sentence A. We say that M is a submodel of N in P, writing M ≤_{P} N, if M and N have the same domain, all other predicate symbols in A besides P have the same extensions in M and N, and the extension of P in M is included in its extension in N. The model M is minimal in P iff N ≤_{P} M only if N = M. The sentence A minimally entails q with respect to P, written A μ⊧_{P} q, iff q is true in all models of A that are minimal in P.

(51.3) Theorem (McCarthy-Davis). If A μ⊢_{P} q, then A μ⊧_{P} q.

Proof. Let M be a model of A minimal in P. Let P′ be a predicate satisfying the left side of Circ(P, A) when substituted for Φ. By the second conjunct of the left side, P is an extension of P′. If the right side of the instantiated circumscription schema were not satisfied, P would be a proper extension of P′. In that case, we could get a proper submodel M′ of M by letting M′ agree with M on all predicates except P and agree with P′ on P. This would contradict the assumed minimality of M.

(51.4) Theorem (Davis). There are satisfiable sentences with no minimal models.

Proof. Let A be the conjuction of the following four sentences.

(1) ∀x∃y Succ(x, y)

(2) ∃y∀x ¬Succ(x, y)
(3) ∀x, y, z [Succ(x, y) ∧ Succ(x, z) ⊃ y = z]
(4) ∀x, y, z [Succ(y, x) ∧ Succ(z, x) ⊃ y = z]

Every model of A contains a submodel isomorphic to the natural numbers. But this submodel contains an infinite chain of sub-submodels corresponding to the sets of natural numbers exceeding k for each natural number k. Hence A has no minimal model.

(51.5) Theorem (Davis). There are A and P such that A μ⊧_{P} q but not A μ⊢_{P} q.

Proof. Let A be the conjunction of the following set of sentences. (1) ∃x Zero(x)

(2) ∀x, y [Zero(x) ∧ Zero(y) ⊃ x = y]
(3) ∀x∃y Succ(x, y)
(4) ∀x, y [Succ(x, y) ⊃ ¬Zero(y)]
(5) ∀x, y [Zero(x) ⊃ P lus(x, y, x)]
(6) ∀x, y, z, u, v [P lus(x, y, z) ∧ Succ(y, u) ∧ Succ(z, v) ⊃ P lus(x, u, v)]
(7) ∀x, y [Zero(y) ⊃ T imes(x, y, y)]
(8) ∀x, y, z, u, v [T imes(x, y, z) ∧ Succ(y, u) ∧ P lus(z, x, v) ⊃ T imes(x, u, v)]
(9) ∀x, y, z [(Zero(x) ∨ Succ(y, x) ∨ P lus(y, z, x) ∨ T imes(y, z, x)) ⊃ Number(x)]

It is easily seen that there is a unique minimal model of A, namely the standard model of arithmetic. Hence A μ⊧_{Number} q iff q is a true sentence of arithmetic. But the elements of Circ(Number, A) are recursively enumerable, while the truths of arithmetic are not, hence there are circumscriptively true but underivable sentences.

I have repeated these definitions and theorems virtually verbatim from their sources, both because they are worth knowing, and to emphasize the intimate connection they illustrate between the circumscriptive rule of inference and the notion of entailment in minimal models. This is important, for in my view circumscription is a natural and proper topic within the main tradition of mathematical logic. The heart of standard mathematical logic is the study of the entailment relation: When do the models of one set of sentences include the models of some other set of sentences? Analyzing these relations between sets of models leads naturally to analyzing the structure of the class of all models, and as in most mathematical fields, there are natural orders relating the objects of study. In model theory, the model-submodel relation is one such order, so circumscription arises naturally when one studies entailment from the viewpoint of the model-inclusion order. Circumscription would arise naturally in mathematical logic even if no one cared about psychology, even if no one cared to mechanize intelligence. The notion of circumscription is logical, not psychological.

On the other hand, the notion of reasoned assumption is psychological, not logical, at least as far as standard mathematical logic is concerned. Consider the theory of simple reasons. This theory captures essentially all the principal motivations and characteristics of reasoned assumptions, but few logical notions are in evidence. Instead, the important notions are the psychological concepts of intention or desire, and of economic or decision-theoretic tradeoffs between simultaneously unsatisfiable ratiocinative desires and intentions. Questions of entailment and deducibility are not prominent; questions of utility and feasibility are. One can, of course, view state components as axioms and admissible extensions as sets of theorems, but the existence of interesting finite agents realizing these theories belies the identification, for no familiar logic has only a finite language, or has as little structure among its sentences as do some perfectly rigorous simple reasons agents.^{38}

These disparate notions have been confused because of the circumstances in which they were developed. Theories of reasoned assumptions can take logical form, as seen in the linguistic reasons theory, and their first formal treatment was in non-monotonic logic, which as we observed previously, attempted to phrase reasoned assumptions in terms of logical consistency with sets of axioms. Since only logical terms appeared in that development, non-monotonic logic claimed logical status. Thus on one side, the properly psychological notions masqueraded as logical notions. But on the other side, the properly logical notion of circumscription found billing as a psychological notion, at least in artificial agents. Circumscription, of course, has application in certain psychologies, but that no more makes it a principally psychological notion than does the prevalence of carbon-based chemistry in human brains fit carbon for psychological prominence. It is instructive to compare the case of Modus Ponens. From a psychological point of view, circumscription and Modus Ponens are equally relevant, and equally foreign. Both are concepts from mathematical logic whose mechanizations find application in implementing certain psychological functions in certain agents. In this respect, circumscription is at a disadvantage because it is less mechanizable than Modus Ponens, and because much less is known about how and when to fruitfully apply it. But discretionary use of these techniques in implementing psychological functions does not make them crucial for psychological problems or make them psychological notions per se. There is really no more (and no less) need to “explain” the connection between circumscription and theories of reasoned assumptions than there is to “explain” the connection between Modus Ponens and theories of reasoned assumptions.

38Indeed, from the viewpoint of psychology, even the formal notion of axiom acquires nonlogical force, since the word word “axiom” derives from the Greek axioma and axios, words for worth or value and things thought worthy or valued.

The issue is further complicated by the deductivists in psychology and the psychologists in logic. Deductivists are those who, in carciature at least, view all psychological problems as questions of formulating the appropriate logical axioms so that all mental activity can be phrased in terms of deductions from these axioms. As a claim about interesting psychologies, this view is either preposterous or trivial, depending on how one interprets it. As a methodology for how to conduct research in artificial intelligence, it is much less preposterous or trivial, but not without its problems. Psychologists in logic are those who, again in carciature, view logic as the study of the “laws of thought,” a more general view than that taken in standard mathematical logic, and one which leads to all sorts of extensions of logic to incorporate psychological concepts. As a methodology, emphasizing logical investigation of psychological concepts, this view too has its merits, however distasteful the abuse of the term “logic” is to those with classical views. But as a thesis that there are laws including and beyond those of logic that must be common to the psychologies of all rational agents, the claim is unsubstantiated and very suspect, not only due to the diversity of imaginable psychologies, but also because the notion of a natural, universal standard of rationality is itself suspect.

It is important not to misconstrue this discussion of the psychological or logical centrality of certain notions as an attempt to mark boundaries between these fields, or to require labelling of all notions in terms of recognized disciplines. Topics in one field metamorphose into topics in the other quite frequently. But psychology’s main aim is to study agents, their minds and their actions, and standard logic’s main aim is to study truth itself. The two should not be identified lightly.

Let us turn from distinctions to connections. On the practical side, almost nothing is known about when to circumscribe (in advance? when stuck?), what to circumscribe (all of the agent’s beliefs? just a few?), how to circumscribe (mechanize mathematical induction?!), and when and how to retreat from circumscriptively obtained conclusions. The ideas extant (but mostly untried) run as follows. The preferred way of organizing logically-based agents these days is in terms of multiple, mutually referential theories; in the extreme, separate theories for each component for each concept, purpose, and activity of the agent.^{39} In these contexts, circumscription seems suited to the formulation of defaults, which are then treated by the methods of reasoned assumptions. For example, one constructs a logical theory axiomatizing some concept, say rowboats. This “definitional” theory is usually incomplete, say by stating that the boat either can be rowed or lacks oars. One might employ circumscription to complete the theory, computing all the main conclusions that follow in which the boat lacks any problems.^{40} These conclusions, such as the presence of oars, the soundness of the hull, etc., can then be added to the definitional theory in the form of default rules, making the assumptions whenever not specifically ruled out. Similarly, one might use circumscription “on demand” in problem-solving situations by routinely taking the statement of the problem and using circumscription to compute all the basic facts, for example definite lists of all objects and all predicate extensions, making those not already believed to be reasoned assumptions whose qualification is that nothing new is learnt about the problem formulation (new in the sense of not entailed by the initial formulation and hence in contradiction to the assumptions).

On the theoretical side, one can attempt to connect circumscription and reasoned assumptions in several ways. First, one can formulate the definition of something like inevitability in terms of circumscription. Here one has axioms stating the presence or absence of some state components, and other axioms giving the interpretations of state components and general restrictions (in other words, embedding the theory of reasoned assumptions in the agent’s own language). Circumscribing these with respect to the “present” predicate on state components yields conclusions about what must hold in all minimal models of the axioms, about what components are inevitable given the initial components. Unfortunately, I do not know whether one can make this suggestion precise in any interesting way.

39See, for example, [Weyhrauch 1980], [Konolige and Nilsson 1980], [Doyle 1980].

40There are sometimes computationally tractable ways of doing this, see for example [Reiter 1982].

(51.6) Question. Assume a linguistic reasons agent is axiomatized in the suggested way, and suppose S ⊆ L has admissible extensions {E_{1}, …, E_{n}}. Is it the case that circumscribing the axiomatization with respect to “present in the state” implies (or even is equivalent with) ⋀ E_{1} ∨ … ∨ ⋀ E_{n}?

Another possible connection is to consider circumscribing a set of linguistic reasons with respect to all predicates at once. One expects this to contain more conclusions than the intersection of all admissible extensions, simply because the circumscription will try to complete all predicates, while the reasons in the state will only complete certain predicates with respect to certain instances.

(51.7) Question. Suppose S ⊆ L in a linguistic reasons agent is coherent. Does the circumscription of S with respect to all predicates properly include all sentences in ⋂ AExts(S)?

More generally, we can ask for characterization of those psychologies in which important psychological notions match interesting logical notions “in the limit.” The obvious candidate is minimal psychological entailment, even though it is not terribly important in the preceding development.

(51.8) Question. In what sorts of logically based psychologies is minimal psychological entailment the same as minimal entailment?

Note that these questions are still problems for correct formulation rather than simply resolvable conjectures.

V. Conclusions

§52. We have come to the end of this story, even though there is still much to tell. In the preceding we explored the principal approach taken in artificial intelligence to the problem of acting with only incomplete information, that of employing rules of thumb for making and revising assumptions. We interpreted these rules of thumb as ratiocinative desires about when to be or not to be agnostic, how to resolve ambiguities, and when to abandon previous assumptions. We presented a mathematical framework in which each of the constituent ideas underlying applications of the approach could be individually introduced and analyzed. Within this framework we provided mathematical semantics for ratiocinative rules of thumb, which one might call “admissible state semantics” since the meaning of each reason is a set of sanctioned “admissible” states. The formal basis allows mathematical formulation and proof of many conceptions previously known only to folklore, and we stated and proved a number of these results. However, compared to the probabilistic approaches common in other fields, theories of reasoned assumptions are still near the beginnings of their development. I am acutely aware of the essential triviality of some of the results presented, but allow that a new field must begin somewhere. Nevertheless, some of the results are conceptually important, whatever their mathematical depth, for instance Theorem 27.16, the strong validity-optimality of admissible extensions. Hopefully the formal basis will permit deeper understanding of the issues involved, since now many questions of formulation can be treated technically rather than merely debated philosophically, and perhaps permit attack on the important practical questions about efficient mechanizations of conservative agents.

Many topics have been left for treatment elsewhere, either receiving no mention or only passing mention in the preceding. Among these come a development of the evolutionary theory in terms of the global structure of trajectory space; treatments of the abstract notions of reflection and conservatism used here concretely; relations of ideas discussed to Carnap’s theory of probability, Dacey’s theory of conclusions, Levi’s epistemic actions, Shafer’s theory of evidence, and Lewis’s theory of counterfactuals;^{41} and development of practical revision systems satisfying attractive conservation specifications.

§53. While I have tried to draw connections between the methodologies of artificial intelligence and other fields, I have tried to avoid methodological debate within artificial intelligence itself, and hope a very few words of explanation will be tolerated. It is easy to misunderstand the work presented in the preceding, for its aims are somewhat different than those usual in artificial intelligence. The preceding does not attempt to solve a problem in the usual sense. It offers no new algorithms for realizing mental functions. Instead, its aim is to understand the problems and approaches already known. This involves the mathematician’s methodological suspicion that the original formulation of a notion may not be the best one, and that better formulations may permit deep analysis where only complexity reigned before. I call this enterprise rational psychology, the investigation of psychology by reason alone, choosing this name after the example of rational mechanics. I say no more here, as details may be found elsewhere.^{42}

41[Carnap 1950], [Dacey 1978], [Levi 1967], [Shafer 1976], [Lewis 1973]

42[Doyle 1982], [Doyle 1983a]

References

Birkhoff, G., 1967. Lattice Theory, third edition, Providence: American Mathematical Society. Beltrametti, E. G., and Cassinelli, G., 1981. The Logic of Quantum Mechanics, Reading: Addison-Wesley. Carnap, R., 1950. Logical Foundations of Probability, Chicago: University of Chicago Press. Charniak, E., Riesbeck, C. K., and McDermott, D. V., 1980. Artificial Intelligence Programming, Hillsdale,

New Jersey: Lawrence Erlbaum Associates. Dacey, R., 1978. A theory of conclusions, Philosophy of Science 45, 563-574. Davis, M., 1980. The mathematics of non-monotonic reasoning, Artificial Intelligence 13, 73-80. de Witt, B. S., and Graham, N., 1973. The Many-Worlds Interpretation of Quantum Mechanics, Princeton:

Princeton University Press. Doyle, J., 1979. A truth maintenance system, Artificial Intelligence 12, 231-272. Doyle, J., 1980. A model for deliberation, action, and introspection, Cambridge: MIT Artificial Intelligence

Laboratory, TR-581. Doyle, J., 1982. The foundations of psychology, Pittsburgh: Department of Computer Science, Carnegie-

Mellon University. Doyle, J., 1983a. What is rational psychology?, Pittsburgh: Department of Computer Science, Carnegie-

Mellon University. Doyle, J., 1983b. Methodological simplicity in expert system construction: the case of judgments and

reasoned assumptions, AI Magazine, to appear. Doyle, J., 1983c. The ins and outs of reason maintenance, Eighth International Joint Conference on

Artificial Intelligence. Frisch, A. M, and Allen, J. F., 1982. Knowledge retrieval as limited inference, Proc. Sixth Conference on

Automated Deduction (D. W. Loveland, ed.), Lecture Notes in Computer Science # 138, Berlin: Springer-Verlag, 274-291.

Gabbay, D. M., 1982. Intuitionistic basis for non-monotonic logic, Proc. Sixth Conference on Automated Deduction (D. W. Loveland, ed.), Lecture Notes in Computer Science # 138, Berlin: Springer-Verlag, 260-273.

Gärdenfors, P., 1980. Epistemic importance and minimal changes of belief, Lund: Department of Philosophy, Lund University.

Garey, M. R., and Johnson, D. S., 1979. Computers and Intractability: a guide to the theory of NPcompleteness, San Francisco: W. H. Freeman.

Goodman, N., 1973. The problem of counterfactual conditionals, Fact, Fiction, and Forecast, third edition, New York: Bobbs-Merrill, 3-27.

Goodwin, J. W., 1982. An improved algorithm for non-monotonic dependency-net update, Linköping: Software Systems Research Center, Linköping University.

James, W., 1897. The Will to Believe and other essays in popular philosophy, New York: Longmans, Green and Co.

Konolige, K., and Nilsson, N. J., 1980. Multiple-agent planning systems, Proc. Conf. American Association for Artificial Intelligence, 138-142.

Kyburg, H. E., Jr., 1970. Probability and Inductive Logic, New York: Macmillan.

Levi, I., 1967. Gambling with Truth: an essay on induction and the aims of science, New York: Knopf.

Levi, I., 1980. The Enterprise of Knowledge: an essay on knowledge, credal probability, and chance, Cambridge: MIT Press.

Lewis, D., 1973. Counterfactuals, Cambridge: Harvard University Press.

Lewis, D., 1980. A subjectivist’s guide to objective chance, Ifs (W. L. Harper, R. Stalnaker, and G. Pearce, eds.), Dordrecht: Reidel, 267-297.

London, P. E., 1978. Dependency networks as a representation for modelling in general problem solvers, College Park: Department of Computer Science, University of Maryland, TR-698.

Luce, R. D., and Raiffa, H., 1957. Games and Decisions, New York: Wiley.

Martins, J. P., 1983. Reasoning in multiple belief spaces, Ph.D. thesis, Buffalo: Department of Computer Science, State University of New York.

McAllester, D. A., 1980. An outlook on truth maintenance, Cambridge: Artificial Intelligence Laboratory, Massachusetts Institute of Technology, AI Memo 551.

McCarthy, J., 1980. Circumscription—a form of non-monotonic reasoning, Artificial Intelligence 13, 27-39.

McCarthy, J., and Hayes, P. J., 1969. Some philosophical problems from the standpoint of artificial intelligence, Machine Intelligence 4 (B. Meltzer and D. Michie, eds.), New York: American Elsevier, 463-502.

McDermott, D., 1982a. Nonmonotonic logic II: nonmonotonic modal theories, J. A. C. M. 29, 33-57.

McDermott, D., 1982b. Contexts and data-dependencies: a synthesis, Department of Computer Science, Yale University.

McDermott, D., and Doyle, J., 1980. Non-monotonic logic—I, Artificial Intelligence 13, 41-72.

Minsky, M., 1962. Problems of formulation for artificial intelligence, Proc. Symp. on Mathematical Problems in Biology, Providence: American Mathematical Society, 35-46.

Minsky, M., 1963. Steps towards artificial intelligence, Computers and Thought (E. A. Feigenbaum and J. Feldman, eds.), New York: McGraw-Hill, 406-450.

Minsky, M., 1965. Matter, mind, and models, Proc. IFIP Congress, 45-49.

Minsky, M., 1975. A framework for representing knowledge, The Psychology of Computer Vision (P. Winston, ed.), New York: McGraw-Hill. Appendix in MIT AI Laboratory Memo 306.

Minsky, M., 1980. K-lines: a theory of memory, Cognitive Science 4, 117-133.

Minsky, M., and Papert, S., 1969. Perceptrons: an introduction to computational geometry, Cambridge: MIT Press.

Montague, R., 1963. Syntactical treatments of modality, with corollaries on reflection principles and finite axiomatizability, Acta Philosophica Fennica 16, 153-167.

Moore, R. C., 1983. Semantical considerations on nonmonotonic logic, Eighth International Joint Conference on Artificial Intelligence.

Pascal, B., 1662. Pensées sur la religion et sur quelques autres sujets (tr. M Turnell), London: Harvill, 1962.

Quine, W. V., 1953. Two dogmas of empiricism, From a Logical Point of View, Cambridge: Harvard University Press.

Quine, W. V., 1970. Philosophy of Logic, Englewood Cliffs: Prentice-Hall.

Quine, W. V., and Ullian, J. S., 1978. The Web of Belief, second edition, New York: Random House.

Rabin, M. O., 1974. Theoretical impediments to artificial intelligence, Information Processing 74, Amsterdam: North-Holland, 615-619.

Rabin, M. O., 1976. Probabilistic algorithms, Algorithms and Complexity: New directions and recent trends (J. F. Traub, ed.), New York: Academic Press, 22-39.

Reiter, R., 1978. On reasoning by default, Proc. Second Conf. on Theoretical Issues in Natural Language Processing, 210-218.

Reiter, R., 1980. A logic for default reasoning, Artifical Intelligence 13, 81-132.

Reiter, R., 1982. Circumscription implies predicate completion (sometimes), AAAI-82, 418-420.

Reiter, R., and Criscuolo G., 1981. On interacting defaults, Proc. Seventh International Joint Conference on Artificial Intelligence, 270-276.

Rescher, N., 1964. Hypothetical Reasoning, Amsterdam: North Holland.

Savage, L. J., 1972. The Foundations of Statistics, 2nd rev. ed., New York: Dover.

Scott, D. S., 1982. A theory of domains and computability, lecture notes, Pittsburgh: Department of Computer Science, Carnegie-Mellon University.

Shafer, R., 1976. A Mathematical Theory of Evidence, Princeton: Princeton University Press.

Smith, B. C., 1982. Reflection and semantics in a procedural language, Cambridge: Laboratory for Computer Science, Massachusetts Institute of Technology, TR-272.

Stallman, R. M., 1981. A new way of representing defaults, unpublished manuscript, Cambridge: Massachusetts Institute of Technology.

Stallman, R. M., and Sussman, G. J., 1977. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artificial Intelligence 9, 135-196.

Szolovits, P., 1978. The lure of numbers: how to live with and without them in medical diagnosis, Proc. Coll. Computer-Assisted Decision Making using Clinical and Paraclinical (Laboratory) Data (B. E. Statland and S. Bauer, eds.), Tarrytown: Technicon, 65-76.

Thomason, R. H., 1979. Some limitations to the psychological orientation in semantic theory, mimeo, Pittsburgh: University of Pittsburgh.

Thompson, A., 1979. Network truth maintenance for deduction and modelling, Proc. Fifth International Joint Conference on Artificial Intelligence, 877-879.

Tukey, J. W., 1960. Conclusions vs. decisions, Technometrics 2, 423-433.

Turner, R., 1981. Counterfactuals without possible worlds, J. Philosophical Logic 10, 453-493.

Van Frassen, B. C., 1980. A temporal framework for conditionals and chance, Ifs (W. L. Harper, R. Stalnaker, and G. Pearce, eds.), Dordrecht: Reidel, 323-340.

Weyhrauch, R. W., 1980. Prolegomena to a theory of mechanized formal reasoning, Artificial Intelligence 13, 133-170.

Zadeh, L., 1975. Fuzzy logic and approximate reasoning, Synthese 30, 407-428.

Table of Symbols

Symbols appearing in the text are listed below in three groups. First are ones in the roman alphabet (alphabetically), second are ones in the greek alphabet (alphabetically), and third are other symbols. Some symbols appear more than once to avoid confusions about ambiguities of classification. The text also standardly uses the letters a, b, c, d, e, f, g to mean elements of D, the letters A, B, C, D, E, F, G, S to mean subsets of D, and Ê, Ŝ to mean sets of subsets of D.

AE  A posteriori extent
AExts  Set of admissible extensions
Alt  Set of alternative states in backtracking
B^{c}  Complement of B in D, i.e. D − B
CE  Conditional extent
D  Domain of an agent’s states
E  Relative frequency of element in distribution
Exts  Set of extensions of a set
E  Extended transition function (Epsilon)
FGExts  Set of finitely grounded extensions
GExts  Set of grounded extensions
I  State admissibility interpretation function
J  Extension admissibility interpretation function
L  “Provable” modality
L  A logical language
M  “Consistent” modality
m  Measure function
N  Natural numbers
NP  Class of non-deterministic polynomial time computable functions
O  Complexity order class
P  Power set
P  Class of deterministic polynomial time computable functions
#P  Class of non-deterministic polynomial time countable functions
Pr  Probability
Prh  Probability of coming to hold a component
Q  Set of component-admissible states
QExts  Set of component-admissible extensions
R  Real numbers
R  Global restriction on admissible states
S  Stallman’s “Should” modality
S̸  Set of admissible states
T  Trajectory space of a system
Th  Closure of a set with respect to ⊢
U  Universe of a set
V  Set of valid reasons
∂  Kernel transition function
Δ  Full transition function
△  Symmetric set difference
E  Extended transition function
Λ  Elements generated by all ranks
Λ_{α}  Elements generated by rank α

μ  Minimization operator
μ⊢  Circumscriptive deducibility relation
μ⊧  Minimal entailment relation
μ∥=_{S}  Minimal psychological entailment
μ|∼_{S}  Minimal psychological derivability
ν  Transition minimization operator (“nearest”)
Σ  Set of closed term substitutions
<_{G}  Well-ordering of G
⪯  Comparison of transition sizes
{≺ \atop S}  Comparative similarity relation about S
△  Symmetric set difference
<  Extensions of sets
<·  Admissible extensions
⌈ ⌉  Quasi-quotes
A \\ B ∥− C  Reason interpretation
⊢  Deducibility relation
μ⊢  Circumscriptive deducibility relation
⊧  Entailment relation
μ⊧  Minimal entailment relation
|∼  Psychological arguability relation
∥=_{S}  Psychological entailment relation in S
|∼_{S}  Psychological derivability relation
μ∥=_{S}  Minimal psychological entailment
μ|∼_{S}  Minimal psychological derivability
⊕  Direct (disjoint) sum
×  Direct (Cartesian) product
⊖  “Meta-negation,” see §48
⊙  “Meta-disjunction,” see §48
#P  Class of non-deterministic polynomial time countable functions