def inline {α : Sort u} (a : α) : α

inline (f x) is an indication to the compiler to inline the definition of f at the application site itself (by comparison to the @[inline] attribute, which applies to all applications of the function).

Equations

• inline a = a

@[inline]

def flip {α : Sort u} {β : Sort v} {φ : Sort w} (f : α → β → φ) : β → α → φ

flip f a b is f b a. It is useful for "point-free" programming, since it can sometimes be used to avoid introducing variables. For example, (·<·) is the less-than relation, and flip (·<·) is the greater-than relation.

Equations

• flip f b a = f a b

@[simp]

theorem Function.const_apply {β : Sort u_1} {α : Sort u_2} {y : β} {x : α} : Function.const α y x = y

@[simp]

theorem Function.comp_apply {β : Sort u_1} {δ : Sort u_2} {α : Sort u_3} {f : β → δ} {g : α → β} {x : α} : Function.comp f g x = f (g x)

structure Thunk (α : Type u) : Type u

• fn : Unit → α

Thunks are "lazy" values that are evaluated when first accessed using Thunk.get/map/bind. The value is then stored and not recomputed for all further accesses.

@[extern lean_thunk_pure]

def Thunk.pure {α : Type u_1} (a : α) : Thunk α

Store a value in a thunk. Note that the value has already been computed, so there is no laziness.

Equations

• Thunk.pure a = { fn := fun x => a }

@[extern lean_thunk_get_own]

def Thunk.get {α : Type u_1} (x : Thunk α) : α

Forces a thunk to extract the value. This will cache the result, so a second call to the same function will return the value in O(1) instead of calling the stored getter function.

Equations

• Thunk.get x = Thunk.fn x ()

@[inline]

def Thunk.map {α : Type u_1} {β : Type u_2} (f : α → β) (x : Thunk α) : Thunk β

Map a function over a thunk.

Equations

• Thunk.map f x = { fn := fun x => f (Thunk.get x) }

@[inline]

def Thunk.bind {α : Type u_1} {β : Type u_2} (x : Thunk α) (f : α → Thunk β) : Thunk β

Constructs a thunk that applies f to the result of x when forced.

Equations

• Thunk.bind x f = { fn := fun x => Thunk.get (f (Thunk.get x)) }

@[simp]

theorem Thunk.sizeOf_eq {α : Type u_1} [inst : SizeOf α] (a : Thunk α) : sizeOf a = 1 + sizeOf (Thunk.get a)

instance thunkCoe {α : Type u_1} : CoeTail α (Thunk α)

Equations

• thunkCoe = { coe := fun a => { fn := fun x => a } }

structure Iff (a : Prop) (b : Prop) : Prop

• intro :: (

• Modus ponens for if and only if. If a ↔ b and a, then b.

  mp : a → b

• Modus ponens for if and only if, reversed. If a ↔ b and b, then a.

  mpr : b → a
• )

If and only if, or logical bi-implication. a ↔ b means that a implies b and vice versa. By propext, this implies that a and b are equal and hence any expression involving a is equivalent to the corresponding expression with b instead.

def «term_<->_» : Lean.TrailingParserDescr

If and only if, or logical bi-implication. a ↔ b means that a implies b and vice versa. By propext, this implies that a and b are equal and hence any expression involving a is equivalent to the corresponding expression with b instead.

Equations

• «term_<->_» = Lean.ParserDescr.trailingNode `term_<->_ 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " <-> ") (Lean.ParserDescr.cat `term 21))

def «term_↔_» : Lean.TrailingParserDescr

If and only if, or logical bi-implication. a ↔ b means that a implies b and vice versa. By propext, this implies that a and b are equal and hence any expression involving a is equivalent to the corresponding expression with b instead.

Equations

• «term_↔_» = Lean.ParserDescr.trailingNode `term_↔_ 20 21 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ↔ ") (Lean.ParserDescr.cat `term 21))

inductive Sum (α : Type u) (β : Type v) : Type (maxuv)

• Left injection into the sum type α ⊕ β. If a : α then .inl a : α ⊕ β.

  inl: {α : Type u} → {β : Type v} → α → α ⊕ β

• Right injection into the sum type α ⊕ β. If b : β then .inr b : α ⊕ β.

  inr: {α : Type u} → {β : Type v} → β → α ⊕ β

Sum α β, or α ⊕ β, is the disjoint union of types α and β. An element of α ⊕ β is either of the form .inl a where a : α, or .inr b where b : β.

def «term_⊕_» : Lean.TrailingParserDescr

Sum α β, or α ⊕ β, is the disjoint union of types α and β. An element of α ⊕ β is either of the form .inl a where a : α, or .inr b where b : β.

Equations

• «term_⊕_» = Lean.ParserDescr.trailingNode `term_⊕_ 30 31 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⊕ ") (Lean.ParserDescr.cat `term 30))

inductive PSum (α : Sort u) (β : Sort v) : Sort (max(max1u)v)

• Left injection into the sum type α ⊕' β. If a : α then .inl a : α ⊕' β.

  inl: {α : Sort u} → {β : Sort v} → α → α ⊕' β

• Right injection into the sum type α ⊕' β. If b : β then .inr b : α ⊕' β.

  inr: {α : Sort u} → {β : Sort v} → β → α ⊕' β

PSum α β, or α ⊕' β, is the disjoint union of types α and β. It differs from α ⊕ β in that it allows α and β to have arbitrary sorts Sort u and Sort v, instead of restricting to Type u and Type v. This means that it can be used in situations where one side is a proposition, like True ⊕' Nat.

The reason this is not the default is that this type lives in the universe Sort (max 1 u v), which can cause problems for universe level unification, because the equation max 1 u v = ?u + 1 has no solution in level arithmetic. PSum is usually only used in automation that constructs sums of arbitrary types.

def «term_⊕'_» : Lean.TrailingParserDescr

PSum α β, or α ⊕' β, is the disjoint union of types α and β. It differs from α ⊕ β in that it allows α and β to have arbitrary sorts Sort u and Sort v, instead of restricting to Type u and Type v. This means that it can be used in situations where one side is a proposition, like True ⊕' Nat.

The reason this is not the default is that this type lives in the universe Sort (max 1 u v), which can cause problems for universe level unification, because the equation max 1 u v = ?u + 1 has no solution in level arithmetic. PSum is usually only used in automation that constructs sums of arbitrary types.

Equations

• «term_⊕'_» = Lean.ParserDescr.trailingNode `term_⊕'_ 30 31 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⊕' ") (Lean.ParserDescr.cat `term 30))

@[unbox]

structure Sigma {α : Type u} (β : α → Type v) : Type (maxuv)

• The first component of a dependent pair. If p : @Sigma α β then p.1 : α.

  fst : α

• The second component of a dependent pair. If p : Sigma β then p.2 : β p.1.

  snd : β fst

Sigma β, also denoted Σ a : α, β a or (a : α) × β a, is the type of dependent pairs whose first component is a : α and whose second component is b : β a (so the type of the second component can depend on the value of the first component). It is sometimes known as the dependent sum type, since it is the type level version of an indexed summation.

structure PSigma {α : Sort u} (β : α → Sort v) : Sort (max(max1u)v)

• The first component of a dependent pair. If p : @Sigma α β then p.1 : α.

  fst : α

• The second component of a dependent pair. If p : Sigma β then p.2 : β p.1.

  snd : β fst

PSigma β, also denoted Σ' a : α, β a or (a : α) ×' β a, is the type of dependent pairs whose first component is a : α and whose second component is b : β a (so the type of the second component can depend on the value of the first component). It differs from Σ a : α, β a in that it allows α and β to have arbitrary sorts Sort u and Sort v, instead of restricting to Type u and Type v. This means that it can be used in situations where one side is a proposition, like (p : Nat) ×' p = p.

The reason this is not the default is that this type lives in the universe Sort (max 1 u v), which can cause problems for universe level unification, because the equation max 1 u v = ?u + 1 has no solution in level arithmetic. PSigma is usually only used in automation that constructs pairs of arbitrary types.

inductive Exists {α : Sort u} (p : α → Prop) : Prop

• Existential introduction. If a : α and h : p a, then ⟨a, h⟩ is a proof that ∃ x : α, p x.

  intro: ∀ {α : Sort u} {p : α → Prop} (w : α), p w → Exists p

