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$ Commented 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$ Commented 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
    Commented 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$ Commented Jan 11, 2010 at 16:11
  • $\begingroup$ @Scott: That is fine. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Jan 1, 2011 at 22:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .