internlm/Lean-Github huggingface dataset:
Theorem: List.map_mem_id
Proof state before:
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1 : ∀ x ∈ hd :: tl, f x = x
⊢ map f (hd :: tl) = hd :: tl
Tactic:
simp at h1
Proof state after:
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1 : f hd = hd ∧ ∀ a ∈ tl, f a = a
⊢ map f (hd :: tl) = hd :: tl
Theorem: List.map_mem_id
Proof state before:
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1 : f hd = hd ∧ ∀ a ∈ tl, f a = a
⊢ map f (hd :: tl) = hd :: tl
Tactic:
cases h1
Proof state after:
case intro
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
left✝ : f hd = hd
right✝ : ∀ a ∈ tl, f a = a
⊢ map f (hd :: tl) = hd :: tl
Theorem: List.map_mem_id
Proof state before:
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1_left : f hd = hd
h1_right : ∀ a ∈ tl, f a = a
⊢ map f (hd :: tl) = hd :: tl
Tactic:
simp
Proof state after:
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1_left : f hd = hd
h1_right : ∀ a ∈ tl, f a = a
⊢ f hd = hd ∧ map f tl = tl
Theorem: List.map_mem_id
Proof state before:
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1_left : f hd = hd
h1_right : ∀ a ∈ tl, f a = a
⊢ f hd = hd ∧ map f tl = tl
Tactic:
constructor
Proof state after:
case left
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1_left : f hd = hd
h1_right : ∀ a ∈ tl, f a = a
⊢ f hd = hd

case right
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1_left : f hd = hd
h1_right : ∀ a ∈ tl, f a = a
⊢ map f tl = tl
Theorem: List.map_mem_id
Proof state before:
case left
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1_left : f hd = hd
h1_right : ∀ a ∈ tl, f a = a
⊢ f hd = hd
Tactic:
exact h1_left
Proof state after:
no goals
Theorem: List.map_mem_id
Proof state before:
case right
α : Type
f : α → α
hd : α
tl : List α
ih : (∀ x ∈ tl, f x = x) → map f tl = tl
h1_left : f hd = hd
h1_right : ∀ a ∈ tl, f a = a
⊢ map f tl = tl
Tactic:
exact ih h1_right
Proof state after:
no goals
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs ys : List α
h1 : xs.length = ys.length
h2 : xs.Nodup
h3 : ys.Nodup
⊢ ∃ f, InjOn f xs ∧ map f xs = ys
Tactic:
induction xs generalizing ys
Proof state after:
case nil
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ ∃ f, InjOn f [] ∧ map f [] = ys

case cons
α : Type
inst✝ : DecidableEq α
head✝ : α
tail✝ : List α
tail_ih✝ : ∀ (ys : List α), tail✝.length = ys.length → tail✝.Nodup → ys.Nodup → ∃ f, InjOn f tail✝ ∧ map f tail✝ = ys
ys : List α
h1 : (head✝ :: tail✝).length = ys.length
h2 : (head✝ :: tail✝).Nodup
h3 : ys.Nodup
⊢ ∃ f, InjOn f (head✝ :: tail✝) ∧ map f (head✝ :: tail✝) = ys
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ ∃ f, InjOn f [] ∧ map f [] = ys
Tactic:
have s1 : ys = []
Proof state after:
case s1
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ ys = []

α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∃ f, InjOn f [] ∧ map f [] = ys
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case s1
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ ys = []

α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∃ f, InjOn f [] ∧ map f [] = ys
Tactic:
{
  apply List.eq_nil_of_length_eq_zero
  simp only [← h1]
  simp
}
Proof state after:
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∃ f, InjOn f [] ∧ map f [] = ys
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∃ f, InjOn f [] ∧ map f [] = ys
Tactic:
simp only [s1]
Proof state after:
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∃ f, InjOn f [] ∧ map f [] = []
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∃ f, InjOn f [] ∧ map f [] = []
Tactic:
apply Exists.intro id
Proof state after:
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ InjOn id [] ∧ map id [] = []
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ InjOn id [] ∧ map id [] = []
Tactic:
constructor
Proof state after:
case left
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ InjOn id []

