Opened 5 years ago

Closed 18 months ago

#24171 closed enhancement (fixed)

Formal set membership function

Reported by: Ralf Stephan Owned by:
Priority: major Milestone: sage-9.4
Component: symbolics Keywords:
Cc: Vincent Delecroix Merged in:
Authors: Ralf Stephan, Matthias Koeppe Reviewers: Travis Scrimshaw, Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: a8c94ca (Commits, GitHub, GitLab) Commit: a8c94cab974c8983dad63c2c6e989936984de49a
Dependencies: #31877 Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

To express solution sets from solvers an expression-is-element-of-set relation is needed. For ease of implementation this can be made a formal function element_of.

It depends on sets being made coercible into SR. The present ticket plays safe and only does this for finite sets and a few standard infinite sets: NN, ZZ, QQ, AA; and RealSets.

element_of converts to SymPy's Contains. This is useful in combination with #31931, which adds SymPy conversions to some of the above sets.

Change History (50)

comment:1 Changed 5 years ago by Ralf Stephan

Description: modified (diff)

comment:2 Changed 5 years ago by Ralf Stephan

Branch: u/rws/formal_set_membership_function

comment:3 Changed 5 years ago by Ralf Stephan

Authors: Ralf Stephan
Commit: 669ea22318ab33f23f727626eb30e59fa138d253
Status: newneeds_review

New commits:

669ea2224171: Formal set membership function

comment:4 Changed 5 years ago by Travis Scrimshaw

I can reproduce this error

**********************************************************************
File "src/sage/misc/dev_tools.py", line 438, in sage.misc.dev_tools.import_statements
Failed example:
    load_submodules(sage.sets)
Expected:
    load sage.sets.real_set... succeeded
    load sage.sets.set_from_iterator... succeeded
Got:
    load sage.sets.set_from_iterator... succeeded

I think why this now fails is because real_set is now loaded on startup.

comment:5 Changed 5 years ago by Ralf Stephan

Status: needs_reviewneeds_work

I think it would be good if RealSet answered positive to is_Set, I'm just not sure how to accomplish it correctly. If done it wouldn't need to be loaded at start.

comment:6 Changed 5 years ago by git

Commit: 669ea22318ab33f23f727626eb30e59fa138d253af82717b1bfeffbe6fc972686882916b0525b149

Branch pushed to git repo; I updated commit sha1. New commits:

34c977324171: make RealSet inherit from Set_generic
af8271724171: remove RealSet import; SR set coercion doctests

comment:7 Changed 5 years ago by Ralf Stephan

Status: needs_workneeds_review

comment:8 Changed 5 years ago by git

Commit: af82717b1bfeffbe6fc972686882916b0525b149592ce8745028ec0659b952e872dfff0a85ef5a5d

Branch pushed to git repo; I updated commit sha1. New commits:

592ce8724171: Py3 fixes

comment:9 Changed 5 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

LGTM. Thanks.

comment:10 Changed 5 years ago by Ralf Stephan

Thanks for the review.

comment:11 Changed 5 years ago by Volker Braun

Status: positive_reviewneeds_work

Merge conflictw

comment:12 Changed 5 years ago by git

Commit: 592ce8745028ec0659b952e872dfff0a85ef5a5daa11a3ee31cb75f5acf2e5cef1db52fd2092893b

Branch pushed to git repo; I updated commit sha1. New commits:

aa11a3eMerge branch 'develop' into t/24171/formal_set_membership_function

comment:13 Changed 5 years ago by Ralf Stephan

Status: needs_workpositive_review

comment:14 Changed 5 years ago by Volker Braun

Status: positive_reviewneeds_work

See patchbot

comment:15 Changed 5 years ago by Ralf Stephan

Actually the fails are due to the blockers #24284 and #24378 but they are not reviewed yet.

comment:16 Changed 5 years ago by Ralf Stephan

Branch: u/rws/formal_set_membership_functionu/rws/24171

comment:17 Changed 5 years ago by Ralf Stephan

Commit: aa11a3ee31cb75f5acf2e5cef1db52fd2092893bac6af264cb8beed2c7196691003ff93552a9f5b9

OK, I added junk to the branch, so what Volker means are the patchbot plugin fails. Also, the rare random fails are now happening frequently so patchbot pass depend on the blockers.


New commits:

ac6af2624171: Formal set memberhzip function

comment:18 Changed 5 years ago by Volker Braun

Dependencies: #24284 #24378