Existential quantification. If p : α → Prop is a predicate, then ∃ x : α, p x asserts that there is some x of type α such that p x holds. To create an existential proof, use the exists tactic, or the anonymous constructor notation ⟨x, h⟩. To unpack an existential, use cases h where h is a proof of ∃ x : α, p x, or let ⟨x, hx⟩ := h where `.

Because Lean has proof irrelevance, any two proofs of an existential are definitionally equal. One consequence of this is that it is impossible to recover the witness of an existential from the mere fact of its existence. For example, the following does not compile:

example (h : ∃ x : Nat, x = x) : Nat :=
  let ⟨x, _⟩ := h  -- fail, because the goal is `Nat : Type`
  x

The error message recursor 'Exists.casesOn' can only eliminate into Prop means that this only works when the current goal is another proposition:

example (h : ∃ x : Nat, x = x) : True :=
  let ⟨x, _⟩ := h  -- ok, because the goal is `True : Prop`
  trivial

inductive ForInStep (α : Type u) : Type u

• .done a means that we should early-exit the loop. .done is produced by calls to break or return in the loop.

  done: {α : Type u} → α → ForInStep α

• .yield a means that we should continue the loop. .yield is produced by continue and reaching the bottom of the loop body.

  yield: {α : Type u} → α → ForInStep α

Auxiliary type used to compile for x in xs notation.

This is the return value of the body of a ForIn call, representing the body of a for loop. It can be:

• .yield (a : α), meaning that we should continue the loop and a is the new state. .yield is produced by continue and reaching the bottom of the loop body.
• .done (a : α), meaning that we should early-exit the loop with state a. .done is produced by calls to break or return in the loop,

instance instInhabitedForInStep : {a : Type u_1} → [inst : Inhabited a] → Inhabited (ForInStep a)

Equations

• instInhabitedForInStep = { default := ForInStep.done default }

class ForIn (m : Type u₁ → Type u₂) (ρ : Type u) (α : outParam (Type v)) : Type (max(max(maxu(u₁+1))u₂)v)

• forIn x b f : m β runs a for-loop in the monad m with additional state β. This traverses over the "contents" of x, and passes the elements a : α to f : α → β → m (ForInStep β). b : β is the initial state, and the return value of f is the new state as well as a directive .done or .yield which indicates whether to abort early or continue iteration.

  The expression

  let mut b := ...
  for x in xs do
    b ← foo x b
  

  in a do block is syntactic sugar for:

  let b := ...
  let b ← forIn xs b (fun x b => do
    let b ← foo x b
    return .yield b)
  

  (Here b corresponds to the variables mutated in the loop.)

  forIn : {β : Type u₁} → [inst : Monad m] → ρ → β → (α → β → m (ForInStep β)) → m β

ForIn m ρ α is the typeclass which supports for x in xs notation. Here xs : ρ is the type of the collection to iterate over, x : α is the element type which is made available inside the loop, and m is the monad for the encompassing do block.

class ForIn' (m : Type u₁ → Type u₂) (ρ : Type u) (α : outParam (Type v)) (d : outParam (Membership α ρ)) : Type (max(max(maxu(u₁+1))u₂)v)

• forIn' x b f : m β runs a for-loop in the monad m with additional state β. This traverses over the "contents" of x, and passes the elements a : α along with a proof that a ∈ x to f : (a : α) → a ∈ x → β → m (ForInStep β). b : β is the initial state, and the return value of f is the new state as well as a directive .done or .yield which indicates whether to abort early or continue iteration.

  forIn' : {β : Type u₁} → [inst : Monad m] → (x : ρ) → β → ((a : α) → a ∈ x → β → m (ForInStep β)) → m β

ForIn' m ρ α d is a variation on the ForIn m ρ α typeclass which supports the for h : x in xs notation. It is the same as for x in xs except that h : x ∈ xs is provided as an additional argument to the body of the for-loop.

inductive DoResultPRBC (α : Type u) (β : Type u) (σ : Type u) : Type u

• pure (a : α) s means that the block exited normally with return value a

  pure: {α β σ : Type u} → α → σ → DoResultPRBC α β σ

• return (b : β) s means that the block exited via a return b early-exit command

  return: {α β σ : Type u} → β → σ → DoResultPRBC α β σ

• break s means that break was called, meaning that we should exit from the containing loop

  break: {α β σ : Type u} → σ → DoResultPRBC α β σ

• continue s means that continue was called, meaning that we should continue to the next iteration of the containing loop

  continue: {α β σ : Type u} → σ → DoResultPRBC α β σ

Auxiliary type used to compile do notation. It is used when compiling a do block nested inside a combinator like tryCatch. It encodes the possible ways the block can exit:

• pure (a : α) s means that the block exited normally with return value a.
• return (b : β) s means that the block exited via a return b early-exit command.
• break s means that break was called, meaning that we should exit from the containing loop.
• continue s means that continue was called, meaning that we should continue to the next iteration of the containing loop.

All cases return a value s : σ which bundles all the mutable variables of the do-block.

inductive DoResultPR (α : Type u) (β : Type u) (σ : Type u) : Type u

• pure (a : α) s means that the block exited normally with return value a

  pure: {α β σ : Type u} → α → σ → DoResultPR α β σ

• return (b : β) s means that the block exited via a return b early-exit command

  return: {α β σ : Type u} → β → σ → DoResultPR α β σ

Auxiliary type used to compile do notation. It is the same as DoResultPRBC α β σ except that break and continue are not available because we are not in a loop context.

inductive DoResultBC (σ : Type u) : Type u

• break s means that break was called, meaning that we should exit from the containing loop

  break: {σ : Type u} → σ → DoResultBC σ

• continue s means that continue was called, meaning that we should continue to the next iteration of the containing loop

  continue: {σ : Type u} → σ → DoResultBC σ

Auxiliary type used to compile do notation. It is an optimization of DoResultPRBC PEmpty PEmpty σ to remove the impossible cases, used when neither pure nor return are possible exit paths.

inductive DoResultSBC (α : Type u) (σ : Type u) : Type u

• This encodes either pure (a : α) or return (a : α):

  • pure (a : α) s means that the block exited normally with return value a
  • return (b : β) s means that the block exited via a return b early-exit command

  The one that is actually encoded depends on the context of use.

  pureReturn: {α σ : Type u} → α → σ → DoResultSBC α σ

• break s means that break was called, meaning that we should exit from the containing loop

  break: {α σ : Type u} → σ → DoResultSBC α σ

• continue s means that continue was called, meaning that we should continue to the next iteration of the containing loop

  continue: {α σ : Type u} → σ → DoResultSBC α σ

Auxiliary type used to compile do notation. It is an optimization of either DoResultPRBC α PEmpty σ or DoResultPRBC PEmpty α σ to remove the impossible case, used when either pure or return is never used.

class HasEquiv (α : Sort u) : Sort (maxu(v+1))

• x ≈ y says that x and y are equivalent. Because this is a typeclass, the notion of equivalence is type-dependent.

  Equiv : α → α → Sort v

HasEquiv α is the typeclass which supports the notation x ≈ y where x y : α.

def «term_≈_» : Lean.TrailingParserDescr

x ≈ y says that x and y are equivalent. Because this is a typeclass, the notion of equivalence is type-dependent.

Equations

• «term_≈_» = Lean.ParserDescr.trailingNode `term_≈_ 50 51 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ≈ ") (Lean.ParserDescr.cat `term 51))

class EmptyCollection (α : Type u) : Type u

• ∅ or {} is the empty set or empty collection. It is supported by the EmptyCollection typeclass.

  emptyCollection : α

EmptyCollection α is the typeclass which supports the notation ∅, also written as {}.

def «term{}» : Lean.ParserDescr

∅ or {} is the empty set or empty collection. It is supported by the EmptyCollection typeclass.

Equations

• «term{}» = Lean.ParserDescr.node `term{} 1024 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol "{") (Lean.ParserDescr.symbol "}"))

def «term∅» : Lean.ParserDescr

∅ or {} is the empty set or empty collection. It is supported by the EmptyCollection typeclass.

Equations

• «term∅» = Lean.ParserDescr.node `term∅ 1024 (Lean.ParserDescr.symbol "∅")

structure Task (α : Type u) : Type u

• pure :: (

• If task : Task α then task.get : α blocks the current thread until the value is available, and then returns the result of the task.

  get : α
• )

Task α is a primitive for asynchronous computation. It represents a computation that will resolve to a value of type α, possibly being computed on another thread. This is similar to Future in Scala, Promise in Javascript, and JoinHandle in Rust.

The tasks have an overridden representation in the runtime.

instance instInhabitedTask : {a : Type u_1} → [inst : Inhabited a] → Inhabited (Task a)

Equations

• instInhabitedTask = { default := { get := default } }

instance instNonemptyTask : ∀ {α : Type u_1} [inst : Nonempty α], Nonempty (Task α)

Equations

• @instNonemptyTask = @instNonemptyTask.proof_1

@[inline]

abbrev Task.Priority : Type

Task priority. Tasks with higher priority will always be scheduled before ones with lower priority.

Equations

• Task.Priority = Nat

def Task.Priority.default : Task.Priority

The default priority for spawned tasks, also the lowest priority: 0.

Equations

• Task.Priority.default = 0

def Task.Priority.max : Task.Priority

The highest regular priority for spawned tasks: 8.

