
## 8 **Martin Gebser And Joohyung Lee And Yuliya Lierler**

ΠX, we denote the set of all rules (3) of Π such that X |= B, F**. The following**
proposition states that all nonempty proper subsets of an elementary loop of ΠX
are externally supported by Π w.r.t. X.

Proposition 5 For any nondisjunctive program Π, any set X **of atoms, and any elementary loop** Y
of ΠX , X satisfies ES Π(Z**) for all nonempty proper subsets** Z of Y .

Proposition 5 tells us that any elementary loop Y of ΠX **that is unfounded by Π**
w.r.t. X is maximal among the elementary loops of ΠX **. From this, we obtain the**
following result. Theorem 1 (e)
The following condition is equivalent to each of conditions (a)–(c) in Theorem 1:
(e) X satisfies LF Π(Y ) for every set Y **of atoms such that** Y is
- a maximal elementary loop of ΠX **, or**
- **a singleton whose atom occurs in Π.**
Given a nondisjunctive program Π and a set X **of atoms, we say that a set** Y of atoms that occur in Π is *elementarily unfounded* **by Π w.r.t.** X if Y is
- an elementary loop of ΠX **that is unfounded by Π w.r.t.** X or
- **a singleton that is unfounded by Π w.r.t.** X.

7 Proposition 5 tells us that any non-singleton elementarily unfounded **set for Π**
w.r.t. X **is a maximal elementary loop of Π**X .

It is clear from the definition that every elementarily unfounded set **for Π w.r.t.** X
is an elementary loop of Π and that it is also unfounded by Π w.r.t. X**. However,**
the converse does not hold in general. For instance, {p, q} **is an elementary loop**
that is unfounded by the program w.r.t. {p, q, r}, but {p, q} is not an elementarily unfounded set w.r.t. {**p, q, r**}.

The following corollary, which follows from Proposition 5, states that **all nonempty proper subsets of an elementarily unfounded set are externally supported. It**
is essentially a reformulation of Theorem 5 from (Gebser and Schaub **2005).** Corollary 1 For any nondisjunctive program Π, any set X of atoms, and any elementarily unfounded set Y for Π w.r.t. X, X does not satisfy ES Π(Y ), but satisfies ES Π(Z**) for**
all nonempty proper subsets Z of Y .

Corollary 1 tells us that elementarily unfounded sets form an "anti-chain": one of them cannot be a proper subset of another. (On the other hand, an elementary loop may contain another elementary loop as its proper subset.) Also **it tells us** that elementarily unfounded sets are minimal among the nonempty unfounded sets occurring in Π. Interestingly, the converse also holds.

7 Elementarily unfounded sets are closely related to "active **elementary loops" defined**
in (Gebser and Schaub 2005). We further investigate this relationship in Section 2.5.

p ← q, **not r** q ← p, **not r**