AFTD Auto-Formalizing Theoretical Domains

interval_family_member_depth_le_card

theoremverified

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.

  1. 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.ι`.

    lines 3–4

    uses Nat.card_eq_fintype_card

      unfold interval_family_member_depth
      rw [← Nat.card_eq_fintype_card]
  2. 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.

    line 5

    uses Finite.card_subtype_le

      exact 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

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