Ω-consistent 이론

수학적 논리학에서 Ω 일치(^[1]또는 오메가 일치, 수적으로 분리되는 것이라고도 함) 이론은 (문장의 집합) 일관성이 있을 뿐만 아니라(즉, 모순을 증명하지 못한다) 직관적으로 모순되는 문장의 어떤 무한한 조합을 증명하는 것을 회피하는 이론이다.그 이름은 불완전성 정리를 증명하는 과정에서 개념을 도입한 쿠르트 괴델 때문이다.^[2]

정의

이론 T는 산술 공식의 번역이 있으면 산술의 언어를 T의 언어로 해석하여 T가 이 번역에 따라 자연수의 기본 공리를 증명할 수 있도록 한다고 한다.

A T that interprets arithmetic is ω-inconsistent if, for some property P of natural numbers (defined by a formula in the language of T), T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) holds), but T also proves that there is some natural number n (necessarily nonstandard in any model for T) such P(n)가 실패한다는 것.이는 T가 P(n)가 실패하는 n의 어떤 특정한 값에 대해 증명할 수 없을 수 있기 때문에, 단지 그러한 n이 있다는 것만을 증명할 수 없기 때문에 T 내부에서 모순을 일으키지 않을 수 있다.

T는 Ω이 존재하지 않는 경우 Ω과 일치한다.

σ-음향에는₁ 약하지만 밀접한 관계가 있는 성질이 있다.산술 N의 표준 모델(즉, 덧셈과 곱셈이 있는 통상적인 자연수의 구조)에서 T에서 증명할 수 있는 모든 σ이⁰₁^[3] 참이라면 이론 T는 sound-소리₁(또는 다른 용어로 1-일치)이다.T가 합리적인 연산 모델을 공식화할 만큼 충분히 강하다면, ,-사운드는₁ T가 튜링 머신 C가 정지한다는 것을 증명할 때마다 C가 실제로 정지하도록 요구하는 것과 동등하다.모든 Ω 일치 이론은 σ-sound이지만₁, 그 반대의 경우도 아니다.

보다 일반적으로, 우리는 더 높은 수준의 산술적 계층 구조에 대해 유사한 개념을 정의할 수 있다.if이 산술 문장의 집합(일반적으로 일부 n의 경우 σ⁰_n)인 경우, T에서 증명할 수 있는 모든 γ이 표준 모델에서 참이면 이론 T는 γ-sound이다.γ이 모든 산술적 공식의 집합일 때 sound-음성은 just (산술적) 건전성이라고 한다.만약 T의 언어가 산술어(예: 집합 이론과 반대되는)로만 이루어진다면, 사운드 시스템은 통상적인 수학 자연수의 집합인 집합 Ω으로 생각할 수 있는 모델을 가진 것이다.일반 T의 경우는 다르다. 아래의 Ω-logic을 참조한다.

σ-음향은_n 다음과 같은 계산 해석을 가지고 있다:이 이론이 or-오라클을_n−1 사용하는 프로그램 C가 정지한다는 것을 증명한다면, C는 실제로 정지한다.

예

일관된 Ω 일관성 없는 이론

Peano 산술 이론은 PA를 쓰고, "PA는 일치한다"는 주장을 공식화한 산술문은 Con(PA)을 쓴다.Con(PA)은 "모든 자연수 n에 대해 n은 PA로부터 0=1이라는 증명의 괴델 숫자가 아니다."(이 공식은 직접적인 모순 대신 0=1을 사용한다. PA가 확실히 ¬0=1을 증명하기 때문에, 0=1 또한 증명된다면, 우리는 모순을 가질 수 있고, 반면에 PA가 모순을 증명한다면, 같은 결과를 얻을 수 있다.0=1)을 포함한 모든 것을 증명한다.

이제 PA가 정말 일관성이 있다고 가정하면 PA + ¬Con(PA)도 일관성이 있다는 것을 따르게 되는데, 만약 그렇지 않다면 PA는 괴델의 두 번째 불완전성 정리를 반박하는 Con(PA)(감소)을 증명할 것이기 때문이다.단, PA + ¬Con(PA)은 Ω과 정합성이 없다.이는 어떤 특정한 자연수 n에 대해, PA + conCon(PA)은 n이 0=1이라는 증명의 괴델 숫자가 아님을 증명하기 때문이다(PA 자체는 그 사실을 증명하고, 추가적인 가정 ¬Con(PA)은 필요하지 않다).그러나 PA + ¬Con(PA)은 일부 자연수 n에 대해 n은 그러한 증명의 괴델 번호(Gödel 번호)라는 것을 증명한다(이는 단지 클레임 conCon(PA)의 직접적인 재작성일 뿐이다).

