Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Challenge 9: an element of density at least 12−1r+2\tfrac12-\tfrac1{r+2}21​−r+21​ in every union-closed family

Definition
TenChallenges_Challenge_09

by utkuokur · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

franklten-challengesunion-closed

The scaled form of Challenge 9. For a natural number rrr, UC(r)\mathrm{UC}(r)UC(r) says: every nondegenerate union-closed finite family F\mathcal FF of finite sets has an element xxx with

δF(x) ≥ 12−1r+2.\delta_{\mathcal F}(x)\ \ge\ \frac12-\frac1{r+2}.δF​(x) ≥ 21​−r+21​.

The rung r=0r=0r=0 is trivial, the rungs r≤6r\le 6r≤6 follow from the known bound 3−52\frac{3-\sqrt5}{2}23−5​​, and r=7r=7r=7 is open; the statement for all rrr is the union-closed sets conjecture.

Formalization Note. The inequality is in Q\mathbb QQ and the element xxx ranges over the whole type UUU.

Definition code
import Definitions.Def_TenChallenges_UnionClosed

namespace TenChallenges

/-- Every nondegenerate finite union-closed family
has an element of density at least `1/2 - 1/(r + 2)`. -/
def statement_09 (r : ℕ) : Prop :=
  ∀ {U : Type*} [DecidableEq U] (F : Finset (Finset U)),
    IsUnionClosed F → Nondegenerate F →
      ∃ x, density F x ≥ (1 / 2 : ℚ) - 1 / ((r : ℚ) + 2)

end TenChallenges
Source
Ten Challenges repository, file Challenges/challenge_09.lean (commit ff14a56), https://github.com/TenChallenges/ten-challenges/blob/main/Challenges/challenge_09.lean; V. Bajpai, N. Bowler, J. Carmesin, U. Okur, 10 Scalable Challenges in Combinatorics, AI4Math @ CICM 2026, challenge 9.
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1

For a natural number r∈{0,1,2,… }r \in \{0, 1, 2, \dots\}r∈{0,1,2,…}, statement⁡09(r)\operatorname{statement}_{09}(r)statement09​(r) is the following proposition (it is additionally parametrised by an arbitrary, fixed universe in which the type UUU below lives).

For every type UUU equipped with a decidable equality (a procedure deciding whether two elements of UUU are equal; UUU may be finite or infinite, and is otherwise unrestricted), and for every finite family FFF of finite subsets of UUU (a finite set whose members are finite subsets of UUU, without repetition), if

  1. FFF is union-closed: for all finite subsets A,BA, BA,B of UUU, A∈FA \in FA∈F and B∈FB \in FB∈F imply A∪B∈FA \cup B \in FA∪B∈F (with A=BA = BA=B allowed; nothing is required about intersections or about ∅\emptyset∅), and
  2. FFF is nondegenerate: F≠∅F \neq \emptysetF=∅ and F≠{∅}F \neq \{\emptyset\}F={∅} (literally equivalent to: FFF has at least one nonempty member; ∅∈F\emptyset \in F∅∈F is allowed, and FFF may consist of a single set),

then there exists an element x∈Ux \in Ux∈U such that

dens⁡F(x)  ≥  12  −  1r+2,wheredens⁡F(x)  =  ∣{ A∈F:x∈A }∣max⁡(1, ∣F∣)  ∈  Q.\operatorname{dens}_F(x) \;\ge\; \frac{1}{2} \;-\; \frac{1}{r + 2}, \qquad\text{where}\qquad \operatorname{dens}_F(x) \;=\; \frac{\bigl|\{\, A \in F : x \in A \,\}\bigr|}{\max(1,\,|F|)} \;\in\; \mathbb{Q}.densF​(x)≥21​−r+21​,wheredensF​(x)=max(1,∣F∣)​{A∈F:x∈A}​​∈Q.

Here ∣⋅∣|\cdot|∣⋅∣ counts members, so dens⁡F(x)\operatorname{dens}_F(x)densF​(x) is the number of members of FFF containing xxx, divided by max⁡(1,∣F∣)\max(1,|F|)max(1,∣F∣) (natural numbers viewed as rationals; the maximum is taken among natural numbers). Under hypothesis 2 one has F≠∅F \neq \emptysetF=∅, so the denominator is exactly ∣F∣|F|∣F∣ and dens⁡F(x)∈[0,1]\operatorname{dens}_F(x) \in [0,1]densF​(x)∈[0,1] is the fraction of members of FFF that contain xxx. On the right-hand side rrr is viewed as a rational number, r+2≥2r + 2 \ge 2r+2≥2, so no division by zero occurs; the bound equals r2(r+2)\frac{r}{2(r+2)}2(r+2)r​, which is strictly less than 12\frac1221​ for every rrr (it is 0,16,14,310,…0, \frac16, \frac14, \frac{3}{10}, \dots0,61​,41​,103​,… for r=0,1,2,3,…r = 0, 1, 2, 3, \dotsr=0,1,2,3,…). The inequality is non-strict (≥\ge≥).

Quantifier structure and edge cases:

  • rrr is fixed before UUU and FFF are chosen; the witness xxx may depend on UUU and FFF (and on rrr). Only existence is asserted, not uniqueness, and xxx is not required to belong to any member of FFF.
  • For r=0r = 0r=0 the required bound is 000; since dens⁡F(x)≥0\operatorname{dens}_F(x) \ge 0densF​(x)≥0 for every xxx, the conclusion then only demands that some element xxx of UUU exists.
  • If UUU has no elements, its only finite subset is ∅\emptyset∅, so FFF is ∅\emptyset∅ or {∅}\{\emptyset\}{∅} and hypothesis 2 fails: the statement holds vacuously for such UUU. More generally hypothesis 2 forces FFF to contain a nonempty set, hence UUU to have an element.
  • The hypotheses are satisfiable (e.g. F={{a}}F = \{\{a\}\}F={{a}} for any a∈Ua \in Ua∈U), so the statement is not vacuous overall.
Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by utkuokur · Nov 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me