case right
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ map id [] = []
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case s1
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ ys = []
Tactic:
apply List.eq_nil_of_length_eq_zero
Proof state after:
case s1.x
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ ys.length = 0
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case s1.x
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ ys.length = 0
Tactic:
simp only [← h1]
Proof state after:
case s1.x
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ [].length = 0
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case s1.x
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
⊢ [].length = 0
Tactic:
simp
Proof state after:
no goals
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case left
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ InjOn id []
Tactic:
simp only [List.InjOn]
Proof state after:
case left
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∀ ⦃x₁ : α⦄, x₁ ∈ [] → ∀ ⦃x₂ : α⦄, x₂ ∈ [] → id x₁ = id x₂ → x₁ = x₂
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case left
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ ∀ ⦃x₁ : α⦄, x₁ ∈ [] → ∀ ⦃x₂ : α⦄, x₂ ∈ [] → id x₁ = id x₂ → x₁ = x₂
Tactic:
simp
Proof state after:
no goals
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case right
α : Type
inst✝ : DecidableEq α
ys : List α
h1 : [].length = ys.length
h2 : [].Nodup
h3 : ys.Nodup
s1 : ys = []
⊢ map id [] = []
Tactic:
simp
Proof state after:
no goals
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys : List α
h1 : (xs_hd :: xs_tl).length = ys.length
h2 : (xs_hd :: xs_tl).Nodup
h3 : ys.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys
Tactic:
cases ys
Proof state after:
case nil
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
h2 : (xs_hd :: xs_tl).Nodup
h1 : (xs_hd :: xs_tl).length = [].length
h3 : [].Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = []

case cons
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
h2 : (xs_hd :: xs_tl).Nodup
head✝ : α
tail✝ : List α
h1 : (xs_hd :: xs_tl).length = (head✝ :: tail✝).length
h3 : (head✝ :: tail✝).Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = head✝ :: tail✝
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
h2 : (xs_hd :: xs_tl).Nodup
h1 : (xs_hd :: xs_tl).length = [].length
h3 : [].Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = []
Tactic:
case nil =>
  simp at h1
Proof state after:
no goals
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
h2 : (xs_hd :: xs_tl).Nodup
h1 : (xs_hd :: xs_tl).length = [].length
h3 : [].Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = []
Tactic:
simp at h1
Proof state after:
no goals
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
h2 : (xs_hd :: xs_tl).Nodup
ys_hd : α
ys_tl : List α
h1 : (xs_hd :: xs_tl).length = (ys_hd :: ys_tl).length
h3 : (ys_hd :: ys_tl).Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Tactic:
simp at h1
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
h2 : (xs_hd :: xs_tl).Nodup
ys_hd : α
ys_tl : List α
h3 : (ys_hd :: ys_tl).Nodup
h1 : xs_tl.length = ys_tl.length
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
h2 : (xs_hd :: xs_tl).Nodup
ys_hd : α
ys_tl : List α
h3 : (ys_hd :: ys_tl).Nodup
h1 : xs_tl.length = ys_tl.length
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Tactic:
simp at h2
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h3 : (ys_hd :: ys_tl).Nodup
h1 : xs_tl.length = ys_tl.length
h2 : xs_hd ∉ xs_tl ∧ xs_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h3 : (ys_hd :: ys_tl).Nodup
h1 : xs_tl.length = ys_tl.length
h2 : xs_hd ∉ xs_tl ∧ xs_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Tactic:
simp at h3
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2 : xs_hd ∉ xs_tl ∧ xs_tl.Nodup
h3 : ys_hd ∉ ys_tl ∧ ys_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2 : xs_hd ∉ xs_tl ∧ xs_tl.Nodup
h3 : ys_hd ∉ ys_tl ∧ ys_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Tactic:
cases h2
Proof state after:
case intro
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h3 : ys_hd ∉ ys_tl ∧ ys_tl.Nodup
left✝ : xs_hd ∉ xs_tl
right✝ : xs_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h3 : ys_hd ∉ ys_tl ∧ ys_tl.Nodup
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Tactic:
cases h3
Proof state after:
case intro
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
left✝ : ys_hd ∉ ys_tl
right✝ : ys_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ map f (xs_hd :: xs_tl) = ys_hd :: ys_tl
Tactic:
simp
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
xs_ih : ∀ (ys : List α), xs_tl.length = ys.length → xs_tl.Nodup → ys.Nodup → ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Tactic:
specialize xs_ih ys_tl h1 h2_right h3_right
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
xs_ih : ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
xs_ih : ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Tactic:
apply Exists.elim xs_ih
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
xs_ih : ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∀ (a : α → α),
    InjOn a xs_tl ∧ map a xs_tl = ys_tl → ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
xs_ih : ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∀ (a : α → α),
    InjOn a xs_tl ∧ map a xs_tl = ys_tl → ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Tactic:
intro f a1
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
xs_ih : ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys_tl
f : α → α
a1 : InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
xs_ih : ∃ f, InjOn f xs_tl ∧ map f xs_tl = ys_tl
f : α → α
a1 : InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Tactic:
clear xs_ih
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1 : InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1 : InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f, InjOn f (xs_hd :: xs_tl) ∧ f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Tactic:
simp only [List.InjOn]
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1 : InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f,
    (∀ ⦃x₁ : α⦄, x₁ ∈ xs_hd :: xs_tl → ∀ ⦃x₂ : α⦄, x₂ ∈ xs_hd :: xs_tl → f x₁ = f x₂ → x₁ = x₂) ∧
      f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1 : InjOn f xs_tl ∧ map f xs_tl = ys_tl
