AFTD Auto-Formalizing Theoretical Domains

chore_remaining_set_two_mul_eq_empty

theoremverified

For every natural number $n$, the set of remaining chores after $2n$ chores have been assigned (out of $2n$ total chores) is empty.

Statement

lemma chore_remaining_set_two_mul_eq_empty (n : ℕ) :
    chore_remaining_set (2 * n) n = ∅
Source
arXiv:2611.04884, Section 4, line 729
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • chore_remaining_setFor m chores and n agents, the set V of remaining chores consists of all chores whose index is at least 2n.
  • floor_le_ceil_div_iffFor S > 0, floor(x/S) <= a <= ceil(x/S) iff x < (a+1) S and a S < x + S.

Read back from the Lean

For every natural number $n$, chore_remaining_set (2 * n) n is equal to the empty set.

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 theorem states that after $2n$ chores are assigned from a pool of $2n$ total chores, no chores remain. By definition, `chore_remaining_set (2 * n) n` filters the universal set of $\mathrm{Fin}(2n)$ for indices $e$ satisfying $2n \le e$. Because every element of $\mathrm{Fin}(2n)$ is strictly less than $2n$, no element satisfies this condition, so the resulting set is empty.

  1. chore_remaining_set (2 * n) n = ∅ automation

    Unfolding the definition of `chore_remaining_set`, the set consists of all elements $e \in \mathrm{Fin}(2n)$ such that $2n \le e$. Since by definition every element of $\mathrm{Fin}(2n)$ satisfies $e < 2n$, the condition $2n \le e$ is false for all elements in the type. The simplifier recognizes this contradiction and reduces the filtered set to the empty set `∅`. The lemma `floor_le_ceil_div_iff` is supplied by the tactic search harness but plays no role in closing the goal.

    line 3

    uses floor_le_ceil_div_iff

        chore_remaining_set (2 * n) n = ∅ := by first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff | (simp only [chore_remaining_set] at *; first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff)
floor_le_ceil_div_iff
For natural numbers $x, S, a$ with $S > 0$, $a$ lies between $\lfloor x / S \rfloor$ and $\lceil x / S \rceil$ if and only if $x < (a + 1) S$ and $a S < x + S$.

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 remaining chores set is empty when there are exactly 2n chores. -/lemma chore_remaining_set_two_mul_eq_empty (n : ℕ) :    chore_remaining_set (2 * n) n = ∅ := by first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff | (simp only [chore_remaining_set] at *; first | exact floor_le_ceil_div_iff | (apply floor_le_ceil_div_iff <;> assumption) | (apply floor_le_ceil_div_iff <;> simp_all) | simpa using floor_le_ceil_div_iff)
See it in the graphDiscuss this resultChallenge it