[#P2884] Constructing a union from non-cancelling intersections

Problem. Let \(\mathcal F=\{S_1,\ldots,S_n\}\) be a finite family of pairwise inclusion-incomparable finite sets. For each nonempty \(T\subseteq\{1,\ldots,n\}\), put \(S_T=\bigcap_{i\in T}S_i\). For each distinct set \(U\) among the \(S_T\), define \(\mu(U)=\sum_{T:S_T=U}(-1)^{|T|+1}\), and call \(U\) non-cancelling when \(\mu(U)\ne0\). Starting with the non-cancelling intersections, one may form \(A\mathbin{\dot\cup}B=A\cup B\) only when \(A\cap B=\varnothing\), and \(A\mathbin{\dot\setminus}B=A\setminus B\) only when \(B\subseteq A\). Can \(\bigcup_{i=1}^n S_i\) always be obtained by finitely many such operations?

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

The conjecture has a natural finite search at each ground-set size. Minimal counterexample searches, canonical intersection lattices, and expression certificates are compact artifacts that can be reused across algebraic and database-theoretic approaches.

2Definitions

Definition 1 (The coefficient mu(U). The coefficient mu(U) is the total coefficient of the distinct intersection U after equal terms in the inclusion-exclusion formula are collected.

Definition 2 (The two partial operations are disjoint union and subset complement; an expression). The two partial operations are disjoint union and subset complement; an expression is valid only when every operation node satisfies its stated disjointness or containment condition.

3What counts as a solution

Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.
A counterexample must list the sets, compute every collected coefficient mu(U), and include a complete finite invariant or exhaustive certificate excluding all valid expression trees.

1Status

Saved packet · July 31, 2026

What counts as a solution

Saved packet status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.^[1] Relevance to this problem For non cancelling intersections conjecture, pins the dated research frontier: UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. Give a valid expression for every finite incomparable. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. A complete resolution must satisfy this condition: Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists. Open full record →
Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.^[1] Relevance to this problem For Constructing a union from non-cancelling intersections, record non-cancelling-intersections-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.

On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for question 467258; all mathematical comments were checked for proposed counterexamples and clarifications.
Amarilli, Monet, and Suciu, arXiv:2401.16210, is the primary source for the exact conjecture. Version 1 gives a Boolean-lattice reformulation and partial cases while retaining the general statement as a conjecture.
A 2024 SIGMOD Record survey says the associated database-circuit question still hinges on the unproven non-cancelling intersections conjecture; searches through 2026 located no superseding proof.
A TheoremDB search for non-cancelling intersections, dot-algebra, inclusion-exclusion coefficients, and the Boolean-lattice formulation found no duplicate.

Recorded example 1. For S1={a,b,d}, S2={a,b,c,e}, and S3={a,c,f}, collecting equal intersections cancels {a}; the remaining intersections can still be combined by valid subset complements and disjoint unions to obtain {a,b,c,d,e,f}.

Computational notes

The primary note reports brute-force success on large collections of finite examples but presents that evidence only as support for the conjecture.

How the 2 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemConstructing a union from non-cancelling intersections

All 1 recorded relations between these records and the problem

Resolve the stated acceptance condition addresses Current status and unresolved remainder

2See also

Plane tilings by every five-cell lattice animalcombinatorics
Cycle Double Cover Conjecturecombinatorics
Sabidussi's Compatibility Conjecturecombinatorics

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Constructing a union from non-cancelling intersections.” TheoremDB. P2884. Problem statement; statement text SHA-256 426b8005bf4946f5cf1ca50a7614478038fa51b758df96a7d7afc7bb42180e06. https://theoremdb.org/statement/?ref=P2884

BibTeX

@misc{theoremdb-problem-426b8005bf4946f5cf1ca50a7614478038fa51b758df96a7d7afc7bb42180e06,
  title = {{Constructing a union from non-cancelling intersections}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 426b8005bf4946f5cf1ca50a7614478038fa51b758df96a7d7afc7bb42180e06},
  url = {https://theoremdb.org/statement/?ref=P2884}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net^[1], current as of July 31, 2026.

1Lean verification

1References

Packet source. MathOverflow: A conjecture about inclusion-exclusion. Question 467258 and all visible comments, checked through the Stack Exchange API on 2026-07-27. Question 467258 and all visible comments, checked through the Stack Exchange API on 2026-07-27. ↗forum · discovery source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Constructing a union from non-cancelling intersections: UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Source named by the research packet.
Antoine Amarilli, Mikaël Monet, and Dan Suciu, “The Non-Cancelling Intersections Conjecture”. arXiv:2401.16210 (2024). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:2401.16210, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Also cited at Full preprint relevant to Constructing a union from non-cancelling intersections.Source used to assess the problem's recorded status.For Constructing a union from non-cancelling intersections: UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.
Antoine Amarilli and Florent Capelli, “Tractable Circuits in Database Theory,” SIGMOD Record 53(2) (2024), 6-20. Status evidence identified in the source record and checked at the linked publication. ↗website · primary source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Also cited at Section 5, discussion of the non-cancelling intersections conjecture, especially page 13.Source used to assess the problem's recorded status.For Constructing a union from non-cancelling intersections, this source records a 2024 survey use of the conjecture and its unresolved role in probabilistic-query provenance.

This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.

[#P2884] Constructing a union from non-cancelling intersections

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance