Opened 22 months ago
Last modified 3 months ago
#30263 new defect
declare_union yields wrong results
Reported by:  ghmjungmath  Owned by:  

Priority:  major  Milestone:  sage9.7 
Component:  manifolds  Keywords:  sets, union 
Cc:  egourgoulhon, tscrim  Merged in:  
Authors:  Matthias Koeppe  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/mkoeppe/declare_union_yields_wrong_results (Commits, GitHub, GitLab)  Commit:  743f11446a96c32cde3873ebe0a907cdbd0c305b 
Dependencies:  #31764  Stopgaps: 
Description (last modified by )
(for the visualization of the posets, use #31680 and install the dot2tex
package  without that package, the layout is quite misleading)
sage: M = Manifold(3, 'M') sage: U = M.open_subset('U'); V = M.open_subset('V'); W = M.open_subset('W') sage: M.declare_union(U, V, W)  TypeError Traceback (most recent call last) <ipythoninput3c7f527dcc1ea> in <module>() > 1 M.declare_union(U, V, W) TypeError: declare_union() takes 3 positional arguments but 4 were given sage: def label(element): ....: try: ....: return element._name ....: except AttributeError: ....: return '[' + ', '.join(sorted(x._name for x in element)) + ']' sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) sage: M.declare_union(U, V.union(W)) sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) sage: U.union(V).union(W) Open subset U_union_V_union_W of the 3dimensional differentiable manifold M sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) sage: U.union(V.union(W)) 3dimensional differentiable manifold M sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) # same sage: M.is_subset(U.union(V).union(W)) False
#31764 adds support for arbitrary unions. But the main issue here is the failing associativity of the union.
We fix it as follows.
When creating a union, we update the open covers of the supersets of the members, replacing the union members by the union.
Change History (23)
comment:1 Changed 19 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:2 Changed 14 months ago by
 Milestone changed from sage9.3 to sage9.4
comment:3 Changed 13 months ago by
Unions of several subsets also appear in another form  as open covers (which are merely lists of subsets and not manifold subsets in their own right). One might ask whether this could be unified as well.
comment:4 Changed 13 months ago by
 Dependencies set to #31680
 Description modified (diff)
comment:5 Changed 13 months ago by
 Description modified (diff)