이 예에서 공리 ¬Con(PA)은 σ이므로₁ 시스템 PA + ¬Con(PA)은 사실 ω-unsound일 뿐 Ω이 존재하지₁ 않는다.

산술적으로 건전하고 Ω 일관성이 없는 이론

각 자연수 n에 대한 공리 c ≠ n과 함께 T가 PA가 되게 한다. 여기서 c는 언어에 추가된 새로운 상수다.그 다음 T는 산술적으로 건전하지만(PA의 어떤 비표준 모델이 T의 모델로 확장될 수 있기 때문에), Ω으로 일관성이 없다(${\displaystyle \mathrm{모든}}$ 숫자 n에 대해 $\exists {\displaystyle \mathrm{}}$ ${\displaystyle x}$= ${\displaystyle x}$ ${\displaystyle\exists x\,$c$=$x$\},$ c ≠ n).

산술어만을 이용한 σ음₁ Ω 일관성 없는 이론은 다음과 같이 구성할 수 있다.어떤_n n > 0에 대해서도 인덕션 스키마가 σ-포뮬라로_n 제한되는 PA의 하위 이론이 되게 한다.Ⅰ_{n + 1} 이론은 정밀하게 공리화할 수 있으므로, A를 그 하나의 공리로 하고, 이론 T_n = Iς + ¬A를 고려한다.A가 인덕션 스키마의 한 예라고 가정할 수 있는데, 인덕션 스키마는 그 형식을 갖추고 있다.

${\displaystyle \forall w\,[B(0,w)\land \forall x\, (B(x,w)\to B(x+1,w))\to \all x\,B(x,w)]}$

만약 우리가 공식을 의미한다면

${\displaystyle \forall w\,[B(0,w)\land \forall x\, (B(x,w)\to B(x+1,w))\to B(n,w)]}$

P(n)에 의해, 그리고 모든 자연수 n에 대해 이론 T(실제로, 심지어 순수한 술어 미적분까지도)는 P(n)를 증명한다.반면 T는${\displaystyle \mathrm{}}$axi x ${\displaystyle \neg \mathrm{}}$ ${\displaystyle P}$( ${\displaystyle x}$) ${\displaystyle \exists$ x$\,\neg P(x)}$라는 공식은 공리$$¬A와 논리적으로 동등하기 때문에 증명한다.따라서 T는 Ω과 일관성이 없다.

T가 π-sound라는_{n + 3} 것을 보여줄 수 있다.사실, 그것은 (확실히 건전한) 이론 I Ⅰ에_n 대한 Ⅱ 보수적인_{n + 3} 것이다.논쟁은 더욱 복잡하다(Iς에서_{n + 1} I in에_n 대한 σ반사_{n + 2} 원리의 실현 가능성에 의존한다).

산술적으로 불건전하고 Ω 일관성이 있는 이론

Ω-Con(PA)을 "PA는 Ω-consistency" 문장으로 공식화한다.그러면 이론 PA + Ω-Con(PA)은 불건전하지만(정확히 말하면 Ω-unsound₃), Ω은 일치한다.그 주장은 첫 번째 예와 유사하다: 적절한 버전의 힐버트-베르네이즈-Löb 유도 조건은 "provability pragement" Ω-Prov(A) = Ω-Con(PA + +A)에 대해 유지되므로 괴델의 두 번째 불완전성 정리의 아날로그를 만족한다.

Ωlogic

정수가 진정한 수학 정수인 산술 이론의 개념은 Ω-logic에 의해 포착된다.^[4]T는 자연수만을 보유하려는 단수 술어 기호 N과 각 (표준) 자연수(별도의 상수일 수도 있고 0, 1, 1, 2, ... 등의 상수일 수도 있음)에 대해 1개씩 보유하려는 특정 이름 0, 1, 2, ...을 포함하는 셈 가능한 언어의 이론이 되도록 하자.T 자체는 실제 숫자나 집합과 같은 더 일반적인 객체를 지칭할 수 있다는 점에 유의하십시오. 따라서 T의 모델에서 N(x)을 만족하는 객체는 T가 자연수로 해석하는 물체일 수 있으며, 이 모든 물체는 지정된 이름 중 하나로 명명될 필요가 없다.

Ω-logic 시스템은 형식에 대한 Ω-rule인 지정된 자유 변수 x를 가진 각 T-formula P(x)에 대해 일반적인 1차 술어 로직의 모든 공리와 규칙을 포함한다.

