# Documentation

Mathlib.Logic.Equiv.Fin

# Equivalences for Fin n#

Equivalence between Fin 0 and Empty.

Instances For

Equivalence between Fin 0 and PEmpty.

Instances For

Equivalence between Fin 1 and Unit.

Instances For

Equivalence between Fin 2 and Bool.

Instances For
@[simp]
theorem piFinTwoEquiv_apply (α : Fin 2Type u) :
↑() = fun f => (f 0, f 1)
@[simp]
theorem piFinTwoEquiv_symm_apply (α : Fin 2Type u) :
().symm = fun p => Fin.cons p.fst (Fin.cons p.snd finZeroElim)
def piFinTwoEquiv (α : Fin 2Type u) :
((i : Fin 2) → α i) α 0 × α 1

Π i : Fin 2, α i is equivalent to α 0 × α 1. See also finTwoArrowEquiv for a non-dependent version and prodEquivPiFinTwo for a version with inputs α β : Type u.

Instances For
theorem Fin.preimage_apply_01_prod {α : Fin 2Type u} (s : Set (α 0)) (t : Set (α 1)) :
(fun f => (f 0, f 1)) ⁻¹' s ×ˢ t = Set.pi Set.univ (Fin.cons s (Fin.cons t finZeroElim))
theorem Fin.preimage_apply_01_prod' {α : Type u} (s : Set α) (t : Set α) :
(fun f => (f 0, f 1)) ⁻¹' s ×ˢ t = Set.pi Set.univ ![s, t]
@[simp]
theorem prodEquivPiFinTwo_symm_apply (α : Type u) (β : Type u) :
().symm = fun f => (f 0, f 1)
@[simp]
theorem prodEquivPiFinTwo_apply (α : Type u) (β : Type u) :
↑() = fun p => Fin.cons p.fst (Fin.cons p.snd finZeroElim)
def prodEquivPiFinTwo (α : Type u) (β : Type u) :
α × β ((i : Fin 2) → Matrix.vecCons α ![β] i)

A product space α × β is equivalent to the space Π i : Fin 2, γ i, where γ = Fin.cons α (Fin.cons β finZeroElim). See also piFinTwoEquiv and finTwoArrowEquiv.

Instances For
@[simp]
theorem finTwoArrowEquiv_apply (α : Type u_1) :
↑() = (piFinTwoEquiv fun x => α).toFun
@[simp]
theorem finTwoArrowEquiv_symm_apply (α : Type u_1) :
().symm = fun x => ![x.fst, x.snd]
def finTwoArrowEquiv (α : Type u_1) :
(Fin 2α) α × α

The space of functions Fin 2 → α is equivalent to α × α. See also piFinTwoEquiv and prodEquivPiFinTwo.

Instances For
def OrderIso.piFinTwoIso (α : Fin 2Type u) [(i : Fin 2) → Preorder (α i)] :
((i : Fin 2) → α i) ≃o α 0 × α 1

Π i : Fin 2, α i is order equivalent to α 0 × α 1. See also OrderIso.finTwoArrowEquiv for a non-dependent version.

Instances For
def OrderIso.finTwoArrowIso (α : Type u_1) [] :
(Fin 2α) ≃o α × α

The space of functions Fin 2 → α is order equivalent to α × α. See also OrderIso.piFinTwoIso.

Instances For
def finCongr {m : } {n : } (h : m = n) :
Fin m Fin n

The 'identity' equivalence between Fin n and Fin m when n = m.

Instances For
@[simp]
theorem finCongr_apply_mk {m : } {n : } (h : m = n) (k : ) (w : k < m) :
↑() { val := k, isLt := w } = { val := k, isLt := (_ : k < n) }
@[simp]
theorem finCongr_symm {m : } {n : } (h : m = n) :
().symm = finCongr (_ : n = m)
@[simp]
theorem finCongr_apply_coe {m : } {n : } (h : m = n) (k : Fin m) :
↑(↑() k) = k
theorem finCongr_symm_apply_coe {m : } {n : } (h : m = n) (k : Fin n) :
↑(().symm k) = k
def finSuccEquiv' {n : } (i : Fin (n + 1)) :
Fin (n + 1) Option (Fin n)

