chore_remaining_set_two_mul_eq_empty
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.
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.
uses
floor_le_ceil_div_iffchore_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$.
- The tactic block on line 3 is the result of an automated tactic search using `first | ...`. The successful branch unfolds `chore_remaining_set` and calls `simpa using floor_le_ceil_div_iff`. However, the lemma `floor_le_ceil_div_iff` is entirely unused by `simpa`; the simplifier closes the goal on its own because `Fin (2 * n)` elements are strictly less than `2 * n` by definition.
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.
/-- 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)