|
|
| (같은 사용자의 중간 판 20개는 보이지 않습니다) |
| 1번째 줄: |
1번째 줄: |
| [[해석학]]과 [[위상수학]]에서, 하이네-보렐 정리(Heine-Borel theorem)는 유클리드 공간에서, 닫힌 유계 집합만이 컴팩트하다는 것을 말한다. 유클리드 공간을 자주 다루는 실해석학에서 기본적인 성질을 증명할 때 자주 사용된다.
| | =미분 갈루아 이론= |
|
| |
|
| == 진술 ==
| |
| 유클리드 공간의 부분집합 <math>K</math>에 대하여, 다음 두 조건이 동치이다:
| |
| : <math>K</math>가 닫혀 있고 유계이다.
| |
| : <math>K</math>가 [[컴팩트]]하다.
| |
|
| |
|
| == 증명 ==
| |
| 이하는 [[PMA]]에 소개된 증명을 따른다.
| |
|
| |
|
| === 보조정리 1 ===
| |
| <math>k</math> 차원 hyperrectangle은 컴팩트하다.
| |
|
| |
|
| ''Proof''. <math>I = \prod_{j=1}^k [a_j, b_j]</math>를 <math>k</math> 차원 hyperrectangle이라고 하고, 그 대각선 길이를 <math>\delta = \sqrt{\sum (b_j - a_j)^2 }</math>이라 하자. <math>\delta = \operatorname{diam}I</math>이므로 <math> I </math>의 두 점의 거리는 <math> \delta </math>보다 작거나 같다. 이제, 모순을 이끌어 내기 위해서 유한한 부분 덮개를 가지지 않는 어떤 <math> I </math>의 열린 덮개 <math> \{ G_\alpha \} </math>가 있다고 하자. 그러면 <math> I </math>의 각 변을 절반씩 나누어 만들어지는 <math> 2^k </math>개의 hyperrectangle 중에서 <math> \{G_\alpha\} </math>의 유한한 부분 덮개로 덮이지 않는 hyperrectangle이 하나 이상 존재하는데, 이 중 하나를 <math> I_1 </math>이라고 하자. 이런 식으로, <math> I_n </math>를 <math> 2^k</math> 개로 나눈 후 그 중 유한한 부분 덮개로 덮이지 않는 것을 <math> I_{n+1} </math>이라 하자. 그렇다면 집합들의 열 <math>\left < I_n \right></math>은 <math> I_n \supseteq I_{n+1} </math>이고, 이 중 어느 것도 <math> \{ G_\alpha \} </math>의 유한한 부분 덮개로 덮이지 않고, <math> I_n </math>의 임의의 두 점 사이 거리는 <math> 2^{-n} \delta </math>보다 작을 수밖에 없다. <math> I_n = \prod_{j=1}^k [a_{n, j}, b_{n, j}] </math>라 두고 <math>\mathbf x \in \prod _j [\sup_n a_{n, j}, \inf_n b_{n, j}] \ne \emptyset </math>라 하면 <math>\mathbf x\in \bigcap_{n=1}^\infty I_n</math>이다. <math> \{G_\alpha\} </math>는 열린 덮개이므로 어떤 <math> G_\alpha </math>에 포함되는 <math> \mathbf x </math>의 열린 <math> \epsilon </math>-ball이 있을 것이고, [[아르키메데스 성질]]에 의하여 <math> 2^{-n}\delta \le \epsilon </math>인 <math> n </math>이 존재한다. 그런데 이것은 <math> I_n \subset G_\alpha </math>를 뜻하는 것이므로 모순이다.
| | <!-- |
| | =람다 계산= |
| | {{학술}} |
| | [[분류:람다 계산]] |
| | {{넘겨주기 있음|람다 대수|람다 연산|람다 계산법|받침=예}} |
|
| |
|
| === 보조정리 2 === | | '''람다 계산'''(람다 대수, 람다 연산, 람다 계산법; {{llang|1=en|2=lambda calculus}})은 수리논리학과 이론 컴퓨터과학에서 사용하는 형식 체계(formal system)로, 함수의 정의, 적용, 재귀 등을 치환, 바인딩(binding) 등을 이용하여 추상화한다. [[알론조 처치]]가 1930년대 처음 발표하였다. |
| 컴팩트한 집합의 닫힌 부분집합은 컴팩트하다.
| |
|
| |
|
| ''Proof''. 컴팩트 집합 <math> K </math>의 (<math> X </math>에 대해) 닫힌 부분집합 <math> F </math>에 대하여, <math> \{ V_\alpha \} </math>를 <math> F </math>의 열린 덮개라 하자. 그러면 <math> \{V_\alpha \} \cup \{ F^\mathrm c \} </math>은 <math> K </math>의 열린 덮개를 이룬다. 그런데 <math> K</math>가 컴팩트하므로 <math> K </math>를 덮는 유한한 부분 덮개가 존재하고, 만약 그 부분 덮개에 <math> F^\mathrm c </math>가 있으면 제외시키자. 그러면 그것은 <math> \{ V_\alpha\}</math>의 부분 덮개가 된다. | | == 역사 == |
| | [[라이프니츠]]는 다음과 같은 생각을 가지고 있었다. |
| | * 모든 문제들이 서술될 수 있는 '보편적인(universal) 언어'를 만들어라. |
| | * 위의 언어로 서술된 모든 문제를 해결할 수 있는 방법을 찾아라. |
| | 첫 번째 것은, 만약 수학적인 문제만으로 제한한다면, [[러셀]]과 [[프레게]] 등에 의한 '집합론'의 공리적 서술로 인하여 꽤 만족스러운 결과를 얻었다고 할 수 있다. 하지만 두 번째 것은, 당연히 안 될 것 같지만, 그 증명이 명확하지 않았다. (이는 [[힐베르트]]에 의하여 ''Entscheidungsproblem''로 불리게 된다. 직역하면 ''결정 문제''이다.) 이것은 1930년대에 [[알론조 처치]]와 [[앨런 튜링]]에 의하여 각각 독립적으로 해결되는데, 그 답은 [[처치-튜링 명제]]를 가정할 때<ref>Church-Turing 명제는 다음을 말한다: 알고리듬으로 계산 가능함과 튜링 기계로의 계산 가능성은 동치이다. 이와 동치 명제로, 알고리듬으로 계산 가능함과 lambda calculus로 표현 가능함은 동치이다.)</ref> '''No'''이다. 튜링은 후에 이 두 방법으로의 ''계산 가능성'', 즉 계산 가능한 함수들의 모임이 서로 같음을 보였다. |
| | 람다 계산이 고안된 이후로, 람다 연산에 기반한 ''함수 프로그래밍 언어''(functional programming language)가 만들어졌다. ''Reduction machine''은 이런 functional language의 실행을 위하여 고안되었다. |
|
| |
|
| === 보조정리 3 === | | == 이해 == |
| <math> K </math>가 컴팩트하면 그 무한 부분집합은 <math> K </math>의 극한점을 하나 이상 가진다. (사실 그 역도 성립한다.)
| | Lambda calculus는 함수의 계산을 조금 더 간편하게 나타내는 표기이다. 간단히 말하면, 대수학에서 잊을 만하면 한 번씩 나오는 'evaluation'과 비슷한 개념이라고 할 수 있다. 예를 들어, <math>x</math>에 대한 식 <math>x^2 - \sin x</math>가 있다고 하자. 이는 다음과 같은 함수를 나타내기도 한다: |
| | | :<math>x \mapsto x^2 - \sin x.</math> |
| ''Proof''. <math> K </math>의 무한 부분집합 <math>E</math> 안에 <math>K</math>의 극한점이 하나도 없으면, <math>q\in K</math>의 근방 <math>V_q</math>와 <math>E</math>가 많아야 하나가 되게 할 수 있다. 그런데 이 <math>V_q</math>는 <math>E</math>를 덮지 못하므로 <math>K</math> 역시 덮지 못하고, 이는 <math>K</math>의 컴팩트성에 모순이다.
| | 이 함수를 lambda calculus에서는 |
| | | :<math>\lambda x. x^2 - \sin x</math> |
| === 보조정리 4 ===
| | 로 나타낸다.<ref><math>\lambda x[x \mapsto x^2 - \sin x]</math>로 나타내기도 한다.</ref> 그리고 이 함수의 <math>x=a</math>에서의 함숫값을 |
| <math>\mathbb R^k</math>의 부분집합 <math> K </math>에 대하여, 임의의 <math>K</math>의 무한 부분집합이 <math> K </math>의 극한점을 하나 이상 가지면 <math>K</math>는 닫혀 있고 유계이다. | | :<math>(\lambda x. x^2 - \sin x)a</math> |
| | | 로 나타낸다. 예를 들어 <math>(\lambda x.x^2 - \sin x)\pi = \pi^2 - \sin \pi = \pi^2</math>이다. 이 λ-연산자는 |
| ''Proof''. 만약 <math>K</math>가 유계가 아니라고 가정하면 <math>K</math>에서 <math>|\mathbf x_ n | > n</math>인 원소들을 가져와 점렬을 만들 수 있고, <math>\{\mathbf x_n\}_{n\in\mathbb N}</math>은 극한점을 가지지 않으므로 모순이다.
| | --> |
| | |
| 만약 <math>K</math>가 닫혀 있지 않다고 가정하면, <math>\mathbf x^* \in K' \setminus K</math>가 존재한다. <math>\mathbf x_0</math>가 극점이므로 <math>| \mathbf x_n - \mathbf x^* | < 1/n</math>인 <math>\left< \mathbf x_n\right></math>가 존재하고, <math>\{\mathbf x_n \}</math>는 무한집합이며 <math>\mathbf x^*</math>만을 극한점으로 갖는다. 그런데 이 집합은 <math>K</math>의 극한점을 포함하지 않으므로 모순이다.
| |
| | |
| === 본 정리의 증명 ===
| |
| # <math>K</math>가 닫혀 있고 유계이면 <math>K</math>는 컴팩트하다.
| |
| : <math>K</math>가 유계이면 <math>K \subseteq I</math>인 hyperrectangle <math>I</math>가 존재하고, <math>K</math>는 컴팩트한 <math>I</math>(보조정리 1)의 닫힌 부분집합이므로 컴팩트하다(보조정리 2).
| |
| # <math>K</math>가 컴팩트하면 닫혀 있고 유계이다.
| |
| : 보조정리 3과 보조정리 4에 의하여 증명된다.
| |