Cardinality of infinite sets loops forever

[Luca De Feo]

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()

[Vincent Delecroix]

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

[Luca De Feo]

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".

[Vincent Delecroix]

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.

[Luca De Feo]

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.

[Karl-Dieter Crisman]

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

[Vincent Delecroix]

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) ...

[Vincent Delecroix]

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

[Luca De Feo]

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.

[Nathann Cohen]

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