Zulip Chat Archive
Stream: lean4
Topic: Preserving a property through inductive constructions
Nicolas Rouquette (Jan 29 2023 at 22:01):
Suppose we have a list l
for which we have a hypothesis like this:
∃ x, x ∈ l ∧ p x
where p
is a predicate over the elements of l
.
Now suppose I have an inductive constructor that operates on such lists.
I would like to proove that such constructors preserve p
.
Here is an MWE that is specific to my use case:
import Std.Data.AssocList
import Std.Data.List.Lemmas
namespace MWE11
theorem cond_eq_ite (c : Bool) (a b : α) : cond c a b = if c then a else b := by cases c <;> rfl
theorem cond_decide {α} (p : Prop) [Decidable p] (t e : α) : cond (decide p) t e = if p then t else e := by
by_cases p <;> simp [*]
-- https://leanprover.zulipchat.com/#narrow/stream/270676-lean4/topic/Problems.20simplifying.20.20conditions.20with.20hypotheses/near/324212540
@[simp] theorem beq_eq_eq [DecidableEq α] (x y : α) :
(x == y) = decide (x = y) := rfl
abbrev Strings := List String
def addSubSup: String → String → Std.AssocList String Strings → Std.AssocList String Strings
| sub, sup, .nil => .cons sub [sup] .nil
| sub, sup, .cons a as tail => bif a = sub then .cons sub (as.insert sup) tail else .cons a as (addSubSup sub sup tail)
@[simp] theorem addSubSup.sub_sup
(sub sup: String)
(tail: Std.AssocList String Strings)
(h: ∃ x, x ∈ Std.AssocList.toList tail ∧ x.fst = sup)
: ∃ x, x ∈ Std.AssocList.toList (addSubSup sub sup tail) ∧ x.fst = sup
:= by
sorry
end MWE11
Intuitively, addSubSup
only preprends entries to the 3rd argument; so if that 3rd argument satisfies a property, then the result of the constructors should also satisfy the same property.
Any suggestions about proving this sort of thing?
Last updated: Dec 20 2023 at 11:08 UTC