class Std.PRange.UpwardEnumerable (α : Type u) : Type u

This typeclass provides the function succ? : α → Option α that computes the successor of elements of α, or none if no successor exists. It also provides the function succMany?, which computes n-th successors.

succ? is expected to be acyclic: No element is its own transitive successor. If α is ordered, then every element larger than a : α should be a transitive successor of a. These properties and the compatibility of succ? with succMany? are encoded in the typeclasses LawfulUpwardEnumerable, LawfulUpwardEnumerableLE and LawfulUpwardEnumerableLT.

• succ? : α → Option α

  Maps elements of α to their successor, or none if no successor exists.

• succMany? (n : Nat) (a : α) : Option α

  Maps elements of α to their n-th successor, or none if no successor exists. This should semantically behave like repeatedly applying succ?, but it might be more efficient.

  LawfulUpwardEnumerable ensures the compatibility with succ?.

  If no other implementation is provided in UpwardEnumerable instance, succMany? repeatedly applies succ?.

def Std.PRange.UpwardEnumerable.LE {α : Type u} [UpwardEnumerable α] (a b : α) : Prop

According to UpwardEnumerable.LE, a is less than or equal to b if b is a or a transitive successor of a.

Equations

• Std.PRange.UpwardEnumerable.LE a b = ∃ (n : Nat), Std.PRange.UpwardEnumerable.succMany? n a = some b

def Std.PRange.UpwardEnumerable.LT {α : Type u} [UpwardEnumerable α] (a b : α) : Prop

According to UpwardEnumerable.LT, a is less than b if b is a proper transitive successor of a. 'Proper' means that b is the n-th successor of a, where n > 0.

Given LawfulUpwardEnumerable α, no element of α is less than itself.

Equations

• Std.PRange.UpwardEnumerable.LT a b = ∃ (n : Nat), Std.PRange.UpwardEnumerable.succMany? (n + 1) a = some b

theorem Std.PRange.UpwardEnumerable.le_of_lt {α : Type u} [UpwardEnumerable α] {a b : α} (h : LT a b) : LE a b

class Std.PRange.Least? (α : Type u) : Type u

The typeclass Least? α optionally provides a smallest element of α, least? : Option α.

The main use case of this typeclass is to use it in combination with UpwardEnumerable to obtain a (possibly infinite) ascending enumeration of all elements of α.

• least? : Option α

  Returns the smallest element of α, or none if α is empty.

  Only empty types are allowed to define least? := none. If α is ordered and nonempty, then the value of least? should be the smallest element according to the order on α.

class Std.PRange.LawfulUpwardEnumerable (α : Type u) [UpwardEnumerable α] : Prop

This typeclass ensures that an UpwardEnumerable α instance is well-behaved.

• ne_of_lt (a b : α) : UpwardEnumerable.LT a b → a ≠ b

  There is no cyclic chain of successors.

• succMany?_zero (a : α) : UpwardEnumerable.succMany? 0 a = some a

  The 0-th successor of a is a itself.

• succMany?_succ (n : Nat) (a : α) : UpwardEnumerable.succMany? (n + 1) a = (UpwardEnumerable.succMany? n a).bind UpwardEnumerable.succ?

  The n + 1-th successor of a is the successor of the n-th successor, given that said successors actualy exist.

theorem Std.PRange.UpwardEnumerable.succMany?_zero {α : Type u_1} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a : α} : succMany? 0 a = some a

theorem Std.PRange.UpwardEnumerable.succMany?_succ {α : Type u_1} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {n : Nat} {a : α} : succMany? (n + 1) a = (succMany? n a).bind succ?

theorem Std.PRange.UpwardEnumerable.succMany?_one {α : Type u_1} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a : α} : succMany? 1 a = succ? a

theorem Std.PRange.UpwardEnumerable.succMany?_add {α : Type u_1} [UpwardEnumerable α] [LawfulUpwardEnumerable α] (m n : Nat) (a : α) : succMany? (m + n) a = (succMany? m a).bind fun (x : α) => succMany? n x

theorem Std.PRange.LawfulUpwardEnumerable.succMany?_succ_eq_succ?_bind_succMany? {α : Type u_1} [UpwardEnumerable α] [LawfulUpwardEnumerable α] (n : Nat) (a : α) : UpwardEnumerable.succMany? (n + 1) a = (UpwardEnumerable.succ? a).bind fun (x : α) => UpwardEnumerable.succMany? n x

theorem Std.PRange.UpwardEnumerable.le_refl {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] (a : α) : LE a a

theorem Std.PRange.UpwardEnumerable.le_trans {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a b c : α} (hab : LE a b) (hbc : LE b c) : LE a c

theorem Std.PRange.UpwardEnumerable.le_of_succ?_eq {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a b : α} (hab : succ? a = some b) : LE a b

theorem Std.PRange.UpwardEnumerable.lt_of_lt_of_le {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a b c : α} (hab : LT a b) (hbc : LE b c) : LT a c

theorem Std.PRange.UpwardEnumerable.not_gt_of_le {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a b : α} : LE a b → ¬LT b a

theorem Std.PRange.UpwardEnumerable.not_gt_of_lt {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a b : α} (h : LT a b) : ¬LT b a

theorem Std.PRange.UpwardEnumerable.ne_of_lt {α : Type w} [UpwardEnumerable α] [LawfulUpwardEnumerable α] {a b : α} : LT a b → a ≠ b

