proof

Theorem

Let $AF=(A,R)$ be an argumentation framework, let $GE$ denote its grounded extension, and let $S$ be any complete extension of $AF$. Then $GE\subseteq S.$ (Equivalently: the grounded extension is the $\subseteq$-least complete extension.)

To prove this we need to pin down how $GE$ is constructed, then show it can never overtake any complete extension.

Setup: recall $F$ and the two facts we need

Recall $F(S)=\{a\in A:a\text{ is acceptable w.r.t. }S\}$.

Fact A — complete extensions are fixed points of $F$. If $S$ is complete, then $S$ is admissible, so every $a\in S$ is acceptable w.r.t. $S$, i.e. $S\subseteq F(S)$. Completeness additionally requires that every argument acceptable w.r.t. $S$ already belongs to $S$, i.e. $F(S)\subseteq S$. Together: $S=F(S).$

Fact B (grounded extension, constructive definition). For a finitary $AF$ (every argument has finitely many attackers — Dung’s standard assumption), define the approximation sequence $F^0=\varnothing ,F^{i+1}=F(F^i)(i\ge 0),$ and set $GE={\bigcup }_{i\ge 0}{F}^i.$ This is exactly the grounded extension (the least fixed point of $F$, built by iterating $F$ from the empty set). (For non-finitary $AF$s the same construction works but must be iterated transfinitely — the proof below carries over unchanged via transfinite induction.)

Lemma 1 ($F$ is monotonic)

If $S\subseteq T$, then $F(S)\subseteq F(T)$.

Proof. Let $a\in F(S)$. Then every attacker $b$ of $a$ is countered by some $c\in S$, i.e. $c\to b$. Since $S\subseteq T$, this same $c$ is in $T$. Hence every attacker of $a$ is countered by some element of $T$, so $a\in F(T)$. $■$

Lemma 2 (the approximation sequence increases)

$F^i\subseteq F^{i+1}$ for every $i\ge 0$.

Proof. By induction on $i$.

• Base case ($i=0$): $F^0=\varnothing \subseteq F^1$ trivially — the empty set is a subset of anything.
• Step: assume $F^i\subseteq F^{i+1}$. Apply Lemma 1 to both sides: $F(F^i)\subseteq F(F^{i+1})$, i.e. $F^{i+1}\subseteq F^{i+2}$. $■$

(This is what justifies taking the union in Fact B as a well-defined, increasing approximation to $GE$.)

Main proof: $F^i\subseteq S$ for every $i$, and every complete extension $S$

Claim. For every $i\ge 0$ and every complete extension $S$: $F^i\subseteq S$.

Proof by induction on $i$.

• Base case ($i=0$): $F^0=\varnothing \subseteq S$ trivially, for any $S$.

• Inductive step: assume $F^i\subseteq S$. Since $S$ is complete, Fact A gives $S=F(S)$. Apply Lemma 1 (monotonicity) to $F^i\subseteq S$: $F(F^i)\subseteq F(S)=S.$ That is, $F^{i+1}\subseteq S$.

By induction, $F^i\subseteq S$ holds for all $i\ge 0$. $■$

Conclusion

Since $F^i\subseteq S$ for every $i$, taking the union over all $i$: $GE={\bigcup }_{i\ge 0}{F}^i\subseteq S.$

Since $S$ was an arbitrary complete extension, this holds for every complete extension of $AF$. Hence $GE\subseteq S\text{for every complete extension }S,$ i.e. the grounded extension is a subset of every complete extension — it is the $\subseteq$-least one. $■$

(A companion fact, not needed for the inclusion itself but worth knowing: $GE$ is itself shown to be conflict-free and $F(GE)=GE$, so $GE$ is a complete extension — Dung 1995. That’s what makes “the least complete extension” a coherent description rather than just a lower bound.)

Sanity check on the running example

Recall the AF from before: $A\to B$, $B\to A$, $B\to C$, $C\to C$.

• $F^0=\varnothing$.
• $F^1=F(\varnothing )$: an argument is acceptable w.r.t. $\varnothing$ only if it has no attackers at all. Here $A$ is attacked by $B$, $B$ by $A$, $C$ by $B$ and by itself — every argument has at least one attacker. So $F^1=\varnothing$.
• The sequence has already stabilized: $GE=\varnothing$.

Check against the theorem: $GE=\varnothing \subseteq \{A\}$ ✓, and $\varnothing \subseteq \{B\}$ ✓ — consistent, if unexciting (this AF is “self-defeating” enough that nothing gets bootstrapped for free; grounded is empty, and it’s trivially inside both preferred/semi-stable candidates). If you’d like, I can rerun this with a richer example where $GE$ is non-empty, to make the containment less trivial to check by hand.