Квантификатор ветвления

В логике квантор ветвления ^[1], также называемый квантором Хенкина , конечным частично упорядоченным квантором или даже нелинейным квантором , представляет собой частичное упорядочение ^[2].

${\displaystyle \langle Qx_{1}\dots Qx_{n}\rangle }$

кванторов для Q  ∈ {∀,∃}. Это частный случай обобщенного квантора . В классической логике префиксы кванторов линейно упорядочены так, что значение переменной y m _, связанной квантором Q _{m ,} зависит от значения переменных

у ₁ , ..., у _{м −1}

связанный квантификаторами

Qy ₁ , ..., Qy _{m −1}

предшествующий Q _m . В логике с (конечной) частично упорядоченной квантификацией это, как правило, не так.

Ветвящаяся квантификация впервые появилась в докладе Леона Хенкина на конференции 1959 года . ^[3] Системы частично упорядоченной квантификации являются промежуточными по силе между логикой первого порядка и логикой второго порядка . Они используются в качестве основы для дружественной к независимости логики Хинтикки и Габриэля Санду .

Определение и свойства

Простейший квантификатор Хенкина — это ${\displaystyle Q_{H}}$

${\displaystyle (Q_{H}x_{1},x_{2},y_{1},y_{2})\varphi (x_{1},x_{2},y_{1},y_{2})\equiv {\begin{pmatrix}\forall x_{1}\,\exists y_{1}\\\forall x_{2}\,\exists y_{2}\end{pmatrix}}\varphi (x_{1},x_{2},y_{1},y_{2}).}$

Она (фактически каждая формула с префиксом Хенкина, а не только самая простая) эквивалентна своей скулемизации второго порядка , т.е.

${\displaystyle \exists f\,\exists g\,\forall x_{1}\forall x_{2}\,\varphi (x_{1},x_{2},f(x_{1}),g(x_{2})).}$

Он также достаточно эффективен, чтобы определить квантификатор (т.е. «существует бесконечно много»), определяемый как ${\displaystyle Q_{\geq \mathbb {N} }}$

