ordNub

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
67 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

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
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Atze van der Ploeg
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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Tom Ellis
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
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Roman Cheplyaka-2
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]
> <mailto:[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
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Atze van der Ploeg
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
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Atze van der Ploeg
> (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 emtpy

As 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 <[hidden email]>:

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
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Roman Cheplyaka-2
The set of all values of the type is always enumerable (it's even
recursive, since otherwise you wouldn't be able to tell if something is
a value or not).

Since it's enumerable, you can enumerate all values of that type:

  v1, v2, v3, ...

Take x1 < x2 iff x1 precedes x2 in the above sequence. This is obviously
computable.

Roman

On 01/01/15 17:31, Atze van der Ploeg wrote:

>> (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 emtpy
>
> As 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 <[hidden email]
> <mailto:[hidden email]>>:
>
>     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]
>     <mailto:[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] <mailto:[hidden email]>
>         http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>
>
> _______________________________________________
> 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
1234