Skip to content

feat(Combinatorics/Enumerative/Bonferroni): add Bonferroni inequalities#36886

Open
Deep0Thinking wants to merge 5 commits intoleanprover-community:masterfrom
Deep0Thinking:bonferroni-inclusion-exclusion
Open

feat(Combinatorics/Enumerative/Bonferroni): add Bonferroni inequalities#36886
Deep0Thinking wants to merge 5 commits intoleanprover-community:masterfrom
Deep0Thinking:bonferroni-inclusion-exclusion

Conversation

@Deep0Thinking
Copy link
Copy Markdown
Contributor

This PR adds Bonferroni inequalities.

Main theorems:

  • Finset.indicator_biUnion_le_bonferroniIndicator_of_odd
  • Finset.bonferroniIndicator_le_indicator_biUnion_of_even
  • Finset.card_biUnion_le_bonferroniCard_of_odd
  • Finset.bonferroniCard_le_card_biUnion_of_even

Co-authored-by: Claude (Opus 4.6) [email protected]


Open in Gitpod

@github-actions github-actions bot added the new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! label Mar 20, 2026
@github-actions
Copy link
Copy Markdown

Welcome new contributor!

Thank you for contributing to Mathlib! If you haven't done so already, please review our contribution guidelines, as well as the style guide and naming conventions. In particular, we kindly remind contributors that we have guidelines regarding the use of AI when making pull requests.

We use a review queue to manage reviews. If your PR does not appear there, it is probably because it is not successfully building (i.e., it doesn't have a green checkmark), has the awaiting-author tag, or another reason described in the Lifecycle of a PR. The review dashboard has a dedicated webpage which shows whether your PR is on the review queue, and (if not), why.

If you haven't already done so, please come to https://leanprover.zulipchat.com/, introduce yourself, and mention your new PR.

Thank you again for joining our community.

@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 20, 2026

PR summary 17578798c6

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference
Mathlib.Combinatorics.Enumerative.Bonferroni (new file) 805

Declarations diff

+ bonferroniCard
+ bonferroniCard_eq_sum_bonferroniIndicator
+ bonferroniCard_le_card_biUnion_of_even
+ bonferroniIndicator
+ bonferroniIndicator_bounds
+ bonferroniIndicator_congr
+ bonferroniIndicator_eq_indicator_biUnion_of_card_le
+ bonferroniIndicator_eq_trunc_choose_sum
+ bonferroniIndicator_eq_zero
+ bonferroniIndicator_le_indicator_biUnion_of_even
+ card_biUnion_eq_bonferroniCard_of_card_le
+ card_biUnion_le_bonferroniCard_of_odd
+ card_inf'_eq_sum_indicator
+ full_choose_sum_eq_one
+ indicator_biUnion_le_bonferroniIndicator_of_odd
+ mem_iUnion_of_mem_biUnion
+ mem_truncPowerset
+ truncPowerset
+ truncPowerset_eq_filter_nonempty
+ truncPowerset_nonempty
+ truncPowerset_stabilize
+ trunc_choose_sum_bounds
+ trunc_choose_sum_eq_one_sub

You can run this locally as follows
## summary with just the declaration names:
./scripts/pr_summary/declarations_diff.sh <optional_commit>

## more verbose report:
./scripts/pr_summary/declarations_diff.sh long <optional_commit>

The doc-module for scripts/pr_summary/declarations_diff.sh contains some details about this script.


No changes to technical debt.

You can run this locally as

./scripts/reporting/technical-debt-metrics.sh pr_summary
  • The relative value is the weighted sum of the differences with weight given by the inverse of the current value of the statistic.
  • The absolute value is the relative value divided by the total sum of the inverses of the current values (i.e. the weighted average of the differences).

@github-actions github-actions bot added the t-combinatorics Combinatorics label Mar 20, 2026
@AlexeyMilovanov
Copy link
Copy Markdown
Contributor

Have you considered generalizing these inequalities to arbitrary measures in MeasureTheory?

Since you have already established the pointwise bounds for indicator functions (bonferroniIndicator_bounds), the result for general measures should follow relatively easily by integrating both sides and using the monotonicity of the integral. This generalization would make the theorems directly applicable to probability theory and other areas.

@Deep0Thinking
Copy link
Copy Markdown
Contributor Author

Have you considered generalizing these inequalities to arbitrary measures in MeasureTheory?

Since you have already established the pointwise bounds for indicator functions (bonferroniIndicator_bounds), the result for general measures should follow relatively easily by integrating both sides and using the monotonicity of the integral. This generalization would make the theorems directly applicable to probability theory and other areas.

Thanks for the suggestion! I totally agree and I will implement that as a follow-up PR which depends on this one to keep the PR clean.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! t-combinatorics Combinatorics

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants