Coq 中子列表的归纳命题
Inductive proposition for sublists in Coq
我正在努力想出一个列表的子列表的概念，它是通过删除列表中的元素创建的（以便保留顺序）。我需要想出一个归纳命题来决定 l1 是否是 l2 的子列表。
到目前为止：
- 我知道空列表是所有列表的子列表。
- 所有列表都是它们自己的子列表。
- 如果已知 l1 是 l2 的子列表，则将相同列表附加到 l1 和 l2 的头部或尾部的列表将导致前者是后者的子列表
- 现在是困难的部分。如何证明像 ["x";"y"] 这样的列表是 ["a";"x";"z";"y"] 的子列表？
语法类似于
Inductive Sublist {X : Type} : list X -> list X -> Prop := ..
有人可以帮我吗？
你已经非正式地做了什么？只使用你的三个规则。如果你不能管理它意味着你可能有一个太复杂/不完整的定义。
我认为你可以专注于你的例子，同时牢记列表是如何构建的，而不是试图去思考所有那些复杂的例子。
为什么 [ x ; y ] 是 [ a ; x ; y ; z ] 的子列表？因为（没有第二个列表的头部）[ x ; y ] 是 [ x ; y ; z ] 的子列表，那是因为 [ y ] 是 [ y ; z ] 的子列表，这是因为 [] 是 [ z ] 的子列表，它始终成立。
你看到规律了吗？
我正在努力想出一个列表的子列表的概念，它是通过删除列表中的元素创建的（以便保留顺序）。我需要想出一个归纳命题来决定 l1 是否是 l2 的子列表。
到目前为止：
- 我知道空列表是所有列表的子列表。
- 所有列表都是它们自己的子列表。
- 如果已知 l1 是 l2 的子列表，则将相同列表附加到 l1 和 l2 的头部或尾部的列表将导致前者是后者的子列表
- 现在是困难的部分。如何证明像 ["x";"y"] 这样的列表是 ["a";"x";"z";"y"] 的子列表？
语法类似于 Inductive Sublist {X : Type} : list X -> list X -> Prop := ..
有人可以帮我吗？
你已经非正式地做了什么？只使用你的三个规则。如果你不能管理它意味着你可能有一个太复杂/不完整的定义。
我认为你可以专注于你的例子，同时牢记列表是如何构建的，而不是试图去思考所有那些复杂的例子。
为什么 [ x ; y ] 是 [ a ; x ; y ; z ] 的子列表？因为（没有第二个列表的头部）[ x ; y ] 是 [ x ; y ; z ] 的子列表，那是因为 [ y ] 是 [ y ; z ] 的子列表，这是因为 [] 是 [ z ] 的子列表，它始终成立。
你看到规律了吗？