Note about Mathlib/Init/

The files in Mathlib/Init are leftovers from the port from Mathlib3. (They contain content moved from lean3 itself that Mathlib needed but was not moved to lean4.)

We intend to move all the content of these files out into the main Mathlib directory structure. Contributions assisting with this are appreciated.

#align statements without corresponding declarations (i.e. because the declaration is in Batteries or Lean) can be left here. These will be deleted soon so will not significantly delay deleting otherwise empty Init files.

Unbundled algebra classes

These classes are part of an incomplete refactor described here on the github Wiki. However a subset of them are widely used in mathlib3, and it has been tricky to clean this up as this file was in core Lean 3.

By themselves, these classes are not good replacements for the Monoid / Group etc structures provided by mathlib, as they are not discoverable by simp unlike the current lemmas due to there being little to index on. The Wiki page linked above describes an algebraic normalizer, but it was never implemented in Lean 3.

Porting note:

This file is ancient, and it would be good to replace it with a clean version that provides what mathlib4 actually needs.

I've omitted all the @[algebra] attributes, as they are not used elsewhere.

The section StrictWeakOrder has been omitted, but I've left the mathport output in place. Please delete if cleaning up.

I've commented out some classes which we think are completely unused in mathlib.

I've added many of the declarations to nolints.json. If you clean up this file, please add documentation to classes that we are keeping.

Mario made the following analysis of uses in mathlib3:

• is_symm_op: unused except for some instances
• is_commutative: used a fair amount via some theorems about folds (also assuming is_associative)
• is_associative: ditto, also used in noncomm_fold
• is_left_id, is_right_id: unused except in the mathlib class is_unital and in mono (which looks like it could use is_unital)
• is_left_null, is_right_null: unused
• is_left_cancel, is_right_cancel: unused except for instances
• is_idempotent: this one is actually used to prove things not directly about is_idempotent
• is_left_distrib, is_right_distrib, is_left_inv, is_right_inv, is_cond_left_inv, is_cond_right_inv: unused
• is_distinct: unused (although we reinvented this one as nontrivial)
• is_irrefl, is_refl, is_symm, is_trans: significant usage
• is_asymm, is_antisymm, is_total, is_strict_order: a lot of uses but all in order theory and it's unclear how much could not be transferred to another typeclass
• is_preorder: unused except for instances (except antisymmetrization, maybe it could be transferred)
• is_total_preorder, is_partial_order: unused except for instances
• is_linear_order: unused except for instances
• is_equiv: unused except for instances (most uses can use equivalence instead)
• is_per: unused
• is_incomp_trans: unused
• is_strict_weak_order: significant usage (most of it on rbmap, could be transferred)
• is_trichotomous: some usage
• is_strict_total_order: looks like the only usage is in rbmap again

class IsSymmOp (α : Sort u) (β : Sort v) (op : α → α → β) : Prop

• symm_op : ∀ (a b : α), op a b = op b a

Instances

• List.instIsSymmOpZipWith
• isSymmOp_of_isCommutative
• isSymmOp_of_isSymm

theorem IsSymmOp.symm_op {α : Sort u} {β : Sort v} {op : α → α → β} [self : IsSymmOp α β op] (a : α) (b : α) : op a b = op b a

@[reducible, inline, deprecated Std.Commutative]

abbrev IsCommutative (α : Sort u) (op : α → α → α) : Prop

A commutative binary operation.

Equations

• IsCommutative α op = Std.Commutative op

@[instance 100]

instance isSymmOp_of_isCommutative (α : Sort u) (op : α → α → α) [Std.Commutative op] : IsSymmOp α α op

Equations

• ⋯ = ⋯

@[reducible, inline, deprecated Std.Associative]

abbrev IsAssociative (α : Sort u) (op : α → α → α) : Prop

An associative binary operation.

Equations

• IsAssociative α op = Std.Associative op

@[reducible, inline, deprecated Std.LawfulLeftIdentity]

abbrev IsLeftId (α : Sort u) (op : α → α → α) (o : outParam α) : Prop

