AFTD Auto-Formalizing Theoretical Domains

one_layered_max_layers_of_lt

theoremverified

If m < r, then F(m, r) = 0, as no 1-layered family of r-subsets can be formed on at most m vertices.

Statement

theorem one_layered_max_layers_of_lt (m r : ℕ) (h : m < r) : one_layered_max_layers m r = 0
Source
arXiv:2611.08071 Section 2
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • one_layered_max_layersFor natural numbers m and r, one_layered_max_layers m r is the supremum (maximum) over all n ≤ m and all 1-layered families of r-subsets…
  • OneLayeredFamilyGiven a type V and a natural number r, a 1-layered family of r-subsets on V is a structure OneLayeredFamily (V : Type*) (r : ℕ) consisting…
Used by 1
  • one_layered_binomial_boundFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) in a 1-layered family of r-subsets on at most m vertices satisfies…

Read back from the Lean

For any natural numbers $m$ and $r$, if $m < r$, then one_layered_max_layers m r equals 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that F(m, r) = 0 when m < r, we show that no 1-layered family of r-subsets can exist on at most m vertices. An auxiliary lemma first proves that any 1-layered family of r-subsets on an n-element vertex set forces r ≤ n, because each layer is nonempty and consists of r-element subsets. Consequently, having at most m vertices with m < r leaves no valid families, making the set of achievable layer counts defining F(m, r) empty. The supremum of this empty set in ℕ is ⊥ = 0, which yields F(m, r) = 0.

  1. Any 1-layered family of r-subsets on an n-element set requires r ≤ n.

    Since the family has a positive number of layers (k > 0), its first layer (layer 0) exists and is nonempty by definition, so it contains some subset A ⊆ Fin n. By the definition of a 1-layered family, every set in every layer has cardinality r, so |A| = r. Moreover, because A is a subset of the n-element set Fin n, its cardinality is at most n by Finset.card_le_univ. Linear arithmetic (omega) on |A| = r and |A| ≤ n then concludes r ≤ n.

    lines 4–8

    uses Finset.card_le_univ

      obtain ⟨A, hA⟩ := F.layers_nonempty ⟨0, F.k_pos⟩
      have hcard : A.card = r := F.layers_card _ A hA
      have hle : A.card ≤ n := by
        simpa using Finset.card_le_univ A
      omega
  2. The set of achievable layer counts for 1-layered families of r-subsets on Fin n with n ≤ m is empty.

    Unfolding the definition of one_layered_max_layers, we establish that the set of layer counts is empty by showing that it cannot be nonempty (using Set.not_nonempty_iff_eq_empty). If it were nonempty, there would exist some n ≤ m and a 1-layered family of r-subsets on Fin n. By one_layered_max_layers_of_lt_aux, this family forces r ≤ n. Since n ≤ m and the theorem assumes m < r, this yields r ≤ m < r, which is an arithmetic contradiction closed by omega.

    lines 12–18

    uses Set.not_nonempty_iff_eq_empty, one_layered_max_layers_of_lt_aux

      unfold one_layered_max_layers
      have hempty : {k : ℕ | ∃ n ≤ m, ∃ F : OneLayeredFamily (Fin n) r, F.k = k} = ∅ := by
        rw [← Set.not_nonempty_iff_eq_empty]
        intro hne
        obtain ⟨k, n, hn, F, hFk⟩ := hne
        have := one_layered_max_layers_of_lt_aux n r F
        omega
  3. The supremum of the empty set in ℕ evaluates to 0.

    Rewriting the set of layer counts with the emptiness result, its supremum becomes sSup ∅, which equals ⊥ by csSup_empty. In the natural numbers, ⊥ is definitionally 0, so the proof is finished by reflexivity (rfl).

    lines 19–20

    uses csSup_empty

      rw [hempty, csSup_empty]
      rfl
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the cardinality of the whole type.
Set.not_nonempty_iff_eq_empty
A set is empty if and only if it is not nonempty.
one_layered_max_layers_of_lt_aux
Any 1-layered family of r-subsets on Fin n satisfies r ≤ n.
csSup_empty
In a conditionally complete linear order with a bottom element, the supremum of the empty set is that bottom element ⊥.

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

/-- A 1-layered family of `r`-subsets on `Fin n` forces `r ≤ n`, since some layer is nonempty. -/private theorem one_layered_max_layers_of_lt_aux (n r : ℕ) (F : OneLayeredFamily (Fin n) r) :    r ≤ n := by  obtain ⟨A, hA⟩ := F.layers_nonempty ⟨0, F.k_pos⟩  have hcard : A.card = r := F.layers_card _ A hA  have hle : A.card ≤ n := by    simpa using Finset.card_le_univ A  omega/-- The maximum number of layers F(m, r) is 0 when m < r. -/theorem one_layered_max_layers_of_lt (m r : ℕ) (h : m < r) : one_layered_max_layers m r = 0 := by  unfold one_layered_max_layers  have hempty : {k : ℕ | ∃ n ≤ m, ∃ F : OneLayeredFamily (Fin n) r, F.k = k} = ∅ := by    rw [← Set.not_nonempty_iff_eq_empty]    intro hne    obtain ⟨k, n, hn, F, hFk⟩ := hne    have := one_layered_max_layers_of_lt_aux n r F    omega  rw [hempty, csSup_empty]  rfl
See it in the graphDiscuss this resultChallenge it