# Ticket #9677(needs_work defect)

Opened 3 years ago

## Sage Sets don't implement genuine comparison

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

### 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

## Change History

### comment:1 Changed 3 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 3 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 3 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 3 years ago by rlm

• Status changed from new to needs_review

### comment:5 Changed 3 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 3 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 3 years ago by rlm

Patch is updated.

### comment:8 Changed 3 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 3 years ago by was

• Status changed from needs_review to needs_work

### comment:10 Changed 17 months ago by mhansen

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

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 17 months 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 15 months 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.