interval_family_member_depth_le_card
The depth of a member is at most the number of members of the family.
Statement
theorem interval_family_member_depth_le_card {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R)
(i : F.ι) : interval_family_member_depth F i ≤ Fintype.card F.ι- Source
- Sanity check of interval_family_member_depth.
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- interval_family_member_depthThe depth of a member I of an interval family: the number of members of the same color as I (the color of the owner) whose interval…
- instFintypeIntervalFamilyThe collection of intervals in an interval family is finite.
- ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
- IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
The proof, explained
The depth of a member $i$ is defined as the cardinality of the subtype of members $j \in F.\iota$ that share the color of $i$ and whose interval contains that of $i$. After rewriting the total number of members from `Fintype.card` to `Nat.card`, the inequality follows immediately from the general principle that a subtype of a finite type has at most the cardinality of the ambient type.
The inequality reduces to showing that the cardinality of a subtype of $F.\iota$ is at most the cardinality of $F.\iota$, both expressed via `Nat.card`.
Unfolding the definition of `interval_family_member_depth` expresses the member depth as the cardinality of the subtype of elements $j \in F.\iota$ whose owner has the same color as the owner of $i$ and whose interval contains the interval of $i$. Rewriting the right-hand side using `Nat.card_eq_fintype_card` replaces `Fintype.card F.ι` with `Nat.card F.ι`.
uses
Nat.card_eq_fintype_cardunfold interval_family_member_depth rw [← Nat.card_eq_fintype_card]
The member depth is at most the total number of members in the family.
The lemma `Finite.card_subtype_le` states that any subtype of a finite type has cardinality at most that of the ambient type, which directly finishes the proof.
uses
Finite.card_subtype_leexact Finite.card_subtype_le _
Nat.card_eq_fintype_card- For any finite type, its cardinality measured by `Nat.card` equals its cardinality measured by `Fintype.card`.
Finite.card_subtype_le- For any finite type, the cardinality of any subtype is at most the cardinality of the ambient type.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem interval_family_member_depth_le_card {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) (i : F.ι) : interval_family_member_depth F i ≤ Fintype.card F.ι := by unfold interval_family_member_depth rw [← Nat.card_eq_fintype_card] exact Finite.card_subtype_le _