Spawning a task with a priority higher than Task.Priority.max is not an error but will spawn a dedicated worker for the task, see Task.Priority.dedicated. Regular priority tasks are placed in a thread pool and worked on according to the priority order.

Equations

• Task.Priority.max = 8

def Task.Priority.dedicated : Task.Priority

Any priority higher than Task.Priority.max will result in the task being scheduled immediately on a dedicated thread. This is particularly useful for long-running and/or I/O-bound tasks since Lean will by default allocate no more non-dedicated workers than the number of cores to reduce context switches.

Equations

• Task.Priority.dedicated = 9

@[noinline, extern lean_task_spawn]

def Task.spawn {α : Type u} (fn : Unit → α) (prio : optParam Task.Priority Task.Priority.default) : Task α

spawn fn : Task α constructs and immediately launches a new task for evaluating the function fn () : α asynchronously.

prio, if provided, is the priority of the task.

Equations

• Task.spawn fn prio = { get := fn () }

@[noinline, extern lean_task_map]

def Task.map {α : Type u} {β : Type v} (f : α → β) (x : Task α) (prio : optParam Task.Priority Task.Priority.default) : Task β

map f x maps function f over the task x: that is, it constructs (and immediately launches) a new task which will wait for the value of x to be available and then calls f on the result.

prio, if provided, is the priority of the task.

Equations

• Task.map f x prio = { get := f x.get }

@[noinline, extern lean_task_bind]

def Task.bind {α : Type u} {β : Type v} (x : Task α) (f : α → Task β) (prio : optParam Task.Priority Task.Priority.default) : Task β

bind x f does a monad "bind" operation on the task x with function f: that is, it constructs (and immediately launches) a new task which will wait for the value of x to be available and then calls f on the result, resulting in a new task which is then run for a result.

prio, if provided, is the priority of the task.

Equations

• Task.bind x f prio = { get := (f x.get).get }

structure NonScalar : Type

• You should not use this function

  val : Nat

NonScalar is a type that is not a scalar value in our runtime. It is used as a stand-in for an arbitrary boxed value to avoid excessive monomorphization, and it is only created using unsafeCast. It is somewhat analogous to C void* in usage, but the type itself is not special.

inductive PNonScalar : Type u

• You should not use this function

  mk: Nat → PNonScalar

PNonScalar is a type that is not a scalar value in our runtime. It is used as a stand-in for an arbitrary boxed value to avoid excessive monomorphization, and it is only created using unsafeCast. It is somewhat analogous to C void* in usage, but the type itself is not special.

This is the universe-polymorphic version of PNonScalar; it is preferred to use NonScalar instead where applicable.

@[simp]

theorem Nat.add_zero (n : Nat) : n + 0 = n

theorem optParam_eq (α : Sort u) (default : α) : optParam α default = α

Boolean operators

@[extern c inline "#1 || #2"]

def strictOr (b₁ : Bool) (b₂ : Bool) : Bool

strictOr is the same as or, but it does not use short-circuit evaluation semantics: both sides are evaluated, even if the first value is true.

Equations

• strictOr b₁ b₂ = (b₁ || b₂)

@[extern c inline "#1 && #2"]

def strictAnd (b₁ : Bool) (b₂ : Bool) : Bool

strictAnd is the same as and, but it does not use short-circuit evaluation semantics: both sides are evaluated, even if the first value is false.

Equations

• strictAnd b₁ b₂ = (b₁ && b₂)

@[inline]

def bne {α : Type u} [inst : BEq α] (a : α) (b : α) : Bool

x != y is boolean not-equal. It is the negation of x == y which is supplied by the BEq typeclass.

Unlike x ≠ y (which is notation for Ne x y), this is Bool valued instead of Prop valued. It is mainly intended for programming applications.

Equations

• (a != b) = !a == b

def «term_!=_» : Lean.TrailingParserDescr

x != y is boolean not-equal. It is the negation of x == y which is supplied by the BEq typeclass.

Unlike x ≠ y (which is notation for Ne x y), this is Bool valued instead of Prop valued. It is mainly intended for programming applications.

Equations

• «term_!=_» = Lean.ParserDescr.trailingNode `term_!=_ 50 51 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " != ") (Lean.ParserDescr.cat `term 51))

class LawfulBEq (α : Type u) [inst : BEq α] : Prop

• If a == b evaluates to true, then a and b are equal in the logic.

  eq_of_beq : ∀ {a b : α}, (a == b) = true → a = b

• == is reflexive, that is, (a == a) = true.

  rfl : ∀ {a : α}, (a == a) = true

LawfulBEq α is a typeclass which asserts that the BEq α implementation (which supplies the a == b notation) coincides with logical equality a = b. In other words, a == b implies a = b, and a == a is true.

instance instLawfulBEqBoolInstBEqInstDecidableEqBool : LawfulBEq Bool

Equations

• instLawfulBEqBoolInstBEqInstDecidableEqBool = instLawfulBEqBoolInstBEqInstDecidableEqBool.proof_1

instance instLawfulBEqInstBEq {α : Type u_1} [inst : DecidableEq α] : LawfulBEq α

Equations

• @instLawfulBEqInstBEq = @instLawfulBEqInstBEq.proof_1

instance instLawfulBEqCharInstBEqInstDecidableEqChar : LawfulBEq Char

Equations

• instLawfulBEqCharInstBEqInstDecidableEqChar = instLawfulBEqCharInstBEqInstDecidableEqChar.proof_1

instance instLawfulBEqStringInstBEqInstDecidableEqString : LawfulBEq String

Equations

• instLawfulBEqStringInstBEqInstDecidableEqString = instLawfulBEqStringInstBEqInstDecidableEqString.proof_1

Logical connectives and equality

def trivial : True

True is true, and True.intro (or more commonly, trivial) is the proof.

Equations

• trivial = True.intro

theorem mt {a : Prop} {b : Prop} (h₁ : a → b) (h₂ : ¬b) : ¬a

theorem not_false : ¬False

theorem not_not_intro {p : Prop} (h : p) : ¬¬p

theorem proofIrrel {a : Prop} (h₁ : a) (h₂ : a) : h₁ = h₂

theorem id.def {α : Sort u} (a : α) : id a = a

@[macro_inline]

def Eq.mp {α : Sort u} {β : Sort u} (h : α = β) (a : α) : β

If h : α = β is a proof of type equality, then h.mp : α → β is the induced "cast" operation, mapping elements of α to elements of β.

You can prove theorems about the resulting element by induction on h, since rfl.mp is definitionally the identity function.

Equations

• Eq.mp h a = h ▸ a

@[macro_inline]

def Eq.mpr {α : Sort u} {β : Sort u} (h : α = β) (b : β) : α

If h : α = β is a proof of type equality, then h.mpr : β → α is the induced "cast" operation in the reverse direction, mapping elements of β to elements of α.

You can prove theorems about the resulting element by induction on h, since rfl.mpr is definitionally the identity function.

Equations

• Eq.mpr h b = (_ : β = α) ▸ b

theorem Eq.substr {α : Sort u} {p : α → Prop} {a : α} {b : α} (h₁ : b = a) (h₂ : p a) : p b

theorem cast_eq {α : Sort u} (h : α = α) (a : α) : cast h a = a

def Ne {α : Sort u} (a : α) (b : α) : Prop

a ≠ b, or Ne a b is defined as ¬ (a = b) or a = b → False, and asserts that a and b are not equal.

Equations

• (a ≠ b) = ¬a = b

def «term_≠_» : Lean.TrailingParserDescr

a ≠ b, or Ne a b is defined as ¬ (a = b) or a = b → False, and asserts that a and b are not equal.

Equations

• «term_≠_» = Lean.ParserDescr.trailingNode `term_≠_ 50 51 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ≠ ") (Lean.ParserDescr.cat `term 51))

theorem Ne.intro {α : Sort u} {a : α} {b : α} (h : a = b → False) : a ≠ b

theorem Ne.elim {α : Sort u} {a : α} {b : α} (h : a ≠ b) : a = b → False

theorem Ne.irrefl {α : Sort u} {a : α} (h : a ≠ a) : False

theorem Ne.symm {α : Sort u} {a : α} {b : α} (h : a ≠ b) : b ≠ a

theorem false_of_ne {α : Sort u} {a : α} : a ≠ a → False

theorem ne_false_of_self {p : Prop} : p → p ≠ False

theorem ne_true_of_not {p : Prop} : ¬p → p ≠ True

theorem true_ne_false : ¬True = False

theorem Bool.of_not_eq_true {b : Bool} : ¬b = true → b = false

theorem Bool.of_not_eq_false {b : Bool} : ¬b = false → b = true

theorem ne_of_beq_false {α : Type u_1} [inst : BEq α] [inst : LawfulBEq α] {a : α} {b : α} (h : (a == b) = false) : a ≠ b

