interval_family_member_depth_pos
Every member of an interval family has depth at least 1, since it counts itself.
Statement
theorem interval_family_member_depth_pos {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R)
(i : F.ι) : 1 ≤ interval_family_member_depth F i- 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.
- IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
- ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
The proof, explained
By definition, the depth of an interval family member $i$ is the cardinality of the set of members whose owner shares $i$'s owner's color and whose interval contains $i$'s interval. The element $i$ itself belongs to this set because set inclusion is reflexive. Since the set is finite and nonempty, its cardinality is at least 1.
The set of family members whose owner shares the color of $i$'s owner and whose interval contains that of $i$ is nonempty.
By definition, the depth of member $i$ is the cardinality of the set of members $j$ whose owner has the same color as $i$'s owner and whose interval contains $F.\mathrm{interval}(i)$. The element $i$ itself is a witness: its owner trivially has the same color as itself, and its interval contains itself by reflexivity of set inclusion (`subset_rfl`).
uses
subset_rflunfold interval_family_member_depth have : Nonempty {j : F.ι // T.color (F.owner j) = T.color (F.owner i) ∧ F.interval i ⊆ F.interval j} := ⟨⟨i, rfl, subset_rfl⟩⟩
The depth of member $i$ is at least 1.
By `Nat.card_pos`, any nonempty finite type has cardinality at least 1 ($0 < \mathrm{card}$). Since the index type of the family is finite, the witnessing subtype is also finite and nonempty, concluding the proof.
uses
Nat.card_posexact Nat.card_pos
subset_rfl- every set is a subset of itself ($a \subseteq a$)
Nat.card_pos- a nonempty finite type has strictly positive cardinality ($0 < \mathrm{card}(\alpha)$, or equivalently $1 \le \mathrm{card}(\alpha)$)
- In Lean, for natural numbers, $1 \le n$ and $0 < n$ are definitionally equivalent, so `Nat.card_pos` (which establishes $0 < \mathrm{card}(\alpha)$) directly closes the goal $1 \le \mathrm{card}(\alpha)$.
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_pos {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) (i : F.ι) : 1 ≤ interval_family_member_depth F i := by unfold interval_family_member_depth have : Nonempty {j : F.ι // T.color (F.owner j) = T.color (F.owner i) ∧ F.interval i ⊆ F.interval j} := ⟨⟨i, rfl, subset_rfl⟩⟩ exact Nat.card_pos