# P2884: Constructing a union from non-cancelling intersections

- ID: `P2884`
- Reference: `non-cancelling-intersections-conjecture`
- Page: https://theoremdb.org/statements/P2884
- Record maturity: Reviewed problem with recorded work

## 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?

### Problem setup

- **Definition.** The coefficient mu(U) is the total coefficient of the distinct intersection U after equal terms in the inclusion-exclusion formula are collected.
- **Remark.** 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.

### What 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.

## 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. 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](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

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.

- Original intake status: 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.
- 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: 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}.

### Open directions

- **Route 1** (reported): 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](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `non-cancelling-intersections-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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. https://mathoverflow.net/questions/467258/a-conjecture-about-inclusion-exclusion
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - forum; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>Antoine Amarilli, Mikaël Monet, and Dan Suciu, “The Non-Cancelling Intersections Conjecture”. arXiv:2401.16210 (2024). Full preprint relevant to Constructing a union from non-cancelling intersections. https://arxiv.org/abs/2401.16210
   - preprint; reference source; arXiv:2401.16210, checked 2026-07-31; checked 2026-07-31
   - Source use: citation_only
   - 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.
3. <a id="reference-3"></a>Antoine Amarilli and Florent Capelli, “Tractable Circuits in Database Theory,” SIGMOD Record 53(2) (2024), 6-20. Section 5, discussion of the non-cancelling intersections conjecture, especially page 13 https://sigmodrecord.org/publications/sigmodRecord/2406/pdfs/full-issue.pdf
   - website; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.