0%

分析学笔记(1)数理逻辑与集合论

初学数学分析,很多概念理解的并不深刻,这份笔记只是初学阶段的一点整理。本篇为一些在数学分析中涉及的基本理论,包括集合论的基本概念与ZFC公理、数理逻辑基础,目的是为后续内容做好铺垫。

\[\require{mathtools}\]

一、数理逻辑基础

这一块内容是为了整个笔记的完整性,以重述概念为主。

\(\S1.1\) 命题逻辑

Definition 1.1.1 命题是一个非真即假的陈述句。

通过逻辑连接符\(\neg,\vee,\wedge,\to,\leftrightarrow\)​​​,可以利用较简单的命题来构造复合命题,即

Definition 1.1.2 命题公式按如下规则生成:
(1) 命题变元是命题公式;
(2)\(P\)是命题公式,则\(\neg P\)是命题公式;
(3)\(P,Q\)​​是命题公式,则\(P\wedge Q,P\vee Q,P\to Q,P\leftrightarrow Q\)​​是命题公式;
(4) 当且仅当有限次应用1-3条规则得到的包含命题变元,逻辑联结词和圆括号的有意义的符号串是命题公式。

一个非常简单的递归定义,看上去还是非常清晰的。

Definition 1.1.3\(A\to B\)是一个永真式,则称其为永真蕴含式,记作\(A\Rightarrow B\)

特殊地,若命题\(A\)​蕴涵着某个假命题,则\(A\)​为假,这即是反证法的思想:为了证明\(A\)为假,先假设\(A\)是真,再证明\(A\)蕴涵着某个一定为假的命题。

\(\S1.2\) 变量与量词

Definition 1.2.1 变量是表示某种特定类型的数学对象的符号,称未被指定为某个具体对象的变量为自由变量,否则称之为约束变量。

Definition 1.2.2\(P(x)\)是一个关于自由变量\(x\)​的命题。全称量词\(\forall\)读作“对任意的”,即“\(\forall x\in X\colon P(x)\)​为真”与“\(P(x)\)对所有的\(x\in X\)均为真”等价。类似地,存在量词\(\exists\)​读作“存在”。

多个量词可以嵌套在一起,否定一个命题会使得该命题中的全称量词变为存在量词,存在量词变为全程量词。

\(\S1.3\) 相等

相等遵守以下四条相等公理:

Axiom 1.3.1(自反公理) 给定任意的对象\(x\)​,有\(x=x\)​。

Axiom 1.3.2(对称公理) 给定任意两个同类型的对象\(x,y\)​,若\(x=y\)​,则\(y=x\)​。

Axiom 1.3.3(传递公理) 给定任意三个同类型的对象\(x,y,z\)​​,若\(x=y\)​​且\(y=z\)​,则\(x=z\)​。

Axiom 1.3.4(替换公理) 给定任意两个同类型的对象\(x,y\)​​,若\(x=y\)​​,则对任意一个函数或运算\(f\)​​,有\(f(x)=f(y)\)​​,对任意一个关于\(x\)​​的性质\(P(x)\)​​,\(P(x)\)​​和\(P(y)\)​是等价的命题。

前三条公理非常显然,用下文提到的一个概念来描述即是,这三条公理断言了相等是一个等价关系。

而替换公理则说明了这些符号只是一个泛指的变量,例如在模3的意义下,\(1\)等于\(4\),对于函数\(f(x)=x+2\),就有\(1+2\)等于\(4+2\)

数理逻辑暂且就只介绍这些粗浅的概念了,接下来引入一些集合论的概念。

二、ZFC集合论

下文不对公理和公理模式做区分。

\(\S2.1\) 朴素集合论

Definition 2.1.1(非正式) 一个集合是一些确定的对象无序的放在一起的整体,同时朴素集合论中的空集、子集和集合运算等概念就不再赘述了。

同时,为了更好的描述无限集合,朴素集合论承认概括公理:

Axiom 2.1.1(概括公理)(危险) 假设\(\forall x\),存在关于\(x\)的性质\(P(x)\),则存在一个集合\(\{x\colon P(x)\)为真\(\}\),使得\(\forall y\)\(y\in\{x\colon p(x)\)为真\(\}\iff P(y)\)为真。