$P{\displaystyle }$( ${\displaystyle 0}$)${\displaystyle }$, ${\displaystyle P}$( ${\displaystyle 1}$)${\displaystyle }$, ${\displaystyle P}$( 2${\displaystyle }$)${\displaystyle }$,${\displaystyle }$… ${\displaystyle P(0),$ P $(1), P$ ($2),\$ldots$$}} 추론$$ ${\displaystyle x}$( ${\displaystyle N}$( ${\displaystyle x}$)${\displaystyle }$→ ${\displaystyle P}$ ( x ) $displaysty \forall$ x$\,$ ( N$)(x)\p(x$

즉, 이론이 지정된 이름에 의해 주어진 각 자연수 n에 대해 별도로 P(n)를 주장한다면, 또한 규칙의 무한히 많은 선행자의 명백하고 보편적으로 계량화된 상대방에 의해 한 번에 모든 자연수에 대해 집합적으로 P를 주장할 수 있다.산술 이론의 경우, 의도된 영역인 Peano 산술과 같은 자연수를 가진 이론의 경우, 용어 N은 중복되며 각 P에 대한 규칙의 결과로${\displaystyle \mathrm{}}$simplifying ${\displaystyle x}$ ${\displaystyle P}$( ${\displaystyle x}$) ${\displaystyle \forall x\,P(x)}$로 단순화된다$.$

T의 Ω 모델은 자연수를 포함하고 지정된 이름과 기호 N을 표준으로 해석한 T의 모델이다. 각각은 그러한 숫자와 그 숫자만을 도메인으로 가지고 있는 술어로 해석된다(비표준 숫자가 없는 것이다.N이 언어에 없는 경우 N의 영역은 모델의 영역이어야 한다. 즉, 모델은 자연수만 포함한다. (T의 다른 모델들은 이러한 기호를 비표준적으로 해석할 수 있다. 예를 들어 N의 영역은 셀 수도 없다.)이러한 요건은 모든 Ω 모델에서 Ω-rule을 울리게 한다.생략형 정리에 대한 코롤러로서, 역은 또한 유지된다: 이론 T는 Ω 로직에서 일관성이 있는 경우에만 Ω-모델을 갖는다.

Ω-로직과 Ω-consistency의 밀접한 관계가 있다.Ω-로직으로 일관되는 이론도 Ω-consistent(및 산술적으로 건전하다)이다.Ω-로직의 일관성이 Ω-consistency보다 훨씬 강한 개념이기 때문에 역은 거짓이다.그러나 다음과 같은 특성화는 다음과 같다: Ω-규칙의 검증되지 않은 적용에 따른 폐쇄가 일관성이 있는 경우에만 이론이 Ω-consistic이다.

기타 일관성 원칙과의 관계

만약 T 이론이 재귀적으로 공리화할 수 있다면, 크레이그 스미르시스키 때문에 Ω-일관성은 다음과 같은 특징을 갖는다.^[5]

$T{\displaystyle }$+ ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{F}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{T}}_{}}$+ ${\displaystyle T\mathbb{}}$ ${\displaystyle {\mathrm{H}}_{}}$ ${\displaystyle {{\mathrm{}}_{}^{}}_{}}$ 2 ${\displaystyle {{}_{}^{}}_{}}$( N${\displaystyle }$) ${\displaystyle$ T$+\mathrm${RFN}$_{T}+\mathrm {Th} _{\Pi _{2}^{0}}}(\mathb {N}$)이$$ 일관성이 있는 경우에만 T가 Ω이다.

Here, ${\displaystyle \mathrm {Th} _{\Pi _{2}^{0}}(\mathbb {N} )}$ is the set of all Π⁰₂-sentences valid in the standard model of arithmetic, and ${\displaystyle \mathrm {RFN} _{T}}$ is the uniform reflection principle for T, which consists of the axioms

${\displaystyle \forall x\,(\mathrm {Prov}) _{T}(\ulcorner \varphi({\dot {x})\urcorner )\to \varphi(x)}$

자유 변수가 하나 있는$$ $모든{\displaystyle }$ 공식 ${\displaystyle \varphi }$에 대해.특히 산술 언어의 미세한 공리학적 이론 T는 T + PA가 $\sigma {\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$ -sound인$$ 경우에만 Ω으로 일치한다.

메모들

참고 문헌 목록

• 쿠르트 괴델(1931년).'위버 공식 unentscheidbare Setze der Principia Mathematica und verwandter Systeme I.'모나체프테 퓌르 수학에서.영어로 번역된 "공국 수학 및 관련 시스템의 공식적으로 불문명 제안".