Opened 11 years ago

# Sage Sets don't implement genuine comparison

Reported by: Owned by: rlm AlexGhitza major sage-6.4 basic arithmetic kini Robert Miller Mike Hansen N/A todo

### Description

Right now there is either equals, or less than. If `a != b`, then we get `a < b` but not `b > a`:

```sage: a = Set([1])
sage: b = Set([])
sage: a == b
False
sage: a < b
True
sage: b > a
False
```

This came up in

### comment:1 Changed 11 years ago by nbruin

The noted behaviour is definitely a bug. However, the attached patch solves this by introducing an attempt at inducing a total ordering on Sets by sorting them first by cardinality and then by lexicographic ordering on the sorted list of set elements. This only works if the elements of the set have a total ordering implemented.

While python used to try to have a total ordering on all objects, this has been abandoned (e.g. python complex numbers and python sets)

### comment:2 follow-up: ↓ 3 Changed 11 years ago by rlm

I completely, emphatically disagree. I think that total orderings are very important to try to preserve wherever possible, especially in this case.

### comment:3 in reply to: ↑ 2 Changed 11 years ago by rlm

I completely, emphatically disagree. I think that total orderings are very important to try to preserve wherever possible, especially in this case.

### comment:4 Changed 11 years ago by rlm

• Status changed from new to needs_review

### comment:5 Changed 11 years ago by was

I don't understand why you have these lines:

```            if len_self != len_other:
return cmp(len_self, len_other)
```

that just makes it so that the comparison is incompatible with what it is for lists. Why not just make it the same?

### comment:6 Changed 11 years ago by rlm

You mean just remove those lines? That's fine with me. This was just meant to be an optimization.

### comment:7 Changed 11 years ago by rlm

Patch is updated.

### comment:8 Changed 11 years ago by was

I guess you didn't test your patch? I just applied it and ran tests on sage.math, and got:

```----------------------------------------------------------------------
The following tests failed:

sage -t  devel/sage/sage/graphs/graph_generators.py # 2 doctests failed
sage -t  devel/sage/sage/graphs/digraph.py # 2 doctests failed
sage -t  devel/sage/sage/combinat/sf/powersum.py # 0 doctests failed
sage -t  devel/sage/sage/graphs/graph.py # Time out
----------------------------------------------------------------------
Timings have been updated.
Total time for all tests: 488.9 seconds
```

### comment:9 Changed 11 years ago by was

• Status changed from needs_review to needs_work

### comment:10 Changed 9 years ago by mhansen

• Reviewers set to Mike Hansen
• Status changed from needs_work to positive_review

I rebased the patch and ran the tests which do pass. I think we can give this positive review.

### comment:11 follow-up: ↓ 12 Changed 9 years ago by dsm

• Status changed from positive_review to needs_work

I think the patch behaviour of

```sage: a = [2,3]
sage: b = [2,3,4j]
sage: set(a) < set(b)
True
sage: Set(a) < Set(b)
False

```

is too dangerous to let pass unremarked.

### comment:12 in reply to: ↑ 11 Changed 9 years ago by was

I think the patch behaviour of

```sage: a = [2,3]
sage: b = [2,3,4j]
sage: set(a) < set(b)
True
sage: Set(a) < Set(b)
False

```

is too dangerous to let pass unremarked.

In Python (according to http://docs.python.org/library/sets.html) for the set type we have: "The subset and equality comparisons do not generalize to a complete ordering function. For example, any two disjoint sets are not equal and are not subsets of each other, so all of the following return False: a<b, a==b, or a>b. Accordingly, sets do not implement the cmp() method."

The Python convention does make sense and is what most people would expect... and is the direction Sage should move in.

RLM who wrote "I completely, emphatically disagree." has got sucked up into an industry job, so isn't involved in Sage development right now, so I don't think he'll care much what happens with this ticket.

That said, having a total ordering -- which is different and inconsistent with set's order -- is useful (!). However, it can be done as a separate explicit function or method, which can get passed to the sort method explicitly.

### comment:14 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:15 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:16 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:17 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:18 Changed 6 years ago by jakobkroeker

• Stopgaps set to todo
Note: See TracTickets for help on using tickets.