Canonically ordered monoids #
An OrderedCommMonoid
with one-sided 'division' in the sense that
if a ≤ b
, there is some c
for which a * c = b
. This is a weaker version
of the condition on canonical orderings defined by CanonicallyOrderedCommMonoid
.
For
a ≤ b
,a
left dividesb
Instances
An OrderedAddCommMonoid
with one-sided 'subtraction' in the sense that
if a ≤ b
, then there is some c
for which a + c = b
. This is a weaker version
of the condition on canonical orderings defined by CanonicallyOrderedAddCommMonoid
.
For
a ≤ b
, there is ac
sob = a + c
.
Instances
Equations
- (_ : ExistsAddOfLE α) = (_ : ExistsAddOfLE α)
Equations
- (_ : ExistsMulOfLE α) = (_ : ExistsMulOfLE α)
A canonically ordered additive monoid is an ordered commutative additive monoid
in which the ordering coincides with the subtractibility relation,
which is to say, a ≤ b
iff there exists c
with b = a + c
.
This is satisfied by the natural numbers, for example, but not
the integers or other nontrivial OrderedAddCommGroup
s.
- add : α → α → α
- zero : α
- nsmul : ℕ → α → α
- nsmul_zero : ∀ (x : α), AddMonoid.nsmul 0 x = 0
- nsmul_succ : ∀ (n : ℕ) (x : α), AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
- le : α → α → Prop
- lt : α → α → Prop
- le_refl : ∀ (a : α), a ≤ a
- bot : α
For
a ≤ b
, there is ac
sob = a + c
.For any
a
andb
,a ≤ a + b
Instances
A canonically ordered monoid is an ordered commutative monoid
in which the ordering coincides with the divisibility relation,
which is to say, a ≤ b
iff there exists c
with b = a * c
.
Examples seem rare; it seems more likely that the OrderDual
of a naturally-occurring lattice satisfies this than the lattice
itself (for example, dual of the lattice of ideals of a PID or
Dedekind domain satisfy this; collections of all things ≤ 1 seem to
be more natural that collections of all things ≥ 1).
- mul : α → α → α
- one : α
- npow : ℕ → α → α
- npow_zero : ∀ (x : α), Monoid.npow 0 x = 1
- npow_succ : ∀ (n : ℕ) (x : α), Monoid.npow (n + 1) x = x * Monoid.npow n x
- le : α → α → Prop
- lt : α → α → Prop
- le_refl : ∀ (a : α), a ≤ a
- bot : α
For
a ≤ b
, there is ac
sob = a * c
.For any
a
andb
,a ≤ a * b
Instances
Equations
- (_ : ExistsAddOfLE α) = (_ : ExistsAddOfLE α)
Equations
- (_ : ExistsMulOfLE α) = (_ : ExistsMulOfLE α)
A canonically linear-ordered additive monoid is a canonically ordered additive monoid whose ordering is a linear order.
- add : α → α → α
- zero : α
- nsmul : ℕ → α → α
- nsmul_zero : ∀ (x : α), AddMonoid.nsmul 0 x = 0
- nsmul_succ : ∀ (n : ℕ) (x : α), AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
- le : α → α → Prop
- lt : α → α → Prop
- le_refl : ∀ (a : α), a ≤ a
- bot : α
- min : α → α → α
- max : α → α → α
- compare : α → α → Ordering
A linear order is total.
- decidableLE : DecidableRel fun (x x_1 : α) => x ≤ x_1
In a linearly ordered type, we assume the order relations are all decidable.
- decidableEq : DecidableEq α
In a linearly ordered type, we assume the order relations are all decidable.
- decidableLT : DecidableRel fun (x x_1 : α) => x < x_1
In a linearly ordered type, we assume the order relations are all decidable.
The minimum function is equivalent to the one you get from
minOfLe
.The minimum function is equivalent to the one you get from
maxOfLe
.- compare_eq_compareOfLessAndEq : ∀ (a b : α), compare a b = compareOfLessAndEq a b
Comparison via
compare
is equal to the canonical comparison given decidable<
and=
.
Instances
A canonically linear-ordered monoid is a canonically ordered monoid whose ordering is a linear order.
- mul : α → α → α
- one : α
- npow : ℕ → α → α
- npow_zero : ∀ (x : α), Monoid.npow 0 x = 1
- npow_succ : ∀ (n : ℕ) (x : α), Monoid.npow (n + 1) x = x * Monoid.npow n x
- le : α → α → Prop
- lt : α → α → Prop
- le_refl : ∀ (a : α), a ≤ a
- bot : α
- min : α → α → α
- max : α → α → α
- compare : α → α → Ordering
A linear order is total.
- decidableLE : DecidableRel fun (x x_1 : α) => x ≤ x_1
In a linearly ordered type, we assume the order relations are all decidable.
- decidableEq : DecidableEq α
In a linearly ordered type, we assume the order relations are all decidable.
- decidableLT : DecidableRel fun (x x_1 : α) => x < x_1
In a linearly ordered type, we assume the order relations are all decidable.
The minimum function is equivalent to the one you get from
minOfLe
.The minimum function is equivalent to the one you get from
maxOfLe
.- compare_eq_compareOfLessAndEq : ∀ (a b : α), compare a b = compareOfLessAndEq a b
Comparison via
compare
is equal to the canonical comparison given decidable<
and=
.
Instances
Equations
- One or more equations did not get rendered due to their size.
Equations
- One or more equations did not get rendered due to their size.
In a linearly ordered monoid, we are happy for bot_eq_zero
to be a @[simp]
lemma
In a linearly ordered monoid, we are happy for bot_eq_one
to be a @[simp]
lemma.