- 博客(55)
- 收藏
- 关注
RSS订阅原创 数理逻辑5 -- 计算理论3
部分递归函数（Partial Recursive Function）定义图灵机不单单是为了好玩，还为了研究什么样的东西才是“可计算”的。从图灵机“一步一步”操作的方式来看，好像任意函数都能被计算。但实际上，只有某一类函数可被图灵机计算。这类函数被称作部分递归函数，与图灵机可计算的函数是等价的。前面漫长的证明哥德尔不完备定理过程中，哥德尔引入了“原始递归和递归函数”的概念，然后利用哥德尔编码...
2018-05-02 22:41:42
552
原创 数理逻辑5 -- 计算理论2
图灵机的示意图（Diagram）上节笔记给出了图灵机的定义，那一大堆四元组构成的指令集真个是比汇编代码还要难懂。不仅难写，更难检查。因此，我们需要一种“简便”的图灵机表示方式。我们说，一个图灵机的示意图包含以下内容： (1) 令F1,F2,...,FrF1,F2,...,Fr\mathcal{F}_1, \mathcal{F}_2, ..., \mathcal{F}_r为任意图灵机，它们...
2018-04-15 16:17:59
524
原创 数理逻辑5 -- 计算理论1
图灵机 Turing Machine我读此书和做笔记主要出自于好奇心，前三章是为了搞懂神神秘秘的哥德尔不完备定理，顺便学习一阶逻辑的知识。第四章的集合论是为了以后的实分析、测度论、概率和随机过程等夯实基础，同时满足罗素悖论的好奇心。现在第五章，终于见到了自己的老本行，往好奇心方面说是为了弄懂停机问题，往夯实基础方面说是为了后续的复杂度理论和算法设计做准备，至少也要彻底弄懂P=NP究竟是什么问题...
2018-04-14 16:37:13
815
原创 数理逻辑4 -- 公理化集合论18
上节构造了类HHH，以下命题给出了正则公理的等价形式。命题4.45：正则公理等价于V=HV=HV = H。证明： a. 假设V=HV=HV = H。考虑X≠∅X≠∅X \neq \emptyset，令αα\alpha为XXX中成员的排位的最小序数，令bbb满足α=ρ′bα=ρ′b\alpha = \rho'b。那么，b∩X=∅b∩X=∅b \cap X = \emptyset。否则的话，...
2018-04-08 16:10:26
451
原创 数理逻辑4 -- 公理化集合论17
继续选择公理的讨论。命题4.43：以下好式子是选择公理AC的推论 a. 任意无限集都有可列子集。Inf(x)⇒(∃y)(y⊆x∧Den(y))Inf(x)⇒(∃y)(y⊆x∧Den(y))Inf(x) \Rightarrow (\exists y)(y \subseteq x \land Den(y)) b. 无限集是Dedekind无限。Inf(x)⇒DedInf(x)Inf(x)⇒De...
2018-04-07 21:43:23
385
原创 数理逻辑4 -- 公理化集合论16
选择公理（Axiom of Choice）选择公理在集合论里受到很多争议，它看起来“很自然”，所以很多人以为它定能从其它公理推导得出。但实际上，在众多集合论中，选择公理已被证明和其它公理彼此独立，而没了选择公理，很多定理又无法被证明。因此，选择公理就被看作是是“奇葩”，看起来很自然很重要，但竟要“假设”它成立。选择公理有很多等价形式，以下命题给出了一些。 命题4.42：以下好式子是等价的...
2018-04-06 14:23:15
660
原创 数理逻辑4 -- 公理化集合论15
基数算术（cardinal arithmetic）命题4.37： a. ⊢ω×ω≅ω⊢ω×ω≅ω\vdash \omega \times \omega \cong \omega，可数集合的“可数次并”还是可数的。 b. ⊢2⪯X∧2⪯Y⇒X∪Y⪯X×Y⊢2⪯X∧2⪯Y⇒X∪Y⪯X×Y\vdash 2 \preceq X \land 2 \preceq Y \Rightarrow X \cu...
2018-04-04 15:37:38
279
原创 数理逻辑4 -- 公理化集合论14
序数算术（ordinal arithmetic）前面笔记中已定义了序数的加法、乘法、幂运算，这里回顾一下，证明它们的许多性质。在此之前，我们给出一个常用的技巧。引理4.14.1： a. ⊢X≅fY∧(∀x)(x∈X⇒x⊆f′x)⇒⋃X⊆⋃Y\vdash X \cong_f Y \land (\forall x)(x \in X \Rightarrow x \subseteq f'x)...
2018-03-28 15:53:08
248
原创 数理逻辑4 -- 公理化集合论13
关于有限集，再来一些练习。引理4.13.1（Tarski，1925）：我们说XXX是YYY的最小值，当且仅当，X∈Y∧(∀y)(y∈Y⇒¬(y⊂X))X∈Y∧(∀y)(y∈Y⇒¬(y⊂X))X \in Y \land (\forall y)(y \in Y \Rightarrow \neg (y \subset X))，也即XXX是YYY的“最小集合”。那么，一个集合ZZZ是有限的，当且仅当，...
2018-03-26 17:05:40
520
1
原创 数理逻辑4 -- 公理化集合论12
有限集我们说，一个类XXX是有限的（Finite），当且仅当，它能与某个ωω\omega中的序数等势。即，定义4.12.1： a. Fin(X)Fin(X)Fin(X)：是(∃α)(α∈ω∧X≅α)(∃α)(α∈ω∧X≅α)(\exists \alpha)(\alpha \in \omega \land X \cong \alpha)的缩写。以下结论是显然的。 引理4.12.1： ...
2018-03-24 20:43:01
227
原创 时间序列分析1
从统计学的角度去看，时间序列就是个随机过程，因此讨论时间序列之前，先要把随机过程的基本概念讨论清楚。随机变量与随机过程 简单地理解随机变量与随机过程是不难的，但这里要从更严谨的角度去理解。当然，这里的严谨也没到测度论那种地步。*定义1.1（随机变量）：一个随机变量XXX是以样本空间ΩΩ\Omega为定义域，以实数RRR为值域的函数，即X:Ω→RX:Ω→RX: \Omega \righta...
2018-03-15 17:37:50
525
原创 数理逻辑4 -- 公理化集合论11
上一节讨论到类的等势。等势具备等价关系的所有性质，因此我们可以依据等势把所有集合（即真类VVV中的所有元素）分成等势的类。比如uuu是一个集合，那么所有和x={u}x={u}x = \{ u \}等势的集合所组成的类可记作1c1c1_c。这样的类被称为“弗雷格 - 罗素”基数，Frege-Russell cardinal number。（弗雷格是德国哲学家、逻辑学家，他在布尔之后进一步把集合、逻辑...
2018-03-14 09:16:11
381
原创 数理逻辑4 -- 公理化集合论10
等势(Equinumerosity) 康托尔通过研究集合之间的“势”，来研究无穷大和超限数等概念，著名的对角线论证法也从这诞生。定义4.10.1： a. X≅FYX≅FYX \cong_F Y：是Fnc1(F)∧D(F)=X∧R(F)=YFnc1(F)∧D(F)=X∧R(F)=YFnc_1(F) \land \mathcal{D}(F) = X \land \mathcal{R}(F) =...
2018-02-25 18:31:40
336
原创 数理逻辑4 -- 公理化集合论9
这节再讨论些关于序数的定理。教材从这里开始懒的写好式子了，全用自然语言来表达。命题4.15：RR是类YY上的良序，FF是YY到YY的函数，对于任意u,v∈Yu, v \in Y，若<u,v>∈R \in R，则<F′u,F′v>∈R \in R。那么，对任意u∈Yu \in Y，要么u=F′uu = F'u，要么<u,F′u>∈R \in R \}，只需证X...
2018-02-06 17:16:02
230
原创 数理逻辑4 -- 公理化集合论8
继续讨论一些序数的性质。引理4.8.1： a. ⊢(∀α)([Suc(α)⇒(⋃α)′=α]∧[Lim(α)⇒⋃α=α])⊢(∀α)([Suc(α)⇒(⋃α)′=α]∧[Lim(α)⇒⋃α=α])\vdash (\forall \alpha)\Big( \big[ Suc(\alpha) \Rightarrow (\bigcup \alpha)'=\alpha \big] \land \bi...
2018-02-05 21:10:40
264
原创 数理逻辑4 -- 公理化集合论7
上一节给出了序数的定义，下面讨论它们的性质。命题4.8： a. ⊢Ord(X)⇒(X∉X∧(∀u)(u∈X⇒u∉u))" style="position: relative;" tabindex="0" id="MathJax-Element-3-Frame" class="Mat
2018-02-04 15:12:52
279
原创 数理逻辑4 -- 公理化集合论6
罗素悖论 罗素悖论在NBG理论下并不会产生矛盾。记Y={x|x∉x}" role="presentation" style="position: relative;">Y={x|x∉x}Y={x|x∉x}Y = \{ x | x \notin x \}，这个Y" role="presentation" style="position: relative;">YYY就称为“罗素类”。
2018-02-02 09:58:28
661
原创 数理逻辑4 -- 公理化集合论5
Axiom U保证了Sum Class是一个集合，即(∀x)(∃y)(∀u)(u∈y⇔(∃v)(u∈v∧v∈x))(\forall x)(\exists y)(\forall u)(u \in y \Leftrightarrow (\exists v)(u \in v \land v \in x))引理4.5.1： a. ⊢(∀x)(∀y)(⋃{x,y}=x∪y)\vdash (\forall x
2018-01-31 15:48:05
375
原创 数理逻辑4 -- 公理化集合论4
上一节笔记中命题4.4提供了一般性的类存在依据，以下就以此定义几个特殊的类。几个特殊的类和新的函数符号 1. 考虑好式子φ(X,Y1,Y2)\varphi(X, Y_1, Y_2)为(∃u)(∃v)(X=u,v>∧u∈Y1∧v∈Y2)(\exists u)(\exists v)(X = \land u \in Y_1 \land v \in Y_2)，显然它是谓词好式子。根据命题4.4可得
2018-01-29 11:38:09
354
原创 数理逻辑4 -- 公理化集合论2
这节笔记就一个个讨论前面提到的公理，穿插它们导致的一些结论。引理4.2.1：⊢M(Z)∧Z=Y⇒M(Y)\vdash M(Z) \land Z = Y \Rightarrow M(Y) 证明： 1. M(Z)M(Z)，假设 2. (∃X)(Z∈X)(\exists X)(Z \in X)，这是1的展开写法 3. Z∈bZ \in b，由2和规则C 4. Z=YZ = Y，假设 5.
2018-01-26 10:20:49
447
原创 数理逻辑4 -- 公理化集合论1
集合论是所有数学的基础，很多数学概念都可用集合来表示。比如，我们可以用集合论建立自然数系统，也可建立函数。从朴素的集合论角度来看，所谓一个集合，就是“一堆元素”。但罗素悖论指出，我们不能那样定义集合，否则就会产生罗素悖论。即是说，我们是否允许一个集合包含自身作为元素？如果允许，就会导致罗素悖论，即我们定义一个集合AA，它的元素是所有哪些不属于自己的集合，那么试问是否A∈AA \in A？如果是...
2018-01-25 09:27:52
2608
1
原创 数理逻辑3 -- 形式数论16
哥德尔第一不完备定理要求理论K具有ω−\omega-一致性，数学家Rosser把这个条件变弱了。他说，K不需要ω−\omega-一致性，而是满足两个小小条件，一样可以构造出如下一个不可判定句子： H(x1): (∀x2)(PF(x2,x1)⇒(∀x3)(NEG(x1,x3)⇒(∃x4)(x4≤x2∧PF(x4,x3))))H(x_1): \ \ (\forall x_2)\Big( PF(x_
2018-01-22 22:10:53
319
原创 数理逻辑3 -- 形式数论15
上节给出了19类哥德尔构造的递归函数和关系，这节还有几个，然后水到渠成，哥德尔不完备定理呼之欲出。定义3.15.1：一阶理论K包含原始递归（或，递归）公理集，当且仅当以下关系PrAxPrAx是原始递归（或，递归）：PrAx(y)：y是K中某个适当公理（ProperAxiom）的哥德尔数PrAx(y)：y是K中某个适当公理（Proper Axiom）的哥德尔数根据以上定义，不难证明，一阶理论
2018-01-22 11:54:11
295
原创 数理逻辑3 -- 形式数论14
这节开始讨论哥德尔构造的几十个递归关系和函数。讨论之前，给出一个引理，这是命题3.17的推论，在之前的讨论中一直“隐形”使用。它源于我的一个疑问，感谢Stack Math上无名帮助者的答案。 引理3.14.1：若函数f(x1,...,xn,y,z)f(x_1,...,x_n, y, z)是原始递归（或，递归），则g(x1,...,xn,z)=∑yzf(x1,...,xn,y,z)g(x_1,
2018-01-20 21:38:33
359
原创 数理逻辑3 -- 形式数论12
形式系统的算术化：哥德尔数 这节来到了哥德尔不完备定理的峰底，剩下的路崎岖难行，到处是九十度的悬崖峭壁。哥德尔数是一种“编码”，它把形式系统中的每个符号都映射成一个整数，基于此再把每个表达式映射成一个整数，再接着把每一个表达式序列也映射成一个整数。这是哥德尔证明不完备定理的聪明之举，他把形式系统算术化，这样关于这个形式系统的“元命题”（比如，“这个系统不存在某种好式子”，“这种好式子的证明序列至少
2018-01-16 14:00:10
405
原创 数理逻辑3 -- 形式数论9
关系的组合 既然函数可以通过各种操作组合出新的函数，关系当然也有类似的操作。关系的组合是通过和命题演算系统（第一章的系统L）里的连接符号进行操作的。我们可以定义以下关系的组合操作： 定义3.9.1： a. 若R1(x1,...,xn)R_1(x_1,...,x_n)是关系，则记R(x1,...,xn)R(x_1,...,x_n)为¬R1(x1,...,xn)\neg R_1(x_1,...,x
2018-01-16 09:43:34
312
原创 数理逻辑3 -- 形式数论10
COV（Course-Of-Values）递归 在递归规则中，不仅可以让f(y+1)f(y+1)的值取决于f(y)f(y)，也可取决于f(u),uyf(u), u的值。这种情况下的递归规则就称为COV（Course-Of-Values）递归。其中一个COV递归的形式是：记f#(x_1,...,x_n,y) = \prod_{uf#(x_1,...,x_n,y) = \prod_{u，那么f(x_
2018-01-14 17:29:51
292
原创 数理逻辑3 -- 形式数论11
这节证明一个重要的定理。命题3.24：每个递归函数都在S中可表达。 证明：不难证明，三个初始函数都可在S中可表达。下面考虑递归规则和受限μ−\mu-操作规则产生的函数在S中的表达性。 (1) 递归规则：根据定义，记函数ff为函数gg和hh通过递归规则而得出，且gg和hh都是递归函数。假设gg和hh在S中可表达，我们需证明ff也可在S中表达。因为ff由递归规则而得，即有以下式子： f(x1,..
2018-01-14 13:29:35
182
原创 数理逻辑3 -- 形式数论8
本节开始讨论递归函数，终于来到了哥德尔定理的山脚下。上节讨论了函数在含等式理论中的表达性。由于PA理论S（即用一阶代数语言和S1-S9那些公理组成的一阶理论）也是含等式的理论，因此研究S中可表达的函数很重要，这些个函数对数理逻辑和计算机科学都有着深远影响。我们先来看一些特殊的函数。 定义3.8.1：以下函数称为初始函数（Initial Function）： I. 零函数（Zer
2018-01-11 11:09:20
300
原创 数理逻辑3 -- 形式数论7
玩的越来越难，越来越抽象了。在自然数系统中，我们经常会考察一些n元关系和函数，比如xyx 就是二元关系，x+y=zx + y = z是三元关系，3+5=83+5 = 8是二元函数f(3,5)=8f(3, 5)=8。这些个n元关系和函数是自然数系统的性质，与形式逻辑系统无关。那么，我们现在关心的是这些个n元关系和函数如何能在形式逻辑系统中“表达”出来呢？为了严格讨论“关系、函数如何在形式逻辑
2018-01-10 09:47:28
312
原创 数理逻辑3 -- 形式数论6
前面一大堆东西，都是用一阶理论建立“自然数系统”。既然是自然数，当然少不了“除法”。本节笔记把除法弄完，下节就开始玩点更难的东西了。我们可以如此定义“除法”： 定义：t|st | s 是 (∃z)(s=t⋅z)(\exists z) (s = t \cdot z)的缩写，这里zz是不在项s,ts, t中的第一个变量符号。用日常语言来说就是：tt能整除ss的意思是，存在一个zz，使得s=t⋅zs =
2018-01-09 15:51:48
363
原创 数理逻辑3 -- 形式数论5
继续上节的证明。o. 要证t≠r⇒(tr∨rt)t \neq r \Rightarrow (t。水平不够，只能用归纳法。记B(x)B(x)为t≠x⇒(tx∨xt)t\neq x \Rightarrow (t。 首先，考虑B(0)B(0) 1. t≠0t \neq 0，假设 2. 0≤t0 \leq t，命题3.7i 3. 0t0 ，由1、2和析取消除 4. t0∨0tt ，由3和析取
2018-01-09 10:32:20
214
原创 数理逻辑3 -- 形式数论4
歌德尔不完备定理是命题3.37，还有很长的路要走，慢慢来吧。命题3.6: m,n是任意自然数， a. 如果m≠nm \neq n, 则⊢m¯≠n¯\vdash \bar{m} \neq \bar{n} b. ⊢m+n¯¯¯¯¯¯¯¯¯=m¯+n¯\vdash \overline{m+n} = \bar{m} + \bar{n} c. ⊢m⋅n¯¯¯¯¯¯¯=m¯⋅n¯\vdash \ov
2018-01-04 13:57:23
239
原创 数理逻辑3 -- 形式数论3
推论3.3 S是含等式的一阶理论。 证明：不难，略。S是含等式的理论，意味着我们在加法和乘法中可以做“替代”操作，因为⊢x=y⇒B(x,x)⇒B(x,y)\vdash x=y \Rightarrow B(x, x) \Rightarrow B(x,y)成立。 其中，利用Gen和规则A4，上述的变量x,yx,y 换成项t,st, s也是成立的。命题3.4：对任意的项t,r,st, r, s，以下w
2018-01-03 10:24:22
370
原创 数理逻辑3 -- 形式数论1
这节开始跳到第三章，其实第二章还有好多内容，但冗长沉闷，也不知道后面是否能用上。所以，先跳到第三章，若需要用到第二章剩余的内容，再跳回去。
2017-11-20 22:17:19
772
原创 数理逻辑2 -- 量化理论9
这节笔记我们讨论一个特殊的一阶理论：含等式的一阶理论。含等式的一阶理论K是这么个理论：它有一个谓词符号A21A^2_1，然后我们把A21(t,s)A^2_1(t, s)简写为t=st=s，把¬A21(t,s)\neg A^2_1(t, s)简写为t≠st \neq s。这个理论除了A1-A5这5套公理之外，还附带以下两套公理： (A6) (∀x1)x1=x1(\forall x_1)x_1
2017-08-10 10:32:09
406
原创 数理逻辑2 -- 量化理论8
本节笔记我们继续完备性定理的证明。该定理被称为量化理论的基本定理(fundamental theorem)，可见其重要性。上节提到一大堆引理与定义，我们首先给出后续要用到的定义。定义2.39：好式子相似性：如果xix_i和xjx_j不同，称B(xi)B(x_i)和B(xj)B(x_j)是相似的，当且仅当，xjx_j在B(xi)B(x_i)中对xix_i自由，并且B(xi)B(x_i)
2017-08-09 14:07:13
739
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人