是什么让自然数在超时方面如此特别？

Question

在之前的中，我收到了以下关于如何创建 n 维欧几里得的回复 space：

def euclidean_space (n : ℕ) : Type := set (repeated_prod n ℝ)

并且我收到了以下关于创建欧几里德 space 子集的回复：

def euclidean_subset (M : Type) := ∃ (n : ℕ) (P : euclidean_space n → Prop), M = subtype P

运行通过我修改后的代码编译的所有内容都很棒并且相信答案（至少，大部分）是正确的。我想尝试运行对代码进行一些基本检查。特别是，我希望：

#reduce euclidean_space 2

给予：

ℝ × ℝ

好吧，它没有。它超时了。然后我继续尝试其他一些设置。我将 euclidean_space 修改为：

def euclidean_space (n : ℕ) : Type := set (repeated_prod n ℕ)

虽然，不再忠实于它的名字，但应该期待

#reduce euclidean_space 2

给予：

ℕ × ℕ

嗯，几乎，它给出了：

ℕ × ℕ → Prop

鉴于结果，我删除了 set 调用并将 euclidean_space 重新定义为：

def euclidean_space (n : ℕ) : Type := (repeated_prod n ℕ)

减少产生了预期的结果。然后我回去用 ℝ 替换了 ℕ:

def euclidean_space (n : ℕ) : Type := (repeated_prod n ℝ)

euclidean_subset 仍然编译，但是 #reduce 仍然使用 ℝ 给出超时。为什么ℕ不会超时？

Answer 1

real是一个定义，所以也会减少：

def real := @cau_seq.completion.Cauchy ℚ _ _ _ abs _

实际上，这是一个复杂的（没有双关语意）定义，可能依赖于数十个或数百个其他定义。递归减少所有这些将花费很长时间，并产生一些巨大且完全无用的输出。

另一方面，nat 是无参数归纳类型。那里没有什么可以减少的。

What makes the natural numbers so special with regards to timing out?