Repository: sympy/sympy
Pull request: increase safety of ConditionSet
<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234". See
https://github.com/blog/1506-closing-issues-via-pull-requests .-->

fixes #14495 
fixes #14500

#### Brief description of what is fixed or changed

ConditionSet uses more caution when undergoing substitution. For the most part, that first argument should be treated like a dummy and not touched. But when possible, it can be changed to a new symbol provided that the assumptions are less restrictive and matching in commutativity.
```
>>> ConditionSet(x, x < 2, {y, z}).subs(x, 1)
ConditionSet(x, x < 2, {y, z})  <-- formerly {y, z}

>>> ConditionSet(x, x > 5, Interval(1, 7)).subs(x, Symbol('n', negative=True))  <-- formerly EmptySet
Traceback (most recent call last):
...
ValueError:
A dummy symbol can only be replaced with a symbol having the same
assumptions or one having a single assumption having the same
commutativity.
```

#### Other comments


Problem statement:
guard dummy symbol of ConditionSet
Don't target the first argument unless the replacement is of symbol -> symbol type:
```
>>> ConditionSet(x, Eq(y, 0), S.Integers).subs(x,1)
ConditionSet(1, Eq(y, 0), S.Integers)  # should be unchanged
```



ambiguous behavior of ConditionSet
```
Help on class ConditionSet in module sympy.sets.conditionset:

class ConditionSet(sympy.sets.sets.Set)
 |  Set of elements which satisfies a given condition.
 |
 |  {x | condition(x) is True for x in S}

...
```
Does that mean the "set of all x in S for which condition(x) is True" or "the set S if the condition(x) is True"?
```
>>> c = ConditionSet(x,x>5,Interval(1,7))
>>> c.subs(x,8)  # 8 is not in S
Interval(1, 7)
>>> 8 in c
False

>>> c = ConditionSet(x,x>5,S.Integers)
>>> c.subs(x,2*pi)  # 2pi is not an integer
S.Integers
>>> 2*pi in c
False

>>> c=ConditionSet(y,x>5,S.Integers)
>>> c.subs(x,4)
EmptySet()
>>> c.subs(x,6)
S.Integers
>>> 6 in c
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "...sympy\sets\sets.py", line 556, in __contains__
    raise TypeError('contains did not evaluate to a bool: %r' % symb)
TypeError: contains did not evaluate to a bool: x > 5
>>> 3 in c
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "...sympy\sets\sets.py", line 556, in __contains__
    raise TypeError('contains did not evaluate to a bool: %r' % symb)
TypeError: contains did not evaluate to a bool: x > 5

Perhaps an error at instantiation should be raise if the condition is not a function of the given variable?
```
Also, should there be a doit method or autoevaluation for something like this?
```
>>> ConditionSet(x,x>5,Interval(1,3))
ConditionSet(x, x > 5, Interval(1, 3))  <--- should this evaluate to False?
```

Other fixes:
`ConditionSet(x,x>5,Interval(1,7)).subs(x, 8)` should be S.EmptySet

`ConditionSet(x,x>5,Interval(1,7)).subs(x, Symbol('n', negative=True)` should be unchanged: the dummy is not there to help with the condition, only to test idientify where the element from the base_set should be tested in the condition.

Hints from issue discussion:
The base set should not be targeted if the old matches the sym of the condition set.

Or wait...perhaps only the base set should be targetted in this case.
It should mean  "set of all x in S for which condition(x) is True". The role of `x` is comparable to the role of an integration variable in a definite integral: It can be replaced by another symbol but it does not make sense to replace it by a number.

I think `ConditionSet(x,x>5,Interval(1,3))` should evaluate to `EmptySet`.
So it's like a filter? If so, then ConditionSet(x, x> 5, S.Reals) -> Interval.open(5, oo). If I understand correctly, it is similar to ImageSet. We could write `ImageSet(Lambda(x, 2*x), S.Integers)` or `ConditionSet(x, Eq(Mod(x, 2), 0), S.Integers)` to mean "the set of even integers". A difference, however, is that the former is iterable:

```
>>> it = iter(ImageSet(Lambda(x, 2*x), S.Integers))
>>> [next(it) for i in range(5)]
[0, 2, −2, 4, −4]
```
`ConditionSet(x,x>5,Interval(1,7)).subs(x, 8)` should be S.EmptySet
`ConditionSet(x,x>5,Interval(1,7)).subs(x, Symbol('n', negative=True)` should be unchanged: the dummy is not there to help with the condition, only to test idientify where the element from the `base_set` should be tested in the condition.

