뢰브의 정리

수학적 논리학에서 뢰브의 정리에서는 페아노 산술(PA) (또는 PA를 포함한 모든 공식 시스템)에서 모든 공식 P에 대해, "P가 PA에서 증명될 수 있다면 P는 진실"이라고 PA에서 증명할 수 있다고 기술하고 있다.좀 더 공식적으로, Prov(P)가 P 공식의 입증가능성을 의미한다면,

\matrm {if} \PA\vdash({\rm {Prov}(P)\오른쪽 화살표 P)\matrm {, 그 다음} \PA\vdash P,

또는

{\dfrac {PA\vdash {\rm {Prov}(P)\오른쪽 화살표 P}{PA\vdash P}}.}

뢰브 정리의 즉각적인 귀결(반대)은 P가 PA에서 증명할 수 없다면, P가 PA에서 증명될 수 있다면 P는 진실이다.예를 들어 " $1+1=3$ + $1+1=3$ = 3 $1+1=3$ 이 $1+1=3$ (가) PA에서 제공될 수 있는 경우, $1+1=3$ 1 + $1+1=3$ = $1+1=3$ {\ $displaystyle$ 1+ $1=3$ 은 PA에서 제공되지 않는다.^{[note 1]}

뢰브의 정리는 1955년에 그것을 공식화한 마틴 휴고 뢰브(Martin Hugo Löb)의 이름을 따서 명명되었다.그것은 커리의 역설과 관련이 있다.

뢰브의 검증 논리 정리

Provability 로직은 주어진 시스템에서 $\phi$ ${\displaystyle \pi$ }의 Provability를 모달 로직의 언어로 표현함으로써 괴델의 불완전성 이론에 사용된 인코딩의 세부사항에서 추상화된다. $\Box \phi$ ${\displaystyle \Box \phi$ $\Box \phi$

그러면 공리에 의해 뢰브의 정리를 공식화할 수 있다.

\Box(\Box P\오른쪽 화살표 P)\오른쪽 화살표 \Box P,

궤델 뢰브(Gedel-Löb)의 경우, 공리 GL로 알려져 있다.이것은 때때로 주입되는 추론 규칙에 의해 공식화된다.

P}

로부터

\displaystyle \Box P\오른쪽 화살표 P.}

모달 로직 K4(또는 공리 $\Box A\rightarrow \Box \Box A$ 4, $\Box A\rightarrow \Box \Box A$ A $\Box A\rightarrow \Box \Box A$ → $\Box A\rightarrow \Box \Box A$ ◻ ◻ $\Box A\rightarrow \Box \Box A$ $\Box A\rightarrow \Box \Box A$ {\ $displaystyle \Box \rightarrow \Box$ \ $Box A}$ , )를 취함으로써 발생하는 Provability logic은 Provability logic에서 가장 집중적으로 조사되는 시스템이다.

뢰브의 정리 모달 증명

뢰브의 정리는 모달 논리 내에서 검증 연산자(K4 시스템)에 모달 고정점의 존재에 관한 몇 가지 기본적인 규칙만을 사용하여 증명할 수 있다.

모달 공식

공식에 대해 다음과 같은 문법을 가정한다.

$X$ $X$ 이 $X$ (가) 제안 변수라면 X ${\displaystyle$ X $}$ 은 $X$ 이다 $X$ .
$K$ $K$ 이 $K$ (가) 제안 상수라면 K $K$ 은 공식이다 $K$ .
$A$ 이(가) 공식이라면 $A$ $\Box A$ $\Box A$ ${\displaystyle \Box$ A $}$ 은 공식이다 $\Box A$ .
If $A$ and $B$ are formulas, then so are $\neg A$ , $A\rightarrow B$ , $A\wedge B$ , $A\vee B$ , and $A\leftrightarrow B$

모달 문장은 명제 변수가 없는 모달 공식이다. $\vdash A$ 는 $\vdash A$ $\vdash A$ A $\vdash A$ 을(를) 사용하여 $A$ ${\displaystyle$ A $}$ 이(가) 정리임을 $A$ 의미한다.

모달 고정점