A binary operation with a left identity.

Equations

• IsLeftId α op o = Std.LawfulLeftIdentity op o

@[reducible, inline, deprecated Std.LawfulRightIdentity]

abbrev IsRightId (α : Sort u) (op : α → α → α) (o : outParam α) : Prop

A binary operation with a right identity.

Equations

• IsRightId α op o = Std.LawfulRightIdentity op o

class IsLeftCancel (α : Sort u) (op : α → α → α) : Prop

• left_cancel : ∀ (a b c : α), op a b = op a c → b = c

Instances

• Equiv.instIsLeftCancelCoeForallForallArrowCongr

theorem IsLeftCancel.left_cancel {α : Sort u} {op : α → α → α} [self : IsLeftCancel α op] (a : α) (b : α) (c : α) : op a b = op a c → b = c

class IsRightCancel (α : Sort u) (op : α → α → α) : Prop

• right_cancel : ∀ (a b c : α), op a b = op c b → a = c

Instances

• Equiv.instIsRightCancelCoeForallForallArrowCongr

theorem IsRightCancel.right_cancel {α : Sort u} {op : α → α → α} [self : IsRightCancel α op] (a : α) (b : α) (c : α) : op a b = op c b → a = c

@[reducible, inline, deprecated Std.IdempotentOp]

abbrev IsIdempotent (α : Sort u) (op : α → α → α) : Prop

Equations

• IsIdempotent α op = Std.IdempotentOp op

class IsIrrefl (α : Sort u) (r : α → α → Prop) : Prop

IsIrrefl X r means the binary relation r on X is irreflexive (that is, r x x never holds).

• irrefl : ∀ (a : α), ¬r a a

Instances

• CovBy.isIrrefl
• Finset.instIsIrreflSSubset
• IsRefl.compl
• Prod.isIrrefl
• Set.instIsIrreflSSubset
• Subrel.instIsIrreflElem
• WellFounded.instIsIrreflRel
• instIsIrreflEmptyRelation
• instIsIrreflGt
• instIsIrreflLt
• instIsIrreflOfIsNonstrictStrictOrder
• instIsIrreflOfIsWellFounded
• instIsIrreflOfIsWellOrder

theorem IsIrrefl.irrefl {α : Sort u} {r : α → α → Prop} [self : IsIrrefl α r] (a : α) : ¬r a a

class IsRefl (α : Sort u) (r : α → α → Prop) : Prop

IsRefl X r means the binary relation r on X is reflexive.

• refl : ∀ (a : α), r a a

Instances

• AddCommute.instIsRefl
• AddCommute.on_isRefl
• Associated.instIsRefl
• Commute.instIsRefl
• Commute.on_isRefl
• Finset.instIsReflSubset
• IsIrrefl.compl
• IsTotal.to_isRefl
• List.SublistForall₂.is_refl
• Nat.ModEq.instIsRefl
• Order.Preimage.instIsRefl
• Prod.instIsReflLex
• Prod.instIsReflLex_1
• Relation.ReflGen.instIsRefl
• Relation.instIsReflReflTransGen
• Set.instIsReflSubset
• Subrel.instIsReflElem
• WCovBy.isRefl
• instIsReflDvd
• instIsReflGe
• instIsReflLe
• instIsReflPropIff

theorem IsRefl.refl {α : Sort u} {r : α → α → Prop} [self : IsRefl α r] (a : α) : r a a

class IsSymm (α : Sort u) (r : α → α → Prop) : Prop

IsSymm X r means the binary relation r on X is symmetric.

• symm : ∀ (a b : α), r a b → r b a

Instances

• Associated.instIsSymm
• Subrel.instIsSymmElem

theorem IsSymm.symm {α : Sort u} {r : α → α → Prop} [self : IsSymm α r] (a : α) (b : α) : r a b → r b a

@[instance 100]

instance isSymmOp_of_isSymm (α : Sort u) (r : α → α → Prop) [IsSymm α r] : IsSymmOp α Prop r