comment:19 Changed 5 years ago by Ralf Stephan

Actually the reason why #24171 fails the random expression tests is because the here introduced function is yet another function that fails that test.

comment:20 Changed 5 years ago by git

Commit: ac6af264cb8beed2c7196691003ff93552a9f5b9365ea784a37f3a99202ce2f801ce901d29d36cca

Branch pushed to git repo; I updated commit sha1. New commits:

6559c5e24282: Exclude some functions with arg restrictions from random testing
5db62d3Merge branch 'u/rws/exclude_some_functions_with_arg_restrictions_from_random_testing' of git://trac.sagemath.org/sage into tmp17
365ea7824171: exclude element_of from random testing too

comment:21 Changed 5 years ago by Ralf Stephan

Dependencies: #24284 #24378#24284 #24378 #24443

comment:22 Changed 5 years ago by Ralf Stephan

Cc: Vincent Delecroix added
Status: needs_workneeds_info

The following problem appeared: to be able to use a symbolic element_of function its arguments (1. expression, 2. set/domain) must be convertible to the symbolic ring. One doctest in symbolic/ring.pyx tests that r (the R interpreter) does not convert to symbolic. But r is in Sets() and so we cannot simply test for x in Sets() and allow conversion of x because r would then be allowed.

So we must test for all kinds of sets, e.g. ZZ in InfiniteEnumeratedSets(), RR in Fields(), RealSet(0,1) in SetsWithPartialMaps(), and Set(range(0,5)) in FiniteSets(), because we need to catch all of these but cannot use the catch-all in Sets(). Is the R interpreter really in the sets category? Is there a better catch-all?

comment:23 Changed 5 years ago by Ralf Stephan

BTW RealSet(-oo,oo) in Fields() is False which looks like a bug, right?

comment:24 in reply to:  23 ; Changed 5 years ago by Vincent Delecroix

Replying to rws:

BTW RealSet(-oo,oo) in Fields() is False which looks like a bug, right?

Not to me. RealSet(-oo,oo) or RealSet(0,1) act as a facade (like in Sets().Facade()). That is to say, it does not have any proper elements. Making it a field would be rather artificial because the operation + and * that might (or might not) exist on the elements is obtained from other parts of Sage.

comment:25 in reply to:  24 ; Changed 5 years ago by Ralf Stephan

Replying to vdelecroix:

... RealSet(-oo,oo) or RealSet(0,1) act as a facade ...

Is there an object that can act as the set of real numbers in Sage?

comment:26 in reply to:  25 ; Changed 5 years ago by Vincent Delecroix

Replying to rws:

Replying to vdelecroix:

... RealSet(-oo,oo) or RealSet(0,1) act as a facade ...

Is there an object that can act as the set of real numbers in Sage?

Very sadly, no!

My dream is:

  1. rename RealField(prec) -> RealFloatingPointField_mpfr(prec)
  2. rename RealLazyField -> RealComputableField and RLF -> RCF
  3. create a class RealField() to model (abstractly) the set of real numbers
  4. rename RR -> RFPF

The reason for 2./3. is that we want to distinguish between the field of all real numbers (denoted RR in math literature) and the field of computable numbers (which is a countable subfield). An element of RCF would simply be a computer program that gives access to the digit expansion of a number. It should provide access to all mathematical constants like pi, e, etc and most transcendental functions. A serious problem about RCF is that the equality is not decidable... but we can not avoid it.

The set of real numbers (my number 3. in the list) would not implement anything serious. It would only act as an abstract set that can be obtained as the metric completion of QQ. It could be used as a building block for more advanced structures (like manfiolds).

I put 4. apart as it is a serious backward incompatibility.reasons.

comment:27 in reply to:  26 Changed 5 years ago by Ralf Stephan

Dependencies: #24284 #24378 #24443#24284 #24378 #24456
Status: needs_infoneeds_work

comment:28 Changed 5 years ago by Ralf Stephan

Branch: u/rws/24171u/rws/24171-1

comment:29 Changed 5 years ago by Ralf Stephan

Commit: 365ea784a37f3a99202ce2f801ce901d29d36cca628f9220672280b526134311efdab819aa3f05c5
Status: needs_workneeds_review

This now depends on #24456 and has sufficiently changed to need a new review. Could you please?


New commits:

62d2d2124456: class for the field of real numbers
628f92224171: Formal set membership function

comment:30 Changed 5 years ago by Ralf Stephan

