Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To make the title a little bit more proecise:

Let $X$ be a set and a map, $F:\mathcal{P} (X) \rightarrow \mathcal{P} (X)$ (where $\mathcal{P} (X)$ denotes the powerset of $X$), such that $A \subseteq F(A)$ and $F(A) \subseteq F(B)$ for all $\mathcal{P} (X) \ni A \subseteq B \in \mathcal{P} (X)$.

If we call a set $T \in \mathcal{P} (X)$ closed if $F(T)=T$.

How can I prove that given a function $F$ like above, a map $F':\mathcal{P} (X) \rightarrow \mathcal{P} (X)$ exists, such that all sets that are closed under $F$ are also closed under $F'$ and such that $F'$ satisfies the same properties as $F$ and additionally the property $F'(F'(A))=F'(A)$ for all $A \in \mathcal{P} (X)$ ?

Somehow $F$ would have to be iterated infinitely many times, to obtain the idempotency, but I can't figure out, how to do that.

share|improve this question
    
Are you sure you are not missing some properties of $F$ in your question? Since with the above definition (monotone and increasing) it is possible that the only closed set is $X$. At least $F(\emptyset)=\emptyset$ seems to be rasonable in most situations. The reason why I am asking is that the usual definition of preclosure (or Čech closure) operator is slightly different. See en.wikipedia.org/wiki/Preclosure_operator and en.wikipedia.org/wiki/Closure_operator –  Martin Sleziak Apr 24 '11 at 19:25
add comment

1 Answer

up vote 6 down vote accepted

One way is to do what you're thinking, that is, to try and iterate $F$ infinitely until it stabilizes, and then you'll have idempotency. This might require a transfinite iteration, so I'll explain this approach after.

A simpler approach is to let $F'(A)$ be the intersection of all the $F$-closed sets containing $A$. It's easy to check that this works. This is similar to the situation where you define a closed set in a topological space to be one whose complement is open, and then define the closure of a set $A$ to be the intersection of all closed sets containing $A$.

Now, for the iterative approach, we're going to define a transfinite sequence of functions $F_{\alpha} : \mathcal{P}(X) \to \mathcal{P}(X)$. Define $F_0 = F$, and $F_{\alpha + 1} = F\circ F_{\alpha}$. For limit ordinals $\delta$, define $F_{\delta}(A) = \bigcup _{\alpha < \delta} F_{\alpha}(A)$. For each $A$, we get an increasing transfinite sequence of subsets of $X$: $$A \subseteq F_0(A) \subseteq F_1(A) \subseteq \dots \subseteq F_{\alpha}(A) \subseteq \dots$$ This sequence must stabilize at some point, since $X$ is a set and the ordinals form a proper class. So for a given $A$, we set $F'(A)$ to be the eventual value of the transfinite sequence above.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.