건설증거

수학에서 건설적인 증명은 물체를 창조하는 방법을 만들거나 제공함으로써 수학적 물체의 존재를 증명하는 증거의 방법이다. 이것은 예를 제시하지 않고 특정한 종류의 물체의 존재를 증명하는 비건설적 증거(존재 증명 또는 순수한 존재 정리라고도 한다)와는 대조적이다. 뒤따르는 더 강한 개념과의 혼동을 피하기 위해, 그러한 건설적인 증거를 효과적인 증명이라고 부르기도 한다.

건설적인 증거는 또한 건설적인 수학에서 유효한 입증의 더 강한 개념을 언급할 수 있다. 구성주의는 명시적으로 구축되지 않은 물체의 존재를 수반하는 모든 증명 방법을 거부하는 수학 철학이다. 이는 특히 배제된 중간의 법칙, 무한의 공리, 선택의 공리 등을 배제하고, 일부 용어(예를 들어 "또는"이라는 용어는 고전보다 건설 수학에서 더 강한 의미를 갖는다)에 대해 다른 의미를 유도한다.^[1]

일부 비건설적 증거는 어떤 명제가 거짓이면 모순이 뒤따른다는 것을 보여준다. 따라서 명제는 진실이어야 한다( 모순에 의해 증명). 그러나 직감주의를 비롯한 건설 수학의 일부 품종에서는 폭발(ex falso quodlibet)의 원리가 받아들여졌다.

건설적인 증거는 인증된 수학적 알고리즘을 정의하는 것으로 볼 수 있다: 이 아이디어는 브루워-에서 탐구된다.헤이팅-콜모고로프 건설논리의 해석, 증명과 프로그램 사이의 커리-하워드의 대응, 그리고 페르 마틴-뢰프의 직관적 유형 이론, 티에리 코콴트와 제라드 휴에트의 건설 미적분 같은 논리 시스템.

역사적 예

19세기 말까지만 해도 모든 수학적 증거는 본질적으로 건설적이었다. 게오르크 칸토어의 무한 집합 이론과, 실수의 공식적 정의와 함께 최초의 비건설적 건설이 나타났다.

이전에 고려된 문제를 해결하기 위해 비건설적 증거를 처음으로 사용한 것은 힐베르트의 Nullstellensatz와 힐베르트의 기본 정리인 것 같다. 철학적 관점에서 보면, 전자는 특히, 잘 정해진 사물의 존재를 암시하는 것처럼 흥미롭다.

