AFTD Auto-Formalizing Theoretical Domains

finset_inflationary_iter_stable_at_card

theoremverified

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

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

    lines 9–12

    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 _
  2. 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$.

    lines 13–23

    uses Nat.add_succ

      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]
  3. 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)|$.

    lines 24–27

    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⟩⟩
  4. 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)|$.

    lines 28–36

    uses Nat.zero_le

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

    lines 37–39

    uses Finset.eq_of_subset_of_card_le, Finset.subset_univ, le_rfl

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

    lines 40–44

    uses Finset.Subset.antisymm, Finset.subset_univ

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

    line 49

    uses IN800Inflationary.stable_at_card

      exact 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

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