계산 가능한 분석에서 "연속성"이라는 용어는 무엇입니까?

Question

배경

나는 Haskell에서 임의의 실수를 나타내는 데이터 유형을 구현한 적이 있습니다.코시 수열이 수렴되도록 하여 모든 실수에 라벨을 붙입니다.그러면 $\mathbb{R}$ 일반적인 토폴로지에 있어야 합니다.덧셈, 뺄셈, 곱셈, 나눗셈도 구현했습니다.

그러나 선생님은 “이건 좋은 생각이 아닌 것 같다.여기서는 비교를 결정할 수 없으므로 그다지 실용적이지 않습니다.특히 0으로 나누는 것이 무한루프에 빠지게 하는 것은 보기에 좋지 않습니다."

그래서 내 데이터 유형을 확장하고 싶었습니다. $\mathbb{Q}$.동등 비교 이후 $\mathbb{Q}$ 결정 가능하다, $\mathbb{Q}$ 개별 토폴로지에 있습니다.이는 토폴로지를 의미합니다. $\mathbb{R}$ 의 개별 토폴로지보다 더 정밀해야 합니다. $\mathbb{Q}$.

하지만 그런 데이터 유형을 구현할 수 있다고 해도 비실용적이라는 것을 알게 된 것 같습니다.

증명, 1단계

허락하다 $\mathbb{R}$ 보다 더 정밀하다 $\mathbb{Q}$ 개별 토폴로지에서.그 다음에 $\{0\}$ 다음에서 영업 중입니다. $\mathbb{R}$.추정하다 $+ :\mathbb{R}^2 → \mathbb{R}$ 연속적이다.그 다음에 $\{(x,-x):x \in \mathbb{R}\}$ 다음에서 영업 중입니다. $\mathbb{R}^2$.부터 $\mathbb{R}^2$ 제품 토폴로지에 있고, $\{(x,-x)\}$ 의 기본 요소이다 $\mathbb{R}^2$ 모든 $x \in \mathbb{R}$.그것은 다음과 같습니다 $\{x\}$ 의 기본 요소이다 $\mathbb{R}$ 모든 $x \in \mathbb{R}$.그건, $\mathbb{R}$ 개별 토폴로지에 있습니다.

증명, 2단계

부터 $\mathbb{R}$ 개별 토폴로지에 있으며, $\mathbb{R}$ 계산적으로 동등함을 비교할 수 있습니다.이는 모순이므로 $+$ 연속적이지 않고, 따라서 계산할 수 없습니다.

질문

나를 괴롭히는 것은 굵은 글씨입니다.모든 계산 가능한 함수는 연속적이라는 것은 잘 알려져 있습니다(Weihrauch 2000, p.6).연속성의 분석적 정의와 위상학적 정의는 유클리드 공간과의 함수에서 일치하지만, $\mathbb{R}$ 위의 공간은 유클리드 공간이 아닙니다.그래서 내 증명이 맞는지 확신할 수 없습니다.계산 가능한 분석에서 "연속성"의 정의는 무엇입니까?

Answer 1

연속성의 정의가 무엇인지에 대해 사람들마다 서로 다른 견해가 있지만, 제가 보기에는 연속성을 일부 오라클과 관련된 계산 가능성으로 정의해야 합니다.예를 들어:

정의:기능 $f :\mathbf{X} o \mathbf{Y}$ 계산 가능한 부분 함수가 있는 경우 연속입니다. $F :\subseteq \mathbf{X} imes \mathbb{N}^\mathbb{N} o \mathbf{Y}$ 그리고 일부 $p \in \mathbb{N}^\mathbb{N}$ 그렇게 $f(x) = F(x,p)$.

따라서 공간을 처리하는 데 있어 가장 원시적인 개념은 공간을 위해 어떤 표현을 사용하는지이며, 이는 계산 가능성이라는 개념을 낳고, 여기에서 연속성이라는 개념을 얻습니다.

지금까지 연속성의 정의는 토폴로지의 연속성과 관련이 없어 보이며 왜 그 용어가 선택되었는지 궁금할 수 있습니다.한 가지 이유는 우리가 일반적으로 사용하는 것입니다. 허용되는 표현, 이는 계산 가능한 분석 정의에서 연속적인 이들 사이의 함수가 정확히 위상학적 의미에서 연속적인 함수라는 특성을 갖습니다.