The opposite of a symmetric relation is symmetric.

Equations

• ⋯ = ⋯

class IsAsymm (α : Sort u) (r : α → α → Prop) : Prop

IsAsymm X r means that the binary relation r on X is asymmetric, that is, r a b → ¬ r b a.

• asymm : ∀ (a b : α), r a b → ¬r b a

Instances

• Finset.instIsAsymmSSubset
• List.Lex.isAsymm
• Set.instIsAsymmSSubset
• WellFounded.instIsAsymmRel
• instIsAsymmGt
• instIsAsymmLt
• instIsAsymmOfIsWellFounded
• instIsAsymmOfIsWellOrder
• isAsymm_of_isTrans_of_isIrrefl

theorem IsAsymm.asymm {α : Sort u} {r : α → α → Prop} [self : IsAsymm α r] (a : α) (b : α) : r a b → ¬r b a

class IsAntisymm (α : Sort u) (r : α → α → Prop) : Prop

IsAntisymm X r means the binary relation r on X is antisymmetric.

• antisymm : ∀ (a b : α), r a b → r b a → a = b

Instances

• Encodable.instIsAntisymmPreimageNatCoeEmbeddingEncode'Le
• Finset.instIsAntisymmSubset
• IsAsymm.toIsAntisymm
• Prod.instIsAntisymmLexOfIsStrictOrder
• Set.instIsAntisymmSubset
• instIsAntisymmGe
• instIsAntisymmGt
• instIsAntisymmLe
• instIsAntisymmLt

theorem IsAntisymm.antisymm {α : Sort u} {r : α → α → Prop} [self : IsAntisymm α r] (a : α) (b : α) : r a b → r b a → a = b

@[instance 100]

instance IsAsymm.toIsAntisymm {α : Sort u} (r : α → α → Prop) [IsAsymm α r] : IsAntisymm α r

Equations

• ⋯ = ⋯

class IsTrans (α : Sort u) (r : α → α → Prop) : Prop

IsTrans X r means the binary relation r on X is transitive.

• trans : ∀ (a b c : α), r a b → r b c → r a c

Instances

• Associated.instIsTrans
• Finset.instIsTransSSubset
• Finset.instIsTransSubset
• List.SublistForall₂.is_trans
• List.instIsTransSubset
• Order.Preimage.instIsTrans
• Prod.instIsTransLex
• Relation.instIsTransReflTransGen
• Relation.instIsTransTransGen
• Set.instIsTransSSubset
• Set.instIsTransSubset
• Subrel.instIsTransElem
• instIsTransDvd
• instIsTransGe
• instIsTransGt
• instIsTransLe
• instIsTransLt
• instIsTransOfIsWellOrder
• instIsTransOfTrans
• instIsTransPropIff

theorem IsTrans.trans {α : Sort u} {r : α → α → Prop} [self : IsTrans α r] (a : α) (b : α) (c : α) : r a b → r b c → r a c

instance instTransOfIsTrans {α : Sort u} {r : α → α → Prop} [IsTrans α r] : Trans r r r

Equations

• instTransOfIsTrans = { trans := ⋯ }

@[instance 100]

instance instIsTransOfTrans {α : Sort u} {r : α → α → Prop} [Trans r r r] : IsTrans α r

Equations

• ⋯ = ⋯

class IsTotal (α : Sort u) (r : α → α → Prop) : Prop

IsTotal X r means that the binary relation r on X is total, that is, that for any x y : X we have r x y or r y x.

• total : ∀ (a b : α), r a b ∨ r b a

Instances

• Encodable.instIsTotalPreimageNatCoeEmbeddingEncode'Le
• LE.isTotal
• LowerSet.isTotal_le
• OrderDual.isTotal_le
• Prod.isTotal_left
• Prod.isTotal_right
• Prop.le_isTotal
• UpperSet.isTotal_le
• WithBot.isTotal_le
• WithTop.isTotal_le
• instIsTotalGe

