指称语义，证明不动点迭代导致最小不动点

Question

我正在研究 denotational semantics 上的 Haskell wikibook 部分，我有点卡在这个练习中：

Prove that the fixed point obtained by fixed point iteration starting with is also the least one, that it is smaller than any other fixed point. (Hint: is the least element of our cpo and g is monotone).

以下陈述定义了导致练习的核心概念（我认为）：

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

我想我基本上理解了显示 g(f) = f 的部分，但我真的不知道该练习的内容。据我了解，阶乘函数 f 是最小不动点（至少基于 operator) but it's not at all clear to me what it means (intuitively) to compare functions with ，更不用说我如何找到示例中显示的最小不动点以外的不动点了。

我明白 小于其他一切，我明白因为 g(x) 是单调的，如果我将它应用于两个事物，其中一个小于另一个，结果将还是服从这个顺序。

我想我会从取一些函数 f' 并假设 . If that is the case, through the monotonic property of g I can show that 开始证明。如果我能证明 g(f') = g(f) 或 f' = f 必然存在，我认为证明是完整的，但我不知道如何证明。

Answer 1

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

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

所以，y是数列的上界。但是x是最少的，所以x <= y。 QED.