theorem beq_false_of_ne {α : Type u_1} [inst : BEq α] [inst : LawfulBEq α] {a : α} {b : α} (h : a ≠ b) : (a == b) = false

theorem HEq.ndrec {α : Sort u2} {a : α} {motive : {β : Sort u2} → β → Sort u1} (m : motive α a) {β : Sort u2} {b : β} (h : HEq a b) : motive β b

theorem HEq.ndrecOn {α : Sort u2} {a : α} {motive : {β : Sort u2} → β → Sort u1} {β : Sort u2} {b : β} (h : HEq a b) (m : motive α a) : motive β b

theorem HEq.elim {α : Sort u} {a : α} {p : α → Sort v} {b : α} (h₁ : HEq a b) (h₂ : p a) : p b

theorem HEq.subst {α : Sort u} {β : Sort u} {a : α} {b : β} {p : (T : Sort u) → T → Prop} (h₁ : HEq a b) (h₂ : p α a) : p β b

theorem HEq.symm {α : Sort u} {β : Sort u} {a : α} {b : β} (h : HEq a b) : HEq b a

theorem heq_of_eq {α : Sort u} {a : α} {a' : α} (h : a = a') : HEq a a'

theorem HEq.trans {α : Sort u} {β : Sort u} {φ : Sort u} {a : α} {b : β} {c : φ} (h₁ : HEq a b) (h₂ : HEq b c) : HEq a c

theorem heq_of_heq_of_eq {α : Sort u} {β : Sort u} {a : α} {b : β} {b' : β} (h₁ : HEq a b) (h₂ : b = b') : HEq a b'