Current behavior of ConditionSet does not allow the dummy symbol to be replaced with anything but a symbol so `ConditionSet(x,x>5,Interval(1,7)).subs(x, 8)` is unchanged which looks right to me.

Containment also looks ok:
```
>>> 8 in ConditionSet(x,x>5,Interval(1,7))
False
>>> 0 in ConditionSet(x,x>5,Interval(1,7))
False
>>> 2 in ConditionSet(x,x>5,Interval(1,7))
False
>>> 6 in ConditionSet(x,x>5,Interval(1,7))
True
```

Treatment of a condition that is independent of the dummy symbol looks ok:

```
ConditionSet(y,x>5,S.Integers).subs(x, 8) -> S.Integers since the condition is always true
```

There are only 2 deficient behaviors that I see right now:

1. The following should not evaluate since the dummy is not there to help with the condition, only to identify how the element from the `base_set` should be tested in the condition.
```
ConditionSet(x,x>5,Interval(1,7)).subs(x, Symbol('n', negative=True))
```
2. containment tests when the condition is independent of the dummy variable
```
>>> 6 in ConditionSet(x,y>5,Interval(1,7))
Traceback (most recent call last):
...
TypeError: contains did not evaluate to a bool: y > 5
```
I believe the result should be false if the value is not in the base set; and if it is, then the condition should be returned:
```
>> 6 in ConditionSet(x,y>5,Interval(1,7))
y > 5
>> 0 in ConditionSet(x,y>5,Interval(1,7))
False
```
I agree with this.
> containment tests when the condition is independent of the dummy variable

It appears that when a test is written as `foo in bah` must give True or False; the containment method can give a conditional answer, however.

Commit message: increase safety of ConditionSet

Patch to review:
diff --git a/sympy/sets/conditionset.py b/sympy/sets/conditionset.py
index bb0e21dc79a0..d45d78163b58 100644
--- a/sympy/sets/conditionset.py
+++ b/sympy/sets/conditionset.py
@@ -1,8 +1,10 @@
 from __future__ import print_function, division
 
 from sympy import S
+from sympy.sets.contains import Contains
 from sympy.core.basic import Basic
 from sympy.core.containers import Tuple
+from sympy.core.expr import Expr
 from sympy.core.function import Lambda
 from sympy.core.logic import fuzzy_bool
 from sympy.core.symbol import Symbol, Dummy
@@ -10,6 +12,7 @@
 from sympy.sets.sets import (Set, Interval, Intersection, EmptySet, Union,
                              FiniteSet)
 from sympy.utilities.iterables import sift
+from sympy.utilities.misc import filldedent
 from sympy.multipledispatch import dispatch
 
 
@@ -23,7 +26,8 @@ class ConditionSet(Set):
     ========
 
     >>> from sympy import Symbol, S, ConditionSet, pi, Eq, sin, Interval
-    >>> x = Symbol('x')
+    >>> from sympy.abc import x, y
+
     >>> sin_sols = ConditionSet(x, Eq(sin(x), 0), Interval(0, 2*pi))
     >>> 2*pi in sin_sols
     True
@@ -33,6 +37,53 @@ class ConditionSet(Set):
     False
     >>> 5 in ConditionSet(x, x**2 > 4, S.Reals)
     True
