AFTD Auto-Formalizing Theoretical Domains

interval_family_member_depth_pos

theoremverified

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.

  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`).

    lines 3–5

    uses subset_rfl

      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⟩⟩
  2. 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.

    line 6

    uses Nat.card_pos

      exact 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)$)

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

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
See it in the graphDiscuss this resultChallenge it