楼主:
antidote (Against SCA)
2017-02-02 05:02:47※ 引述《ADHD (注意力不足过动症)》之铭言：
: ※ 引述《scxKinsey (西欺板匿名专用)》之铭言：
: : http://i.imgur.com/TOTzALz.png
: : 如题
: : Γ是无限set的情况掰不出来
: : 一钟头后直接交上去应该扣一半吧
: : 上网找也找不到解答 因为课本是教授写的 有事没事还会更新一下
: : 难道我就只能被教授肛了吗 还是要先发制人肛了教授先?
: : 卦?
: 随便试试看
: 如果对你有帮助就好了
: 讲个我自己想了一下大概的想法
: 要直接证有点难
: 用矛盾来证的话
: 那就变成
: 假设所有的集合delta(三角形) 不|= A delta为所有可能的Γ的子集合
: 这样的假设会导出矛盾
: 所以必定有些delta |= A
: 我们开始推导
: delta 不|= A代表的是
: 存在一些真值分配(truth value assignment)使得
: delta为真而A为假
: *
: 我们假设集合Γ中存在真值函数(truth function){a1,a2,.........ai,....}
: 我们现在依序做出一些delta
: delta1 {a1}
: delta2 {a1,a2}
: .
: .
: .
: .
: .
: deltai {a1,a2.....ai}
: 而我们知道对于每一个deltai而言每一个deltar 其中r<=i
: deltar都是deltai的子集合
: 如果有一个真值分配使得deltai为真A为假
: 则也会使得deltar为真而A为假
: 每一个有限集合deltai都有另一个有限集合(delta(i+1))是他的父集合
: 根据假设
: 每一个可能的子集合delta都 不|= A(也就是存在真值分配使得delta为真A为假)
: 因此存在真值分配使得所有的deltai为真而A为假 i为任意正整数
: 现在
: 我们把每一个有限集合deltai都联集起来 其中i从1到无限大
: 而根据刚刚的*的推论
: 存在"同一个"真值分配使得每一个不同的delta为真而A为假
这边有个问题，*这个subproof里面似乎只证明了每个让deltai为真但A为假的assignment
也会让deltai的每个子集合为真但A为假
但如果delta之间不是subset的关系呢
比如说{a1,a3}跟{a2,a4}这两个gamma的finite subsets
*在这里似乎就不适用
: 这样的真值分配使得所有delta的联集也为真 而同时A为假
: 在这边
: 所有delta的联集就是Γ
: 而Γ为真A为假代表的就是 Γ 不|= A
: 与前提矛盾
: 因此必定存在delta为Γ的有限集合 使得delta |= A
: 中间有些地方可能还需要证
: 可能就要麻烦你自己了QQ
在这边提供一个不太一样的证法
由于题目上是写Corollary 1.9
我猜前面是有先给一个theorem 然后才要你证compactness
刚刚看了以前中阶逻辑跟model theory的课本
发现大部分的证法都是从completeness theorem出发 证到compactness
这边就先假设题目已经给你completeness了:
If gamma ╞ phi, then gamma ├ phi.
先假定我们有上面这条定理(以及反过来但超级容易证的soundness)
那回到本来题目要证的
因为entailment(gamma╞phi)跟inconsistency( (gamma∪not phi)╞)两个可以互相定义
所以我们可以把题目改成
If gamma╞ , then there is a subset delta of gamma such that delta╞
也就是说if gamma is not satisfiable, then delta is not satisfiable.
(satifiable指的是可以找到一个truth assignment让集合里面的elements全都为真),
现在先假设(反证)gamma is not satisfiable以及no finite subset of gamma is not
satifiable(i.e. all finite subsets of gamma are satifiable)
根据completeness, 由于gamma is not satisfiable (i.e. gamma ╞) 所以 gamma会是
inconsistent (i.e. gamma ├)
(一个集合是consistent的意思是从它里面的元素不会导出contradiction)
因为一阶逻辑的证明长度是有限的，因此我们必定能从gamma里面挑出有限的元素、经过
有限的步骤来证明gamma会导出矛盾
现在把这个证明里面出现的premises全部挑出来(*只会有有限多的)当成一个集合gamma*
我们可以从这个gamma*导出矛盾(跟gamma矛盾的证明有一样的前提跟步骤)
也就是说gamma*会是inconsistent
而根据soundness，我们会得到gamma*也是not satisfiable
但由于gamma*的元素都是从gamma里挑出来的，因此这个set会是gamma的finite subset
但这与一开始假设的"all finite subsets of gamma are satisfiable"矛盾
因此，if gamma is not satisfiable, then there must be a finite subset of
gamma which is not satisfiable.
小弟我文组的 有错请鞭小力一点
谢谢大家