HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Closure operator and set of fixpoint

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
operatorfixpointandclosureset

Problem

In chapter 2.2 of

Giacobazzi, Roberto; Ranzato, Francesco, Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements, Inf. Comput. 145, No.2, 153-190 (1998). ZBL0921.68057.

it's said:


An (upper) closure operator (or simply closure) on a poset $C$ is an operator $\rho:C \to C$ monotone, idempotent and extensive (i.e.,
$\forall x \in C . x \le \rho(x)$). We denote by $uco(C)$ the set of all closure operators on the poset $C$. If $C$ is a complete lattice then each closure operator $uco(C)$ is uniquely determined by the set of its fixpoints, which is its image $\rho(C)$

Where can I find a proof of the phrase in bold?

Solution

There is an intimate connection between closure operators and complete lattices.

Given a closure operator $C$ on a set $X$, we can construct a complete lattice $L(C)$ as follows:

  • The points of the lattice are the fixpoints of $C$.



  • The meet of the lattice is $A \wedge B = A \cap B$.



  • The join of the lattice is $A \vee B = C(A \cup B)$.



Conversely, given a complete lattice $L$ of subsets of $X$, we can construct a closure operator $C:=C(L)$ on $X$ using the formula
$$ C(A) = \bigcap \{ B \in L : B \supseteq A \}. $$

It turns out that these two operators are inverses:
$C(L(C)) = C$ and $L(C(L)) = L$.

In particular, this shows that $C$ is determined by the set $L(C)$ of fixpoints, since
$$
C(A) = \bigcap \{B \in L(C) : B \supseteq A\}.
$$

(This information is taken from the sample chapter of M-solid varieties of algebras by Koppitz and Denecke.)

Context

StackExchange Computer Science Q#81240, answer score: 4

Revisions (0)

No revisions yet.