Nullstellensatz는 다음과 같이 명시할 수 있다. $f_{1},\ldots ,f_{k}$ $f_{1},\ldots ,f_{k}$ , $f_{1},\ldots ,f_{k}$ … , $f_{1},\ldots ,f_{k}$ ${\$ 이(가) 공통 복합 0이 없는 $nindeterminates$ 의 다항식인 $f_{1},\ldots ,f_{k}$ 경우 $g_{1},\ldots ,g_{k}$ 다항식 $g_{1},\ldots ,g_{k}$ $g_{1},\ldots ,g_{k}$ , $g_{1},\ldots ,g_{k}$ , , $g_{1},\ldots ,g_{k}$ k $g_{1},\ldots ,g_{k}$ {\ $displaysty g_{1},\ldots,g_{k}$ 등이 있다.

f_{1}g_{1}g_{1}+\ldots +f_{k}g_{k}=1.

그러한 비건설적인 존재 정리는 그 당시의 수학자들에게 너무나 놀라운 것이어서 그 중 한 사람인 폴 고든은 다음과 같이 썼다. "이것은 수학이 아니라 신학이다."^[2]

25년 후 그레테 헤르만은 힐베르트의 결과를 사용했기 때문에 강력한 의미에서는 건설적인 증거가 되지 $g_{1},\ldots ,g_{k},$ 않는 g $g_{1},\ldots ,g_{k},$ , $g_{1},\ldots ,g_{k},$ , , $g_{1},\ldots ,g_{k},$ $g_{1},\ldots ,g_{k},$ , $g_{1},\ldots ,g_{k$ 를 계산하는 알고리즘을 제공했다. 그녀는 만약 $g_{1},\ldots ,g_{k}$ 1 $g_{1},\ldots ,g_{k}$ , … $g_{1},\ldots ,g_{k}$ , $g_{1},\ldots ,g_{k}$ $g_{1},\ldots ,g_{k}$ ${\$ 이 $g_{1},\ldots ,g_{k}$ 존재한다면, 2 $2^{2^{n}}$ {\ $displaystyle$ 2 $^{2^{n}}}$ 미만의 도에서 발견될 수 있다는 것을 증명했다 $2^{2^{n}}$ ^[3]

$g_{i}.$ 은 g $g_{i}.$ $g_{i$ 의 한정된 계수 수를 알 수 없는 것으로 간주함으로써 선형 방정식의 시스템 해결로 문제가 감소함에 따라 알고리즘을 제공한다. $}$

예

비건설적 증명

우선 소수 정리가 있다는 정리를 고려한다. 유클리드의 증거는 건설적이다. 그러나 유클리드 증거를 단순화하는 공통적인 방법은 정리에서의 주장과는 달리 한정된 수의 그것들만이 있을 뿐이며, 이 경우 가장 큰 것이 있을 경우에는 n을 가리킨다고 가정한다. 그런 다음 숫자 n! + 1(1 + 첫 번째 n 숫자의 곱)을 고려하십시오. 이 숫자가 원시적이거나 모든 주요 요인이 n보다 크다. 특정 소수만을 설정하지 않고, 이것은 원래의 가정과는 반대로 n보다 큰 하나가 존재한다는 것을 증명한다.

이제 정리 " $a^{b}$ ${\$ $a}$ 과 b {\displaystyle $a^{b}$ 가 $b$ 합리적으로 되도록 $a^{b}$ 비합리적인 $숫자$ a ${\$ displaystyle a}과 $a$ b ${\displaysty b}$ 이(가) 존재한다"를 고려해보자. 이 정리는 건설적인 증거와 비건설적인 증거를 모두 사용함으로써 증명될 수 있다.

도브 자르덴의 다음과 같은 1953년 증명서는 적어도 1970년 이후 비건설적 증명의 예로 널리 사용되어 왔다.^[4]^[5]

골레스타
339.비이성적 지수에 대한 비이성적 수의 힘이 합리적일 수 있다는 간단한 증거
${\sqrt {2}}^{\sqrt {2}}$ ${\sqrt {2}}^{\sqrt {2}}$ ${\$ 은 ${\sqrt {2}}^{\sqrt {2}}$ (는) 합리적이거나 비합리적이다. 만약 그것이 합리적이라면, 우리의 진술은 증명된다. 비합리적이라면 $({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2$ ( $({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2$ ) $({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2$ = 2 ${\displaystyle({\sqrt{2}}^{\sqrt{2}})^{\sqrt{2}}=2}}:}$ 는 우리의 진술을 증명한다 $({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2$ .
도브 자르덴 예루살렘

좀 더 자세한 내용:

${\sqrt {2}}$ ${\$ 는 ${\sqrt {2}}$ 비합리적이고 2는 합리적이라는 점을 상기하십시오. 숫자 $q={\sqrt {2}}^{\sqrt {2}}$ = $q={\sqrt {2}}^{\sqrt {2}}$ $q={\sqrt {2}}^{\sqrt {2}}$ ${\$ 합리적이거나 비합리적이다.
$q$ $q$ 이(가) 합리적이라면 $q$ 정리가 참이며, $a$ 및 $a$ $b$ $b$ 이 $b$ (가) ${\sqrt {2}}$ 모두 2 {\ $displaystyle$ {\ $sqrt{2$ }이다 ${\sqrt {2}}$
$q$ $q$ 이(가) 비합리적인 경우 $q$ ${\displaystyle$ a}이 $($ 가 $)$ ${\sqrt {2}}^{\sqrt {2}}$ {\ $displaystyle$ {2 $}}}$ 이고 b ${\sqrt {2}}^{\sqrt {2}}$ ${\$ $displaystyle b}$ 이 $b$ (가 $)$ ${\sqrt {2}}$ ${\$ {2 ${\sqrt {2}}$ 이므로 정리가 참이다.

\left\sqrt{2}}^{\sqrt{2}}={\sqrt{2}}}^{\sqrt{2}}}}}={\sqrt {{}}}}={\sqrt{2}=2}}

그 핵심에서, 이 증거는 비건설적인데, 이는 제외된 중간 법칙의 예인 "q가 이성적이거나 비이성적"이라는 문구에 의존하기 때문이다. 이는 건설적인 증거 내에서 유효하지 않다. 비건설적 증거는 a와 b를 구성하지 않는다; 그것은 단지 여러 가지 가능성(이 경우 상호 배타적인 두 가지 가능성)을 줄 뿐이고 그들 중 하나의 가능성(어떤 가능성)이 원하는 예를 제시해야 하는지는 보여주지 않는다.

밝혀진 바와 같이 ${\sqrt {2}}^{\sqrt {2}}$ ${\sqrt {2}}^{\sqrt {2}}$ ${\$ 는 $\sqrt{2}^{\sqrt2}$ 겔폰드-슈나이더 정리 때문에 불합리하지만, 이 사실은 비건설적 증명의 정확성과는 무관하다.

건설적 증거

비이성적인 힘의 비이성적인 힘에 대한 위의 정리의 건설적인 증거는 다음과 같은 실제적인 예를 제시할 것이다.

a={\sqrt {2}\\\nft b=\log _{2}9\\\\nft a^{b}=3\,

2의 제곱근은 비합리적이고, 3은 이성적이다. $\log _{2}9$ $\log _{2}9$ $\log _{2}9$ $[\displaystyle \log _{2$ }9 $}$ 도 비합리적인데 $\log _{2}9$ , 만일 그것이 $m \over n$ ${\displaystyle$ m $\over n}$ 과 $m \over n$ 같다면, 로그의 속성으로 보면 9는ⁿ 2와^m 같겠지만, 전자는 홀수이고 후자는 짝수인 것이다.

좀 더 실질적인 예는 그래프 부정리 입니다. 이 정리의 결과, 미성년자 중 어느 누구도 특정 유한 집합의 "강제입찰 미성년자"에 속하지 않는 경우에만 토러스 위에 그래프를 그릴 수 있다. 그러나 이 유한집단의 존재에 대한 증거는 건설적이지 않으며, 금지된 미성년자는 실제로 특정되지 않는다.^[6] 그들은 아직 알려지지 않았다.

브루베리안 백작샘플

건설 수학에서, 고전 수학에서와 같이 백범례를 줌으로써 진술이 반증될 수 있다. 그러나 이 진술이 비구축적이라는 것을 보여주기 위해 브루베리안 백작(bruwerian counterrex)을 주는 것도 가능하다.^[7] 이러한 종류의 예는 그 진술이 비건설적이라고 알려진 어떤 원칙을 내포하고 있음을 보여준다. 만약 어떤 진술이 건설적으로 증명할 수 없는 어떤 원칙을 내포한다는 것이 건설적으로 증명될 수 있다면, 그 진술 자체는 건설적으로 증명될 수 없다.

예를 들어, 특정 진술은 배제된 중간부의 법칙을 암시하는 것으로 보일 수 있다. 이러한 유형의 브루베리안 백작의 예는 디아코네스쿠의 정리인데, 이는 선택의 공리가 그러한 시스템에서 배제된 중간 법칙을 내포하고 있기 때문에 건설적인 세트 이론의 시스템에서는 선택의 완전한 공리가 비건설적이라는 것을 보여준다. 건설적 역수학 분야는 여러 원리가 배제된 중간 법칙의 여러 파편과 동등하다는 것을 보여줌으로써, 그들이 얼마나 비건설적인가라는 관점에서 여러 원리를 분류함으로써 이러한 생각을 더욱 발전시킨다.

브루워는 또한 "약한" counterexamples를 제공했다.^[8] 그러나 그러한 반증들은 진술을 반증하지 않는다; 그것들은 단지 현재 그 진술에 대한 건설적인 증거가 알려져 있지 않다는 것을 보여줄 뿐이다. 한 가지 약한 백례는 수학의 풀리지 않은 문제를 가져가는 것으로 시작된다. 골드바흐의 추측은 모든 자연수가 4보다 큰 것이 두 자리의 합인지를 묻는 것이다. 다음과 같이 합리적인 숫자의 순서 a(n)를 정의한다.^[9]

a(n)={\begin{cases}(1/2)^{n}&{\mbox{if every even natural number in the interval }}[4,n]{\mbox{ is the sum of two primes}},\\(1/2)^{k}&{\mbox{if }}k{\mbox{ is the least even natural number in the interval }}[4,n]{\mbox{ which is not the sum of two primes}}\end{cases}}

각 n에 대해 a(n)의 값은 철저한 검색에 의해 결정될 수 있으며, 따라서 a는 구성적으로 잘 정의된 시퀀스다. 더욱이 a는 일정한 수렴 속도를 갖는 코우치 수열이기 때문에 건설 수학에서 실수의 일반적인 처리에 따라 어떤 실수의 α로 수렴된다.

실수 α에 관한 몇 가지 사실들은 건설적으로 증명될 수 있다. 그러나, 건설 수학에서 단어의 다른 의미를 근거로, "α = 0 또는 α α 0 0"이라는 건설적인 증거가 있다면, 이는 골드바흐의 추측에 대한 건설적인 증거(전자의 경우)나 골드바흐의 추측이 거짓이라는 건설적인 증거(후자의 경우)가 있음을 의미할 것이다. 그러한 증거를 알 수 없기 때문에 인용된 진술 또한 알려진 건설적인 증거를 가지고 있어서는 안 된다. 그러나 골드바흐의 추측에 건설적인 증거(현재 우리가 그것을 알고 있는지는 알 수 없듯이)가 있을 가능성이 전적으로 있으며, 이 경우 인용된 진술은 비록 현재로서는 알 수 없는 것이기는 하지만 건설적인 증거도 가질 것이다. 약한 백반샘플의 주요 실제 용도는 문제의 "경직성"을 확인하는 것이다. 예를 들어, 방금 보여 준 백례본은 인용된 진술이 골드바흐의 추측만큼 "적어도 입증하기 어렵다"는 것을 보여준다. 이런 종류의 약한 백배는 종종 전지전능의 제한된 원리와 관련이 있다.

참고 항목

참조

^ Bridges, Douglas; Palmgren, Erik (2018), "Constructive Mathematics", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Summer 2018 ed.), Metaphysics Research Lab, Stanford University, retrieved 2019-10-25
^ McLarty, Colin (April 15, 2008). Circles disturbed: the interplay of mathematics and narrative — Chapter 4. Hilbert on Theology and Its Discontents The Origin Myth of Modern Mathematics. Doxiadēs, Apostolos K., 1953-, Mazur, Barry. Princeton: Princeton University Press. doi:10.1515/9781400842681.105. ISBN 9781400842681. OCLC 775873004. S2CID 170826113.
^ Hermann, Grete (1926). "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale: Unter Benutzung nachgelassener Sätze von K. Hentzelt". Mathematische Annalen (in German). 95 (1): 736–788. doi:10.1007/BF01206635. ISSN 0025-5831.
^ J. Roger Hindley, "비건설성의 본보기로서의 루트-2 증명", 2014년 9월, 전체 텍스트 2014-10-23 Wayback Machine
^ 도브 자르덴 "비합리적인 지수에 대한 비합리적인 수의 힘이 합리적일 수 있다는 간단한 증거", 스크립타 수학자 19:229 (1953)의 골동품 제 339호
^ Fellows, Michael R.; Langston, Michael A. (1988-06-01). "Nonconstructive tools for proving polynomial-time decidability" (PDF). Journal of the ACM. 35 (3): 727–739. doi:10.1145/44483.44491.
^ Mandelkern, Mark (1989). "Brouwerian Counterexamples". Mathematics Magazine. 62 (1): 3–27. doi:10.2307/2689939. ISSN 0025-570X. JSTOR 2689939.
^ A. S. 트로엘스트라, 직관주의의 원리, 수학 95, 1969, 페이지 102
^ 마크 반 아텐, 2015년, 스탠포드 수학 백과사전 "Weak Counterexamples"

추가 읽기

J. 프랭클린과 A. 다우드(2011) 수학 증명: 소개. Kew Books, ISBN 0-646-54509-4, ch. 4
Hardy, G. H. & Wright, E. M. (1979) 숫자 이론 소개 (제5판) 옥스퍼드 대학 출판부 ISBN 0-19-853171-0
앤 스저프 트로엘스트라와 더크 반 달렌(1988) "수학의 구성주의: 제1권" Exvier Science. ISBN 978-0-444-70506-8

외부 링크

스탠포드 철학 백과사전 마크 판 아텐의 약한 백과사전

[1] Bridges, Douglas; Palmgren, Erik (2018), "Constructive Mathematics", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Summer 2018 ed.), Metaphysics Research Lab, Stanford University, retrieved 2019-10-25

[2] McLarty, Colin (April 15, 2008). Circles disturbed: the interplay of mathematics and narrative — Chapter 4. Hilbert on Theology and Its Discontents The Origin Myth of Modern Mathematics. Doxiadēs, Apostolos K., 1953-, Mazur, Barry. Princeton: Princeton University Press. doi:10.1515/9781400842681.105. ISBN 9781400842681. OCLC 775873004. S2CID 170826113.

[3] Hermann, Grete (1926). "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale: Unter Benutzung nachgelassener Sätze von K. Hentzelt". Mathematische Annalen (in German). 95 (1): 736–788. doi:10.1007/BF01206635. ISSN 0025-5831.

[4] J. Roger Hindley, "비건설성의 본보기로서의 루트-2 증명", 2014년 9월, 전체 텍스트 2014-10-23 Wayback Machine

[5] 도브 자르덴 "비합리적인 지수에 대한 비합리적인 수의 힘이 합리적일 수 있다는 간단한 증거", 스크립타 수학자 19:229 (1953)의 골동품 제 339호

[6] Fellows, Michael R.; Langston, Michael A. (1988-06-01). "Nonconstructive tools for proving polynomial-time decidability" (PDF). Journal of the ACM. 35 (3): 727–739. doi:10.1145/44483.44491.

[7] Mandelkern, Mark (1989). "Brouwerian Counterexamples". Mathematics Magazine. 62 (1): 3–27. doi:10.2307/2689939. ISSN 0025-570X. JSTOR 2689939.

[8] A. S. 트로엘스트라, 직관주의의 원리, 수학 95, 1969, 페이지 102

[9] 마크 반 아텐, 2015년, 스탠포드 수학 백과사전 "Weak Counterexamples"

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search