The Lattice of Sets

Oliver Schulte Universität Potsdam Sommersemester 2004 Logik und Lernen

May 19, 2004

1 The Lattice of Sets

For the theoretical analysis of both logic programs and learning algorithms, the lattice of sets is an important fundamental mathematical structure. We have seen that logic programs can be thought of as taking as input a set of literals (typically, tuples) and returning as output a larger set. In learning theory, we will consider logic programs as defining sets of instances (e.g., classifying customers as “wealthy” or “poor”.) More general rules correspond to larger sets of instances.

So the ordering of sets by set inclusion is crucial for both logic programs and learning. Fix a set P of basic points. Subsets of P are written A, B etc. The space of all subsets of P is called the powerset of P and is denoted by 2^{P}. I write A ⊆ B to denote that A is a subset of B (i.e., x ∈ B if x ∈ A) and A ⊂ B to denote that A is a proper subset of B (i.e., A ⊆ B and there is an x ∈ B such that x ∉ A). As usual, A ∪ B denotes the union of A and B and A ∩ B denotes the intersection. Note that we can extend these operations to arbitrary sets: If A ⊆ 2^{P} is a collection of subsets of P, then ⋃ A ≡ {x ∈ P : there is an A ∈ A such that x ∈ A}. Similarly, ⋂ A ≡ {x ∈ P : x ∈ A for all A ∈ A}. The relation A ⊆ B is an ordering of the powerset 2^{P}. Clearly A ⊆ A ∪ B, and A ∩ B ⊆ A. The more interesting fact is that ∪ and ∩ are the closest approximations to A, B in the following sense.

Proposition 1 Say that C is an upper bound of A, B if A ⊆ C and B ⊆ C. Then if C is an upper bound of A, B, we have that A ∪ B ⊆ C. Thus A ∪ B is the least upper bound (gub) of A, B.

Similarly, we have that A ∩ B is the greatest lower bound (glb) of A, B. Also, these facts hold for the general operations: ⋃ A is the least upper bound of A, and ⋂ A is the greatest lower bound of A. In terms of universal algebra, ∪ is the join of A and B (written A ∨ B) and ∩ is the meet of A and B (written A ∧ B).

Set Theory Logic Program
Basic Points Literals
Sets  Sets of Literals
Operator  Logic Program

Table 1: Modelling Logic Programs as Set Operators

2 Operators and the Knaster-Tarski Theorem

We can view logic programs as transforming sets of formulas or tuples into larger sets. Abstractly, we may take tuples to be our basic points P, and then we may view a logic program as an operator τ : 2^{P} → 2^{P}. Intuitively, the operator models deriving consequences of a set of formulas A in one step. (Other interpretations are possible as well.)

If we give more formulas to a logic program as “input”, then we get out a larger set of derived consequences. Formally, this means that our set operator is monotone:

τ(A) ⊆ τ(B) whenever A ⊆ B.

When the logic program no longer derives new consequences in one step, we have reached a situation in which τ(A) = A. This is the definition of a fixpoint.

Definition 2 A fixpoint of an operator τ : 2^{P} → 2^{P} is a set A ⊆ P such that τ(A) = A.

The Knaster-Tarksi theorem asserts that every monotone set operator has a least fixed point. For logic programs, a natural idea is to take this least fixed point as the set of consequences associated with the program. To prove the theorem, we start with the observation that if A is fixed point, then τ(A) ⊆ A. Say that A is a prefixpoint if τ(A) ⊆ A. Note that there is at least one prefixpoint since τ(P) ⊆ P. Let us write P F (τ) ≡ {A : τ(A) ⊆ A} for the set of prefixpoints. We now show that the intersection of all prefixpoints is the desired least fixpoint. We begin by observing that the intersection of any set of prefixpoints is itself a prefixpoint.

Lemma 3 Let C be a collection of prefixpoints. Then ⋂ C is a prefixpoint.

Proof. We want to show that τ(⋂ C) ⊆ ⋂ C. For each C ∈ C, we have that ⋂ C ⊆C, so by monotonicity τ(⋂ C) ⊆ τ(C). Also, τ(C) ⊆ C since C is a prefixpoint. So τ(⋂ C) ⊆ C for all C ∈ C. This means that τ(⋂ C) is a lower bound for C, so τ(⋂ C) ⊆ ⋂ C since ⋂ C is the glb of C.

Theorem 4 (Knaster-Tarski) Every monotone operator τ : 2^{P} → 2^{P} has a least fixed point.

Proof. Recall that P F (τ) is the set of prefixpoints of τ, and set F ≡ ⋂ P F (τ). From the lemma, we have that τ(F) ⊆ F. Suppose for contradiction that (*) τ(F) ⊂ F. Then τ(τ(F)) ⊆ τ(F) since τ is monotone. But then τ(F) is a prefixpoint, i.e. τ(F) ∈ P F (τ). So F ⊆ τ(F) since F = ⋂ P F (τ), contradicting (*). This contradiction shows that τ(F) = F. Also, since all fixpoints A of τ are prefixpoints and thus members of P F (τ), we have that F is the least fixpoint of τ.