Note that we have no proper check for if something is a subset of the complexes. I ended up allowing conversion of all finite sets and (NN, ZZ, QQ, RealField, RealSet, AA) to symbolic.

comment:31 Changed 5 years ago by Ralf Stephan

Status: needs_reviewneeds_work

comment:32 Changed 18 months ago by Matthias Köppe

Branch: u/rws/24171-1u/mkoeppe/24171-1

comment:33 Changed 18 months ago by Matthias Köppe

Commit: 628f9220672280b526134311efdab819aa3f05c572565f2720115475272c030db26b1144b87377bb
Dependencies: #24284 #24378 #24456
Milestone: sage-8.2sage-9.4

rebased away from stalled dependency #24456


New commits:

72565f224171: Formal set membership function

comment:34 Changed 18 months ago by Matthias Köppe

The is_finite method added here will not be necessary any more with #31877

comment:35 Changed 18 months ago by git

Commit: 72565f2720115475272c030db26b1144b87377bb5e623bb508d45a0ac79538c93bc115562b6269e0

Branch pushed to git repo; I updated commit sha1. New commits:

4b09685RealSet: Put it in a suitable subcategory of TopologicalSpaces()
46eed0eRealSet.ambient: Change to a normal method
51c8152Merge branch 't/31877/refine_category_of_realset' into t/24171/set-membership-rebased
5e623bbRealSet.is_finite: Remove, inherited from category

comment:36 Changed 18 months ago by Matthias Köppe

Dependencies: #31877

comment:37 Changed 18 months ago by git

Commit: 5e623bb508d45a0ac79538c93bc115562b6269e07d19916c0fbf2bf76054401df372fbedde7cdbb6

Branch pushed to git repo; I updated commit sha1. New commits:

7d19916Do not use QQ.completion(oo,oo) - not implemented

comment:38 Changed 18 months ago by git

Commit: 7d19916c0fbf2bf76054401df372fbedde7cdbb65310e04bae60c574eafe491ebcea366e57513822

Branch pushed to git repo; I updated commit sha1. New commits:

9b4e22424176: check set argument of element_of()
5310e04Function_elementof: Remove use of is_Set

comment:39 Changed 18 months ago by Matthias Köppe

Status: needs_workneeds_review

This branch works now as advertised, but a careful review of this design is needed

comment:40 Changed 18 months ago by Travis Scrimshaw

We could add more support for other infinite sets later on (e.g., number fields), but this would be good for most (perhaps all?) use-cases. I think everything else is good except I don't understand why this line is added (see the diff):

oo = infinity

comment:41 Changed 18 months ago by Matthias Köppe

that's just a leftover, I'll get rid of it

comment:42 Changed 18 months ago by git

Commit: 5310e04bae60c574eafe491ebcea366e5751382243cabe82529c55b1ab3add68304f3b2b73971cba

Branch pushed to git repo; I updated commit sha1. New commits:

43cabe8Do not use QQ.completion(oo,oo) - not implemented (fixup)

comment:43 Changed 18 months ago by Travis Scrimshaw

Thank you. Green bot => positive review. Please add yourself whether you think you are an author and/or reviewer.

comment:44 Changed 18 months ago by git

Commit: 43cabe82529c55b1ab3add68304f3b2b73971cbac793fcc4f9def7070c36785603958c48cf2710b0

Branch pushed to git repo; I updated commit sha1. New commits:

c793fccFunction_elementof: Remove use of is_Set (fixup)

comment:45 Changed 18 months ago by Matthias Köppe

Reviewers: Travis ScrimshawTravis Scrimshaw, Matthias Koeppe

comment:46 Changed 18 months ago by git

Commit: c793fcc4f9def7070c36785603958c48cf2710b0a8c94cab974c8983dad63c2c6e989936984de49a

Branch pushed to git repo; I updated commit sha1. New commits:

a8c94caFunction_elementof: Add conversion to sympy

comment:47 Changed 18 months ago by Matthias Köppe

Authors: Ralf StephanRalf Stephan, Matthias Koeppe
Description: modified (diff)

comment:48 Changed 18 months ago by Travis Scrimshaw

Status: needs_reviewpositive_review

comment:49 Changed 18 months ago by Matthias Köppe

Thanks!

comment:50 Changed 18 months ago by Volker Braun

Branch: u/mkoeppe/24171-1a8c94cab974c8983dad63c2c6e989936984de49a
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.