Repository: sympy/sympy

Issue:
Set.is_subset is broken
This is the main body of `Set.is_subset`:
https://github.com/sympy/sympy/blob/215b9ee31f3aa5eb31826c904674cb2ff37617ff/sympy/sets/sets.py#L369-L375
This is used by all Set subclasses as well since none override this method.

This puts the main task of handling all the different kinds of Set onto the `intersect` method. It is then left with the problem of establishing whether the two sets are equal which it does by first checking with `==` and then checking if the result is an `Intersection`. It actually checks if `other` is *not* an intersection though (clearly that should be `s_o`) and then if it is an intersection it returns `s_o` when it should really return None.
```julia
In [3]: FiniteSet(x).is_subset(FiniteSet(y).intersect(FiniteSet(z)))   
Out[3]: {x} ∩ {y} ∩ {z}
```
These last two problems are fixed in #17526 but others remain.

Firstly intersect might result in an unevaluated Intersection simply because the algorithms don't exist in SymPy to evaluate the result or because it isn't possible to evaluate given arbitrary symbols:
```julia
In [35]: FiniteSet(x).intersect(Interval(y, z))                                                                                   
Out[35]: {x} ∩ [y, z]

In [36]: FiniteSet(x).is_subset(Interval(y, z))                                                                                   
Out[36]: False
```
Secondly we are left with the task even if the intersection evaluates of determining whether the two sets are equal which can fail (especially since this just uses `==`):
```julia
In [37]: S1 = ConditionSet(x, Eq(x**2%2, 0), Integers)                                                                            

In [38]: S2 = ImageSet(Lambda(x, (2*x)**2), Integers)                                                                             

In [39]: S1                                                                                                                       
Out[39]: 
⎧             2          ⎫
⎨x | x ∊ ℤ ∧ x  mod 2 = 0⎬
⎩                        ⎭

In [40]: S2                                                                                                                       
Out[40]: 
⎧   2        ⎫
⎨4⋅x  | x ∊ ℤ⎬
⎩            ⎭

In [41]: S1.is_subset(S2)                                                                                                         
Out[41]: True

In [42]: S2.is_subset(S1)                                                                                                         
Out[42]: False

In [43]: S1.intersect(S2) == S1                                                                                                   
Out[43]: True

In [44]: S2.intersect(S1) == S2                                                                                                   
Out[44]: False
```
Fixing this would mean implementing a proper `Eq(S1, S2)` checker. There are a number of `_eval_Eq` methods for doing this.

I wonder though if a totally different approach is needed. Rather than having `Set.is_subset` delegate to `Subclass.intersect` and `Subclass.eval_Eq` maybe it would be better to define this all the other way round and implement `Eq` on top of `is_subset` (leaving intersect separate). We can define `Set._eval_Eq`as:
```
def _eval_Eq(self, other):
    return fuzzy_and([self.is_subset(other), other.is_subset(self))
``` 
Then the subclasses can implement `is_subset` for different combinations of sets. To me this seems a more natural way to define the equality of sets. I also prefer the idea that equality is clearly built on another boolean (is_subset) rather than depending on evaluation (of the intersection). In turn `is_subset` can be built on top of other primitives like `_contains` in the case of `FiniteSet` or relationals on the parameters of other set types.

Discussion:

Patch:
diff --git a/sympy/sets/fancysets.py b/sympy/sets/fancysets.py
index 5a1cf8dc34..38210f6f69 100644
--- a/sympy/sets/fancysets.py
+++ b/sympy/sets/fancysets.py
@@ -40,6 +40,7 @@ class Rationals(with_metaclass(Singleton, Set)):
     _inf = S.NegativeInfinity
     _sup = S.Infinity
     is_empty = False
+    is_finite_set = False
 
     def _contains(self, other):
         if not isinstance(other, Expr):
@@ -101,6 +102,7 @@ class Naturals(with_metaclass(Singleton, Set)):
     _inf = S.One
     _sup = S.Infinity
     is_empty = False
+    is_finite_set = False
 
     def _contains(self, other):
         if not isinstance(other, Expr):
@@ -110,6 +112,12 @@ def _contains(self, other):
         elif other.is_integer is False or other.is_positive is False:
             return False
 
+    def _eval_is_subset(self, other):
+        return Range(1, oo).is_subset(other)
+
+    def _eval_is_superset(self, other):
+        return Range(1, oo).is_superset(other)
+
     def __iter__(self):
         i = self._inf
         while True:
