如何证明Isabelle/HOL中反函数的存在？
How to prove the existence of inverse functions in Isabelle/HOL?
我正在尝试证明以下关于双射函数反函数存在性的基本定理（用Isabelle/HOL学习定理证明）：
For any set S and its identity map 1_S, α:S→T is bijective iff there
exists a map β: T→S such that βα=1_S and αβ=1_S.
以下是我在尝试定义相关内容（包括 and their inverses）之后到目前为止所得到的。但是由于我对 Isabelle and/or Isar.
缺乏了解，我陷入了困境并且无法取得太大进展
theory Test
imports Main
"HOL.Relation"
begin
lemma bij_iff_ex_identity : "bij_betw f A B ⟷ (∃ g. g∘f = restrict id B ∧ f∘g = restrict id A)"
unfolding bij_betw_def inj_on_def restrict_def iffI
proof
let ?g = "restrict (λ y. (if f x = y then x else undefined)) B"
assume "(∀x∈A. ∀y∈A. f x = f y ⟶ x = y)"
have "?g∘f = restrict id B"
proof
(* cannot prove this *)
end
在上面，我试图给出一个明确的存在性见证（即原函数f的反函数g）。我有几个关于证明的问题。
是否以 Isabelle 术语正确定义了概念（函数、反函数等）。
如何扩展相关定义，然后用函数应用来简化它们。我关注了 Isabelle (2021) examples/tutorials 中关于应用式简化和结构化式 Isar 证明的一些内容，但无法流畅地使用 Isar 证明。一旦我开始证明命令，我不知道如何简化或进一步移动。
Isar 有了 assumes ... shows ... 的新方法来陈述定理。是否像上面的例子一样支持证明 iff (⟷)？没有它，就无法访问 assms 等，是否有必要 assume 证明期间除了结论之外的所有内容。
谁能帮忙解释一下上面关于反函数的存在性证明是如何完成的？
lemma bij_iff_ex_identity : "bij_betw f A B ⟷ (∃ g. g∘f = restrict id B ∧ f∘g = restrict id A)"
我认为这不是您想要的，我怀疑这是真的。 g∘f = restrict id B 并不意味着 g∘f 和 id 在 B 上相等。表示总函数g∘f（HOL中只有总函数）等于总函数restrict id B。后者 returns id x 在 x∈B 上 undefined 否则。所以为了使这个等式成立，只要 f 的输入不在 B 中，g 就需要输出 undefined。但是 g 怎么会知道呢！
如果你想用restrict，你可以写restrict (g∘f) B = restrict id B。但就个人而言，我宁愿选择更简单的 (∀x∈B. (g∘f) x = x).
所以修正后的定理是：
lemma bij_iff_ex_identity : "bij_betw f A B ⟷ (∃ g. (∀x∈A. (g∘f) x = x) ∧ (∀y∈B. (f∘g) y = y))"
（这仍然是错误的，顺便说一下，正如 quickcheck 在 Isabelle/jEdit 中告诉我的那样，请参阅输出 window。如果 A 有一个元素并且 B是空的，f 不能是双射。所以你尝试的定理实际上在数学上是不正确的。我不会尝试修复它，但只回答剩下的行。
unfolding bij_betw_def inj_on_def restrict_def iffI
这里的iffI没有作用。展开只能应用形式为 A = B 的定理（无条件重写规则）。 iffI 不是那种形式。 （用thm iffI看。）
proof
就我个人而言，我不使用裸形式 proof，但总是使用 proof - 或 proof (some method)。因为 proof 只是应用了一些默认方法（在这种情况下，等同于 (rule iffI)，所以我认为最好将其显式化。proof - 只是开始证明而不应用额外的方法。
let ?g = "restrict (λ y. (if f x = y then x else undefined)) B"
这里有一个未绑定的变量 x。 （注意 IDE 中的背景颜色。）这很可能不是您想要的。形式上，它是允许的，但 x 将被视为某个任意常量。
一般来说，我认为没有任何方法可以简单地定义 g（即，仅使用量词和函数应用程序以及 if-then-else）。我认为定义逆的唯一方法（即使你知道它存在）是使用 THE 运算符，因为你需要说 g y 是“the” x这样 f x = y。 （然后在稍后的证明中，您将 运行 变成证明义务，证明它确实存在并且它是唯一的。）参见 Hilbert_Choice.thy 中 inv_into 的定义（除了它使用 SOME 而不是 THE）。也许对于初学者来说，尝试只使用现有的 inv_into 常量来做证明。
assume "(∀x∈A. ∀y∈A. f x = f y ⟶ x = y)"
所有 assume 命令必须具有与证明目标完全相同的假设。您可以通过临时编写命令 show A for A 来测试您是否写对了（这是一个无法证明的目标，但是，它会完成证明，因此它会诱使 Isabelle 检查是否正确）。如果这个命令没有报错，那么你的 assumes 是对的。在你的情况下，你没有，它应该是 (∀x∈A. ∀y∈A. f x = f y ⟶ x = y) ∧ f ' A = B。 （' 是这里的反引号。标记不让我写它。）
我的建议：首先尝试使用 bij 而不是 bij_betw 来证明。 （如果你想作弊，一个方向是 BNF_Fixpoint_Base.o_bij。）
完成后，您可以尝试概括。
我同意 Dominique Unruh 的深刻见解。但是，我想提一下，Isabelle/HOL 的主库的源代码中已经存在一个定理，它捕捉了您试图证明的定理背后的思想。事实上，它至少以两种不同的格式存在：让我将它们命名为传统的 Isabelle/HOL 格式和规范的 FuncSet 格式。对于前者，见定理bij_betw_iff_bijections:
"bij_betw f A B ⟷ (∃g. (∀x ∈ A. f x ∈ B ∧ g(f x) = x) ∧ (∀y ∈ B. g y ∈ A ∧ f(g y) = y))"
FuncSet的情况有点复杂。似乎不存在一个单一的定理来捕捉这个想法。但是，定理 bij_betwI、bij_betw_imp_funcset 和 inv_into_funcset 加在一起几乎等同于您要陈述的定理。让我提供一个草图，说明如何以一种在 FuncSet 意义上被认为是合理规范的方式表达这个定理（尝试自己证明）：
lemma bij_betw_iff:
shows "bij_betw f A B ⟷
(
∃g.
(∀x. x∈A ⟶ g (f x) = x) ∧
(∀y. y∈B ⟶ f (g y) = y) ∧
f ∈ A → B ∧
g ∈ B → A
)"
sorry
我还想重复 Dominique Unruh 给出的建议，并提供几点补充意见：
My recommendation: Try the proof with bij instead of bij_betw first.
的确，这是一个非常好的主意。通常，通过尝试将问题限制在显式定义的集合 A 和 B，而不是直接使用类型，您触及了一个称为 relativization[=78] 的主题=] 在逻辑上。例如，对于温和的外行人的介绍，请参见 https://leanprover.github.io/logic_and_proof/first_order_logic.html [1]，对于在集合论背景下稍微更全面的介绍，请参见 [2，第 12 章]。正如您现在可能已经注意到的那样，将 Isabelle/HOL 中的定理相对化并不那么容易，并且需要额外的证明工作。
但是，存在 Isabelle/HOL 的扩展，允许自动进行定理相对化过程。有关此扩展的更多信息，请参阅 Ondřej Kunčar 和 Andrei Popescu [3] 在 Higher-Order Logic 中从类型到集合的文章 。该框架也有一个大规模的应用实例[4]。独立地，我正在努力使这个扩展更多 user-friendly 并且非常缓慢地接近我努力的最后阶段：参见 https://gitlab.com/user9716869/tts_extension。因此，原则上，如果你知道如何使用 Types-To-Sets 并且你接受它的公理，那么用 bij 证明定理就足够了，例如
"bij f ⟷ (∃g. (∀x. g (f x) = x) ∧ (∀y. f (g y) = y))",
然后，定理如
bij_betw_iff_bijections 和 bij_betw_iff 可以一键免费自动合成（几乎...）。
最后，为了完整起见，让我针对您的疑问提出我自己的建议（尽管，正如我提到的，我同意 Dominique Unruh 所说的一切）
how to expand the relevant definitions and then simplify them with
function applications. I have followed some Isabelle (2021)
examples/tutorials about both the apply-style simp, and structured
style Isar proof but couldn't use the Isar proof fluently. Once I
started the proof command, I don't know how to simp or move any
further.
我相信学习您想要学习的东西的最佳方法是完成 Tobias Nipkow 和 Gerwin Klein 具体语义学 一书中的练习 [5]。此外，我还会查看 Tobias Nipkow 等人 [6] 的 A Proof Assistant for Higher-Order Logic（它有点过时，但我发现它特别适用于学习 apply 式 scripting/direct 规则应用）。顺便说一句，我自己 self-taught 从这些书中读到的 Isabelle 几乎没有任何形式化方法方面的经验。
Isar has the new way of assumes ... shows ... for stating the theorem.
Is there similar support for proving iff's (⟷) like the example above?
Without it, there is no access to assms etc., and is it necessary to
assume everything except the conclusion during the proof.
我会将 Dominique Unruh 给出的建议更明确：为此使用 rule iffI 或 intro iffI。
Edit. 当您使用 rule iffI（或类似的）开始您的结构化 Isar 证明时，您需要为每个子目标（使用 assume ... show ...范式）。但是，有一种工具可以自动生成此类样板 Isar 代码。它叫做Sketch-and-Explore，你可以在Isabelle/HOL的主库目录HOL/ex中找到它。在这种情况下，您需要做的就是键入 sketch(rule iffI)，然后将为每个子目标自动生成 assume/show 范式。
参考资料
- Avigad J、Lewis RY 和 van Doorn F. 逻辑与证明。
- Jech T. 集合论。第三版。海德堡：施普林格； 2006. (纯数学和应用数学, 系列专着和教科书).
- Kunčar O，Popescu A。Higher-Order 逻辑中通过局部类型定义从类型到集合。自动推理杂志。 2019;62(2):237–60.
- Immler F, Zhan B. Isabelle/HOL 中线性代数的平滑流形和类型集。在：第 8 届 ACM SIGPLAN 认证程序和证明国际会议。纽约：ACM； 2019.p。 65–77。 (CPP 2019).
- Nipkow T, Klein G. 具体语义 Isabelle/HOL。海德堡：Springer-Verlag； 2017. (http://concrete-semantics.org/)
- Nipkow T、Paulson LC、Wenzel M。 Higher-Order 逻辑的证明助手。海德堡：Springer-Verlag； 2017.
我正在尝试证明以下关于双射函数反函数存在性的基本定理（用Isabelle/HOL学习定理证明）：
For any set S and its identity map 1_S, α:S→T is bijective iff there exists a map β: T→S such that βα=1_S and αβ=1_S.
以下是我在尝试定义相关内容（包括
theory Test
imports Main
"HOL.Relation"
begin
lemma bij_iff_ex_identity : "bij_betw f A B ⟷ (∃ g. g∘f = restrict id B ∧ f∘g = restrict id A)"
unfolding bij_betw_def inj_on_def restrict_def iffI
proof
let ?g = "restrict (λ y. (if f x = y then x else undefined)) B"
assume "(∀x∈A. ∀y∈A. f x = f y ⟶ x = y)"
have "?g∘f = restrict id B"
proof
(* cannot prove this *)
end
在上面，我试图给出一个明确的存在性见证（即原函数f的反函数g）。我有几个关于证明的问题。
是否以 Isabelle 术语正确定义了概念（函数、反函数等）。
如何扩展相关定义，然后用函数应用来简化它们。我关注了 Isabelle (2021) examples/tutorials 中关于应用式简化和结构化式 Isar 证明的一些内容，但无法流畅地使用 Isar 证明。一旦我开始证明命令，我不知道如何简化或进一步移动。
Isar 有了
assumes ... shows ...的新方法来陈述定理。是否像上面的例子一样支持证明 iff (⟷)？没有它，就无法访问assms等，是否有必要assume证明期间除了结论之外的所有内容。
谁能帮忙解释一下上面关于反函数的存在性证明是如何完成的？
lemma bij_iff_ex_identity : "bij_betw f A B ⟷ (∃ g. g∘f = restrict id B ∧ f∘g = restrict id A)"
我认为这不是您想要的，我怀疑这是真的。 g∘f = restrict id B 并不意味着 g∘f 和 id 在 B 上相等。表示总函数g∘f（HOL中只有总函数）等于总函数restrict id B。后者 returns id x 在 x∈B 上 undefined 否则。所以为了使这个等式成立，只要 f 的输入不在 B 中，g 就需要输出 undefined。但是 g 怎么会知道呢！
如果你想用restrict，你可以写restrict (g∘f) B = restrict id B。但就个人而言，我宁愿选择更简单的 (∀x∈B. (g∘f) x = x).
所以修正后的定理是：
lemma bij_iff_ex_identity : "bij_betw f A B ⟷ (∃ g. (∀x∈A. (g∘f) x = x) ∧ (∀y∈B. (f∘g) y = y))"
（这仍然是错误的，顺便说一下，正如 quickcheck 在 Isabelle/jEdit 中告诉我的那样，请参阅输出 window。如果 A 有一个元素并且 B是空的，f 不能是双射。所以你尝试的定理实际上在数学上是不正确的。我不会尝试修复它，但只回答剩下的行。
unfolding bij_betw_def inj_on_def restrict_def iffI
这里的iffI没有作用。展开只能应用形式为 A = B 的定理（无条件重写规则）。 iffI 不是那种形式。 （用thm iffI看。）
proof
就我个人而言，我不使用裸形式 proof，但总是使用 proof - 或 proof (some method)。因为 proof 只是应用了一些默认方法（在这种情况下，等同于 (rule iffI)，所以我认为最好将其显式化。proof - 只是开始证明而不应用额外的方法。
let ?g = "restrict (λ y. (if f x = y then x else undefined)) B"
这里有一个未绑定的变量 x。 （注意 IDE 中的背景颜色。）这很可能不是您想要的。形式上，它是允许的，但 x 将被视为某个任意常量。
一般来说，我认为没有任何方法可以简单地定义 g（即，仅使用量词和函数应用程序以及 if-then-else）。我认为定义逆的唯一方法（即使你知道它存在）是使用 THE 运算符，因为你需要说 g y 是“the” x这样 f x = y。 （然后在稍后的证明中，您将 运行 变成证明义务，证明它确实存在并且它是唯一的。）参见 Hilbert_Choice.thy 中 inv_into 的定义（除了它使用 SOME 而不是 THE）。也许对于初学者来说，尝试只使用现有的 inv_into 常量来做证明。
assume "(∀x∈A. ∀y∈A. f x = f y ⟶ x = y)"
所有 assume 命令必须具有与证明目标完全相同的假设。您可以通过临时编写命令 show A for A 来测试您是否写对了（这是一个无法证明的目标，但是，它会完成证明，因此它会诱使 Isabelle 检查是否正确）。如果这个命令没有报错，那么你的 assumes 是对的。在你的情况下，你没有，它应该是 (∀x∈A. ∀y∈A. f x = f y ⟶ x = y) ∧ f ' A = B。 （' 是这里的反引号。标记不让我写它。）
我的建议：首先尝试使用 bij 而不是 bij_betw 来证明。 （如果你想作弊，一个方向是 BNF_Fixpoint_Base.o_bij。）
完成后，您可以尝试概括。
我同意 Dominique Unruh 的深刻见解。但是，我想提一下，Isabelle/HOL 的主库的源代码中已经存在一个定理，它捕捉了您试图证明的定理背后的思想。事实上，它至少以两种不同的格式存在：让我将它们命名为传统的 Isabelle/HOL 格式和规范的 FuncSet 格式。对于前者，见定理bij_betw_iff_bijections:
"bij_betw f A B ⟷ (∃g. (∀x ∈ A. f x ∈ B ∧ g(f x) = x) ∧ (∀y ∈ B. g y ∈ A ∧ f(g y) = y))"
FuncSet的情况有点复杂。似乎不存在一个单一的定理来捕捉这个想法。但是，定理 bij_betwI、bij_betw_imp_funcset 和 inv_into_funcset 加在一起几乎等同于您要陈述的定理。让我提供一个草图，说明如何以一种在 FuncSet 意义上被认为是合理规范的方式表达这个定理（尝试自己证明）：
lemma bij_betw_iff:
shows "bij_betw f A B ⟷
(
∃g.
(∀x. x∈A ⟶ g (f x) = x) ∧
(∀y. y∈B ⟶ f (g y) = y) ∧
f ∈ A → B ∧
g ∈ B → A
)"
sorry
我还想重复 Dominique Unruh 给出的建议，并提供几点补充意见：
My recommendation: Try the proof with bij instead of bij_betw first.
的确，这是一个非常好的主意。通常，通过尝试将问题限制在显式定义的集合 A 和 B，而不是直接使用类型，您触及了一个称为 relativization[=78] 的主题=] 在逻辑上。例如，对于温和的外行人的介绍，请参见 https://leanprover.github.io/logic_and_proof/first_order_logic.html [1]，对于在集合论背景下稍微更全面的介绍，请参见 [2，第 12 章]。正如您现在可能已经注意到的那样，将 Isabelle/HOL 中的定理相对化并不那么容易，并且需要额外的证明工作。
但是，存在 Isabelle/HOL 的扩展，允许自动进行定理相对化过程。有关此扩展的更多信息，请参阅 Ondřej Kunčar 和 Andrei Popescu [3] 在 Higher-Order Logic 中从类型到集合的文章 。该框架也有一个大规模的应用实例[4]。独立地，我正在努力使这个扩展更多 user-friendly 并且非常缓慢地接近我努力的最后阶段：参见 https://gitlab.com/user9716869/tts_extension。因此，原则上，如果你知道如何使用 Types-To-Sets 并且你接受它的公理，那么用 bij 证明定理就足够了，例如
"bij f ⟷ (∃g. (∀x. g (f x) = x) ∧ (∀y. f (g y) = y))",
然后，定理如
bij_betw_iff_bijections 和 bij_betw_iff 可以一键免费自动合成（几乎...）。
最后，为了完整起见，让我针对您的疑问提出我自己的建议（尽管，正如我提到的，我同意 Dominique Unruh 所说的一切）
how to expand the relevant definitions and then simplify them with function applications. I have followed some Isabelle (2021) examples/tutorials about both the apply-style simp, and structured style Isar proof but couldn't use the Isar proof fluently. Once I started the proof command, I don't know how to simp or move any further.
我相信学习您想要学习的东西的最佳方法是完成 Tobias Nipkow 和 Gerwin Klein 具体语义学 一书中的练习 [5]。此外，我还会查看 Tobias Nipkow 等人 [6] 的 A Proof Assistant for Higher-Order Logic（它有点过时，但我发现它特别适用于学习 apply 式 scripting/direct 规则应用）。顺便说一句，我自己 self-taught 从这些书中读到的 Isabelle 几乎没有任何形式化方法方面的经验。
Isar has the new way of assumes ... shows ... for stating the theorem. Is there similar support for proving iff's (⟷) like the example above? Without it, there is no access to assms etc., and is it necessary to assume everything except the conclusion during the proof.
我会将 Dominique Unruh 给出的建议更明确：为此使用 rule iffI 或 intro iffI。
Edit. 当您使用 rule iffI（或类似的）开始您的结构化 Isar 证明时，您需要为每个子目标（使用 assume ... show ...范式）。但是，有一种工具可以自动生成此类样板 Isar 代码。它叫做Sketch-and-Explore，你可以在Isabelle/HOL的主库目录HOL/ex中找到它。在这种情况下，您需要做的就是键入 sketch(rule iffI)，然后将为每个子目标自动生成 assume/show 范式。
参考资料
- Avigad J、Lewis RY 和 van Doorn F. 逻辑与证明。
- Jech T. 集合论。第三版。海德堡：施普林格； 2006. (纯数学和应用数学, 系列专着和教科书).
- Kunčar O，Popescu A。Higher-Order 逻辑中通过局部类型定义从类型到集合。自动推理杂志。 2019;62(2):237–60.
- Immler F, Zhan B. Isabelle/HOL 中线性代数的平滑流形和类型集。在：第 8 届 ACM SIGPLAN 认证程序和证明国际会议。纽约：ACM； 2019.p。 65–77。 (CPP 2019).
- Nipkow T, Klein G. 具体语义 Isabelle/HOL。海德堡：Springer-Verlag； 2017. (http://concrete-semantics.org/)
- Nipkow T、Paulson LC、Wenzel M。 Higher-Order 逻辑的证明助手。海德堡：Springer-Verlag； 2017.