/
...
/
/
§1.数理逻辑 MA
Search
Try Notion
§1.数理逻辑 MA
§1.1 逻辑
引入: 本书的语言, 就像大部分数学文献那样, 是由普通语言和一系列理论叙述专用符号构成的. 我们将按照需要引入这些专用符号
通用的数理逻辑符号
¬        \neg \quad \land \quad \lor \implies \iff
约定优先级Left to right\overset{Left \ to\ right}{\longrightarrow}
在这样的约定下,若有如下表达式 ¬ABC    D\neg A \land B \lor C \implies D 解释成 (((¬A)B)C)    D(((\neg A ) \land B ) \lor C ) \implies D
A    BA \implies B 等价表述
A 蕴含B 集合论角度: 假定A    BA\implies B命题为真, 则有 ABA \subset B
🤔若A, 则B(半命题引入)
注意我们只讨论了若A真,B为真的情况,而没有分析若A(前件为假的情况)
所以在A为假时候 语句若A, 则B无法判断真假并不是一个完整命题
证明中往往需要隐含 ”若A, 则B 若¬\neg A, 则B”中的下半句 或者 能保证A为真
命题证明
证明命题: 即证明命题A    BA\implies B其中 A 是前提,B 是结 论.证明这个命题,就是建立一串蕴涵关系 A    C1    C2...    BA\implies C_1 \implies C_2 ... \implies B
推导法则
三段法: 如果 A 成立 且 A    \impliesB 也成立 , 则 B成立
排中率: 即不论命题 A 的具体内容如何, (A 或¬\neg A)总是成立的. 因此, 有 ¬¬A    A\neg \neg A \iff A
💡如果我们没有逻辑体系, 究竟怎么建立数学分析呢
这里在本质上只讨论了记号,而没有分析逻辑推导体系,也没有涉及诸如真实性、可证明性、可推导性等构成数理逻辑研宄
用一则著名的寓言来说明:蜈蚣在解释它宄竟如何控制自己的全部那么多条腿的时候,连路都不会走了
🤔蕴含关系(若..则..)的真值表
前件为假 导致 蕴含命题为真的本质, 是为了我们使用蕴含关系的
§1.2 集合
集合引入: 从 19 世纪末 20 世纪初开始,集合论语言成为最通用的数学语言.这甚至表现在数学的一种定义中:数学是研究集合上的各种结构(关系)的科学
朴素集合论(康托尔集合论)
集合可由任何有区别的对象组成    \iff组成一个集合的对象称为该集合的元素
集合由其组成对象整体唯一确定;
何性质都确定一个具有该性质的对象的集合;
为何不是精确定义?: 因为它涉及可能比集合的概念本身更复杂(总之未曾定义过)的概念.这种描述的目的是通过建立与其他概念的联系来解释
集合的表达
如果x是一个对象, P是一种性质, P(x)表示具有x对象具有性质P
{xP(x)}\{x | P(x) \} 表示具有性质 P 的整整一类对象
组成类或集合的对象称为类或集合的元素
集合的不完美性
集合的给定方法可能在明确程度上有所不同,这就让我们想到,集合己经不再是那种简单的完美无瑕的概念
罗素悖论
设M代表集合,P(M)表示性质: M不以其本身为元素
设一个集合K={M | P(M)} 则要么 P(K)成立要么¬\negP(K) 成立
P(K)若真,因为由K的定义 K={M | P(M)} ,K满足P(K),是K中一个元素,矛盾
P(K)若假,表示这表示 KKK\in K 和K的定义矛盾
🤔罗素悖论关键
构成悖论的基本要素是自我指涉与自我否定
什么是悖论?悖论不是那些错误的语句,而是那些没有办法赋值的语句
例子: 这句话是错的
集合间包含关系
🤔何为关系: 涉及两个对象的命题→命题的一种形式
🤔命题的等价形式: 关系、论断(恒为真的命题)
定义元素-集合属于关系: 命题 “x是集合 X的元素” := xXx\in X
定义集合等价关系:
直接基于属于关系: A=B:=x ((xA)    (xB))A=B:= \forall x\ ( (x\in A) \iff (x \in B))
基于集合间包含关系: A=B    (AB)(AB)A=B \iff (A\subset B) \land (A\supset B)
🤔同一命题的不同定义: ((X:=A)(A    B))    ((X:=B)(A    B))((X:=A)\land (A\iff B))\iff ((X:=B)\land (A\iff B))
集合间包含关系(子集关系)
基于元素-集合属于关系
AB:=x ((xA)    (xB))A\subset B := \forall x\ ((x\in A) \implies (x\in B))
集合运算
何为集合运算:
利用 属于关系 和 命题连词 来定义某个P(x)性质,把满足该性质的元素组成一个新的集合
🤔何为性质: 具有变元的命题
往往是描述集合中元素x具有某种性质P(x),而性质P(x)又通过逻辑连词和属于关系确定
并集运算: AB:={xM(xA)(xB)}A \cup B := \{ x \in M | \left( x \in A \right) \lor \left( x \in B \right) \}
交集运算: AB:={xM(xA)(xB)}A \cap B := \{ x \in M | \left( x \in A \right) \land \left( x \in B \right) \}
差集运算: A\B or AB:={xM(xA)(xB)}A \backslash B\ or\ A-B := \{ x \in M | \left( x \in A \right) \land \left( x \notin B \right) \}
直积(也算一种集合运算)
有序偶-预先概念
无序偶定义: 对于任何两个集合A,B, 可以组成一个新的集合一偶{A,B}={B,A}, 其元素是且仅是集合A和B.这个集合在A≠B时由两个元素组成, 而在A=B时由一个元素组成
有序偶定义: (A,B)相较于无需偶元素A,B具有附加特征,从而能够区别偶(A,B)中的第一个元素和第二个元素
直积定义
X×Y:={(x,y)(xX)(yY)}X \times Y := \{ \left( x , y \right) | \left( x \in X \right) \land \left( y \in Y \right) \}
Y=XY=X时候可以简写为X2X^2
§1.3 函数
(1) 函数概念
⚠️课本上的概念
其基础性非数学所独有, 设 XXYY 是某两个集合. 如果集合X X 的每一个元素xx, 都按照某规律 ff 与集合 YY 的元素 yy  相对应,我们就说有一个函数,它定义于集合 XX 并取值于集合 YY
我们说XX为其定义集合,元素 xx 称为函数的变元或自变量
而与自变量 x0x_0 相对应的元素 y0Yy_0 \in Y 称为元素 x0x_0 上的函数值. 表示为 f(x0)f(x_0)
并可以定义值集合: f(X):={ yY  x( (xX)(y=f(x)) }Yf(X):=\{\ y\in Y\ |\ \exists x(\ (x\in X)\wedge (y=f(x))\ \} \subset Y
🤔函数的概念(自我思考)
函数的概念: 存在两个集合XX, YY 使得, xX, !yY, Let x and y correspond\forall x \in X, \ \exist! y \in Y,\text{ Let x and y correspond}
!\exist! : 表述 ”唯一存在” , 即x1=x2    f(x1)=f(x2)x_1= x_2 \implies f(x_1) = f(x_2)
我们称XX为函数的 “定义集合” (一类特殊的出发集合)
我们称YY为函数的 “值集合” (所有到达集合的父集合)
f(X):={ yY  x( (xX)(y=f(x)) }Yf(X):=\{\ y\in Y\ |\ \exists x(\ (x\in X)\wedge (y=f(x))\ \} \subset Y 定义为 在定义集合XXff函数的到达集合
函数的记号说明
函数的同义词或记号: 映射, 变换, 算子, 泛函
符号: 记作 f: X Yf:\ X\to \ Y Xf YX\overset{f}{\mathop{\to }}\,\ Y
定义域和值域从上下文看很明显时也使用 x    f(x)ory=f(x)x\; \mapsto \;f(x)\quad or\quad y = f(x)
函数的延拓限制
AX  and  f:XYA \subset X\;and\;f:X \to Y 且有 φ:AY\varphi :A \to Y 使得 xA,  f(x)=φ(x)\forall x \in A,\;f(x) = \varphi (x)
则称 φ\varphiff 的限缩, ffφ\varphi 的延拓
φ\varphi 也可记作 fAf|_A
像与原像
元素的像: 当函数 f: X Yf:\ X\to \ Y , 我们称 y0y_0x0x_0 的像
集合的像: 我们定义 f(A):={ yY  x( (xA)(y=f(x)) }f(A):=\{\ y\in Y\ |\ \exists x(\ (x\in A)\wedge (y=f(x))\ \} 为集合A的像
注意🤔: 和值集合的定义几乎一摸一样, 但是我们的出发集合AA 不在一定等于函数的的定义集合X 而是 AXA\subset X
集合的原像: f1(B):={ xX  f(x)B}f^{-1}(B):=\{\ x\in X\ |\ f(x) \in B \}
注意💡: 这个是函数的原像的定义, 而非反函数的定义, 哪怕一个 x0x_0 对应多个 y0y_0 也是有原像的(非单射, 非满射)
(2) 满射/单射/双射
映射分类
引入: 引入像和原像概念后我们可以以此来分类映射
满射: 当集合X的像等价于Y即 f(X)=Yf(X)=Y
单射: 满足 f(x1)=f(x2)        x1=x2f({x_1}) = f({x_2})\; \implies\;{x_1} = {x_2}
双射: 一个映射是满射且是单射的时候为双射
满射的等价表述
已知定义 f(X):={ yY  x( (xX)(y=f(x)) }Yf(X):=\{\ y\in Y\ |\ \exists x(\ (x\in X)\wedge (y=f(x))\ \} \subset Y
且有 f(X)=Y={yY}f(X) = Y = \{y \in Y \}
则有后面的f(X)定义时候后面的选择条件恒定为真, 即 yY we have x( (xX)(y=f(x)Ture\forall y\in Y\ \text{we have}\ \exists x(\ (x\in X)\wedge (y=f(x) \equiv Ture
上述表述和函数的概念几乎一样,只是少了唯一性 函数的概念: xX, !yY, Let x and y correspond\forall x \in X, \ \exist! y \in Y,\text{ Let x and y correspond}
反函数定义
f1:YXf^{-1}:Y \rightarrow X 的定义: 若 f(x)=yf(x)=y , 定义 f1(y)=xf^{-1}(y)=x 
💡注意 反函数f1:YX f^{-1}:Y \rightarrow X 和 原像 f1(Y)f^{-1}(Y) 缩写都是f1f^{-1}但是意思不同
🤔反函数存在条件: 若双射     \iff则存在 f1:  YX{f^{ - 1}}:\;Y \to X
接下来我们验证: 若双射且上面定义,则符合函数规则
由于ff为满射, 故 y0Y, x0X, let f(x0)=y0\forall y_0 \in Y ,\ \exist x_0 \in X,\ let \ f(x_0)=y_0
由于ff为单射, f(x1)=f(x2)        x1=x2f({x_1}) = f({x_2})\; \implies\;{x_1} = {x_2}
二者组合, 则有再加上反函数定义: y0Y, !x0X, let f1(y0)=x0\forall y_0 \in Y ,\ \exist! x_0 \in X,\ let \ f^{-1}(y_0)=x_0 和函数的概念形式上一致
🤔单射 满射 这个概念的意义
函数的概念由两个子命题组成
和单射 满射即满足
(3) 复合/恒等映射
复合映射:
若有映射 f:XZg:ZYf:X \to Z\quad g:Z \to Y 则可以构造映射 fg:XY let fg(x):=f(g(x))f \bullet g:X \rightarrow Y \ \text{let}\ f\bullet g(x) := f(g(x)) 
并且我们将 f:XXf(x):=xf:X \to X\quad f(x):=x 定义为恒等映射 exe_x
引理: 恒等映射和单射满射关系
定理内容
f:XY g:YXf:X\rightarrow Y\ g:Y\rightarrow X
gf=ex    g \bullet f = e_x \implies ff 为单射, gg 为满射
证明1: gg为满射
定义A:=f(X)A:=f(X) 方便后面的讨论, 即 (gf)(X)=g(f(X))=g(A)(g \bullet f)(X) = g(f(X)) = g(A) 
由到达集合和总值集合关系 g(A)g(Y)Xg(A) \subset g(Y) \subset X
💡由于 (gf)(X)=ex(X)=X    Xg(A)(g \bullet f)(X) =e_x(X) =X \implies X \subset g(A)
💡则有 Xg(A)=gf(X)g(Y)XX \subset g(A) = g \bullet f(X) \subset g(Y) \subset X
可得 Xg(Y)X    g(Y)=XX\subset g(Y) \subset X\implies g(Y) =X (满射的定义)
证明2: ff为单射
由函数的概念可知: y1=y2    g(y1)=g(y2) y_1 = y_2 \implies g(y_1) = g(y_2)
由题目可知: yn=f(xn)g(yn)=eX(xn)=xny_n = f(x_n) \quad g(y_n) = e_X(x_n) =x_n
替换(i)中 yn g(yn)y_n\ g(y_n) 可得 f(x1)=f(x2)    x1=x2f(x_1) = f(x_2) \implies x_1 = x_2 即为单射的定义
逆函数第二定义
性质内容:
已知两个映射f:XY g:YXf:X\rightarrow Y\ g:Y\rightarrow X
(gf=eX)(fg=eY)    f and g are inverse mapping couple(g \bullet f = e_X )\land( f \bullet g = e_Y ) \iff f\ \text{and}\ g\ \text{are inverse mapping couple}
证明
借助上面 恒等映射和单射满射关系 可知, ff gg 均为双射函数
且有f(g(x))=xf(g(x))=x 故为逆映射
我们也可以将符合 (gf=eX)(fg=eY)(g \bullet f = e_X )\land( f \bullet g = e_Y ) 的函数定义为逆映射, 形式上更加对称
§1.4 关系
函数的定义的发展历程
我们在 §1.3 中提到的函数概念是由欧拉给出的, 而想要准确定义函数, 则需要更多的工作
“理论的普遍观点认为,只有把彼此有关联的数理解为是一起给定的,依赖关系才会存在” 这正是精确定义函数概念的思想
本节最前面对函数概念的描述是一种反映其本质的相当动态的描述, 但从现代标准来看,还不能称之为定义,因为它使用了一个与函数等价的概念—-对应
集合论的语言定义函数
关系.: 序偶 (x,y)(x,y) 的任何集合称为关系 RR
🤔区别于实数集, 一般严谨的写成 R\mathbb{R} ,但经常在理解上下文情况下我们直接写成 RR
值集合 定义集合: 组成RR的所有序偶的第一个元素的集合 XX 称为关系 RR 的定义集合,而第二个元素的集合 YY 称为关系 RR 的值集合
可以将关系RR理解为直积 X×YX \times Y 的子集
常常把 (x,y)R(x,y)\in R  写为 xRyxRy , 并说 xxyy 之间的关系为 RR
等价关系
等价关系定义: 任何具有下述三个性质的关系称为等价关系, 用符号” aba\sim b ” 表示
自反性: aRaaRa
传递性: (aRb)(bRc)    aRc(aRb)\land(bRc) \implies aRc
对称性: aRb    bRaaRb \iff bRa
平行关系 为 一种等价关系
XX 是平面上的直线的集合.如果直线 bXb \in X 平行于直线 aXa \in X , 我们称两条直线具有关系 RR , 可以验证, 关系 RR 符合上面三条性质
序关系
偏序关系定义: 任何具有下述三个性质的关系称为偏序关系, 用符号” aba\preccurlyeq b ” 表示
自反性: aRaaRa
传递性: (aRb)(bRc)    aRc(aRb)\land(bRc) \implies aRc
反对称性: (aRb)(bRa)    a=b(aRb) \land (bRa) \implies a=b 
序关系: 除了满足偏序定义之外, 还满足排中律(可比性), 称定义了序关系集合为线性序集
排中律: a,b(aRb)(bRa)True\forall a,\forall b \quad(aRb)\lor(bRa) \equiv \text{True}
函数关系: 满足 xRy1xRy2    y1=y2xRy_1 \land xRy_2 \implies y_1 = y_2 的关系称为函数
§1.5 势函数(集合)
定义函数Card(X)Card(X):
该函数输入的”元素” 为集合输出的元素为”势” ,我们来研究所有”势”元素构造的集合”势集合” 具备什么性质
定义: 如果集合 XX 到集合 YY 的双射存在, ,则称集合 XXYY 等势, 记作 CardX=CardYCard X = Card Y
§Ext 1 一些玄学思考
集合论靠公理系统定义, 集合论内也可以包括公理系统?
ZFC本身也是形式主义的产物, 但是ZFC强大的表现力使得形式系统本身可以在ZFC中得以表现, 因此乙F定义了何为形式系统, 并且发现, 无矛盾形式系统总可以看作是某个论域上的命题集, 公理集总可以看作是对论域的限制, 而真命题则是在一切满足限制条件的论域上总成立的命题. 在这种定义下, ZFC证明了演绎定理、完全性定理、不完全性定理等一系列有用的命题.
🤔函数 泛函 算符
函数: 一般指的是定义集合
§Ext 2 函数命题 自有记号版本
(1) 基本定义
xX,yY Let:  [(x,y)f][(x,y)f (x=x    y=y)]\forall x \in X, \exist y \in Y \text{ Let: } \ [(x,y) \in f] \land [\forall (x' ,y') \in f \ (x'=x \implies y' = y)]
XX 记作定义集, YY 记作到达集 定义集 XX→到达集 YY
"值集” \subset "到达集”
且有所有原像构成集合 “原像集“, 所有像构 “像集”
可以发现 “原像集" = "定义集” “像集" \subset "达到集”
我们也称 "像集” 为 "值集” 记作 f(X)f(X)
f(X):={yYxX, Let (x,y)f}f(X) := \{y \in Y | \exist x \in X , \text{ Let } (x,y) \in f\}
我们先定义了 "值集合” 再来定义到达集合
Y:=Y Is a Set that f(X)YY : = Y \text{ Is a Set that } f(X) \subset Y 
可以说 "到达集合” 本身没啥意义, 仅仅是包含 f(X)f(X) 集合 都可以称该函数的到达集