⊢ ∃ f,
    (∀ ⦃x₁ : α⦄, x₁ ∈ xs_hd :: xs_tl → ∀ ⦃x₂ : α⦄, x₂ ∈ xs_hd :: xs_tl → f x₁ = f x₂ → x₁ = x₂) ∧
      f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Tactic:
cases a1
Proof state after:
case intro
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
left✝ : InjOn f xs_tl
right✝ : map f xs_tl = ys_tl
⊢ ∃ f,
    (∀ ⦃x₁ : α⦄, x₁ ∈ xs_hd :: xs_tl → ∀ ⦃x₂ : α⦄, x₂ ∈ xs_hd :: xs_tl → f x₁ = f x₂ → x₁ = x₂) ∧
      f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
⊢ ∃ f,
    (∀ ⦃x₁ : α⦄, x₁ ∈ xs_hd :: xs_tl → ∀ ⦃x₂ : α⦄, x₂ ∈ xs_hd :: xs_tl → f x₁ = f x₂ → x₁ = x₂) ∧
      f xs_hd = ys_hd ∧ map f xs_tl = ys_tl
Tactic:
apply Exists.intro (Function.updateITE f xs_hd ys_hd)
Proof state after:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
⊢ (∀ ⦃x₁ : α⦄,
      x₁ ∈ xs_hd :: xs_tl →
        ∀ ⦃x₂ : α⦄,
          x₂ ∈ xs_hd :: xs_tl → Function.updateITE f xs_hd ys_hd x₁ = Function.updateITE f xs_hd ys_hd x₂ → x₁ = x₂) ∧
    Function.updateITE f xs_hd ys_hd xs_hd = ys_hd ∧ map (Function.updateITE f xs_hd ys_hd) xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
⊢ (∀ ⦃x₁ : α⦄,
      x₁ ∈ xs_hd :: xs_tl →
        ∀ ⦃x₂ : α⦄,
          x₂ ∈ xs_hd :: xs_tl → Function.updateITE f xs_hd ys_hd x₁ = Function.updateITE f xs_hd ys_hd x₂ → x₁ = x₂) ∧
    Function.updateITE f xs_hd ys_hd xs_hd = ys_hd ∧ map (Function.updateITE f xs_hd ys_hd) xs_tl = ys_tl
Tactic:
constructor
Proof state after:
case left
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
⊢ ∀ ⦃x₁ : α⦄,
    x₁ ∈ xs_hd :: xs_tl →
      ∀ ⦃x₂ : α⦄,
        x₂ ∈ xs_hd :: xs_tl → Function.updateITE f xs_hd ys_hd x₁ = Function.updateITE f xs_hd ys_hd x₂ → x₁ = x₂

case right
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
⊢ Function.updateITE f xs_hd ys_hd xs_hd = ys_hd ∧ map (Function.updateITE f xs_hd ys_hd) xs_tl = ys_tl
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case left
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
⊢ ∀ ⦃x₁ : α⦄,
    x₁ ∈ xs_hd :: xs_tl →
      ∀ ⦃x₂ : α⦄,
        x₂ ∈ xs_hd :: xs_tl → Function.updateITE f xs_hd ys_hd x₁ = Function.updateITE f xs_hd ys_hd x₂ → x₁ = x₂
Tactic:
intro x1 x1_mem x2 x2_mem
Proof state after:
case left
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
x1 : α
x1_mem : x1 ∈ xs_hd :: xs_tl
x2 : α
x2_mem : x2 ∈ xs_hd :: xs_tl
⊢ Function.updateITE f xs_hd ys_hd x1 = Function.updateITE f xs_hd ys_hd x2 → x1 = x2
Theorem: List.nodup_eq_len_imp_exists_bijon
Proof state before:
case left
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
x1 : α
x1_mem : x1 ∈ xs_hd :: xs_tl
x2 : α
x2_mem : x2 ∈ xs_hd :: xs_tl
⊢ Function.updateITE f xs_hd ys_hd x1 = Function.updateITE f xs_hd ys_hd x2 → x1 = x2
Tactic:
simp at x1_mem
Proof state after:
case left
α : Type
inst✝ : DecidableEq α
xs_hd : α
xs_tl : List α
ys_hd : α
ys_tl : List α
h1 : xs_tl.length = ys_tl.length
h2_left : xs_hd ∉ xs_tl
h2_right : xs_tl.Nodup
h3_left : ys_hd ∉ ys_tl
h3_right : ys_tl.Nodup
f : α → α
a1_left : InjOn f xs_tl
a1_right : map f xs_tl = ys_tl
x1 x2 : α
x2_mem : x2 ∈ xs_hd :: xs_tl
x1_mem : x1 = xs_hd ∨ x1 ∈ xs_tl
⊢ Function.updateITE f xs_hd ys_hd x1 = Function.updateITE f xs_hd ys_hd x2 → x1 = x2