Challenge 9: an element of density at least in every union-closed family
DefinitionTenChallenges_Challenge_09The scaled form of Challenge 9. For a natural number , says: every nondegenerate union-closed finite family of finite sets has an element with
The rung is trivial, the rungs follow from the known bound , and is open; the statement for all is the union-closed sets conjecture.
Formalization Note. The inequality is in and the element ranges over the whole type .
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1
For a natural number , is the following proposition (it is additionally parametrised by an arbitrary, fixed universe in which the type below lives).
For every type equipped with a decidable equality (a procedure deciding whether two elements of are equal; may be finite or infinite, and is otherwise unrestricted), and for every finite family of finite subsets of (a finite set whose members are finite subsets of , without repetition), if
- is union-closed: for all finite subsets of , and imply (with allowed; nothing is required about intersections or about ), and
- is nondegenerate: and (literally equivalent to: has at least one nonempty member; is allowed, and may consist of a single set),
then there exists an element such that
Here counts members, so is the number of members of containing , divided by (natural numbers viewed as rationals; the maximum is taken among natural numbers). Under hypothesis 2 one has , so the denominator is exactly and is the fraction of members of that contain . On the right-hand side is viewed as a rational number, , so no division by zero occurs; the bound equals , which is strictly less than for every (it is for ). The inequality is non-strict ().
Quantifier structure and edge cases:
- is fixed before and are chosen; the witness may depend on and (and on ). Only existence is asserted, not uniqueness, and is not required to belong to any member of .
- For the required bound is ; since for every , the conclusion then only demands that some element of exists.
- If has no elements, its only finite subset is , so is or and hypothesis 2 fails: the statement holds vacuously for such . More generally hypothesis 2 forces to contain a nonempty set, hence to have an element.
- The hypotheses are satisfiable (e.g. for any ), so the statement is not vacuous overall.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.