Opened 8 years ago

Closed 7 years ago

## #16676 closed defect (fixed)

# Cardinality of infinite sets loops forever

Reported by: | Luca De Feo | Owned by: | |
---|---|---|---|

Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |

Component: | combinatorics | Keywords: | sets infinite_loop |

Cc: | Merged in: | ||

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description

This was reported in Ask question http://ask.sagemath.org/question/23467.

Most operations on Sets have their `cardinality()`

method defined by

return len(list(self))

This obviously fails on infinite sets which Sage does not know of:

sage: Set(ZZ).difference(Set()).cardinality()

### Change History (12)

### comment:1 Changed 8 years ago by

### comment:2 follow-up: 3 Changed 8 years ago by

Looping forever is always a bug in my opinion. The class `Set_object_difference`

knows in advance that the loop is not going to stop when the first set is infinite, thus it could avoid the computation. This only solves the first layer of the problem, though.

Obviously the problem is undecidable. A properly designed system should only start the enumeration when it **knows** the set is finite. This is best implemented with three-way logic, a topic that resurfaces often in discussion threads.

The semi-decidable algorithm could still be run by a call to `is_finite(try_hard=True)`

, then `Set_object_difference`

could be smart and run it only when `self.__X.is_finite(try_hard=True)`

returns true.

However this would require a thorough redesign of the `Set`

API, which I do not have time to start right now. I was merely reporting the bug for reference.

By the way, the fix you suggest would clash on the following bug of `is_finite()`

:

sage: Set(ZZ).difference(Set()).is_finite() ... RuntimeError: maximum recursion depth exceeded while calling a Python object

This is a different problem and an easy fix, though, as long as we agree that `False`

means "I don't know".

### comment:3 follow-up: 4 Changed 8 years ago by

This is a different problem and an easy fix, though, as long as we agree that

`False`

means "I don't know".

I do not agree.

### comment:4 follow-up: 5 Changed 8 years ago by

Replying to vdelecroix:

This is a different problem and an easy fix, though, as long as we agree that

`False`

means "I don't know".I do not agree.

Me neither. So I guess someone must step up and add three-way logic to the Set API. A grep for `Unknown`

in Sage src shows three-way logic is used almost nowhere inside Sage, and certainly not in sets.

### comment:5 Changed 8 years ago by

`False`

means "I don't know".I do not agree.

Me neither. So I guess someone must step up and add three-way logic to the Set API. A grep for

`Unknown`

in Sage src shows three-way logic is used almost nowhere inside Sage, and certainly not in sets.

Sage (for now) says `True`

only if we know for sure it is true, otherwise `False`

. One would have to have a discussion on sage-devel otherwise - and of course that is a long thing to implement. The problem is, among others, that lots of symbolic expressions might or might not be zero, and the question is how much computation to invest in trying to discern this...

### comment:6 Changed 8 years ago by

Milestone: | sage-6.3 → sage-6.4 |
---|

### comment:7 Changed 7 years ago by

Hello,

Actually, it is "solved" in #18159 as

sage: X = Set(QQ) sage: Y = Set(Primes()) sage: B = Set(X.difference(Y)) sage: B.cardinality() Traceback (most recent call last): ... NotImplementedError: computation of cardinality of Set-theoretic difference of Set of elements of Rational Field and Set of all prime numbers: 2, 3, 5, 7, ... not yet implemented

... (needs review) ...

### comment:8 Changed 7 years ago by

Milestone: | sage-6.4 → sage-6.7 |
---|

### comment:9 follow-up: 11 Changed 7 years ago by

Milestone: | sage-6.7 → sage-duplicate/invalid/wontfix |
---|---|

Status: | new → needs_review |

Now #18159 is closed and we will have

sage: Set(ZZ).difference(Set()).cardinality() +Infinity sage: Set(QQ).difference(Set(ZZ)).cardinality() NotImplementedError: computation of cardinality of Set-theoretic difference of Set of elements of Rational Field and Set of elements of Integer Ring not yet implemented

I suggest to close this ticket as won't fix. Or do you think it is worth to add a doctest for these?

Vincent

### comment:10 Changed 7 years ago by

I do not think a doctest is needed. I'll compile #18159 as soon as I have a little spare time, and close this ticket if everything looks ok.

### comment:11 Changed 7 years ago by

Status: | needs_review → positive_review |
---|

sage: Set(ZZ).difference(Set()).cardinality() +Infinity sage: Set(QQ).difference(Set(ZZ)).cardinality() NotImplementedError: computation of cardinality of Set-theoretic difference of Set of elements of Rational Field and Set of elements of Integer Ring not yet implemented

Perhaps we should start adding parentheses in those error messages. Something like

computation of cardinality of (Set-theoretic difference of Set of elements of Rational Field) and (Set of elements of Integer Ring) not yet implemented.

But then we would eventually end up with the more lisp-looking message

computation of cardinality of (Set-theoretic difference of Set of elements of (Rational Field)) and (Set of elements of (Integer Ring)) not yet implemented.

Sigh... `:-P`

Nathann

### comment:12 Changed 7 years ago by

Resolution: | → fixed |
---|---|

Status: | positive_review → closed |

**Note:**See TracTickets for help on using tickets.

Hi,

This is not a bug. Deciding if an iterator is finite is semi-decidable and I do not want that because only half of the answer is known we do not give it a try. There are many problems which are known to be undecidable (like equality of symblolic stuff, or the word problem in fg groups). But it is worth it to design the best algorithm that answer most of the cases.

One way to "fix" this non-problem would be to through a warning before we start the enumeration:

Vincent