${\displaystyle (Q_{\geq \mathbb {N} }x)\varphi (x)\equiv (\exists a)(Q_{H}x_{1},x_{2},y_{1},y_{2})[\varphi (a)\land (x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land (\varphi (x_{1})\rightarrow (\varphi (y_{1})\land y_{1}\neq a))].}$

Из этого следует несколько вещей, включая неаксиоматизируемость логики первого порядка с (впервые обнаруженную Эренфойхтом ) и ее эквивалентность -фрагменту логики второго порядка ( экзистенциальной логике второго порядка ) — последний результат был опубликован независимо в 1970 году Гербертом Эндертоном ^[4] и У. Уолкоу. ^[5] ${\displaystyle Q_{H}}$ ${\displaystyle \Sigma _{1}^{1}}$

Следующие квантификаторы также определяются с помощью . ^[2] ${\displaystyle Q_{H}}$

• Решер: «Число φ меньше или равно числу ψ »

${\displaystyle (Q_{L}x)(\varphi x,\psi x)\equiv \operatorname {Card} (\{x\colon \varphi x\})\leq \operatorname {Card} (\{x\colon \psi x\})\equiv (Q_{H}x_{1}x_{2}y_{1}y_{2})[(x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land (\varphi x_{1}\rightarrow \psi y_{1})]}$

• Хартиг: « φ равночисленны с ψ »

${\displaystyle (Q_{I}x)(\varphi x,\psi x)\equiv (Q_{L}x)(\varphi x,\psi x)\land (Q_{L}x)(\psi x,\varphi x)}$

• Чан: «Число φ равно числу областей определения модели»

${\displaystyle (Q_{C}x)(\varphi x)\equiv (Q_{L}x)(x=x,\varphi x)}$

Квантификатор Хенкина сам по себе может быть выражен как квантификатор Линдстрёма типа (4) . ^[2] ${\displaystyle Q_{H}}$

Отношение к естественным языкам

Хинтикка в своей статье 1973 года ^[6] выдвинул гипотезу о том, что некоторые предложения в естественных языках лучше всего понимать с точки зрения квантификаторов ветвления, например: «какой-то родственник каждого жителя деревни и какой-то родственник каждого горожанина ненавидят друг друга» следует интерпретировать, по мнению Хинтикки, как: ^{[7] [8]}

${\displaystyle {\begin{pmatrix}\forall x_{1}\,\exists y_{1}\\\forall x_{2}\,\exists y_{2}\end{pmatrix}}[(V(x_{1})\wedge T(x_{2}))\rightarrow (R(x_{1},y_{1})\wedge R(x_{2},y_{2})\wedge H(y_{1},y_{2})\wedge H(y_{2},y_{1}))].}$

который, как известно, не имеет эквивалента в логике первого порядка. ^[7]

Идея ветвления не обязательно ограничивается использованием классических квантификаторов в качестве листьев. В статье 1979 года ^[9] Джон Барвайз предложил вариации предложений Хинтикка (как иногда называют вышеприведенное), в которых внутренние квантификаторы сами являются обобщенными квантификаторами , например: «Большинство сельских жителей и большинство городских жителей ненавидят друг друга». ^[7] Заметив, что это не закрыто отрицанием, Барвайз также предложил практический тест для определения того, действительно ли предложения на естественном языке содержат квантификаторы ветвления, а именно, для проверки того, содержит ли их отрицание на естественном языке универсальную квантификацию по заданной переменной (предложению ). ^[10] ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle \Pi _{1}^{1}}$

Предложение Хинтикки было встречено скептически рядом логиков, поскольку некоторые предложения первого порядка, подобные приведенному ниже, по-видимому, достаточно хорошо отражают предложение Хинтикки на естественном языке.

${\displaystyle [\forall x_{1}\,\exists y_{1}\,\forall x_{2}\,\exists y_{2}\,\varphi (x_{1},x_{2},y_{1},y_{2})]\wedge [\forall x_{2}\,\exists y_{2}\,\forall x_{1}\,\exists y_{1}\,\varphi (x_{1},x_{2},y_{1},y_{2})]}$

где

${\displaystyle \varphi (x_{1},x_{2},y_{1},y_{2})}$

обозначает

${\displaystyle (V(x_{1})\wedge T(x_{2}))\rightarrow (R(x_{1},y_{1})\wedge R(x_{2},y_{2})\wedge H(y_{1},y_{2})\wedge H(y_{2},y_{1}))}$

Хотя затем последовало много чисто теоретических дебатов, только в 2009 году некоторые эмпирические тесты со студентами, обучавшимися логике, показали, что они с большей вероятностью назначают модели, соответствующие «двунаправленному» предложению первого порядка, а не предложению с квантификатором ветвления, нескольким конструкциям естественного языка, полученным из предложения Хинтикки. Например, студентам показывали неориентированные двудольные графы — с квадратами и кругами в качестве вершин — и просили сказать, правильно ли описывают диаграммы предложения типа «более 3 кругов и более 3 квадратов соединены линиями». ^[7]

Смотрите также

• Семантика игры
• Логика зависимости
• Логика, дружественная независимости (логика IF)
• Квантификатор Мостовского
• Квантификатор Линдстрема
• Непервоупорядочиваемость

Ссылки

1. Стэнли Питерс; Даг Вестерстол (2006). Квантификаторы в языке и логике . Clarendon Press. С. 66–72. ISBN 978-0-19-929125-0.
2. Антонио Бадиа (2009). Квантификаторы в действии: обобщенная квантификация в запросах, логических и естественных языках. Springer. стр. 74–76. ISBN 978-0-387-09563-9.
3. Хенкин, Л. «Некоторые замечания о бесконечно длинных формулах». Инфинитистские методы: материалы симпозиума по основам математики, Варшава, 2–9 сентября 1959 г. , Panstwowe Wydawnictwo Naukowe и Pergamon Press, Варшава, 1961, стр. 167–183. ОСЛК  2277863
4. Яакко Хинтикка и Габриэль Санду, «Теоретико-игровая семантика», в Справочнике по логике и языку , под ред. Дж. ван Бентема и А. тер Мейлена , Elsevier 2011 (2-е изд.) со ссылкой на Enderton, HB, 1970. Конечные частично упорядоченные квантификаторы. Z. Math. Logik Grundlag. Math. 16, 393–397 doi :10.1002/malq.19700160802.
5. Бласс, А.; Гуревич, Ю. (1986). «Кванторы Хенкина и полные проблемы» (PDF) . Annals of Pure and Applied Logic . 32 : 1–16. doi :10.1016/0168-0072(86)90040-0. hdl : 2027.42/26312 .цитируя W. Walkoe, Конечная частично-упорядоченная квантификация, Журнал символической логики 35 (1970) 535–555. JSTOR  2271440
6. Хинтикка, Дж. (1973). «Квантификаторы против теории квантификации». Dialectica . 27 (3–4): 329–358. doi :10.1111/j.1746-8361.1973.tb00624.x.
7. Gierasimczuk, N.; Szymanik, J. (2009). "Ветвящаяся квантификация против двухсторонней квантификации" (PDF) . Журнал семантики . 26 (4): 367. doi :10.1093/jos/ffp008.
8. Шер, Г. (1990). «Способы ветвления кванторов» (PDF) . Лингвистика и философия . 13 (4): 393–422. doi :10.1007/BF00630749. S2CID  61362436.
9. Barwise, J. (1979). «О разветвленных квантификаторах в английском языке». Журнал философской логики . 8 : 47–80. doi :10.1007/BF00258419. S2CID  31950692.
10. Hand, Michael (1998). "Обзорная работа: On Branching Quantifiers in English, Jon Barwise; Branching Generalized Quantifiers and Natural Language. Generalized Quantifiers, Linguistic and Logical Approaches, Dag Westerståhl, Peter Gärdenfors; Ways of Branching Quantifiers, Gila Sher". Журнал символической логики . 63 (4): 1611–1614. doi :10.2307/2586678. JSTOR  2586678. S2CID  117833401.

Внешние ссылки

• Теоретико-игровой квантификатор в PlanetMath.