theorem IsTotal.total {α : Sort u} {r : α → α → Prop} [self : IsTotal α r] (a : α) (b : α) : r a b ∨ r b a

class IsPreorder (α : Sort u) (r : α → α → Prop) extends IsRefl , IsTrans : Prop

IsPreorder X r means that the binary relation r on X is a pre-order, that is, reflexive and transitive.

Instances

• instIsPreorderGe
• instIsPreorderLe
• isTotalPreorder_isPreorder

class IsTotalPreorder (α : Sort u) (r : α → α → Prop) extends IsTrans , IsTotal : Prop

IsTotalPreorder X r means that the binary relation r on X is total and a preorder.

Instances

• instIsTotalPreorderGe
• instIsTotalPreorderLe
• instIsTotalPreorderLe_1

@[instance 100]

instance isTotalPreorder_isPreorder (α : Sort u) (r : α → α → Prop) [s : IsTotalPreorder α r] : IsPreorder α r

Every total pre-order is a pre-order.

Equations

• ⋯ = ⋯

class IsPartialOrder (α : Sort u) (r : α → α → Prop) extends IsPreorder , IsAntisymm : Prop

IsPartialOrder X r means that the binary relation r on X is a partial order, that is, IsPreorder X r and IsAntisymm X r.

Instances

• List.instIsPartialOrderIsInfix
• List.instIsPartialOrderIsPrefix
• List.instIsPartialOrderIsSuffix
• instIsPartialOrderGe
• instIsPartialOrderLe

class IsLinearOrder (α : Sort u) (r : α → α → Prop) extends IsPartialOrder , IsTotal : Prop

IsLinearOrder X r means that the binary relation r on X is a linear order, that is, IsPartialOrder X r and IsTotal X r.

Instances

• instIsLinearOrderGe
• instIsLinearOrderLe

class IsEquiv (α : Sort u) (r : α → α → Prop) extends IsPreorder , IsSymm : Prop

IsEquiv X r means that the binary relation r on X is an equivalence relation, that is, IsPreorder X r and IsSymm X r.

Instances

• Quotient.instIsEquivEquiv
• StrictWeakOrder.isEquiv
• eq_isEquiv

class IsStrictOrder (α : Sort u) (r : α → α → Prop) extends IsIrrefl , IsTrans : Prop

IsStrictOrder X r means that the binary relation r on X is a strict order, that is, IsIrrefl X r and IsTrans X r.

Instances

• Pi.Lex.isStrictOrder
• instIsStrictOrderGt
• instIsStrictOrderLt

class IsIncompTrans (α : Sort u) (lt : α → α → Prop) : Prop

IsIncompTrans X lt means that for lt a binary relation on X, the incomparable relation fun a b => ¬ lt a b ∧ ¬ lt b a is transitive.

• incomp_trans : ∀ (a b c : α), ¬lt a b ∧ ¬lt b a → ¬lt b c ∧ ¬lt c b → ¬lt a c ∧ ¬lt c a

Instances

• instIsIncompTransLt

theorem IsIncompTrans.incomp_trans {α : Sort u} {lt : α → α → Prop} [self : IsIncompTrans α lt] (a : α) (b : α) (c : α) : ¬lt a b ∧ ¬lt b a → ¬lt b c ∧ ¬lt c b → ¬lt a c ∧ ¬lt c a

class IsStrictWeakOrder (α : Sort u) (lt : α → α → Prop) extends IsStrictOrder , IsIncompTrans : Prop

IsStrictWeakOrder X lt means that the binary relation lt on X is a strict weak order, that is, IsStrictOrder X lt and IsIncompTrans X lt.

Instances

• instIsStrictWeakOrderLt
• isStrictTotalOrder_of_isStrictTotalOrder
• isStrictWeakOrder_of_linearOrder

class IsTrichotomous (α : Sort u) (lt : α → α → Prop) : Prop

IsTrichotomous X lt means that the binary relation lt on X is trichotomous, that is, either lt a b or a = b or lt b a for any a and b.

• trichotomous : ∀ (a b : α), lt a b ∨ a = b ∨ lt b a

