如何在 Isabelle 中定义一个 function/map 从一组到另一组 (f: A -> B)？

Question

Isabelle/HOL (2021) 中定义函数 f 从特定集合 A 到另一个集合 B 的正确方法是什么?

从数学上讲，函数 f: A -> B 通常被定义为从其域 A 到其共同域 B 的映射。并且函数 f 被定义为 A × B 中的一种特殊关系，其中只有一个 y ∈ B 满足 x f y 对于每个 x ∈ A.

但是在Isabelle/HOL中，函数似乎是根据计算来定义的，例如f x = Suc x。似乎没有地方可以明确地定义域和共同域。

我只是想知道是否有一种传统的方法可以在 Isabelle 中定义函数，使其具有域和共同域并与上述关系的定义兼容。

Answer 1

背景

如您所见，在 Isabelle/HOL 中，函数通常是 'a⇒'b 类型的项，其中 'a 和 'b 可以是任意类型。因此，Isabelle 中的所有功能都是完整的。 Joachim Breitner 的博客 post 很好地解释了这一点：link。我不会重述博客内容的任何内容post：相反，我将专注于您在问题中提出的问题。

函数的常规定义

我知道传统数学中定义函数的两种方法（这里我使用术语“传统数学”来表示在某些集合论基础中暴露的数学）：

例如，根据 [1，第 6 章]，函数只是一个单值二元关系。
一些作者[2,Chapter 2]通过定义定义一个函数及其定义域和余定义域，即一个函数变成一个三元组(A,B,r)，其中r⊆A×B仍然是单值的二元关系，A 恰好是关系的定义域。

您可以找到一些进一步的讨论 here。如果函数是二元关系，则定义域和范围通常与函数表示的关系的定义域和范围相同。然而，谈论这样一个实体的密码域毫无意义。如果函数定义为三元组 (A,B,r)，则陪域是分配的集合 B.

Isabelle/HOL I: 作为关系

Isabelle/HOL已经在理论Relation.thy中给出了单值关系概念的定义。该定义隐含在谓词的定义中 single_valued:

definition single_valued :: "('a × 'b) set ⇒ bool"
  where "single_valued r ⟷ (∀x y. (x, y) ∈ r ⟶ (∀z. (x, z) ∈ r ⟶ y = z))"

因此，实际上，单值关系是 ('a × 'b) set 类型的项，因此它满足谓词 single_valued。还提供了关于该定义的一些初步结果。

当然，这个谓词可以用于创建从'a到'b的“函数作为关系”的新类型构造函数。有关更多信息，请参阅 Isabelle [3, section 11.7] 的官方文档和文章 Lifting and Transfer: A Modular Design for Quotients in Isabelle/HOL [4, section 3]在 Isabelle/HOL 中定义新的类型构造函数。这种类型在某处已经可用的可能性不大，但在快速搜索源后我找不到它（或任何类似的东西）。当然，几乎没有什么可以阻止人们提供一种类型来捕获答案的前一小节中给出的函数的任一集合论定义。我想，像下面这样的定义是可行的，但我还没有测试过：

typedef ('a, 'b) relfun = 
  ‹
    {
      (A::'a set, B::'b set, f::('a × 'b) set). 
        single_valued f ∧ Domain f = A ∧ Range f ⊆ B
    }
  ›
proof-
  let ?r = ‹({}, {}, {})›
  show ?thesis unfolding single_valued_def by (intro exI[of _ ?r]) simp
qed

Isabelle/HOL二：FuncSet等限制

虽然 Isabelle/HOL 中的函数是全部的，但仍然可以使用多种方法模拟将函数限制在某个预定义域（即 UNIV::'a set 的适当子集） .一种常见的方法（在理论 HOL-Library.FuncSet 中公开）是强制函数在部分域上为 undefined。我在下面的回答更详细地解释了这一点。

Isabelle/HOL 三：HOL/ZF，HOL 和 HOTG 中的 ZFC

这可能有点离题。然而，存在 Isabelle/HOL 的扩展，具有不同强度的集合论公理 [5,6,7]。例如，HOL[6]中的ZFC提供了某种代表冯·诺依曼宇宙的类型V。现在可以定义所有内化在这种类型中的相关集合论概念，当然包括函数的任何一种常规定义。在 HOL 中的 ZFC 中，可以使用所谓的运算符 VLambda 将 HOL 中定义的函数内部化，如下所示：(F::V) = VLambda (A::V) (f::V⇒V)。现在，F 是一个内化在类型 V 中的单值二元关系，其域 A 和 ⟨x, f x⟩.

形式的值

附带说明一下，在我自己对范畴论进行形式化研究时，我在 V 上明确公开了函数的两个定义作为谓词：Category Theory for ZFC in HOL.

总结

What is the correct way in Isabelle/HOL (2021) to define a function f from a specific set A to another set B?

直接回答你的问题，我的观点是，没有单一的“正确方法”来定义从特定集合 A 到另一个集合 B 的函数。但是，你有很多选择可以探索：每个这些选项各有优缺点。

参考资料

Takeuti G，Zaring WM。公理化集合论简介。海德堡：施普林格出版社； 1971.
Goldblatt R. Topoi：逻辑的分类分析。 Mineola：多佛出版社； 2013.
Wenzel M. Isabelle/Isar 参考手册。 2019.
Huffman B, Kunčar O. 提升和转移：Isabelle/HOL 中商的模块化设计。在：Gonthier G，Norrish M，编辑。认证程序和证明。海德堡：施普林格； 2013.p。 131–46.
Obua S. Partizan Games 在 Isabelle/HOLZF。在：Barkaoui K，Cavalcanti A，Cerone A，编辑。计算的理论方面 - ICTAC 2006。柏林：施普林格； 2006.p。 272–86.
保尔森 LC。 Zermelo Fraenkel 高阶逻辑中的集合论。正式证明的存档。 2019.
Chen J、Kappelmann K、Krauss A.https://bitbucket.org/cezaryka/tyset/src [Internet]. HOTG. Available from: https://bitbucket.org/cezaryka/tyset/src。

如何在 Isabelle 中定义一个 function/map 从一组到另一组 (f: A -> B)？

How to define a function/map from one set to another (f: A -> B) in Isabelle?

isabelle