수량사 분기식

논리에서 분기 quantifier,[1]또한 Henkin quantifier, 플레이어와 한정되어 부분적으로 순서 또는 심지어 비선형 quantifier 기호, 부분 ordering[2]요구했다.

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

Q∈{∀,∃}에 quantifiers 중.일반화된 quantifier의 특별한 경우이다.고전 논리에서, 기호 접두사 선형적으로 주문한 변수 ym 기호 Qm에 의해 바인딩 되는 값이 변수의 값에 따라 결정되게 되어 있다.

y1,..., ym−1

quantifiers에 의해 바인딩 되

Qy1,..., Qym−1

Qm 선행.(유한한)부분적으로 순서화된 양화와 논리에서 이번 사건 일반에 있지 않다.null

분기 수량화 먼저 레온 Henkin의 1959년 회의 종이에 등장했다.[3]부분적으로 순서화된 수량화 시스템 힘에 일차 논리와 2차 논리의 중간에 있다.그들은 Hintikka의 그리고 가브리엘 Sandu의independence-friendly 논리를 위한 기초로 사용되고 있다.null

정의 및 속성

가장 간단한 Henkin QH{\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}\varphi(x_{1},x_{2},y_{1},y_{2})y_{2}\end{pmatrix}.}$

그것은(사실 Henkin 접두사를 사용하여 모든 공식뿐 아니라 가장 단순한 것)의 2차 Skolemization에, 즉 해당합니다

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

그것은 또한 충분히}}(즉"이 무한히 많다")로 정의한 기호 Q≥ N{\displaystyle Q_{\geq \mathbb{N}을 정의할 강력하다.

${\displaystyle(Q_{\geq \mathb {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))].}$

Several things follow from this, including the nonaxiomatizability of first-order logic with ${\displaystyle Q_{H}}$ (first observed by Ehrenfeucht), and its equivalence to the ${\displaystyle \Sigma _{1}^{1}}$-fragment of second-order logic (existential second-order logic)—the latter result published independently i1970년 ^[5]Herbert Enderton과^[4] W. W. Walkoe.null

다음의 정량자도 $Q{\displaystyle {}_{}}$ ${\displaystyle H_{}}$ ${\$에 의해 정의할 수 있다$.$^[2]

• 레셔 : "φ의 수가 ψ의 수보다 작거나 같음"

${\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})]}$

• 헤르틱 : " "s는 ψ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)}}$

• 장="φ의 수는 모델의 영역과 같다"고 했다.

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

Henkin 계량기 ${\displaystyle Q_{}}$ $H{\displaystyle {}_{}}$ ${\$$H}}$은(는) 타입(4) 린드스트룀 계량기로 표현될$$ 수 있다.^[2]null

자연 언어와의 관계

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}))].}$

1차 로직 등가물이 없는 것으로 알려져 있다.^[7]null

가지치기 사상은 반드시 고전적인 정량자를 나뭇잎으로 사용하는 것에만 국한되는 것은 아니다.1979년 paper,[9]에서 존 Barwise, 예를 들어:"대부분의 마을 사람들과 대부분의 townsmen은 서로 미워하Hintikka의 문장들은 내부 quantifiers 그들 스스로 일반 quantifiers 변화(로 위에 가끔이라고 불린다)을 제안했다."[7]그 Σ 11{\displaystyle \Sigma_{1}^{1}}부정에 따라서 닫히지 않다 산, Barwise 알.따라서 자연어 문장이 실제로 분기 정량자를 포함하는지, 즉 자연어 부정이 집합 변수에 대한 보편 정량화를 포함하는지 여부를 시험하기 위한 실제 시험을 제안했다(^[10]${\displaystyle {EX1\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 1 ${\$}:{1$}).$null

힌티크카의 제안은 많은 논리학자들의 회의론에 부딪혔다. 아래 문장처럼 일부 1차 순서 문장이 자연어 힌티크카 문장을 충분히 잘 포착할 수 있는 것처럼 보이기 때문이다.null

${\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})\웨지 T(x_{1},y_{1})\우측화살표(R(x_{1},y_{2})\웨지 R(x_{1},y_{2})\웨지 H(y_{2},y_},y_{1})}$

비록 많은 순전히 이론적인 논쟁이 뒤따랐지만, 2009년에 이르러서야 논리로 훈련된 학생들을 대상으로 한 일부 경험적 테스트에서 힌티크카 문장에서 파생된 여러 자연어 구조에 분기-정량형 문장보다는 "양방향" 1차 문장과 일치하는 모델을 배정할 가능성이 더 높다는 것을 알게 되었다.예를 들어, 학생들은 사각형과 원을 정점으로 한 간접적인 초당적 그래프를 보여주었고, "3개 이상의 원과 3개 이상의 사각형이 선으로 연결되어 있다"와 같은 문장이 도표를 올바르게 묘사하고 있는지 말하도록 요청받았다.^[7]null

참고 항목

• 게임 의미론
• 의존 논리
• 독립성 친화 논리(IF 논리)
• 모스토스키 정량기
• 린드스트룀 정량기
• 비우선순위화성

참조

외부 링크

• PlanetMath의 게임 이론적 정량화기.