Instances

• List.Lex.isTrichotomous
• Prod.IsTrichotomous
• WithBot.trichotomous.gt
• WithBot.trichotomous.lt
• WithTop.trichotomous.gt
• WithTop.trichotomous.lt
• instIsTrichotomousGe
• instIsTrichotomousGt
• instIsTrichotomousLe
• instIsTrichotomousLt
• instIsTrichotomousOfIsWellOrder

theorem IsTrichotomous.trichotomous {α : Sort u} {lt : α → α → Prop} [self : IsTrichotomous α lt] (a : α) (b : α) : lt a b ∨ a = b ∨ lt b a

class IsStrictTotalOrder (α : Sort u) (lt : α → α → Prop) extends IsTrichotomous , IsStrictOrder : Prop

IsStrictTotalOrder X lt means that the binary relation lt on X is a strict total order, that is, IsTrichotomous X lt and IsStrictOrder X lt.

Instances

• List.Lex.isStrictTotalOrder
• instIsStrictTotalOrderLt
• instIsStrictTotalOrderOfIsWellOrder
• isStrictTotalOrder_of_linearOrder

instance eq_isEquiv (α : Sort u) : IsEquiv α fun (x x_1 : α) => x = x_1

Equality is an equivalence relation.

Equations

• ⋯ = ⋯

theorem irrefl {α : Sort u} {r : α → α → Prop} [IsIrrefl α r] (a : α) : ¬r a a

theorem refl {α : Sort u} {r : α → α → Prop} [IsRefl α r] (a : α) : r a a

theorem trans {α : Sort u} {r : α → α → Prop} [IsTrans α r] {a : α} {b : α} {c : α} : r a b → r b c → r a c

theorem symm {α : Sort u} {r : α → α → Prop} [IsSymm α r] {a : α} {b : α} : r a b → r b a

theorem antisymm {α : Sort u} {r : α → α → Prop} [IsAntisymm α r] {a : α} {b : α} : r a b → r b a → a = b

theorem asymm {α : Sort u} {r : α → α → Prop} [IsAsymm α r] {a : α} {b : α} : r a b → ¬r b a

theorem trichotomous {α : Sort u} {r : α → α → Prop} [IsTrichotomous α r] (a : α) (b : α) : r a b ∨ a = b ∨ r b a

theorem incomp_trans {α : Sort u} {r : α → α → Prop} [IsIncompTrans α r] {a : α} {b : α} {c : α} : ¬r a b ∧ ¬r b a → ¬r b c ∧ ¬r c b → ¬r a c ∧ ¬r c a

@[instance 90]

instance isAsymm_of_isTrans_of_isIrrefl {α : Sort u} {r : α → α → Prop} [IsTrans α r] [IsIrrefl α r] : IsAsymm α r

Equations

• ⋯ = ⋯

@[elab_without_expected_type]

theorem irrefl_of {α : Sort u} (r : α → α → Prop) [IsIrrefl α r] (a : α) : ¬r a a

@[elab_without_expected_type]

theorem refl_of {α : Sort u} (r : α → α → Prop) [IsRefl α r] (a : α) : r a a

@[elab_without_expected_type]

theorem trans_of {α : Sort u} (r : α → α → Prop) [IsTrans α r] {a : α} {b : α} {c : α} : r a b → r b c → r a c

@[elab_without_expected_type]

theorem symm_of {α : Sort u} (r : α → α → Prop) [IsSymm α r] {a : α} {b : α} : r a b → r b a

@[elab_without_expected_type]

theorem asymm_of {α : Sort u} (r : α → α → Prop) [IsAsymm α r] {a : α} {b : α} : r a b → ¬r b a

@[elab_without_expected_type]

theorem total_of {α : Sort u} (r : α → α → Prop) [IsTotal α r] (a : α) (b : α) : r a b ∨ r b a

@[elab_without_expected_type]

theorem trichotomous_of {α : Sort u} (r : α → α → Prop) [IsTrichotomous α r] (a : α) (b : α) : r a b ∨ a = b ∨ r b a

