finset_inflationary_iter_stable_at_card
An inflationary operation on subsets of a finite n-element set is stationary after n iterations.
Statement
theorem finset_inflationary_iter_stable_at_card {V : Type*} [Fintype V] [DecidableEq V] (f : Finset V → Finset V) (hf : ∀ S, S ⊆ f S) (S : Finset V) : f ((f^[Fintype.card V]) S) = (f^[Fintype.card V]) S
- Source
- Filed by the prover as a step towards another result
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- zero_forcing_finset_iter_decidesA blue set is zero forcing exactly when the executable parallel forcing process colors every vertex after at most the number of vertices…
The proof, explained
We consider the nondecreasing sequence of iterates $S_k = f^k(S)$ and split into two cases based on whether the sequence stabilizes before step $n = |V|$. If $S_i = S_{i+1}$ for some $i < n$, then $S_i$ is a fixed point of $f$, and by induction all subsequent iterates remain equal to $S_i$, so $f(S_n) = S_n$. Otherwise, each step strictly increases the cardinality of the set, which implies $|S_i| \ge i$ for all $i \le n$ by induction. In particular, $|S_n| \ge n$, forcing $S_n$ to be the universal set $V$, which is itself a fixed point of the inflationary map $f$.
The sequence of iterates $S_k = f^k(S)$ satisfies $S_{k+1} = f(S_k)$ and forms an ascending chain $S_k \subseteq S_{k+1}$.
We define the sequence $\mathrm{chain}(k) = f^k(S)$. By definition of function iteration via `Function.iterate_succ_apply'`, the next term is $\mathrm{chain}(k+1) = f(\mathrm{chain}(k))$. Since $f$ is inflationary ($S' \subseteq f(S')$ for every subset $S'$), each set is contained in the next: $\mathrm{chain}(k) \subseteq \mathrm{chain}(k+1)$.
uses
Function.iterate_succ_apply'let chain : ℕ → Finset V := fun k => (f^[k]) S have hnext (k : ℕ) : chain (k+1) = f (chain k) := by simp [chain, Function.iterate_succ_apply'] have hmono (k : ℕ) : chain k ⊆ chain (k+1) := by rw [hnext]; exact hf _
If the sequence stabilizes at some step $i < |V|$, then the iterate at step $|V|$ is a fixed point of $f$.
We split into cases based on whether there exists an index $i < |V|$ such that $\mathrm{chain}(i) = \mathrm{chain}(i+1)$. In the affirmative case, let $i$ be such an index. Since $\mathrm{chain}(i+1) = f(\mathrm{chain}(i))$, the set $\mathrm{chain}(i)$ is a fixed point of $f$. By induction on $k$, rewriting with `Nat.add_succ`, $\mathrm{chain}(i+k) = \mathrm{chain}(i)$ for all $k \ge 0$. Since $i < |V|$, linear arithmetic (`omega`) gives $|V| = i + (|V| - i)$, so $\mathrm{chain}(|V|) = \mathrm{chain}(i)$, which is a fixed point of $f$.
uses
Nat.add_succby_cases h : ∃ i < Fintype.card V, chain i = chain (i+1) · obtain ⟨i, hi, heq⟩ := h have hfix : f (chain i) = chain i := by rw [← hnext]; exact heq.symm have later : ∀ k, chain (i+k) = chain i := by intro k induction k with | zero => simp | succ k ih => rw [Nat.add_succ, hnext, ih, hfix] have hn : Fintype.card V = i + (Fintype.card V - i) := by omega change f (chain (Fintype.card V)) = chain (Fintype.card V) rw [hn, later, hfix]
In the remaining case where no early stabilization occurs, the cardinality strictly increases at each step $i < |V|$.
Assuming there is no $i < |V|$ with $\mathrm{chain}(i) = \mathrm{chain}(i+1)$, each step $i < |V|$ satisfies $\mathrm{chain}(i) \ne \mathrm{chain}(i+1)$. Combined with monotonicity, `Finset.ssubset_iff_subset_ne` shows that $\mathrm{chain}(i) \subset \mathrm{chain}(i+1)$ is a strict subset. By `Finset.card_lt_card`, strict inclusion implies $|\mathrm{chain}(i)| < |\mathrm{chain}(i+1)|$.
uses
Finset.card_lt_card,Finset.ssubset_iff_subset_ne· have hstrict (i : ℕ) (hi : i < Fintype.card V) : (chain i).card < (chain (i+1)).card := by apply Finset.card_lt_card exact (Finset.ssubset_iff_subset_ne).2 ⟨hmono i, fun heq => h ⟨i, hi, heq⟩⟩
For every $i \le |V|$, the cardinality of $\mathrm{chain}(i)$ is at least $i$.
We proceed by induction on $i$. The base case $0 \le |\mathrm{chain}(0)|$ follows from `Nat.zero_le`. In the inductive step, if $i+1 \le |V|$, then $i < |V|$ by linear arithmetic (`omega`), so the strict cardinality growth yields $|\mathrm{chain}(i)| < |\mathrm{chain}(i+1)|$. Combining this with the induction hypothesis $i \le |\mathrm{chain}(i)|$, linear integer arithmetic (`omega`) establishes $i + 1 \le |\mathrm{chain}(i+1)|$.
uses
Nat.zero_lehave hlower : ∀ i ≤ Fintype.card V, i ≤ (chain i).card := by intro i hi induction i with | zero => exact Nat.zero_le _ | succ i ih => have hp : i < Fintype.card V := by omega have hs := hstrict i hp have hprev := ih (by omega) omega
At step $|V|$, the chain reaches the universal set: $\mathrm{chain}(|V|) = \mathrm{Finset.univ}$.
By `Finset.subset_univ`, $\mathrm{chain}(|V|) \subseteq \mathrm{Finset.univ}$. From the lower bound with $i = |V|$ (using `le_rfl`), $|\mathrm{Finset.univ}| = |V| \le |\mathrm{chain}(|V|)|$. By `Finset.eq_of_subset_of_card_le`, a subset of a finite set with cardinality at least that of the ambient set must equal the ambient set.
uses
Finset.eq_of_subset_of_card_le,Finset.subset_univ,le_rflhave hu : chain (Fintype.card V) = Finset.univ := by apply Finset.eq_of_subset_of_card_le (Finset.subset_univ _) simpa using hlower (Fintype.card V) le_rfl
The universal set is a fixed point of $f$, completing the proof that $f(f^{|V|}(S)) = f^{|V|}(S)$.
The universal set satisfies $f(\mathrm{Finset.univ}) \subseteq \mathrm{Finset.univ}$ by `Finset.subset_univ`, and $\mathrm{Finset.univ} \subseteq f(\mathrm{Finset.univ})$ because $f$ is inflationary. By `Finset.Subset.antisymm`, $f(\mathrm{Finset.univ}) = \mathrm{Finset.univ}$. Since $\mathrm{chain}(|V|) = \mathrm{Finset.univ}$, this concludes the negative case.
uses
Finset.Subset.antisymm,Finset.subset_univhave hfu : f Finset.univ = Finset.univ := by apply Finset.Subset.antisymm (Finset.subset_univ _) exact hf _ change f (chain (Fintype.card V)) = chain (Fintype.card V) rw [hu, hfu]
The main theorem follows directly from the helper lemma.
The theorem `finset_inflationary_iter_stable_at_card` restates `IN800Inflationary.stable_at_card`, so directly invoking that lemma finishes the proof.
uses
IN800Inflationary.stable_at_cardexact IN800Inflationary.stable_at_card f hf S
Function.iterate_succ_apply'- The $(n+1)$-th iterate of a function $f$ applied to $x$ equals $f(f^n(x))$.
Nat.add_succ- For natural numbers $n$ and $m$, $n + (m + 1) = (n + m) + 1$.
Finset.card_lt_card- A strict subset of a finite set has strictly smaller cardinality.
Finset.ssubset_iff_subset_ne- A finite set $s$ is a strict subset of $t$ if and only if $s \subseteq t$ and $s \ne t$.
Nat.zero_le- Every natural number is greater than or equal to zero.
Finset.eq_of_subset_of_card_le- If a finite set $s$ is a subset of $t$ and $|t| \le |s|$, then $s = t$.
Finset.subset_univ- Every finite subset of a finite type is contained in the universal set.
le_rfl- The inequality relation $\le$ is reflexive: $a \le a$.
Finset.Subset.antisymm- Subset inclusion is antisymmetric: if $s_1 \subseteq s_2$ and $s_2 \subseteq s_1$, then $s_1 = s_2$.
IN800Inflationary.stable_at_card- An inflationary operation on finite subsets of an $n$-element set reaches a fixed point after $n$ iterations.
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.
set_option maxRecDepth 8192set_option maxHeartbeats 8000000namespace IN800Inflationarylemma stable_at_card {V : Type*} [Fintype V] [DecidableEq V] (f : Finset V → Finset V) (hf : ∀ S, S ⊆ f S) (S : Finset V) : f ((f^[Fintype.card V]) S) = (f^[Fintype.card V]) S := by let chain : ℕ → Finset V := fun k => (f^[k]) S have hnext (k : ℕ) : chain (k+1) = f (chain k) := by simp [chain, Function.iterate_succ_apply'] have hmono (k : ℕ) : chain k ⊆ chain (k+1) := by rw [hnext]; exact hf _ by_cases h : ∃ i < Fintype.card V, chain i = chain (i+1) · obtain ⟨i, hi, heq⟩ := h have hfix : f (chain i) = chain i := by rw [← hnext]; exact heq.symm have later : ∀ k, chain (i+k) = chain i := by intro k induction k with | zero => simp | succ k ih => rw [Nat.add_succ, hnext, ih, hfix] have hn : Fintype.card V = i + (Fintype.card V - i) := by omega change f (chain (Fintype.card V)) = chain (Fintype.card V) rw [hn, later, hfix] · have hstrict (i : ℕ) (hi : i < Fintype.card V) : (chain i).card < (chain (i+1)).card := by apply Finset.card_lt_card exact (Finset.ssubset_iff_subset_ne).2 ⟨hmono i, fun heq => h ⟨i, hi, heq⟩⟩ have hlower : ∀ i ≤ Fintype.card V, i ≤ (chain i).card := by intro i hi induction i with | zero => exact Nat.zero_le _ | succ i ih => have hp : i < Fintype.card V := by omega have hs := hstrict i hp have hprev := ih (by omega) omega have hu : chain (Fintype.card V) = Finset.univ := by apply Finset.eq_of_subset_of_card_le (Finset.subset_univ _) simpa using hlower (Fintype.card V) le_rfl have hfu : f Finset.univ = Finset.univ := by apply Finset.Subset.antisymm (Finset.subset_univ _) exact hf _ change f (chain (Fintype.card V)) = chain (Fintype.card V) rw [hu, hfu]end IN800Inflationarytheorem finset_inflationary_iter_stable_at_card {V : Type*} [Fintype V] [DecidableEq V] (f : Finset V → Finset V) (hf : ∀ S, S ⊆ f S) (S : Finset V) : f ((f^[Fintype.card V]) S) = (f^[Fintype.card V]) S := by exact IN800Inflationary.stable_at_card f hf S