测试逻辑[番外] 超限归纳在拓扑上的一个应用

此文作讲解的不是数理逻辑, 而是测试逻辑中一个重要定理---超限归纳在拓扑的一个基本定理上的应用(其实还顺带介绍了不少拓扑). 当然, 在本篇的之后可能会讲到佐恩引理, 那么这些用超限归纳解题的过程都能被简化, 这也是大多数教科书所用的做法. 不过归根结底本文目的是让读者见识到数理逻辑并非是无用的"玩具"; 相反, 超限归纳在较为初等的学科, 如拓扑学上也能大显身手.

另外由于本文是番外, 笔者将使用他比较熟悉的英文以及排版较为简单的markdown进行写作.

1 Preliminary

1.1 A topological space is a set S equipped with a \tau\subset P(S) such that

\emptyset\in\tau, S\in\tau;
\forall x,y\in\tau(x\cap y\in\tau);
\forall A\subset\tau(\cup A\in\tau).

The elements of \tau are called open sets. On the contrary, we call X\subset S a closed set iff S-X\in\tau. Note that it's easy to prove the intersection of finitely many open sets is still an open set; the union of finitely many closed sets is a closed set, and the intersection of closed sets is a closed set.

1.2 A normal space is a topological space S such that for any two disjoint closed sets A,B, there two disjoint open sets U,V such that A\subset U, B\subset V.

1.3 For an X\subset S, we define the closure of X as

\text{Cl}(X)=\cap\lbrace A:A\text{ is closed and }X\subset A\rbrace

1.4 A set of A\subset\tau is called an open covering of S iff \cup A=S. We often denote A as \lbrace U_i\rbrace_{i\in I}.

1.5 A locally finite covering of S is a covering \lbrace U_i\rbrace_{i\in I} such that for every x\in S, there is an open set X such that X only intersects with finite U_i. In other words, there is a finite J\subset I such that

X\cap\left(\mathop{\cup}\limits_{i\in I-J}U_i\right)=\emptyset

2 An important result in normal spaces

2.1 For any non-empty open set U in a normal space S and a closed set A\subset U, we can find an open set V such that A\subset V\subset\text{Cl}(V)\subset U.

Proof Since U is open, S-U is closed. As A\subset U, A and S-U are disjoint. By normality, there are disjoint open V,W such that A\subset V and S-U \subset W. As V, W are disjoint, V\subset S-W\subset U. Now since W is open, S-W is closed, and V\subset S-W, so \text{Cl}(V)\subset S-W\subset U.

3 An application of transfinite induction---Shrinking Lemma

Now we present a lemma crucial to prove the magical existence of partition of unity---shrinking lemma.

3.1(Shrinking Lemma) For a locally-finite covering \lbrace U_i\rbrace_{i\in I} of a normal space S, there's a covering \lbrace V_i\rbrace_{i\in I} such that \forall i\in I(V_i\subset\text{Cl}(V_i)\sub U_i).

Before diving into this lemma's proof, we firstly investigate the finite situation.

Let's start from the most simple situation: S is covered by two open sets: U_1,U_2. Then we can extend U_1-U_2, a closed subset of U_1, to some open V_1 such that \text{Cl}(V_1)\sub U_1 and V_1\cup U_2=S.

For a finite open covering \lbrace U_1,...,U_n\rbrace, we take U_1 and \mathop{\cup}\limits_{i=2}^n U_i as a binary covering. In this way, we can find V_1\subset\text{Cl}(V_1)\subset U_1, and the finite covering becomes \lbrace V_1,U_2,...,U_n\rbrace. Then we take U_2 and V_1\cup\left(\mathop{\cup}\limits_{i=3}^n U_i\right) as a binary covering, and we can similarly find V_2. After finite steps, we can turn the initial covering into \lbrace V_1,...,V_n\rbrace satisfying the conditions.

\lbrace V_1,...,V_n\rbrace is a covering because we check this after every step turing U_i into V_i. However, when I is infinite, this kind of "checking" won't work. Yet we can still inherit the idea of induction and utilize a powerful tool against infinity---transfinite induction.

Proof of 3.1 Admitting axiom of choice, we take a well ordering of I. Suppose \text{Ord}(I)=\gamma, we prove that there is a sequence (V_0,V_1,...) such that for all \alpha\le\gamma

(\cup\lbrace V_\beta:\beta<\alpha\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\alpha\rbrace)=S

by induction on \alpha.

Firstly when \alpha=0, the proposition is immediate as \cup\lbrace U_\beta:\beta\ge0\rbrace is just the initial covering.

For a successor ordinal \alpha+1, we prove that the proposition holds if it holds for \alpha. To be particular, when

(\cup\lbrace V_\beta:\beta<\alpha\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\alpha\rbrace)=S

we want to prove

(\cup\lbrace V_\beta:\beta<\alpha\rbrace)\cup V_{\alpha}\cup(\cup\lbrace U_\beta:\beta\ge\alpha+1\rbrace)=S

To prove this, we just imitate what we did in finite situations: take U_\alpha and (\cup\lbrace V_\beta:\beta<\alpha\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\alpha+1\rbrace) as a binary covering, then there's a V_{\alpha}\sub\text{Cl}(V_\alpha)\sub U_\alpha such that

(\cup\lbrace V_\beta:\beta<\alpha\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\alpha+1\rbrace)\cup V_{\alpha}=S

For a non-zero limit ordinal \alpha, we prove that when for all \delta<\alpha

(\cup\lbrace V_\beta:\beta<\delta\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\delta\rbrace)=S

the following holds:

(\cup\lbrace V_\beta:\beta<\alpha\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\alpha\rbrace)=S

If not, take an x\in S-(\cup\lbrace V_\beta:\beta<\alpha\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\alpha\rbrace), then we have \forall\beta<\alpha(x\notin V_\beta) and \forall\beta\ge\alpha(x\notin U_\beta).

By locally finiteness, take an open O_x\ni x such that O_x intersects with finitely many U_i. Now if x is contained in some U_i, U_i must intersects with O_x, so x is only contained in finitely many U_i, namely \lbrace U_{\delta_1},...,U_{\delta_n}\rbrace. By the above argument, \forall 1\le i\le n(\delta_i<\alpha). Suppose \delta=\max\limits_{1\le i\le n}\lbrace\delta_i\rbrace, as \alpha is a non-zero limit ordinal, \delta+1<\alpha, and the following assumed proposition leads to a contradiction:

(\cup\lbrace V_\beta:\beta<\delta+1\rbrace)\cup(\cup\lbrace U_\beta:\beta\ge\delta+1\rbrace)=S

Since \forall\beta<\alpha(x\notin V_\beta), x\notin\cup\lbrace V_\beta:\beta<\delta+1\rbrace, so x\in \cup\lbrace U_\beta:\beta\ge\delta+1\rbrace. Yet \delta is the largest ordinal such that U_\delta\ni x, which is contradictory.