mathlib3 documentation

data.list.nodup_equiv_fin

Equivalence between fin (length l) and elements of a list #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

Given a list l,

@[simp]
theorem list.nodup.nth_le_bijection_of_forall_mem_list_coe {α : Type u_1} (l : list α) (nd : l.nodup) (h : (x : α), x l) (i : fin l.length) :
def list.nodup.nth_le_bijection_of_forall_mem_list {α : Type u_1} (l : list α) (nd : l.nodup) (h : (x : α), x l) :

If l lists all the elements of α without duplicates, then list.nth_le defines a bijection fin l.length → α. See list.nodup.nth_le_equiv_of_forall_mem_list for a version giving an equivalence when there is decidable equality.

Equations
@[simp]
theorem list.nodup.nth_le_equiv_apply_coe {α : Type u_1} [decidable_eq α] (l : list α) (H : l.nodup) (i : fin l.length) :
def list.nodup.nth_le_equiv {α : Type u_1} [decidable_eq α] (l : list α) (H : l.nodup) :
fin l.length {x // x l}

If l has no duplicates, then list.nth_le defines an equivalence between fin (length l) and the set of elements of l.

Equations
@[simp]
theorem list.nodup.nth_le_equiv_symm_apply_val {α : Type u_1} [decidable_eq α] (l : list α) (H : l.nodup) (x : {x // x l}) :
@[simp]
theorem list.nodup.nth_le_equiv_of_forall_mem_list_apply {α : Type u_1} [decidable_eq α] (l : list α) (nd : l.nodup) (h : (x : α), x l) (i : fin l.length) :
@[simp]
theorem list.nodup.nth_le_equiv_of_forall_mem_list_symm_apply_val {α : Type u_1} [decidable_eq α] (l : list α) (nd : l.nodup) (h : (x : α), x l) (a : α) :
def list.nodup.nth_le_equiv_of_forall_mem_list {α : Type u_1} [decidable_eq α] (l : list α) (nd : l.nodup) (h : (x : α), x l) :

If l lists all the elements of α without duplicates, then list.nth_le defines an equivalence between fin l.length and α.

See list.nodup.nth_le_bijection_of_forall_mem_list for a version without decidable equality.

Equations
theorem list.sorted.nth_le_mono {α : Type u_1} [preorder α] {l : list α} (h : list.sorted has_le.le l) :
monotone (λ (i : fin l.length), l.nth_le i _)
theorem list.sorted.nth_le_strict_mono {α : Type u_1} [preorder α] {l : list α} (h : list.sorted has_lt.lt l) :
strict_mono (λ (i : fin l.length), l.nth_le i _)
def list.sorted.nth_le_iso {α : Type u_1} [preorder α] [decidable_eq α] (l : list α) (H : list.sorted has_lt.lt l) :
fin l.length ≃o {x // x l}

If l is a list sorted w.r.t. (<), then list.nth_le defines an order isomorphism between fin (length l) and the set of elements of l.

Equations
@[simp]
theorem list.sorted.coe_nth_le_iso_apply {α : Type u_1} [preorder α] {l : list α} [decidable_eq α] (H : list.sorted has_lt.lt l) {i : fin l.length} :
@[simp]
theorem list.sorted.coe_nth_le_iso_symm_apply {α : Type u_1} [preorder α] {l : list α} [decidable_eq α] (H : list.sorted has_lt.lt l) {x : {x // x l}} :
theorem list.sublist_of_order_embedding_nth_eq {α : Type u_1} {l l' : list α} (f : ↪o ) (hf : (ix : ), l.nth ix = l'.nth (f ix)) :
l <+ l'

If there is f, an order-preserving embedding of into such that any element of l found at index ix can be found at index f ix in l', then sublist l l'.

theorem list.sublist_iff_exists_order_embedding_nth_eq {α : Type u_1} {l l' : list α} :
l <+ l' (f : ↪o ), (ix : ), l.nth ix = l'.nth (f ix)

A l : list α is sublist l l' for l' : list α iff there is f, an order-preserving embedding of into such that any element of l found at index ix can be found at index f ix in l'.

theorem list.sublist_iff_exists_fin_order_embedding_nth_le_eq {α : Type u_1} {l l' : list α} :
l <+ l' (f : fin l.length ↪o fin l'.length), (ix : fin l.length), l.nth_le ix _ = l'.nth_le (f ix) _

A l : list α is sublist l l' for l' : list α iff there is f, an order-preserving embedding of fin l.length into fin l'.length such that any element of l found at index ix can be found at index f ix in l'.

theorem list.duplicate_iff_exists_distinct_nth_le {α : Type u_1} {l : list α} {x : α} :
list.duplicate x l (n : ) (hn : n < l.length) (m : ) (hm : m < l.length) (h : n < m), x = l.nth_le n hn x = l.nth_le m hm

An element x : α of l : list α is a duplicate iff it can be found at two distinct indices n m : ℕ inside the list l.