Endo不动点取值数量及EndoFix类型对应的拓扑空间探究

类型定义 #

先看我们讨论的自定义类型：

newtype EndoFix = EndoFix {appEndoFix :: EndoFix -> EndoFix}

这个类型本质是Data.Monoid中Endo类型的不动点——因为Endo a的定义是a -> a，所以Endo EndoFix就是EndoFix -> EndoFix，正好与EndoFix的结构完全对应。

构造的取值示例 #

我们可以手动构造出一系列直观的取值：

example0 = EndoFix id
example1 = EndoFix (const example0)
example2 = EndoFix (const example1)

基于这些递推构造的示例，还能通过不动点组合子得到一个极限元素：

import Data.Function
exampleOmega = fix (EndoFix . const)

核心问题解答 #

1. EndoFix对应的实际拓扑空间 #

你的直觉是对的：不存在能区分这些构造元素的半判定过程，从可观测等价的角度，这些元素本质上是同一个。在斯科特拓扑（Scott Topology）的框架下（这是函数式语言语义中常用的拓扑模型），EndoFix对应的商空间（按可观测等价划分）是一个平凡单点拓扑空间。

原因很简单：任何试图区分example0、example1、exampleOmega的操作，都需要无限次函数应用才能得到差异，但半判定过程只能在有限步骤内给出结果，因此永远无法完成区分。从域论的角度，这些元素都属于同一个等价类，对应的拓扑空间没有非平凡的开集，只有空集和全集。

2. Endo的不动点有多少个取值 #

这个问题需要分两个层面来看：

• 纯集合论层面：如果把EndoFix看作普通集合，它的基数等于连续统的基数（2^{ℵ₀）——因为每个EndoFix元素对应一个从自身到自身的函数，而满足κ=κ}κ的最小基数就是2^ℵ₀（更大的不可数基数也满足，但在标准集合论假设下，最小的就是连续统基数）。
• 可观测等价层面：由于不存在能区分不同元素的半判定过程，所有EndoFix的取值在“可有效区分”的意义下只有1个。

内容的提问来源于stack exchange，提问作者Dannyu NDos