Suppose *A* is a set and *S* is a collection of subsets closed under arbitrary unions and intersections. Can we find a collection *F* of functions from *A* to itself such that a subset *B* of *A* is in *S* if and only if $f(B) \subseteq B$ for all $f \in F$ (in other words, is *S* precisely the collection of invariant subsets under a collection of functions)?


P.S.: I don't really know what subject tag to give this, so I'm giving it "combinatorics", which seems the closest, though it is more like a question from lattice theory.



Collection of subsets closed under union and intersection
The answer is **Yes**. Furthermore, such a family can be found of size at most the cardinality of A, even when S is much larger.


The key to the solution is to realize that every such family S arises as the collection of downward-closed sets for a certain partial pre-order on A, which I shall define. (Conversely, every such order also leads to such a family.)


An interesting special case occurs when the family S is linearly ordered by inclusion. For example, one might consider the family of cuts in the rational line, that is, downward-closed subsets of Q. (I had thought briefly at first that this might be a counterexample, but after solving it, I realized a general solution was possible by moving to partial orders.)


Suppose that S is such a collection of subsets of A. Define the induced partial pre-order on A by 


* a <= b if whenever B in S and b in B, then also a in B.


It is easy to see that this relation is transitive and reflexive. 


I claim, first, that S consists of exactly the subsets of A that are downward closed in this order. It is clear that every set in S is downward closed in this order. Conversely, suppose that X is downward closed with respect to <=. For any b in X, consider the set Xb, which the intersection of all sets in S containing b as an element. This is in S. Also, Xb consists of precisely of the predecessors of b with respect to <=. So Xb subset X. Thus, X is the union of the Xb for b in X. So X is in S. 


Next, define fa(b) = a if a <= b, and otherwise fa(b) = b. Let F be the family of all such functions fa for a in A. 


Clearly, every B in S is closed under every fa, by the definition of <=. Conversely, suppose that X is closed under all fa. Thus, whenever b is in X and a <= b, then a is in X also. So X is downward closed, and hence by the claim above, X is in S. 


Incidently, the sets S are exactly the open sets in the topology on A induced by the lower cones of <=.


