card_candidate_links_le_sq
For every natural number n and every finite set L of pairs of integers (i, j) satisfying 0 ≤ i < j < n, the cardinality of L is at most n * n.
Statement
theorem card_candidate_links_le_sq (n : ℕ) (L : Finset (ℤ × ℤ))
(hL : ∀ p ∈ L, 0 ≤ p.1 ∧ p.1 < p.2 ∧ p.2 < (n : ℤ)) :
L.card ≤ n * n- Source
- arXiv:2611.08570 Section 1.2.2 & Theorem 1.10
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- online_cycle_augmentation_reduction_to_tl_hitting_setLet n be a natural number, L a finite set of pairs (i, j) of integers satisfying 0 ≤ i < j < n, w a real cost function on pairs, and α a…
Read back from the Lean
For every natural number $n$ and every finite set $L$ of pairs of integers $(p_1, p_2)$, if every pair $p \in L$ satisfies $0 \le p_1 < p_2 < n$, then the cardinality of $L$ is less than or equal to $n^2$.
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
The proof bounds the finite set L by embedding it into the Cartesian product of integer intervals [0, n) × [0, n). From the condition that every pair (i, j) in L satisfies 0 ≤ i < j < n, transitivity shows that both coordinates lie in [0, n). The size of L is therefore at most the cardinality of this product, which is n * n.
The set L is a subset of the Cartesian product of integer intervals [0, n) × [0, n).
Take an arbitrary pair p = (i, j) ∈ L. The hypothesis hL guarantees 0 ≤ i, i < j, and j < n. Transitivity (lt_trans) yields i < n, meaning i ∈ [0, n). Since i < j implies i ≤ j (le_of_lt), transitivity (le_trans) with 0 ≤ i yields 0 ≤ j, so j ∈ [0, n) as well. Hence p belongs to [0, n) × [0, n).
uses
Finset.mem_product,Finset.mem_Ico,lt_trans,le_of_lt,le_transhave h_sub : L ⊆ Finset.Ico (0 : ℤ) (n : ℤ) ×ˢ Finset.Ico (0 : ℤ) (n : ℤ) := by intro p hp have ⟨h1, h2, h3⟩ := hL p hp rw [Finset.mem_product, Finset.mem_Ico, Finset.mem_Ico] exact ⟨⟨h1, lt_trans h2 h3⟩, ⟨le_trans h1 (le_of_lt h2), h3⟩⟩
The cardinality of L is at most n * n.
Since L ⊆ [0, n) × [0, n), the cardinality of L is bounded by the cardinality of the product (Finset.card_le_card). The cardinality of the Cartesian product is the product of the sizes of the two intervals (Finset.card_product). Each integer interval [0, n) has cardinality (n - 0).toNat = n (Int.card_Ico, sub_zero, Int.toNat_natCast), giving a total size of n * n.
uses
Finset.card_le_card,Finset.card_product,Int.card_Ico,sub_zero,Int.toNat_natCasthave h_card := Finset.card_le_card h_sub simp only [Finset.card_product, Int.card_Ico, sub_zero, Int.toNat_natCast] at h_card exact h_card
Finset.mem_product- An element belongs to the Cartesian product of two finite sets if and only if its first coordinate belongs to the first set and its second coordinate belongs to the second.
Finset.mem_Ico- An element x belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
lt_trans- Strict inequality is transitive: if a < b and b < c, then a < c.
le_trans- Non-strict inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_of_lt- A strict inequality implies the corresponding non-strict inequality: if a < b, then a ≤ b.
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most that of t.
Finset.card_product- The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
Int.card_Ico- The cardinality of the half-open integer interval [a, b) is the natural number value of b - a.
sub_zero- Subtracting zero leaves an element unchanged: a - 0 = a.
Int.toNat_natCast- Converting a natural number cast to the integers back to a natural number yields the original natural number.
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.
/-- Every candidate link set L on an n-vertex cycle with 0 ≤ i < j < n has cardinality at most n^2. -/theorem card_candidate_links_le_sq (n : ℕ) (L : Finset (ℤ × ℤ)) (hL : ∀ p ∈ L, 0 ≤ p.1 ∧ p.1 < p.2 ∧ p.2 < (n : ℤ)) : L.card ≤ n * n := by have h_sub : L ⊆ Finset.Ico (0 : ℤ) (n : ℤ) ×ˢ Finset.Ico (0 : ℤ) (n : ℤ) := by intro p hp have ⟨h1, h2, h3⟩ := hL p hp rw [Finset.mem_product, Finset.mem_Ico, Finset.mem_Ico] exact ⟨⟨h1, lt_trans h2 h3⟩, ⟨le_trans h1 (le_of_lt h2), h3⟩⟩ have h_card := Finset.card_le_card h_sub simp only [Finset.card_product, Int.card_Ico, sub_zero, Int.toNat_natCast] at h_card exact h_card