$F(X)$ ( $F(X)$ ) $F(X)$ 이 $F(X)$ (가) 하나의 제안 $변수$ X ${\displaystyle$ X $}$ 만 있는 모달 공식이라면 $X$ $F(X)$ ( $F(X)$ ) $F(X)$ 의 모달 고정 지점은 다음과 같은 $\Psi$ 문장 $\Psi$ $\Psi$ 이다 $F(X)$ .

\vdash \PSI \좌우 이동 F(\Box \PSI )

우리는 하나의 자유 변수를 가진 모든 모달 공식에 대해 그러한 고정된 점의 존재를 가정할 것이다.이것은 물론 명백하게 추측할 수 있는 것은 아니지만 $\Box$ we ${\displaystyle \Box$ }을(를) Peano Mathing에서 검증가능성으로 $\Box$ 해석하면, 대각선 보조마에서 모달 고정점의 존재가 뒤따른다.

추론의 모달 규칙

모달 고정점의 존재 외에도, 우리는 힐버트-베르네이즈 검증 조건이라고 알려진 검증 $\Box$ 연산자 $\Box$ operator{\ $displaystyle \Box }$ 에 대한 다음과 같은 추론 규칙을 가정한다.

(필요) $\vdash A$ $\vdash A$ {\ $displaystyle \vdash A}$ 로부터 $\vdash A$ $\vdash \Box A$ A $\vdash \Box A$ : 비공식적으로 이것은 A가 정리라면 그것은 증명할 수 있다고 말한다.
(내부 필요) $\vdash \Box A\rightarrow \Box \Box A$ ⊢ $\vdash \Box A\rightarrow \Box \Box A$ $\vdash \Box A\rightarrow \Box \Box A$ → $\vdash \Box A\rightarrow \Box \Box A$ ◻ $\vdash \Box A\rightarrow \Box \Box A$ $\vdash \Box A\rightarrow \Box \Box A$ $\vdash \Box A\rightarrow \Box A$ : A가 증명 가능하다면 증명할 수 있다.
(박스배급성) $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$ ( $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$ $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$ ) $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$ → $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$ → $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$ $\vdash \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)$ ) ${\디스플레이$ 스타일 $\vdash$ \vdash $\Box$ ( $A\오른쪽$ 화살표 $B)\오른쪽 화살표$ (\ $Box$ A $\오른쪽$ 화살표 $\B)}$ : 이 규칙은 Provability Operator 안에서 modus pon을 할 수 있다.만약 A가 B를 암시하고, A가 증명할 수 있다면, B는 증명할 수 있다.

뢰브의 정리 증명