概括公理实则是在断言每个性质都对应一个集合,由此我们可以简单地将满足某些性质的元素都归到一个集合中。

很可惜,朴素集合论遇上了麻烦。在这之前,我想先插入一些题外话。个人认为,“反例”在学习分析时,特别对初学者而言,是加深理解的一个利器。典型的例如Weierstrass函数,对分析学产生了重要的影响。而Russell即是构造了一个在概括公理下的“反例”,冲击了概括公理。

Russell悖论\(P(x)\iff\)​​"\(x\)​​是一个集合,并且\(x\notin x\)​​",定义\(A\coloneqq \{x\colon P(x)\)​为真\(\}\)​​。假如\(A\notin A\)​​​,则\(P(A)\)​为真,从而\(A\in A\)​;假如\(A\in A\)​,则\(P(A)\)​为假,从而\(A\notin A\)。因此,无论哪种情况,都有\(A\in A\)\(A\notin A\)​​​。

产生这个悖论的原因在于概括公理允许过大的集合存在,因此需要引入一系列公理限制集合的构造。下面介绍ZFC公理集合论。(再插句题外话:为什么朴素集合论没有那么多的公理呢?因为在假定概括公理为真的情况下,可以轻松推出下文许多公理,很可惜,这么美好的事情是不现实的。)

\(\S2.2\) ZFC集合论

先从定义集合的相等开始:

Axiom 2.2.1(外延公理) \(\forall x(x\in A\leftrightarrow x\in B)\leftrightarrow A=B\)

即称两个集合\(A,B\)是相等的,当且仅当\(A\)\(B\)中的元素相同。

Remark 这个公理说明集合内的元素是集合唯一的性质。

Axiom 2.2.2(分类公理) \(\forall A\exists B\forall x(x\in B\leftrightarrow x\in A\wedge P(x))\)。​​​

即设A是一个集合,\(P(x)\)​​是\(A\)​​中元素的一个性质,则存在集合\(\{x\in A\colon P(x)\}\)​为所有\(A\)中具有性质\(P\)的元素。

分类公理即对概括公理的弱化,假如集合真的存在(注意,目前我们还不能断定真的存在集合),我们已经能构造出空集了。

Proposition 2.2.1 若存在一个集合,则唯一存在没有任何元素的集合。

  • Proof​​ 假设存在一个集合\(A\)​,令\(P(x)\)​为\(x\neq x\)​​,则由分类公理即可得存在性,再有外延公理可得唯一性。\(\Box\)

