Generaliserte Kvantifiserere

Innholdsfortegnelse:

Generaliserte Kvantifiserere
Generaliserte Kvantifiserere
Anonim

Inngangsnavigasjon

  • Inngangsinnhold
  • Bibliografi
  • Akademiske verktøy
  • Venner PDF forhåndsvisning
  • Forfatter og sitatinfo
  • Tilbake til toppen

Generaliserte kvantifiserere

Først publisert man 5. desember 2005; materiell revisjon fredag 26. juli 2019

Generaliserte kvantifiserere er nå standardutstyr i verktøykassene til både logikere og lingvister. Hensikten med denne oppføringen er å beskrive disse verktøyene: hvor de kommer fra, hvordan de jobber og hva de kan brukes til å gjøre. Beskrivelsen er nødvendigvis tegnet, men flere mer omfattende undersøkelser finnes i litteraturen og vil bli referert til når det er hensiktsmessig. For å sette full forståelse av teksten nedenfor, vil grunnleggende fortrolighet med elementær settteoretisk terminologi og med språket i førsteordens logikk være nyttig.

  • 1. Forberedelser
  • 2. Aristoteles
  • 3. Frege
  • 4. Generalisere den universelle og eksistensielle kvantifisereren
  • 5. Generaliserte kvantifiserere av vilkårlige typer
  • 6. Emneutralitet
  • 7. Relativisering
  • 8. Uttrykksmakt
  • 9. Generaliserte kvantifisere og beregning
  • 10. Generaliserte kvantifisere og naturlige språk
  • 11. Konservativitet
  • 12. Utvidelse
  • 13. Symmetri og monotonicity
  • 14. Bestemmere som ikke er ISOM
  • 15. Konstanse
  • 16. Polyadic Natural Language Quantifiers
  • 17. GQ Teori og lingvistikk
  • 18. Kvantifisering og erkjennelse
  • Bibliografi
  • Akademiske verktøy
  • Andre internettressurser
  • Relaterte oppføringer

1. Forberedelser

Begrepet "generalisert kvantifiserer" gjenspeiler at disse enhetene ble introdusert i logikk som generaliseringer av standardkvantifisererne for moderne logikk, (forall) og (exist). [1] I ettertid kan man si at (forall) og (exist) har funnet å være bare to tilfeller av et mye mer generelt kvantifiseringsbegrep, noe som gjør uttrykket “generalisert” overflødig. I dag er det også vanlig å bruke bare "kvantifiserer" for den generelle forestillingen, men "generalisert kvantifiserer" er fremdeles hyppig av historiske grunner. Denne artikkelen bruker begge begrepene, med en tendens til å sette inn "generaliserte" i logiske sammenhenger, og slippe den i språklige sammenhenger.

Vi skiller kvantifiseringsuttrykk fra det de betegner eller betegner, de (generaliserte) kvantifisererne selv. På logiske språk er kvantifiseringsuttrykk variabelt-bindende operatører. Dermed er (exist) den kjente operatøren slik at i en formel (eksisterer x / f), [2] (exist x) binder alle frie forekomster av x i (f). Det betyr kvantifisereren "det finnes" - vi får se nøyaktig hva dette objektet er. På samme måte blir symbolet (Q_0) ofte brukt som en operatør med variabel binding som betyr "det finnes uendelig mange".

På naturlige språk har en rekke uttrykk blitt sett på som kvantifiseringsuttrykk, for eksempel hvert av følgende engelske uttrykk:

alt, ingenting, tre bøker, de ti professorene, John, John og Mary, bare John, brannmenn, hver, minst fem, de fleste, alle unntatt ti, mindre enn halvparten av, John's, noen studenters, nei … bortsett fra Mary, mer mannlige enn kvinnelige, vanligvis, aldri, hverandre. [3]

Hva er da generaliserte kvantifiserere? Før du svarer på dette spørsmålet, er et kort historisk forspill nyttig.

2. Aristoteles

Aristoteles syllogistikk kan sees på som en formell studie av betydningen av de fire grunnleggende kvantifiseringsuttrykkene alle, nei, noen, ikke alle og av deres egenskaper. For eksempel gyldigheten, ifølge Aristoteles, til syllogismen

alle (A, B) alle (B, C) noen (A, C)

viser at han, i motsetning til moderne logisk bruk, anså alt for å ha eksistensiell import, slik at alle A er B innebærer at A ikke er et tomt begrep. Likeledes gyldigheten av syllogismen

noen (A, B) alle (B, C) alle (A, C)

uttrykker at noen øker monoton (som vi nå uttrykker det) i det andre argumentet. Hver gyldig syllogisme formaliserer en del av betydningen av disse kvantifiseringsuttrykkene, men Aristoteles studie av deres egenskaper gikk utover syllogistikken. Han observerte for eksempel at noen og ingen er konvertible eller, som vi nå kan si, symmetriske, siden de tilfredsstiller ordningen

Q (A, B) Q (B, A)

i kontrast til alle og ikke alle. Videre studerte han hvordan ulike former for negasjon kombinert med kvantifiseringsuttrykk i (det som senere ble kalt) opposisjonsplassen. [4]Middelalderske logikere fortsatte i Aristoteles tradisjon, men utvidet også syllogistisk resonnement til tilfeller der A, B selv kunne kvantifiseres uttrykk, og dermed håndtere premisser og konklusjoner som Noen esel av enhver mann ikke kjører (eksempel fra John Buridan, 1300-tallet). Selv om den aristoteliske logikken kommer utenom moderne logikkens ekspressivitet og presisjon, var syllogistikken absolutt et avgjørende bidrag til studiet av kvantifisering. Faktisk har syllogistiske systemer med forskjellige uttrykkskraft nylig blitt studert i matematisk logikk, nettopp på grunn av deres tilhørighet til naturlige resonnementer og deres enkle beregningsegenskaper; se avsnitt 18 nedenfor.

Spesielt interessant i den nåværende konteksten er det faktum at disse kvantifiseringsuttrykkene tar to argumenter eller begreper, og dermed kan sees på som binære relasjoner, både syntaktisk (som Aristoteles uten tvil så dem) og semantisk: gitt at begrepene indikerer sett med individer, uttrykk noen kan tas for å betegne forholdet mellom overlapping, dvs. å ha ikke-tomt kryss, mellom to sett, og alt betyr inkluderingsrelasjonen. Legg merke til at dette ikke er relasjoner mellom individer, men mellom sett med individer - andreordens relasjoner. Faktisk er de nøyaktig de generaliserte kvantifisererne, henholdsvis noen og alle (på et gitt univers).

Denne tråden - at kvantifiseringsuttrykkene betegner andre ordens relasjoner - ble ikke plukket opp av noen av Aristoteles middelalderske tilhengere (så vidt vi vet). I stedet plukket de opp det faktum at de to begrepene har ulik status: den første kombineres med kvantifiseringsuttrykket for å danne et substantivfrase (som vi nå sier), som er gjenstand for setningen, mens den andre er en verbfrase utgjør predikatet. Dette førte til at de fokuserte på det motivet - alle menn, noen hunder, ingen seilere - betegnet, noe som konseptuelt synes å være et vanskeligere spørsmål. Man kan anta at alle menn betegner enhver mann (eller settet med menn), og at noen hunder betyr en bestemt hund, men hva med ingen seilere? Faktisk kan man vise at tilnærminger som disse er dømt til å mislykkes. [5] Den moderne "løsningen" er at substantivfraser betegner sett med sett med individer, slik at for eksempel noen hunder betegner settet med minst en hund, men det ser ut til å kreve en mer abstrakt og matematisk tilnærming til semantikk enn ideen, som i det minste er implisitt i Aristoteles, at kvantifiserende fraser indikerer forhold mellom (betegnelsene på) termer.

3. Frege

Det andre store historiske bidraget til teorien om generaliserte kvantifiserere kom fra "oppfinneren" av moderne logikk, Gottlob Frege, på 1870-tallet. Faktisk er Freges bidrag todelt. Som enhver filosofistudent vet, introduserte han språket i predikatlogikk, med sentensielle tilkoblinger, identitet og den variable bindende operatøren (forall) (selv om hans todimensjonale logiske notasjon ikke lenger brukes). Dette er kvantifisererne som logikere i løpet av 1950-årene begynte å "generalisere". Men Frege formulerte også eksplisitt den abstrakte forestillingen om en kvantifiserer som en andreordens relasjon, eller, som han kalte det, et begrep på andre nivå (“Begriff zweiter Stufe”). Han var godt klar over at de fire aristoteliske kvantifisererne var gode eksempler, men han ønsket å unngå fokuset på emne-predikatform,som han (med mye begrunnelse) så på å ha vært et stort hinder for utviklingen av logikk etter Aristoteles. Det var derfor en viktig oppdagelse at alle disse tallene kunne defineres i form av (forall) og sentimental operatører (erstatte alle ((A, B)) med (forall x (A (x) høyre høyre) B (x))), noen ((A, B)) av (neg / forall x (A (x) høyre mark / neg B (x))) osv.).

Faktisk er den eneste signifikante forskjellen mellom Freges forestilling om et annet nivå-konsept og den moderne forestillingen om en generalisert kvantifiserer at Frege ikke hadde ideen om en tolkning eller modell, som vi nå (siden innføringen av modellteori i 1950-tallet) ser som et univers at kvantifisererne strekker seg over, pluss en tildeling av passende semantiske objekter til de ikke-logiske symbolene. Freges symboler hadde alle faste betydninger, og det eneste universet han vurderte var totaliteten til alt. Men bortsett fra dette, kan man godt si at det var Frege som oppdaget generaliserte kvantifiserere. Dette aspektet av Freges logikk forble imidlertid i bakgrunnen i lang tid, og modellteoretikere på 50- og 60-tallet ser ikke ut til å ha vært klar over det.

4. Generalisere den universelle og eksistensielle kvantifisereren

Moderne predikatlogikk fikser betydningen av (forall) og (exist) med de respektive leddene i sannhetsdefinisjonen, som spesifiserer induktiv betingelsene under en formel (f (x_1, / ldots, x_n)) (med høyst (x_1, / ldots, x_n) gratis) er tilfreds med tilsvarende elementer (a_1, / ldots, a_n) i en modell (M = (M, I)) (hvor M er universet og jeg tolkningsfunksjonen som tildeler passende utvidelser til ikke-logiske symboler): (M / modeller / f (a_1, / ldots, a_n)). Avsnittene er (der “iff” som vanlig står for “hvis og bare hvis”)

  • (1) (M / modeller / forall x / p (x, a_1, / ldots, a_n)) iff for hver (a / i M), (M / modeller / p (a, a_1, / ldots, a_n))
  • (2) (M / modeller / eksisterer x / p (x, a_1, / ldots, a_n)) hvis det er noen (a / i M) st (M / modeller / p (a, a_1, / ldots, a_n))

For å introdusere andre kvantifiserere, må man sette pris på hva slags uttrykk (forall) og (exist) er. Syntaktisk er de operatører som binder en variabel i en formel. For å se hvordan de fungerer semantisk er det nyttig å skrive om (1) og (2) litt. Først betegner hver formel (p (x)) med en gratis variabel i en modell (M) en delmengde av M; settet med individer i M tilfredsstillende (p (x)). Mer generelt sett, hvis (p (x, x_1, / ldots, x_n) = / p (x, / xbar)) på det meste har de gratis variablene som er vist og (abar = a_1, / ldots, a_n) er elementer av M, la

(p (x, / abar) ^ { M, x} = {a / i M: / M / modeller / p (a, / abar) })

være utvidelsen av (p (x, / xbar)) i (M) i forhold til (a_1, / ldots, a_n). Så kan vi omformulere (1) og (2) som følger:

  • (3) (M / modeller / forall x / p (x, / abar)) iff (p (x, / abar) ^ { M, x} = M)
  • (4) (M / modeller / eksisterer x / p (x, / abar)) iff (p (x, / abar) ^ { M, x} neq / emp)

Dermed dukker forholdene på høyre side ut som egenskaper til settene (p (x, / abar)). Faktisk kan vi tenke på (forall) og (exist) som betegner disse egenskapene, dvs. egenskapen til å være identisk med universet, og å være ikke-tomme, henholdsvis. Og nå er det lett å tenke på andre egenskaper til sett som også kan behandles som kvantifiseringsmidler, for eksempel egenskapen til å inneholde minst 5, eller nøyaktig 3, elementer, eller å være uendelige. [6]

