AFTD Auto-Formalizing Theoretical Domains

order_prefix_zero

theoremverified

For any ordering bijection e of a finite type α, the prefix of length zero is empty: order_prefix e 0 = ∅.

Statement

theorem order_prefix_zero {α : Type*} [DecidableEq α] [Fintype α]
    (e : Fin (Fintype.card α) ≃ α) :
    order_prefix e 0 = ∅
Source
arXiv:2611.16207, Lemma 2
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • order_prefixGiven a finite type α with decidable equality, an ordering bijection e : Fin (Fintype.card α) ≃ α, and a natural number k, order_prefix e…
  • integer_box_completion_card_leAn admissible integer vector family with the full-box completion property has at most r(n-1) terms.
Used by 1
  • local_no_swap_of_in_coreFor any cooperative game v on a finite type α satisfying v(∅) = 0 and any ordering bijection e : Fin (Fintype.card α) ≃ α, if the marginal…

Read back from the Lean

For any type α with decidable equality and a finite type instance, and for any equivalence e from Fin (Fintype.card α) to α, order_prefix e 0 is the empty finset ∅.

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

By definition, the prefix `order_prefix e 0` is the image under `e` of all indices `j` satisfying `j < 0`. Because no natural number is strictly less than zero, this index set is empty. The image of the empty set is empty, so `order_prefix e 0 = ∅`.

  1. The prefix of length 0 of any ordering bijection e is the empty set: order_prefix e 0 = ∅. automation

    Unfolding the definition of `order_prefix`, the set `order_prefix e 0` is the image under `e` of the set of indices `{j : Fin (Fintype.card α) | (j : ℕ) < 0}`. Because no natural number is strictly less than 0, this index set is empty, and the image of the empty set is empty. The simplifier closes the goal directly (the lemma `integer_box_completion_card_le` passed to `simpa` is unused).

    line 4

    uses order_prefix, integer_box_completion_card_le

        order_prefix e 0 = ∅ := by first | exact integer_box_completion_card_le | (apply integer_box_completion_card_le <;> assumption) | (apply integer_box_completion_card_le <;> simp_all) | simpa using integer_box_completion_card_le | (simp only [order_prefix] at *; first | exact integer_box_completion_card_le | (apply integer_box_completion_card_le <;> assumption) | (apply integer_box_completion_card_le <;> simp_all) | simpa using integer_box_completion_card_le)
order_prefix
The prefix of length k under an ordering bijection e is the image under e of all indices j < k.
integer_box_completion_card_le
A theorem bounding the cardinality of an index set for integer vectors under certain divisibility conditions (present in the source tactic call as an artifact of proof search, but mathematically unused).

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

/-- The prefix of length zero of any ordering bijection is the empty set. -/theorem order_prefix_zero {α : Type*} [DecidableEq α] [Fintype α]    (e : Fin (Fintype.card α) ≃ α) :    order_prefix e 0 = ∅ := by first | exact integer_box_completion_card_le | (apply integer_box_completion_card_le <;> assumption) | (apply integer_box_completion_card_le <;> simp_all) | simpa using integer_box_completion_card_le | (simp only [order_prefix] at *; first | exact integer_box_completion_card_le | (apply integer_box_completion_card_le <;> assumption) | (apply integer_box_completion_card_le <;> simp_all) | simpa using integer_box_completion_card_le)
See it in the graphDiscuss this resultChallenge it