Opened 7 years ago

Closed 6 years ago

#16676 closed defect (fixed)

Cardinality of infinite sets loops forever

Reported by: defeo 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:

Status badges

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 7 years ago by vdelecroix

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:

sage: QQ.difference(ZZ).cardinality()
Warning: Sage does not know whether this set is finite or infinite
and will try to enumerate of all its element to see... (you can
interrupt the computation with Ctrl-C in the console or Echap
in the notebook)

Vincent

comment:2 follow-up: Changed 7 years ago by defeo

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 in reply to: ↑ 2 ; follow-up: Changed 7 years ago by 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.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by defeo

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 in reply to: ↑ 4 Changed 7 years ago by kcrisman

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.

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 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 6 years ago by vdelecroix

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 6 years ago by vdelecroix

  • Milestone changed from sage-6.4 to sage-6.7

comment:9 follow-up: Changed 6 years ago by vdelecroix

  • Milestone changed from sage-6.7 to sage-duplicate/invalid/wontfix
  • Status changed from new to 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 6 years ago by defeo

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 in reply to: ↑ 9 Changed 6 years ago by ncohen

  • Status changed from needs_review to 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 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.