# mathlibdocumentation

data.list.nodup_equiv_fin

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

Given a list l,

• if l has no duplicates, then list.nodup.nth_le_equiv is the equivalence between fin (length l) and {x // x ∈ l} sending ⟨i, hi⟩ to ⟨nth_le l i hi, _⟩ with the inverse sending ⟨x, hx⟩ to ⟨index_of x l, _⟩;

• if l has no duplicates and contains every element of a type α, then list.nodup.nth_le_equiv_of_forall_mem_list defines an equivalence between fin (length l) and α; if α does not have decidable equality, then there is a bijection list.nodup.nth_le_bijection_of_forall_mem_list;

• if l is sorted w.r.t. (<), then list.sorted.nth_le_iso is the same bijection reinterpreted as an order_iso.

@[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) :
= l.nth_le i _
def list.nodup.nth_le_bijection_of_forall_mem_list {α : Type u_1} (l : list α) (nd : l.nodup) (h : ∀ (x : α), x l) :
{f //

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) :
( i) = l.nth_le i _
def list.nodup.nth_le_equiv {α : Type u_1} [decidable_eq α] (l : list α) (H : l.nodup) :
{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_coe {α : Type u_1} [decidable_eq α] (l : list α) (H : l.nodup) (x : {x // x l}) :
( H).symm) x) =
@[simp]
theorem list.nodup.nth_le_equiv_of_forall_mem_list_symm_apply_coe {α : Type u_1} [decidable_eq α] (l : list α) (nd : l.nodup) (h : ∀ (x : α), x l) (a : α) :
(.symm) a) =
@[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) :
= l.nth_le i _
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 : l) :
monotone (λ (i : fin l.length), l.nth_le i _)
theorem list.sorted.nth_le_strict_mono {α : Type u_1} [preorder α] {l : list α} (h : 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 : l) :
≃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 : l) {i : fin l.length} :
( i) = l.nth_le i _
@[simp]
theorem list.sorted.coe_nth_le_iso_symm_apply {α : Type u_1} [preorder α] {l : list α} [decidable_eq α] (H : l) {x : {x // x l}} :
( H).symm) x) =
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 : ↪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 : α} :
∃ (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.