patternMinor
Closure operator and set of fixpoint
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?
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:
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.)
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.