@[elab_without_expected_type]

theorem incomp_trans_of {α : Sort u} (r : α → α → Prop) [IsIncompTrans α r] {a : α} {b : α} {c : α} : ¬r a b ∧ ¬r b a → ¬r b c ∧ ¬r c b → ¬r a c ∧ ¬r c a

def StrictWeakOrder.Equiv {α : Sort u} {r : α → α → Prop} (a : α) (b : α) : Prop

Equations

• StrictWeakOrder.Equiv a b = (¬r a b ∧ ¬r b a)

Instances For

• StrictWeakOrder.isEquiv

theorem StrictWeakOrder.erefl {α : Sort u} {r : α → α → Prop} [IsStrictWeakOrder α r] (a : α) : StrictWeakOrder.Equiv a a

theorem StrictWeakOrder.esymm {α : Sort u} {r : α → α → Prop} {a : α} {b : α} : StrictWeakOrder.Equiv a b → StrictWeakOrder.Equiv b a

theorem StrictWeakOrder.etrans {α : Sort u} {r : α → α → Prop} [IsStrictWeakOrder α r] {a : α} {b : α} {c : α} : StrictWeakOrder.Equiv a b → StrictWeakOrder.Equiv b c → StrictWeakOrder.Equiv a c

theorem StrictWeakOrder.not_lt_of_equiv {α : Sort u} {r : α → α → Prop} {a : α} {b : α} : StrictWeakOrder.Equiv a b → ¬r a b

theorem StrictWeakOrder.not_lt_of_equiv' {α : Sort u} {r : α → α → Prop} {a : α} {b : α} : StrictWeakOrder.Equiv a b → ¬r b a

instance StrictWeakOrder.isEquiv {α : Sort u} {r : α → α → Prop} [IsStrictWeakOrder α r] : IsEquiv α StrictWeakOrder.Equiv

Equations

• ⋯ = ⋯

def StrictWeakOrder.«term_≈[_]_» : Lean.TrailingParserDescr

The equivalence relation induced by lt

Equations

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

theorem isStrictWeakOrder_of_isTotalPreorder {α : Sort u} {le : α → α → Prop} {lt : α → α → Prop} [DecidableRel le] [IsTotalPreorder α le] (h : ∀ (a b : α), lt a b ↔ ¬le b a) : IsStrictWeakOrder α lt

theorem lt_of_lt_of_incomp {α : Sort u} {lt : α → α → Prop} [IsStrictWeakOrder α lt] [DecidableRel lt] {a : α} {b : α} {c : α} : lt a b → ¬lt b c ∧ ¬lt c b → lt a c

theorem lt_of_incomp_of_lt {α : Sort u} {lt : α → α → Prop} [IsStrictWeakOrder α lt] [DecidableRel lt] {a : α} {b : α} {c : α} : ¬lt a b ∧ ¬lt b a → lt b c → lt a c

theorem eq_of_incomp {α : Sort u} {lt : α → α → Prop} [IsTrichotomous α lt] {a : α} {b : α} : ¬lt a b ∧ ¬lt b a → a = b

theorem eq_of_eqv_lt {α : Sort u} {lt : α → α → Prop} [IsTrichotomous α lt] {a : α} {b : α} : StrictWeakOrder.Equiv a b → a = b

theorem incomp_iff_eq {α : Sort u} {lt : α → α → Prop} [IsTrichotomous α lt] [IsIrrefl α lt] (a : α) (b : α) : ¬lt a b ∧ ¬lt b a ↔ a = b

theorem eqv_lt_iff_eq {α : Sort u} {lt : α → α → Prop} [IsTrichotomous α lt] [IsIrrefl α lt] (a : α) (b : α) : StrictWeakOrder.Equiv a b ↔ a = b

theorem not_lt_of_lt {α : Sort u} {lt : α → α → Prop} [IsStrictOrder α lt] {a : α} {b : α} : lt a b → ¬lt b a