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.

  • 1
    $\begingroup$ I suggest also the set-theory tag, since it engages with infinite combinatorics. $\endgroup$ – Joel David Hamkins Jan 11 '10 at 15:23
  • 2
    $\begingroup$ There is a trivial counterexample, if A itself is not in S (and also if emptyset is not in S). Please revise the question, since the problem is interesting. $\endgroup$ – Joel David Hamkins Jan 11 '10 at 15:34
  • 6
    $\begingroup$ I believe "arbitrary unions and intersections" can be taken to include the empty union (empty set) and the empty intersection (A itself). $\endgroup$ – S. Carnahan Jan 11 '10 at 16:08
  • $\begingroup$ The lattice-theoretic keyword here is distributive lattice: see, e.g. en.wikipedia.org/wiki/Distributive_lattice . $\endgroup$ – Qiaochu Yuan Jan 11 '10 at 16:11
  • $\begingroup$ @Scott: That is fine. $\endgroup$ – Joel David Hamkins Jan 11 '10 at 16:30

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 <=.

| cite | improve this answer | |
  • $\begingroup$ My pleasure! What a fun problem. $\endgroup$ – Joel David Hamkins Jan 12 '10 at 2:45
  • $\begingroup$ Very interesting indeed. You might also find it useful to view the question in terms of the usual Galois correspondence (if you haven't done so already): For any $S \subseteq$ PowerSet(A), and $H \subseteq A^A$, define $\lambda(S)=\{f \in A^A : f(B) \subseteq B, \forall B\in S\}$ and $\rho(H)=\{B\subseteq A: f(B)\subseteq B, \forall f\in H\}$. Then, for a given set $S$, the answer to your question is yes precisely when $S = \rho\lambda(S)$; i.e. when $S$ is closed with respect to the $\rho\lambda$ closure operator. If, e.g., $S$ is a lattice of congruence relations, it need not be closed. $\endgroup$ – William DeMeo Jan 1 '11 at 22:07
  • $\begingroup$ Although the answer may be "no" when $S$ is a lattice of congruence relations (taking $f(\theta)\subseteq \theta$ to mean "$f$ respects $\theta$"), I don't think this contradicts Professor Hamkins' answer, since a congruence lattice need not be closed under unions. $\endgroup$ – William DeMeo Jan 1 '11 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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