헤이팅 산술

수학적 논리학에서 헤잉 산술 ${\displaystyle \mathsf{HA}}$ ${\$는 직관주의 철학에 따라 산술을 공리화한 것입니다.^[1]이 이름은 처음 제안한 아렌트 헤잉의 이름을 따서 지어졌습니다.

공리화

헤잉 산술은 추론을 위해$$ 직관적 술어 미적분학 ${\displaystyle \mathsf{IQC}}$ ${\displaystyle$ ${\mathsf {PA}}$를 사용한다는 점을$$제외하고는 페아노 산술 ${\displaystyle \mathsf{PA}}$ ${\$ {\$mathsf {IQC}}$의 1차 이론과 동일하게 특성화할 수 있습니다.특히, 이는 이중 네거티브 제거 원리는 물론, 제외된 중간 ${\displaystyle \mathrm{PEM}}$ ${\$의 원리가$$성립하지 않음을 의미합니다.${\displaystyle \mathrm{PEM}}$ ${\$이라고 하는 것은$$ 제외된 중간 문이 모든 명제에 대해 자동으로 증명할 수 없음을 의미합니다. 실제로 이러한 문은 ${\displaystyle \mathsf{HA}}$ ${\$에서 여전히 증명할 수 있으며 이러한$$ 연결의 부정은 일관되지 않습니다.${\$${\displaystyle \mathsf{displaystyle}}$ {\mathsf {$PA}}}$은(는$$) $모든{\displaystyle \mathsf{}}$ ${\displaystyle \mathsf{HA}}$ ${\$ - 정리도 $PA{\displaystyle \mathsf{}}$ ${\$ - 정리입니다$.$

헤이팅 산술은 Peano 산술의 공리로 구성되며 의도된 모델은 $자연수{\displaystyle \mathbb{}}$ N$${\$displaystyle {\mathbb {N}}$의 집합입니다$.$서명은 0 "${\displaystyle \mathrm{}}$ ${\displaystyle 0$과 계승자 "${\displaystyle }$ ${\displaystyle$ S$}"$을 포함하며, 이론은 덧셈과 곱셈을 특징으로 합니다.이는 논리에 영향을 미칩니다.$1{\displaystyle :}$= S ${\displaystyle 0}$ ${\displaystyle$1:=$S0}$을$($를$)$ $사용$하면 {\$displaystyle$\bot}을(를) ${\displaystyle 0}$= 1 {\$displaystyle$0→1}로 정의할 수 있고, 모든 $명제$ P$${\$displaystyle$$\neg$ P$}$이($가$) ${\displaystyle P}$ =${\displaystyle \mathrm{}}$⊥$${\$displaystyle$ $P$$\to \bot}$이(가) 되도록 하는 메타 정리입니다$.$⊥${\displaystyle$ \$bot$}의$$부정은 형식 $P$ → ${\displaystyle P}$ ${\displaystyle P\to P}$이므로 사소한 명제입니다.

숫자의 경우$$¬${\displaystyle (s}$ = ${\displaystyle t)}$ ${\displaystyle$$s\neq$}에 대해 ≠ ${\displaystyle t}$ ${\$displaystyle s\$neq$$}$을(를$)$ 씁니다$.$고정수 $t$ ${\displaystyle t}$의 경우$$반사율에 의해 ${\displaystyle \mathrm{등호}}$t =$$t {\$displaystyle$ t=$t$}가 $참$이고 명제$$P {\$displaystyle$ P$}$가 (${\displaystyle t}$ = ${\displaystyle t})$ →$$P {\$displaystyle$ (t = t)\$to$ P$}$와 같습니다$.$ ${\displaystyle \mathrm{그러면}}$ $P$ ∨ Q ${\displaystyle P\lor$ Q$}$가 ∃ ${\displaystyle n}$으로 정의될 수 있음을 알 수 있습니다${\displaystyle .}$ ${\displaystyle (n}$ → ${\displaystyle 0}$ → ${\displaystyle P}$)${\displaystyle }$∧ (${\displaystyle n}$ ≠ $0$ = Q )${\displaystyle n.(n$ = $0\to$ P$)\l$$그리고 (n\neq 0\to Q$ 이러한 형식적인 접속 제거는 정량자가 없는 원시 재귀 산술 ${\displaystyle \mathsf{PR}}$ ${\${PRA$}}$에서는 불가능했습니다$.$ ${\displaystyle \mathsf{이론}}$은 임의의 원시 재귀 함수에 대한 함수 기호로 확장될 수 있으므로 PR ${\${PRA$}}$도 이 이론의 일부입니다.총 함수 $f$ ${\displaystyle f}$의 경우$$$f$ (${\displaystyle n}$ )${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle f(n$) =$$0 형식의 술어를 종종 고려합니다$.$

정리

이중부정

임의의 직관 이론에서 폭발이 유효하므로, ¬ ¬ ${\displaystyle P}$ ${\displaystyle \neg \neg$ P$}$가 일부 $P$ ${\displaystyle P}$에 대한 정리라면$,$ 정의상 이론이 일치하지 않는 ${\displaystyle \mathrm{경우}}$에만 ¬ P ${\displaystyle \neg$ P$}$가 증명 가능합니다.실제로 헤잉 산술에서 이중 부정은 ¬ ${\displaystyle P}$ → ${\displaystyle 0}$ = ${\displaystyle 1}$ ${\displaystyle \neg P\to$0 = $1}$을(를) 명시적으로 표현합니다$.$ $술어$ ${\displaystyle Q}$$${\$displaystyle Q}$에 대해$$¬ ¬ ∃ ${\displaystyle n.}$ Q (${\displaystyle n}$) ${\displaystyle \neg \neg$\exists $n$의 형식 정리입니다$.$$Q(n)}$은(는) $일부{\displaystyle }$ t {\$displaystyle$ t}에$$대해 Q${\displaystyle (t)}$ ${\$$displaystyle Q(t)}$이(가) 검증될 수$$ 있음을 배제하는 것이 일관되지 않음을 나타냅니다$$$.$ 건설적으로, 이는 ${\displaystyle$ t$}$에서 $존재{\displaystyle }$ 주장보다 약합니다$.$ 메타 이론적 논의의 큰 부분은 고전적으로 증명 가능한 존재 주장에 관한 것입니다.

${\displaystyle 이중}$ 네거티브 ¬ ¬ P ${\displaystyle \neg \neg P}$는 α →$$¬ P )${\displaystyle }$→ (${\displaystyle \alpha }$→ ${\displaystyle 0}$ = 1${\displaystyle }$) ${\displaystyle (\alpha \to \neg$P)\$to (\alpha \to$ 0 = 1)}을$($를) 수반합니다$.$ 따라서 ${\displaystyle 형태}$ ¬ ¬ P ${\displaystyle \neg \neg P}$의 정리는 $항상$ α ${\displaystyle \alpha}$ 문을 결정적으로 거부(또한 양의)할 수 있는 새로운 수단을 제공합니다$.$

고전적으로 동등한 진술의 증명

${\displaystyle \mathsf{HA}}$ ⊢ ${\displaystyle \mathrm{\alpha }}$ → ¬ ¬ α ${\displaystyle {\mathsf {HA}}\vdash \alpha \to \neg \neg \alpha}$의 의미는 고전적으로 되돌릴 수 있으며, 이를 $통해$ ${\displaystyle \mathsf{HA}}$⊢${\displaystyle (}$∃ ${\displaystyle n}$. ¬ ψ${\displaystyle }$( ${\displaystyle n}$)${\displaystyle }$→ ¬ ∀ n .${\displaystyle }$ψ (${\displaystyle }$n${\displaystyle }$) ${\displaystyle {\mathsf {HA}}\vdash {\big (}\$exists n ).$\neg \psi (n){\big )}\to \neg$\for $all n.\psi (n$ 여기서 모든 수에 대한 유효성을 가정할 때 수치 반례의 존재 대 부조리한 결론의 차이입니다.이중 부정을 삽입하면 ${\displaystyle \mathsf{PA}}$ ${\$ -theorms가$$ ${\displaystyle \mathsf{HA}}$ ${\$ -theorms로$$ 바뀝니다.더 정확하게 말하면, ${\displaystyle \mathsf{PA}}$ ${\displaystyle {\mathsf {PA}}$에서 증명할 수 있는 모든 공식에 대해$,$ 그 공식의 고전적으로 동등한 Gödel-Gentzen 음의 번역은 ${\displaystyle \mathsf{HA}}${\$displaystyle${\$mathsf {HA}}$에서 이미 증명할 수 있습니다$.$ 하나의 공식에서, 번역 절차는 ($$∃ ${\displaystyle n.}$ ${\displaystyle Q}$( ${\displaystyle n{}^{}}$) ${\displaystyle N^{}}$ ${\displaystyle${\$big (})\존재하는 n$의 재작성을 포함합니다$.$$Q(n){\big )}^{N}$에서 $¬ ∀$ ${\displaystyle n}$.${\displaystyle }$$¬$ ${\displaystyle {QN}^{}n).}$ ${\displaystyle \neg \forall n.$$\neg Q^{N}(n).$$}$결과는$$ 모든 Peano 산술 정리가 구성적인 증명과 고전적인 논리적 개작으로 구성된 증명을 가지고 있음을 의미합니다.대략적으로, 최종 단계는 이중 네거티브 제거의 적용에 달합니다.

특히, 결정할 수 없는 원자 명제가 존재하는 경우, 존재하는 정량화나 접속을 전혀 포함하지 않는 명제 ψ ${\displaystyle \psi }$에 $대해$ ${\displaystyle \mathsf{PA}}$ ⊢ ψ ⟺ ${\displaystyle \mathsf{HA}}$ ⊢ ψ$${\$displaystyle {\mathsf {PA}}\vdash \psi \iff${\$mathsf {HA}\vdash \psi$}가 있습니다$.$

유효한 원칙 및 규칙

최소 논리는 부정 공식, ¬ ¬ ${\displaystyle \mathrm{(}}$¬ ${\displaystyle \alpha }$)${\displaystyle }$↔ ${\displaystyle (}$¬ ${\displaystyle \alpha )}$ ${\displaystyle \neg \neg (\neg \alpha )\left$ right arrow $(\neg \alpha )}$에 대해 이중 부정 제거를 증명합니다$.$ 보다 일반적으로, 헤잉 산술은 해롭 공식에 대한 이 고전적인 동등성을 증명합니다.

그리고 σ ${\displaystyle {}_{}^{}}$ ${\displaystyle \Sigma _{1}^{0}}$ - 결과도 잘 동작함: 산술 계층 구조의 가장 낮은 수준에서 마코프의 규칙은 허용 가능한 추론 규칙, 즉 $n$이 ${\displaystyle n}$인 φ ${\displaystyle \varphi}$의 경우,

${\displaystyle {\mathsf {HA}}\vdash \neg \neg \exists m 입니다.\varphi (n,m)\iff {\mathsf {HA}}\vdash \exists m 입니다.\varphi(n,m)}$

정량자가 없는 술어에 대해 말하는 대신, 원시 재귀 술어 또는 크리네의 T 술어에 대해 이를 동등하게 공식화할 수 있으며, $이$를 ${\displaystyle {MR}_{\mathrm{}}}$ ${\displaystyle {\mathrm{QF}}_{}}$ ${\displaystyle {MR}}_{\mathrm {QF}},$resp라고 합니다.${\displaystyle {\mathrm{MR}}_{}}$ ${\displaystyle {\mathrm{PR}}_{}}$ ${\displaystyle {\mathrm {MR}$ _${\mathrm {PR}}}$ 및 ${\displaystyle {}_{}}$ 0 ${\displaystyle {\mathrm {MR}$${\displaystyle {\mathrm{\_}}_{}}$${0}}.$$\phi$ ${\displaystyle$ ${\mathrm {MR}}_{\$$mathrm$${Dec$$}}$의 트랙터빌리티 측면이 구문 조건을 기반으로 하는 것이 아니라 왼쪽에도 필요한 경우에도 $허용$됩니다$.$${\displaystyle \vdash \forall m.$$\backslash$$varphi (n,m)\lor \neg \varphi (n,m)}.$

구문 형식에 기초하여 명제를 분류할 때, 단지 고전적인 유효한 동치에 기초하여 더 낮은 복잡도를 잘못 할당해서는 안 됩니다.

중간제외

직관적 논리에 대한 다른 이론과 마찬가지로, ${\displaystyle \mathrm{PEM}}$ ${\$의 다양한 인스턴스가 이 구성 산술에서 증명될 수 있습니다$$.$분리$ 도입에$$의해 $명제$ P {\$displaystyle$$$P} ${\displaystyle \mathrm{또는}}$¬$$P {\displaystyle \$neg P}$ 중 하나가 $증명$될 ${\displaystyle \mathrm{때}}$마다 P$$∨ ¬ P {\$displaystyle P\lor$ \$neg$ P$}$도 증명됩니다.예를 들어, $0$ = ${\displaystyle 0}$ ${\displaystyle$0=$0}$ 및 ∀ ${\displaystyle n.\mathrm{sn}}$ ≠ 0 ${\displaystyle \forall n.$공리에서 $Sn\neq 0},$ 술어 $n$ $=$ 0 ${\displaystyle$ n $=$$0$}에 대해 제외 중간 유도의 전제를 검증할 수 있습니다$.$ 그런 다음 하나는 0에 대한 동일성이 결정될 수 있다고 말합니다.실제로 ${\displaystyle \mathsf{HA}}$ ${\displaystyle {\mathsf {HA}}$은(는) 동일함을 증명합니다$$ " = ${\displaystyle$ =$\}"$ 모든 숫자, 즉 ∀ ${\displaystyle n.}$ ∀ ${\displaystyle m.}$ ${\displaystyle (n}$ = ${\displaystyle m}$ ∨ ${\displaystyle n}$ ≠ ${\displaystyle m)}$ ${\displaystyle \forall$n.$\forall m.(n=m\lor$ n$\neq$ m$)\}.$ 헤잉 산술의 유일한 술어 기호는 같으므로, n${\displaystyle ,}$ ${\displaystyle \dots ,}$ ${\displaystyle m}$ ${\displaystyle n,\n$$dots$$,m}$이$($가$)$ 자유 변수이면, 이론은 규칙 아래에서 닫힙니다.

${\displaystyle {\mathsf {HA}}\vdash \fall n.\cdots \fall m.\,\phi (n,\dots,m)\lor \neg \phi (n,\dots,m)}$

최소 논리에 대한 이론은 모든 명제에 대한${\displaystyle }$¬ ¬(${\displaystyle P}$ ∨ ¬ ${\displaystyle \mathrm{P})}$ ${\displaystyle \neg \neg (P\lor \neg$ P$))}$를 증명합니다.따라서 이론이 일치한다면, 배제된 중간 진술의 부정을 입증하는 것은 결코 아닙니다.

실제로, ${\displaystyle \mathsf{HA}}$ ${\$와 같은 다소 보수적인 구성 프레임워크에서$,$ 어떤 유형의 문이 알고리즘적으로 결정 가능한지 이해될 때, 제외된 중간 분리의 증명할 수 없는 결과는 $P{\displaystyle }$ ${\displaystyle P}$의 알고리즘적 결정 불가능성을 표현합니다$.$

보수성

단순한 진술을 위해, 이론은 단지 그러한 고전적으로 유효한 이진 이분법 ϕ ${\displaystyle (n,}$…)${\displaystyle }$∨ ¬ ϕ ${\displaystyle (n,}$ ${\displaystyle \dots )}$ ${\displaystyle \phi (n,\dots)\lor \neg \phi (n,\dots)}$을(를) 검증하지 않습니다$.$프리드먼 변환을 사용하여 ${\displaystyle \mathsf{PA}}$ ${\displaystyle {\mathsf {PA}}$의$$π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{2}^{0}}$ - 정리는 모두 ${\displaystyle \mathsf{HA}}$ ${\displaystyle {\mathsf {HA}}$로 증명됩니다$.$ : $n개$의 ${\displaystyle n}$과(와$)$ 한정자가 없는 φ {\$displaystyle \varphi}$의 경우$,$

${\displaystyle {\mathsf {PA}}\vdash \exists m입니다.\varphi (n,m)\iff {\mathsf {HA}}\vdash \exists m 입니다.\varphi(n,m)}$

이 결과는 물론$$명시적인 ${\displaystyle \mathrm{보편적}}$폐쇄$$∀ n {\$displaystyle$ \$forall$ n$}$으로도 표현될 수 있습니다$.$ 대략적으로 고전적으로 증명 가능한 계산 가능한 관계에 대한 간단한 설명은 이미 건설적으로 증명할 수 있습니다.비록 문제를 중단시킬 때, 정량자가 없는 명제뿐만 아니라 π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{1}^{0}}$ - 명제는 중요한 역할을 하며, 앞으로도 논의될 것처럼 이러한 명제들은 고전적으로 독립적일 수 있습니다.마찬가지로 이미 고유한 존재$$∃${\displaystyle !n.}$ ${\displaystyle Q}$ (${\displaystyle }$n )${\displaystyle \exists!n입니다.$무한 도메인의 $Q(n)},$ 즉 $∃$ ${\displaystyle n.}$ $∀$ w${\displaystyle .}$( ${\displaystyle n}$ $=$ ${\displaystyle w}$ $↔$ ${\displaystyle Q}$ (${\displaystyle }$w${\displaystyle }$)${\displaystyle \$$exists$$n.$$아무쪼록.$${\big (}n=w\$왼쪽 오른쪽 $화살표 Q(w){\big$ $)\}\},$ 형식적으로 특별히 간단하지 않습니다.

따라서 ${\displaystyle \mathsf{PA}}$ ${\displaystyle {\mathsf {PA}}}$는 π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{2}^{0}}$ - ${\displaystyle \mathsf{HA}}$ ${\displaystyle {\mathsf {HA}}$에 대해 보수적입니다$.$ 대조적으로 로빈슨 $산술$ Q ${\displaystyle {\mathsf {Q}}$의 고전 이론이 모든 σ ${\displaystyle {}_{}^{}}$ ${\displaystyle \Sigma _{1}^{0}$- ${\displaystyle \mathsf{PA}}$ ${\displaystyle {\mathsf {PA}}$ - 정리,일부 단순 π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{1}^{0}}$- ${\displaystyle \mathsf{PA}}$ ${\displaystyle {\mathsf {PA}}$ - 정리는 독립적입니다.또한 귀납법은 프리드먼의 결과에 중요한 역할을 합니다.예를 들어, 순서에 대한 공리와 선택적으로 결정 가능한 동등성으로 $Q$ ${\displaystyle {\mathsf {Q}}$를 강화하여 얻은 더 효과적인 이론은 직관적인 상대보다 π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{2}^{0}}$ -문을 더 많이 증명합니다.

여기서의 논의는 결코 철저하지 않습니다.구성 이론에 의해 고전 정리가 이미 포함되어 있을 때에 대한 다양한 결과가 있습니다.또한 어떤 논리를 사용하여 금속 논리적 결과를 얻었는지도 관련이 있을 수 있습니다.예를 들어, 실현 가능성에 대한 많은 결과는 실제로 건설적인 금속 논리에서 얻어졌습니다.그러나 구체적인 맥락이 주어지지 않을 때, 명시된 결과는 고전적인 것으로 가정해야 합니다.

증명할수없는문

독립성 결과는 이론에서 증명할 수 없는 명제와 관련이 있습니다.고전 이론이 일관되고 구성 상대가 정리 $P{\displaystyle }$ ${\displaystyle P}$ 중 하나를 증명하지 않으면$$$P{\displaystyle }$ ${\displaystyle P}$는 후자와 독립적입니다$$.몇몇 독립적인 명제들이 주어지면, 그것들로부터 더 많은 것을, 특히 건설적인 틀에서, 정의하는 것은 쉽습니다.

하이팅 산술의 ${\displaystyle \mathrm{dp}}$ ${\$모든 명제 $\alpha {\displaystyle }$ ${\displaystyle \alpha}$ 및$$ $\beta {\displaystyle }$ ${\displaystyle \beta$^[2]에 대해,

${\displaystyle {\mathsf {HA}}\vdash \alpha \lor \beta \iff {\mathsf {HA}}\vdash \alpha {\text{ or }}{\mathsf {HA}}\vdash \beta }$

실제로, 이것과 그것의 수치 일반화는 $또한{\displaystyle \mathsf{}}$ 건설적인 2차 산술 및 ${\displaystyle \mathsf{CZF}}${\$displaystyle {\mathsf${CZF$}},$ ${\displaystyle \mathsf{IZF}}${\$displaystyle {\mathsf {IZF}}$와 같은 공통 집합 이론에 의해 나타납니다$.$ 이것은 건설 이론의 비공식적인 개념에 대한 일반적인 데시데라툼입니다.

이제 ${\displaystyle \mathrm{DP}}$ ${\displaystyle {\mathrm {DP}}}$인 이론에서$,$ $명제$ P ${\displaystyle P}$가 독립적이라면, 고전적으로 사소한 $P$ ∨ ¬ ${\displaystyle \mathrm{P}}$ ${\displaystyle P\lor \neg$ P$}$는 또 다른 독립적인 명제이며, 그 반대도 마찬가지입니다.증명할 수 없는 인스턴스가 하나 이상 있는 경우 스키마가 유효하지 않습니다. 이는 ${\displaystyle \mathrm{PEM}}$ ${\$이(가) 실패하게 되는$$ 방법입니다.${\displaystyle \mathsf{PA}}$ ${\$의 경우와 마찬가지로, 어느 하나의 접속부를 검증하지 않고 공리적으로 제외된 중간 문을 채택함으로써$$ ${\displaystyle \mathrm{DP}}$ ${\$를 깰 수 있습니다$.$

더 많은 것을 말할 수 있습니다.$P$ ${\displaystyle P}$이(가) 고전적으로도 독립적이면, 부정 ¬ ${\displaystyle P}$ ${\displaystyle \neg P}$도 독립적입니다. 이것은 ¬ ¬ P ${\displaystyle \neg \neg P}$이($)$ P {\$displaystyle P}$와 동일한지 여부를 유지합니다$.$ 그러면, 구성적으로, 약한 제외 ${\displaystyle \mathrm{중간}}$ W ${\displaystyle \mathrm{PE}}$ ${\displaystyle \mathrm{M}}${\$displaystyle {\mathrm {WPEM}}$이(가) 성립하지 않습니다.¬${\displaystyle \alpha }$ ∨ ¬ ¬ α ${\displaystyle$ \$neg$ \$alpha$ \$lor \neg$ \$neg$ \$alpha }$가 모든 명제에 대해 갖는 원리는 유효하지 않습니다.이러한 $P$ ${\displaystyle P}$이(${\displaystyle {가}_{}^{}}$)$$σ $10$ {\displaystyle \$Sigma _{$1}^{$0}}$인 경우$,$ 연결을 증명할 수 없으므로 π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{1}^{0}}$ -$$${\displaystyle \mathrm{PEM}}$ ${\displaystyle {\mathrm {PEM}}},$ 또는$$${\displaystyle \mathrm{원시}}$ 재귀 함수의 WL $PO$ {\$displaystyle {\mathrm$ {WLPO$}}$ 인스턴스에 해당하는 것입니다$.$

고전적으로 독립적인 명제

괴델의 불완전성 정리에 대한 지식은 ${\displaystyle \mathsf{PA}}$ ${\$ - 증명$$ 가능하지만 ${\displaystyle \mathsf{HA}}$ ${\$ - 증명$$ 가능하지 않은 문장 유형을 이해하는 데 도움이 됩니다.

힐베르트의 열 번째 문제의 해결은 일부 구체적인 다항식 $f{\displaystyle }$ ${\displaystyle f}$와 그에 상응하는 다항식을 제공하여 후자가 해결책을 가지고 있다는 주장은 알고리즘적으로 결정할 수 없습니다.그 명제는 다음과 같이 표현될 수 있습니다.

${\displaystyle \exists w_{1}입니다.\cdots \exists w_{n}.f(w_{1},\dots,w_{n})=0}$

이러한 영가치 존재 주장은 보다 구체적으로 다음과 같이 해석됩니다.${\displaystyle \mathsf{PA}}$ ${\$ 또는$$ ${\displaystyle \mathsf{ZFC}}$ ${\$}와 같은 이론$FC}}}$은(는) 이러한 명제가 이론 자체의 불일치에 대한 산술화된 주장과 동일하다는 것을 증명합니다$$.따라서 그러한 명제는 심지어 강력한 고전 집합 이론에 대해서도 적을 수 있습니다.

일관되고 건전한 산술 이론에서, ${\displaystyle {\mathrm {I} _{f}}$가 독립적인 σ ${\displaystyle {}_{}^{}}$ ${\displaystyle \Sigma _{1}^{0}}$ - 명제인 $경우$, 그러한 존재 주장.그러면 ${\displaystyle {}_{}}$ := ¬ ${\displaystyle {\mathrm {C} _{f$}}:=\$neg {\mathrm {I} _{f}}}$이$($가) 한정자를 통해 음수를 밀어넣어 독립적인 Goldbach형 또는 π$$ {\$displaystyle$ \$Pi _{$1}^{$0}}$ - 명제로 ${\displaystyle 표시}$됩니다$.$명시적으로 말하면, ${\displaystyle {}_{}}$ 네거티브 ¬ ¬ ${\displaystyle \neg \neg {I} _{f}}($또는 ¬ ${\displaystyle {}_{}}${\$displaystyle \neg {\mathrm {C} _{f}})$도 독립적입니다$.$그리고 어떤 경우든 삼중 부정은 이미 직관적으로 단일 부정과 동등합니다.

PA가 DP를 위반함

다음은 이러한 독립적인 진술에 포함된 의미를 설명합니다.어떤 이론의 모든 증명의 열거에 지수가 주어지면, 그것이 어떤 명제의 증명인지 검사할 수 있습니다.${\$은(는) 다음 절차를 올바르게 표현할 수 있다는 점에서 적합합니다$$.원시 재귀 술어 $F{\displaystyle }$( w${\displaystyle }$) := ${\displaystyle \mathrm{Prf}}$ ( ${\displaystyle w,}$⌜ ${\displaystyle 0}$ = ${\displaystyle 1}$ ⌝ )${\displaystyle \mathrm {F}(w)$가 있습니다:증명이 부조리 $명제$ ${\displaystyle 0}$ $=$ 1$${\$displaystyle 0$$=1$$\}$ 중 하나임을 나타내는 $=\mathrm {Prf}$ ($w,\ulcorner$ 0$=1\urcorner$)}입니다. 이것은 다항식의 반환 값이 0에 대한 위의 산술 술어에 대한 것입니다.${\displaystyle \mathsf{PA}}$ ${\displaystyle {\mathsf {PA}}$이(가) 일치하면 ${\displaystyle {\mathrm {w}}}$의 모든 개별 $인덱스$에 대해 ¬ ${\displaystyle F(w}$ ${\displaystyle \underset{}{}}$) ${\displaystyle \neg \mathrm {F}({\mathrm {w}})$를 증명한다고 논리적으로 추론할 수 있습니다$.$

효과적으로 공리화된 이론에서는 각 증명에 대한 검사를 연속적으로 수행할 수 있습니다.만일 이론이 정말로 일치한다면, 부조리의 증거는 존재하지 않는데, 그것은 언급된 "부조리 탐색"이 결코 멈추지 않을 것이라는 진술에 해당합니다.형식적으로 이론에서, 전자는 명제 ¬ ∃ ${\displaystyle w.F}$ (${\displaystyle w)}$ ${\displaystyle \neg \exists w.\mathrm {F}(w)$로 표현되며$,$ 산술화된 불일치 주장을 부정합니다.동치 π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{1}^{0}}$ - 명제 ∀ ${\displaystyle w}$.${\displaystyle }$¬ ${\displaystyle F}$ ${\displaystyle (w)}$ ${\displaystyle \for$ all $w.$$\neg \mathrm {F}(w)}$은(는) 모든 증명이 부조리의 증거가 아니라는 것을 밝힘으로써 검색의 절대 중단을 공식화합니다$$.그리고 실제로 확률을 정확하게 나타내는 오메가 일관성 이론에서는 부조리 탐색이 중단(명시적 비일관성 유도 불가)으로 결론을 내릴 수 있다는 증거가 없으며, 괴델이 보여주듯이 부조리 탐색이 절대 중단되지 않는다는 증거가 있을 수도 없습니다( 일관성 유도 불가).재구성하면, 부조리 검색이 절대 중단되지 않는다는 증거는 없으며(일치성은 도출할 수 없음), 부조리 검색이 절대 중단되지 않는다는 증거도 없습니다(일치성은 거부할 수 없음).반복하자면, 이 두 연결 중 어느 것도 ${\displaystyle \mathsf{PA}}$ ${\$ -provable이고$$, 그 연결은 세 $가지{\displaystyle \mathsf{}}$ ${\displaystyle \mathsf{PA}}$ ${\$ -provable입니다$$.실제로 ${\displaystyle \mathsf{PA}}$ ${\$이(가) 일치하면 ${\displaystyle \mathrm{DP}}$ ${\$을(를$)$ 위반합니다.

σ $10$ ${\displaystyle$ \$Sigma$ _${1}^{0}}$ -0 =$$의 증명의 존재를 표현하는 명제 ${\displaystyle$ 0=1$}은($는) 논리적으로 긍정적인 문장입니다.그럼에도 불구하고, ${\displaystyle {\mathsf{PA}}_{}}$$${\$displaystyle \neg {\mathrm {Con}}_{\mathsf {PA}}}$에서 $역사적$으로 ¬ $C$로 ${\displaystyle {}_{}^{}}$된 반면$,$ 부정은$$PA {\$displaystyle \Pi$ _{1}^{$0}$ ${\displaystyle {-Con}_{}}$ {\$displaystyle {\mathrm {Con}}_${\mathsf {$PA}}$로 표시된 명제입니다$.$ 건설적인 맥락에서, 부정 부호의 이러한 사용은 오해의 소지가 있는 명명법일 수 있습니다.

프리드먼은 또 다른 흥미로운 증명할 수 없는 진술을 세웠습니다. 즉, 일관되고 적절한 이론은 결코 산술화된 연결 특성을 증명하지 않는다는 것입니다.

증명할 수 없는 고전적 원리

이미 논리적으로 최소화된 논리는 모든 비contrad성 주장을 증명하며, 특히${\displaystyle }$¬ (${\displaystyle {}_{}}$ ∧ ¬${\displaystyle {}_{}}$ 경우${\displaystyle {}_{}}$ ${\displaystyle \neg ({\mathrm {I} _{f})\land \neg {\mathrm {I} _{f})}$ 및 ¬ ${\displaystyle ({}_{}}$ ∧ ¬ ${\displaystyle {}_{}}$) ${\displaystyle \neg ({\mathrm {C} _{f}) {\mathrm {C} _{f}}$를 증명합니다$.$ (${\displaystyle {}_{}}$ ∧ ¬ ${\displaystyle {}_{}}$ )${\displaystyle {}_{}}$↔ ¬ (${\displaystyle {}_{}}$ F ∨ ¬ ${\displaystyle {}_{}}$) ${\displaystyle ({\mathrm {C}$ _${f$})$})\land \neg {\mathrm {C}$ _${$$f})\left$ right arrow $\neg ({\mathrm {I} _{f}},$ 정리 $¬$ ($Cf$ $∧ ¬$ $) {\displaystyle \neg$({\$mathrm$ {$C}$ _${f})\land \neg {\mathrm${C} _{f$}}$는 증명 가능한 이중 네거티브 배제 중간 분리(또는 존재 주장)로 읽을 수 있습니다.그러나 이와 관련된 성질이나 드 모르간의 법칙이 직관적으로 성립하지 않기 때문에 평원에서 제외된 중간 ${\displaystyle {}_{}}$ ∨ ¬ ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm {C} _{f}\neg {\mathrm {C} _{f}}$는 ${\displaystyle \mathsf{HA}}$ ${\displaystyle {\mathsf {HA}}$ - 증명할 수 없습니다.

${\displaystyle \mathrm{WPEM}}$ ${\$과 ${\displaystyle \mathrm{WLPO}}$ ${\$의 원칙을 설명했습니다$$.이제 ${\displaystyle \mathsf{PA}}$ ${\$에서$$최소수 원칙 ${\displaystyle \mathrm{LNP}}$ ${\$는 유도 원칙과 동일한 많은 문들 중 하나일 뿐입니다.아래 증명은 ${\displaystyle \mathrm{LNP}}$ ${\displaystyle {\mathrm {LNP}}}$이(가) ${\displaystyle \mathrm{PEM}}$ ${\displaystyle {\mathrm {PEM}}}$을(를) 의미하며$,$ 따라서 이 원리가 ${\displaystyle \mathsf{HA}}$ ${\displaystyle {\mathsf {HA}}$에서도 일반적으로 유효할 수 없는 이유를 보여줍니다$.$ 그러나, 모든 사소한 술어에 대해 이중 음의 최소 개수 존재를 허용하는 스키마는 ¬ ¬ ${\displaystyle \mathrm{LNP}}$ ${\displaystyy$}로 표시됩니다.$lee \neg \neg {\mathrm {LNP}}}$, 일반적으로 유효합니다.괴델의 증명에 비추어 볼 때, 이 세 가지 원리의 분해는 헤이팅 산술이 구성 논리의 확률 판독과 일치하는 것으로 이해될 수 있습니다.

원시 재귀 $술어$에 대한 마코프의 ${\displaystyle {\mathrm{원리}}_{}}$ ${\$ _${\mathrm {PR}}}$이$($가) ${\displaystyle \mathsf{이미}}$ HA {\$displaystyle {\mathsf {HA}}$에 대한 함의 스키마로 사용되지 않습니다$$$.$ 엄밀하게 더 강한 ${\displaystyle {\mathrm{MP}}_{}}$ ${\displaystyle {\mathrm{Dec}}_{}}$ ${\mathrm {MP} _{\mathrm {Dec}}}.$비록 해당 규칙의 형태이지만, 이들은 a입니다.언급한 바와 같이, 허용 가능한.마찬가지로, 이 이론은 부정된 술어에 대해 전제 $원칙$ ${\displaystyle \mathrm{IP}}${\$displaystyle {\mathrm {IP}}}$의 독립성을 증명하지 않지만, 모든 부정된 명제에 대한 규칙 하에서 닫힙니다. 즉, ¬ ${\displaystyle P}$ → ∃ ${\displaystyle n.}$ Q (${\displaystyle n}$) ${\displaystyle \neg P\to \$exists$n.$$Q$$n)}.$존재론적 진술이 단순한 단절로 대체되는 버전도 마찬가지입니다.

그리고$$(${\displaystyle \alpha }$ → ¬ ¬ ${\displaystyle \mathrm{\beta })}$ ↔ ¬ ¬ ${\displaystyle \mathrm{(}\alpha }$ → ${\displaystyle \beta )}$ ${\displaystyle (\alpha \to \neg \neg \$beta$)\left$ right arrow $\neg \neg$(\$alpha \to$\beta $)}$는 직관적으로 유지되지만 이중 네거티브 시프트 ${\displaystyle \mathrm{DNS}}$ ${\displaystyle {\mathrm${DNS$}}}$는 모든 숫자에 대한 보편적인 정량화를 가진 "¬ ¬${\displaystyle }${\$displaystyle \neg \neg$의 교환성 스키마가 아닙니다.이것은 Church의 논문에 대한 부분에서 논의된 바와 같이$,$ $일부$ M$${\$displaystyle$ M$}$에 대한$$¬ ${\displaystyle {}_{}}$ M${\displaystyle \neg {\mathrm {Dec}$ _{M}}의 일관성으로 설명되는 흥미로운 분석입니다.

최소수 원칙

자연계의 순서 관계를 이용하여 강력한 유도 원리는 다음과 같습니다.

${\displaystyle \for all n.{\Big(}{\big(})\모두에 대하여(k<n).\phi(k){\big )}\,\to \,\phi(n){\Big )}\,\to \,\모든 m에 대하여.\phi(m)}$

${\displaystyle \mathrm{클래스}}$ 표기법에서 집합론에서 익숙한 것처럼 산술 $문장$ Q (${\displaystyle }$n${\displaystyle }$) ${\displaystyle$ Q $(n)}$는 $n$ ∈ ${\displaystyle B}$ ${\displaystyle n\in B}$로 표현되며, $여기$서 B := ${\displaystyle \{m}$ ∈ ${\displaystyle N}$ ∣ ${\displaystyle Q}$( ${\displaystyle m}$)}${\displaystyle$ B :=\{$m\in {\mathbb {N}}\mid$Q ($m)\}.$ 주어진$$부정된 형태의 술어에 대해 ϕ (${\displaystyle }$n${\displaystyle }$) : = ¬${\displaystyle }$( n ∈ ${\displaystyle B}$) ${\displaystyle \phi$ ($n)$:$=\neg (n\in$ B$)\},$ 논리적 동치는

${\displaystyle \neg \exists (n\in B)입니다.\neg \exists (k\in B).k<n\,\,\왼쪽 오른쪽 화살표 \,\,B=\{\}$

통찰력은 $하위$ 클래스 B 중에서 ⊂ ${\displaystyle N}${\$displaystyle B\subset${\$mathbb${N$}}},$(아마도) 최소 구성원이 없는 것은 무인인 것, 즉 빈 클래스인 것과 같다는 것입니다.비어 있지 않은 모든 하위 클래스에 대해 n ${\displaystyle n}$보다 작은 멤버 ${\displaystyle k}$ ∈ B ${\displaystyle k\in B}$가 없을 때 멤버 ${\displaystyle n}$ ∈ B${\$displaystyle k\in $B}$이(가) 존재할 가능성을 일관되게 배제할 수 없음을 나타내는 정리에서 대조 결과를 취하면 다음과 같습니다$.$

${\displaystyle B\neq \{\}\,\to \,\neg \neg \exists (n\in B).\neg \exists (k\in B).k<n}$

이중 부정 제거가 항상 유효한 페아노 산술에서, 이것은 일반적인 공식에서 최소 수 원리를 증명합니다.고전적인 독서에서 비어 있지 않은 것은 최소한의 구성원이 거주하는 것과 동등합니다.

건설적으로, 다음 예가 보여주는 것처럼, 약화는 일반적으로 해제될 수 없습니다.일부 $명제{\displaystyle }$ P ${\displaystyle$ P$}($위와 같이$$ ${\displaystyle {}_{}}$ ${\displaystyle {C} _{f}})$의 경우 술어를 고려합니다.

${\displaystyle Q_{P}(n):=(n=0\land P)\lor n=1}$

이 ${\displaystyle {QP}_{}}$ ${\displaystyle Q_{P}}$은(는) $자연수$의 하위 클래스${\displaystyle {}_{}}$b ${\displaystyle P_{}}$에 해당합니다${\displaystyle .}$ = {${\displaystyle \mathrm{z}}$∣ {0${\displaystyle \}}$ ∪ ${\displaystyle P\}}$ ∈ {$}$ {\$displaystyle$b_$P}:$=$\{z\in \{0$\}\$mid P\}\$cup \{$1\}.$이 반에서 가장 적은 구성원이 무엇인지 물을 수 있습니다.이 클래스에 있는 것으로 증명되거나 가정된 모든 $수$는$$0 {\$displaystyle$ 0$}$ $또는$1 {\$displaystyle 1}$과$($와) 같습니다. 즉, $b$ ${\displaystyle P_{}}$⊆ {${\displaystyle 0,}$ ${\displaystyle 1\}}${\$displaystyle b_{P}\subseteq$\{$0,1$ 동일성의 판별 가능성과 분리 삼단논법을 사용하면 동등성 $P$ ↔ Q ${\displaystyle P_{}}$ (${\displaystyle {}_{}0}$) ${\displaystyle P\left$ rightarrow $Q_{P}(0$ 만약 기본 명제가 성립한다면$P{\displaystyle }$ ${\displaystyle P}$에서 술어는 독립적이고 이론에서 결정할 수 없습니다.$이제$ 1 = 1 ${\displaystyle$1=$1}$이므로$$명제 ${\displaystyle {QP}_{}}$(${\displaystyle 1)}$ ${\displaystyle Q_{P}(1)}$이(가) 사소한 참이므로 클래스에 거주합니다. $1$ ∈ ${\displaystyle b_{}}$ P ${\displaystyle 1\in b_{P$ 특히 이 클래스에 대한 최소 개수 존재는 거부할 수 없습니다.${\displaystyle {QP}_{}}$(${\displaystyle 1)}$ ${\displaystyle Q_{P}(1)}$와의 연결이 사소한$$ 경우, ${\displaystyle {QP}_{}}$ ${\$를 검증하는 최소 개수의 존재 주장 자체가 P$$ ${\displaystyle P}$에 대한 제외 중간 문으로 해석됩니다$.$ 이러한 개수의 값에 대한 지식은 사실상 P ${\displaystyle P}$의 보유 여부를 결정합니다.따라서 독립적인 $P{\displaystyle }$ ${\displaystyle P}$의 경우$$${\displaystyle {QP}_{}}$가 ${\$인 최소 수 원칙 인스턴스도 ${\displaystyle \mathsf{HA}}$ ${\mathsf {HA}}$과(와) 독립적입니다$.$

집합 이론 표기법에서 $P$ ${\displaystyle P}$는 $0$ ∈ ${\displaystyle b_{}}$ P ${\displaystyle 0\in b_{P}$와 같으며, $sob$ ${\displaystyle P_{}}$ = ${\displaystyle \{0,}$ ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle b_{$$P}=\{0,1\}}$이며$,$ 부정도 ${\displaystyle {bP}_{}}$ $=$ ${\displaystyle \{1\}}$ ${\displaystyle b_{$$P}=\{1$이는 이해하기 어려운 술어가 이해하기 어려운 부분집합을 정의할 수 있음을 보여줍니다.구성적 집합론에서도, 자연인의 등급에 대한 표준 순서는 결정할 수 있지만, 자연인들은 잘 정렬되어 있지 않습니다.그러나 실현 불가능한 존재 주장을 건설적으로 암시하지 않는 강력한 귀납 원리도 여전히 이용할 수 있습니다.

안티클래식 확장

계산 가능한 컨텍스트에서 술어 $M{\displaystyle }$ ${\displaystyle M}$의 경우$,$ 고전적으로 사소한 무한 접속

${\displaystyle \forall n.$${\big (}M(n)\lor \neg M(n){\big$ $)\},$

$또한{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {Dec}_{}}$ M ${\$라고 쓰여진 것은 의사결정 문제의 결정 가능성을 검증한 것으로 읽을 수 있습니다.클래스 표기법에서 $M{\displaystyle (n)}$ ${\displaystyle M(n)}$은(는) $n{\displaystyle }$∈ ${\displaystyle M}${\$displaystyle n\in$ M$}$으로도 씁니다$.$

${\displaystyle \mathsf{HA}}$ ${\$는 ${\displaystyle \mathsf{PA}}$ ${\${PA$}}$에서 증명할 수 없는 명제를 증명하므로$$$$, 특히 고전 이론의 어떠한 정리도 거부하지 않습니다.그러나 공리 ${\displaystyle \mathsf{HA}}$ +${\displaystyle }$¬ ${\displaystyle {Dec}_{}}$ M ${\displaystyle$ M} {\$mathsf {HA}}+\neg {\mathrm {Dec}}_{M}}$가 일치하는 술어 M$${\$displaystyle$ M$}$도 있습니다.다시, 건설적으로, 그러한 부정은 $M{\displaystyle }$(${\displaystyle t)}$ ${\displaystyle M(t)}$에 대한 제외 중간에 대한 특정 수치 반례 ${\displaystyle t}$의 존재와 동등하지 않습니다$.$ 실제로, 이미 최소 논리는 모든 명제에 대한 이중 부정 제외 중간을 증명하고, 따라서 ∀ ${\displaystyle n.}$${\displaystyle \forall n.$$\neg \neg {\big (}Q(n))\lor \neg Q(n))},$이는 $¬$ ${\displaystyle (}$$∃$ ${\displaystyle n.}$ $¬$ (${\displaystyle Q}$( ${\displaystyle n))}$$∨ ¬$ ${\displaystyle \mathrm{Q}}$ (${\displaystyle n}$ ) ) ${\displaystyle \neg {\big (})\n존재합니다.$임의의 술어 $Q{\displaystyle }$ ${\displaystyle$ Q$}$에 대해$\backslash$$neg {\big (}Q(n)\lor \neg Q$$($$n){\big )}{\big )}}.$

교회론

교회 규칙은 ${\displaystyle \mathsf{HA}}$ ${\$에서 허용 가능한 규칙입니다$.$ 교회의 논제 원리 ${\displaystyle {\mathrm{CT}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ _${0}}$은(는) ${\displaystyle \mathsf{HA}}$ ${\$에서 채택될 수 있지만$$$$${\displaystyle \mathsf{PA}}$ ${\$은(는) 이를 거부합니다$$.그것은 방금 설명한 것과 같은 부정을 암시합니다.

위의 논리적 의미에서 결정 가능한 모든 술어 역시 총 계산 가능 함수에 의해 결정된다는 형식의 원리를 생각해 보십시오.제외된 중간과 어떻게 충돌하는지 확인하려면 계산할 수 없는 술어를 정의하기만 하면 됩니다.$이$를 위해 δ${\displaystyle e_{}}$ (${\displaystyle w}$ ) :${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle 1_{}}$(${\displaystyle e,}$ e${\displaystyle ,}$ ${\displaystyle w}$) ${\displaystyle \Delta _{e}(w)$ :Kleene의 T 술어에서 정의된 술어에 $대한 =$T_${1}(e,e,w)}$입니다.총 계산 가능한 함수의 인덱스 $e$ ${\displaystyle e}$은$($는)$$∀ ${\displaystyle x.}$ ∃ ${\displaystyle w.}$ ${\displaystyle {T1}_{}}$(${\displaystyle e,}$ ${\displaystyle x,}$ $)$ {\$displaystyle \for all$ x$.\existes$w.$T_{1}(e,x,w$ ${\displaystyle {T1}_{}}$ ${\displaystyle T_{1}$은(는) 원시 재귀적으로 구현할 수 있지만 술어 $∃$ ${\displaystyle {}_{}}$.${\displaystyle }$$δ$${\displaystyle e_{}}$(${\displaystyle w)}$ ${\displaystyle \이$(는) $있습니다.$${\displaystyle e}$의$\Delta _{e}(w)},$$$즉 클래스 $H$ :$=$ ${\displaystyle \{e}$ $∣ ∃$ ${\displaystyle \mathrm{w}.}$ $δ$ ${\displaystyle e_{}}$ (${\displaystyle w)\}}$ ${\displaystyle$H :$=$\{$e\mid$\$exists$ $w.$대각선에서 정지하는 방법을 설명하는 증인이 있는 부분 계산 가능 함수 인덱스의 $\Delta _{e}(w)\}$는 계산 가능하게 열거할 수 있지만 계산할 수 없습니다.¬ ∃ ${\displaystyle {}_{}}$를 사용하여 정의된 고전적인 보어 $M${\$displaystyle$M}입니다${\displaystyle .}$ δe (${\displaystyle$ \$neg$ \$exists$ w$.$$\Delta _{e}(w)}$은(는) 계산 가능하게 열거할 수도 없습니다. 중단 문제를 참조하십시오.이 확인된 결정할 수 없는 $문제$ ∈ ${\displaystyle M}$ ${\displaystyle e\in M}$은(는) 위반 예제를 제공합니다.임의의 $인덱스$e {\$displaystylee}$에 대해 동등한 형식은$$∀ ${\displaystyle w.}$ ¬ δ ${\displaystyle e_{}}$( ${\displaystyle w)}${\$displaystyle \forall$ w$.$$\neg \Delta _{e}(w)}$는 해당 함수를 평가할 때$({\displaystyle e}$에서),$$ 평가 이력에 대한 모든 가능한 설명(${\displaystyle }$ ${\displaystyle w$이 당면한 평가를 설명하지 않음을 나타냅니다$$.특히 함수에 대해 결정할 수 없는 것은 ${\displaystyle \mathrm{WLPO}}$ ${\$에 해당하는 값에 대한 부정을 설정합니다$.$

공식적인 교회의 원칙은 당연히 재귀적 학파와 관련이 있습니다.마르코프의 원리 $MP{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{Dec}}_{}}$ ${\$는 해당 학교와 구성 수학에서 일반적으로 채택됩니다$$.Church 원칙이 있는 경우 ${\displaystyle {\mathrm{MP}}_{}}$ ${\displaystyle {\mathrm{Dec}}_{}}$ ${\$ _${\mathrm {Dec}}}}$은(는) 약한 형식 $MP{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{PR}}_{}}$ ${\$과 같습니다$.$후자는 일반적으로 단일 공리, 즉 ${\displaystyle {}_{}}$의${\displaystyle }$¬ ¬ ∃ ${\displaystyle w}$에 대한 이중 네거티브 제거로 ${\displaystyle \mathrm{표현}}$될${\displaystyle }$수 $.$ T 1 (e, x, w$)$ {\displaystyle \$neg \neg \exists$w.$T_{1}(e,x,w$ $MP{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{Dec}}_{}}$ ${\displaystyle {MP}$ _${\mathrm {Dec}}$+ ${\displaystyle {\mathrm{EC}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{0}}_{}}$ ${\$은(는) ${\displaystyle {\mathrm{판별}}_{}}$ 가능한 $술어$에 대한 전제의 독립성을 증명합니다$.$ $그러나$ IP ${\$${\$$mathrm {IP}$$_{0$$}}$과(와) 일관되게 일치하지 않습니다$.$${\displaystyle {\mathrm{CT}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$도 ${\displaystyle \mathrm{DNS<img\; alt="\{\backslash displaystyle\; \{\backslash mathrm\; \{CT\}\; \_\{0\}\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline\; mw-invert"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/9356445668640deacf4704ef8974894969d5ecb9"\; style="vertical-align:\; -0.671ex;\; width:4.41ex;\; height:2.509ex;">}}$ ${\${DNS$}}$을(를$)$ 거부합니다.L. E. J. 브라우어의 직관주의 학파는 헤잉 산술을 ${\displaystyle \mathrm{PEM}}$ ${\$과 $CT{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$을 모두 부정하는 원리의 집합으로 확장합니다$.$

모델들

일관성.

만약 어떤 이론이 일관성이 있다면, 어떤 증거도 부조리 중 하나가 아닙니다.쿠르트 괴델은 음의 번역을 도입하여 헤잉 산술이 일치하면 페아노 산술도 일치한다는 것을 증명했습니다.즉, 그는 ${\displaystyle \mathsf{PA}}$ ${\$에 대한 일관성 작업을 ${\displaystyle \mathsf{HA}}$ ${\$의 일관성 작업으로 줄였습니다$.$ 그러나 특정 이론의 일관성을 증명할 수 없다는 괴델의 불완전성 정리는 헤잉 산술 자체에도 적용됩니다.

고전적인 1차 이론 ${\displaystyle \mathsf{PA}}$ ${\$의 표준 모델과 비표준 모델 또한 Heyting 산술 ${\displaystyle \mathsf{HA}}$ ${\$의 모델입니다$.$

집합론

또한 전체 ${\displaystyle \mathsf{HA}}$ ${\$에 대한 구성 집합 이론 모델과 그 의도된 의미론이 있습니다.상대적으로 약한 집합론은 다음과 같습니다.그들은 ω ${\displaystyle \omega}$에서 산술 공식의 유도를 증명하기 위해 서술적 분리의 공리 스키마인 무한의 공리를 채택할 것이며$,$ 재귀적 정의를 위해 유한 도메인에 함수 공간의 존재를 증명할 것입니다.특히, 이러한 이론들은 ${\displaystyle \mathrm{PEM}}$ ${\$ 분리 또는 집합 유도의 전체 공리(정규성 공리는 말할 것도 없고), 일반 함수 공간(제곱 집합의 전체 공리는 말할 것도 없습니다.

${\displaystyle \mathsf{HA}}$ ${\displaystyle {\mathsf {HA}}$는 또한 서수${\displaystyle \mathsf{}}$클래스가 $\omega$ ${\displaystyle \omega}$인$$약한 구성 집합 이론과 쌍해석 가능하므로 폰 노이만 자연수의 집합이 이론에서 집합으로 존재하지 않습니다.메타이론적으로, 그 이론의 영역은 서수의 클래스만큼 크며, 자연 ${\displaystyle n}$ ∈ ω$${\$displaystyle n\in$ \omega$}}$과(와) 사영된 모든 집합의 ${\displaystyle {\mathrm {Fin}}}$에서 클래스 $F$를 통해 기본적으로 주어집니다$.$이를$${\$displaystyle$ V$$= {\$mathrm$ {Fin$}}}$에서 $V$ = ${\displaystyle F}$라고 하며, 다른 공리는 집합 대수와 순서와 관련된 것입니다.술어 분리 스키마, 확장성, 페어링 및 Set induction 스키마와 밀접하게 관련된 Union 및 Binary Intersection입니다.그러면 이 이론은 이미 강한 인피니티가 없는$$ CZF {\$displaystyle {\mathsf${CZF$}}$에 의해 주어진 이론과 동일합니다.이 집합 이론에서 ${\displaystyle \mathsf{HA}}$ ${\$의 논의는 모형 이론과 같습니다.그리고 다른 방향에서, 집합의 이론적 공리는 원시 재귀 관계에 관하여 증명됩니다.

${\displaystyle x\iny\iff \exists(r<2^{x}).\exists (s<y).{\big(}2^{x}(2s+1)+r=y{\big}}$

집합의 작은 우주는 상호 멤버쉽을 암호화하는 유한 이진 시퀀스의 순서화된 집합으로 이해될 수 있습니다.예를 들어, ${\displaystyle {1002\mathrm{}}_{}}$ ${\$ 'th 세트는 하나의 다른 세트를 포함하고 ${\displaystyle {1101012\mathrm{}}_{}}$ ${\$ $\text{'}$th 세트는 4개의 다른 세트를 포함합니다.BIT 술어 참조.

실현가능성

메타 이론에서$$ $n개$의 숫자 ${\$에 대해 연구 대상 이론의 숫자는 ${\$로 표시됩니다$.$

직관적 산술에서는 일반적으로 연결 ${\displaystyle \mathrm{속성}}$ DP$${\$displaystyle${\$mathrm {$DP$}}}$이(가) 유효합니다.그리고 그것이 성립하는 산술의 어떤 확장도 ${\displaystyle \mathrm{NEP}}$ ${\$

${\displaystyle {\mathsf {HA}}\vdash \exists n.\psi(n)\iff {\text{exists}}{\text{}}{\mathsf {HA}}\vdash \psi({\mathrm {n}})}$

따라서 이 속성들은 헤잉 산술에서 금속학적으로 동등합니다.실제로 존재 및 분리 속성은 해롭 $공식$ α ${\displaystyle \alpha },$즉 증명 $가능$한 α → ∃${\displaystyle n}$에 대해 ${\displaystyle \mathrm{존재}}$ 주장을 상대화할$$때 여전히 $유지$됩니다.$$exists$($n) ${\displaystyle$ \alpha \$to \$psi n$.\$ψ $(n)}.$

Church의 학생인 Kleene은 Heyting 산술의 중요한 실현 가능성 모델을 소개했습니다.결국, 그의 제자 넬스 데이비드 넬슨은 (${\displaystyle \mathsf{HA}}$ ${\$의 확장에서$)$ ${\displaystyle \mathsf{HA}}$ ${\$모든 변수가 구속됨을 의미함)의 모든 닫힌 정리가 실현될 수 있음을 확립했습니다.헤잉 산술의 추론은 실현 가능성을 유지합니다.또한 ${\displaystyle \mathsf{HA}}$가 ⊢ ∀ ${\displaystyle n.}$ ∃ ${\displaystyle m.}$ φ${\displaystyle (n,}$ m${\displaystyle )}$ ${\displaystyle {\mathsf {HA}}\vdash \forall n.$$\exists m.$$\varphi(n,m)}$ 그러면 $n$ ${\displaystyle {\mathrm {n}}}$에서 평가된 $함수$가 $m$ ${\displaystyle {\mathrm {m}}}$로 끝날$$때마다 ${\displaystyle \mathsf{HA}}$ $⊢ φ$ ${\displaystyle (n}$ ${\displaystyle \underset{}{},}$ ${\displaystyle m}$ ${\displaystyle \underset{}{}}$) ${\displaystyle {\mathsf {HA}}\vdash \varphi({\mathrm {n}}),$$\{\backslash$$밑줄 {\mathrm {m}}}).$함수 인수 $n{\displaystyle \mathrm{}}$ ${\$의 유한 개수로 확장할 수 있습니다$.$ ${\displaystyle \mathsf{HA}}$ ${\$이(가) 아니지만$$ 실현 가능한 고전 정리도 있습니다.

Georg Kreisel에 의해 실현 가능성의 유형화된 버전이 소개되었습니다.이를 통해 그는 직관주의 이론에 대한 고전적으로 유효한 마르코프 원리의 독립성을 증명했습니다.

BHK 해석과 변증법 해석도 참조.

효과적인 토포스에서는 $이미$ σ$$1 {\$displaystyle$ \$Sigma_{$1}}로 제한된 귀납법을 가진 헤잉 산술의 유한 공리화 가능한 하위 시스템이 범주형입니다.여기서의 범주성은 테넨바움의 정리를 연상시킵니다.이 모델은 ${\displaystyle \mathsf{HA}}$ ${\$을(를) 검증하지만$$ ${\displaystyle \mathsf{PA}}$ ${\$은(는) 검증하지 않으므로$$ 이 컨텍스트에서 완전성이 실패합니다.

유형론

추론 규칙 기반 논리 형식화를 미러링하는 유형의 이론적 실현은 다양한 언어로 구현되었습니다.

확장자

Heyting arithmic은 원시 재귀적 함수에 대해 추가된 잠재적 함수 기호와 함께 논의되었습니다.그 이론은 아커만 함수의 총합을 증명합니다.

이를 넘어서 공리주의와 형식주의 선택은 구성주의자들 내부에서도 항상 논쟁이 되어 왔습니다.${\displaystyle \mathsf{HA}}$ ${\$의 많은 유형의 확장은 증명 이론에서 광범위하게 연구되었습니다$$. 예를 들어, 숫자 사이의 함수 유형 및 그 사이의 함수 유형 등이 있습니다.다양한 가능한 공리가 함수의 적용을 지배하면서 형식은 자연스럽게 더 복잡해집니다.전체 함수 클래스는 이런 식으로 풍부해질 수 있습니다.유한형 ${\displaystyle {\mathsf{HA}}^{}}$ ω ${\$$displaystyle {\mathsf$$${$HA}}^{\omega}}$를 가진 이론은 ${\displaystyle N^{}}$ {\$displaystyle${\$mathbb${N$}^{\mathbb${N$}}}$의 함수 확장성과 선택 공리를 더 결합하면 $여전히$ ${\displaystyle \mathsf{HA}}${\$displaystyle${\$mathsf$ {HA$}}$와 같은 산술 공식을 증명하고 유형 이론적 해석을 갖습니다.그러나 이 이론은 N ${\displaystyle N^{}}$ ${\displaystyle {\mathbb {N}}^{\mathbb {N}}}$에 대한 Church의 논문을 ${\displaystyle {거부}^{}}$할${\displaystyle {}^{}}$뿐만 $N$ → N {\$displaystyle {\mathbb {$N}^{\mathbb ${N}}\에서 {\$mathbb {$N}}}$까지의 모든 함수는 연속됩니다.그러나 서로 다른 확장 규칙, 선택 공리, 마르코프 및 독립 원리, 그리고 심지어 K ő$닉$의 보조자까지 모두 함께 채택하지만 각각 특정 강도나 수준에서 제외된 중간을 증명하지 못할 수 있는 다소 "충만한" 산술을 π ${\displaystyle {}_{}^{}}$ ${\displaystyle \Pi _{1}^{0}}$ -공식 수준에서 정의할 수 있습니다.일찍이 집중적 평등성과 브루어적 선택 서열을 가진 변종들도 조사되었습니다.

건설적인 2차 산술의 역수학 연구가 수행되었습니다.^[4]

역사

이론의 형식 공리화는 Heyting (1930), Herbrand and Kleene으로 거슬러 올라갑니다.괴델은 1933년 ${\displaystyle \mathsf{PA}}$ ${\$에 대한 일관성 결과를 증명했습니다.

관련개념

헤이팅 산술은 부울 대수의 직관적인 유사체인 헤이팅 대수와 혼동되어서는 안 됩니다.

참고 항목

• BHK해석
• 건설적 분석
• 구성집합론
• 해롭 공식
• 실현가능성

참고문헌

• Ulrich Kohlenbach (2008), 응용 증명 이론, Springer.
• Anne S. Troelstra, ed. (1973), 직관적 산술과 분석의 메타수학적 조사, Springer, 1973.

외부 링크

• 스탠포드 철학 백과사전: Joan Moschovakis의 "직관적 수론"
• 볼프강 버의 헤잉 산술의 파편