=Paper=
{{Paper
|id=Vol-2052/paper9
|storemode=property
|title=Predications, Fast and Slow
|pdfUrl=https://ceur-ws.org/Vol-2052/paper9.pdf
|volume=Vol-2052
|authors=Tim Fernando
|dblpUrl=https://dblp.org/rec/conf/commonsense/Fernando17
}}
==Predications, Fast and Slow==
https://ceur-ws.org/Vol-2052/paper9.pdf
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.