Merk at disse egenskapene bare avhenger av universet M, ikke av resten av modellen. Ekstensivt er de ganske enkelt sett med undergrupper av M. Dette fører til følgende definisjon. hovedsakelig fra Mostowski (1957):

Definisjon 1

En generalisert kvantifiserer Q av typen ({ langle} 1 { rangle}) er

  • (5) a. syntaktisk, en variabel-bindende operatør slik at når (f) er en formel så er (Qx / f), og (Qx) binder alle frie forekomster av x i (f);
  • b. semantisk, en kartlegging fra vilkårlige universer (ikke-tomme sett) M til et sett (Q_M) av undersett av M, som tolker formler til formen (Qx / f) i henhold til leddet (tag {i } M / modeller Q x / p (x, / abar) tekst {iff} p (x, / abar) ^ { M, x} i Q_M)

Her bruker vi det samme symbolet for kvantifiseringsuttrykket og kartleggingen som det betyr eller betegner. Dermed blir (forall) nå tatt for å betegne den universelle kvantifisereren, også skrevet (forall), som er kartleggingen gitt av

(forall_M = {M })

for alle M. Tilsvarende betegner (exist) kartleggingen definert av

(exist_M = {A / subseteq M: A / neq / emp })

Og her er noen andre generaliserte kvantifiserere:

(tag {6} label {ex-qlist1} begin {alignat} {2} (eksisterer _ { geq 5}) _ M & = {A / subseteq M: | A | / geq 5 } & (| X | / textrm {er størrelsen eller} && / textrm {cardinality of} X) (exist _ {= 3}) _ M & = {A / subseteq M: | A | = 3 } (Q_0) _M & = {A / subseteq M: A / text {er uendelig} } (Q ^ R) _M & = {A / subseteq M: | A | > | MA | } & / textrm {("Rescher} && / textrm {kvantifiserer")} (Q _ { tekst {enda}}) _ M & = {A / subseteq M: | A | / text {er jevn} } end {alignat})

Vi har nå en presis forestilling om en generalisert kvantifiserer, hvorav (forall) og (exist) er tilfeller, sammen med uendelig mange andre. Dessuten ser vi hvordan man utvider førsteordens logikk FO til en logikk (FO (Q)), ved å legge klausulen (5a) til formasjonsreglene, og leddet (5b-i) til sannhetsdefinisjonen. Tilsvarende hvis vi legger til mer enn en generalisert kvantifiserer: (FO (Q_1, / ldots, Q_n)).

I en slik logikk kan man være i stand til å si ting som ikke er uttrykkelige i FO. For eksempel er det velkjent at i FO kan ikke ideen om endethet uttrykkes. Det er således ingen måte å si om et ordensforhold (<) at hvert element bare har endelig mange forgjengere, for eksempel. Men dette er bare den typen ting man kan uttrykke i (FO (Q_0)):

(tag {7} forall x / neg Q_0 y (y <x))

På samme måte kan man ikke si i FO at et (endelig) sett A inneholder nøyaktig halvparten av elementene i universet M, men det er uttrykkelig i (FO (Q ^ R)):

(tag {8} neg Q ^ RxA (x) kile / neg Q ^ Rx / neg A (x))

(Den første konjunkten sier at (| A | / leq | MA |), og den andre at (| MA | / leq | A |).)

5. Generaliserte kvantifiserere av vilkårlige typer

Ytterligere generalisering er mulig. For det første kan vi la Q binde en variabel i to eller flere formler. For det andre kan vi la den samtidig binde to eller flere variabler i (noen av) disse formlene. Skrivingen av Q indikerer dette: Q er av typen ({ langle} n_1, / ldots, n_k { rangle}) (der hver (n_i) er et naturlig tall (geq 1)) hvis det gjelder k-formler, og binder (n_i) variabler i den i formelen. Dette forklarer hvorfor kvantifisererne i forrige avsnitt ble sagt å være av typen ({ langle} 1 { rangle}).

I det generelle tilfellet velger man normalt forskjellige variabler (x_ {i1},) …, (x_ {in_i} = / xbar_i) for (1 / leq i / leq k), slik at en formel begynner med Q har formen

[Q / xbar_1, / ldots, / xbar_k (f_1, / ldots, / f_k))

der alle frie forekomster av (x_ {i1}, / ldots, x_ {in_i}) i (f_i) blir bundet. Nå assosierer Q seg med hvert univers M ak -ary relation (Q_M) mellom relasjoner over M, der det første argumentet er et (n_i) - arisk forhold mellom individer. Den tilsvarende klausulen i sannhetsdefinisjonen blir

(tag {9} M / modeller Q / xbar_1, / ldots, / xbar_k (p_1 (xbar_1, / abar), / ldots, / p_k (xbar_k, / abar)) textrm {iff} / Q_M (p_1 (xbar_1, / abar) ^ { M, / xbar_1}, / ldots, / p_k (xbar_k, / abar) ^ { M, / xbar_k}))

Her (p_i (xbar_i, / ybar)) er en formel med høyst de frie variablene som vises, (abar) er en sekvens av elementer av M som tilsvarer (ybar), og (p_i (xbar_i, / abar) ^ { M, / xbar_i}) er forlengelsen av (p_i (xbar_i, / ybar)) i (M) i forhold til (abar), dvs. settet med (n_i) - tuples (bbar_i) slik at (M / models / p_i (bbar_i, / abar)).

Dette er det offisielle konseptet med en generalisert kvantifiserer i denne artikkelen. Det ble introdusert av Lindström (1966), og disse kvantifisererne kalles noen ganger "Lindström kvantifiserere". [7] Hvis vi fester M til universet som inneholder "alt", har vi i hovedsak Freges forestilling om et andre nivå-konsept. [8]

Q er monadisk hvis det i hvert univers M er en relasjon mellom undergrupper av M, dvs. hvis dens type er ({ langle} 1, / ldots, 1 { rangle}); ellers er den polyadisk. For eksempel er de aristoteliske kvantifiseringene nevnt tidligere av typen ({ langle} 1,1 { rangle}): [9]

(tag {10} label {ex-qlist2} start {align} textit {all} _M (A, B) & / iff A / subseteq B \\ / textit {some} _M (A, B) & / iff A / cap B / neq / emp \\ / textit {no} _M (A, B) & / iff A / cap B = / emp \\ / textit {ikke alle} _M (A, B) & / iff A / not / subseteq B / end {align})

Her er noen flere type ({ langle} 1,1 { rangle}) kvantifiserere: [10]

(tag {11} label {ex-qlist3} begin {alignat} {2} (textit {minst fem}) _ M (A, B) & / iff | A / cap B | / geq 5 (textit {nøyaktig tre}) _ M (A, B) & / iff | A / cap B | = 3 \(textit {uendelig mange}) _ M (A, B) & / iff A / cap B / tekst {er uendelig} / \ textit {mest} _M (A, B) & / iff | A / cap B |> | AB | \(textit {et jevnt antall}) _ M (A, B) & / iff | A / cap B | / text {er jevnt} / \ textit {MO} _M (A, B) & / iff | A | > B | \\ / textit {I} _M (A, B) & / iff | A | = | B | & / textrm {("Härtig} && / textrm {kvantifisereren")} end {alignat})

Med monadiske kvantifiserere er det praktisk å bruke bare en variabel, og la Q binde den samme variabelen i hver av formlene. For å si at de fleste A ikke er B, kan man for eksempel skrive

(textit {most}: x (A (x), / neg B (x)))

i det tilsvarende logiske språket, i stedet for (textit {most}: x, y (A (x), / neg B (y))).

Her er noen polyadiske kvantifiserere:

(tag {12} label {ex-qlist4} begin {alignat} {2} W_M (R) & / iff R / text {er en velordnet ordning av} M & / textrm {type} { langle } 2 { rangle} (Q_0 ^ n) _M (R) & / iff / text {det er en uendelig} & / hphantom { iff } A / subseteq M / ST A ^ n / subseteq R & / textrm {type} { langle} n { rangle} / Res ^ k (textit {most}) _ M (R, S) & / iff | R / cap S | > | RS | & / textrm {type} { langle} k, k { rangle} / \ textit {RECIP} _M (A, R) & / iff / textrm {for alle distinkte} a, b / i A \& / hphantom { iff } textrm {det er} n / geq 1 \& / hphantom { iff } textrm {og} c_0, / ldots, c_n / ST c_0 = a \& / hphantom { iff } {} amp c_n = b / amp c_iRc_ {i + 1} textrm {for} i <n / quad & / textrm {type} { langle} 1,2 { rangle} end {alignat}]

W og (Q_0 ^ n) kommer fra logikk og settteori. (Res ^ k (textit {most})) er gjenopptakelsen av de fleste til k-tippler. Gjenopptak kan brukes på en hvilken som helst kvantifiserer (i syntaks betyr dette å bytte ut hver individuelle variabel med en tilsvarende k-mengde variabler); det har logiske bruksområder, men også, som RECIP, bruker i tolkningen av visse setninger på naturlige språk; se avsnitt 16 nedenfor.

6. Emneutralitet