外延公理已经定义了集合的相等,回想下\(\S1.3\)​中关于相等的替换公理,我们来验证下替换公理适用于分类。

  • Proof 假设替换公理不适应,即存在\(A=A'\),有\(\{x\in A\colon P(x)\}\neq\{x\in A'\colon P(x)\}\)​。记两个集合分别为\(B,B'\),不妨设\(B\)中存在元素\(x\),有\(x\notin B'\)
    \(x\in B\)可知\(x\in A\)​​​​。又由外延公理,\(x\in A'\)​​​​。假设\(P(x)\)​​​​为真,则\(x\in B'\)​​​​,否则有\(x \notin B'\)​​​​,均与上述矛盾,从而替换公理适用于分类。\(\Box\)​​​

现在集合还很匮乏,为了构造更多可用的集合,配对“公理”被引入了。

Axiom 2.2.3(配对"公理") \(\forall A\forall B\exists C\forall x(x\in C\leftrightarrow x=a\vee x=b)\)

即对对象\(A,B\)​,存在集合\(C=\{A,B\}\)​​。

Axiom 2.2.4(并集公理) \(\forall A\exists B\forall x(x\in B\leftrightarrow\exists y(x\in y\wedge y\in A))\)。​

即对\(A\),存在一个集合\(B\)\(A\)中元素的元素都在\(B\)中且\(B\)中元素都在\(A\)的元素中,并引入记号\(B=\bigcup A\)

集合的交也可被类似定义。

Definition 2.2.1 设集合\(A,B\)满足\(A\)的任意元素\(\alpha\)都与\(B\)的一个子集对应,则记该子集为\(B_\alpha\),用\(\{B_\alpha\}\)表示以\(B_\alpha\)为元素的集合,称为一族集。所有对应的子集的并可记作\(\bigcup_{\alpha\in A}B_\alpha\)

虽然现在还没有定义函数,但可以暂用一下以前的知识。为了考察定义域为\(X\),值域为\(Y\)的所有函数,我们需要考虑\(X\)的所有子集和\(Y\)的所有子集,因此引入了幂集公理。

Axiom 2.2.5(幂集公理) \(\forall A\exists B\forall x(x\in B\leftrightarrow x\subseteq A)\)

即对集合\(A\),存在集合\(B\),其元素是\(A\)的所有子集,我们将\(B\)记作\(2^A\)

注意,上述所有的定理都是在假设有集合存在的情况下,目前我们还不能保证确实存在有集合。先引入两个定义:

Definition 2.2.2 对任意集合\(A\)\(A^+\coloneqq A\cup\{A\}\)称为\(A\)的后继集。

Definition 2.2.3 \(Inf(x)\leftrightarrow\emptyset\in x\wedge\forall u(u\in x\to u^+\in x)\),将性质\(Inf\)为真的集合称为归纳集。

对于一个集合,可以进行的一个最基本的操作是取出集合中的每一个元素,按某种方式将每个元素都转换成一个新对象,并最好能将新的对象都放在一个集合里。为此,引入替代公理。

接下来引入无穷公理来说明集合存在。

Axiom 2.2.6(无穷公理) \(\exists A(\exists \emptyset(\emptyset\in A)\wedge\forall x(x\in A\to x^+\in A))\)。​

即空集是存在的,且存在归纳集\(A\),包括某个存在的集合和任何其中的集合的后继集。

无穷公理先说明空集存在,再说明无穷集存在。

这时已经确保了有集合存在,因此空集也被唯一确定了,记其为\(\emptyset\),把这个结论称为空集定理。

Theorem 2.2.1(空集定理) \(\exists! \emptyset\forall x(x\notin\emptyset)\)。​

Axiom 2.2.7(替代公理) \(\forall A(\forall x\in A( \forall y_1\forall y_2(P(x,y_1)\wedge P(x,y_2)\to y_1=y_2)))\to\exists B\forall y(y\in B\leftrightarrow\exists x(x\in A\wedge P(x,y)))\)。​​​

将替代公理用自然语言表达不会这么繁琐:

\(A\)是一个集合,对任意\(x\in A\)和任意一个对象\(y\),假设存在一个关于\(x,y\)的命题 \(P(x,y)\)使得对任意\(x\in A\),至多有一个\(y\)使得\(P(x,y)\)为真,则存在一个集合\(\{y\colon P(x,y)\)对某个\(x\in A\)为真\(\}\)​。

事实上,若我们将“存在唯一的没有任何元素的集合”当作一条公理,则我们可以证明替代公理蕴含分类公理。

Theorem 2.2.2 若承认空集公理,则空集公理和替代公理蕴含分类公理。

  • Proof\(A\)是一个集合,\(P(x)\)\(A\)​中元素的一个性质。
    \(1)\)​ 若\(A\)​中存在一个元素使得\(P(x)\)为真,任意取定一个\(A\)中使得\(P(x)\)为真的元素\(x_0\)\(x,y\)都是\(A\)中元素,令\(\phi(x,y)\)定义如下:若\(P(x)\)为假,则只有\(y=x_0\)\(\phi(x,y)\)​为真;若\(P(x)\)为真,则只有\(y=x\)\(\phi(x,y)\)为真。
    显然\(\phi\)满足替代公理中的条件,而替代公理对两个相等的集合也成立,因此存在集合\(\{y\colon \phi(x,y)\)对某个\(x\in A\)为真\(\}=\{x\in A\colon P(x)\)为真\(\}\)
    (题外话:我看见很多证明由此就说明了替代公理蕴含分类公理,但事实上从我\(1)\)中证明的第一句话的表述就能看出,这没有考虑空集的情况。)
    \(2)\)\(A\)中不存在元素使得\(P(x)\)​为真,则由空集公理,\(\emptyset\)​即是符合条件的集合。 \(\Box\)

另外前文谈及配对“公理”时我对公理二字一直加了引号,因为由替代公理可以轻易推出它。

