AFTD Auto-Formalizing Theoretical Domains

card_candidate_links_le_sq

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

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.

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

    lines 5–9

    uses Finset.mem_product, Finset.mem_Ico, lt_trans, le_of_lt, le_trans

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

    lines 10–12

    uses Finset.card_le_card, Finset.card_product, Int.card_Ico, sub_zero, Int.toNat_natCast

      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
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

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