# ordNub

67 messages
1234
Open this post in threaded view
|

## Re: ordNub

 On Thu, Jan 01, 2015 at 03:37:09PM +0100, Atze van der Ploeg wrote: > This boils down to the question whether on each set with an equality > relation defined on it a total ordering (consistent with the equality > relation) can also be defined. I agree with the essence of this restatement. > One counterexample is the complex numbers. This is what I don't understand.  The complex numbers can be totally ordered.  (Not in a way compatible with the field structure, but that's beside the point). _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: ordNub

 If we do not require that (a <= b) && (a >= b) ==> a == b (where <= is from the total ordering and == is from the equality relation) then it is trivial, takethe total ordering forall x y. x <= y that i mentioned earlier. So the compatiblity with equality (you say field structure) is not besides the point, in factantisymmetry means that the ordering corresponds to the equality relation.Clear now or did I misunderstand?Cheers2015-01-01 15:39 GMT+01:00 Tom Ellis :On Thu, Jan 01, 2015 at 03:37:09PM +0100, Atze van der Ploeg wrote: > This boils down to the question whether on each set with an equality > relation defined on it a total ordering (consistent with the equality > relation) can also be defined. I agree with the essence of this restatement. > One counterexample is the complex numbers. This is what I don't understand.  The complex numbers can be totally ordered.  (Not in a way compatible with the field structure, but that's beside the point). _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: ordNub

 On Thu, Jan 01, 2015 at 03:52:26PM +0100, Atze van der Ploeg wrote: > If we do not require that (a <= b) && (a >= b) ==> a == b (where <= is > from the total ordering and == is from the equality relation) then it is > trivial, take the total ordering forall x y.  x <= y that i mentioned > earlier. > > So the compatiblity with equality (you say field structure) is not besides > the point, in fact antisymmetry means that the ordering corresponds to the > equality relation. > > Clear now or did I misunderstand? Here is my proposed equality and ordering on the complex numbers:     data Complex = Complex (Double, Double) deriving (Eq, Ord) Does this violate any of my requested conditions? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: ordNub

 In reply to this post by Atze van der Ploeg You misunderstood. Complex numbers can be ordered in a way that is compatible with the equality — the lexicographic ordering. (That said, I don't understand why this discussion is relevant at all. The fact that the ordering exists doesn't mean that one would want to declare the Ord instance, like with complex numbers.) On 01/01/15 16:52, Atze van der Ploeg wrote: > If we do not require that (a <= b) && (a >= b) ==> a == b (where <= is > from the total ordering and == is from the equality relation) then it is > trivial, take > the total ordering forall x y. x <= y that i mentioned earlier. > > So the compatiblity with equality (you say field structure) is not > besides the point, in fact > antisymmetry means that the ordering corresponds to the equality relation. > > Clear now or did I misunderstand? > > Cheers > > 2015-01-01 15:39 GMT+01:00 Tom Ellis > <[hidden email] > >: > >     On Thu, Jan 01, 2015 at 03:37:09PM +0100, Atze van der Ploeg wrote: >     > This boils down to the question whether on each set with an equality >     > relation defined on it a total ordering (consistent with the equality >     > relation) can also be defined. > >     I agree with the essence of this restatement. > >     > One counterexample is the complex numbers. > >     This is what I don't understand.  The complex numbers can be totally >     ordered.  (Not in a way compatible with the field structure, but that's >     beside the point). _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: ordNub

 In reply to this post by Tom Ellis Nope you're right. Indeed uncompatible with the field structure. Now I'm confused :) I now understand your question, but do not immediately know the answer. Anyone? On Jan 1, 2015 4:02 PM, "Tom Ellis" <[hidden email]> wrote:On Thu, Jan 01, 2015 at 03:52:26PM +0100, Atze van der Ploeg wrote: > If we do not require that (a <= b) && (a >= b) ==> a == b (where <= is > from the total ordering and == is from the equality relation) then it is > trivial, take the total ordering forall x y.  x <= y that i mentioned > earlier. > > So the compatiblity with equality (you say field structure) is not besides > the point, in fact antisymmetry means that the ordering corresponds to the > equality relation. > > Clear now or did I misunderstand? Here is my proposed equality and ordering on the complex numbers:     data Complex = Complex (Double, Double) deriving (Eq, Ord) Does this violate any of my requested conditions? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: ordNub

 > (That said, I don't understand why this discussion is relevant at all.> The fact that the ordering exists doesn't mean that one would want to> declare the Ord instance, like with complex numbers.)It's not relevant, it's just an intellectual exercise.For any set with a equality relation there exists a total order relation on that set consistent with the equality relation. The question is then whether there exists a set with a computable equality relation such that there is no computable total order.I think the following computable function shows that it is always possible (it chooses an order during queries):Maintain a table, initially emtpyAs soon as (a <= b) is requested, see if a and b are already in the table (using the computatble equality function) , if so, use their ordering in the table.If an element is not in the table, add it. Hence the table gives a consistent total order (it depends on which ordering queries are requested, but that is not relevant?)2015-01-01 16:06 GMT+01:00 Atze van der Ploeg :Nope you're right. Indeed uncompatible with the field structure. Now I'm confused :) I now understand your question, but do not immediately know the answer. Anyone? On Jan 1, 2015 4:02 PM, "Tom Ellis" <[hidden email]> wrote:On Thu, Jan 01, 2015 at 03:52:26PM +0100, Atze van der Ploeg wrote: > If we do not require that (a <= b) && (a >= b) ==> a == b (where <= is > from the total ordering and == is from the equality relation) then it is > trivial, take the total ordering forall x y.  x <= y that i mentioned > earlier. > > So the compatiblity with equality (you say field structure) is not besides > the point, in fact antisymmetry means that the ordering corresponds to the > equality relation. > > Clear now or did I misunderstand? Here is my proposed equality and ordering on the complex numbers:     data Complex = Complex (Double, Double) deriving (Eq, Ord) Does this violate any of my requested conditions? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe