12
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I suggest also the set-theory tag, since it engages with infinite combinatorics. $\endgroup$ Jan 11, 2010 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$ Jan 11, 2010 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, 2010 at 16:08
  • $\begingroup$ The lattice-theoretic keyword here is distributive lattice: see, e.g. en.wikipedia.org/wiki/Distributive_lattice . $\endgroup$ Jan 11, 2010 at 16:11
  • $\begingroup$ @Scott: That is fine. $\endgroup$ Jan 11, 2010 at 16:30

1 Answer 1

15
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ My pleasure! What a fun problem. $\endgroup$ Jan 12, 2010 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$ Jan 1, 2011 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$ Jan 1, 2011 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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