Både Mostowski og Lindström hadde en tilleggsbetingelse i sine definisjoner av generaliserte kvantifiserere: De skulle ikke skille isomorfe modeller. Uformelt er de “emne-nøytrale”: sannheten i en uttalelse av formen (f = Qx, yz (A (x), R (y, z))), si, i en modell (M) er ikke avhengig av de individene M består av. Hvis individer fra M er kartlagt på en måte på individene i et annet univers (M '), og hvis A og R er kartlagt tilsvarende, oppnår man en isomorf modell (M'). Isomorphism Closure sier da at (M / models / f) iff (M '\ models / f).

Mer formelt, hvis (M = (M, I)) og (M '= (M', I ')) er modeller for samme ordforråd V av ikke-logiske symboler, er f en isomorfisme fra (M) til (M '), iff

  • f er en bijeksjon (en til funksjon) fra M til (M ');
  • hver gang P er et predikat-symbol som ikke er i V og (a_1, / ldots, a_n / in M ), [(a_1, / ldots, a_n) i I (P) textrm {iff} (f (a_1), / ldots, f (a_n)) i I '(P);)
  • når c er en individuell konstant i V, (I '(c) = f (I (c))).

(M) og (M ') er isomorf, i symboler, (M / cong / M ')

hvis det er en isomorfisme fra den ene til den andre. Hvis Q er en generalisert kvantifiserer av typen ({ langle} n_1, / ldots, n_k { rangle}), er (P_i) et (n_i) - ary predikatsymbol for (1 / leq i / leq k), (M = (M, I)) er en modell for ordforrådet ({P_1, / ldots, P_k }), og (R_i = I (P_i)), skriver vi også

(M = (M, R_1, / ldots, R_k))

Da tilfredsstiller Q Isomorphism Closure, eller bare Isom, hvis følgende gjelder:

(tag {13} label {ex-isom} textrm {If} (M, R_1, / ldots, R_k) cong (M ', R'_1, / ldots, R'_k), / textrm { deretter} / Q_M (R_1, / ldots, R_k) Leftrightarrow Q_ {M '} (R'_1, / ldots, R'_k).)

Man sjekker lett at alle de generaliserte kvantifisererne som er eksemplifisert så langt, faktisk er Isom. Vi inkluderte imidlertid ikke dette kravet i definisjonen av generaliserte kvantifiserere, siden det er naturlige språkvantifiserere som ikke tilfredsstiller det; se nedenfor. Men logikk er ment å være emne-nøytral, så Isom pålegges nesten alltid. Så følger to viktige ting. For det første skiller ikke setninger i logiske språk isomorfe modeller, som angitt ovenfor. Mer presist har vi følgende

Fakta 2

Hvis (L = / FO (Q_1, / ldots, Q_n)), er hver (Q_i) Isom, (f) er en L-setning, og (M / cong / M '), deretter (M / modeller / f / Leftrightarrow / M '\ modeller / f).

For det andre tar Isom en spesielt interessant form for monadiske kvantifikatorer. Hvis (M = (M, A_1, / ldots, A_k)), der (A_i / subseteq M) for hvert i, så (A_1, / ldots, A_k) partisjon M til (2 ^ k) parvis sammenkoblede undergrupper (hvorav noen kan være tomme); la oss kalle dem delene av (M). Vi illustrerer med (k = 2) og (M = (M, A, B)):

to kryssende sirkler inne i en boks (boksen merket 'M') med 'A kryssende B' merking av sirkelskjæringen og 'A minus B' og 'B minus A' merking av ikke-kryssende deler av sirklene. Området inne i boksen, men ikke i sirklene, er merket 'M minus (A union B)'
to kryssende sirkler inne i en boks (boksen merket 'M') med 'A kryssende B' merking av sirkelskjæringen og 'A minus B' og 'B minus A' merking av ikke-kryssende deler av sirklene. Området inne i boksen, men ikke i sirklene, er merket 'M minus (A union B)'

Figur 1

Nå er det ikke vanskelig å se at bare størrelsene på delene avgjør om to modeller av denne typen er isomorfe eller ikke:

Fakta 3

((M, A_1, / ldots, A_k) cong (M ', A'_1, / ldots, A'_k)) hvis kardinalitetene til de tilsvarende delene er de samme.

Dette viser at monadiske og Isom-generaliserte kvantifiserere faktisk bare omhandler mengder, dvs. størrelser på sett i stedet for settene i seg selv. Listen / eqref {ex-qlist3} av typen ({ langle} 1,1 { rangle}) generaliserte kvantifiserere illustrerer dette tydelig, men også de aristoteliske kvantifisererne kan formuleres når det gjelder kardinaliteter, (begynne {align} textit {alle} _M (A, B) & / iff | AB | = 0 \\ / textit {noen} _M (A, B) & / iff | A / cap B |> 0 / end {align})

osv., og tilsvarende for typen ({ langle} 1 { rangle}) eksempler vi ga.

Mer generelt, under Isom, kan monadiske kvantifikatorer sees på som forhold mellom (kardinal) tall. Hvis for eksempel Q er av typen ({ langle} 1 { rangle}), definer du (ved å bruke det samme symbolet Q for forholdet mellom tall)

[Q (kappa, / lambda) iff / text {det er} (M, A) ST | M \! - \! A | = / kappa / amp | A | = / lambda / amp Q_M (A))

Isom garanterer at dette er godt definert, og det har vi

[Q_M (A) iff Q (| M \! - \! A |, | A |))

7. Relativisering

Hver uttalelse som involverer en generalisert kvantifiserer Q, finner sted innenfor et univers M. Noen ganger er det nyttig å kunne speile denne relativiseringen til et univers i M. Dette betyr å definere en ny kvantifiserer med ett ekstra sett argument som sier at Q oppfører seg på universet begrenset til det argumentet nøyaktig slik det oppfører seg på M. Så hvis Q er av typen ({ langle} n_1, / ldots, n_k { rangle}), definerer vi (Q {^ { text {rel}}}) av typen ({ langle } 1, n_1, / ldots, n_k { rangle}) som følger:

(tag {14} (Q {^ { text {rel}}) _ M (A, R_1, / ldots, R_ {n_k}) matematikk { Longleftrightarrow _ { text {def}}} Q_A (R_1 \! / begrensning \! A, / ldots, R_ {n_k} ! / begrensning \! A))

hvor (R_i / subseteq M ^ {n_i}) og (R_i \! / restriction \! A) er begrensningen av (R_i) til A, dvs. settet med (n_i) - tuples i (R_i / cap A ^ {n_i}).

Vi har faktisk allerede sett flere eksempler på relativisering: siden man enkelt verifiserer (se listene / eqref {ex-qlist1} og / eqref {ex-qlist3}) at

(tag {15} begin {align} textit {all} & = / forall {^ { text {rel}}} / \ textit {some} & = / exist {^ { text {rel} }} / \ textit {minst fem} & = (exist _ { geq 5}) {^ { text {rel}}} / \ textit {nøyaktig tre} & = (exist _ {= 3}) {^ { text {rel}}} / \ textit {uendelig mange} & = (Q_o) {^ { text {rel}}} / \ textit {most} & = (Q ^ R) {^ { text {rel}}} / \ textit {et jevnt antall} & = (Q _ { text {even}}) {^ { text {rel}}} end {align})

8. Uttrykksmakt

Vi beskrev hvordan generaliserte kvantifiserere kan legges til FO, noe som resulterer i mer ekspressive logikker. En logikk i denne forstand består omtrent av et sett med setninger, en klasse av modeller og en sannhetsrelasjon (eller en tilfredshetsrelasjon) mellom setninger og modeller. Slike logikker kalles ofte modellteoretisk logikk, siden de er definert semantisk med tanke på modeller og sannhet, snarere enn bevisteoretisk i form av et deduktivt system for å utlede teoremer. [11] Her begrenser vi oppmerksomheten til logikk av formen (FO (Q_1, Q_2, / ldots)), dannet ved å legge generaliserte kvantifiserere til FO, der hver kvantifiserer kommer med en formasjonsregel og en semantisk klausul for sannheten definisjon som beskrevet i avsnitt 5 ovenfor.

Det er en åpenbar måte å sammenligne den ekspressive kraften til modellteoretisk logikk. (L_2) er minst like uttrykksfulle som (L_1), i symboler, [L_1 / leq L_2)

hvis hver (L_1) - setning (f) er logisk ekvivalent med noen (L_2) - setning (p), dvs. (f) og (p) er sant i de samme modellene. I tillegg har (L_1) og (L_2) den samme uttrykksmakten, (L_1 / ekv. L_2), hvis (L_1 / leq L_2) og (L_2 / leq L_1), og (L_2) er sterkere enn (L_1), (L_1 <L_2), hvis (L_1 / leq L_2) men (L_2 / not / leq L_1). Altså (L_1 <L_2) hvis alt som kan sies i (L_1) også kan sies i (L_2), men det er noen (L_2) - setning som ikke tilsvarer noen setning i (L_1).

Hvordan etablerer man fakta om uttrykksmakt? Det virker som om man må vise (L_1 / leq L_2) man må gå gjennom alle de uendelig mange setningene i (L_1) og for hver finne en ekvivalent i (L_2). Men i praksis er det nok å vise at de generaliserte kvantifiseringene i (L_1) er definerbare i (L_2). Hvis Q er av typen ({ langle} 1,2 { rangle}), si, er Q definert i (L_2) hvis det er en (L_2) - setning (p) hvis ikke-logisk ordforråd består nøyaktig av ett unary og ett binært predikatsymbol, slik at for alle modeller (M = (M, A, R)), [Q_M (A, R) iff (M, A, R) modeller / p)

Tilsvarende for andre typer. For eksempel er kvantifisereren alt definert i FO, ettersom følgende gjelder:

(textit {all} _M (A, B) iff (M, A, B) modeller / forall x (A (x) høyre pil B (x)))

På samme måte kan (Q ^ R) defineres i (FO (textit {most})), siden

[(Q ^ R) _M (A) iff (M, A, B) modeller / textit {most}: x (x = x, A (x)))

(legg merke til at alle logikkene våre inneholder det logiske apparatet til FO, så de er alle utvidelser av FO). Det siste er et eksempel på følgende observasjon:

(16) For enhver generalisert kvantifiserer Q, er Q definerbar i (FO (Q {^ { tekst {rel}}}))

Slike fakta om definabilitet kan være enkle eller vanskelige å fastslå, [12] men de er nok til å etablere positive fakta om ekspressivitet, siden vi har:

Fakta 4

(FO (Q_1, / ldots, Q_n) leq L) hvis og bare hvis hver (Q_i) er definerbar i L.

På den annen side er det vanskeligere å bevise utilregnelighet, dvs. at en eller annen setning ikke tilsvarer noen L-følelse. En måte som noen ganger fungerer er å slå fast at (L_1) har en del eiendommer som (L_2) mangler; så kan man kanskje konkludere med at (L_1 / not / leq L_2). Noen egenskaper som er typiske for FO, men mislykkes for de fleste sterkere logikker, er:

  • Löwenheim-egenskapen: Hvis en setning er sann i en uendelig modell, er den også sant i noen tellbar modell.
  • Tarski-egenskapen: Hvis en setning er sann i en utallig uendelig modell, er den også sann i en utellelig modell.
  • Kompakthetsegenskapen: Hvis ingen modeller gjør hvert element i settsettet (Phi) sant, er det et begrenset undergruppe (Psi) av (Phi) slik at ingen modell gjør hver setning i (Psi) sant.
  • Fullstendighetsegenskapen: Settet med gyldige setninger er rekursivt talt (dvs. kan genereres av et formelt system).

For eksempel har (FO (Q_0)) ikke kompakthetsegenskapen. [13] Dette kan sees ved å se på settet med setninger

(Phi \: = \: { neg Q_0x (x = x) cup { theta_n: n = 1,2, / ldots })

hvor (theta_n) er en FO-mening som sier at det er minst n elementer i universet. Hvis du tar en endelig undergruppe (Phi ') av (Phi), og M er et univers hvis kardinalitet er den største n slik at (theta_n) hører til (Phi'), da er alle setninger i (Phi ') sanne i M. Men intet univers kan gjøre alle setninger i (Phi) sanne. Og dette viser at (Q_0) ikke kan defineres i FO, dvs. at (FO (Q_0) ikke / leq / FO), siden vi ellers kan erstatte (Phi) med et tilsvarende sett med FO-følelser, men FO har kompakte egenskaper, slik at det umulig.

Imidlertid fungerer denne måten å bevise uttrykk for bare for logikk med egenskaper som ovenfor. Dessuten fungerer de bare hvis det er tillatt med uendelige universer, men interessante fakta om ekspressbarhet gjelder også for begrensede modeller, for eksempel det faktum at (Q ^ R) og (Q _ { text {til og med}}) ikke kan defineres i FO, eller at de fleste = ((Q ^ R) {^ { text {rel}}}) ikke kan defineres i (FO (Q ^ R)). Logikere har utviklet mye mer direkte og effektive metoder for å vise udefinerbare resultater som fungerer også for begrensede modeller. [14]

Ovennevnte egenskaper kjennetegner faktisk FO, i den forstand at ingen riktig utvidelse av FO kan ha (visse kombinasjoner av) dem. Dette er innholdet i en berømt teorem om modellteoretisk logikk, Lindströms teorem, hvis versjon er gitt nedenfor. For et tilgjengelig bevis, se for eksempel Ebbinghaus, Flum og Thomas (1994). Vi sier at en logikk (L = / FO (Q_1, / ldots, Q_n)) relativiseres hvis "samtalen" til (16) gjelder for hver (Q_i), dvs. hvis hver ((Q_i) { ^ { text {rel}}}) kan defineres i L.

Teorem 5 (Lindström) Hvis L er kompakt og har Löwenheim-egenskapen, så (L / equiv / FO). Forutsatt at L relativiserer, hvis L er komplett og har Löwenheim-egenskapen, eller hvis L har både Löwenheim- og Tarski-egenskapene, så (L / equiv / FO).

9. Generaliserte kvantifisere og beregning

I tillegg til sannhetsforholdene knyttet til generaliserte kvantifiserere, kan man studere beregningene som kreves for å etablere sannheten i en kvantifisert uttalelse i en modell. Generelle kvantifiserere dukker faktisk opp forskjellige steder i den delen av informatikk som studerer beregningskompleksitet. I denne sammenheng begrenser vi oppmerksomheten til endelige universer, og antar Isom gjennomgående. Så en kvantifiserer er egentlig et sett med begrensede modeller; av Isom kan vi anta at modeller av kardinalitet m alle har samme domene (M = {1, / ldots, m }). Slike modeller kan kodes som ord, det vil si endelige symbolstrenger. For eksempel kan en modell ((M, A)) av typen ({ langle} 1 { rangle}) sees som et binært ord (a_1 / ldots a_m), der (a_i) er 1 hvis (i / i A) og 0 ellers. Dermed er (| A |) antallet av 1er og (| M \! - \! A |) antallet av 0-er; av Isom,rekkefølgen i strengen spiller ingen rolle. Så Q blir et sett (W_Q) med ord, det vil si et formelt språk: et delsett av settet med alle endelige strenger med kodesymboler.[15]

Vi kan nå spørre hva som skal til for å gjenkjenne at et ord tilhører (W_Q). Den abstrakte forestillingen om en automat gir et svar; automata er maskiner som godtar eller avviser ord, og de klassifiseres i henhold til kompleksiteten i operasjonene de utfører. Språket som gjenkjennes av en automat, er det settet med ord den godtar. [16]

En endelig automat har et begrenset antall stater, inkludert en starttilstand og minst en aksepterende tilstand. Den begynner å skanne et ord på det venstre symbolet i starttilstanden, og på hvert trinn beveger det ett symbol til høyre og går inn i en (muligens) ny tilstand, i henhold til en gitt overgangsfunksjon. Hvis det kan bevege seg langs hele ordet som ender i en aksepterende tilstand, godtas ordet. Bruken av automatteori på generaliserte kvantifiserere ble initiert i van Benthem (1986) (kap. 7, “Semantic automata”). Det er enkelt å konstruere en endelig automat som gjenkjenner (forall) (eller (forall {^ { text {rel}}} =) alle), dvs. å sjekke at w bare består av 1: bare vær i starttilstanden = aksepterer tilstand så lenge det oppstår 1er, men gå til en avvisende tilstand så snart en 0 er skannet, og forbli der hva som blir oppstått etterpå. En litt mer komplisert automat gjenkjenner (Q _ { text {til og med}}): igjen er det to tilstander, en starttilstand = den aksepterende tilstanden og en avvisende tilstand, og denne gangen forblir i samme tilstand når 0 er skannet, men gå til den andre tilstanden når en 1 skannes. For å ende i den aksepterende tilstanden er det da nødvendig og tilstrekkelig at det er et jevnt antall 1er. Denne maskinen bruker i hovedsak sykluser med lengde 2, mens det første eksemplet bare hadde 1-sykluser. Kall en automat av sistnevnte type acyklisk. Van Benthem viste at FO-definerbare kvantifiserere er nøyaktig de som er akseptert av endelige automatar som er acykliske og permutasjonen lukket.og denne gangen forblir i samme tilstand når 0 er skannet, men gå til den andre tilstanden når en 1 blir skannet. For å ende i den aksepterende tilstanden er det da nødvendig og tilstrekkelig at det er et jevnt antall 1er. Denne maskinen bruker i hovedsak sykluser med lengde 2, mens det første eksemplet bare hadde 1-sykluser. Kall en automat av sistnevnte type acyklisk. Van Benthem viste at FO-definerbare kvantifiserere er nøyaktig de som er akseptert av endelige automatar som er acykliske og permutasjonen lukket.og denne gangen forblir i samme tilstand når 0 er skannet, men gå til den andre tilstanden når en 1 blir skannet. For å ende i den aksepterende tilstanden er det da nødvendig og tilstrekkelig at det er et jevnt antall 1er. Denne maskinen bruker i hovedsak sykluser med lengde 2, mens det første eksemplet bare hadde 1-sykluser. Kall en automat av sistnevnte type acyklisk. Van Benthem viste at FO-definerbare kvantifiserere er nøyaktig de som er akseptert av endelige automatar som er sykliske og permutasjonen lukket. Van Benthem viste at FO-definerbare kvantifiserere er nøyaktig de som er akseptert av endelige automatar som er sykliske og permutasjonen lukket. Van Benthem viste at FO-definerbare kvantifiserere er nøyaktig de som er akseptert av endelige automatar som er sykliske og permutasjonen lukket.[17]

En litt mer sammensatt automat, pushdown-automaten, har rudimentære hukommelsesressurser i form av en stabel med symboler som kan skyves eller sprettes fra toppen, slik at den kan holde oversikt over hva som skjedde på tidligere trinn. Et annet resultat av van Benthem er at typen ({ langle} 1 { rangle}) som er akseptert av pushdown-automater, er nettopp de som det tilsvarende binære forholdet mellom tall kan defineres (med førsteordens midler) i additiv aritmetikk, dvs. i modellen ((N, +)), der (N = {0,1,2, / ldots }). Et eksempel er (Q ^ R) (eller dens relativisering mest): vi har (Q ^ R (m, n) Leftrightarrow m <n), og høyre side er definerbar i ((N, +)) av (eksisterer x (x / neq 0 / kile m + x = n)). [18]

Dermed blir en algoritmisk karakterisering matchet med en logisk. Dette er en fremtredende retning i studiet av algoritmisk kompleksitet. Tenk nå den mest generelle abstrakte automatikken eller beregningsapparatene, dvs. Turing-maskiner. En (av mange) interessante kompleksitetsklasser er PTIME: et problem, identifisert med det tilsvarende ordssettet, er PTIME hvis det er et polynom (p (x)) og en Turing-maskin som godtar W slik at når (w / i W) har lengde n, tar den aksepterende beregningen på de fleste (p (n)) trinn. PTIME-problemer blir vanligvis ansett som "gjennomførbare", mens mer komplekse problemer er "intractable", for eksempel EXPTIME, der antall trinn som kreves kan vokse eksponentielt. Et tidlig resultat av Immerman og Vardi er at PTIME-settene med (ordkodende) endelige modeller nettopp er de som kan beskrives med enkeltsetninger i (FO (LFP)), som er FO-logikk med en ekstra mekanisme for å danne minst faste -poeng.[19] Her må vi representere ikke bare monadiske modeller, men vilkårlige. For eksempel kan en binær relasjon til universet ({1, / ldots, m }) være representert med et ord (w_ {11} cdots w_ {1m} # / ldots / #w_ {m1 } cdots w_ {mm}), der forholdet har ((i, j)) iff (w_ {ij} = 1). Men denne gangen ser det ut til at rekkefølgen betyr noe, og faktisk nevnte Immerman og Vardi-resultatet bare for modeller med en gitt lineær rekkefølge og et binært predikatsymbol som står for den rekkefølgen.

Logikk som (FO (LFP)) kan omformes som logikk for formen (FO (Q_1, Q_2, / ldots)). Her kan det kreves uendelig mange kvantifiserere, men i noen tilfeller er det nok med en enkelt. Når det gjelder (FO (LFP)), er det nok å legge til alle gjenopptakene (se slutten av avsnitt 5 ovenfor) til en enkelt kvantifiserer. Mer generelt, la (FO ^ * (Q_1, Q_2, / ldots)) være som (FO (Q_1, Q_2, / ldots)) men med mekanismer for å gjøre relativiseringer (seksjon 7) og for å gjenoppta hver (Q_i) til k-titler for hver k. Så er det en enkelt kvantifiserer Q slik at (FO (LFP) = / FO ^ * (Q)).

Så generaliserte kvantifiseringer forblir en enkel og allsidig måte å tilføre FO uttrykksmakt på. Et naturlig spørsmål var om den logiske karakteriseringen av PTIME som er nevnt ovenfor kunne forbedres ved bruk av generaliserte kvantifiserere, spesielt hvis man kunne fjerne begrensningen til ordnede strukturer på denne måten. Svaret viste seg imidlertid å være negativt, siden Hella (1989) beviste at PTIME-beregnbare egenskapene til vilkårlige endelige strukturer ikke kan karakteriseres ved å legge til et begrenset antall generaliserte kvantifiserere til FO, eller til og med (FO (LFP)). Spørsmålet om PTIME kan kjennetegnes av en logikk med formen (FO ^ * (Q)) forblir åpen, men å løse det ville være et stort gjennombrudd i kompleksitetsteorien.

10. Generaliserte kvantifisere og naturlige språk

På slutten av 1960-tallet viste Richard Montague hvordan semantikken til betydelige deler av naturlige språk kunne håndteres med logiske verktøy. [20] En av hans viktigste innsikter var at substantivfraser (NP) kan tolkes som sett med undersett av domenet, dvs. som (det vi nå kaller) type ({ langle} 1 { rangle}) kvantifiserere. Montague arbeidet innen typeteori, men rundt 1980 begynte en rekke lingvister og logikere å anvende modellteoretiske rammer for logikk med generaliserte kvantifiserere på semestikk for naturlig språk. [21] Vurder strukturen til en enkel engelsk setning hvis emne er et kvantifisert NP: [22]

  • (17)

    Linguistics tree [S [NP [Det [most] [N [studenter] [VP [smoke]
    Linguistics tree [S [NP [Det [most] [N [studenter] [VP [smoke]

(Emnet) NP består av en determiner og et substantiv (N). Både substantivet og verbfrasen (VP) har sett som utvidelser, og derfor blir bestemmeren naturlig tatt for å betegne et binært forhold mellom sett, dvs. en type ({ langle} 1,1 { rangle}) kvantifiserer. En ytring fra (17) har et (diskurs) univers i bakgrunnen (si, settet med mennesker ved et bestemt universitet), men betydningen av de fleste, hvert, minst fem og lignende uttrykk er ikke knyttet til bestemte universer. For eksempel betydningen av alle i

  • (18) a. Alle katter liker melk.
  • b. Alle elektronene har negativ ladning.
  • c. Alle naturlige tall har en etterfølger.
  • d. Alle tvillinger liker hverandre.
  • e. Alle kompakte undergrupper av Hausdorff-rommene er stengt.

har ingenting å gjøre med katter eller elektroner eller antall eller tvillinger eller Hausdorff-rom, heller ikke med diskursuniversene som kan være forbundet med eksemplene ovenfor. Det står ganske enkelt for inkluderingsrelasjonen, uavhengig av hva vi tilfeldigvis snakker om. Derfor er den generaliserte kvantifisereren alle, som med hvert univers M assosierer inkluderingsrelasjonen over M, utmerket egnet til å tolke alle, og på samme måte for andre bestemmere.

Imidlertid er det karakteristisk for setninger med formen (17) at substantivargumentet og VP-argumentet ikke er på nivå. Navnet kombineres med bestemmelsesstedet for å danne NP, en egen bestanddel, og denne bestanddelen kan også tas for å betegne en generalisert kvantifiserer, denne tiden av typen ({ langle} 1 { rangle}). Dermed betegner minst fem studenter settet med undergrupper av universet som inneholder minst fem studenter. Denne kvantifisereren er resultatet av å fryse det første argumentet av typen ({ langle} 1,1 { rangle}) tre til settet med elever; vi skriver disse tre (^ { textit {student}}). Generelt, hvis A er et fast sett og Q en type ({ langle} 1,1 { rangle}) kvantifiserer, kan man definere typen ({ langle} 1 { rangle}) kvantifiserer (Q ^ A) av

(tag {19} label {QA} (Q ^ A) _M (B); / Longleftrightarrow _ { text {def}}; Q_ {M / cup A} (A, B))

for enhver M og hvilken som helst (B / subseteq M). I en sammensetningssemantikk er det naturlig å ta hver bestanddel av en setning for å ha en separat betegnelse eller betydning, og standardbetydningene for substantivfraser er type ({ langle} 1 { rangle}) kvantifiserere.

Dette gjelder også for noen NP-er som mangler bestemmere, for eksempel navn. Mens det leksikale elementet John er tilordnet noen individuelle j ved en tolkning, kan NP John tas for å betegne kvantifisereren (I_j), definert, for enhver M, av

[(I_j) _M = {B / subseteq M / !: j / in B })

Dette er faktisk godt motivert, ikke bare fordi tolkningen av NP blir mer enhetlig, men også fordi John kan kombinere med kvantifiserte NP:

(20) John og tre professorer kom til møtet

Her er det praktisk hvis John og tre professorer har samme semantiske kategori. Legg merke til at generaliserte kvantifiserere - i kontrast til individer! - har en tydelig boolsk struktur; definere (her i typen ({ langle} 1 { rangle}) sak, men tilsvarende for alle andre typer)

(begynne {align} (Q_1 / kil Q_2) _M (A) & / iff (Q_1) _M (A) textrm {og} (Q_2) _M (A) (neg Q) _M (A) & / iff / textrm {ikke} Q_M (A) end {align})

Så kan vi ta den komplekse determineren i (20) for å betegne (I_j / kile / textit {tre} ^ { textit {professor}}). Tilsvarende det komplekse NP i

(21) John og Mary kom til møtet

betyr (I_j / kile I_m).

Det første argumentet (som kommer fra substantivet) av en type ({ langle} 1,1 { rangle}) -detoter, kalles ofte begrensningen, og det andre omfanget. Forskjellen i syntaktisk status mellom disse to argumentene viser seg å ha en tydelig semantisk motstykke.

11. Konservativitet

Det ble tidlig observert den typen ({ langle} 1,1 { rangle}) kvantifiserere som er angitt av bestemmere på naturlige språk, har følgende egenskap:

  • (22) Konservativitet (Conserv):

    For alle M og alle (A, B / subseteq M), [Q_M (A, B) iff Q_M (A, A / cap B).)

Dette kan sees fra setningspar som følgende, der det er klart at den andre setningen bare er en vanskelig måte å uttrykke den første:

  • (23) a. De fleste studenter røyker.
  • b. De fleste studenter er studenter som røyker.
  • (24) a. Minst fem professorer var fraværende.
  • b. Minst fem professorer var fraværende professorer.
  • (25) a. Mer enn en tredel av hovedfagsstudentene er utlendinger.
  • b. Mer enn en tredjedel av hovedfagsstudentene er utenlandske hovedfagsstudenter.

Conserv sier at bare den delen av B som er felles for A, betyr for sannheten til (Q_M (A, B)). Det vil si at delen (BA) i figur 1 ikke spiller noen rolle. Dette ser ut til å gjelde for alle bestemmelsesbetegnelser, men det mislykkes for helt naturlige logiske kvantifikatorer, for eksempel MO og I fra listen / eqref {ex-qlist3} ovenfor. Årsaken er at det er karakteristisk for bestemmelsesbetegnelser at begrensningsargumentet begrenser kvantifiseringsområdet til det argumentet.

12. Utvidelse

Ideen om domenerestriksjon har faktisk en ytterligere ingrediens. Å begrense kvantifiseringsdomenet til en undergruppe A av M betyr ikke bare at (BA) ikke er relevant, men hele delen av M som ligger utenfor A, og derav også delen (M- (A / cup B)) i figur 1. Dette er i sin tur et eksempel på en mer generell egenskap som kan brukes på vilkårlige generaliserte kvantifiserere:

  • (26) Utvidelse (Ext):

    Hvis Q er av typen ({ langle} n_1, / ldots, n_k { rangle}), (R_i / subseteq M ^ {n_i}) for (1 / leq i / leq k) og (M / subseteq M '), deretter [Q_M (R_1, / ldots, R_k) iff Q_ {M'} (R_1, / ldots, R_k).)

Det vil si at ingenting skjer når universet blir utvidet eller krympet, så lenge argumentene ikke er endret. Husk at for type ({ langle} 1 { rangle}) kvantifiserere har vi allerede gitt en logisk mekanisme for å begrense kvantifiseringsdomenet til en underenhet, med tanke på relativisering (seksjon 7). Vi kan nå se (i (b) nedenfor) at kombinasjonen av Conserv og Ext utgjør nøyaktig den samme tingen:

Fakta 6

  1. For en hvilken som helst kvantifiserer Q, oppfyller (Q {^ { text {rel}}}) Ext.
  2. En type ({ langle} 1,1 { rangle}) kvantifiserer er Conserv and Ext hvis og bare hvis det er relativisering av en type ({ langle} 1 { rangle}) kvantifiserer. [23]

Igjen ser det ut til at alle bestemmelsesbetegnelser tilfredsstiller Ext. Ved første blikk synes ingenting i prinsippet å forhindre at et språk inneholder en bestemmende faktor, si evso, som betydde alle på universer med mindre enn 10 elementer og noen på større universer. Men ikke bare er det faktisk ingen slik determiner på noe språk, det kan ikke være, hvis substantivargumentet til en determiner er å begrense kvantifiseringsområdet til denotasjonen av det substantivet.

En kvantifiserer som evso er intuitivt ikke konstant, i den forstand at den ikke betyr det samme, eller ikke tolkes av samme regel, på hvert univers. Ext kan sees på som et sterkt krav til konstans: regelen som tolker Q nevner ikke engang universet. Mange kvantifiserere fra språk og logikk er faktisk Ext. Som vi så, er alle relativiserte kvantifiserere Ext, og alle de andre kvantifiseringene i listene / eqref {ex-qlist2} - / eqref {ex-qlist4} også, bortsett fra W. [24] Det ser ut til at alle kvantifiserere som tar mer enn ett argument som dukker opp i naturlige språksammenhenger, er Ext. Og mange type ({ langle} 1 { rangle}) kvantifiserere er Ext også, for eksempel (exist), (I_j), (Q ^ A) (når Q er Ext; se / eqref {QA} ovenfor), og alt i listen / eqref {ex-qlist1} unntatt (Q ^ R).

Men (forall) og (Q ^ R) er ikke Ekst. Likevel er man tilbøyelig til å si for dem også at de betyr det samme for hvert univers. Tilfellet med (forall) er spesielt interessant siden man kan hevde at det tolker NP-er som alt eller alle ting. Cruxen her er ting. Hvis dette uttrykket blir sett på som en logisk konstant som alltid betegner universet, betegner disse NPene (forall): for alle M og alle (B / subseteq M), (begynne {align} (textit {every} ^ { textit {ting}}) _ M (B) & / iff / textit {every} _M (M, B) & / iff M / subseteq B & / iff M = B \& / iff / forall_M (B) end {align})

Når Ext holder, kan vi vanligvis slippe abonnementet M og skrive for eksempel, [Q (A, B))

i stedet for (Q_M (A, B)). Det vil si at et passende univers kan forutsettes, men legges igjen i bakgrunnen.

13. Symmetri og monotonicity

Andre egenskaper deles ikke av alle naturlige språkvantifiserere, men skiller ut viktige underklasser. Vi nevnte to allerede i seksjon 2 over: symmetri og monotonicity. Typiske symmetriske kvantifiserere er noen, ingen, minst fem, nøyaktig tre, et jevnt antall, uendelig mange, mens alle de fleste, høyst en tredjedel av de er ikke-symmetriske. En annen måte å uttrykke symmetri på er å si at sannhetsverdien til (Q (A, B)) bare avhenger av settet (A / cap B). Mer presist, ring Q kryssende hvis for alle M og alle (A, A ', B, B' / subseteq M):

(27) Hvis (A / cap B = A '\ cap B') så (Q_M (A, B) Leftrightarrow Q_M (A ', B'))

En verifiserer enkelt:

Fakta 7

For konservativ type ({ langle} 1,1 { rangle}) kvantifiserere er symmetri og krysseffekt ekvivalent. [25]

Vi bemerket at noen av syllogismene uttrykker monotoniske egenskaper. I mer kortfattet notasjon er en type ({ langle} 1,1 { rangle}) kvantifiserer Q

høyre økning (høyre avtagende) iff for alle M og alle (A, B / subseteq B '\ subseteq M) (alle (A, B' / subseteq B / subseteq M)), (Q_M (A, B)) impliserer (Q_M (A, B ')).

Tilsvarende for venstre øker eller avtar, og faktisk for monotonicitet i et gitt argument sted for en generalisert kvantifiserer. Spesielt er det klart hva det betyr for en type ({ langle} 1 { rangle}) kvantifiserer å være monoton. Monotonicity er allestedsnærværende blant kvantifikatorer for naturlige språk. Det ser ut til at syntetisk enkle engelske NP-er alle betegner monotone (økende eller reduserende) type ({ langle} 1 { rangle}) kvantifiserere, og nesten alle syntaktisk enkle engelske determinanter betegner riktige monotone kvantifikatorer. [26] Vi har også:

  • (28) a. Kvantifisererne (I_j) (navn) øker
  • b. (Q ^ A) øker (avtar) hvis Q er riktig øker (avtar).

De aristoteliske alle, noen, nei er ensformige i begge argumentene (f.eks. Alt er høyre øker og venstre avtar), og det samme er minst fem, ikke mer enn ti, uendelig mange, mens de fleste, minst to tredjedeler av de høyre øker men verken øker eller avtar i det venstre argumentet. Nøyaktig tre, mellom to og syv er ikke-monotone, selv om begge disse er konjunksjoner av en (høyre og venstre) økning og en synkende kvantifiserer (f.eks. Minst tre og høyst tre), i motsetning til et jevnt antall, som er ikke en (begrenset) boolsk kombinasjon av monotone kvantifikatorer.

Både symmetri og monotonicitet har viktige forklarende roller for visse språklige fenomener. Symmetri er et trekk ved (de fleste av) kvantifiseringsmidlene som er tillatt i såkalte eksistensielle der setninger (f.eks. Det er minst fem menn i hagen er fin, men det er de fleste menn i hagen er ikke). Monotonicity er avgjørende for å forklare fordelingen av polaritetselementer (ingen vil noen gang lykkes er bra, men noen vil lykkes er det ikke: negative polaritetselementer som noen gang krever et synkende miljø). [27] Videre er monotonicity avgjørende involvert i naturlige former for resonnement; se avsnitt 18.

14. Bestemmere som ikke er ISOM

Ta i betraktning

  • (29) Johns bøker ble stjålet.
  • (30) Noen studenters bøker er ikke returnert.
  • (31) Ingen professor utenom Mary kom til møtet.
  • (32) Alle strandgjengere bortsett fra noen få entusiastiske svømmere var fullt kledd.
  • (33) Flere mannlige enn kvinnelige studenter røyker.

Uttrykkene Johns, noen studenters, ingen _ unntatt Mary, alle _ bortsett fra noen få entusiastiske svømmere, mer mannlige enn kvinnelige, blir ganske naturlig sett på som bestemmere: når de kombineres med substantiv, danner de fraser som oppfører seg som vanlige NP-er. Dessuten er typen ({ langle} 1,1 { rangle}) kvantifiserere de signerer Conserv og Ext. Setningene i følgende par er for eksempel trivielt likeverdige:

  • (34) a. Johns bøker ble stjålet.
  • b. Johns bøker er bøker som ble stjålet.

Men i motsetning til de foregående eksemplene, er de ikke Isom, ettersom de involverer noen faste individer eller eiendommer: hvis Johns bøker ble stjålet, og antallet stjålne bøker er det samme som antallet røde blyanter (i noe diskursunivers), og antallet bøker som ikke ble stjålet, er det samme som antallet blyanter som ikke er røde, det følger ikke at Johannes blyanter er røde, slik Isom ville ha det.

Imidlertid, akkurat som ikke-Isom-kvantifisereren tre (^ { textit {student}}) resulterer ved å fryse begrensningsargumentet til Ext-kvantifiserer tre, resulterer ikke-Isom-kvantifisererne ovenfor ved å fryse argumenter i mer abstrakte forhold, som er Isom. Vi illustrerer dette med den besittende avgjøreren Johns. [28]

Med tanke på at John betegner et individ j, kan bestemmeren John's defineres, for alle M og alle (A, B / subseteq M), av [29]

(texttt {John's} _M (A, B) iff / emp / neq A / cap R_j / subseteq B)

hvor (R_j = {b / i M / !: R (j, b) }) og R er en "besitter" -relasjon; det er velkjent at dette forholdet varierer mye med omstendighetene - man kan snakke om bøkene som John eier, eller har skrevet, eller lånt, eller kjøpt som gave til Mary, etc. Anta at R er eierskap. Da (29) sier at John eier minst en bok, og at alle bøkene han eier ble stjålet. Tenk nå på den mer generelle “kvantifiserer” definert, for (a / i M), (R / subseteq M ^ 2), og (A, B / subseteq M), av

(mathbf {P} _M (a, R, A, B) iff / emp / neq A / cap R_a / subseteq B)

Vi kan si at dette er en generalisert kvantifiserer av typen ({ langle} 0,2,1,1 { rangle}), og lar 0 stå for individer. (mathbf {P}) er Isom (utvidende definisjon / eqref {ex-isom} på en åpenbar måte til kvantifiserere av denne typen), og Johns resultater ved å fryse de to første argumentene til passende verdier.

Lignende konstruksjoner fungerer for andre tilfeller av kvantifiseringsuttrykk på naturlige språk som betegner ikke-isom-kvantifiserere. For eksempel angir bestemmelsesstedet ingen _ bortsett fra Mary (gitt at Mary refererer til m)

[(texttt {ingen _ unntatt Mary}) _ M (A, B) iff A / cap B = {m })

Det vil si (31) sier at Mary er professor, at hun kom til møtet, og at ingen andre professor gjorde det. Igjen kan en tilsvarende Isom-kvantifiserer av typen ({ langle} 0,1,1 { rangle}) lett defineres. Så på denne måten kan Isom hentes ut for naturlige språkvantifiserere. På den annen side er det bedre med syntaks å assosiere type ({ langle} 1,1 { rangle}) med determinatorer, og lar mange generaliseringer angående determinatene også i ikke-Isom-saken.

15. Konstanse

Isom, dvs. emneutralitet, blir standard sett på som en nødvendig betingelse for å være en logisk konstant. [30]Det er mulig å skille logikalitet fra konstans i den tidligere nevnte betydningen av det samme over forskjellige universer. For det første er logikalitet en egenskap som bør stenges under definisjon, mens det slett ikke er klart at konstansen bør lukkes på samme måte. Vær for eksempel oppmerksom på at klassen for Ext-kvantifiserere ikke er lukket under førsteordens definabilitet. Mer presist er det stengt under de vanlige boolske operasjonene, men ikke under indre negasjon og dermed ikke under innføring av dualer, der den indre negasjonen av en type ({ langle} 1 { rangle}) kvantifiserer Q er definert av ((Q / neg) _M (A) Leftrightarrow Q_M (M \! - \! A)), og den doble av (Q ^ d = / neg (Q / neg)). For eksempel (eksisterer ^ d = / forall).

En intuisjon kan være at Ext er tilstrekkelig for konstans. Men en annen intuisjon er at en kvantifiserer som betyr det samme på alle universer, spesielt skal tilfredsstille Isom, som tvinger Q til å være den "samme" på alle universer av samme kardinalitet. Disse to ideene er uforenlige, fordi de sammen tilsier at Ext impliserer Isom, som er åpenbart usant. Det er tydelig at den vage forestillingen om å si det samme på tvers av forskjellige univers innrømmer forskjellige presisjoner. Ved nærmere ettersyn virker det usannsynlig at det er en presis versjon som vil romme alle intuisjoner om ensartethet.

I denne situasjonen vil et forslag være å ganske enkelt bestemme at konstans utgjør Ext + Isom. Dette ville være en karnapisk forklaring av konstans. Kvantifiserere med denne kombinasjonen av egenskaper ser ut til å bety det samme på alle universer. På den annen side ville Ext men ikke-Isom-kvantifiserere som tre (^ { textit {student}}) eller noen professorer ikke ha den samme betydningen på tvers av forskjellige domener, som vi så stemmer overens med en intuisjon. Videre er de få naturlige ikke-Ext-kvantifiserere vi har opplevd alle definible fra Ext + Isom-kvantifiserere. [31]

16. Polyadic Natural Language Quantifiers

Tenk på en typisk engelsk setning der både subjekt og objekt er kvantifisert:

(35) De fleste filmene ble anmeldt av to kritikere

Sannhetsbetingelsene til (36) kan gis i form av en polyadisk kvantifiserer, av typen ({ langle} 1,1,2 { rangle}) (utelat M):

[Q (A, B, R) iff / textit {most} (A, {a / !: / textit {two} (B, R_a) }))

(Dette er "smalt omfang" -lesning; lesingen "bredt omfang" vil være i stedet (textit {two} (B, {b / !: / textit {most}) (A, (R ^ {- 1}) _b))).) Men denne polyadiske kvantifisereren er resultatet av to type ({ langle} 1,1 { rangle}) etter en allestedsnærværende konstruksjon som vi kaller iterasjon. Hvis (Q, Q ') er av typen ({ langle} 1 { rangle}), definerte du typen ({ langle} 2 { rangle}) kvantifiserer (Q / cdot Q') av

(tag {36} Q / cdot Q '(R) iff Q ({a / !: Q' (R_a) }))

Deretter oppnår vi iterasjonen av to type ({ langle} 1,1 { rangle}) kvantifiserere (Q_1, Q_2) som ovenfor med (Q_1 ^ A / cdot Q_2 ^ B). Egenskaper ved iterasjoner er studert i van Benthem (1989), Keenan (1992), Westerståhl (1994) og Steinert-Threlkeld og Icard (2013).

Keenan tenker på iterasjon som Frege-grensen. Som han og andre påpekte, ser det ut til å være mange naturlige språkvantifiserere utover denne grensen, dvs. ikke definerbare som iterasjoner. Vi gir noen få eksempler her; mange flere finnes i referansene nettopp gitt. Neste setning kan se ut som å uttrykke en iterasjon, men gjør det faktisk ikke.

(37) Ulike studenter svarte på forskjellige spørsmål under eksamen

Eksempel (37) har antagelig forskjellige tolkninger, for eksempel en som bruker følgende type ({ langle} 1,1,2 { rangle}) kvantifiserer:

[Q (A, B, R) iff / forall a, b / i A (a / neq b / Rightarrow B / cap R_a / neq B / cap R_b))

Denne kvantifisereren er fremdeles definert av første ordre, men ikke en iterasjon. [32] Deretter bør du vurdere

  • (38) a. Folk er vanligvis takknemlige for brannmenn som redder dem.
  • b. Menn foretar sjelden pass på jenter som bruker briller. (Dorothy Parker)

Adverb som vanligvis, sjelden, alltid, kan aldri tas for å betegne generaliserte kvantifiserere (en observasjon opprinnelig gjort i Lewis (1975)). For eksempel er hunder som aldri meow grovt synonymt med Ingen hunder meow. Men for (38) kan det argumenteres for at det er en lesning der kvantifisereren gjelder par: blant parene som består av en person og en brannmann som redder vedkommende, er et flertall slik at personen er takknemlig. Dette er bare gjenopptakelsen av de fleste til par, som vi definerte i / eqref {ex-qlist4}:

[Res ^ 2 (textit {most}) (R, S) iff | R / cap S | > | RS |)

Så i (38b), (R (a, b)) iff (a / in / textit {person}) og (b / in / textit {brannmann}) og (a \: / textit {reddet} b), og (S (a, b)) iff a er takknemlig for b. Det kan vises at for mange kvantifiserere, spesielt de fleste, er (Res ^ n (Q)) ikke definert i (FO (Q)). Faktisk er (Res ^ 2 (textit {most})) ikke definert fra noen endelig antall monadiske kvantifikatorer, så det er et eksempel på en irreducerbelig polyadisk kvantifiserer. [33]

Neste:

  • (39) a. Fem kastere fra Boston satt ved siden av hverandre.
  • b. De fleste av parlamentsmedlemmene viser indirekte til hverandre.

Her (39a) kan ha sannhetsforholdene

(eksisterer X / subseteq / textit {Boston pitcher} [| X | = 5 / amp / textit {RECIP} (X, / textit {satt ved siden av})])

der RECIP er typen ({ langle} 1,2 { rangle}) kvantifiserer definert i / eqref {ex-qlist4}. Det vil si at det er et sett med fem mugger fra Boston slik at hvis du tar to av disse, enten sitter de ved siden av hverandre, eller så er det en mugge, eller to, eller høyst tre (alt i det valgte settet), mellom dem. Tilsvarende for (39b). Dette er bare en av flere konstruksjoner av polyadiske kvantifikatorer som forekommer i gjensidige setninger. [34]

Til slutt, vurder setningen

(40) De fleste gutter i klassen din og de fleste jenter i klassen min har alle datert hverandre

(40) er blitt fremmet som et eksempel på forgreningskvantifisering, som kan skrives i et todimensjonalt logisk format som

  • (41)

    'mest x A (x)' og 'mest y B (y)' hver med linjer til 'R (x, y)'
    'mest x A (x)' og 'mest y B (y)' hver med linjer til 'R (x, y)'

hvor den tiltenkte avlesningen er at det er et underett X av A som inneholder de fleste elementene i A, og et lignende stort underett Y av B, slik at hvert par ((a, b)) hvor (a / i X) og (b / i Y) hører til forholdet R. Mer generelt har vi en polyadisk kvantifiserer av typen ({ langle} 1,1,2 { rangle}) definert for alle (Q_1, Q_2) av typen ({ langle} 1,1 { rangle}) av

(tag {42} label {ex-br} Br (Q_1, Q_2) (A, B, R) iff \\ / eksisterer X / subseteq A \: / exist Y / subseteq B \, [Q_1 (A, X) amp Q_2 (B, Y) amp X / ganger Y / subseteq R])

Ganske plausibelt gir dette en lesning av (40). Legg merke til at x og y her er uavhengige av hverandre. Hvis man i stedet vil bruke noen av de lineære setningene

(textit {most}: x (A (x), / textit {most}: y (B (y), R (x, y))) / \ textit {most}: y (B (y), / textit {most}: x (A (x), R (x, y))))

så avhenger enten y av x eller omvendt. Den todimensjonale syntaks i (41) gjenspeiler denne semantiske uavhengigheten. [35]

Det kan vises at (Br (textit {most}, / textit {most})) ikke er uttrykkelig i (FO (textit {most})) alene; faktisk ikke med noen endelig antall monadiske kvantifikatorer (for et bevis, se Hella, Väänänen og Westerståhl (1997)). På den annen side oppnås forgreningskvantifikatorer med en "løfte" -operasjon brukt på monadiske kvantifiseringsmidler, og tilsvarende for gjenopptakelse. Selv om det naturlige språket har mange polyadiske kvantifiserere langt utenfor Frege-grensen, kan man fremdeles stille et krav for påstanden om at disse alle er oppnådd fra monadiske kvantifiserere på systematiske måter.

17. GQ Teori og lingvistikk

Ankomsten av generaliserte kvantifiserere hadde en stor innvirkning på språklig semantikk via Montages arbeid på slutten av 60-tallet, forsterket av anvendelsen av modellteoretiske metoder på begynnelsen av 80-tallet av Barwise og Cooper, Keenan og Stavi og andre (se note 21). I nesten alle eksempler i disse verkene var det naturlige språket engelsk. Lingvistere har siden brukt og testet verktøyene og metodene for “GQ-teori” på andre språk. Samlingen Bach et al. (1995) har blant annet syv case-studier av kvantifisering på andre språk. Det understreker også skillet mellom D-kvantifisering og A-kvantifisering. I D-kvantifisering, som de fleste av våre eksempler så langt viser, er kvantifiseringsuttrykket (vanligvis) en determiner som gjelder et substantiv. A-kvantifisering utføres på andre måter-A står for adverb, hjelpestoffer,anbringelser og justeringer av argumentstruktur. Mange språk foretrekker A-kvantifisering, noen utelukkende. Engelsk har begge typer; husker kvantifiseringsadverbene i (38).[36]

Nylig har bindene Keenan og Paperno (2012) og Paperno og Keenan (2017) et eget kapittel som svarer på et fast sett med spørsmål om uttrykk for kvantifisering for hvert av 34 forskjellige språk (annerledes også fra de som er nevnt ovenfor), for å lage en omfattende oversikt over ekspressive ressurser. [37]Tilnærmingen er semantisk: spørsmålene er av formen "Kan man uttrykke X på ditt språk, og i så fall på hvilke måter?", Som tillater presise spørsmål om konservativitet, monotonicity, polaritetselementer, monadisk kontra polyadisk kvantifisering, etc. bli satt til hvert språk. Sammendraget i det siste kapittelet viser at mange av generaliseringene som gjelder for engelsk, om eksistensen av uttrykk som angir visse kvantifiserere og egenskapene til disse, også inneholder alle eller de fleste andre språk som er studert (Keenan og Paperno liste 25 slike generaliseringer).

På den annen side, fra begynnelsen av 1990-tallet, har noen språklister hevdet at GQ-teorien ikke er i stand til å redegjøre for en rekke viktige semantiske fenomener - på engelsk og andre språk relatert til kvantifisering. Szabolcsi (2010) gir en detaljert redegjørelse for denne utviklingen. Et spørsmål er at GQ-teorien ser ut til å ikke ha noe å si om komposisjonsbetydningen til komplekse bestemmere. Hvordan er for eksempel betydningen av mer enn fem avledet fra betydningen av delene? Eller vurder det meste, som ofte blir behandlet som en enkel determiner, selv om betydningen på en eller annen måte må komme fra å være en superlativ av mer.

Et annet problematisk fenomen er omfang. Selv om GQ-teorien i prinsippet ser ut til å tillate alle teoretisk mulige omfang av nestede kvantifiseringsuttrykk, har naturlige språk begrensninger som regulerer hvilke av disse som faktisk er tillatt. Faktisk er omfang et hovedtema i språklig syntaks og semantikk, og et sammensatt emne. Problemet er også metodologisk: hvordan bestemme om en gitt setning S faktisk kan bety Y (hvor Y tilsvarer en bestemt omfang)? For det første må man filtrere ut tilfeller der utilgjengeligheten av Y avhenger av fakta om verden, ikke om språk. For det andre, hvis intuisjoner skal telle: språkvitternes, eller de som morsmål i en testsituasjon, eller kanskje statistiske bevis bør spille en rolle? Fortsatt,mens det er sant at mange avlesninger som virker umulige ved første blikk faktisk er tilgjengelige i tilstrekkelig spesifikke sammenhenger, er det sannsynlig at språk har omfangsbegrensninger utenfor rekkevidden til GQ-teorien.[38]

“GQ-teoretikeren” kunne svare at verktøyene hennes aldri var ment å forklare omfanget fullt ut, eller muliggjøre komposisjonsanalyser av hvert komplekst uttrykk. Modellteoretiske rammer er først og fremst beskrivende: det gir matematiske objekter som kan tjene som (modeller av) mening, og formulere egenskaper og forhold mellom disse objektene. Noen ganger avslører fakta om de matematiske objektene innsikt om tingene de modellerer, som for tilfeller av monotonicitet og polaritet, eller om betydningen av sammenlagte substantivfraser. Men det er ingen grunn til å forvente at dette skal skje i alle tilfeller.

Dette er posisjoner i en pågående debatt om rollen til formelle metoder, og særlig modellteoretiske verktøy, i semantikk; en debatt som på ingen måte er avgjort. Det som synes klart er at fenomenene knyttet til kvantifisering på naturlige språk fortsetter å gi utmerket materiale for den diskusjonen.

18. Kvantifisering og erkjennelse

De siste årene har det skjedd en eksplosjon av arbeid som forbinder semantikk, resonnement og erkjennelse, mye av det knyttet til hvordan foredragsholdere forstår og lærer og resonnerer med kvantifiserte uttrykk. En viktig forskningsdel angår monotonicity (seksjon 13). Allerede Barwise og Cooper (1981) bemerket tilstedeværelsen av monotone kvantifiserere på naturlige språk, og foreslo en måte å vise at monotone kvantifiserere er enklere å behandle enn ikke-monotone kvantifikatorer, og at økende kvantifiserere er lettere enn å redusere. De antydet også at psykologiske eksperimenter kunne brukes til å teste hypotesen deres. Deres tekniske forslag ble videreutviklet i van Benthem (1986), som introduserte en forestilling om tellekompleksitet og viste at under noen forutsetningerkvantifisererne med minimal tellekompleksitet er nettopp de med en viss sterk monotonicitetseiendom.[39]

Monotonicity er også involvert i det van Benthem har kalt “ett-trinns” resonnement, som ser ut til å være lett tilgjengelig for høyttalere. Enkle oppførselen til grunnleggende bestemmere viser allerede hvordan en slik begrunnelse er lisensiert. Når du markerer høyre økende (avtagende) type ({ langle} 1,1 { rangle}) kvantifiserere med en + (a (-)) til høyre, og på samme måte for venstre monotonicity, har vi for eksempel:

(- / textit {hver} +) (+ / textit {noen} +) (- / textit {no} -) (cdot \, / textit {most} +) (cdot \, / textit {nøyaktig tre}, / cdot)

der (cdot) markerer at stillingen verken synker eller øker. Et fint eksempel er følgende inferanse (fra Icard og Moss (2014), tilpasse et eksempel i Geurts og Slik (2005)):

(43) De fleste amerikanere som kjenner et fremmedspråk, snakker det hjemme De fleste amerikanere som kjenner et fremmedspråk, snakker det hjemme eller på jobben

Forutsetningen er en "eselsetning" med de fleste, og det er notorisk vanskelig å finne de eksakte sannhetsforholdene for disse. Faktisk er flere avlesninger mulig. [40] På tross av dette ser det ut til at høyttalere ikke har noe problem med å gjøre denne slutningen, tilsynelatende siden de fleste er riktig økende (VP-argumentet snakker det hjemme utvides til å snakke det hjemme eller på jobben), uavhengig av hva emnet setning (det samme i begge setninger) betyr nøyaktig.

Mange andre uttrykk og uttrykk foruten bestemmere viser faste monotonicitetsmønstre. Fra og med van Benthem (1986) har dette ført til algoritmer for hvordan polaritetsmarkører tilordnes nodene til analysetrær av setninger (i forhold til en gitt grammatikk), eller hvordan man kan innlemme slike markører direkte i typeanmeldelsen; se Icard og Moss (2014) for en oversikt og ytterligere referanser. Foruten deres rolle i inferens, kan slik markering også forklare, og noen ganger til og med forutsi, fordelingen av negative polaritetselementer på språk (slutten av seksjon 13). Dessuten er det i mange tilfeller ingen syntaktisk analyse nødvendig: det kan gjøres konklusjoner direkte på overflateform, og vil i denne forstand være tilgjengelig "på fly" for høyttalere; sammenligne (43). Artikkelen som nettopp er nevnt presenterer også en fullstendig aksiomatisering av en formell Monotonicity Calculus,der mange varianter av resonnement med monotonicity kan komme til uttrykk.[41]

En noe parallell utvikling har vært den formelle studien av forskjellige syllogistiske fragmenter; vi bemerket i seksjon 2 at mange syllogismer uttrykker monotonicity egenskaper. Disse fragmentene, hvorav de fleste er studert av Ian Pratt-Hartmann og fremfor alt Larry Moss, spenner fra de som inneholder bare enkle setninger som allXY eller someXY til dem som lar komplimenter, relative klausuler, transitive verb, ikke-førsteordens kvantifiserere som de fleste, og andre funksjoner. Her er et eksempel (Moss pc) på en slutning i et slikt fragment:

Alle liker alle som liker Pat Pat liker hver klarinettist Alle liker alle som liker alle som liker hver klarinettist

Dette illustrerer hvordan ganske involvert resonnement kan komme til uttrykk i et enkelt syllogistisk-lignende språk. Inferensen er gyldig, men man må tenke litt for å se det. [42] Et hovedtrekk ved de fleste av disse fragmentene er at i tillegg til å ha eksplisitte fullstendige aksiomatiseringer, kan gyldigheten i dem avgjøres, i motsetning til førsteordens logikk. Dette gjelder også for noen fragmenter med kvantifiseringsmidler som ikke er FO-definerbare. I likhet med monotonicity-beregningen er studiet av syllogistiske fragmenter en del av bedriften noe løst kalt naturlig logikk, noe som resulterer i veloppførte delsystemer av mer kjente logikker, i den forstand at de både er nærmere naturlig språk og beregningsmessig mer gjennomførbare; se Moss (2015) for en undersøkelse. [43]

På den kognitive siden har spørsmål om forståelse og læring relatert til kvantifisering og monotonicitet blitt studert både innen psykologi og nevrovitenskap. Geurts og Slik (2005) spurte forsøkspersoner om bestemte slutninger som involverte monotonicity var gyldige eller ikke; resultatene stadfestet i stor grad Barwise og Cooper tidligere hypoteser. Betydningen av individuelle bestemmere er også studert empirisk; Pietroski et al. (2009) undersøkte det meste, hvor metoden var å vise forsøkspersoner et bilde med gule og blå prikker i veldig kort tid (for å eliminere telling) og spørre, si om det er sant eller usant at de fleste av prikkene er gule. Variasjoner av denne typen eksperiment er vanlige i litteraturen; en nylig forekomst er Odic et al. (2018), som studerer skillet om masse / telle i kognisjon og semantikk. Begge studiene involverer menneskelig tallfølelse og dens forhold til forståelse av kvantifiseringsspråk. Man kan underholde en "whorfian" -hypotese om at sistnevnte er en forutsetning for førstnevnte. Dette ble testet med nevrobiologiske metoder (hjerneskanningsmetoder kombinert med psykologiske tester med pasienter som lider av forskjellige hjerneforstyrrelser) i Clark og Grossman (2007). De fant ingen empirisk støtte for den hypotesen; se også Clark (2011a) for en beskrivelse av eksperimentet og mer om forskning på kvantifisering og tallfølelse. Dette ble testet med nevrobiologiske metoder (hjerneskanningsmetoder kombinert med psykologiske tester med pasienter som lider av forskjellige hjernesykdommer) i Clark og Grossman (2007). De fant ingen empirisk støtte for den hypotesen; se også Clark (2011a) for en beskrivelse av eksperimentet og mer om forskning på kvantifisering og tallfølelse. Dette ble testet med nevrobiologiske metoder (hjerneskanningsmetoder kombinert med psykologiske tester med pasienter som lider av forskjellige hjernesykdommer) i Clark og Grossman (2007). De fant ingen empirisk støtte for den hypotesen; se også Clark (2011a) for en beskrivelse av eksperimentet og mer om forskning på kvantifisering og tallfølelse.

Det foreligger nå en god del empiriske studier av hvordan ulike klasser av kvantifiserere identifisert ved logiske eller beregningsmessige midler reflekteres i form av læring, forståelse, kognitiv belastning, osv. Omvendt, språklige og kognitive fakta antyder nye teoretiske spørsmål. For eksempel, med hensyn til beregningskompleksitet, viste Sevenster (2006) at forgreningen av de fleste som i (40) i seksjon 9 er intractable. [44]Deretter observerte Szymanik at hvis operasjonene for gjenopptakelse og iterasjon (som i henholdsvis (38) og (36)) blir brukt på PTIME-kvantifiserere, er resultatet igjen i PTIME, i motsetning til forgrening. Tilsvarende bevarer noen former for gjensidige konstruksjoner PTIME-regnbarhet, mens andre ikke gjør "å løfte" nøyaktig fem med RECIP som i (39a), men på samme måte løfter de fleste som i (39b) ikke.

I van Benthems semantiske automatinnstilling (seksjon 9) beviste Steinert-Threlkeld og Icard (2013) at Frege-grensen (seksjon 16) er robust i den forstand at hvis to Conserv og Ext type ({ langle} 1,1 { rangle}) kvantifiserere kan gjenkjennes med begrensede (eller nedtrekkbare) automater, og det samme er iterasjonen. Dessuten viste Steinert-Threlkeld (2016) at for store klasser av type ({ langle} 1,1,2 { rangle}) kvantifiserere, kan det avgjøres om de er iterasjoner av type ({ langle} 1, 1 { rangle}) kvantifiserere eller ikke. En nylig presentasjon av både teoretiske og empiriske resultater rundt de kognitive aspektene ved kvantifiseringsgjenkjenning er Szymanik (2016).

Det er gitt beregningsmodeller for å lære betydningen av kvantifiserere; for eksempel av Clark (2011a) i den semantiske automatinnstillingen. I en nyere utvikling studerer Steinert-Threlkeld og Szymanik (kommende) lærbarhet med teknologien i nevrale nettverk, og tester om visse kvantifiserere som tilfredsstiller tre ofte foreslåtte universaler - at enkle bestemmelsesbetegnelser er henholdsvis monoton, Isom og Conserv - er lettere å lære enn kvantifiserere som ikke har disse egenskapene. For hver universell blir tiden det tar nettverket å lære en kvantifiserer som tilfredsstiller den sammenlignet med tiden det tar å lære en kvantifiserer som ikke gjør det. Det viser seg at monoton og Isom er enklere enn ikke-monotone og ikke-Isom, mens det ikke er noen påvisbar forskjell for Conserv. [45]

Dette er bare glimt av pågående forskning. Undersøkelsen av hvordan foredragsholdere behandler kvantifiserte uttrykk, og kombinerer den grunnleggende modellteoretiske analysen med metoder fra psykologi, nevrovitenskap og informatikk, er nå et rikt område i studien av generaliserte kvantifiserere.

Bibliografi

  • Bach, Emmon, Eloise Jelinek, Angelika Kratzer, og Barbara H. Partee (red.), 1995, Kvantifisering i naturlige språk, (Studies in Linguistics and Philosophy 54), Dordrecht: Springer Netherlands. doi: 10,1007 / 978-94-017-2817-1
  • Barwise, Jon, 1979, “On Branching Quantifiers in English”, Journal of Philosophical Logic, 8 (1): 47–80. doi: 10,1007 / BF00258419
  • Barwise, Jon og Robin Cooper, 1981, “Generalised Quantifiers and Natural Language”, Linguistics and Philosophy, 4 (2): 159–219. doi: 10,1007 / BF00350139
  • Barwise, Jon og Solomon Feferman (red.), 1985, Model Theoretic Logics, (Perspectives in Mathematical Logic), New York: Springer-Verlag.
  • van Benthem, Johan, 1986, Essays in Logical Semantics, (Studies in Linguistics and Philosophy, 29), Dordrecht: D. Reidel.
  • –––, 1989, “Polyadic Quantifiers”, Linguistics and Philosophy, 12 (4): 437–464. doi: 10,1007 / BF00632472
  • van Benthem, Johan FAK og Alice ter Meulen (red.), 2011, Handbook of Logic and Language, andre utgave, Amsterdam: Elsevier.
  • Bonnay, Denis, 2008, “Logicality and Invariance”, Bulletin of Symbolic Logic, 14 (1): 29–68. doi: 10,2178 / bsl / 1208358843
  • Cartwright, Richard L., 1994, “Speaking of Everything”, Noûs, 28 (1): 1–20. doi: 10,2307 / 2215917
  • Clark, Robin, 2011a, “Generalised Quantifiers and Number Sense”, Philosophy Compass, 6 (9): 611–621. doi: 10.1111 / j.1747-9991.2011.00419.x
  • ––– 2011b, “Om læremidlene til kvantifiseringer”, i van Benthem og ter Meulen 2011: 911–923.
  • Clark, Robin og Murray Grossman, 2007, “Number Sense and Quantifier Interpretation”, Topoi, 26 (1): 51–62. doi: 10,1007 / s11245-006-9008-2
  • Dalrymple, Mary, Makoto Kanazawa, Yookyung Kim, Sam McHombo og Stanley Peters, 1998, “Gjensidige uttrykk og gjensidighetsbegrepet”, Linguistics and Philosophy, 21 (2): 159–210. doi: 10,1023 / A: 1005330227480
  • Ebbinghaus, Heinz-Dieter og Jörg Flum, 1995, Finite Model Theory, (Springer Monographs in Mathematics), Berlin: Springer Berlin Heidelberg. doi: 10,1007 / 3-540-28788-4
  • Ebbinghaus, Heinz-Dieter, Jörg Flum og Wolfgang Thomas, 1994, Mathematical Logic (Einführung in die mathematatische Logik), andre utgave, New York: Springer-Verlag. doi: 10,1007 / 978-1-4757-2355-7
  • Filin Karlsson, Martin, 2017, “All There Is: On the Semantics of Quantification over Absolutely Everything”, Ph. D. Oppgave, Universitetet i Gøteborg, (Acta Philosophica Gothoburgensia 31). [Karlsson 2017 tilgjengelig online]
  • Geurts, Bart og Frans van der Slik, 2005, “Monotonicity and Processing Load”, Journal of Semantics, 22 (1): 97–117. doi: 10,1093 / jos / ffh018
  • Glanzberg, Michael, 2004, “Kvantifisering og realisme”, Filosofi og fenomenologisk forskning, 69 (3): 541–572. doi: 10.1111 / j.1933-1592.2004.tb00518.x
  • Hackl, Martin, 2000, “Comparative Quantifiers”, PhD Thesis, Massachusetts Institute of Technology. [Hackl 2000 tilgjengelig online]
  • Hella, Lauri, 1989, “Definabilitetshierarkier av generaliserte kvantifiserere”, Annals of Pure and Applied Logic, 43 (3): 235–271. doi: 10.1016 / 0168-0072 (89) 90070-5
  • Hella, Lauri, Jouko Väänänen og Dag Westerståhl, 1997, “Definabilitet av polyadiske heiser av generaliserte kvantifiserere”, Journal of Logic, Language and Information, 6 (3): 305–335. doi: 10,1023 / A: 1008215718090
  • Henkin, Leon, 1961, "Noen kommentarer om uendelig lange formler", i infinitistiske metoder: Proceedings of the Symposium on Foundations of Mathematics, Warszawa, 2-9 september 1959, Oxford: Pergamon Press, 167–183.
  • Higginbotham, James og Robert May, 1981, “Spørsmål, kvantifiseringer og kryssing”, The Linguistic Review, 1 (1): 41–79. doi: 10,1515 / tlir.1981.1.1.41
  • Hintikka, Jaakko, 1973, “Quantifiers vs. Quantification Theory”, Dialectica, 27 (3–4): 329–358. doi: 10.1111 / j.1746-8361.1973.tb00624.x
  • Hopcroft, John E. og Jeffrey D. Ullman, 1979, Introduction to Automata Theory, Language and Computation, (Addison-Wesley Series in Computer Science), Reading, MA: Addison-Wesley.
  • Icard III, Thomas F., 2014, “Higher-Order Syllogistics”, i Formell grammatikk 2014, Glyn Morrill, Reinhard Muskens, Rainer Osswald, og Frank Richter (red.), (Lecture Notes in Computer Science 8612), Berlin, Heidelberg: Springer Berlin Heidelberg, 1–14. doi: 10,1007 / 978-3-662-44121-3_1
  • Icard III, Thomas Icard og Lawrence S. Moss, 2014, “Recent Progress in Monotonicity”, i Perspectives on Semantic Representations for Textual Inference, (LiLT 9), Stanford, CA: CSLI Publications, 167–194. [Icard and Moss 2014 tilgjengelig online]
  • Icard, Thomas, Lawrence Moss og William Tune, 2017, “A Monotonicity Calculus and its Completeness”, i Proceedings of the 15. Meeting on the Mathematics of Language, London, UK: Association for Computational Linguistics, 75–87. doi: 10,18653 / v1 / W17-3408
  • Keenan, Edward L., 1992, “Beyond the Frege Boundary”, Linguistics and Philosophy, 15 (2): 199–221. doi: 10,1007 / BF00635807
  • Keenan, Edward L. og Leonard M. Faltz, 1984, Boolean Semantics for Natural Language, Dordrecht: Springer Netherlands. doi: 10,1007 / 978-94-009-6404-4
  • Keenan, Edward L. og Lawrence S. Moss, 1985, “Generalised Quantifiers and the Expressive Power of Natural Language”, i Generalised Quantifiers in Natural Language, Alice ter Meulen og Johan van Benthem (red.), Berlin, Boston: De Gruyter, 73–124. doi: 10,1515 / 9783110867909,73
  • Keenan, Edward L. og Denis Paperno (red.), 2012, Handbook of Quantifiers in Natural Language, (Studies in Linguistics and Philosophy 90), Dordrecht: Springer Netherlands. doi: 10,1007 / 978-94-007-2681-9
  • Keenan, Edward L. og Jonathan Stavi, 1986, “En semantisk karakterisering av naturlige språkbestemmere”, lingvistikk og filosofi, 9 (3): 253–326. doi: 10,1007 / BF00630273
  • Keenan, Edward L. og Dag Westerståhl, 2011, “Generalised Quantifiers in Linguistics and Logic”, i van Benthem og ter Meulen 2011: 859–910.
  • Lewis, David, 1975, “Adverbs of Quantification”, i Formal Semantics of Natural Language, Edward L. Keenan (red.), Cambridge: Cambridge University Press, 3–15. doi: 10,1017 / CBO9780511897696.003
  • Lindström, Per, 1966, “First Order Predicate Logic with Generalised Quantifiers”, Theoria, 32 (3): 186–195. doi: 10.1111 / j.1755-2567.1966.tb00600.x
  • Linnebo, Øystein, 2006, “Sets, Properties and Unrestricted Quantification”, i Rayo og Uzquiano 2006: 149–178.
  • Luosto, Kerkko, 2000, “Hierarchies of Monadic Generalised Quantifiers”, Journal of Symbolic Logic, 65 (3): 1241–1263. doi: 10,2307 / 2586699
  • Montague, Richard, 1974, Formal Philosophy: Selected Papers of Richard Montague, Richmond H. Thomason (red.), New Haven, CT: Yale University Press.
  • Moss, Lawrence S., 2015, “Natural Logic”, i The Handbook of Contemporary Semantic Theory, Shalom Lappin og Chris Fox (red.), Andre utgave, John Wiley & Sons, 646–681.
  • Mostowski, Andrzej, 1957, “On a Generalization of Quantifiers”, Fundamenta Mathematicae, 44 (1): 12–36. doi: 10,4064 / fm-44-1-12-36
  • Mostowski, Marcin, 1998, “Computational Semantics for Monadic Quantifiers”, Journal of Applied Non-Classical Logics, 8 (1–2): 107–121. doi: 10,1080 / 11663081.1998.10510934
  • Odic, Darko, Paul Pietroski, Tim Hunter, Justin Halberda og Jeffrey Lidz, 2018, “Individuals and Non-Individuals in Cognition and Semantics: The Mass / Count Distinction and Quantity Representation”, Glossa: A Journal of General Linguistics, 3 (1): 61. doi: 10.5334 / gjgl.409
  • Paperno, Denis og Edward L. Keenan (red.), 2017, Handbook of Quantifiers in Natural Language: Volume II, (Studies in Linguistics and Philosophy 97), Cham: Springer International Publishing. doi: 10,1007 / 978-3-319-44330-0
  • Parsons, Terence, 1997 [2017], “The Traditional Square of Opposition”, The Stanford Encyclopedia of Philosophy, (Sommer 2017), Edward N. Zalta (red.). URL =
  • Peters, Stanley og Dag Westerståhl, 2002, “Does English Really Have Resumptive Quantification?”, I The Construction of Meaning, David I. Beaver, Luis D. Casillas Martínez, Brady Z. Clark, og Stefan Kaufmann (red.), Stanford, CA: CSLI Publications, 181–195.
  • –––, 2006, Quantifiers in Language and Logic, Oxford: Oxford University Press. doi: 10,1093 / acprof: oso / 9780199291267.001.0001
  • –––, 2013, “The Semantics of Possessives”, Språk, 89 (4): 713–759. doi: 10,1353 / lan.2013.0065
  • Pietroski, Paul, Jeffrey Lidz, Tim Hunter, og Justin Halberda, 2009, "Betydningen av 'mest': Semantikk, Numerosity and Psychology", Mind & Language, 24 (5): 554–585. doi: 10.1111 / j.1468-0017.2009.01374.x
  • Rayo, Agustín, 2012, “Absolute Generality Reconsidered”, i Oxford Studies in Metaphysics bind 7, Karen Bennett og Dean W. Zimmerman (red.), Oxford: Oxford University Press, 93–126. doi: 10,1093 / acprof: oso / 9780199659081.003.0004
  • Rayo, Agustín og Gabriel Uzquiano (red.), 2006, Absolute Generality, Oxford: Clarendon Press.
  • Sher, Gila Y., 1997, “Delvis ordnet (forgrening) generaliserte kvantifiserere: En generell definisjon”, Journal of Philosophical Logic, 26 (1): 1–43. doi: 10,1023 / A: 1017944808396
  • Steinert-Threlkeld, Shane, 2016, “Some Properties of Iterated Language”, Journal of Logic, Language and Information, 25 (2): 191–213. doi: 10,1007 / s10849-016-9239-6
  • Steinert-Threlkeld, Shane og Thomas F. Icard III, 2013, “Iterating Semantic Automata”, Linguistics and Philosophy, 36 (2): 151–173. doi: 10,1007 / s10988-013-9132-6
  • Steinert-Threlkeld, Shane og Jakub Szymanik, forestående, “Lærbarhet og semantiske universiteter”, semantikk og pragmatikk. [Steinert-Threlkeld og Szymanik kommer tilgjengelig online]
  • Szabolcsi, Anna, 2010, Kvantifisering, Cambridge: Cambridge University Press. doi: 10,1017 / CBO9780511781681
  • Szymanik, Jakub, 2016, Quantifiers and Cognition: Logical and Computational Perspectives, (Studies in Linguistics and Philosophy 96), Cham: Springer International Publishing. doi: 10,1007 / 978-3-319-28749-2
  • Westerståhl, Dag, 1987, “Branching Generalised Quantifiers and Natural Language”, i Generalised Quantifiers, Peter Gärdenfors (red.) (Studies in Linguistics and Philosophy 31), Dordrecht: Springer Netherlands, 269–298. doi: 10,1007 / 978-94-009-3381-1_10
  • –––, 1989, “Kvantifiserer i formelle og naturlige språk”, i Handbook of Philosophical Logic, Dov M. Gabbay og Franz Guenthner (red.), Dordrecht: Springer Netherlands, 4: 1–131. Reprinted, 2007, Handbook of Philosophical Logic, Dov M. Gabbay og Franz Guenthner (red.), Dordrecht: Springer Netherlands, 14: 223–338. doi: 10,1007 / 978-1-4020-6324-4_4
  • –––, 1994, “Iterated Quantifiers”, i Dynamics, Polarity and Quantification, Makoto Kanazawa og Christopher J. Piñón (red.), (CSLI Lecture Notes 48), Stanford, CA: CSLI Publications, 173–209.
  • –––, 2012, “Classical vs. Modern Squares of Opposition and Beyond”, i The Square of Opposition: A General Framework for Cognition, Jean-Yves Beziau og Gillman Payette (red.), Bern: P. Lang, 195 -229.
  • –––, 2017, “Sameness”, i Feferman on Foundations, Gerhard Jäger og Wilfried Sieg (red.), (Fremragende bidrag til logikk 13), Cham: Springer International Publishing, 449–467. doi: 10,1007 / 978-3-319-63334-3_16
  • Williamson, Timothy, 2003, “Alt”, Philosophical Perspectives, 17 (1): 415–465. doi: 10.1111 / j.1520-8583.2003.00017.x

Akademiske verktøy

september mann ikon
september mann ikon
Hvordan sitere denne oppføringen.
september mann ikon
september mann ikon
Forhåndsvis PDF-versjonen av denne oppføringen hos Friends of the SEP Society.
inpho-ikonet
inpho-ikonet
Slå opp dette emnet på Internet Philosophy Ontology Project (InPhO).
phil papirer ikon
phil papirer ikon
Forbedret bibliografi for denne oppføringen på PhilPapers, med lenker til databasen.

Andre internettressurser

[Ta kontakt med forfatteren med forslag.]