Zulip Chat Archive
Stream: mathlib4
Topic: Conditional LinearOrder
Moritz R (Feb 23 2026 at 14:11):
Im currently proving some stuff about the DershowitzManna ordering extension
which extends an ordering on a to an ordering on Multiset a.
This extension has lots of nice properties in the sense that it transfers many properties from the order on a to the extension.
E.g. from Preorder a one getsPartialorder (Multiset a)
and from LinearOrder a one gets LinearOrder (Multiset a).
I'm wondering if im doing the conditional LinearOrder def correctly - the LinearOrder should agree with the partialOrder if it exists.
def Multiset.IsDershowitzMannaLT.instPartialOrder [Preorder α] : PartialOrder (Multiset α) :=
@partialOrderOfSO _ Multiset.IsDershowitzMannaLT Multiset.IsDershowitzMannaLT.IsStrictOrder
def Multiset.IsDershowitzMannaLT.instLinearOrder [LinearOrder α] : LinearOrder (Multiset α) where
toPartialOrder := @Multiset.IsDershowitzMannaLT.instPartialOrder α _
toDecidableLE := (@linearOrderOfSTO (Multiset α) Multiset.IsDershowitzMannaLT
Multiset.IsDershowitzMannaLT.IsStrictTotalOrder _).toDecidableLE
le_total := (@linearOrderOfSTO _ Multiset.IsDershowitzMannaLT
Multiset.IsDershowitzMannaLT.IsStrictTotalOrder _).le_total
min := (@linearOrderOfSTO _ Multiset.IsDershowitzMannaLT
Multiset.IsDershowitzMannaLT.IsStrictTotalOrder _).min
max := (@linearOrderOfSTO _ Multiset.IsDershowitzMannaLT
Multiset.IsDershowitzMannaLT.IsStrictTotalOrder _).max
Moritz R (Feb 23 2026 at 14:14):
And one additional question:
I later need to pull back both of these defs via an injective function.
Can i just do the following (or will this get me any diamonds?)
/-- Literals are compared, by comparing `L1.toMultiset` and `L2.toMultiset` using
the multiset extension. -/
instance (priority := high) Literal.instPartialOrder [PartialOrder (Term F α)] :
PartialOrder (Literal F α) :=
@PartialOrder.lift _ _
Multiset.IsDershowitzMannaLT.instPartialOrder
Literal.toMultiset
Literal.toMultiset_injective
/-- Literals are compared, by comparing `L1.toMultiset` and `L2.toMultiset` using
the multiset extension. -/
instance (priority := high) Literal.instLinearOrder [LinearOrder (Term F α)] :
LinearOrder (Literal F α) :=
@LinearOrder.lift' _ _
Multiset.IsDershowitzMannaLT.instLinearOrder
Literal.toMultiset
Literal.toMultiset_injective
Moritz R (Feb 23 2026 at 14:15):
This should be fine, since both lifts are abbrevs and the orders are in both cases defined using the same condition right?
Eric Wieser (Feb 23 2026 at 21:23):
You should tag your multiset defs with instance_reducible
Moritz R (Feb 26 2026 at 20:22):
Can you exlain what that is needed for?
Moritz R (Feb 26 2026 at 20:23):
Should i always do this with defs that have a class type as the result?
Eric Wieser (Feb 26 2026 at 20:24):
This is needed so that lean can tell the two instances are the same without having to turn on more aggressive unfolding
Last updated: Feb 28 2026 at 14:05 UTC