Theorem 2.2.3 替代公理可以推出配对公理。

  • Proof 对任意对象\(A,B\),由上述定理,\(\emptyset,\emptyset\cup\{\emptyset\}\)是两个集合,不妨记为\(0,1\)。取\(C=\{0,1\}\),定义\(P(x,y)\)\(C\)的一个命题,只有\(P(0,A),P(1,B)\)为真。则对\(C\)使用替代公理,即可得存在集合\(D=\{A,B\}\)\(\Box\)

Axiom 2.2.8(正则公理) \(\forall A(A\neq\emptyset\to\exists(x\in A\wedge\neg\exists y(y\in x\wedge y\in A)))\)。​

即若\(A\)是一个非空集合,则\(A\)中至少存在一个元素\(x\)满足\(x\)不是集合或\(x\)\(A\)不相交。

这个公理主要是使得集合成为良基集合,不多做讨论。

上述的公理构成了ZF集合论系统,而ZFC中的C指得是选择公理。

Axiom 2.2.9(选择公理) \(\forall A(\emptyset\notin A\to\exists C\forall B(B\in A\to\exists !x(x\in B\cap C)))\)。​​​

上述所有公理构成了ZFC集合论系统。

三、函数

为了定义函数,需要先引入Cartesian积。

\(\S3.1\)​ Cartesian积

Definition 3.1.1 对任意的对象\(x,y\),称\((x,y)\coloneqq \{\{x\},\{x,y\}\}\)为有序对。

由配对公理,有序对的存在性已经明确了。不用在意这里有序对为什么定义的这么反常,这只是一个“脚手架”。

Definition 3.1.2 对集合\(X,Y\)\(X\times Y\coloneqq \{(x,y)\colon x\in X\wedge y\in Y\}\)称为\(X,Y\)的Cartesian积。

注意,我们还不能确定这是一个集合。

