Generalized Quantifiers on Dependent Types: A System for Anaphora Justyna Grudzin´ska, Marek Zawadowski, Instytut Filozofii, Instytut Matematyki, 4 1 Uniwersytet Warszawski 0 [email protected] 2 [email protected] n a February 4, 2014 J 1 3 Abstract ] O We propose a system for the interpretation of anaphoric relationships between L unbound pronouns and quantifiers. The main technical contribution of our proposal . h consists in combining generalized quantifiers with dependent types. Empirically, our t systemallowsauniformtreatmentofalltypesofunboundanaphora,includingtheno- a m toriouslydifficultcasessuchasquantificationalsubordination,cumulativeandbranch- ing continuations, and ’donkey anaphora’. [ 1 2010 Mathematical Subject Classification 03B65, 91F20 v Keywords: dependent type, generalized quantifier, unbound anaphora. 3 3 0 1 Unbound anaphora 0 . 2 In this paper we propose a system for the interpretation of unbound anaphora. The 0 4 phenomenon of unbound anaphora refers to instances where anaphoric pronouns occur 1 outside the syntactic scopes (i.e. the c-command domain) of their quantifier antecedents. : v The main kinds of unbound anaphora are: i X (1) regular anaphora to quantifiers r a (e.g. Most kids entered. They looked happy.) (2) quantificational subordination (e.g. Every man loves a woman. They kiss them.) (3) relative clause ’donkey anaphora’ (e.g. Every farmer who owns a donkey beats it.) (4) conditional ’donkey anaphora’ (e.g. If a farmer owns a donkey, he beats it.) 1 Unbound anaphoric pronouns have been dealt with in two main semantic paradigms: dynamic semantic theories ([Kamp 1981], [Kamp & Reyle 1993], [Groenendijk & Stokhof 1991], [Van den Berg 1996], [Krifka 1996], [Nouwen 2003], [Brasoveanu 2008]) and the E-type/D-type tradition ([Evans 1997], [Neale 1990], [Heim 1990], [Elbourne 2005]). In the dynamic semantic theories pronouns are taken to be (syntactically free, but semantically bound) variables, and context serves as a medium supplying values for the variables. In the E-type/D-type tradition pronouns are treated as quantifiers (definite descriptions constructed from material in the antecedent sentences). Our system combines aspects of both families of theories. As in the E-type/ D-type tradition we treat unbound anaphoric pronouns as quantifiers; as in the systems of dynamic semantics context is used as a medium supplying (possibly dependent) types as their potential quantificational domains. Like Dekker’s Predicate Logic with Anaphora and more recent multidimensional models ([Dekker 1994], [Dekker 2008a]), our system lendsitself tothecompositional treatment ofunboundanaphora, whilekeepingaclassical, static notion of truth. The main novelty of our proposal consists in combining generalized quantifiers ([Mostowski 1957], [Lindstro¨m 1966], [Barwise & Cooper 1981]) with dependent types ([Martin-Lo¨f 1972], [Ranta 1994]). Empirically, our system allows a uniform account of both regular anaphora to quantifiers and the notoriously difficult cases such as quantifica- tionalsubordination,’donkeyanaphora’,andalsocumulativeandbranchingcontinuations. The paper is organized as follows. In Section 2 we introduce in an informal way the main features of our interpretational architecture. In Section 3 we show how to interpret a range of anaphoric data in our system. Finally, sections 4 and 5 define the syntax and semantics of the system. 2 Main features of the system The main elements of our system are: 1. generalized quantifiers together with operations that lift quantifier phrases to chains of quantifiers (i.e. polyadic quantifiers): for capturing the readings available for (multi-) quantifier sentences; 2. context andtypedependency: both(i) fortheinterpretation of language expressions (i.e. quantifiers, quantifier phrases, predicates, chains and sentences) and (ii) for modeling the dynamic aspects of quantification. 2.1 Context, types and dependent types The variables of our system are always typed. We write x : X to denote that the variable x is of type X and refer to this as a type specification of the variable x. Types, in this paper, are interpreted as sets. We write the interpretation of the type X as kXk. Types can depend on variables of other types. Thus, if we already have a type speci- fication x : X, then we can also have type Y(x) depending on the variable x and we can declare a variable y of type Y by stating y : Y(x). The fact that Y depends on X is modeled as a projection π :kYk→ kXk. So that if the variable x of type X is interpreted 2 as an element a ∈ kXk, kYk(a) is interpreted as the fiber of π over a (the preimage of {a} under π), i.e.: kYk(a) = {b ∈kYk :π(b) = a}. One standard natural language example of such a dependence of types is that if m is a variable of the type of months M, there is a type D(m) of the days of the month m. If we interpret type M as a set kMk of months, then we can interpret type D as a set of days of months in kMk, i.e. as a set of pairs: kDk = {ha,ki : a ∈ kMk, k is (the numberof)a day in month a} equipped with the projection π : kDk → kMk. The particular sets kDk(a) of the days of the month a can be recovered as the fibers of this projection: kDk(a) = {d ∈kDk : π(d) = a}. Suchtypedependenciescanbenested,i.e.,wecanhaveasequenceoftypespecifications of the (individual) variables: x :X,y : Y(x),z : Z(x,y) Context for us is a partially ordered sequence of type specifications of the (individual) variables and it is interpreted as a parameter space, i.e. as a set of compatible n-tuples of elements of the sets corresponding to the types involved (compatible wrt all projections). For the definitions of context and dependent types, see Sections 4.2 (syntax) and 5.1 (semantics). 2.2 Quantifiers, quantifier phrases and predicates Our system defines quantifiers and predicates polymorphically. A generalized quantifier associates to every set Z a subset of the power set of Z 1: kQk(Z) ⊆ P(Z) The interpretation kPk of an n-ary predicate P associates to a tuple of sets Z~ = hZ ,...,Z i a subset of the cartesian product of the sets involved 2: 1 n kPk(Z~)⊆ Z ×...×Z . 1 n Quantifier phrases, e.g. every man or some woman, are interpreted as follows: kevery k= {kmank} m:man ksome k = {X ⊆ kwomank : X 6= ∅} w:woman As an element of the denotation of a quantifier phrase like every man or some woman is homogeneous containing only men or women, we do not need to consider notions such as ”live on” and ”witness set” (for comparison, see [Barwise & Cooper 1981]). The definitions of quantifiers, quantifier phrases and predicates are introduced and generalized to dependent types in Sections 4.4, 4.5 (syntax) and 5.3, 5.4 (semantics). 1Such an association might be required to satisfy some additional conditions (like invariance under bijections), but we shall not consider thisissue here. 2Wemay allow such an association to bepartial. 3 2.3 Chains of quantifiers and sentences Theinterpretationofquantifierphrasesisfurtherextendedintotheinterpretationofchains of quantifiers. Consider an example in (1): (1) Two examiners marked six scripts. Multi-quantifier sentences such as (1) have been known to be ambiguous with different readings correspondingto how various quantifiers are semantically related in the sentence. Thus a sentence like (1) admits of two scope-dependent readings where each of the two examiners marked six scripts (two examiners with wide scope), or where each of the six scripts was marked by two examiners (six scripts with wide scope). There are also two further readings claimed for (1): the cumulative reading saying that each of the two examiners marked at least one of the six scripts, and each of the six scripts was marked by at least one of the two examiners, and the branching reading which says that each of the two examiners marked the same set of six scripts. To account for the readings available for such multi-quantifier sentences, we raise quantifier phrases to the front of a sentence to form (generalized) quantifier prefixes - chains of quantifiers. Chains of quantifiersarebuiltfromquantifierphrasesusingthreechain-constructors: pack-formation rule (?,...,?), sequential composition ?|?, and parallel composition ? . The semantical ? operations that correspond to the chain-constructors (known as cumulation, iteration and branching)captureinacompositionalmannercumulative, scope-dependentandbranching readings, respectively. The idea of chain-constructors and the corresponding semantical operations builds on Mostowski’s notion of quantifier ([Mostowski 1957]) further generalized by Lindstro¨m to a so-called polyadic quantifier ([Lindstro¨m 1966]). (See [Bellert & Zawadowski 1989], compare also [Keenan 1987], [Van Benthem 1989], [Keenan 1992], [Keenan 1993], [Westerst˚ahl 1994]). To use a familiar example, a multi-quantifier prefix like ∀ |∃ m:M w:W is thought of as a single two-place quantifier obtained by an operation on the two single quantifiers, and has as denotation: k∀ |∃ k= {R ⊆ kMk×kWk : {a ∈ kMk : {b ∈ kWk: ha,bi ∈ R}∈ k∃ k} ∈ k∀ k}. m:M w:W w:W m:M The three chain-constructors and the corresponding semantical operations are introduced and generalized to (pre-) chains defined on dependent types in Sections 4.6, 4.7 (syntax) and 5.4 (semantics). Finally, a sentence with a chain of quantifiers Ch = Ch and predicate P = P(~y), ~y:Y~ Ch P(~y), is true iff the interpretation of the predicate (i.e. some set of compatible ~y:Y~ n-tuples) belongs to the interpretation of the chain (i.e. some family of sets of compatible n-tuples). For the definitions of a sentence and validity, see Sections 4.8 (syntax) and 5.5 (semantics). 3 Dynamic extensions of contexts In this section weintroducefurtherelements of ourinterpretational architecture by way of showing how to interpret a range of anaphoric data in our system: quantificational subor- dination(3.1), nesteddependencies(3.2), regularanaphoratoquantifiers(3.3), cumulative 4 and branching continuations (3.4) and donkey anaphora of both the relative clause and conditional varieties (Section 3.5). 3.1 Quantificational subordination Let us begin by considering an example in (1): (1) Every man loves a woman. They kiss them. We build the representation of the first sentence in (1): L(∀ ,∃ ). m:M w:W Sentences of English, contrary to sentences of our formal language, are often ambiguous. Hence one such representation can be associated with more than one sentence in our formal language. The next step thus involves disambiguation. We take quantifier phrases of a given representation and organize them into all possible chains of quantifiers (with some restrictions imposed on particular quantifiers). The disambiguation process will not concern us here, but see [Bellert & Zawadowski 1989] for the extensive discussion of the restrictions on particular quantifiers concerning the places in prefixes at which they can occur 3. In our system language expressions (i.e. quantifiers, quantifier phrases, predicates, (pre-) chains, and sentences) are all defined in context. Thus the first sentence in (1) (on the most natural interpretation where a woman depends on every man) translates into a sentence with a chain of quantifiers in a context: Γ ⊢ ∀ |∃ L(m,w), m:M w:W and says that the set of pairs, a man and a woman he loves, has the following prop- erty: the set of those men that love some woman each is the set of all men. The way to understand the second sentence in (1) (i.e., the anaphoric continuation) is that every man kisses the women he loves rather than those loved by someone else. Thus the first sentence in (1) must deliver some internal relation between the types corresponding to the two quantifier phrases. This observation presents a case of quantificational subordi- nation and is well-known from the dynamic semantics literature ([Kamp & Reyle 1993], [Van den Berg 1996], [Krifka 1996], [Nouwen 2003]). In our system the first sentence in (1) extends the context Γ by adding new variable specifications on newly formed types for every quantifier phrase in the chain: Ch= ∀ |∃ . m:M w:W For thepurposeof theformation of suchnewtypesweintroduceanew type constructor T(seethedefinitioninSection4.9). Thatis,thefirstsentencein(1)(denotedasϕ)extends the context by adding: t :T ; t : T (t ) ϕ,∀m ϕ,∀m:M ϕ,∃w ϕ,∃w:W ϕ,∀m 3In connection with complex sentences, we just add one furtherqualification: the scope of a quantifier is always clause-bounded. 5 The interpretation of types (that correspond to the quantifier phrases in the chain Ch) from the extended context Γ are defined in a two-step procedureusing the inductive ϕ clauses throughwhichwedefineChbutinthereversedirection (for theformaldescription of the procedure, see Section 5.6). Step 1. We define fibers of new types by inverse induction. Basic step. For the whole chain Ch= ∀ |∃ we put: m:M w:W kT k := kLk. ϕ,∀m:M|∃w:W Inductive step. kT k = {a ∈ kMk : {b ∈ kWk : ha,bi ∈ kLk} ∈ k∃ k} ϕ,∀m:M w:W and for a ∈kMk kT k(a) = {b ∈ kWk : ha,bi ∈kLk} ϕ,∃w:W Step 2. We build dependent types from fibers. kT k = {a ∈ kMk : {b ∈ kWk : ha,bi ∈ kLk} ∈ k∃ k} ϕ,∀m:M w:W kTϕ,∃w:Wk= [{{a}×kTϕ,∃w:Wk(a) : a ∈ kTϕ,∀m:Mk} Thus the first sentence in (1) extends the context by adding the type T , interpreted ϕ,∀m:M askT k(i.e.thesetofmenwholove somewomen,inthiscasethissetamountstothe ϕ,∀m:M entire set of men), and the dependent type T (t ), interpreted for a ∈ kT k ϕ,∃w:W ϕ,∀m ϕ,∀m:M as kT k(a) (i.e. the set of women loved by the man a). ϕ,∃w:W Unbound anaphoric pronounsareinterpretedwithreferencetothecontextcreated by the foregoing text: they are treated as universal quantifiers andnewly formed (possibly dependent) types incrementally added to the context serve as their potential quantifica- tional domains. That is, unbound anaphoric pronouns they and them in the second m w sentence of (1) have the ability to pick up and quantify universally over the respective interpretations. We represent the anaphoric continuation in (1) as K(∀tϕ,∀m:Tϕ,∀m:M,∀tϕ,∃w:Tϕ,∃w:W(tϕ,∀m)). It translates into: Γϕ ⊢ ∀tϕ,∀m:Tϕ,∀m:M|∀tϕ,∃w:Tϕ,∃w:W(tϕ,∀m)K(tϕ,∀m,tϕ,∃w), where: k∀tϕ,∀m:Tϕ,∀m:M|∀tϕ,∃w:Tϕ,∃w:W(tϕ,∀m)k = {R ⊆ kTϕ,∃w:Wk : {a ∈ kTϕ,∀m:Mk : {b ∈kTϕ,∃w:Wk(a) : ha,bi ∈ R} ∈k∀tϕ,∃w:Tϕ,∃w:W(tϕ,∀m)k(a)} ∈ k∀tϕ,∀m:Tϕ,∀m:Mk}, yielding the correct truth conditions Every man kisses every woman he loves. 6 3.2 Nested dependencies As the type dependencies can be nested, our analysis can beextended to sentences involv- ing three and more quantifiers. Consider examples in (2a) and (2b): (2a) Every student bought most professors a flower. They will give them to them tomor- row. (2b) Every student bought most professors a flower. They picked them carefully. We represent the first sentence in (2a) and (2b) as B(∀ ,Most ,∃ ). This sentence s:S p:P f:F (on the interpretation where a flower depends on most professors that depends on every student) translates into a sentence: Γ ⊢ ∀ |Most |∃ B(s,p,f), s:S p:P f:F and by the process of dynamic extension updates the context by adding new variable specifications on newly formed types for every quantifier phrase in Ch: t : T ; t :T (t ); t : T (t ,t ) ϕ,∀s ϕ,∀s:S ϕ,Mostp ϕ,Mostp:P ϕ,∀s ϕ,∃f ϕ,∃f:F ϕ,∀s ϕ,Mostp We now apply our interpretation procedure. Step 1. Basic step. For the whole chain Ch= ∀ |Most |∃ we put: s:S p:P f:F kT k := kBk. ϕ,∀s:S|Mostp:P|∃f:F Inductive step. kT k = {a ∈ kSk : {b ∈ kPk : {c ∈ kFk : ha,b,ci ∈ kBk} ∈ k∃ k} ∈ kMost k} ϕ,∀s:S f:F p:P and for a ∈kMk kT k(a) = {b ∈ kPk : {c ∈ kFk : ha,b,ci ∈ kBk} ∈ k∃ k} ϕ,Mostp:P f:F and for a ∈kMk and b ∈ kPk kT k(a,b) = {c ∈ kFk : ha,b,ci ∈ kBk} ϕ,∃f:F Step 2. kT k = {a ∈ kSk : {b ∈ kPk : {c ∈ kFk : ha,b,ci ∈ kBk} ∈ k∃ k} ∈ kMost k} ϕ,∀s:S f:F p:P kTϕ,Mostp:Pk = [{{a}×kTϕ,Mostp:Pk(a) :a ∈ kTϕ,∀s:Sk} kTϕ,∃f:Fk = [{{ha,bi}×kTϕ,∃f:Fk(a,b) : a ∈ kTϕ,∀s:Sk,b ∈ kTϕ,Mostp:Pk(a)} 7 Thus the first sentence in (2a) and (2b) extends the context by adding the type T in- ϕ,∀s:S terpreted askT k(i.e. thesetof studentswhoboughtformosthisprofessorsaflower), ϕ,∀s:S the dependent type T (t ), interpreted for a ∈ kT k as kT k(a) (i.e. ϕ,Mostp:P ϕ,∀s ϕ,∀s:S ϕ,Mostp:P the set of professors for whom the student a bought flowers), and another dependent type T (t ,t ), interpreted for a ∈ kT k and b ∈ kT k(a) as ϕ,∃f:F ϕ,∀s ϕ,Mostp ϕ,∀s:S ϕ,Mostp:P kT k(a,b) (i.e. the set of flowers that the student a bought for the professors b). ϕ,∃f:F In the second sentence of (2a) the three pronouns they , them , and them quantify s p f universally over the respective interpretations. We represent the anaphoric continuation in (2a) as: G(∀tϕ,∀s:Tϕ,∀s:S,∀tϕ,Mostp:Tϕ,Mostp:P(tϕ,∀s),∀tϕ,∃f:Tϕ,∃f:F(tϕ,∀s,tϕ,Mostp)). It translates into: Γϕ ⊢∀tϕ,∀s:Tϕ,∀s:S|∀tϕ,Mostp:Tϕ,Mostp:P(tϕ,∀s)|∀tϕ,∃f:Tϕ,∃f:F(tϕ,∀s,tϕ,Mostp)G(tϕ,∀s,tϕ,Mostp,tϕ,∃f), where: k∀tϕ,∀s:Tϕ,∀s:S|∀tϕ,Mostp:Tϕ,Mostp:P(tϕ,∀s)|∀tϕ,∃f:Tϕ,∃f:F(tϕ,∀s,tϕ,Mostp)k= {R ⊆ kTϕ,∃f:Fk : {a ∈kT k :{b ∈ kT k(a) : {c ∈ kT k(a,b) : ha,b,ci ∈ R} ϕ,∀s:S ϕ,Mostp:P ϕ,∃f:F ∈ k∀tϕ,∃f:Tϕ,∃f:F(tϕ,∀s,tϕ,Mostp)k(a,b)} ∈ k∀tϕ,Mostp:Tϕ,Mostp:P(tϕ,∀s)k(a)} ∈k∀tϕ,∀s:Tϕ,∀s:Sk}, yielding the correct truth conditions Every student will give the respective professors the respective flowers he bought for them. In the second sentence of (2b) the pronoun them quantifies universally over the set f of flowers that the student a ∈ kT k bought for the professors b ∈ kT k(a), ϕ,∀s:S ϕ,Mostp:P so in order to be able to refer to such a set we need to use a type constructor Σ (for the definition of Σ-type and its interpretation, see Sections 4.3 and 5.2): Σtϕ,Mostp:Tϕ,Mostp:P(tϕ,∀s)Tϕ,∃f:F(tϕ,∀s,tϕ,Mostp) To accommodate all of the extra processes needed to obtain a new context out of the old one we introduce a refresh operation. The refresh operation will include: addition of variable specifications on presupposed types (where by presupposed types we understand types belonging to the relevant common ground shared by the speaker and hearer); , P Q of the types given in the context, etc (see Section 4.10). Thus in our example the refresh operation applies so as to update the context by adding a new variable specification on a newly formed -type (abbrev. T ): P ϕ,Σ t :T ; t : T (t ) ϕ,∀s ϕ,∀s:S ϕ,Σ ϕ,Σ ϕ,∀s We represent the anaphoric continuation in (2b) as P(∀tϕ,∀s:Tϕ,∀s:S,∀tϕ,Σ:Tϕ,Σ(tϕ,∀s)). It translates into: Γϕ ⊢∀tϕ,∀s:Tϕ,∀s:S|∀tϕ,Σ:Tϕ,Σ(tϕ,∀s)P(tϕ,∀s,tϕ,Σ), 8 where k∀tϕ,∀s:Tϕ,∀s:S|∀tϕ,Σ:Tϕ,Σ(tϕ,∀s)k = {ha,ci : a ∈ kTϕ,∀s:Sk, c∈ kTϕ,Σk : {a ∈ kTϕ,∀s:Sk : {c ∈ kTϕ,Σk(a) :ha,ci ∈ R}∈ k∀tϕ,Σ:Tϕ,Σ(tϕ,∀s)k(a)} ∈ k∀tϕ,∀s:Tϕ,∀s:Sk}. yielding the correct truth conditions Every student picked every flower he bought for most his professors carefully. 3.3 Regular anaphora to quantifiers Consider an example in (3): (3) Most kids entered. They looked happy. Regarding (3), the well-known observation from the dynamic semantics literature is that the anaphoric pronoun they refers to the so-called ”scope set”, i.e. the entire set of kids who entered ([Kamp & Reyle 1993], [Nouwen 2003], [Van den Berg 1996]). We represent the first sentence in (3) as E(Most ). The representation is unam- k:K biguous. It translates into a sentence: Γ ⊢ Most E(k), k:K and extends the context by adding: t :T ϕ,Mostk ϕ,Mostk:K Since in this case the chain involved contains a single quantifier phrase Ch = Most , k:K we put kT k:= kEk ϕ,Mostk:K The pronoun they in the second sentence quantifies universally over the set kEk, yielding the correct truth-conditions for the anaphoric continuation Every kid who entered looked happy. 3.4 Cumulative and branching continuations Dynamic extensions of contexts and their interpretation are also defined for cumulative and branching continuations (for the definitions, see 5.6). Consider examples in (4a) and (4b): (4a) Last year three scientists wrote (a total of) five articles (between them). They pre- sented them at major conferences. (4b) Last year three scientists (each) wrote (the same) five articles. They presented them at major conferences. Asdiscussedin[Krifka 1996],[Dekker 2008b],thedynamicsofthefirstsentencein(4a)and (4b) can deliver some (respectively: cumulative or branching) internal relation between the types corresponding to three scientists and five articles that can be elaborated upon in the anaphoric continuation. 9 We represent the first sentence in (4a) and (4b) as W(Three ,Five ). Interpreted s:S a:A cumulatively, as in (4a), it translates into a sentence: Γ ⊢ (Three ,Five ) W(s,a). s:S a:A Interpreted in a branching fashion, as in (4b), it translates into a sentence: Three s:S Γ ⊢ W(s,a). Five a:A The anaphoric continuation in (4a) can be interpreted in what Krifka calls a ”cor- respondence” fashion (see [Krifka 1996]). For example, Dr. Smith wrote one article, co-authored two more with Dr. Nelson, who co-authored two more with Dr. Slack, and the scientists that cooperated in writingone or morearticles also cooperated in presenting these (and no other) articles at major conferences. On our analysis, the first sentence in (4a) extends the context by adding the type corresponding to (Three ,Five ): s:S a:A t :T , ϕ,(Threes,Fivea) ϕ,(Threes:S; Fivea:A) interpreted as a set of tuples kT k = {hc,di | c∈ kSk and d ∈kAk : c wrote d} ϕ,(Threes:S,Fivea:A) The anaphoric continuation then quantifies universally over this type (i.e. a set of pairs): Γ ⊢∀ P(t ), ϕ tϕ,(Threes,Fivea) ϕ,(Threes,Fivea) yielding the desired truth-conditions The respective scientists cooperated in presenting at major conferences the respective articles that they cooperated in writing The anaphoric continuation in (4b) can be interpreted in a branching fashion. For example, Dr. Smith, Dr. Nelson and Dr. Slack all co-authored all of the five articles, and all of the scientists involved presented at major conferences all of the articles involved. On our analysis, the first sentence in (4b) extends the context by adding: t : T ; t :T , ϕ,Threes ϕ,Threes:S ϕ,Fivea ϕ,Fivea:A where: kT k∈ kThree k ϕ,Threes:S s:S kT k ∈ kFive k. ϕ,Fivea:A a:A and moreover: kT k= kT k× kT k, ϕ,Threes:S ϕ,Threes:S ϕ,Fivea:A Fivea:A The anaphoric continuation then quantifies universally over the respective types: ∀ t Γ ⊢ ϕ,ThreesP(t ,t ), ϕ ∀ ϕ,Threes ϕ,Fivea tϕ,Fivea yielding the desired truth-conditions All of the three scientists cooperated in presenting at major conferences all of the five articles that they co-authored 10