class Std.PRange.InfinitelyUpwardEnumerable (α : Type u) [UpwardEnumerable α] : Prop

This propositional typeclass ensures that UpwardEnumerable.succ? will never return none. In other words, it ensures that there will always be a successor.

• isSome_succ? (a : α) : (UpwardEnumerable.succ? a).isSome = true

class Std.PRange.LinearlyUpwardEnumerable (α : Type u) [UpwardEnumerable α] : Prop

This propositional typeclass ensures that UpwardEnumerable.succ? is injective.

• eq_of_succ?_eq (a b : α) : UpwardEnumerable.succ? a = UpwardEnumerable.succ? b → a = b

theorem Std.PRange.UpwardEnumerable.isSome_succ? {α : Type u} [UpwardEnumerable α] [InfinitelyUpwardEnumerable α] {a : α} : (succ? a).isSome = true

theorem Std.PRange.UpwardEnumerable.eq_of_succ?_eq {α : Type u} [UpwardEnumerable α] [LinearlyUpwardEnumerable α] {a b : α} (h : succ? a = succ? b) : a = b

@[reducible, inline]

abbrev Std.PRange.UpwardEnumerable.succ {α : Type u} [UpwardEnumerable α] [InfinitelyUpwardEnumerable α] (a : α) : α

Equations

• Std.PRange.UpwardEnumerable.succ a = (Std.PRange.UpwardEnumerable.succ? a).get ⋯

theorem Std.PRange.UpwardEnumerable.succ_eq_get {α : Type u} [UpwardEnumerable α] [InfinitelyUpwardEnumerable α] {a : α} : succ a = (succ? a).get ⋯

theorem Std.PRange.UpwardEnumerable.succ?_eq_some {α : Type u} [UpwardEnumerable α] [InfinitelyUpwardEnumerable α] {a : α} : succ? a = some (succ a)

theorem Std.PRange.UpwardEnumerable.eq_of_succ_eq {α : Type u} [UpwardEnumerable α] [InfinitelyUpwardEnumerable α] [LinearlyUpwardEnumerable α] {a b : α} (h : succ a = succ b) : a = b

theorem Std.PRange.UpwardEnumerable.succ_eq_succ_iff {α : Type u} [UpwardEnumerable α] [InfinitelyUpwardEnumerable α] [LinearlyUpwardEnumerable α] {a b : α} : succ a = succ b ↔ a = b

theorem Std.PRange.UpwardEnumerable.isSome_succMany? {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {n : Nat} {a : α} : (succMany? n a).isSome = true

@[inline]

def Std.PRange.UpwardEnumerable.succMany {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [InfinitelyUpwardEnumerable α] (n : Nat) (a : α) : α

Equations

• Std.PRange.UpwardEnumerable.succMany n a = (Std.PRange.UpwardEnumerable.succMany? n a).get ⋯

theorem Std.PRange.UpwardEnumerable.succMany_eq_get {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {n : Nat} {a : α} : succMany n a = (succMany? n a).get ⋯

theorem Std.PRange.UpwardEnumerable.succMany?_eq_some {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {n : Nat} {a : α} : succMany? n a = some (succMany n a)

theorem Std.PRange.UpwardEnumerable.succMany?_eq_some_iff_succMany {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {n : Nat} {a b : α} : succMany? n a = some b ↔ succMany n a = b

theorem Std.PRange.UpwardEnumerable.succMany_one {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {a : α} : succMany 1 a = succ a

theorem Std.PRange.UpwardEnumerable.succMany_add {α : Type u} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {m n : Nat} {a : α} : succMany (m + n) a = succMany n (succMany m a)

theorem Std.PRange.UpwardEnumerable.succ_le_succ_iff {α : Type w} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [LinearlyUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {a b : α} : LE (succ a) (succ b) ↔ LE a b

theorem Std.PRange.UpwardEnumerable.succ_lt_succ_iff {α : Type w} [UpwardEnumerable α] [LawfulUpwardEnumerable α] [LinearlyUpwardEnumerable α] [InfinitelyUpwardEnumerable α] {a b : α} : LT (succ a) (succ b) ↔ LT a b

class Std.PRange.LawfulUpwardEnumerableLE (α : Type u) [UpwardEnumerable α] [LE α] : Prop

This typeclass ensures that an UpwardEnumerable α instance is compatible with ≤. In this case, UpwardEnumerable α fully characterizes the LE α instance.

• le_iff (a b : α) : a ≤ b ↔ UpwardEnumerable.LE a b

  a is less than or equal to b if and only if b is either a or a transitive successor of a.

class Std.PRange.LawfulUpwardEnumerableLT (α : Type u) [UpwardEnumerable α] [LT α] : Prop

This typeclass ensures that an UpwardEnumerable α instance is compatible with <. In this case, UpwardEnumerable α fully characterizes the LT α instance.

• lt_iff (a b : α) : a < b ↔ UpwardEnumerable.LT a b

  a is less than b if and only if b is a proper transitive successor of a.

class Std.PRange.LawfulUpwardEnumerableLeast? (α : Type u) [UpwardEnumerable α] [Least? α] : Prop

This typeclass ensures that an UpwardEnumerable α instance is compatible with a Least? α instance. For nonempty α, it ensures that least? has a value and that every other value is a transitive successor of it.

• eq_succMany?_least? (a : α) : ∃ (init : α), Least?.least? = some init ∧ UpwardEnumerable.LE init a

  For nonempty α, least? has a value and every other value is a transitive successor of it.