An issue with the existing code is that through a sequence of declare_union
calls, it is possible to obtain a situation in which two subsets must be the same, although declare_union
makes a (not very effective) attempt to stop the user from doing so (by checking whether the two arguments are the same).
In terms of the poset of subsets that is defined by the _subsets
(and _supersets
) attributes (which is visualized by the code from #31680), this is quite problematic.
This could be solved by introducing equivalence classes of subsets  for example by keeping the _subsets
relation acyclic and introducing an _equal_sets
attribute; loops that update subsets will have to be modified.
The elements of the poset introduced in #31680 then would be equivalence classes of subsets rather than subsets.
comment:6 Changed 13 months ago by
 Description modified (diff)
comment:7 Changed 13 months ago by
 Dependencies changed from #31680 to #31680, #31718
comment:8 Changed 13 months ago by
 Branch set to u/mkoeppe/declare_union_yields_wrong_results
comment:9 Changed 13 months ago by
 Commit set to fca7e8988f5fb5175750252e9b71efea0cf9e483
Last 10 new commits:
f095988  FiniteManifoldObjectFamily.__bool__: Remove, inherited from superclass after #31717

5d87cee  Manifold{Object,Subset}FiniteFamily: Rename from FiniteManifold{Object,Subset}Family

2f2ace2  src/doc/en/reference/manifolds/manifold.rst: Add sage.manifolds.family

1aff58a  Fix up docstring markup

b922066  ManifoldSubsetFiniteFamily: If all subsets are open, include 'open' in repr

30271af  Fixup doctest

adac07a  Merge #31680

78cc27a  ManifoldSubset.open_covers: Change to generator, add optional arg 'trivial'; update uses

e026e7a  ManifoldSubset.subset_digraph: Use open_covers method

fca7e89  ManifoldSubset.declare_empty etc.

comment:10 Changed 13 months ago by
 Commit changed from fca7e8988f5fb5175750252e9b71efea0cf9e483 to 26401dd40fb6f24ac1a7a3b5945e3c312c0e002d
Branch pushed to git repo; I updated commit sha1. New commits:
215c378  ManifoldSubset.subset_{digraph,poset}: Add plots in documentation, remove # not tested

84896c4  ManifoldSubsetFiniteFamily: Use full error message in doctest

3364468  Merge #31680

6c8374e  ManifoldSubset.open_covers: Add option supersets; use it to fix is_empty

28650bc  Fix doctests

26401dd  ManifoldSubset.declare_empty: Add plot

comment:11 Changed 13 months ago by
 Commit changed from 26401dd40fb6f24ac1a7a3b5945e3c312c0e002d to ba512023a38e6aa972d1f796bb27a1d9bd9512bf
comment:12 Changed 13 months ago by
 Commit changed from ba512023a38e6aa972d1f796bb27a1d9bd9512bf to 4cf4a52e5e6b063489e18317b9dbfcfbe3b7c4bc
Branch pushed to git repo; I updated commit sha1. New commits:
9ca80d2  ManifoldSubset.{equal_subsets,supersets,superset_family}: New

55d2aa8  ManifoldSubset.{subset,superset}_digraph: New option quotient; use it for {subset,superset}_poset

4cf4a52  ManifoldSubset.declare_equal: New; use it for 1arg ManifoldSubset.declare_union

comment:13 Changed 13 months ago by
 Commit changed from 4cf4a52e5e6b063489e18317b9dbfcfbe3b7c4bc to 55a28ce3b93c44619614c85d3cb1c324d0e68a7b
Branch pushed to git repo; I updated commit sha1. New commits:
0f037ff  ManifoldSubset.intersection: Handle arbitrary intersections

9c75d18  intersection: Refactor

8d63c32  ManifoldSubset.intersection: Only pass name, latex_name to the final intersection

0867b0c  ManifoldSubset.intersection: Go through ManifoldSubsetFiniteFamily to make the order of operations canonical

de5f928  ManifoldSubset._union_subset: Factor out from ManifoldSubset.union

4698da1  ManifoldSubset.union: Handle arbitrary unions

51a89d0  ManifoldSubset.union: Add example and plots

55a28ce  ManifoldSubset.declare_union: Handle arbitrary unions

comment:14 Changed 13 months ago by
 Work issues set to rebase on #31732, #31727
comment:15 Changed 13 months ago by
 Work issues changed from rebase on #31732, #31727 to rebase on #31732, #31727, #31736
comment:16 Changed 13 months ago by
 Branch u/mkoeppe/declare_union_yields_wrong_results deleted
 Commit 55a28ce3b93c44619614c85d3cb1c324d0e68a7b deleted
 Dependencies changed from #31680, #31718 to #31764
 Work issues rebase on #31732, #31727, #31736 deleted
comment:17 Changed 13 months ago by
 Description modified (diff)
comment:18 Changed 13 months ago by
 Description modified (diff)
comment:19 Changed 13 months ago by
 Branch set to u/mkoeppe/declare_union_yields_wrong_results
comment:20 Changed 13 months ago by
 Commit set to 743f11446a96c32cde3873ebe0a907cdbd0c305b
 Description modified (diff)
Last 10 new commits:
0032bf9  ManifoldSubset.intersection: Go through ManifoldSubsetFiniteFamily to make the order of operations canonical

282010b  ManifoldSubset._union_subset: Factor out from ManifoldSubset.union

6772570  ManifoldSubset.union: Handle arbitrary unions

edfea33  ManifoldSubset.union: Add example and plots

fdd0aba  ManifoldSubset.declare_union: Handle arbitrary unions

c2f484c  src/sage/manifolds/subset.py: import itertools

a083569  ManifoldSubset._intersection_subset, _union_subset: Use declare_subset, declare_superset; fix doctest

5d41b46  Merge #31764

aceb0e8  ManifoldSubset._union_subset: Do cache store the union here

743f114  ManifoldSubset._union_subset: Update open covers

comment:21 Changed 10 months ago by
 Milestone changed from sage9.4 to sage9.5
comment:22 Changed 5 months ago by
 Milestone changed from sage9.5 to sage9.6
comment:23 Changed 3 months ago by
 Milestone changed from sage9.6 to sage9.7
Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review.