The paper investigates properties of a non-standard implication \(>\) and its applications in Artificial Intelligence. Statements of the form \(p>q\) are called counterfactuals. Their interpretation does not necessarily coincide with the classic interpretation of \(p\supset q\) for those models \({\mathcal M}\) which satisfy \(\neg p\). The author proposes the following definition of the meaning of the connective \(>\) which extends a propositional language L. (In this review we identify L with the set of all well-formed formulae of L).
Let \(\prec\) be a partial order in the set \({\mathcal P}(L)\) of theories of L, such that \(S\varsubsetneq T\) implies \(S\prec T\) for each \(S,T\in {\mathcal P}(L)\). Let B be a unary predicate on \({\mathcal P}(L)\), let \(S\in {\mathcal P}(L)\), and let \(p\in L\). The set of possible worlds for p in S is defined on page \(46^{11-12}\) as: (1) \(W(p,S)=\{T\subseteq S|\) \(T\nvdash \neg p\), and \(\neg B(T)\), and (\(\forall U\subseteq S)\) (T\(\prec U\) implies \(\neg p\) or B(U)\(\}\). In the reviewed paper B has the intentional meaning of bad world (excluded from consideration), and \(\prec\) is understood as the degree of similarity relation: for T,U\(\subseteq S\), \(T\prec U\) means that U is more similar to S than T is. The set W(p,S) is then used in the definition (page \(46^{13-14})\) of validity of counterfactuals: (2) \(S\vdash_ Gp>q\) iff (\(\forall T\in W(p,S))\) (T\(\vdash p\supset q)\). The author demonstrates (Lemma 4.1) that the interpretation of \(>\) given by (1) and (2) satisfies all the axioms defined by the following schemes attributed to P. Gärdenfors [Acta Philos. Fenn. 30, 381-404 (1978; Zbl 0413.03011)]: (G1) \((p>q)\wedge (p>r)\supset (p>q\wedge r)\); (G2) \(p>true\); (G3) if \(q\supset r\) is an axiom then \((p>q)\supset (p>r)\) is an axiom; (G4) \(p>p\); (G5) if \(p\equiv q\) is an axiom then \((p>r)\supset (q>r)\) is an axiom; (G6) (p\(\wedge q)\supset (p>q)\); (G7) \((p>q)\supset (p\supset q)\); (G8) \((p>r)\wedge (q>r)\supset (p\vee q>r)\). He proves (proof of Theorem 4.2) that under assumption of modularity imposed on relation \(\prec\) also the remaining axiom scheme of Gärdenfors [loc. cit.], (G9) \((p>q)\wedge \neg (p>\neg r)\supset (p\wedge r>q)\), is satisfied. From this, and from the claim (page \(48_{10-11})\) that the system G1...G9 (probably together with modus ponens and tautologies of classic propositional logic) has been demonstrated by Gärdenfors [loc. cit.] to be complete with respect to D. Lewis’s [Counterfactuals. Harvard University Press, Cambridge, MA (1973)] semantics of \(>\), the author draws two conclusions: first, (1) and (2) define an interpretation of \(<\), which is “a slight generalization of Lewis”’ (page \(46_ 7)\), and second, for modular \(\prec\) this interpretation “is identical to Lewis”’ (Theorem 4.2). Moreover, the author proves (Theorem 7.1) that if \(\prec\) coincides with \(\varsubsetneq\), and B(U) is interpreted as \(T\varsubsetneq U\), where T is some fixed subset of S, then for every proposition p the set of all expansions of the default theory (\(\{\) Mq/q\(|\) \(q\in S\setminus T\}\), \(T\cup \{p\})\) in the sense of R. Reiter [Artif. Intell. 13, 81-132 (1980; Zbl 0435.68069)] is generated by W(p,S). The paper contains some other results characterizing the author’s comprehension of counterfactuals, as well as an extensive discussion of their implementational and philosophical aspects. An informal comparison with J. McCarthy’s circumscription [Artif. Intell. 13, 27-39 (1980; Zbl 0435.68073)] is also included.
The lack of explicitly defined semantics of the system presented in the paper seems idiosyncratic. Ignoring complex sentences like \(\neg (p>q)\) in the definition (2) is more serious. Consequently, the fact that the author’s system involves two different interpretations of negation remains implicit. Main theorem 4.2, theorem 7.1, and corollary 8.2 are false. Other results have, at best, incomplete proofs. Here are the details. The proof (pages \(43_{1-2}-44^ 1)\) that for every \(S\subset {\mathcal P}(L)\) there is a maximal subset of S which does not entail \(\neg p\) is invalid. The argument used in the proof holds also for languages with infinitary connectives, but the conclusion does not. Even if this proof was correct it would not suffice to demonstrate the non-emptiness of W(p,S), because despite the author’s intention W(p,S) may be empty (also if \(\prec\) is modular and B universally false). The existence problem, however, has not been taken care of in the paper. This fault invalidated several other proofs. E.g., in the proof of theorem 4.2 the phrase: “such a U exists” (page \(49_ 9)\) is false, and in the second part of the proof of theorem 7.1 the phrase: “all such extensions are of this form” (page \(65^{12})\) is false. The first part of this proof (page \(65^{5-10})\) is incomplete. The author demonstrates only that \(\Gamma\) (U’)\(\subseteq U'\), whereas \(\Gamma (U')=U'\) is necessary. The following observation shows that theorem 4.2 is false. If \(S\nvdash \neg p\) then \(S+(G1...G9)\nvdash p>false\) (to see why, put \(q\leftarrow false\) in G3 and \(q\leftarrow r\) in G7). It is easily seen that the modularity of \(\prec\) does not suffice for the non-emptiness of W(p,S). Of course, if W(p,S) is empty then (2) gives \(S\vdash_ Gp>false\). This also falsifies the statement (page \(46_ 7)\) that the author’s system is more general than Lewis’.
Theorem 4.2 is false, even in finite case with \(\neg B(U)\) holding for every U when W(p,S) is necessarily non-empty. This fact follows from the non-monotonicity of the system defined by (1) and (2). For example, take L with only 2 propositional variables, B(U) false for every U, and \(\prec\) defined by: \(U\prec V\) iff Cn(U) contains fewer non-equivalent propositions than Cn(V) does. \(\prec\) is modular. For \(T=Cn(\neg p\vee q)\) and \(S=Cn(\neg p\vee \neg q)\) we have \(W(p,T)=\{Cn(q)\), Cn(p\(\equiv \neg q)\}\) and \(W(p,S)=\{S\}\). Therefore \(S\vdash_ Gp>\neg q\) and \(T\nvdash_ Gp>\neg q\). Because \(S\subseteq T\), the system defined by (1) and (2) is non-monotonic. On the other hand, it follows from the (incomplete) definition (page \(41^{15-21})\) that Lewis’ system is monotonic, as the system G1...G9 is, i.e. if \(S\subseteq T\) and \(S+(G1...G9)\vdash p\) then \(T+(G1...G9)\vdash p\), for every p, including counterfactuals. Hence neither Lewis’ nor G1...G9 can be equivalent to (1) and (2). (It should be noted that the author uses the term “non- monotonicity” incorrectly. Only for connectives \(\triangleright\) satisfying the deduction theorem, e.g. for standard \(\supset\), the non- monotonicity of \(\vdash_{\alpha}\) is implied by \(S\vdash_{\alpha}p\triangleright r\) and \(S\nvdash_{\alpha}p\wedge q\triangleright r\). Since \(>\) does not satisfy the deduction theorem, \(S\vdash_ Gp>r\) and \(S\nvdash_ Gp\wedge q>r\) do not imply that \(\vdash_ G\) is non-monotonic). The following example shows that theorem 7.1 is false. Put \(T=\{\neg p\}\). In this case W(p,S) is empty, but the default theory (D,T\(\cup \{p\})\) has an extension: the inconsistent theory. Corollary 8.2 is false because for certain S and T satisfying \(S\subseteq T\subseteq Cn(S)\), W(p,S) may be empty while W(p,T) is not. The reason for this is that the predicate B in (1) may distinguish between equivalent theories. This problem would have been avoided if “T\(\subseteq S''\) in (1) had been substituted by “T\(\subseteq Cn(S)''.\)
The author makes interesting suggestions about the origin of some concepts he discusses in his paper. In particular, M. R. Genesereth [Artif. Intell. 24, 411-436 (1984)] received the credit for the hypothesis that “it is possible for machines to be used in automated diagnosis” (page \(57_{4-5})\) of Boolean circuits, and the idea “to index statements with the situations in which they hold, rather than simply view them as being universally true or false” (page \(75^{1-3})\) has been attributed to... Mc Carthy.