An equivalence that removes i and maps it to none. This is a version of Fin.predAbove that produces Option (Fin n) instead of mapping both i.cast_succ and i.succ to i.

Instances For
@[simp]
theorem finSuccEquiv'_at {n : } (i : Fin (n + 1)) :
↑() i = none
@[simp]
theorem finSuccEquiv'_succAbove {n : } (i : Fin (n + 1)) (j : Fin n) :
↑() () = some j
theorem finSuccEquiv'_below {n : } {i : Fin (n + 1)} {m : Fin n} (h : ) :
↑() () = some m
theorem finSuccEquiv'_above {n : } {i : Fin (n + 1)} {m : Fin n} (h : ) :
↑() () = some m
@[simp]
theorem finSuccEquiv'_symm_none {n : } (i : Fin (n + 1)) :
().symm none = i
@[simp]
theorem finSuccEquiv'_symm_some {n : } (i : Fin (n + 1)) (j : Fin n) :
().symm (some j) =
theorem finSuccEquiv'_symm_some_below {n : } {i : Fin (n + 1)} {m : Fin n} (h : ) :
().symm (some m) =
theorem finSuccEquiv'_symm_some_above {n : } {i : Fin (n + 1)} {m : Fin n} (h : ) :
().symm (some m) =
theorem finSuccEquiv'_symm_coe_below {n : } {i : Fin (n + 1)} {m : Fin n} (h : ) :
().symm (some m) =
theorem finSuccEquiv'_symm_coe_above {n : } {i : Fin (n + 1)} {m : Fin n} (h : ) :
().symm (some m) =
def finSuccEquiv (n : ) :
Fin (n + 1) Option (Fin n)

Equivalence between Fin (n + 1) and Option (Fin n). This is a version of Fin.pred that produces Option (Fin n) instead of requiring a proof that the input is not 0.

Instances For
@[simp]
theorem finSuccEquiv_zero {n : } :
↑() 0 = none
@[simp]
theorem finSuccEquiv_succ {n : } (m : Fin n) :
↑() () = some m
@[simp]
theorem finSuccEquiv_symm_none {n : } :
().symm none = 0
@[simp]
theorem finSuccEquiv_symm_some {n : } (m : Fin n) :
().symm (some m) =
theorem finSuccEquiv'_zero {n : } :

The equiv version of Fin.predAbove_zero.