당사가 허용 가능한 진술을 갖고 있는 경우 $\delta :\subseteq \Sigma^\mathbb{N} o \mathbf{X}$, 우리는 토폴로지를 얻습니다 $\mathbf{X}$ 최종 토폴로지로 $\델타$, 즉.세트 $U \subseteq \mathbf{X}$ 세트가 있으면 열려 있습니다 $W$ 그런 유한한 단어의 $\delta^{-1}(U) = \operatorname{dom}(\delta) \cap \bigcup_{w \in W} w\Sigma^\mathbb{N}$.Matthias Schröder는 허용 가능한 표현을 갖는 위상 공간이 정확히 다음과 같다는 것을 보여주었습니다. $T_0$ 가산 기반 공간의 몫.

이제 천천히 질문의 시작점으로 돌아가서 실제에서 이산 토폴로지를 사용하는 것을 방해하는 것은 무엇입니까?우리가 그렇게 할 수 없는 이유는 모든 가산 기반 공간이 분리 가능하기 때문입니다. 즉, (가산 가능한) 조밀한 시퀀스가 ​​있기 때문입니다.몫을 취하면 분리가 가능하므로 표현과 관련된 모든 토폴로지는 반드시 분리 가능합니다.이산 공간은 셀 수 있으면 분리 가능하므로 실수에 대한 이산 위상을 얻을 수 없습니다.

허용 가능한 표현을 얻을 수 있는 방법이 있습니다. $\mathbb{R}$ 그게 만든다 $\mathbb{Q}$ 이산적인 부분 공간(본질적으로 $\mathbb{R}$ ~처럼 $\mathbb{N}^{*} \cup \mathbb{N}^\mathbb{N}$), 그러나 질문에서 주장한 것처럼 덧셈을 계산할 수 없게 만듭니다(그리고 전반적으로 우리가 원하는 실제와 거의 유사하지 않습니다).

참고로 실수로 나누려고 하면 인식하지 못한 채 막히는 것을 피할 수 없습니다. $0$ 실수로 선형 대수학을 수행하려는 경우 중요한 장애물입니다.

참고자료:

피터 콜린스:동적 시스템에 대한 애플리케이션을 사용한 계산 가능한 분석.수학.구조체.계산.과학.30(2):173-233 (2020)

마르틴 회첼 에스카르도:합성 토폴로지:데이터 유형과 고전 공간의.전자.노트 이론.계산.과학.87:21-156 (2004)

키하라 타카유키, 아르노 파울리 0으로 나누기 - 얼마나 나쁜가요?.MFCS 2016:58:1-58:14

아르노 파울리: 재현공간 이론의 위상학적 측면에 대하여.계산 가능성 5(2):159-180 (2016) arXiv

마티아스 슈뢰더:허용 가능성 연장.이론.계산.과학.284(2):519-538 (2002)

Answer 2

Arno의 답변은 매우 유용한 백그라운드 읽기 자료를 제공합니다. $ \ mathbb {r} $ 에 대한 구체적인 질문을 해결하고 싶습니다.

Peter Hertling에 의해 첫 번째로 결과를 회상하겠습니다. 효과적으로 범주화 된 실수 구조 ( pdf 여기서. 실수. $ \ mathbb {r} $ , 즉, 실제를 나타내는 데이터 구조를 나타내는 데이터 구조가 있다고 가정합니다.

• $ 0 $ 및 $ 1 $ 은 $ \ mathbb {r} $ ,
• 필드 조작 $ + $ , $ - $ , $ \ times $ 및 $ / $ 은 계산 가능합니다 (물론 제로는 정의되지 않은 곳에서 부서가 정의되지 않았습니다)
• 리미트 운영자는 $ (x_n) _n $ 가 빠릅니다. -Container "> $ | x_n - x_m | \ leq 2 ^ {- \ min (m, n)} $ ).
• 엄격한 순서 $ <$ 은 semimecidable

위의 조건은 실제가 진짜의 평소 비치화의 계산 가능한 버전 (아르시미디어 공경이 밖에서 밖에서도 보유하고 있음)을 꽤 많이 계산할 수있는 Computable Cauchy 주문 필드 여야합니다.

다음은 다음과 같습니다.

1. $ \ mathbb {r} $ 은 표준 유클리드 토폴로지
입니다.
2. equality는 undecidable이거나, 동등하게, 0에 대한 testng는 미확인 가능성이 없다.
3. 두 개의 그러한 구조는 계산 가능하게 isomorphic이며

이들은 불가피한 사실입니다. 선생님이 아마도 평등이 불행하지 않거나 0으로 나누는 것이 오류를보고해야한다고 생각할 수도 있지만 은 실제의 계산 가능한 구조를 유지하려는 경우 을 준비하는 것이 불가능합니다.

....

구현과 관련하여 : Cauchy Sequence 과 함께 정보와 함께 정보와 함께 실제를 나타내는 것이 중요합니다. 네가 그랬 으면 좋겠어.