1

我正在阅读有关指称语义的 Haskell wikibook 部分,我有点坚持这个练习:

证明从 开始的不动点迭代得到的不动点也是最小的,它比任何其他不动点都小。(提示:是我们 cpo 的最小元素,g 是单调的)。

以下陈述定义了导致练习的概念的核心(我认为):

其中 f 是阶乘函数,并且显示为 g 的不动点,假设 g 是连续的。

我想我基本上理解了显示 g(f) = f 的部分,但我真的不知道该练习什么。据我了解,阶乘函数 f 是最小不动点(至少基于运算符),但我完全不清楚将函数与 进行比较意味着什么(直观地),更不用说我如何找到不动点了除了示例中显示的最小不动点。

我知道这比其他所有事情都少,而且我知道由于 g(x) 是单调的,如果我将它应用于两件事,其中一个小于另一个,结果仍然会遵循这个顺序。

我想我会从取一些函数 f' 并假设开始证明。如果是这样,通过 g 的单调性,我可以证明. 如果我可以证明 g(f') = g(f) 或 f' = f 我认为证明是完整的,但我不知道如何证明这一点。

4

1 回答 1

4

x为序列的 sup/least 上限bot, g(bot), g(g(bot)), ...。设yg(单调) 的任意不动点。我们想证明这一点x <= y

通过对迭代次数的归纳,很容易看出序列中的每个元素都是<= y. 事实上,它微不足道地成立bot,如果z<= y单调性,我们得到g(z) <= g(y) = y

因此,y是序列的上限。但是x是最少的,所以x <= y。QED。

于 2015-10-01T13:50:26.857 回答