theorem finSuccEquiv'_last_apply_castSucc {n : } (i : Fin n) :
↑() () = some i
theorem finSuccEquiv'_last_apply {n : } {i : Fin (n + 1)} (h : i ) :
↑() i = some (Fin.castLT i (_ : i < n))
theorem finSuccEquiv'_ne_last_apply {n : } {i : Fin (n + 1)} {j : Fin (n + 1)} (hi : i ) (hj : j i) :
↑() j = some (Fin.predAbove (Fin.castLT i (_ : i < n)) j)
def finSuccAboveEquiv {n : } (p : Fin (n + 1)) :
Fin n ≃o { x // x p }

Fin.succAbove as an order isomorphism between Fin n and {x : Fin (n + 1) // x ≠ p}.

Instances For
theorem finSuccAboveEquiv_apply {n : } (p : Fin (n + 1)) (i : Fin n) :
↑() i = { val := , property := (_ : p) }
theorem finSuccAboveEquiv_symm_apply_last {n : } (x : { x // x }) :
↑() x = Fin.castLT x (_ : x < n)
theorem finSuccAboveEquiv_symm_apply_ne_last {n : } {p : Fin (n + 1)} (h : p ) (x : { x // x p }) :
↑() x = Fin.predAbove (Fin.castLT p (_ : p < n)) x
def finSuccEquivLast {n : } :
Fin (n + 1) Option (Fin n)

Equiv between Fin (n + 1) and Option (Fin n) sending Fin.last n to none

Instances For
@[simp]
theorem finSuccEquivLast_castSucc {n : } (i : Fin n) :
finSuccEquivLast () = some i
@[simp]
theorem finSuccEquivLast_last {n : } :
finSuccEquivLast () = none
@[simp]
theorem finSuccEquivLast_symm_some {n : } (i : Fin n) :
finSuccEquivLast.symm (some i) =
@[simp]
theorem finSuccEquivLast_symm_none {n : } :
finSuccEquivLast.symm none =
@[simp]
theorem Equiv.piFinSuccAboveEquiv_apply {n : } (α : Fin (n + 1)Type u) (i : Fin (n + 1)) :
↑() = fun f => (f i, fun j => f ())
@[simp]
theorem Equiv.piFinSuccAboveEquiv_symm_apply {n : } (α : Fin (n + 1)Type u) (i : Fin (n + 1)) :
().symm = fun f => Fin.insertNth i f.fst f.snd
def Equiv.piFinSuccAboveEquiv {n : } (α : Fin (n + 1)Type u) (i : Fin (n + 1)) :
((j : Fin (n + 1)) → α j) α i × ((j : Fin n) → α ())

Equivalence between Π j : Fin (n + 1), α j and α i × Π j : Fin n, α (Fin.succAbove i j).

Instances For
def OrderIso.piFinSuccAboveIso {n : } (α : Fin (n + 1)Type u) [(i : Fin (n + 1)) → LE (α i)] (i : Fin (n + 1)) :
((j : Fin (n + 1)) → α j) ≃o α i × ((j : Fin n) → α ())

Order isomorphism between Π j : Fin (n + 1), α j and α i × Π j : Fin n, α (Fin.succAbove i j).

Instances For
@[simp]
theorem Equiv.piFinSucc_apply (n : ) (β : Type u) :
↑() = fun f => (f 0, fun j => f ())
@[simp]
theorem Equiv.piFinSucc_symm_apply (n : ) (β : Type u) :
().symm = fun f => Fin.cons f.fst f.snd
def Equiv.piFinSucc (n : ) (β : Type u) :
(Fin (n + 1)β) β × (Fin nβ)

Equivalence between Fin (n + 1) → β and β × (Fin n → β).

Instances For
def finSumFinEquiv {m : } {n : } :
Fin m Fin n Fin (m + n)

Equivalence between Fin m ⊕ Fin n and Fin (m + n)

Instances For
@[simp]
theorem finSumFinEquiv_apply_left {m : } {n : } (i : Fin m) :
finSumFinEquiv () =
@[simp]
theorem finSumFinEquiv_apply_right {m : } {n : } (i : Fin n) :
finSumFinEquiv () =
@[simp]
theorem finSumFinEquiv_symm_apply_castAdd {m : } {n : } (x : Fin m) :
finSumFinEquiv.symm () =
@[simp]
theorem finSumFinEquiv_symm_apply_natAdd {m : } {n : } (x : Fin n) :
finSumFinEquiv.symm () =
@[simp]
theorem finSumFinEquiv_symm_last {n : } :
finSumFinEquiv.symm () =
def finAddFlip {m : } {n : } :
Fin (m + n) Fin (n + m)

The equivalence between Fin (m + n) and Fin (n + m) which rotates by n.

Instances For
@[simp]
theorem finAddFlip_apply_castAdd {m : } (k : Fin m) (n : ) :
@[simp]
theorem finAddFlip_apply_natAdd {n : } (k : Fin n) (m : ) :
@[simp]
theorem finAddFlip_apply_mk_left {m : } {n : } {k : } (h : k < m) (hk : optParam (k < m + n) (_ : k < m + n)) (hnk : optParam (n + k < n + m) (_ : n + k < n + m)) :
finAddFlip { val := k, isLt := hk } = { val := n + k, isLt := hnk }
@[simp]
theorem finAddFlip_apply_mk_right {m : } {n : } {k : } (h₁ : m k) (h₂ : k < m + n) :
finAddFlip { val := k, isLt := h₂ } = { val := k - m, isLt := (_ : k - m < n + m) }
def finRotate (n : ) :

Rotate Fin n one step to the right.

Instances For
@[simp]
theorem finRotate_succ (n : ) :
finRotate (n + 1) = finAddFlip.trans (finCongr (_ : 1 + n = n + 1))
theorem finRotate_of_lt {n : } {k : } (h : k < n) :
↑(finRotate (n + 1)) { val := k, isLt := (_ : k < n + 1) } = { val := k + 1, isLt := (_ : ) }
theorem finRotate_last' {n : } :
↑(finRotate (n + 1)) { val := n, isLt := (_ : n < n + 1) } = { val := 0, isLt := (_ : 0 < ) }
theorem finRotate_last {n : } :
↑(finRotate (n + 1)) () = 0
theorem Fin.snoc_eq_cons_rotate {n : } {α : Type u_1} (v : Fin nα) (a : α) :
Fin.snoc v a = fun i => Fin.cons a v (↑(finRotate (n + 1)) i)
@[simp]
@[simp]
theorem finRotate_succ_apply {n : } (i : Fin (n + 1)) :
↑(finRotate (n + 1)) i = i + 1
theorem finRotate_apply_zero {n : } :
↑() 0 = 1
theorem coe_finRotate_of_ne_last {n : } {i : Fin ()} (h : i ) :
↑(↑(finRotate (n + 1)) i) = i + 1
theorem coe_finRotate {n : } (i : Fin ()) :
↑(↑() i) = if i = then 0 else i + 1
@[simp]
theorem finProdFinEquiv_symm_apply {m : } {n : } (x : Fin (m * n)) :
finProdFinEquiv.symm x = (, )
@[simp]
theorem finProdFinEquiv_apply_val {m : } {n : } (x : Fin m × Fin n) :
↑(finProdFinEquiv x) = x.snd + n * x.fst
def finProdFinEquiv {m : } {n : } :
Fin m × Fin n Fin (m * n)

Equivalence between Fin m × Fin n and Fin (m * n)

Instances For
@[simp]
theorem Nat.divModEquiv_symm_apply (n : ) [] (p : × Fin n) :
().symm p = p.fst * n + p.snd
@[simp]
theorem Nat.divModEquiv_apply (n : ) [] (a : ) :
↑() a = (a / n, a)
def Nat.divModEquiv (n : ) [] :

The equivalence induced by a ↦ (a / n, a % n) for nonzero n. This is like finProdFinEquiv.symm but with m infinite. See Nat.div_mod_unique for a similar propositional statement.

Instances For
@[simp]
theorem Int.divModEquiv_symm_apply (n : ) [] (p : × Fin n) :
().symm p = p.fst * n + p.snd
@[simp]
theorem Int.divModEquiv_apply (n : ) [] (a : ) :
↑() a = (a / n, ↑(Int.natMod a n))
def Int.divModEquiv (n : ) [] :

The equivalence induced by a ↦ (a / n, a % n) for nonzero n. See Int.ediv_emod_unique for a similar propositional statement.

Instances For
@[simp]
theorem Fin.castLEOrderIso_symm_apply {n : } {m : } (h : n m) (i : { i // i < n }) :
↑() i = { val := i, isLt := (_ : i < n) }
@[simp]
theorem Fin.castLEOrderIso_apply {n : } {m : } (h : n m) (i : Fin n) :
↑() i = { val := , property := (_ : i < n) }
def Fin.castLEOrderIso {n : } {m : } (h : n m) :
Fin n ≃o { i // i < n }

Promote a Fin n into a larger Fin m, as a subtype where the underlying values are retained. This is the OrderIso version of Fin.castLE.

Instances For

Fin 0 is a subsingleton.

Fin 1 is a subsingleton.