@@ -136,7 +144,6 @@ class Naturals0(Naturals):
     Integers : also includes the negative integers
     """
     _inf = S.Zero
-    is_empty = False
 
     def _contains(self, other):
         if not isinstance(other, Expr):
@@ -146,6 +153,12 @@ def _contains(self, other):
         elif other.is_integer is False or other.is_nonnegative is False:
             return S.false
 
+    def _eval_is_subset(self, other):
+        return Range(oo).is_subset(other)
+
+    def _eval_is_superset(self, other):
+        return Range(oo).is_superset(other)
+
 
 class Integers(with_metaclass(Singleton, Set)):
     """
@@ -180,6 +193,7 @@ class Integers(with_metaclass(Singleton, Set)):
 
     is_iterable = True
     is_empty = False
+    is_finite_set = False
 
     def _contains(self, other):
         if not isinstance(other, Expr):
@@ -210,6 +224,12 @@ def as_relational(self, x):
         from sympy.functions.elementary.integers import floor
         return And(Eq(floor(x), x), -oo < x, x < oo)
 
+    def _eval_is_subset(self, other):
+        return Range(-oo, oo).is_subset(other)
+
+    def _eval_is_superset(self, other):
+        return Range(-oo, oo).is_superset(other)
+
 
 class Reals(with_metaclass(Singleton, Interval)):
     """
@@ -1375,6 +1395,9 @@ class Complexes(with_metaclass(Singleton, CartesianComplexRegion)):
 
     """
 
+    is_empty = False
+    is_finite_set = False
+
     # Override property from superclass since Complexes has no args
     sets = ProductSet(S.Reals, S.Reals)
 
diff --git a/sympy/sets/handlers/intersection.py b/sympy/sets/handlers/intersection.py
index 7476a55012..216c337e1e 100644
--- a/sympy/sets/handlers/intersection.py
+++ b/sympy/sets/handlers/intersection.py
@@ -126,6 +126,13 @@ def intersection_sets(a, b):
     if r2.start.is_infinite:
         r2 = r2.reversed
 
+    # If both ends are infinite then it means that one Range is just the set
+    # of all integers (the step must be 1).
+    if r1.start.is_infinite:
+        return b
+    if r2.start.is_infinite:
+        return a
+
     # this equation represents the values of the Range;
     # it's a linear equation
     eq = lambda r, i: r.start + i*r.step
diff --git a/sympy/sets/handlers/issubset.py b/sympy/sets/handlers/issubset.py
new file mode 100644
index 0000000000..b96fc9cb65
--- /dev/null
+++ b/sympy/sets/handlers/issubset.py
@@ -0,0 +1,101 @@
+from sympy import S
+from sympy.core.logic import fuzzy_and, fuzzy_bool, fuzzy_not, fuzzy_or
+from sympy.core.relational import Eq
+from sympy.sets.sets import FiniteSet, Interval, Set, Union
+from sympy.sets.fancysets import Complexes, Naturals, Reals, Range, Rationals
+from sympy.multipledispatch import dispatch
+
+
+_inf_sets = [S.Naturals, S.Naturals0, S.Integers, S.Rationals, S.Reals, S.Complexes]
+
+@dispatch(Set, Set)
+def is_subset_sets(a, b):
+    return None
+
+@dispatch(Interval, Interval)
+def is_subset_sets(a, b):
+    # This is correct but can be made more comprehensive...
+    if fuzzy_bool(a.start < b.start):
+        return False
+    if fuzzy_bool(a.end > b.end):
+        return False
+    if (b.left_open and not a.left_open and fuzzy_bool(Eq(a.start, b.start))):
+        return False
+    if (b.right_open and not a.right_open and fuzzy_bool(Eq(a.end, b.end))):
+        return False
+
+@dispatch(Interval, FiniteSet)
+def is_subset_sets(a_interval, b_fs):
+    # An Interval can only be a subset of a finite set if it is finite
+    # which can only happen if it has zero measure.
+    if fuzzy_not(a_interval.measure.is_zero):
+        return False
+
+@dispatch(Interval, Union)
+def is_subset_sets(a_interval, b_u):
+    if all(isinstance(s, (Interval, FiniteSet)) for s in b_u.args):
+        intervals = [s for s in b_u.args if isinstance(s, Interval)]
+        if all(fuzzy_bool(a_interval.start < s.start) for s in intervals):
+            return False
+        if all(fuzzy_bool(a_interval.end > s.end) for s in intervals):
+            return False
+        if a_interval.measure.is_nonzero:
+            no_overlap = lambda s1, s2: fuzzy_or([
+                    fuzzy_bool(s1.end <= s2.start),
+                    fuzzy_bool(s1.start >= s2.end),
+                    ])
+            if all(no_overlap(s, a_interval) for s in intervals):
+                return False
+
+@dispatch(Range, Range)
+def is_subset_sets(a, b):
+    if a.step == b.step == 1:
+        return fuzzy_and([fuzzy_bool(a.start >= b.start),
+                          fuzzy_bool(a.stop <= b.stop)])
+
+@dispatch(Range, Interval)
+def is_subset_sets(a_range, b_interval):
+    if a_range.step.is_positive:
+        if b_interval.left_open and a_range.inf.is_finite:
+            cond_left = a_range.inf > b_interval.left
+        else:
+            cond_left = a_range.inf >= b_interval.left
+        if b_interval.right_open and a_range.sup.is_finite:
+            cond_right = a_range.sup < b_interval.right
+        else:
+            cond_right = a_range.sup <= b_interval.right
+        return fuzzy_and([cond_left, cond_right])
+
+@dispatch(Interval, Range)
+def is_subset_sets(a_interval, b_range):
+    if a_interval.measure.is_extended_nonzero:
+        return False
+
+@dispatch(Interval, Rationals)
+def is_subset_sets(a_interval, b_rationals):
+    if a_interval.measure.is_extended_nonzero:
+        return False
+
+@dispatch(Range, Complexes)
+def is_subset_sets(a, b):
+    return True
+
+@dispatch(Complexes, Interval)
+def is_subset_sets(a, b):
+    return False
+
+@dispatch(Complexes, Range)
+def is_subset_sets(a, b):
+    return False
+
+@dispatch(Complexes, Rationals)
+def is_subset_sets(a, b):
+    return False
+
+@dispatch(Rationals, Reals)
+def is_subset_sets(a, b):
+    return True
+
+@dispatch(Rationals, Range)
+def is_subset_sets(a, b):
+    return False
diff --git a/sympy/sets/sets.py b/sympy/sets/sets.py
index 90579e0adf..c09d8b6310 100644
--- a/sympy/sets/sets.py
+++ b/sympy/sets/sets.py
@@ -12,7 +12,7 @@
 from sympy.core.evalf import EvalfMixin
 from sympy.core.evaluate import global_evaluate
 from sympy.core.expr import Expr
