Double universal quantification on a list

This file provides an API for List.Forall₂ (definition in Data.List.Defs). Forall₂ R l₁ l₂ means that l₁ and l₂ have the same length, and whenever a is the nth element of l₁, and b is the nth element of l₂, then R a b is satisfied.

theorem List.forall₂_iff {α : Type u_1} {β : Type u_2} (R : α → β → Prop) : ∀ (a : List α) (a_1 : List β), List.Forall₂ R a a_1 ↔ a = [] ∧ a_1 = [] ∨ ∃ (a_2 : α), ∃ (b : β), ∃ (l₁ : List α), ∃ (l₂ : List β), R a_2 b ∧ List.Forall₂ R l₁ l₂ ∧ a = a_2 :: l₁ ∧ a_1 = b :: l₂

@[simp]

theorem List.forall₂_cons {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {a : α} {b : β} {l₁ : List α} {l₂ : List β} : List.Forall₂ R (a :: l₁) (b :: l₂) ↔ R a b ∧ List.Forall₂ R l₁ l₂

theorem List.Forall₂.imp {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {S : α → β → Prop} (H : ∀ (a : α) (b : β), R a b → S a b) {l₁ : List α} {l₂ : List β} (h : List.Forall₂ R l₁ l₂) : List.Forall₂ S l₁ l₂

theorem List.Forall₂.mp {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {S : α → β → Prop} {Q : α → β → Prop} (h : ∀ (a : α) (b : β), Q a b → R a b → S a b) {l₁ : List α} {l₂ : List β} : List.Forall₂ Q l₁ l₂ → List.Forall₂ R l₁ l₂ → List.Forall₂ S l₁ l₂

theorem List.Forall₂.flip {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {a : List α} {b : List β} : List.Forall₂ (flip R) b a → List.Forall₂ R a b

@[simp]

theorem List.forall₂_same {α : Type u_1} {Rₐ : α → α → Prop} {l : List α} : List.Forall₂ Rₐ l l ↔ ∀ (x : α), x ∈ l → Rₐ x x

theorem List.forall₂_refl {α : Type u_1} {Rₐ : α → α → Prop} [IsRefl α Rₐ] (l : List α) : List.Forall₂ Rₐ l l

@[simp]

theorem List.forall₂_eq_eq_eq {α : Type u_1} : (List.Forall₂ fun (x x_1 : α) => x = x_1) = Eq

@[simp]

theorem List.forall₂_nil_left_iff {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l : List β} : List.Forall₂ R [] l ↔ l = []

@[simp]

theorem List.forall₂_nil_right_iff {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l : List α} : List.Forall₂ R l [] ↔ l = []

theorem List.forall₂_cons_left_iff {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {a : α} {l : List α} {u : List β} : List.Forall₂ R (a :: l) u ↔ ∃ (b : β), ∃ (u' : List β), R a b ∧ List.Forall₂ R l u' ∧ u = b :: u'

theorem List.forall₂_cons_right_iff {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {b : β} {l : List β} {u : List α} : List.Forall₂ R u (b :: l) ↔ ∃ (a : α), ∃ (u' : List α), R a b ∧ List.Forall₂ R u' l ∧ u = a :: u'

theorem List.forall₂_and_left {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {p : α → Prop} (l : List α) (u : List β) : List.Forall₂ (fun (a : α) (b : β) => p a ∧ R a b) l u ↔ (∀ (a : α), a ∈ l → p a) ∧ List.Forall₂ R l u

@[simp]

theorem List.forall₂_map_left_iff {α : Type u_1} {β : Type u_2} {γ : Type u_3} {R : α → β → Prop} {f : γ → α} {l : List γ} {u : List β} : List.Forall₂ R (List.map f l) u ↔ List.Forall₂ (fun (c : γ) (b : β) => R (f c) b) l u

@[simp]

theorem List.forall₂_map_right_iff {α : Type u_1} {β : Type u_2} {γ : Type u_3} {R : α → β → Prop} {f : γ → β} {l : List α} {u : List γ} : List.Forall₂ R l (List.map f u) ↔ List.Forall₂ (fun (a : α) (c : γ) => R a (f c)) l u

theorem List.left_unique_forall₂' {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (hr : Relator.LeftUnique R) {a : List α} {b : List α} {c : List β} : List.Forall₂ R a c → List.Forall₂ R b c → a = b

theorem Relator.LeftUnique.forall₂ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (hr : Relator.LeftUnique R) : Relator.LeftUnique (List.Forall₂ R)

theorem List.right_unique_forall₂' {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (hr : Relator.RightUnique R) {a : List α} {b : List β} {c : List β} : List.Forall₂ R a b → List.Forall₂ R a c → b = c

theorem Relator.RightUnique.forall₂ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (hr : Relator.RightUnique R) : Relator.RightUnique (List.Forall₂ R)

theorem Relator.BiUnique.forall₂ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (hr : Relator.BiUnique R) : Relator.BiUnique (List.Forall₂ R)

theorem List.Forall₂.length_eq {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l₁ : List α} {l₂ : List β} : List.Forall₂ R l₁ l₂ → List.length l₁ = List.length l₂

theorem List.Forall₂.nthLe {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {x : List α} {y : List β} : List.Forall₂ R x y → ∀ ⦃i : ℕ⦄ (hx : i < List.length x) (hy : i < List.length y), R (List.nthLe x i hx) (List.nthLe y i hy)

theorem List.forall₂_of_length_eq_of_nthLe {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {x : List α} {y : List β} : List.length x = List.length y → (∀ (i : ℕ) (h₁ : i < List.length x) (h₂ : i < List.length y), R (List.nthLe x i h₁) (List.nthLe y i h₂)) → List.Forall₂ R x y

theorem List.forall₂_iff_nthLe {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l₁ : List α} {l₂ : List β} : List.Forall₂ R l₁ l₂ ↔ List.length l₁ = List.length l₂ ∧ ∀ (i : ℕ) (h₁ : i < List.length l₁) (h₂ : i < List.length l₂), R (List.nthLe l₁ i h₁) (List.nthLe l₂ i h₂)

theorem List.forall₂_zip {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l₁ : List α} {l₂ : List β} : List.Forall₂ R l₁ l₂ → ∀ {a : α} {b : β}, (a, b) ∈ List.zip l₁ l₂ → R a b

theorem List.forall₂_iff_zip {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l₁ : List α} {l₂ : List β} : List.Forall₂ R l₁ l₂ ↔ List.length l₁ = List.length l₂ ∧ ∀ {a : α} {b : β}, (a, b) ∈ List.zip l₁ l₂ → R a b

theorem List.forall₂_take {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (n : ℕ) {l₁ : List α} {l₂ : List β} : List.Forall₂ R l₁ l₂ → List.Forall₂ R (List.take n l₁) (List.take n l₂)

theorem List.forall₂_drop {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (n : ℕ) {l₁ : List α} {l₂ : List β} : List.Forall₂ R l₁ l₂ → List.Forall₂ R (List.drop n l₁) (List.drop n l₂)

theorem List.forall₂_take_append {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (l : List α) (l₁ : List β) (l₂ : List β) (h : List.Forall₂ R l (l₁ ++ l₂)) : List.Forall₂ R (List.take (List.length l₁) l) l₁

theorem List.forall₂_drop_append {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (l : List α) (l₁ : List β) (l₂ : List β) (h : List.Forall₂ R l (l₁ ++ l₂)) : List.Forall₂ R (List.drop (List.length l₁) l) l₂

theorem List.rel_mem {α : Type u_1} {β : Type u_2} {R : α → β → Prop} (hr : Relator.BiUnique R) : (R ⇒ List.Forall₂ R ⇒ Iff) (fun (x : α) (x_1 : List α) => x ∈ x_1) fun (x : β) (x_1 : List β) => x ∈ x_1

theorem List.rel_map {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {R : α → β → Prop} {P : γ → δ → Prop} : ((R ⇒ P) ⇒ List.Forall₂ R ⇒ List.Forall₂ P) List.map List.map

theorem List.rel_append {α : Type u_1} {β : Type u_2} {R : α → β → Prop} : (List.Forall₂ R ⇒ List.Forall₂ R ⇒ List.Forall₂ R) (fun (x x_1 : List α) => x ++ x_1) fun (x x_1 : List β) => x ++ x_1

theorem List.rel_reverse {α : Type u_1} {β : Type u_2} {R : α → β → Prop} : (List.Forall₂ R ⇒ List.Forall₂ R) List.reverse List.reverse

@[simp]

theorem List.forall₂_reverse_iff {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l₁ : List α} {l₂ : List β} : List.Forall₂ R (List.reverse l₁) (List.reverse l₂) ↔ List.Forall₂ R l₁ l₂

theorem List.rel_join {α : Type u_1} {β : Type u_2} {R : α → β → Prop} : (List.Forall₂ (List.Forall₂ R) ⇒ List.Forall₂ R) List.join List.join

theorem List.rel_bind {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {R : α → β → Prop} {P : γ → δ → Prop} : (List.Forall₂ R ⇒ (R ⇒ List.Forall₂ P) ⇒ List.Forall₂ P) List.bind List.bind

theorem List.rel_foldl {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {R : α → β → Prop} {P : γ → δ → Prop} : ((P ⇒ R ⇒ P) ⇒ P ⇒ List.Forall₂ R ⇒ P) List.foldl List.foldl

theorem List.rel_foldr {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {R : α → β → Prop} {P : γ → δ → Prop} : ((R ⇒ P ⇒ P) ⇒ P ⇒ List.Forall₂ R ⇒ P) List.foldr List.foldr

theorem List.rel_filter {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {p : α → Bool} {q : β → Bool} (hpq : (R ⇒ fun (x x_1 : Prop) => x ↔ x_1) (fun (x : α) => p x = true) fun (x : β) => q x = true) : (List.Forall₂ R ⇒ List.Forall₂ R) (List.filter p) (List.filter q)

theorem List.rel_filterMap {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {R : α → β → Prop} {P : γ → δ → Prop} : ((R ⇒ Option.Rel P) ⇒ List.Forall₂ R ⇒ List.Forall₂ P) List.filterMap List.filterMap

theorem List.rel_sum {α : Type u_1} {β : Type u_2} {R : α → β → Prop} [AddMonoid α] [AddMonoid β] (h : R 0 0) (hf : (R ⇒ R ⇒ R) (fun (x x_1 : α) => x + x_1) fun (x x_1 : β) => x + x_1) : (List.Forall₂ R ⇒ R) List.sum List.sum

theorem List.rel_prod {α : Type u_1} {β : Type u_2} {R : α → β → Prop} [Monoid α] [Monoid β] (h : R 1 1) (hf : (R ⇒ R ⇒ R) (fun (x x_1 : α) => x * x_1) fun (x x_1 : β) => x * x_1) : (List.Forall₂ R ⇒ R) List.prod List.prod

inductive List.SublistForall₂ {α : Type u_1} {β : Type u_2} (R : α → β → Prop) : List α → List β → Prop

Given a relation R, sublist_forall₂ r l₁ l₂ indicates that there is a sublist of l₂ such that forall₂ r l₁ l₂.

• nil: ∀ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l : List β}, List.SublistForall₂ R [] l
• cons: ∀ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {a₁ : α} {a₂ : β} {l₁ : List α} {l₂ : List β}, R a₁ a₂ → List.SublistForall₂ R l₁ l₂ → List.SublistForall₂ R (a₁ :: l₁) (a₂ :: l₂)
• cons_right: ∀ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {a : β} {l₁ : List α} {l₂ : List β}, List.SublistForall₂ R l₁ l₂ → List.SublistForall₂ R l₁ (a :: l₂)

theorem List.sublistForall₂_iff {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {l₁ : List α} {l₂ : List β} : List.SublistForall₂ R l₁ l₂ ↔ ∃ (l : List β), List.Forall₂ R l₁ l ∧ List.Sublist l l₂

instance List.SublistForall₂.is_refl {α : Type u_1} {Rₐ : α → α → Prop} [IsRefl α Rₐ] : IsRefl (List α) (List.SublistForall₂ Rₐ)

Equations

• (_ : IsRefl (List α) (List.SublistForall₂ Rₐ)) = (_ : IsRefl (List α) (List.SublistForall₂ Rₐ))

instance List.SublistForall₂.is_trans {α : Type u_1} {Rₐ : α → α → Prop} [IsTrans α Rₐ] : IsTrans (List α) (List.SublistForall₂ Rₐ)

Equations

• (_ : IsTrans (List α) (List.SublistForall₂ Rₐ)) = (_ : IsTrans (List α) (List.SublistForall₂ Rₐ))

theorem List.Sublist.sublistForall₂ {α : Type u_1} {Rₐ : α → α → Prop} {l₁ : List α} {l₂ : List α} (h : List.Sublist l₁ l₂) [IsRefl α Rₐ] : List.SublistForall₂ Rₐ l₁ l₂

theorem List.tail_sublistForall₂_self {α : Type u_1} {Rₐ : α → α → Prop} [IsRefl α Rₐ] (l : List α) : List.SublistForall₂ Rₐ (List.tail l) l