作者freef1y3 ( )
看板logic
标题[请益] 表示 Reflexive Transitive Closure
时间Tue Sep 1 16:55:04 2015
请问 Reflexive Transitive Closure 是否能用一阶逻辑表示呢？
也就是说，是否能给出一个一阶 Theory T 来描述 Relation R 及 R*
使得在所有 T 的 Model 中，R* 都是 R 的 Reflexive Transitive Closure？
Google 了一下好像都说不行
但是我想了一下 (好吧其实想很久) 好像可以这样表示？
∀x∀y (R*(x,y) <=> ((∃p (R(x,p) Λ R*(p,y))) Ｖ x=y))
也就是说，若 R*(x,y) 成立，要嘛 x=y，
否则就是有一个 p 使得 R(x,p) 和 R*(p,y) 都成立
再继续追 R*(p,y)，若 R*(p,y) 成立，要嘛 p=y，
否则就是有一个 p2 使得 R(p,p2) 和 R*(p2,y) 都成立
这样追下去，应该就可以确保：
若 R*(x,y) 成立，
则找的到 p1,p2,...,pi 使得 R(x,p1), R(p1,p2), ..., 一直到 R(pi,y) 都成立
因此 R* 是 R 的 Reflexive Transitive Closure
不知道这样的论述有什麽问题呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.250.41
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/logic/M.1441097707.A.533.html
1F：推 MathTurtle: 问题就在你说的"这样追下去，应该就可以确保" 09/01 20:14
2F：→ MathTurtle: 这里就不是用一阶逻辑可以表达的 09/01 20:14
3F：→ freef1y3: 可是那只是我用来解释的自然语言，没有包含在逻辑式内 09/01 20:40
4F：→ freef1y3: 还是那条逻辑式有用到什麽非一阶逻辑的东西呢？ 09/01 20:40
5F：→ freef1y3: 或者是这种可能导致无穷展开的逻辑式就不属於一阶逻辑？ 09/01 20:46
6F：推 MathTurtle: 因为你给的式子不是定义啊 ... R*出现在biconditional 09/02 00:01
7F：→ MathTurtle: 的两边 09/02 00:01
8F：→ MathTurtle: 要把它弄成定义 你会需要recursion之类的东西 09/02 00:02
9F：推 turboho: 你给的 sentence 不等价於 R* 是 R 的 ref. trns. clos. 09/02 01:17
10F：→ turboho: 考虑 R*(x,y) for every x,y and R(x,y) for x=y 09/02 01:18
12F：→ turboho: 面有人回答，你可以去看看 09/02 01:23
13F：→ freef1y3: 啊 真的耶! 感谢t大解惑~ 09/02 01:35