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

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

${displaystyle langle Qx_{1}dots Qx_{n}angle }$

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

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

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

Qy₁, ..., Qy_м−1

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

Количественная оценка ветвления впервые появилась в документе конференции 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 {egin{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 aland (x_{1}=x_{2}leftrightarrow y_{1}=y_{2})land (varphi (x_{1})ightarrow (varphi (y_{1})land y_{1}eq a))].}$

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

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

• Решер: "Количество φs меньше или равно количеству ψs "

${displaystyle (Q_{L}x)(varphi x,psi x)equiv operatorname {Card} ({xcolon varphi x})leq operatorname {Card} ({xcolon 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}ightarrow psi y_{1})]}$

• Хертиг: " φравноденственны ψs "

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

• Чанг: "Количество φs равнозначна области модели "

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

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

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

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

${displaystyle {egin{pmatrix}forall x_{1},exists y_{1}forall x_{2},exists y_{2}end{pmatrix}}[(V(x_{1})wedge T(x_{2}))ightarrow (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] Джон Барвайз предложенные варианты предложений Hintikka (как иногда называют вышеупомянутое), в которых внутренние кванторы сами являются обобщенные кванторы, например: «Большинство жителей деревни и большинство горожан ненавидят друг друга».^[7] Наблюдая за этим ${displaystyle Sigma _{1}^{1}}$ не закрывается при отрицании, Барвайз также предложил практический тест, чтобы определить, действительно ли предложения на естественном языке включают кванторы ветвления, а именно проверить, включает ли их отрицание на естественном языке универсальную количественную оценку по заданной переменной ( ${displaystyle Pi _{1}^{1}}$ приговор).^[10]

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

${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}))ightarrow (R(x_{1},y_{1})wedge R(x_{2},y_{2})wedge H(y_{1},y_{2})wedge H(y_{2},y_{1}))}$

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

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

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

Рекомендации

1. Стэнли Питерс; Даг Вестерстол (2006). Квантификаторы в языке и логике. Кларендон Пресс. С. 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. OCLC  2277863
4. Яакко Хинтикка и Габриэль Санду, «Теоретико-игровая семантика», в Справочник по логике и языку, изд. J. van Benthem и A. ter Meulen, Elsevier 2011 (2-е изд.) Со ссылкой на Enderton, H.B., 1970. Конечные частично упорядоченные кванторы. Z. Math. Logik Grundlag. Математика. 16, 393–397 Дои:10.1002 / malq.19700160802.
5. Blass, A .; Гуревич Ю. (1986). «Кванторы Хенкина и полные задачи» (PDF). Анналы чистой и прикладной логики. 32: 1–16. Дои:10.1016/0168-0072(86)90040-0. со ссылкой на W. Walkoe, Finite частично-упорядоченное количественное определение, Journal of Symbolic Logic 35 (1970) 535–555. JSTOR  2271440
6. Хинтикка Дж. (1973). «Квантификаторы против теории количественной оценки». Диалектика. 27 (3–4): 329–358. Дои:10.1111 / j.1746-8361.1973.tb00624.x.
7. Gierasimczuk, N .; Шиманик, Дж. (2009). «Количественная оценка ветвления против двусторонней количественной оценки» (PDF). Журнал семантики. 26 (4): 367. Дои:10.1093 / jos / ffp008.
8. Шер, Г. (1990). «Способы разветвления квантификаторов» (PDF). Лингвистика и философия. 13 (4): 393–422. Дои:10.1007 / BF00630749.
9. Барвайз, Дж. (1979). «О кванторах ветвления на английском языке». Журнал философской логики. 8: 47–80. Дои:10.1007 / BF00258419.
10. Рука, Майкл (1998). «Журнал символической логики». Журнал символической логики. 63 (4): 1611–1614. Дои:10.2307/2586678. JSTOR  2586678.

внешняя ссылка

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