theorem heq_of_eq_of_heq {α : Sort u} {β : Sort u} {a : α} {a' : α} {b : β} (h₁ : a = a') (h₂ : HEq a' b) : HEq a b

theorem type_eq_of_heq {α : Sort u} {β : Sort u} {a : α} {b : β} (h : HEq a b) : α = β

theorem eqRec_heq {α : Sort u} {φ : α → Sort v} {a : α} {a' : α} (h : a = a') (p : φ a) : HEq (Eq.recOn h p) p

theorem heq_of_eqRec_eq {α : Sort u} {β : Sort u} {a : α} {b : β} (h₁ : α = β) (h₂ : h₁ ▸ a = b) : HEq a b

theorem cast_heq {α : Sort u} {β : Sort u} (h : α = β) (a : α) : HEq (cast h a) a

theorem iff_iff_implies_and_implies (a : Prop) (b : Prop) : (a ↔ b) ↔ (a → b) ∧ (b → a)

theorem Iff.refl (a : Prop) : a ↔ a

theorem Iff.rfl {a : Prop} : a ↔ a

theorem Iff.trans {a : Prop} {b : Prop} {c : Prop} (h₁ : a ↔ b) (h₂ : b ↔ c) : a ↔ c

theorem Iff.symm {a : Prop} {b : Prop} (h : a ↔ b) : b ↔ a

theorem Iff.comm {a : Prop} {b : Prop} : (a ↔ b) ↔ (b ↔ a)

theorem Iff.of_eq {a : Prop} {b : Prop} (h : a = b) : a ↔ b

theorem And.comm {a : Prop} {b : Prop} : a ∧ b ↔ b ∧ a

Exists

theorem Exists.elim {α : Sort u} {p : α → Prop} {b : Prop} (h₁ : ∃ x, p x) (h₂ : (a : α) → p a → b) : b

Decidable

theorem decide_true_eq_true (h : Decidable True) : decide True = true

theorem decide_false_eq_false (h : Decidable False) : decide False = false

@[inline]

def toBoolUsing {p : Prop} (d : Decidable p) : Bool

Similar to decide, but uses an explicit instance

Equations

• toBoolUsing d = decide p

theorem toBoolUsing_eq_true {p : Prop} (d : Decidable p) (h : p) : toBoolUsing d = true

theorem ofBoolUsing_eq_true {p : Prop} {d : Decidable p} (h : toBoolUsing d = true) : p

theorem ofBoolUsing_eq_false {p : Prop} {d : Decidable p} (h : toBoolUsing d = false) : ¬p

instance instDecidableTrue : Decidable True

Equations

• instDecidableTrue = isTrue trivial

instance instDecidableFalse : Decidable False

Equations

• instDecidableFalse = isFalse not_false

@[macro_inline]

def Decidable.byCases {p : Prop} {q : Sort u} [dec : Decidable p] (h1 : p → q) (h2 : ¬p → q) : q

Synonym for dite (dependent if-then-else). We can construct an element q (of any sort, not just a proposition) by cases on whether p is true or false, provided p is decidable.

Equations

• Decidable.byCases h1 h2 = match dec with | isTrue h => h1 h | isFalse h => h2 h

theorem Decidable.em (p : Prop) [inst : Decidable p] : p ∨ ¬p

theorem Decidable.byContradiction {p : Prop} [dec : Decidable p] (h : ¬p → False) : p

theorem Decidable.of_not_not {p : Prop} [inst : Decidable p] : ¬¬p → p

theorem Decidable.not_and_iff_or_not (p : Prop) (q : Prop) [d₁ : Decidable p] [d₂ : Decidable q] : ¬(p ∧ q) ↔ ¬p ∨ ¬q

@[inline]

def decidable_of_decidable_of_iff {p : Prop} {q : Prop} [inst : Decidable p] (h : p ↔ q) : Decidable q

Transfer a decidability proof across an equivalence of propositions.

Equations

• decidable_of_decidable_of_iff h = if hp : p then isTrue (Iff.mp h hp) else isFalse (_ : q → False)

@[inline]

def decidable_of_decidable_of_eq {p : Prop} {q : Prop} [inst : Decidable p] (h : p = q) : Decidable q

Transfer a decidability proof across an equality of propositions.

Equations

• decidable_of_decidable_of_eq h = decidable_of_decidable_of_iff (_ : p ↔ q)

@[macro_inline]

instance instDecidableForAll {p : Prop} {q : Prop} [inst : Decidable p] [inst : Decidable q] : Decidable (p → q)

Equations

• instDecidableForAll = if hp : p then if hq : q then isTrue (instDecidableForAll.proof_1 hq) else isFalse (_ : (p → q) → False) else isTrue (instDecidableForAll.proof_3 hp)

instance instDecidableIff {p : Prop} {q : Prop} [inst : Decidable p] [inst : Decidable q] : Decidable (p ↔ q)

Equations

• instDecidableIff = if hp : p then if hq : q then isTrue (_ : p ↔ q) else isFalse (_ : (p ↔ q) → False) else if hq : q then isFalse (_ : (p ↔ q) → False) else isTrue (_ : p ↔ q)

if-then-else expression theorems

theorem if_pos {c : Prop} {h : Decidable c} (hc : c) {α : Sort u} {t : α} {e : α} : (if c then t else e) = t

theorem if_neg {c : Prop} {h : Decidable c} (hnc : ¬c) {α : Sort u} {t : α} {e : α} : (if c then t else e) = e

theorem dif_pos {c : Prop} {h : Decidable c} (hc : c) {α : Sort u} {t : c → α} {e : ¬c → α} : dite c t e = t hc

theorem dif_neg {c : Prop} {h : Decidable c} (hnc : ¬c) {α : Sort u} {t : c → α} {e : ¬c → α} : dite c t e = e hnc

theorem dif_eq_if (c : Prop) {h : Decidable c} {α : Sort u} (t : α) (e : α) : (if x : c then t else e) = if c then t else e

instance instDecidableIteProp {c : Prop} {t : Prop} {e : Prop} [dC : Decidable c] [dT : Decidable t] [dE : Decidable e] : Decidable (if c then t else e)

Equations

• instDecidableIteProp = match dC with | isTrue h => dT | isFalse h => dE

instance instDecidableDitePropNot {c : Prop} {t : c → Prop} {e : ¬c → Prop} [dC : Decidable c] [dT : (h : c) → Decidable (t h)] [dE : (h : ¬c) → Decidable (e h)] : Decidable (if h : c then t h else e h)

Equations

• instDecidableDitePropNot = match dC with | isTrue hc => dT hc | isFalse hc => dE hc

@[inline]

abbrev noConfusionTypeEnum {α : Sort u} {β : Sort v} [inst : DecidableEq β] (f : α → β) (P : Sort w) (x : α) (y : α) : Sort w

Auxiliary definition for generating compact noConfusion for enumeration types

Equations

• noConfusionTypeEnum f P x y = Decidable.casesOn (inst (f x) (f y)) (fun x => P) fun x => P → P

@[inline]

abbrev noConfusionEnum {α : Sort u} {β : Sort v} [inst : DecidableEq β] (f : α → β) {P : Sort w} {x : α} {y : α} (h : x = y) : noConfusionTypeEnum f P x y

Auxiliary definition for generating compact noConfusion for enumeration types

Equations

• noConfusionEnum f h = Decidable.casesOn (inst (f x) (f y)) (fun h' => False.elim (_ : False)) fun x x => x

Inhabited

instance instInhabitedProp : Inhabited Prop

Equations

• instInhabitedProp = { default := True }

instance instInhabitedForInStep_1 : {a : Type u_1} → [inst : Inhabited a] → Inhabited (ForInStep a)

Equations

• instInhabitedForInStep_1 = { default := ForInStep.done default }

instance instInhabitedTrue : Inhabited True

Equations

• instInhabitedTrue = { default := True.intro }

instance instInhabitedPNonScalar : Inhabited PNonScalar

Equations

• instInhabitedPNonScalar = { default := PNonScalar.mk default }

instance instInhabitedNonScalar : Inhabited NonScalar

Equations

• instInhabitedNonScalar = { default := { val := default } }

theorem nonempty_of_exists {α : Sort u} {p : α → Prop} : (∃ x, p x) → Nonempty α

Subsingleton

class Subsingleton (α : Sort u) : Prop

• intro :: (

• Any two elements of a subsingleton are equal.

  allEq : ∀ (a b : α), a = b
• )

A "subsingleton" is a type with at most one element. In other words, it is either empty, or has a unique element. All propositions are subsingletons because of proof irrelevance, but some other types are subsingletons as well and they inherit many of the same properties as propositions. Subsingleton α is a typeclass, so it is usually used as an implicit argument and inferred by typeclass inference.

theorem Subsingleton.elim {α : Sort u} [h : Subsingleton α] (a : α) (b : α) : a = b

theorem Subsingleton.helim {α : Sort u} {β : Sort u} [h₁ : Subsingleton α] (h₂ : α = β) (a : α) (b : β) : HEq a b

instance instSubsingleton (p : Prop) : Subsingleton p

Equations

• instSubsingleton = instSubsingleton.proof_1

instance instSubsingletonDecidable (p : Prop) : Subsingleton (Decidable p)

Equations

• instSubsingletonDecidable = instSubsingletonDecidable.proof_1

theorem recSubsingleton {p : Prop} [h : Decidable p] {h₁ : p → Sort u} {h₂ : ¬p → Sort u} [h₃ : ∀ (h : p), Subsingleton (h₁ h)] [h₄ : ∀ (h : ¬p), Subsingleton (h₂ h)] : Subsingleton (Decidable.casesOn h h₂ h₁)

structure Equivalence {α : Sort u} (r : α → α → Prop) : Prop

• An equivalence relation is reflexive: x ~ x

  refl : (x : α) → r x x

• An equivalence relation is symmetric: x ~ y implies y ~ x

  symm : {x y : α} → r x y → r y x

• An equivalence relation is transitive: x ~ y and y ~ z implies x ~ z

  trans : {x y z : α} → r x y → r y z → r x z

An equivalence relation ~ : α → α → Prop is a relation that is:

• reflexive: x ~ x
• symmetric: x ~ y implies y ~ x
• transitive: x ~ y and y ~ z implies x ~ z

Equality is an equivalence relation, and equivalence relations share many of the properties of equality. In particular, Quot α r is most well behaved when r is an equivalence relation, and in this case we use Quotient instead.

def emptyRelation {α : Sort u} : α → α → Prop

The empty relation is the relation on α which is always False.

Equations

• emptyRelation x x = False

def Subrelation {α : Sort u} (q : α → α → Prop) (r : α → α → Prop) : Prop

Subrelation q r means that q ⊆ r or ∀ x y, q x y → r x y. It is the analogue of the subset relation on relations.

Equations

• Subrelation q r = ({x y : α} → q x y → r x y)

def InvImage {α : Sort u} {β : Sort v} (r : β → β → Prop) (f : α → β) : α → α → Prop

The inverse image of r : β → β → Prop by a function α → β is the relation s : α → α → Prop defined by s a b = r (f a) (f b).

Equations

• InvImage r f a₁ a₂ = r (f a₁) (f a₂)

inductive TC {α : Sort u} (r : α → α → Prop) : α → α → Prop

• If r a b then r⁺ a b. This is the base case of the transitive closure.

  base: ∀ {α : Sort u} {r : α → α → Prop} (a b : α), r a b → TC r a b

• The transitive closure is transitive.

  trans: ∀ {α : Sort u} {r : α → α → Prop} (a b c : α), TC r a b → TC r b c → TC r a c

The transitive closure r⁺ of a relation r is the smallest relation which is transitive and contains r. r⁺ a z if and only if there exists a sequence a r b r ... r z of length at least 1 connecting a to z.

Subtype

theorem Subtype.existsOfSubtype {α : Type u} {p : α → Prop} : { x // p x } → ∃ x, p x

theorem Subtype.eq {α : Type u} {p : α → Prop} {a1 : { x // p x }} {a2 : { x // p x }} : a1.val = a2.val → a1 = a2

theorem Subtype.eta {α : Type u} {p : α → Prop} (a : { x // p x }) (h : p a.val) : { val := a.val, property := h } = a

instance Subtype.instInhabitedSubtype {α : Type u} {p : α → Prop} {a : α} (h : p a) : Inhabited { x // p x }

Equations

• Subtype.instInhabitedSubtype h = { default := { val := a, property := h } }

instance Subtype.instDecidableEqSubtype {α : Type u} {p : α → Prop} [inst : DecidableEq α] : DecidableEq { x // p x }

Equations

• One or more equations did not get rendered due to their size.

Sum

instance Sum.inhabitedLeft {α : Type u} {β : Type v} [inst : Inhabited α] : Inhabited (α ⊕ β)

Equations

• Sum.inhabitedLeft = { default := Sum.inl default }

instance Sum.inhabitedRight {α : Type u} {β : Type v} [inst : Inhabited β] : Inhabited (α ⊕ β)

Equations

• Sum.inhabitedRight = { default := Sum.inr default }

instance instDecidableEqSum {α : Type u} {β : Type v} [inst : DecidableEq α] [inst : DecidableEq β] : DecidableEq (α ⊕ β)

Equations

• One or more equations did not get rendered due to their size.

Product

instance instInhabitedProd {α : Type u_1} {β : Type u_2} [inst : Inhabited α] [inst : Inhabited β] : Inhabited (α × β)

Equations

• instInhabitedProd = { default := (default, default) }

instance instInhabitedMProd {α : Type u_1} {β : Type u_1} [inst : Inhabited α] [inst : Inhabited β] : Inhabited (MProd α β)

Equations

• instInhabitedMProd = { default := { fst := default, snd := default } }

instance instInhabitedPProd {α : Sort u_1} {β : Sort u_2} [inst : Inhabited α] [inst : Inhabited β] : Inhabited (PProd α β)

Equations

• instInhabitedPProd = { default := { fst := default, snd := default } }

instance instDecidableEqProd {α : Type u_1} {β : Type u_2} [inst : DecidableEq α] [inst : DecidableEq β] : DecidableEq (α × β)

Equations

• One or more equations did not get rendered due to their size.

instance instBEqProd {α : Type u_1} {β : Type u_2} [inst : BEq α] [inst : BEq β] : BEq (α × β)

Equations

• instBEqProd = { beq := fun x x_1 => match x with | (a₁, b₁) => match x_1 with | (a₂, b₂) => a₁ == a₂ && b₁ == b₂ }

def Prod.lexLt {α : Type u_1} {β : Type u_2} [inst : LT α] [inst : LT β] (s : α × β) (t : α × β) : Prop

Lexicographical order for products

Equations

• Prod.lexLt s t = (s.fst < t.fst ∨ s.fst = t.fst ∧ s.snd < t.snd)

instance Prod.lexLtDec {α : Type u_1} {β : Type u_2} [inst : LT α] [inst : LT β] [inst : DecidableEq α] [inst : DecidableEq β] [inst : (a b : α) → Decidable (a < b)] [inst : (a b : β) → Decidable (a < b)] (s : α × β) (t : α × β) : Decidable (Prod.lexLt s t)

Equations

• Prod.lexLtDec x x = inferInstanceAs (Decidable (x.fst < x.fst ∨ x.fst = x.fst ∧ x.snd < x.snd))

theorem Prod.lexLt_def {α : Type u_1} {β : Type u_2} [inst : LT α] [inst : LT β] (s : α × β) (t : α × β) : Prod.lexLt s t = (s.fst < t.fst ∨ s.fst = t.fst ∧ s.snd < t.snd)

theorem Prod.eta {α : Type u_1} {β : Type u_2} (p : α × β) : (p.fst, p.snd) = p

def Prod.map {α₁ : Type u₁} {α₂ : Type u₂} {β₁ : Type v₁} {β₂ : Type v₂} (f : α₁ → α₂) (g : β₁ → β₂) : α₁ × β₁ → α₂ × β₂

Prod.map f g : α₁ × β₁ → α₂ × β₂ maps across a pair by applying f to the first component and g to the second.

Equations

• Prod.map f g x = match x with | (a, b) => (f a, g b)

Dependent products

theorem ex_of_PSigma {α : Type u} {p : α → Prop} : (x : α) ×' p x → ∃ x, p x

theorem PSigma.eta {α : Sort u} {β : α → Sort v} {a₁ : α} {a₂ : α} {b₁ : β a₁} {b₂ : β a₂} (h₁ : a₁ = a₂) (h₂ : h₁ ▸ b₁ = b₂) : { fst := a₁, snd := b₁ } = { fst := a₂, snd := b₂ }

Universe polymorphic unit

theorem PUnit.subsingleton (a : PUnit) (b : PUnit) : a = b

theorem PUnit.eq_punit (a : PUnit) : a = PUnit.unit

instance instSubsingletonPUnit : Subsingleton PUnit

Equations

• instSubsingletonPUnit = (_ : Subsingleton PUnit)

instance instInhabitedPUnit : Inhabited PUnit

Equations

• instInhabitedPUnit = { default := PUnit.unit }

instance instDecidableEqPUnit : DecidableEq PUnit

Equations

• instDecidableEqPUnit a b = isTrue (_ : a = b)

Setoid

class Setoid (α : Sort u) : Sort (max1u)

• x ≈ y is the distinguished equivalence relation of a setoid.

  r : α → α → Prop

• The relation x ≈ y is an equivalence relation.

  iseqv : Equivalence r

A setoid is a type with a distinguished equivalence relation, denoted ≈. This is mainly used as input to the Quotient type constructor.

instance instHasEquiv {α : Sort u} [inst : Setoid α] : HasEquiv α

Equations

• instHasEquiv = { Equiv := Setoid.r }

theorem Setoid.refl {α : Sort u} [inst : Setoid α] (a : α) : a ≈ a

theorem Setoid.symm {α : Sort u} [inst : Setoid α] {a : α} {b : α} (hab : a ≈ b) : b ≈ a

theorem Setoid.trans {α : Sort u} [inst : Setoid α] {a : α} {b : α} {c : α} (hab : a ≈ b) (hbc : b ≈ c) : a ≈ c

Propositional extensionality

axiom propext {a : Prop} {b : Prop} : (a ↔ b) → a = b

The axiom of propositional extensionality. It asserts that if propositions a and b are logically equivalent (i.e. we can prove a from b and vice versa), then a and b are equal, meaning that we can replace a with b in all contexts.

For simple expressions like a ∧ c ∨ d → e we can prove that because all the logical connectives respect logical equivalence, we can replace a with b in this expression without using propext. However, for higher order expressions like P a where P : Prop → Prop is unknown, or indeed for a = b itself, we cannot replace a with b without an axiom which says exactly this.

This is a relatively uncontroversial axiom, which is intuitionistically valid. It does however block computation when using #reduce to reduce proofs directly (which is not recommended), meaning that canonicity, the property that all closed terms of type Nat normalize to numerals, fails to hold when this (or any) axiom is used:

set_option pp.proofs true

def foo : Nat := by
  have : (True → True) ↔ True := ⟨λ _ => trivial, λ _ _ => trivial⟩
  have := propext this ▸ (2 : Nat)
  exact this

#reduce foo
-- propext { mp := fun x x => True.intro, mpr := fun x => True.intro } ▸ 2

#eval foo -- 2

#eval can evaluate it to a numeral because the compiler erases casts and does not evaluate proofs, so propext, whose return type is a proposition, can never block it.

theorem Eq.propIntro {a : Prop} {b : Prop} (h₁ : a → b) (h₂ : b → a) : a = b

instance instDecidableEqProp {p : Prop} {q : Prop} [d : Decidable (p ↔ q)] : Decidable (p = q)

Equations

• instDecidableEqProp = match d with | isTrue h => isTrue (_ : p = q) | isFalse h => isFalse (_ : p = q → False)

@[simp]

theorem beq_iff_eq {α : Type u_1} [inst : BEq α] [inst : LawfulBEq α] (a : α) (b : α) : (a == b) = true ↔ a = b

Quotients

theorem Iff.subst {a : Prop} {b : Prop} {p : Prop → Prop} (h₁ : a ↔ b) (h₂ : p a) : p b

Iff can now be used to do substitutions in a calculation

axiom Quot.sound {α : Sort u} {r : α → α → Prop} {a : α} {b : α} : r a b → Quot.mk r a = Quot.mk r b

The quotient axiom, or at least the nontrivial part of the quotient axiomatization. Quotient types are introduced by the init_quot command in Init.Prelude which introduces the axioms:

opaque Quot {α : Sort u} (r : α → α → Prop) : Sort u

opaque Quot.mk {α : Sort u} (r : α → α → Prop) (a : α) : Quot r

opaque Quot.lift {α : Sort u} {r : α → α → Prop} {β : Sort v} (f : α → β) :
  (∀ a b : α, r a b → f a = f b) → Quot r → β

opaque Quot.ind {α : Sort u} {r : α → α → Prop} {β : Quot r → Prop} :
  (∀ a : α, β (Quot.mk r a)) → ∀ q : Quot r, β q

All of these axioms are true if we assume Quot α r = α and Quot.mk and Quot.lift are identity functions, so they do not add much. However this axiom cannot be explained in that way (it is false for that interpretation), so the real power of quotient types come from this axiom.

It says that the quotient by r maps elements which are related by r to equal values in the quotient. Together with Quot.lift which says that functions which respect r can be lifted to functions on the quotient, we can deduce that Quot α r exactly consists of the equivalence classes with respect to r.

It is important to note that r need not be an equivalence relation in this axiom. When r is not an equivalence relation, we are actually taking a quotient with respect to the equivalence relation generated by r.

theorem Quot.liftBeta {α : Sort u} {r : α → α → Prop} {β : Sort v} (f : α → β) (c : ∀ (a b : α), r a b → f a = f b) (a : α) : Quot.lift f c (Quot.mk r a) = f a

theorem Quot.indBeta {α : Sort u} {r : α → α → Prop} {motive : Quot r → Prop} (p : (a : α) → motive (Quot.mk r a)) (a : α) : Quot.ind p (Quot.mk r a) = p a

@[inline]

abbrev Quot.liftOn {α : Sort u} {β : Sort v} {r : α → α → Prop} (q : Quot r) (f : α → β) (c : ∀ (a b : α), r a b → f a = f b) : β

Quot.liftOn q f h is the same as Quot.lift f h q. It just reorders the argument q : Quot r to be first.

Equations

• Quot.liftOn q f c = Quot.lift f c q

theorem Quot.inductionOn {α : Sort u} {r : α → α → Prop} {motive : Quot r → Prop} (q : Quot r) (h : (a : α) → motive (Quot.mk r a)) : motive q

theorem Quot.exists_rep {α : Sort u} {r : α → α → Prop} (q : Quot r) : ∃ a, Quot.mk r a = q

@[macro_inline]

def Quot.indep {α : Sort u} {r : α → α → Prop} {motive : Quot r → Sort v} (f : (a : α) → motive (Quot.mk r a)) (a : α) : PSigma motive

Auxiliary definition for Quot.rec.

Equations

• Quot.indep f a = { fst := Quot.mk r a, snd := f a }

theorem Quot.indepCoherent {α : Sort u} {r : α → α → Prop} {motive : Quot r → Sort v} (f : (a : α) → motive (Quot.mk r a)) (h : ∀ (a b : α) (p : r a b), (_ : Quot.mk r a = Quot.mk r b) ▸ f a = f b) (a : α) (b : α) : r a b → Quot.indep f a = Quot.indep f b

theorem Quot.liftIndepPr1 {α : Sort u} {r : α → α → Prop} {motive : Quot r → Sort v} (f : (a : α) → motive (Quot.mk r a)) (h : ∀ (a b : α) (p : r a b), (_ : Quot.mk r a = Quot.mk r b) ▸ f a = f b) (q : Quot r) : (Quot.lift (Quot.indep f) (_ : ∀ (a b : α), r a b → Quot.indep f a = Quot.indep f b) q).fst = q

@[inline]

abbrev Quot.rec {α : Sort u} {r : α → α → Prop} {motive : Quot r → Sort v} (f : (a : α) → motive (Quot.mk r a)) (h : ∀ (a b : α) (p : r a b), (_ : Quot.mk r a = Quot.mk r b) ▸ f a = f b) (q : Quot r) : motive q

Dependent recursion principle for Quot. This constructor can be tricky to use, so you should consider the simpler versions if they apply:

• Quot.lift, for nondependent functions
• Quot.ind, for theorems / proofs of propositions about quotients
• Quot.recOnSubsingleton, when the target type is a Subsingleton
• Quot.hrecOn, which uses HEq (f a) (f b) instead of a sound p ▸ f a = f b assummption

Equations

• One or more equations did not get rendered due to their size.

@[inline]

abbrev Quot.recOn {α : Sort u} {r : α → α → Prop} {motive : Quot r → Sort v} (q : Quot r) (f : (a : α) → motive (Quot.mk r a)) (h : ∀ (a b : α) (p : r a b), (_ : Quot.mk r a = Quot.mk r b) ▸ f a = f b) : motive q

Dependent recursion principle for Quot. This constructor can be tricky to use, so you should consider the simpler versions if they apply:

• Quot.lift, for nondependent functions
• Quot.ind, for theorems / proofs of propositions about quotients
• Quot.recOnSubsingleton, when the target type is a Subsingleton
• Quot.hrecOn, which uses HEq (f a) (f b) instead of a sound p ▸ f a = f b assummption

Equations

• Quot.recOn q f h = Quot.rec f h q

@[inline]

abbrev Quot.recOnSubsingleton {α : Sort u} {r : α → α → Prop} {motive : Quot r → Sort v} [h : ∀ (a : α), Subsingleton (motive (Quot.mk r a))] (q : Quot r) (f : (a : α) → motive (Quot.mk r a)) : motive q

Dependent induction principle for a quotient, when the target type is a Subsingleton. In this case the quotient's side condition is trivial so any function can be lifted.

Equations

• Quot.recOnSubsingleton q f = Quot.rec (fun a => f a) (_ : ∀ (a b : α) (p : r a b), (_ : Quot.mk r a = Quot.mk r b) ▸ f a = f b) q

@[inline]

abbrev Quot.hrecOn {α : Sort u} {r : α → α → Prop} {motive : Quot r → Sort v} (q : Quot r) (f : (a : α) → motive (Quot.mk r a)) (c : ∀ (a b : α), r a b → HEq (f a) (f b)) : motive q

Heterogeneous dependent recursion principle for a quotient. This may be easier to work with since it uses HEq instead of an Eq.ndrec in the hypothesis.

Equations

• Quot.hrecOn q f c = Quot.recOn q f (_ : ∀ (a b : α) (p : r a b), (_ : Quot.mk r a = Quot.mk r b) ▸ f a = f b)

def Quotient {α : Sort u} (s : Setoid α) : Sort u

Quotient α s is the same as Quot α r, but it is specialized to a setoid s (that is, an equivalence relation) instead of an arbitrary relation. Prefer Quotient over Quot if your relation is actually an equivalence relation.

Equations

• Quotient s = Quot Setoid.r

@[inline]

def Quotient.mk {α : Sort u} (s : Setoid α) (a : α) : Quotient s

The canonical quotient map into a Quotient.

Equations

• Quotient.mk s a = Quot.mk Setoid.r a

def Quotient.mk' {α : Sort u} [s : Setoid α] (a : α) : Quotient s

The canonical quotient map into a Quotient. (This synthesizes the setoid by typeclass inference.)

Equations

• Quotient.mk' a = Quotient.mk s a

def Quotient.sound {α : Sort u} {s : Setoid α} {a : α} {b : α} : a ≈ b → Quotient.mk s a = Quotient.mk s b

The analogue of Quot.sound: If a and b are related by the equivalence relation, then they have equal equivalence classes.

Equations

• @Quotient.sound = @Quotient.sound.proof_1

@[inline]

abbrev Quotient.lift {α : Sort u} {β : Sort v} {s : Setoid α} (f : α → β) : (∀ (a b : α), a ≈ b → f a = f b) → Quotient s → β

The analogue of Quot.lift: if f : α → β respects the equivalence relation ≈, then it lifts to a function on Quotient s such that lift f h (mk a) = f a.

Equations

• Quotient.lift f = Quot.lift f

theorem Quotient.ind {α : Sort u} {s : Setoid α} {motive : Quotient s → Prop} : ((a : α) → motive (Quotient.mk s a)) → (q : Quot Setoid.r) → motive q

@[inline]

abbrev Quotient.liftOn {α : Sort u} {β : Sort v} {s : Setoid α} (q : Quotient s) (f : α → β) (c : ∀ (a b : α), a ≈ b → f a = f b) : β

The analogue of Quot.liftOn: if f : α → β respects the equivalence relation ≈, then it lifts to a function on Quotient s such that lift (mk a) f h = f a.

Equations

• Quotient.liftOn q f c = Quot.liftOn q f c

theorem Quotient.inductionOn {α : Sort u} {s : Setoid α} {motive : Quotient s → Prop} (q : Quotient s) (h : (a : α) → motive (Quotient.mk s a)) : motive q

theorem Quotient.exists_rep {α : Sort u} {s : Setoid α} (q : Quotient s) : ∃ a, Quotient.mk s a = q

@[inline]

def Quotient.rec {α : Sort u} {s : Setoid α} {motive : Quotient s → Sort v} (f : (a : α) → motive (Quotient.mk s a)) (h : ∀ (a b : α) (p : a ≈ b), (_ : Quotient.mk s a = Quotient.mk s b) ▸ f a = f b) (q : Quotient s) : motive q

The analogue of Quot.rec for Quotient. See Quot.rec.

Equations

• Quotient.rec f h q = Quot.rec f h q

@[inline]

abbrev Quotient.recOn {α : Sort u} {s : Setoid α} {motive : Quotient s → Sort v} (q : Quotient s) (f : (a : α) → motive (Quotient.mk s a)) (h : ∀ (a b : α) (p : a ≈ b), (_ : Quotient.mk s a = Quotient.mk s b) ▸ f a = f b) : motive q

The analogue of Quot.recOn for Quotient. See Quot.recOn.

Equations

• Quotient.recOn q f h = Quot.recOn q f h

@[inline]

abbrev Quotient.recOnSubsingleton {α : Sort u} {s : Setoid α} {motive : Quotient s → Sort v} [h : ∀ (a : α), Subsingleton (motive (Quotient.mk s a))] (q : Quotient s) (f : (a : α) → motive (Quotient.mk s a)) : motive q

The analogue of Quot.recOnSubsingleton for Quotient. See Quot.recOnSubsingleton.

Equations

• Quotient.recOnSubsingleton q f = Quot.recOnSubsingleton q f

@[inline]

abbrev Quotient.hrecOn {α : Sort u} {s : Setoid α} {motive : Quotient s → Sort v} (q : Quotient s) (f : (a : α) → motive (Quotient.mk s a)) (c : ∀ (a b : α), a ≈ b → HEq (f a) (f b)) : motive q

The analogue of Quot.hrecOn for Quotient. See Quot.hrecOn.

Equations

• Quotient.hrecOn q f c = Quot.hrecOn q f c

@[inline]

abbrev Quotient.lift₂ {α : Sort uA} {β : Sort uB} {φ : Sort uC} {s₁ : Setoid α} {s₂ : Setoid β} (f : α → β → φ) (c : ∀ (a₁ : α) (b₁ : β) (a₂ : α) (b₂ : β), a₁ ≈ a₂ → b₁ ≈ b₂ → f a₁ b₁ = f a₂ b₂) (q₁ : Quotient s₁) (q₂ : Quotient s₂) : φ

Lift a binary function to a quotient on both arguments.

Equations

• One or more equations did not get rendered due to their size.

@[inline]

abbrev Quotient.liftOn₂ {α : Sort uA} {β : Sort uB} {φ : Sort uC} {s₁ : Setoid α} {s₂ : Setoid β} (q₁ : Quotient s₁) (q₂ : Quotient s₂) (f : α → β → φ) (c : ∀ (a₁ : α) (b₁ : β) (a₂ : α) (b₂ : β), a₁ ≈ a₂ → b₁ ≈ b₂ → f a₁ b₁ = f a₂ b₂) : φ

Lift a binary function to a quotient on both arguments.

Equations

• Quotient.liftOn₂ q₁ q₂ f c = Quotient.lift₂ f c q₁ q₂

theorem Quotient.ind₂ {α : Sort uA} {β : Sort uB} {s₁ : Setoid α} {s₂ : Setoid β} {motive : Quotient s₁ → Quotient s₂ → Prop} (h : (a : α) → (b : β) → motive (Quotient.mk s₁ a) (Quotient.mk s₂ b)) (q₁ : Quotient s₁) (q₂ : Quotient s₂) : motive q₁ q₂

theorem Quotient.inductionOn₂ {α : Sort uA} {β : Sort uB} {s₁ : Setoid α} {s₂ : Setoid β} {motive : Quotient s₁ → Quotient s₂ → Prop} (q₁ : Quotient s₁) (q₂ : Quotient s₂) (h : (a : α) → (b : β) → motive (Quotient.mk s₁ a) (Quotient.mk s₂ b)) : motive q₁ q₂

theorem Quotient.inductionOn₃ {α : Sort uA} {β : Sort uB} {φ : Sort uC} {s₁ : Setoid α} {s₂ : Setoid β} {s₃ : Setoid φ} {motive : Quotient s₁ → Quotient s₂ → Quotient s₃ → Prop} (q₁ : Quotient s₁) (q₂ : Quotient s₂) (q₃ : Quotient s₃) (h : (a : α) → (b : β) → (c : φ) → motive (Quotient.mk s₁ a) (Quotient.mk s₂ b) (Quotient.mk s₃ c)) : motive q₁ q₂ q₃

theorem Quotient.exact {α : Sort u} {s : Setoid α} {a : α} {b : α} : Quotient.mk s a = Quotient.mk s b → a ≈ b

@[inline]

abbrev Quotient.recOnSubsingleton₂ {α : Sort uA} {β : Sort uB} {s₁ : Setoid α} {s₂ : Setoid β} {motive : Quotient s₁ → Quotient s₂ → Sort uC} [s : ∀ (a : α) (b : β), Subsingleton (motive (Quotient.mk s₁ a) (Quotient.mk s₂ b))] (q₁ : Quotient s₁) (q₂ : Quotient s₂) (g : (a : α) → (b : β) → motive (Quotient.mk s₁ a) (Quotient.mk s₂ b)) : motive q₁ q₂

Lift a binary function to a quotient on both arguments.

Equations

• Quotient.recOnSubsingleton₂ q₁ q₂ g = Quot.recOnSubsingleton q₁ fun a => Quot.recOnSubsingleton q₂ fun a_1 => g a a_1

instance instDecidableEqQuotient {α : Sort u} {s : Setoid α} [d : (a b : α) → Decidable (a ≈ b)] : DecidableEq (Quotient s)

Equations

• One or more equations did not get rendered due to their size.

Function extensionality

theorem funext {α : Sort u} {β : α → Sort v} {f : (x : α) → β x} {g : (x : α) → β x} (h : ∀ (x : α), f x = g x) : f = g

Function extensionality is the statement that if two functions take equal values every point, then the functions themselves are equal: (∀ x, f x = g x) → f = g. It is called "extensionality" because it talks about how to prove two objects are equal based on the properties of the object (compare with set extensionality, which is (∀ x, x ∈ s ↔ x ∈ t) → s = t).

This is often an axiom in dependent type theory systems, because it cannot be proved from the core logic alone. However in lean's type theory this follows from the existence of quotient types (note the Quot.sound in the proof, as well as the show line which makes use of the definitional equality Quot.lift f h (Quot.mk x) = f x).

instance instSubsingletonForAll {α : Sort u} {β : α → Sort v} [inst : ∀ (a : α), Subsingleton (β a)] : Subsingleton ((a : α) → β a)

Equations

• @instSubsingletonForAll = @instSubsingletonForAll.proof_1

Squash

def Squash (α : Type u) : Type u

Squash α is the quotient of α by the always true relation. It is empty if α is empty, otherwise it is a singleton. (Thus it is unconditionally a Subsingleton.) It is the "universal Subsingleton" mapped from α.

It is similar to Nonempty α, which has the same properties, but unlike Nonempty this is a Type u, that is, it is "data", and the compiler represents an element of Squash α the same as α itself (as compared to Nonempty α, whose elements are represented by a dummy value).

Squash.lift will extract a value in any subsingleton β from a function on α, while Nonempty.rec can only do the same when β is a proposition.

Equations

• Squash α = Quot fun x x => True

def Squash.mk {α : Type u} (x : α) : Squash α

The canonical quotient map into Squash α.

Equations

• Squash.mk x = Quot.mk (fun x x => True) x

theorem Squash.ind {α : Type u} {motive : Squash α → Prop} (h : (a : α) → motive (Squash.mk a)) (q : Squash α) : motive q

@[inline]

def Squash.lift {α : Type u_1} {β : Sort u_2} [inst : Subsingleton β] (s : Squash α) (f : α → β) : β

If β is a subsingleton, then a function α → β lifts to Squash α → β.

Equations

• Squash.lift s f = Quot.lift f (_ : ∀ (x x_1 : α), True → f x = f x_1) s

instance instSubsingletonSquash {α : Type u} : Subsingleton (Squash α)

Equations

• @instSubsingletonSquash = @instSubsingletonSquash.proof_1

Relations

class Antisymm {α : Sort u} (r : α → α → Prop) : Type

• An antisymmetric relation (·≤·) satisfies a ≤ b → b ≤ a → a = b.

  antisymm : ∀ {a b : α}, r a b → r b a → a = b

Antisymm (·≤·) says that (·≤·) is antisymmetric, that is, a ≤ b → b ≤ a → a = b.

Kernel reduction hints

opaque Lean.reduceBool (b : Bool) : Bool

When the kernel tries to reduce a term Lean.reduceBool c, it will invoke the Lean interpreter to evaluate c. The kernel will not use the interpreter if c is not a constant. This feature is useful for performing proofs by reflection.

Remark: the Lean frontend allows terms of the from Lean.reduceBool t where t is a term not containing free variables. The frontend automatically declares a fresh auxiliary constant c and replaces the term with Lean.reduceBool c. The main motivation is that the code for t will be pre-compiled.

Warning: by using this feature, the Lean compiler and interpreter become part of your trusted code base. This is extra 30k lines of code. More importantly, you will probably not be able to check your development using external type checkers (e.g., Trepplein) that do not implement this feature. Keep in mind that if you are using Lean as programming language, you are already trusting the Lean compiler and interpreter. So, you are mainly losing the capability of type checking your development using external checkers.

Recall that the compiler trusts the correctness of all [implemented_by ...] and [extern ...] annotations. If an extern function is executed, then the trusted code base will also include the implementation of the associated foreign function.

opaque Lean.reduceNat (n : Nat) : Nat

Similar to Lean.reduceBool for closed Nat terms.

Remark: we do not have plans for supporting a generic reduceValue {α} (a : α) : α := a. The main issue is that it is non-trivial to convert an arbitrary runtime object back into a Lean expression. We believe Lean.reduceBool enables most interesting applications (e.g., proof by reflection).

axiom Lean.ofReduceBool (a : Bool) (b : Bool) (h : Lean.reduceBool a = b) : a = b

The axiom ofReduceBool is used to perform proofs by reflection. See reduceBool.

This axiom is usually not used directly, because it has some syntactic restrictions. Instead, the native_decide tactic can be used to prove any proposition whose decidability instance can be evaluated to true using the lean compiler / interpreter.

Warning: by using this feature, the Lean compiler and interpreter become part of your trusted code base. This is extra 30k lines of code. More importantly, you will probably not be able to check your development using external type checkers (e.g., Trepplein) that do not implement this feature. Keep in mind that if you are using Lean as programming language, you are already trusting the Lean compiler and interpreter. So, you are mainly losing the capability of type checking your development using external checkers.

axiom Lean.ofReduceNat (a : Nat) (b : Nat) (h : Lean.reduceNat a = b) : a = b

The axiom ofReduceNat is used to perform proofs by reflection. See reduceBool.

Warning: by using this feature, the Lean compiler and interpreter become part of your trusted code base. This is extra 30k lines of code. More importantly, you will probably not be able to check your development using external type checkers (e.g., Trepplein) that do not implement this feature. Keep in mind that if you are using Lean as programming language, you are already trusting the Lean compiler and interpreter. So, you are mainly losing the capability of type checking your development using external checkers.

class Lean.IsAssociative {α : Sort u} (op : α → α → α) : Type

• An associative operation satisfies (a ∘ b) ∘ c = a ∘ (b ∘ c).

  assoc : ∀ (a b c : α), op (op a b) c = op a (op b c)

IsAssociative op says that op is an associative operation, i.e. (a ∘ b) ∘ c = a ∘ (b ∘ c). It is used by the ac_rfl tactic.

class Lean.IsCommutative {α : Sort u} (op : α → α → α) : Type

• A commutative operation satisfies a ∘ b = b ∘ a.

  comm : ∀ (a b : α), op a b = op b a

IsCommutative op says that op is a commutative operation, i.e. a ∘ b = b ∘ a. It is used by the ac_rfl tactic.

class Lean.IsIdempotent {α : Sort u} (op : α → α → α) : Type

• An idempotent operation satisfies a ∘ a = a.

  idempotent : ∀ (x : α), op x x = x

IsIdempotent op says that op is an idempotent operation, i.e. a ∘ a = a. It is used by the ac_rfl tactic (which also simplifies up to idempotence when available).

class Lean.IsNeutral {α : Sort u} (op : α → α → α) (neutral : α) : Type

• A neutral element can be cancelled on the left: e ∘ a = a.

  left_neutral : ∀ (a : α), op neutral a = a

• A neutral element can be cancelled on the right: a ∘ e = a.

  right_neutral : ∀ (a : α), op a neutral = a

IsNeutral op e says that e is a neutral operation for op, i.e. a ∘ e = a = e ∘ a. It is used by the ac_rfl tactic (which also simplifies neutral elements when available).