Predications, fast and slow Tim Fernando Trinity College Dublin, Ireland Tim.Fernando@tcd.ie Abstract hypothesizes the bulk of reasoning is of the quick “recognize and react” variety, implicating the efficient algorithms of as- Notions of predication based on extensional and in- sociative networks, as opposed to the ponderous mechanisms tensional subsumption, as described by Woods, are of logic. In a similar vein, the psychologist Daniel Kahne- related to Kahneman’s systems of thinking fast and man argues that thinking operates largely under a fast sys- slow. Path-based reasoning with links is applied to tem, breakdowns in which trigger a second slower system that predication over not only individuals but (follow- would otherwise lie dormant [Kahneman, 2011]. Woods and ing Carlson) kinds and stages/time. Predications, Kahneman independently suggest commonsense reasoning is fast and slow, are formulated in monadic second- often easy but at times hard. order logic over strings, analyzed in Goguen and The fast/slow intensional/extensional contrasts are taken Burstall’s institutions. up together below, starting in §2 with Formal Concept Analy- sis [Ganter and Wille, 1999] for a tight conceptual pairing of 1 Introduction extension and intension (shortened there to extent and intent). Well-known complications in predication point to a loosen- In his ACL Lifetime Achievement Award lecture, William ing of that pairing, paving paths in §3 to logical systems in §4 Woods contrasts two competing traditions in Knowledge that Goguen and Burstall [1992] call institutions. Institutions Representation for Natural Language Understanding based on monadic second-order logic over strings are defined, 1. logical reasoning, which is rigorous and formal, but providing a uniform path-based account of predication over often counterintuitive, and which has algorithms that kinds and stages in the sense of Carlson [1977], with monadic match expressions, substitute values for variables, and second-order variables ranging over paths, and many models invoke rules, and reduced to finite ones, amenable to finite-state methods. The 2. associative networks, which are structured and intuitive, bias What you see is all there is (WYSIATI) from Kahneman but typically informal; however, they support efficient [2011] is formulated as a satisfaction condition characteris- algorithms that follow paths through links to draw con- tic of institutions. Reasoning may slow down due to adjust- clusions ments within an institution or perhaps worse, changes of in- stitutions. The former explores unknowns that are known to [Woods, 2010, page 625]. These traditions offer different per- an institution, while the latter arises from unknown unknowns spectives on concepts and subsumption v between concepts. (to borrow Donald Rumsfeld’s words). The custom in logic is to interpret a concept C as a set [[C]] of C-instances, called its extension (under [[·]]), with C sub- sumed by a more general concept C 0 , C v C 0 , when every 2 Formal Concept Analysis and partiality C-instance is a C 0 -instance To bring out a notion of intension buried in purely extensional C v C 0 under [[·]] ⇐⇒ [[C]] ⊆ [[C 0 ]] (1) accounts, FCA defines a context to be a triple hO, A, Hi con- sisting of [Baader et al., 2003]. Rejecting the reduction of a concept (i) a set O of objects d, d0 , . . ., to its extension, Woods advocates a notion of intension that “is as much a psychological issue as a logical issue” [Woods, (ii) a set A of attributes a, a0 , . . ., and 2007, page 83]. Woods steps away from arbitrary instances (iii) a binary relation H ⊆ O × A specifying the attributes given by some interpretation [[·]] to a carefully crafted con- a in A that an object d in O has (so dHa can be read: ceptual taxonomy, for an intensional subsumption quicker to object d has attribute a). compute than the extensional notion specified by (1).1 Woods Now fix a context hO, A, Hi. The extent of a set A ⊆ A of 1 Analyzing intension as a function from indices (or points of attributes is the set reference) to extensions [Carnap, 1947; Montague, 1974] arguably only compounds (1), multiplying notions of instance by indices. AH := {d ∈ O | (∀a ∈ A) dHa} of objects that have every attribute in A, while the intent of a a plausible candidate for M(dHa) is the negation ¬(dHa) set D ⊆ O of objects is the set expressing the absence of contrary information. Were it the case that DH := {a ∈ A | (∀d ∈ D) dHa} dHa ⇐⇒ ¬(dHa) (5) of attributes that every object in D has. The notions of extent and intent constitute an antitone Galois connection inasmuch (4) would be vacuous, as ¬(dHa) reduces to the conclusion as for every D ⊆ O and A ⊆ A, dHa of (4). But (5) cannot hold in a context hO, A, Hi with a bird that flies and another that doesn’t, D ⊆ AH ⇐⇒ A ⊆ DH . (2) neither bird H fly nor bird H fly The inclusions ⊆ in (2) are strengthened into equalities in defining a concept to be a pair (D, A) such that D = AH and exposing a sense in which H is partial, and pushing us beyond A = DH . Equivalently, a concept is a subset A of A such that H if, as commonsense demands, we are to make anything of A = (AH )H (replacing D by AH , to focus on attributes). Re- (4). ducing extension to extent, extensional subsumption (as de- scribed in §1) between concepts A and A0 is just inclusion of 3 Varieties of predication and causal paths extents What could birds fly mean when plainly some birds don’t? A vH A0 ⇐⇒ AH ⊆ A0H The linguist Greg Carlson contrasts two views of generic sen- which, in view of (2), is the converse of inclusion of intents tences, an inductive approach based on observed instances, and a “rules and regulations” view emphasizing not so much A vH A0 ⇐⇒ A0 ⊆ A. their “episodic instances but rather the causal forces behind those instances” [Carlson, 1995, page 225]. The latter causal We can turn an attribute or object x ∈ A ∪ O unambiguously approach (which Carlson favors) is broadly in line with the into a concept  proposal made in Steedman [2005] that causality and goal- {x}H if x ∈ O directed action lie at the heart of temporal semantics. A sim- concept(x) := ple example of goal-directed action is expressed by the pred- ({x}H )H if x ∈ A ication die(tweety), which overturns the temporal proposition assuming A ∩ O = ∅, and then for x0 ∈ A ∪ O, define alive(tweety). The proposition alive(tweety) is inertial inas- much as it persists in the absence of a force overturning it — x is aH x0 ⇐⇒ concept(x) vH concept(x0 ) or to bring out the similarity with (4), so that for d ∈ O and a ∈ A, alive(tweety)@t t S t0 ¬opp(alive(tweety)@t) d is a H a ⇐⇒ dHa (6) alive(tweety)@t0 and for d0 ∈ O, where d is aH d0 ⇐⇒ {d0 }H ⊆ {d}H . (i) alive(tweety)@t says “alive(tweety) holds at time t” The =⇒-half of the last biconditional is the inference rule (ii) t S t0 says “t is succeeded (temporally) by t0 ” d0 Ha d is aH d0 (iii) opp(ψ) says “some force opposes ψ” (3) dHa whence ¬opp(ψ) says “no force opposes ψ.” for property inheritance. Shortcomings of (3) are long- For rigour, let us associate with every attribute a ∈ A, a standing concerns in Knowledge Representation, a common distinct unary relation symbol Pa , allowing us to encode an example being that (a1) to (a3) leave out penguins. FCA-relation H ⊆ O × A as a {Pa }a∈A -model [[·]] over the universe/domain O interpreting Pa as the subset (a1) bird H fly (i.e., birds fly) [[Pa ]] = {d ∈ O | dHa} (a2) tweety is aH bird (i.e., Tweety is a bird) (a3) tweety H fly (i.e., Tweety flies) of O, so that H d ∈ [[Pa ]] ⇐⇒ dHa To accommodate exceptions, let us replace is a by a binary relation IS (left unspecified for the moment) and, following for all d ∈ O. But the point of the relation symbols Pa is Reiter [1980], add an assumption M(dHa) to (3) for not to recreate a particular relation H ⊆ O × A but to move beyond such relations, as described by (4) and (6) above. And d0 Ha d IS d0 M(dHa) central to these moves are the relations IS in (4) and S in (6), (4) dHa for which we introduce a binary relation symbol S. We can with M pronounced “it is consistent to assume” (left implicit then reformulate (4) as the sentence in the :-notation for justifications in Default Logic). Under ih[a] := ∀x∀y((Pa (y) ∧ ySx ∧ ¬Pa (x)) ⊃ Pa (x)) (4), (a3) follows from (a1) and tweety IS bird only with M(a3), which fails when there is information to the contrary of (a3). saying a is inherited through S in the absence of information Now, assuming a comes with a contrary attribute a ∈ A, a to the contrary (assuming a ∈ A). S inverts IS in ih[a] for uniformity with S in (6), which we generalize to a as the where Sa∗ expresses the reflexive transitive closure of the re- inertial requirement striction Sa of S to pairs (x1 , x2 ) such that not Pa (x2 ) ir[a] := ∀x∀y((Pa (y) ∧ ySx ∧ ¬Po(a) (y)) ⊃ Pa (x)) Sa := λx1 λx2 (x1 Sx2 ∧ ¬Pa (x2 )). Now, whether or not ih[a] is true at a model [[·]], the aforemen- assuming an attribute o(a) ∈ A for an a-opposing force. An tioned assumptions about Pa+ make ih[a+ ] true at [[·]] with obvious choice for o(alive(tweety)) is die(tweety), which de- a+ = a. Put another way, ih[a] is satisfied by a model [[·]]+ scribes an event that terminates the state alive(tweety). The identical to [[·]] except possibly at Pa , where distinction between events and states is critical to temporal se- mantics [Kamp and Reyle, 1993; Allen and Ferguson, 1994], [[Pa ]]+ := [[Pa+ ]]. with ir[a] suited as a requirement for a equal to alive(tweety) As for the inertial sentence ir[a], we introduce, in place of a+ but not for die(tweety). Further evidence for the significance for ih[a], an attribute ao with Pao given by of the event/state divide is the ∃/∀-contrast illustrated by (a4) Pao (y) ySx ¬Po(a) (y) Pa (x) and (a5). (8) Pao (x) Pao (x) (a4) Tweety flew in his first year. so that Pao (x) says (a5) Tweety was flightless his first five weeks. an Sao -path to x exists from some y such that Pa (y) While some flight by Tweety in his first year is enough to where Sao is the counterpart in ir[a] of Sa make (a4) true, (a5) specifies flightlessness at every instant of his first five weeks. That is, (a4) claims of an interval that a Sao := λx1 λx2 (x1 Sx2 ∧ ¬Po(a) (x1 )). certain event happens within it, while (a5) claims of an inter- Then [[·]]o satisfies ir[a] where [[Pa ]]o := [[Pao ]]. Sa -paths and val that a certain state holds at each instant in it. Inasmuch as Sao -paths alike are causal, implementing the inheritance and states holds at instants, while events happen over intervals, an inertial laws ih[a] and ir[a], respectively. analogy can be drawn with individuals/kinds Looking back at the previous section, it is doubtful FCA- state instant individual intents are what Woods has in mind by intension (as marvel- ≈ ≈ . lous as Galois connections are). Accordingly, we trade sub- event interval kind sumption vH between intents of FCA-concepts for a pred- Carlson [1977] describes kind-level predicates such as icate symbol S that has many interpretations, in line with widespread that range over kinds, but not over individuals Woods contention that intension is as much psychological as such as Tweety, the failure of (a7) being, as (a8) sugggests, a logical. Insofar as no single interpretation of S on its own sortal error. will do, it is not unreasonable to keep these interpretations as (a6) Birds are widespread. simple as possible. Suppose, for example, [[S]] were given by some finite string d1 · · · dn of n distinct objects di ? (a7) Tweety is widespread. [[S]] = {(di , di+1 ) | 1 ≤ i ≤ n} ? (a8) A typical bird is widespread. and A were finite. Then the construction of [[·]]+ to ensure As presupposition failures, sortal errors are commonly held ih[a] for a in some set Ih ⊆ A of inheritable attributes can be to apply equally to negations, expressed in (5) and ih[a] by implemented by a finite-state transducer transforming a string a, and not to be confused with ¬. To block the leap from A1 · · · An with (a6) to (a7) on the basis of ih(widespread), we must refrain Ai = {a ∈ A | di ∈ [[Pa ]]} from requiring ih[a] of kind-level predicates, just as we re- frain from requiring ir[a] of predicates describing events (for to A01 · · · A0n with which o(a) may not even be defined). That said, the present A0i = {a ∈ A | di ∈ [[Pa ]]+ }. paper focuses on attributes a suited to ih[a] or to ir[a]. Let us agree to call the former inheritable, and the latter inertial. The transducer has subsets of Ih as states q, the empty set as Ensuring an inheritable attribute a satisfies ih[a] or an iner- the initial state, all states final, and transitions tial attribute satisfies ir[a] may call for some repairs on [[Pa ]]. A:A0 q → A0 ∩ Ih where A0 := A ∪ {a ∈ q | a 6∈ A} The repair for ih[a] can be described through a fresh attribute a+ with Pa+ given by two rules so that the current state consists of the inheritable attributes in the last set A0 of attributes returned. Moreover, for a ∈ Ih Pa (x) Pa+ (y) ySx ¬Pa (x) with a ∈ Ih and a = a, we have (7) Pa+ (x) Pa+ (x) [[Pa ]]+ ∩ [[Pa ]]+ = ∅ ⇐⇒ [[Pa ]] ∩ [[Pa ]] = ∅ extending Pa so that Pa+ (x) can be read allowing us to set a+ equal to a+ . As for ir[a] where a be- longs to some set Ir ⊆ A of inertial attributes, we can build a there is an S-path to x avoiding Pa from some y finite-state transducer taking A1 · · · An to Ao1 · · · Aon where such that Pa (y). Aoi = {a ∈ A | di ∈ [[Pa ]]o } That is, Pa+ (x) can be formulated as A:Ao using subsets of Ir as states q, and transitions q → q 0 where ∃y(Pa (y) ∧ ySa∗ x) Ao := A ∪ q and q 0 := {a ∈ Ao ∩ Ir | o(a) 6∈ A}. 4 Predications in flux: an MSO institution MSOA -sentences and MSOA -satisfaction |=A are defined as We step in this section from an FCA context hO, A, Hi up usual in classical predicate logic so that, for example, to an institution hSign, sen, Mod, |=i in the sense of [Goguen A1 · · · An |=A ∃x(Pa (x) ∧ ∀y¬ySx) ⇐⇒ a ∈ A1 and Burstall, 1992], where contexts can be varied system- for all strings A1 · · · An of subsets of A. A fundamental result atically via signatures. The definition of an institution uses is the Büchi-Elgot-Trakhtenbrot theorem [Libkin, 2004, page a modicum of category theory, and is, on first exposure, a 124]: the set mouthful: (i) Sign is a category, with objects Σ called signatures MSOA (ϕ) := {s ∈ (2A )∗ | s |=A ϕ} (ii) sen is a functor from Sign to the category of sets and of strings satisfying an MSOA -sentence ϕ is regular, and functions, with elements of the set sen(Σ) called Σ- conversely, every regular language over the alphabet 2A (of sentences subsets of A) can be obtained this way from some MSOA - sentence ϕ. The use of the powerset 2A as the alphabet of (iii) Mod is a contravariant functor from Sign to the category strings constituting MSOA -models departs from the custom of (small) categories and functors, with Mod(Σ)-objects of A in statements of the Büchi-Elgot-Trakhtenbrot theorem called Σ-models but is crucial when forming an institution where A varies (iv) |= is an indexed family {|=Σ }Σ∈|Sign| of binary rela- [Fernando, 2016].3 tions Let IA be the institution where Sign is the set Fin(A) of |=Σ ⊆ |Mod(Σ)| × sen(Σ) finite subsets A of A partially ordered by ⊆ (for a category), between Σ-models and Σ-sentences, indexed by signa- and for every A ∈ Fin(A), σ tures Σ such that for every Sign-morphism Σ → Σ0 , (i) an A-sentence is an MSOA -sentence, an A-model is Σ0 -model M and Σ-sentence ϕ, a string over the alphabet 2A and |=A is MSOA - M 0 |=Σ0 sen(σ)(ϕ) ⇐⇒ Mod(σ)(M 0 ) |=Σ ϕ. (9) satisfaction (ii) for A ⊆ A0 ∈ Fin(A), sen(A, A0 ) is the inclu- A context hO, A, Hi can be packaged as an institution with sion of MSOA -sentences in MSOA0 -sentences, while exactly one signature Σ, trivializing the category-theoretic re- 0 Mod(A0 , A) intersects a string A01 · · · A0n ∈ (2A )∗ com- quirements above so that the functor sen amounts to ponentwise with A sen(Σ) = A, Mod(A0 , A)(A01 · · · A0n ) := (A01 ∩ A) · · · (A0n ∩ A). the functor Mod to Next, we bring in an FCA-context hO, A, Hi to define for Mod(Σ) = O (understood as a discrete category) every d ∈ O and A ∈ Fin(A), the set and the indexed family |= to A[d] := {a ∈ A | dHa} |=Σ = H. of attributes in A that d has, which we then use to map a string A far more interesting institution associated with hO, A, Hi d1 · · · dn ∈ O∗ to the string pieces together finite fragments of hO, A, Hi on which the A[d1 · · · dn ] := A[d1 ] · · · A[dn ] S-paths behind a+ and ao in §3 tread. Some preliminary def- initions help make this precise. Given a finite subset A of over the alphabet 2A . Let I(O, A, H) be the institution A, with the same signature category and sentence functor as IA , (i) the fragment MSOA of Monadic Second-Order logic but with a string d1 · · · dn ∈ On as an A-model that |=A - over strings [e.g., Libkin, 2004] is given by a binary satisfies an MSOA -sentence ϕ precisely if A[d1 · · · dn ] |=A ϕ predicate symbol S (expressing succession) and a unary (in MSOA ). That is, I(O, A, H) picks out the A-models predicate symbol Pa for each a ∈ A A1 · · · An in IA given by strings d1 · · · dn and H (ii) an MSOA -model h[n], Sn , {[[Pa ]]}a∈A i with domain Ai = {a ∈ A | di Ha}. [n] := {1, . . . , n}, But H might be transformed to a different FCA-context, as we saw in the transformations in §3 of [[·]] to [[·]]+ and [[·]]o to interpreting S as the successor (plus 1) relation satisfy the MSO-sentences Sn := {(i, i + 1) | 1 ≤ i < n} ih[a] := ∀x∀y((Pa (y) ∧ ySx ∧ ¬Pa (x)) ⊃ Pa (x)) on [n], and each Pa as a subset [[Pa ]] of [n] can be iden- saying a is inherited unless there is information a to the con- tified with the string A1 · · · An of subsets trary, and Ai := {a ∈ A | i ∈ [[Pa ]]} ir[a] := ∀x∀y((Pa (y) ∧ ySx ∧ ¬Po(a) (x)) ⊃ Pa (x)) of A consisting of attributes a in A with i in the inter- pretation [[Pa ]] of the unary predicate for a.2 saying a persists unless opposed by some force o(a). The requirement ih[a] is suited to attributes a belonging to a set Ih 2 such that Proceeding from the string A1 · · · An , the equations [[Pa ]] = {i ∈ [n] | a ∈ Ai } (a ∈ A) 3 The reason is that the structure h[n], Sn , [[Pa ]]a∈A i encoded by a take us back to h[n], Sn , {[[Pa ]]}a∈A i, justifying the identification of string A1 · · · An over 2A has A-reduct h[n], Sn , [[Pa ]]a∈A i, encoded MSOA -models with strings of subsets of A. by the string (A1 ∩ A) · · · (An ∩ A) over 2A . (Inh) Ih ⊆ A and for each a ∈ Ih, a ∈ Ih and a = a with that computes [[Pa+ ]] for finitely many inheritable a in one pass from A1 down to An . Similarly for inertia and ao . ySx saying: y subsumes x. The institution IA accommodates different FCA-contexts Inertia ir[a] is suited to attributes a belonging to a set Ir such with attribute set A, providing accounts at bounded granu- that larities A ∈ Fin(A) that can be refined or coarsened, as re- (Inr) Ir ⊆ A and for each a ∈ Ir, o(a) ∈ A − Ir, a ∈ Ir and quired. Assuming A is infinite, we can always extend A to a larger finite A-subset A0 ⊇ A, leading, after repeated ex- a = a with tensions, to infinite models at the limit (or, as detailed below, ySx saying: y is followed by x. inverse limit). How smoothly can these extensions be carried out? As a partial answer, clause (iv) in the definition above of We can use a monadic second-order variable X to pick out a an institution provides the biconditional path, defining the MSO{a,a} -formula patha (X) M 0 |=Σ0 sen(σ)(ϕ) ⇐⇒ Mod(σ)(M 0 ) |=Σ ϕ (9) patha (X) := ∀x(X(x) ⊃ (Pa (x)∨ known as the Satisfaction condition [Goguen and Burstall, ∃y(X(y) ∧ ySx ∧ ¬Pa (x)))) 1992]. In the present institution IA , (9) unwinds to by inverting the rules (7) for Pa+ with X in place of Pa+ . A01 · · · A0n |=A0 ϕ ⇐⇒ (A01 ∩ A) · · · (A0n ∩ A) |=A ϕ Then ih[a+ ] follows from the MSO{a,a} -formula whenever A ⊆ A0 ∈ Fin(A), and for every MSOA -sentence ∀x(Pa+ (x) ≡ ∃X(X(x) ∧ patha (X))) (10) ϕ and string A01 · · · A0n of subsets of A0 . In particular, for a fixed sentence ϕ, we can set A to the vocabulary of ϕ, reducing Pa+ (x) to the possibility of putting x in a set X voc(ϕ), defined to be the set of all attributes mentioned in such that patha (X). Similarly, for inertia ir[a] and ao , we ϕ (making voc(ϕ) the smallest subset A of A for which ϕ is invert the rules (8) for Pao with X in place of Pao for an MSOA -sentence). Satisfaction of ϕ by a string A01 · · · A0n pathoa (X) := ∀x(X(x) ⊃ (Pa (x)∨ of subsets of A0 ∈ Fin(A) with voc(ϕ) ⊆ A0 then reduces to satisfaction by the string ∃y(X(y) ∧ ySx ∧ ¬Po(a) (x)))) (A01 ∩ voc(ϕ)) · · · (A0n ∩ voc(ϕ)) to derive ir[ao ] from the reduction of subsets of voc(ϕ). In other words, the attributes we see in ∀x(Pao (x) ≡ ∃X(X(x) ∧ pathoa (X))) (11) ϕ can — as far as the issue of satisfying ϕ (or not) is con- cerned — be assumed to be all there is, in accordance with of Pao to pathoa . The finiteness of [[S]] (or more specifi- the bias What you see is all there is (WYSIATI) from Kahne- cally [[S]]-chains) is crucial to push through the arguments man [2011]. Of course, “what you see” in ϕ depends on what for ih[a+ ] and ir[ao ] above (extracting Sa - and Sao -paths that we put in ϕ. And while, for example, ih[a] mentions only the reach Pa from patha (X) and path◦a (X)). attributes a and a, many more attributes may appear once we For a in Ih or Ir, it is natural to assume a does not co-occur try to spell out what information to the contrary is buried in a with a (not to mention a). In the simplest case, a might be false (i.e., nc[a] := ∀x¬(Pa (x) ∧ Pa (x)) ∀x¬Pa (x)) turning ih[a] into banning contradictions in [[Pa ]] ∩ [[Pa ]]. The reduction (10) above yields the equivalence of nc[a] and nc[a+ ] ∀x∀y((Pa (y) ∧ ySx) ⊃ Pa (x)) nc[a] ≡ nc[a+ ] but the point of ih[a] is to deal with more interesting cases. As Reiter [1980] notes, the list of birds that do not fly is open- provided Pa does not discriminate between S-predecessors ended, expressed below as · · · in the non-well-formed MSO- of the same object formula (12). ∀x∀y∀y 0 (ySx ∧ y 0 Sx ∧ Pa (y) ⊃ Pa (y 0 )) Pbird (x) ⊃ (Pf ly (x) ≡ which follows from the uniqueness of S-predecessors (Ppenguin (x) ∨ Postrich (x) ∨ · · · )) (12) ∀x∀y∀y 0 (ySx ∧ y 0 Sx ⊃ y = y 0 ). The same open-endedness applies to the forces overturning an inertial attribute a, glossed over by the non-inertial attribute Otherwise, nc[a] may hold while nc[a+ ] fails because an ob- o(a) in ir[a]. In practice, simplifying assumptions are adopted ject in [[Pa ]] has the same S-successor as another in [[Pa ]] (dropping, for example, · · · in (12)) to facilitate reasoning. In situations where these assumptions fail, reasoning may break d1 [[S]]d and d2 [[S]]d with d1 ∈ [[Pa ]] and d2 ∈ [[Pa ]]. down. As Shanahan [2016] points out, The same applies to inertia ir[a] and a0 ; nc[a0 ] follows from Because it sometimes jumps to premature conclu- nc[a] and the reduction (11), under the interpretation above of sions, bounded rationality is logically flawed, but S as no more so than human thinking. Sn := {(i, i + 1) | 1 ≤ i < n} Elaborating on the attributes a, a, o(a) is an art in manag- for some positive integer n. As observed at the end of §3, this ing flaws, and recovering from missteps (slowing reasoning interpretation of S allows us to build a finite-state transducer down). Apart from the attributes in A, there is also the binary pred- For A equal to the set of rational numbers, we can express icate symbol S, interpreted as the successor relation Sn on the Dedekind cut construction of a real number r ∈ R as a {1, 2, . . . , n} for some integer n > 0 for either subsumption function fr ∈ lim{bcA } to get a copy of the real line R from ←− (Inh) or temporal precedence (Inr). Widespread views that A restricted to the functions fr (for r ∈ R).4 time branches and is infinite, and similar claims about con- Compression bcA conditioned by A links the ontology [n] ceptual taxonomies raise the question: of an A-model h[n], Sn , {[[Pa ]]}a∈A i to the granularity A. is it not problematic to assume that Consider, for instance, the finite-state transducer above for [[S]] is Sn for some integer n > 0? inheritance, enforcing ih[a] for a ∈ Ih (assumed finite, for It is, if an A-model that interprets S as a finite successor re- convenience). Suppose on input A1 · · · An , this transducer lation is asked to carry on its own the burden of representing outputs the string T (A1 · · · An ). Applying bcIh to this out- an infinite branching structure. But once we adjust our sights put yields the block compression of T ’s output on input from a single context hO, A, Hi for defining concepts to a bcIh (A1 · · · An ) multitude of satisfaction relations |=A capturing finite frag- bcIh (T (A1 · · · An )) = bc(T (bcIh (A1 · · · An ))). ments of a multitude of contexts, the problem arguably dis- solves. If time branches, it is because there is more than one Similarly for inertia and its transducer To , A-model in Mod(A) describing a branch up to A. And if time bcA (To (A1 · · · An )) = bc(To (bcA (A1 · · · An ))) is infinite, it is because no single signature A can represent the totality of signatures in Sign = Fin(A). where A = Ir ∪ {o(a) | a ∈ Ir}. Attention to granular- And exactly how might infinite branching structures ity A pays off in bounding the search space of candidate emerge from these finite approximations? Very briefly, A-models. But before requiring an A-model A1 · · · An is through an inverse limit construction linking vocabulary (A ∈ equal to bcA (A1 · · · An ), we should be clearer about what Fin(A)) with ontology (Mod(A)). More precisely, we work the strings A1 · · · An represent. Common to ih[a] and ir[a] with strings A1 · · · An of subsets of A that are stutterless in is some form of Leibniz’ Principle of Sufficient Reason, no that change (in Pa over S) without a reason, Ai 6= Ai+1 for all 1 ≤ i < n PSR[a] := ∀x∀y((Pa (y) ∧ ySx ∧ ¬Pa (x)) ⊃ xRa y) (the intuition being that a stutter is some substring Ai Ai+1 such that Ai = Ai+1 ). Clearly, a string s of subsets of A is where the reason Ra is reduced to a unary relation stutterless iff s = bc(s) where the block compression bc(s) of  Pa (x) for inheritance (Inh) s is defined by xRa y := Po(a) (y) for inertia (Inr). s if length(s) ≤ 1 ( bc(s) := bc(As0 ) if s = AAs0 PSR[a] with xRa y as Po(a) (y) is essentially an explanation A bc(A0 s0 ) if s = AA0 s0 where A 6= A0 closure axiom [Lifschitz, 2015]. The non-inertial attribute o(a) designates any force opposing a, while a serves in ih[a] (implementing a form of the Aristotelian claim, no time with- as a differentia in a taxonomy, a path in which is picked out by out change). Next, for any A ∈ Fin(A), let bcA : (2A )∗ → an interpretation of S. By placing demands on the signature (2A )∗ be the function intersecting a string A1 · · · An ∈ (2A )∗ A of MSOA , these attributes provide a causal ontology for componentwise with A before destuttering change. It is instructive to eliminate the negation ¬ in PSR[a] bcA (A1 · · · An ) := bc((A1 ∩ A) · · · (An ∩ A)) and ih/ir[a] by moving Pa (x) to the right of the implication ⊃ for a choice (recalling from the definition of IA that whenever A ⊆ A0 ∈ 0 Fin(A), Mod(A0 , A) intersects a string in (2A )∗ componen- (Pa (y) ∧ ySx) ⊃ (Pa (x) ∨ xRa y) twise with A). Now, the inverse limit between Pa (x) and xRa y given Pa (y) and ySx. A bias to- lim{bcA } wards Pa (x) leading to S-paths in §3 amounts to a minimi- ←− sation assumption on reasons and on a domain [n] subject to of the indexed family {bcA }A∈F in(A) of functions is the set bcA . Of course, we can eliminate a stutter in a string not just of functions f : Fin(A) → (2A )∗ such that through bc but by adding an attribute n to A that names a f (A) = bcA (f (A0 )) whenever A ⊆ A0 ∈ Fin(A). unique position This equality ensures that f provides a consistent system of ∀x∀y(Pn (x) ∧ Pn (y) ⊃ x = y) A-approximations f (A) of a structure that is infinite insofar (corresponding to a nominal in Description Logic). But this as for any positive integer n, there is an A ∈ Fin(A) such that goes against the custom of using attributes for universals, f (A) is a string of length > n. For branching in lim{bcA }, ←− 4 Inverse limits aside, the focus of the present work is very much we lift the prefix relation  on strings on the approximations from finite strings, which, under the prefix re- s  s0 ⇐⇒ s0 = ss00 for some string s00 lation , do not form a complete partial order — a basic requirement on domains over which default reasoning is investigated in [Hitzler, to a relation ≺A on lim{bcA } by universal quantification 2004]. These finite strings enjoy a special status as compact ele- ←− ments in algebraic cpo’s. (I am indebted to a referee for bringing f A f 0 ⇐⇒ (∀A ∈ Fin(A)) f (A)  f 0 (A). this paper to my attention.) rather than particulars, and the anti-nominalist thrust of an [Baader et al., 2003] F. Baader, D. Calvanese, D. McGuin- attribute-centered institution IA that constructs individuals ness, D. Nardi, and P. Patel-Schneider. The Description and temporal instants through inverse limits over kinds and Logic Handbook: Theory, Implementation and Applica- temporal intervals (conceived as basic, rather than as sets of tions. Cambridge University Press, 2003. instances and instants). [Carlson, 1977] G.N. Carlson. A unified analysis of the En- glish bare plural. Linguistics and Philosophy, 1(3):413– 5 Conclusion 456, 1977. The account of predication above proceeds from [Carlson, 1995] G.N. Carlson. Truth conditions and generic sentences: two contrasting views. In The Generic Book, (a) an extensional conception of predication as instantiation, pages 224–237. University of Chicago Press, 1995. analyzed in section 2 as extensional subsumption is aH , given a fixed FCA-context hO, A, Hi [Carnap, 1947] R. Carnap. Meaning and Necessity. Univer- sity of Chicago Press, 1947. Second edition 1956. to [Cooper, 2012] R. Cooper. Type theory and semantic in flux. (b) an institution IA in section 4 within which finite frag- In Handbook of Philosophy of Science, Volume 14: Phi- ments of various FCA-contexts are represented by losophy of Linguistics, pages 271–323. Elsevier, 2012. strings A1 · · · An of finite subsets of A, the successor [Fernando, 2016] T. Fernando. On regular languages over relation in which, S, is an intensional alternative to (the converse of) is aH , along which fast path-based reason- power sets. Journal of Language Modelling, 4(1):29–56, ing advocated by Woods [2007] can be carried out. 2016. [Ganter and Wille, 1999] B. Ganter and R. Wille. Formal So what? The move from (a) to (b) challenges the primacy Concept Anaysis: Mathematical Foundations. Springer- accorded to the set of instances of a predicate by the tradi- Verlag, 1999. tional set-theoretic analysis of predication, proposing a shift in focus away from instances towards strings that track mech- [Goguen and Burstall, 1992] J.A. Goguen and R.M. anisms for predication, including inheritance (between in- Burstall. Institutions: abstract model theory for specifi- stances and kinds) and inertia (over time). This is a significant cation and programming. Journal of the Association for shift, support for which can be found in Computing Machinery, 39(1):95–146, 1992. (i) the rules-and-regulations view defended in Carlson [Goguen, 2004] J.A. Goguen. Information integration in in- [1995] that generic statements are about causal forces, stitutions, 2004. https://cseweb.ucsd.edu/∼goguen/pps/ ifi04.pdf. (ii) the proposal from Steedman [2005] that temporality in natural language primiarily concerns the “representation [Hitzler, 2004] P. Hitzler. Default reasoning over domains of causality and goal-directed action,” and concept hierarchies. In KI 2004, pages 351–365. LNAI 3238, Springer, 2004. (iii) the pluralistic perspective promoted in Goguen [2004] [Kahneman, 2011] D. Kahneman. Thinking, Fast and Slow. away from any one isolated context, towards a space of contexts subject to a Satisfaction Condition characteris- Farrar, Straus and Giroux, 2011. tic of institutions, and [Kamp and Reyle, 1993] H. Kamp and U. Reyle. From Dis- course to Logic. Kluwer, 1993. (iv) the notion of “semantics in flux” challenging “the im- pression” from Montague [1974] “of natural languages [Libkin, 2004] L. Libkin. Elements of Finite Model Theory. as being regimented with meanings determined once and Springer, 2004. for all by an interpretation” [Cooper, 2012, page 271]. [Lifschitz, 2015] V. Lifschitz. The dramatic true story of the An institution IA is presented above where the Satisfaction frame default. Journal of Philosophical Logic, 44:163– Condition amounts to What you see is all there is [Kahne- 196, 2015. man, 2011], and notions of inheritance and inertia can be es- [Montague, 1974] R. Montague. Formal Philosophy. Yale tablished through paths described by monadic second-order University Press, 1974. variables within a logic which (by a fundamental theorem [Reiter, 1980] R. Reiter. A logic for default reasoning. Arti- due to Büchi, Elgot and Trakhtenbrot) represents finite-state ficial Intelligence, 13:81–132, 1980. mechanisms (linked above to fast predications). [Shanahan, 2016] M. Shanahan. The frame problem, 2016. Stanford Encyclopedia of Philosophy (E.N. Zalta, ed.), Acknowledgments https://plato.stanford.edu/archives/spr2016/entries/frame- Thanks to three Commonsense-2017 referees for comments. problem/. [Steedman, 2005] M. Steedman. The productions of time, References 2005. Draft tutorial notes about temporal semantics, http:// [Allen and Ferguson, 1994] J. Allen and G. Ferguson. Ac- homepages.inf.ed.ac.uk/steedman/papers.html. tions and events in interval temporal logic. J. Logic and [Woods, 2007] W.A. Woods. Meaning and links. AI Maga- Computation, 4(5):531–579, 1994. zine, 28(4):71–92, 2007. [Woods, 2010] W.A. Woods. The right tools: Reflections on computation and language. Computational Linguistics, 36(4):601–630, 2010.