one_layered_max_layers_of_lt
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.
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.
uses
Finset.card_le_univobtain ⟨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 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.
uses
Set.not_nonempty_iff_eq_empty,one_layered_max_layers_of_lt_auxunfold 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
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).
uses
csSup_emptyrw [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 ⊥.
- In Lean, the conditionally complete linear order structure on ℕ defines the supremum of the empty set to be the bottom element ⊥, which definitionally equals 0.
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.
/-- 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