mod $\vdash \Box P\rightarrow P$ $\vdash \Box P\rightarrow P$ → P ${\displaystyle \vdash \Box P\오른쪽$ 화살표 $P}$ 와 $P$ 같은 모달 문장 $P$ $P$ 이(가) 있다고 가정해 보십시오 $\vdash \Box P\rightarrow P$
대략 $P$ $P$ 이 $P$ (가) 증명 가능하다면, 사실이라는 것이 정리다.
이것은 건전성을 주장하는 것이다.
From the existence of modal fixed points for every formula (in particular, the formula $X\rightarrow P$ ) it follows there exists a sentence $\Psi$ such that $\vdash \Psi \leftrightarrow (\Box \Psi \rightarrow P)$ .
2부터는 $\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$ → $\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$ → $\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$ ( $\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$ ( $\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$ → $\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$ $){\displaystyle \vdash \Psi \rightarrow (\Box \Psi \rightarrow$ P $)}$ 에 따른다 $\vdash \Psi \rightarrow (\Box \Psi \rightarrow P)$
필요 규칙에서 $\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$ ◻ $\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$ → ( $\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$ ◻ $\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$ → $\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$ ) ${\displaystyle \vdash \Box(\Psi \rightarrow (\Box \Psi \rightarrow$ P $\vdash \Box (\Psi \rightarrow (\Box \Psi \rightarrow P))$ 을(를) 따른다.
4와 박스 배포성 규칙에서 $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ ◻ $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ → → $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ → P $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ ) ${\displaystyle \vdash \Box \PSI \rightarrow \Box (\Box \Psi \rightarrow$ P)}을(\Box \ $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$ \rightarrow)}한다 $\vdash \Box \Psi \rightarrow \Box (\Box \Psi \rightarrow P)$
Applying the box distributivity rule with $A=\Box \Psi$ and $B=P$ gives us $\vdash \Box (\Box \Psi \rightarrow P)\rightarrow (\Box \Box \Psi \rightarrow \Box P)$ .
5, 6부터는 $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ ⊢ $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ → $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ → → $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ ( $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ ( $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ → $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$ P $){\displaystyle \vdash$ \ $Box \Psi \rightarrow (\Box \Box \Psi \rightarrow P)}$ 에 따른다 $\vdash \Box \Psi \rightarrow (\Box \Box \Psi \rightarrow \Box P)$
내부 요구 $\vdash \Box \Psi \rightarrow \Box \Box \Psi$ 에서 $\vdash \Box \Psi \rightarrow \Box \Box \Psi$ $\vdash \Box \Psi \rightarrow \Box \Box \Psi$ → → $\vdash \Box \Psi \rightarrow \Box \Box \Psi$ ◻ { { { ${$ \ $vdash \vdash \Box \rightarrow \Box$ \Box \ $Box \Psi }$ 을(를) 따른다 $\vdash \Box \Psi \rightarrow \Box \Box \Psi$
$\vdash \Box \Psi \rightarrow \Box P$ ~8부터는 $\vdash \Box \Psi \rightarrow \Box P$ ◻ → → $\vdash \Box \Psi \rightarrow \Box P$ P ${\displaystyle \vdash \Box \PSI \rightarrow \Box$ P $}$ 에 따른다 $\vdash \Box \Psi \rightarrow \Box P$
$\vdash \Box \Psi \rightarrow P$ 과 9번부터는 $\vdash \Box \Psi \rightarrow P$ ◻ $\vdash \Box \Psi \rightarrow P$ → → $\vdash \Box \Psi \rightarrow P$ $\vdash \Box \PSI \rightarrow P$ 에 따른다 $\vdash \Box \Psi \rightarrow P$
2부터는 $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ ( $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ → $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ → $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ ) $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ → $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$ 에 따른다 $\vdash (\Box \Psi \rightarrow P)\rightarrow \Psi$
$\vdash \Psi$ 11부터는 $\vdash \Psi$ from $⊢{\displaystyle \vdash \psi }$ 에 따른다.
$\vdash \Box \Psi$ 부터 필수 규칙 $\vdash \Box \Psi$ $\vdash \Box \Psi$ $◻{\displaystyle \vdash \Box \PSI$ }을 $\vdash \Box \Psi$ 를) 따른다.
13번과 10번부터는 $\vdash P$ $\vdash P$ $\vdash P$ 을(를) 따른다 $\vdash P$

예

뢰브 정리의 즉각적인 요점은 P가 PA에서 증명할 수 없다면, "P가 PA에서 증명할 수 있다면 P는 진실이다"는 것이다.PA가 일관성이 있다는 것을 알고 있기 때문에(그러나 PA는 PA가 일관성이 있다는 것을 알지 못한다), 몇 가지 간단한 예를 들어보자.

" $1+1=3$ + $1+1=3$ = 3 $1+1=3$ 이 $1+1=3$ (가) PA에서 증명할 수 있는 경우, $1+1=3$ + $1+1=3$ = $1+1=3$ $1+1=3$ 이 $1+1=3$ (가) PA에서 증명할 수 없으므로 $1+1=3$ 에서 증명할 수 없다.
" $1+1=2$ + $1+1=2$ = 2 $1+1=2$ 이 $1+1=2$ (가) PA에서 증명할 수 있는 경우 $1+1=2$ " $1+1=2$ 1 $1+1=2$ + $1+1=2$ = $1+1=2$ $1+1=2$ ${\displaystyle 1+1=2"$ 형식의 문장이 PA에서 증명할 수 있다. $1+1=2$
"강화된 유한한 램지 정리가 PA에서 증명될 수 있다면, 강화한 유한한 램지 정리가 참이다"는 PA에서 증명할 수 없기 때문에 PA에서는 증명할 수 없다(진실함에도 불구하고).

독사적 논리학에서 뢰브의 정리는 반사적 "형식 4" 이성자로 분류된 어떤 시스템도 역시 "모드스트"여야 한다는 것을 보여준다: 그러한 이성자는 P가 사실이라는 것을 먼저 믿지 않고서는 결코 "P에 대한 나의 믿음이 P가 진실임을 암시할 것이다"라고 믿을 수 없다.^[1]

괴델의 두 번째 불완전성 정리는 뢰브의 정리로부터 따르며 거짓 진술 statement $\bot$ 을 P로 $\bot$ 대체한다.

컨버스:뢰브의 정리는 모달 고정점의 존재를 암시한다.

모달 고정점의 존재는 뢰브의 정리를 암시할 뿐만 아니라, 그 반대도 유효하다.뢰브의 정리가 공리(구성표)로 주어졌을 때, p에서 변조된 공식 A(p)에 대해 $p\leftrightarrow A(p)$ 고정점(증명 가능한 동등성까지) p $p\leftrightarrow A(p)$ ( $p\leftrightarrow A(p)$ p (p ) ${\디스플레이 스타일 p\좌우타로우$ A( $p)}$ 의 존재가 도출될 수 있다.^[2]따라서 정상적인 모달 논리에서는 뢰브의 공리는 공리 스키마 4, ( $(\Box A\rightarrow \Box \Box A)$ $(\Box A\rightarrow \Box \Box A)$ → $(\Box A\rightarrow \Box \Box A)$ $(\Box A\rightarrow \Box \Box A)$ ) $(\Box A\rightarrow \Box \Box A)$ 와 $(\Box A\rightarrow \Box \Box A)$ 모달 고정 포인트가 있는 것과 동등하다.

메모들

^ PA가 일관성이 없는 경우( $1+1=3$ 경우 $,$ $1+1=3$ + $1+1=3$ 1 = 3 {\ $displaystyle 1+$ 1=3}을(를) 포함하여 모든 문장이 입증 가능하다). $1+1=3$

인용구

^ 스물리안, 레이몬드 M, (1986) 자신에 대해 추론하는 논리학자, 1986년 지식 추론의 이론적 측면에 관한 회의의 진행, 몬테레이(CA), 모건 카우프만 출판사, 샌프란시스코(CA), 페이지 341-352
^ Per Lindström (June 2006). "Note on Some Fixed Point Constructions in Provability Logic". Journal of Philosophical Logic. 35 (3): 225–230. doi:10.1007/s10992-005-9013-8. S2CID 11038803.

참조

Boolos, George S. (1995). The Logic of Provability. Cambridge University Press. ISBN 978-0-521-48325-4.
Löb, Martin (1955), "Solution of a Problem of Leon Henkin", Journal of Symbolic Logic, 20 (2): 115–118, doi:10.2307/2266895, JSTOR 2266895
Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 978-1-56881-262-5.
Verbrugge, Rineke (L.C.) (1 January 2016). "Provability Logic". The Stanford Encyclopedia of Philosophy. Retrieved 6 April 2016.

외부 링크

플래닛매트릭스에서의 뢰브의 정리
엘리에저 유드코프스키의 뢰브 정리 만화 안내서

[1] PA가 일관성이 없는 경우( $1+1=3$ 경우 $,$ $1+1=3$ + $1+1=3$ 1 = 3 {\ $displaystyle 1+$ 1=3}을(를) 포함하여 모든 문장이 입증 가능하다). $1+1=3$

[2] 스물리안, 레이몬드 M, (1986) 자신에 대해 추론하는 논리학자, 1986년 지식 추론의 이론적 측면에 관한 회의의 진행, 몬테레이(CA), 모건 카우프만 출판사, 샌프란시스코(CA), 페이지 341-352

[3] Per Lindström (June 2006). "Note on Some Fixed Point Constructions in Provability Logic". Journal of Philosophical Logic. 35 (3): 225–230. doi:10.1007/s10992-005-9013-8. S2CID 11038803.

[note 1]

[1]

[2]

Search