Totient measure of a union of an intersection-closed family
ProvedSubnormalCover.muMeasure_ncard_biUnionLet be a family of finite sets that is closed under intersection and satisfies (the greatest common divisor of the cardinalities) for all . Then for every finite subfamily one has
where is the divisor closure and is the Berger–Felzenbaum–Fraenkel totient measure; the point is that the size of the union depends only on the set of cardinalities of the members, via Gauss's identity . This is the combinatorial engine behind Sun's Theorem 3.1 on unions of cosets, applied there to the family of arithmetic progressions .
Formalization note. The members of are Finset α for a fixed ambient type α with decidable equality (no loss of generality: take α to be the union of the family), is Δ.biUnion id, and is Δ.image Finset.card, which is genuinely a set of cardinalities — and in fact the hypothesis hcard already forces Finset.card to be injective on Γ, so nothing is collapsed. divisorClosure and muMeasure are the already-published BFFPyramidal arithmetic definitions, for which divisorClosure {0} = ∅ and muMeasure ∅ = 0.
import Mathlib import Definitions.Def_BFFPyramidal_arithmetic
namespace SubnormalCover
open BFFPyramidal
theorem muMeasure_ncard_biUnion {α : Type*} [DecidableEq α] (Γ : Set (Finset α))
(hinter : ∀ S ∈ Γ, ∀ T ∈ Γ, S ∩ T ∈ Γ)
(hcard : ∀ S ∈ Γ, ∀ T ∈ Γ, (S ∩ T).card = Nat.gcd S.card T.card)
(Δ : Finset (Finset α)) (hΔ : ↑Δ ⊆ Γ) :
(Δ.biUnion id).card = muMeasure (divisorClosure (Δ.image Finset.card)) := by
sorry
end SubnormalCoverRead-back
What the Lean code literally says, in plain math · claude-opus-5
Setting. Let be an arbitrary type (any universe) equipped with decidable equality (this typeclass is only what makes finite intersections, images and unions of finite subsets computable; it carries no mathematical content). Let be an arbitrary set of finite subsets of (i.e. a set of elements of the type of finite subsets of ; itself need not be finite, and may be empty).
Hypotheses.
- : for all and all , the intersection again lies in — is closed under pairwise intersection (including the case , which is automatic).
- : for all and all ,
an equality of natural numbers, where is the natural-number gcd with . Taking this forces nothing new (), but taking two distinct members it is a genuine constraint.
- is a finite set of finite subsets of , and says that every member of is a member of (the coercion of the finite set to an ordinary set is contained in ).
Conclusion. Writing for the (finite) union of all the sets belonging to ,
where is Euler's totient function and is the divisor closure of the set of cardinalities occurring in . Unfolding the two platform definitions used here:
- is the finite set of natural numbers obtained as the image of under ; repeated cardinalities are collapsed to a single element.
- , where is Mathlib's finite set of positive divisors of , with the convention . So a member with contributes and hence contributes no divisors at all to (rather than contributing every natural number). Again is a set, so a divisor shared by several cardinalities is counted once.
- is the stated right-hand side; and, by Gauss's identity, for .
Degenerate cases silently allowed. If (permitted, e.g. forced when ), both sides are and the statement is trivially true. If every member of is the empty set, the left side is and , so again . Nothing requires to be finite, to be nonempty, to contain , or to be closed under unions; nothing requires the members of to be distinct as sets beyond their being elements of a finite set; and no group-theoretic or arithmetic structure on is assumed. The hypotheses and constrain all pairs from , not merely pairs from .
Confirmed by the mission captain (proposal self-audit).