-from sympy.core.logic import fuzzy_bool, fuzzy_or, fuzzy_and
+from sympy.core.logic import fuzzy_bool, fuzzy_or, fuzzy_and, fuzzy_not
 from sympy.core.numbers import Float
 from sympy.core.operations import LatticeOp
 from sympy.core.relational import Eq, Ne
@@ -59,21 +59,8 @@ class Set(Basic):
     is_Complement = None
     is_ComplexRegion = False
 
-    @property
-    def is_empty(self):
-        """
-        Property method to check whether a set is empty.
-        Returns ``True``, ``False`` or ``None`` (if unknown).
-
-        Examples
-        ========
-
-        >>> from sympy import Interval, var
-        >>> x = var('x', real=True)
-        >>> Interval(x, x + 1).is_empty
-        False
-        """
-        return None
+    is_empty = None
+    is_finite_set = None
 
     @property
     @deprecated(useinstead="is S.EmptySet or is_empty",
@@ -363,25 +350,50 @@ def is_subset(self, other):
         False
 
         """
-        if isinstance(other, Set):
-            dispatch = getattr(self, '_eval_is_subset', None)
-            if dispatch is not None:
-                ret = dispatch(other)
-                if ret is not None:
-                    return ret
-
-            s_o = self.intersect(other)
-            if s_o == self:
-                return True
-            # This assumes that an unevaluated Intersection will always come
-            # back as an Intersection...
-            elif isinstance(s_o, Intersection):
-                return None
-            else:
-                return False
-        else:
+        if not isinstance(other, Set):
             raise ValueError("Unknown argument '%s'" % other)
 
+        # Handle the trivial cases
+        if self == other:
+            return True
+        is_empty = self.is_empty
+        if is_empty is True:
+            return True
+        elif fuzzy_not(is_empty) and other.is_empty:
+            return False
+        if self.is_finite_set is False and other.is_finite_set:
+            return False
+
+        # Dispatch on subclass rules
+        ret = self._eval_is_subset(other)
+        if ret is not None:
+            return ret
+        ret = other._eval_is_superset(self)
+        if ret is not None:
+            return ret
+
+        # Use pairwise rules from multiple dispatch
+        from sympy.sets.handlers.issubset import is_subset_sets
+        ret = is_subset_sets(self, other)
+        if ret is not None:
+            return ret
+
+        # Fall back on computing the intersection
+        # XXX: We shouldn't do this. A query like this should be handled
+        # without evaluating new Set objects. It should be the other way round
+        # so that the intersect method uses is_subset for evaluation.
+        if self.intersect(other) == self:
+            return True
+
+    def _eval_is_subset(self, other):
+        '''Returns a fuzzy bool for whether self is a subset of other.'''
+        return None
+
+    def _eval_is_superset(self, other):
+        '''Returns a fuzzy bool for whether self is a subset of other.'''
+        return None
+
+    # This should be deprecated:
     def issubset(self, other):
         """
         Alias for :meth:`is_subset()`
@@ -426,6 +438,7 @@ def is_superset(self, other):
         else:
             raise ValueError("Unknown argument '%s'" % other)
 
+    # This should be deprecated:
     def issuperset(self, other):
         """
         Alias for :meth:`is_superset()`
@@ -808,6 +821,11 @@ def __iter__(self):
     def is_empty(self):
         return fuzzy_or(s.is_empty for s in self.sets)
 
+    @property
+    def is_finite_set(self):
+        all_finite = fuzzy_and(s.is_finite_set for s in self.sets)
+        return fuzzy_or([self.is_empty, all_finite])
+
     @property
     def _measure(self):
         measure = 1
@@ -1004,6 +1022,10 @@ def is_empty(self):
             cond = self.start > self.end  # Both bounds closed
         return fuzzy_bool(cond)
 
+    @property
+    def is_finite_set(self):
+        return self.measure.is_zero
+
     def _complement(self, other):
         if other == S.Reals:
             a = Interval(S.NegativeInfinity, self.start,
@@ -1178,6 +1200,10 @@ def _sup(self):
     def is_empty(self):
         return fuzzy_and(set.is_empty for set in self.args)
 
+    @property
+    def is_finite_set(self):
+        return fuzzy_and(set.is_finite_set for set in self.args)
+
     @property
     def _measure(self):
         # Measure of a union is the sum of the measures of the sets minus
@@ -1236,6 +1262,9 @@ def boundary_of_set(i):
     def _contains(self, other):
         return Or(*[s.contains(other) for s in self.args])
 
+    def is_subset(self, other):
+        return fuzzy_and(s.is_subset(other) for s in self.args)
+
     def as_relational(self, symbol):
         """Rewrite a Union in terms of equalities and logic operators. """
         if all(isinstance(i, (FiniteSet, Interval)) for i in self.args):
@@ -1326,6 +1355,11 @@ def args(self):
     def is_iterable(self):
         return any(arg.is_iterable for arg in self.args)
 
+    @property
+    def is_finite_set(self):
+        if fuzzy_or(arg.is_finite_set for arg in self.args):
+            return True
+
     @property
     def _inf(self):
         raise NotImplementedError()
@@ -1551,6 +1585,15 @@ def is_iterable(self):
         if self.args[0].is_iterable:
             return True
 
+    @property
+    def is_finite_set(self):
+        A, B = self.args
+        a_finite = A.is_finite_set
+        if a_finite is True:
+            return True
+        elif a_finite is False and B.is_finite_set:
+            return False
+
     def __iter__(self):
         A, B = self.args
         for a in A:
@@ -1586,6 +1629,7 @@ class EmptySet(with_metaclass(Singleton, Set)):
     .. [1] https://en.wikipedia.org/wiki/Empty_set
     """
     is_empty = True
+    is_finite_set = True
     is_FiniteSet = True
 
     @property
@@ -1652,6 +1696,7 @@ class UniversalSet(with_metaclass(Singleton, Set)):
 
     is_UniversalSet = True
     is_empty = False
+    is_finite_set = False
 
     def _complement(self, other):
         return S.EmptySet
@@ -1704,6 +1749,7 @@ class FiniteSet(Set, EvalfMixin):
     is_FiniteSet = True
     is_iterable = True
     is_empty = False
+    is_finite_set = True
 
     def __new__(cls, *args, **kwargs):
         evaluate = kwargs.get('evaluate', global_evaluate[0])
@@ -1801,6 +1847,9 @@ def _contains(self, other):
         # we need Eq to do the evaluation
         return fuzzy_or(fuzzy_bool(Eq(e, other, evaluate=True)) for e in self.args)
 
+    def _eval_is_subset(self, other):
+        return fuzzy_and(other._contains(e) for e in self.args)
+
     @property
     def _boundary(self):
         return self


Test patch:
diff --git a/sympy/calculus/tests/test_singularities.py b/sympy/calculus/tests/test_singularities.py
index 90618e17d1..a741ca2e5c 100644
--- a/sympy/calculus/tests/test_singularities.py
+++ b/sympy/calculus/tests/test_singularities.py
@@ -46,6 +46,8 @@ def test_is_increasing():
     assert is_increasing(-x**2*a, Interval(1, oo), x)
     assert is_increasing(1)
 
+    assert is_increasing(4*x**3 - 6*x**2 - 72*x + 30, Interval(-2, 3)) is False
+
 
 def test_is_strictly_increasing():
     """Test whether is_strictly_increasing returns correct value."""
@@ -58,6 +60,7 @@ def test_is_strictly_increasing():
     assert not is_strictly_increasing(-x**2, Interval(0, oo))
     assert not is_strictly_decreasing(1)
 
+    assert is_strictly_increasing(4*x**3 - 6*x**2 - 72*x + 30, Interval.open(-2, 3)) is False
 
 def test_is_decreasing():
     """Test whether is_decreasing returns correct value."""
diff --git a/sympy/sets/tests/test_fancysets.py b/sympy/sets/tests/test_fancysets.py
index c278a3c300..583ffe2f11 100644
--- a/sympy/sets/tests/test_fancysets.py
+++ b/sympy/sets/tests/test_fancysets.py
@@ -477,6 +477,7 @@ def test_Reals():
     assert S.Reals == Interval(-oo, oo)
     assert S.Reals != Interval(0, oo)
     assert S.Reals.is_subset(Interval(-oo, oo))
+    assert S.Reals.intersect(Range(-oo, oo)) == Range(-oo, oo)
 
 
 def test_Complex():
diff --git a/sympy/sets/tests/test_sets.py b/sympy/sets/tests/test_sets.py
index 755f6ef4be..b432a4fe1b 100644
--- a/sympy/sets/tests/test_sets.py
+++ b/sympy/sets/tests/test_sets.py
@@ -55,7 +55,34 @@ def f(x):
 def test_is_empty():
     for s in [S.Naturals, S.Naturals0, S.Integers, S.Rationals, S.Reals,
             S.UniversalSet]:
-        assert s.is_empty == False
+        assert s.is_empty is False
+
+    assert S.EmptySet.is_empty is True
+
+
+def test_is_finiteset():
+    for s in [S.Naturals, S.Naturals0, S.Integers, S.Rationals, S.Reals,
+            S.UniversalSet]:
+        assert s.is_finite_set is False
+
+    assert S.EmptySet.is_finite_set is True
+
+    assert FiniteSet(1, 2).is_finite_set is True
+    assert Interval(1, 2).is_finite_set is False
+    assert Interval(x, y).is_finite_set is None
+    assert ProductSet(FiniteSet(1), FiniteSet(2)).is_finite_set is True
+    assert ProductSet(FiniteSet(1), Interval(1, 2)).is_finite_set is False
+    assert ProductSet(FiniteSet(1), Interval(x, y)).is_finite_set is None
+    assert Union(Interval(0, 1), Interval(2, 3)).is_finite_set is False
+    assert Union(FiniteSet(1), Interval(2, 3)).is_finite_set is False
+    assert Union(FiniteSet(1), FiniteSet(2)).is_finite_set is True
+    assert Union(FiniteSet(1), Interval(x, y)).is_finite_set is None
+    assert Intersection(Interval(x, y), FiniteSet(1)).is_finite_set is True
+    assert Intersection(Interval(x, y), Interval(1, 2)).is_finite_set is None
+    assert Intersection(FiniteSet(x), FiniteSet(y)).is_finite_set is True
+    assert Complement(FiniteSet(1), Interval(x, y)).is_finite_set is True
+    assert Complement(Interval(x, y), FiniteSet(1)).is_finite_set is None
+    assert Complement(Interval(1, 2), FiniteSet(x)).is_finite_set is False
 
 
 def test_deprecated_is_EmptySet():
@@ -616,6 +643,9 @@ def test_is_subset():
     assert FiniteSet(x).is_subset(FiniteSet(y).subs(y, x)) is True
     assert FiniteSet(x).is_subset(FiniteSet(y).subs(y, x+1)) is False
 
+    assert Interval(0, 1).is_subset(Interval(0, 1, left_open=True)) is False
+    assert Interval(-2, 3).is_subset(Union(Interval(-oo, -2), Interval(3, oo))) is False
+
 
 def test_is_proper_subset():
     assert Interval(0, 1).is_proper_subset(Interval(0, 2)) is True