Elementary definition of Restricted Entailment and some related categories
Lee Flax – 18 February 2009
Assume that agent reasoning is done by semantic entailment: a set of sentences X entails a set of sentences Y if every semantic structure that satisfies all of X also satisfies all of Y. This presents problems for agents because they are bounded by finite resources: of computational power, time, storage capacity, etc. So semantic checking of entailment is not generally possible by a finite agent. This leads to the idea of "restricted entailment", where, by definition, semantic checking is done only over a subset of structures. (If the subset is finite and the language suitably constrained, then the restricted entailment is computable.)
In logic, restricted entailment is defined semantically as follows. Working within a suitable universe of sets, let STRUC be the set of all semantic structures (for a given first-order language). Let W be a subset of STRUC and X a set of first-order sentences. The set of structures modW(X) is defined to be all structures belonging to W that satisfy all of X. Then "X entails Y restricted to W", denoted X|=W Y, if and only if modW(X) is a subset of modW(Y). A restricted entailment is a binary relation defined on sets of first-order sentences. This can be defined categorically in an elementary way by saying X|=W Yif and only if modW(X)>->modW(Y)>->W in the category WET. (Of course, in SET >-> is defined by means of a subobject classifier diagram.)
There is a category SENW with a unique morphism between sets of sentences X and Y if X |=W Y; also there is a category RESENT with objects restricted entailments. There is a unique morphism from |=J to |=I iff |=J is a subset of |=I. RESENT is isomorphic to a certain category of structures FSTRUC, and SENW is equivalent to a category of structures FSTRUCW. The definition of these categories depends on the notion of "fullness" of sets of structures, which in turn depends on the relation of elementary equivalence between structures.
Any restricted entailment |=W is a reflexive, transitive relation on the set of sentences. It defines an equivalence relation, ~, by saying that X~Y iff X|=W Y and Y |=W X. This allows a (pre-)Boolean algebra to be defined on SENW. This can be used to give an algebraic account of AGM belief revision and nonmonotonic entailment (in the context of a belief set K). The algebra can also be used to model some processes in cognitive psychology based in the work of Chris Frith, for example some signs and symptoms of Schizophrenia.
Back