Theorem 3.1.1 Cartesian积是一个集合。

  • Proof​​ 任取\(x_0\in X\)​​,对任意\(y\in Y\)​和有序对,令命题\(P(y,(x_0,y'))\)为真当且仅当\(y=y'\),显然\(P\)满足替代公理的条件,从而有集合\(A_{x_0}=\{(x_0,y)\colon y\in Y\}\)。由并集公理,\(B=\bigcup_{x\in X}A_x\)是一个集合。
    易验证\(B=X\times Y\)\(\Box\)

由归纳法易得,\(n\)​元Cartesian积也是集合。

\(\S3.2\)​​​ 函数(映射)

Definition 3.2.1\(A,B\)为集合,称集合\(R\)为从\(A\)\(B\)的二元关系,当且仅当\(R\subseteq A\times B\)。若\((a,b)\in R\),则记为\(aRb\)

Definition 3.2.2 对集合\(X,Y\),若\(X\)\(Y\)的二元关系\(f\)满足\(\forall x\in X\exists !y\in Y((x,y)\in f)\),则称\(f\)为函数,记作\(f\colon X\to Y\)\(f(x)\coloneqq y\iff(x,y)\in f\)\(X\)称为\(f\)的定义域,\(Y\)称为\(f\)的陪域,\(\text{Im}f\coloneqq \{y\in Y\colon \exists x\in X(y=f(x))\}\)称为\(f\)的值域。

Definition 3.2.3 两个具有相同定义域的函数\(f\colon X\to Y,g\colon X\to Y\)​​​相等,当且仅当\(\forall x\in X,f(x)=g(x)\)​​​,记作\(f=g\)​​​​。

Definition 3.2.4\(f\colon X\to Y,g\colon Y\to Z\)​,则定义\(g,f\)​的复合\(g\circ f\colon X\to Z\)​为一个函数,满足\((g\circ f)(x)=g(f(x))\)​。

Definition 3.2.5 对函数\(f\colon X\to Y\)​​,若满足\(f(x)=f(x')\Rightarrow x=x'\)​​则称\(f\)​​是单射;若满足\(\text{Im}f=Y\)​​则称\(f\)​​​是满射;若\(f\)​​既是单射又是满射则称\(f\)​​是双射。

Definition 3.2.6 若函数\(f\colon X\to Y\)​​是双射,则\(\forall y\in Y\)​​,恰好存在一个\(x\)​​使得\(f(x)=y\)​​,记作\(x=f^{-1}(y)\)​​,则\(f^{-1}\)​​是一个从\(Y\)​​到\(X\)​​的函数,称为\(f\)​​​​的逆。

Definition 3.2.7 设函数\(f\colon X\to Y\)​​​​,若\(S\)​​​​是\(X\)​​​​的一个子集,则\(f(S)\coloneqq \{f(x)\colon x\in S\}\)​​​​称为\(S\)​​​​在\(f\)​​​​下的象;若\(T\)​​​是\(Y\)​​​的一个子集,则\(f^{-1}(T)\coloneqq \{x\in X\colon f(x)\in T\}\)​​​称为\(T\)​​​​的逆象。

Definition 3.3.3 设集合\(A\)到自身的一个二元关系\(R\)满足:
(a) 自反性:\(\forall a\in A(aRa)\)
(b) 传递性:\(\forall a,b,c\in A(aRb\wedge bRc\Rightarrow aRc)\)
(c) 对称性:\(\forall a,b\in A(aRb\Rightarrow bRa)\)
则称该关系是\(A\)上的一个等价关系,通常记作\(\sim\)

\(\S3.3\)​ 集合的基数与序

目前还没有定义自然数,但暂且引用下这个概念来引入集合的基数。

Definition 3.3.1 称集合\(A,B\)等势,当且仅当存在从\(A\)\(B\)的一个双射。

Remark 易证等势是一个等价关系。

Definition 3.3.2 集合\(A\)所在的等势等价类称为\(A\)的基数,记作\(|A|\)\(A,B\)等势记作\(|A|=|B|\)

Definition 3.3.3 设集合\(A\)到自身的一个二元关系\(R\)满足:
(a) 自反性:\(\forall a\in A(aRa)\)
(b) 传递性:\(\forall a,b,c\in A(aRb\wedge bRc\Rightarrow aRc)\)
(c) 反称性:\(\forall a,b\in A(aRb\wedge bRa\Rightarrow a=b)\)
则称\(A\)为一个偏序集,\(R\)\(A\)上的一个偏序关系,常记\(R\)\(\leq\),若\(a\leq b\)\(a\neq b\),则可记为\(a<b\)
若该二元关系还满足
(d) 完全性:\(\forall a,b\in A(aRb\vee bRa)\)
则称\(A\)为一个全序集,\(R\)\(A\)上的一个全序关系。
若还满足
(e) 最小元:\(\forall M\subset A(\exists a\in M\forall b\in M(a\leq b)\vee M=\emptyset)\)
则称\(A\)为一个良序集,\(R\)\(A\)上的一个良序关系。

Definition 3.3.4\(A\)是一个偏序集,\(B\subset A\)。若\(x\in B\)\(\nexists y\in B,y<x\),则称\(x\)\(B\)的最小元。若\(x\in B\)\(\nexists y\in B,x<y\),则称\(x\)\(B\)的最大元。

Definition 3.3.5\(A\)是一个偏序集,\(B\subset A\)。若\(\exists x\in A\forall y\in B(y\leq x)\),则称\(x\)\(B\)的一个上界。

Definition 3.3.6\(A\)是一个偏序集,\(B\subset A\)\(B\)有上界。若\(\exists x\in A\)满足:
(a) \(x\)\(B\)的上界;
(b)\(y<x\),则\(y\)不是\(B\)的上界,
则称\(x\)\(B\)的上确界,记作\(x=\sup B\)

类似地,可以定义下界与下确界,记作\(\inf\)

Definition 3.3.7 若偏序集\(A\)满足\(\forall B\subset A\)\(B\neq\emptyset\)\(B\)有上界,则\(\sup B\in A\),就称\(A\)有最小上界性。

类似地,可以定义最大下界性,而最小上界性与最大下界性之间的紧密联系可以从下述定理看出。

Theorem 3.3.1\(A\)是具有最小上界性的偏序集,\(B\subset A\)\(B\neq\emptyset\)\(B\)有下界,令\(L\)\(B\)的所有下界的集合,则\(\inf B=\sup L\)存在。

  • Proof\(B\)有下界,则\(L\)非空。
    任取\(x\in B\),显然\(x\)\(L\)的上界,由\(A\)的最小上界性,不妨设\(x=\sup L\),有\(x\in L\),因此\(x\)\(B\)的下界。
    任取\(y\in A\)\(y>x\),由上确界的定义,\(y\notin L\),则\(y\)不是\(B\)的下界,因此\(x=\inf B\)\(\Box\)

Remark 由该定理,只要一个偏序集有最小上界性,就一定有最大下界性,因此不用对两者重复讨论。

Definition 3.3.8 偏序集\(A\)上的偏序关系\(\leq\)若满足完全性\(\forall a,b\in A(a\leq b\vee b\leq a)\),则称其为全序关系,称\(A\)为全序集。

Definition 3.3.9 全序集\(A\)上的全序关系\(\leq\)若满足\(A\)的任意一个非空子集都有最小元,则称其为良序关系,称\(A\)为良序集。

Definition 3.3.10 定义基数的序关系\(\forall A,B(|A|\leq|B|\iff\exists C\subset B(|A|=|C|))\)

Theorem 3.3.2 基数的序关系是良定义的。

  • Proof\(A\leq B\)\(A=C\),则存在一个\(C\)\(A\)的双射\(f\)以及存在\(B\)的一个子集\(D\),且存在\(A\)\(D\)的一个双射\(g\)。考虑\(g\circ f\),显然这是\(C\)\(D\)的一个双射,因此\(C\leq B\)。同理易证关于\(B\)也有类似结论。 \(\Box\)

该二元关系的自反与传递是显然的,接着考虑其是否有反称性和完全性,先引入如下两个引理:

Lemma 3.3.1(Cantor-Bernstein-Schroeder 定理) 若存在\(A\)\(B\)的单射和\(B\)\(A\)的单射,则存在\(A\)\(B\)的双射。

Lemma 3.3.2(Zorn引理) 若偏序集\(A\)的任意全序子集都有上界,则\(A\)有最大元。

由Lemma 3.3.1,基数的序关系是偏序关系,再考虑其是否有完全性:

Theorem 3.3.3 基数的序关系是全序关系。

  • Proof 对任意集合\(A,B\),假设不存在\(A\)\(B\)的单射,考虑由所有\(B\)的子集到\(A\)的单射构成的集合\(\Omega\)
    \(\subset\)\(\Omega\)上的偏序关系,任取\(\Omega\)的一个全序子集\(C\),令\(F=\bigcup_{f\in C}f\),则
    \[ \forall (x,y)\neq(x_0,y_0)\in F,\exists f,f'\in C,(x,y)\in f,(x',y')\in f'. \] 不妨设\(f\leq f'\),则\((x,y),(x_0,y_0)\in f'\),从而\(x\neq x_0,y\neq y_0\),即\(F\)\(B\)的子集到\(A\)的单射,即\(F\in\Omega\)。从而\(C\)有上界。由Zorn引理,\(\Omega\)有最大元\(\phi\)。假设\(\phi\)的定义域不为\(B\)且值域不为\(A\),则\(\exists (x,y)\notin\phi\),且\(\phi'=\phi\cup\{(x,y)\}\)是单射,则有\(\phi'\in\Omega,\phi<\phi'\),这与\(\phi\)是最大元矛盾。
    从而必存在一个单射,其值域为\(A\)或定义域为\(B\)。若值域为\(A\),则\(\phi^{-1}\)\(A\)\(B\)的单射,与题意矛盾,因此\(\phi\)\(B\)\(A\)的单射,由此可得完全性。 \(\Box\)

最后,我们考虑集合的基数是否存在上界。

Theorem 3.3.4(Cantor定理) 对任意集合\(X\)\(|X|<|2^X|\)

  • Proof \(|X|\leq|2^X|\)是显然的。假设\(|X|=|2^X|\),则存在双射\(\phi\colon X\to 2^X\)。取\(Y=\{x\in X\colon x\notin\phi(x)\}\)\(y=\phi^{-1}(Y)\)。由\(Y\)定义可知\(y\notin Y\),即\(y\notin\phi(Y)\),但这又使得\(y\in Y\),因此产生矛盾,从而\(|X|<|2^X|\)\(\Box\)