+
+    If the value is not in the base set, the result is false:
+
+    >>> 5 in ConditionSet(x, x**2 > 4, Interval(2, 4))
+    False
+
+    Notes
+    =====
+
+    Symbols with assumptions should be avoided or else the
+    condition may evaluate without consideration of the set:
+
+    >>> n = Symbol('n', negative=True)
+    >>> cond = (n > 0); cond
+    False
+    >>> ConditionSet(n, cond, S.Integers)
+    EmptySet()
+
+    In addition, substitution of a dummy symbol can only be
+    done with a generic symbol with matching commutativity
+    or else a symbol that has identical assumptions.
+
+    Although expressions other than symbols may be used, this
+    is discouraged and will raise an error if the expression
+    is not found in the condition:
+
+    >>> ConditionSet(x + 1, x + 1 < 1, S.Integers)
+    ConditionSet(x + 1, x + 1 < 1, S.Integers)
+
+    >>> ConditionSet(x + 1, x < 1, S.Integers)
+    Traceback (most recent call last):
+    ...
+    ValueError: non-symbol dummy not recognized in condition
+
+    Although the name is usually respected, it must be replaced if
+    the base set is another ConditionSet and the dummy symbol
+    and appears as a free symbol in the base set and the dummy symbol
+    of the base set appears as a free symbol in the condition:
+
+    >>> ConditionSet(x, x < y, ConditionSet(y, x + y < 2, S.Integers))
+    ConditionSet(lambda, (lambda < y) & (lambda + x < 2), S.Integers)
+
+    The best way to do anything with the dummy symbol is to access
+    it with the sym property.
+
+    >>> _.subs(_.sym, Symbol('_x'))
+    ConditionSet(_x, (_x < y) & (_x + x < 2), S.Integers)
     """
     def __new__(cls, sym, condition, base_set):
         # nonlinsolve uses ConditionSet to return an unsolved system
@@ -84,13 +135,16 @@ def __new__(cls, sym, condition, base_set):
                         condition.xreplace({sym: dum}),
                         c.xreplace({s: dum}))
                     sym = dum
-            if sym in base_set.free_symbols or \
-                    not isinstance(sym, Symbol):
-                s = Symbol('lambda')
-                if s in base_set.free_symbols:
-                    s = Dummy('lambda')
-                condition = condition.xreplace({sym: s})
-                sym = s
+            inbase = sym in base_set.free_symbols
+            if inbase or not isinstance(sym, Symbol):
+                s = Dummy('lambda')
+                cond = condition.xreplace({sym: s})
+                if s not in cond.free_symbols:
+                    raise ValueError(
+                        'non-symbol dummy not recognized in condition')
+                if inbase:
+                    condition = cond
+                    sym = s
         return Basic.__new__(cls, sym, condition, base_set)
 
     sym = property(lambda self: self.args[0])
@@ -107,16 +161,40 @@ def contains(self, other):
             other), self.base_set.contains(other))
 
     def _eval_subs(self, old, new):
-        if not isinstance(self.sym, Symbol):
+        if not isinstance(self.sym, Expr):
             # Don't do anything with the equation set syntax;
             # that should go away, eventually.
             return self
-        if old == self.sym:
-            if new not in self.free_symbols:
-                if isinstance(new, Symbol):
-                    return self.func(*[i.subs(old, new) for i in self.args])
-            return self.func(self.sym, self.condition, self.base_set.subs(old, new))
-        return self.func(*([self.sym] + [i.subs(old, new) for i in self.args[1:]]))
+        sym, cond, base = self.args
+        if old == sym:
+            # we try to be as lenient as possible to allow
+            # the dummy symbol to be changed
+            base = base.subs(old, new)
+            if base != self.base_set:
+                # deference is given to the base set
+                return self.func(sym, cond, base)
+            if isinstance(new, Symbol):
+                # if the assumptions don't match, the cond
+                # might evaluate or change
+                if (new.assumptions0 == old.assumptions0 or
+                        len(new.assumptions0) == 1 and
+                        old.is_commutative == new.is_commutative):
+                    return self.func(new, cond.subs(old, new), base)
+                raise ValueError(filldedent('''
+                    A dummy symbol can only be
+                    replaced with a symbol having the same
+                    assumptions or one having a single assumption
+                    having the same commutativity.
+                '''))
+            # don't target cond: it is there to tell how
+            # the base set should be filtered and if new is not in
+            # the base set then this substitution is ignored
+            return self
+        cond = self.condition.subs(old, new)
+        base = self.base_set.subs(old, new)
+        if cond is S.true:
+            return ConditionSet(new, Contains(new, base), base)
+        return self.func(self.sym, cond, base)
 
     def dummy_eq(self, other, symbol=None):
         if not isinstance(other, self.func):
diff --git a/sympy/sets/tests/test_conditionset.py b/sympy/sets/tests/test_conditionset.py
index ae094ccb18a0..c5997c2a0dfc 100644
--- a/sympy/sets/tests/test_conditionset.py
+++ b/sympy/sets/tests/test_conditionset.py
@@ -1,7 +1,7 @@
 from sympy.sets import (ConditionSet, Intersection, FiniteSet,
     EmptySet, Union)
 from sympy import (Symbol, Eq, Lt, S, Abs, sin, pi, Lambda, Interval,
-    And, Mod)
+    And, Mod, oo, Function)
 from sympy.utilities.pytest import raises
 
 
@@ -10,6 +10,7 @@
 y = Symbol('y')
 z = Symbol('z')
 L = Symbol('lambda')
+f = Function('f')
 
 
 def test_CondSet():
@@ -20,6 +21,16 @@ def test_CondSet():
     assert 3*pi not in sin_sols_principal
     assert 5 in ConditionSet(x, x**2 > 4, S.Reals)
     assert 1 not in ConditionSet(x, x**2 > 4, S.Reals)
+    # in this case, 0 is not part of the base set so
+    # it can't be in any subset selected by the condition
+    assert 0 not in ConditionSet(x, y > 5, Interval(1, 7))
+    # since 'in' requires a true/false, the following raises
+    # an error because the given value provides no information
+    # for the condition to evaluate (since the condition does
+    # not depend on the dummy symbol): the result is `y > 5`.
+    # In this case, ConditionSet is just acting like
+    # Piecewise((Interval(1, 7), y > 5), (S.EmptySet, True)).
+    raises(TypeError, lambda: 6 in ConditionSet(x, y > 5, Interval(1, 7)))
 
     assert isinstance(ConditionSet(x, x < 1, {x, y}).base_set, FiniteSet)
     raises(TypeError, lambda: ConditionSet(x, x + 1, {x, y}))
@@ -84,11 +95,35 @@ def test_subs_CondSet():
     # you can only replace sym with a symbol that is not in
     # the free symbols
     assert c.subs(x, 1) == c
-    assert c.subs(x, y) == c
+    assert c.subs(x, y) == ConditionSet(y, y < 2, s)
+    assert ConditionSet(y, y < 2, s).subs(
+        y, w) == ConditionSet(y, y < 2, {w, z})
     assert c.subs(x, w) == ConditionSet(w, w < 2, s)
     assert ConditionSet(x, x < y, s
         ).subs(y, w) == ConditionSet(x, x < w, s.subs(y, w))
-
+    # if the user uses assumptions that cause the condition
+    # to evaluate, that can't be helped from SymPy's end
+    n = Symbol('n', negative=True)
+    assert ConditionSet(n, 0 < n, S.Integers) is S.EmptySet
+    p = Symbol('p', positive=True)
+    assert ConditionSet(n, n < y, S.Integers
+        ).subs(n, x) == ConditionSet(x, x < y, S.Integers)
+    nc = Symbol('nc', commutative=False)
+    raises(ValueError, lambda: ConditionSet(
+        x, x < p, S.Integers).subs(x, nc))
+    raises(ValueError, lambda: ConditionSet(
+        x, x < p, S.Integers).subs(x, n))
+    raises(ValueError, lambda: ConditionSet(
+        x + 1, x < 1, S.Integers))
+    assert ConditionSet(
+        n, n < x, Interval(0, oo)).subs(x, p) == Interval(0, oo)
+    assert ConditionSet(
+        n, n < x, Interval(-oo, 0)).subs(x, p) == S.EmptySet
+    assert ConditionSet(f(x), f(x) < 1, {w, z}
+        ).subs(f(x), y) == ConditionSet(y, y < 1, {w, z})
+
+
+def test_subs_CondSet_tebr():
     # to eventually be removed
     c = ConditionSet((x, y), {x + 1, x + y}, S.Reals)
     assert c.subs(x, z) == c
@@ -111,3 +146,18 @@ def test_dummy_eq():
     assert c1.dummy_eq(c3) is False
     assert c.dummy_eq(c1) is False
     assert c1.dummy_eq(c) is False
+
+
+def test_contains():
+    assert 6 in ConditionSet(x, x > 5, Interval(1, 7))
+    assert (8 in ConditionSet(x, y > 5, Interval(1, 7))) is False
+    # `in` should give True or False; in this case there is not
+    # enough information for that result
+    raises(TypeError,
+        lambda: 6 in ConditionSet(x, y > 5, Interval(1, 7)))
+    assert ConditionSet(x, y > 5, Interval(1, 7)
+        ).contains(6) == (y > 5)
+    assert ConditionSet(x, y > 5, Interval(1, 7)
+        ).contains(8) is S.false
+    assert ConditionSet(x, y > 5, Interval(1, 7)
+        ).contains(w) == And(w >= 1, w <= 7, y > 5)


Code review comments:
diff_hunk: @@ -33,6 +37,53 @@ class ConditionSet(Set):
     False
     >>> 5 in ConditionSet(x, x**2 > 4, S.Reals)
     True
+
+    If the value is not in the base set, the result is false:
+
+    >>> 5 in ConditionSet(x, x**2 > 4, Interval(2, 4))
+    False
+
+    Notes
+    =====
+
+    Symbols with assumptions should be avoided or else the
+    condition may evaluate without consideration of the set:
+
+    >>> n = Symbol('n', negative=True)
+    >>> cond = (n > 0); cond
+    False
+    >>> ConditionSet(n, cond, S.Integers)
+    EmptySet()
+
+    In addition, substitution of a dummy symbol can only be
+    done with a generic symbol with matching commutativity
+    or else a symbol that has identical assumptions.
+
+    Although expressions other than symbols may be used, this
+    is discouraged and will raise an error if the expression
+    is not found in the condition:
+
+    >>> ConditionSet(x + 1, x + 1 < 1, S.Integers)
path: sympy/sets/conditionset.py
text: @user1:
Expressions of this type may become confusing. `ConditionSet(x, x < 1, {-1, 0, 1})` is `{-1, 0}` but what should `ConditionSet(x + 1, x + 1 < 1, {-1, 0, 1})` be? I think that it could be expected to be "the set of `x + 1` for `x` in `{-1, 0, 1}` such that `x + 1 < 1`", which is `{0}`. To obtain `{-1, 0}`, the base set `{-1, 0, 1}` should be "relocated" to `{-2, -1, 0}`.

(This is analogous to replacing `x` by `x + 1` in `Integral(x, (x, -1, 1))`. The limits have to be changed too: `Integral(x + 1, (x, -2, 0))`.)

ConditionSets of this type may be useful in some connections, but I think that substitutions like `x -> x + 1` should be allowed only under strict restrictions (if at all).

@author:
> I think that substitutions like x -> x + 1 should be allowed only under strict restrictions (if at all).

It is disallowed. While one can *create* a ConditionSet with a non-symbol (think "generator") a replacement cannot be made. 
```
>>> ConditionSet(x,x<1,S.Integers).subs(x,x+1)
ConditionSet(x, x < 1, S.Integers)
```
The elements in the base set are the values of the ConditionSet.sym that are filtered by the condition:
```
>>> ConditionSet(x+1,x+1<1,{0,1})
{0}
```
I don't really like that behavior. As much as I have done, however, is to make sure that the sym can be identified in the condition. When it can't, an error is raised as shown in the doctests. (But I see that the case of a FiniteSet base set is not handled properly to catch this.
```
>>> ConditionSet(x+1,x<2,{0,1,3})
ConditionSet(x + 1, x < 2, {0, 1, 3})  <==needs to raise an error.
```

@user2:
The definition is (from the docstring)

```
{x | condition(x) is True for x in S}
```

So the set `ConditionSet(x + 1, x + 1 < 1, {-1, 0, 1})` would be `{x + 1 | x + 1 < 1 and x + 1 in {-1, 0, 1}}`, which is the same as `{x | x < 1 and x in {-1, 0, 1}}` (i.e., `{-1, 0}`). 

Effectively, a condition set represents the set builder notation `{x | P(x)}`, but to disallow open ended definitions, a domain is required, `{x | P(x) ∧ x ∈ S }` (actually you could just let `S` be UniversalSet if you wanted).

Ideally we should allow more general set builder notation `{f(x) | P}`. But the problem is with the domain. Requiring it to be of the form `{f(x) | P ∧ f(x) ∈ S}` seems odd, and might be unexpected. 

I don't know how easy it would be to do, but can we make the third argument of the `ConditionSet` optional, defaulting to `UniversalSet` (and `Contains(x, UniversalSet)` should evaluate to `True` automatically)? Then allow more advanced set builder, but perhaps disallow it for the three argument variant (I'm not sure). One can always include a domain restriction as part of the predicate, like `ConditionSet(x + 1, And(x + 1 < 0, Contains(x, {-1, 0, 1})))` (note here `x` is in `{-1, 0, 1}`, not `x + 1`).

I was never really clear on why the third argument to `ConditionSet` was required. You can already create open ended sets anyway by using `UniversalSet` as the third argument. I think it would be more convenient, symbolically, to just allow open ended sets by default. Forcing a domain makes it harder to deal with sets of more abstract things than just numbers. Obviously something like `solveset` should always return a set that is a subset of the given domain. 

By the way, we don't have symbolic sets yet, but once we do, it will be possible to build Russell's paradox with `ConditionSet(SetSymbol("A"), Not(Contains(SetSymbol("A"), SetSymbol("A")), S.UniversalSet)`.

@user2:
The [Wikipedia article](https://en.wikipedia.org/wiki/Set-builder_notation) is a good reference for this. 

@author:
How does this look?
```
>>> c = ConditionSet(x, x < 2); c
ConditionSet(x, x < 2)
>>> c.base_set
UniversalSet()
>>> pprint(c)
{x | x < 2}
>>> latex(c)
'\\left\\{x\\; |\\; x < 2 \\right\\}'
```

@author:
ping @user2 , @user1 

@user1:
This looks ok to me. The combination `\\; |\\;` could be replaced by `\\mid`.

@author:
OK, this has been changed.