What are interesting families of subsets of a given set?

Motivation

The usual starting point of both Topology and Measure Theory is the definition of a family of subsets of a set $S$.

Indeed, one defines a topology on $S$ to be a family of subsets including the empty set $\emptyset$ and $S$ itself and which is closed under arbitrary unions and finite intersections. These are the open sets. (One can of course also define a topology by stipulating which are the closed sets, which are now closed under finite unions and arbitrary intersections.)

In Measure Theory one starts by defining on $S$ the notion of a $\sigma$-algebra, which is a collection of subsets again including $S$ and which is closed under complementation and countable unions, so in particular it also includes $\emptyset$ and is closed under countable intersections. The subsets in the $\sigma$-algebra are the measurable sets.

When I learnt these subjects I was always intrigued by the similarity of both definitions. This suggests other family of subsets of a set $S$ defined by demanding that both $\emptyset$ and $S$ belong to the family and that the family be closed under some operations.

Question

Are there any interesting families of subsets, other than topologies and $\sigma$-algebras, which can be defined in this way? And if so, to which areas of mathematics are they germane?

-
Note that of course an algebra of sets, rather than a $\sigma$-algebra, is also natural and important. This is already touched upon in Gjergji Zaimi's answer below. – Pete L. Clark Dec 30 2009 at 11:18
Since this site is swamped by category-theory people, I am waiting for the response: You shouldn't study set with structure, instead you should study categories. And, although I would deplore that response, I admit that there is a point there. Much of the point of defining sigma-algebra is in order to define "measurable function" ... and much of the point of defining topology is in order to define "continuous function". – Gerald Edgar Jan 31 2010 at 18:28

This fascinating essay by Gromov discusses the issue of "interesting" substructures in a very general way.

-
 Wow. Fascinating is an understatement. +1 for pointing this out. It may not be at all what I had in mind, but it's going to be a fun read! – José Figueroa-O'Farrill Dec 30 2009 at 14:02

Even families of subsets closed under unions are interesting. The following conjecture of Peter Frankl has been open for 31 years:

Let $A$ be a finite set, and let $\mathcal{F}$ be a collection of subsets of $A$, not all empty, such that the union of any two sets in $\mathcal{F}$ is also an element of $\mathcal{F}$. Then there exists an element belonging to at least half the sets in $\mathcal{F}$.

-
 Very interesting! Thanks. – José Figueroa-O'Farrill Mar 2 2010 at 23:55 Wow. At first blush this looks on the level of a Putnam problem. But then reading that Péter Frankl won the gold in the IMO (1971), I'm pretty sure he would have found a simple, clever solution if there were one! – I. J. Kennedy Jun 28 2010 at 23:45

A filter on a set $X$ is a nonempty family of nonempty subsets of $X$ which is stable under finite intersection and passage to supersets. These are extremely useful in topology, certain branches of algebra and logic: see

http://en.wikipedia.org/wiki/Filter_(mathematics)

Ultrafilters (filters which are maximal under containment) are especially fun and useful.

Note that a filter of sets is a special case of a filter on a Boolean algebra, which is essentially the order-dual notion to the notion of ideal that you get by transporting structure from Boolean rings to Boolean algebras. As some of the other answers touch on, "nice families of sets" often have to do with Boolean algebras, it seems.

-

Here is a motivating example. Let $V$ be a vector space over some field $K$, and let $S$ be a finite set of vectors from $V$. Let $I$ be the set of all subsets of $S$ that are linearly independent over $K$ (including the empty set). Then $I$ has the following three properties: (1) It includes the empty set, (2) it is closed under subsets: if $T\in I$ and $T'\subseteq T$ then $T'\in I$, and (3) if $T_1,T_2\in I$ satisfy $|T_1|<|T_2|$ then there exists a $v\in T_2$, $v\notin T_1$, such that $T_1\cup {v}\in I$.

In general, a matroid is a pair $(S,I)$ with $S$ a finite set and $I\subseteq P(S)$ ("$P$" for power set) having the above three properties.

I came across this notion in the context of information theory, in the following presentation: http://www-syscom.univ-mlv.fr/~vignat/EPFL09/abbe.pdf

Surely, information theory is not the main area of mathematics for matroids, and unfortunately I don't know what is (Wikipedia relates it to combinatorics).

-
 Finite geometries are yet another example from combinatorics: a finite projective geometry is a finite set $S$ of points together with a set of subsets of $S$ (the lines) satisfying some axioms. – unknown (google) Dec 30 2009 at 9:15 @unkonwn: Is this perhaps related to Kaplansky's result that every orthocomplemented complete modular lattice is a continuous geometry? (see jstor.org/stable/1969811 ) – José Figueroa-O'Farrill Dec 30 2009 at 14:13 @Jose: Sorry, I don't know anything at all about continuous geometry. Thanks for the link, though! – unknown (google) Dec 30 2009 at 18:30

Another (IMHO) interesting kind of structure is that of a convexity. A convexity on $X$ is a family of subsets of $X$ that is closed under arbitrary intersections, contains $\emptyset$ and $X$, and is closed under directed unions (a family is (upwards) directed iff for all $A,B$ in the family there is some $C$ in the family such that $A \cup B \subset C$). See the book "Theory of Convex Structures" by Van de Vel, e.g. There is some nice interplay with topology, and some analogical ideas, like separation axioms for convexities.

-
 Thanks for this. This is really along the lines that I was thinking. I will check this book out. – José Figueroa-O'Farrill Jan 31 2010 at 18:46

Not that I have much to add, and this is a very interesting question but maybe you forgot to mention a notion of a Borel algebra which is the sigma algebra generated by a topology.

The Borel Hierarchy might be of interest, also Meagre sets are related to topologies and also mentioned quite a bit.

Oh, and also a collection of sets that is closed under union and intersection is a distributive lattice. Birkhoff's representation theorem gives a one to one correspondence between distributive lattices and partial orders.

Similarly there is Stone's representation theorem which gives a duality between the category of Boolean algebras and the category of Stone spaces, therefore every boolean algebra is isomorphic to a field of sets.

-
 Thanks for the links! I was not aware of this. – José Figueroa-O'Farrill Dec 30 2009 at 7:51 I actually knew about Birkhoff's theorem from a different angle: that of logics in quantum mechanics and in particular Mackey's book on the Foundations of Quantum Mechanics. Borel algebras are the states in classical statistical mechanics. Quantum logics (orthocomplemented unimodular lattices), by contrast, are not Boolean. I should have made the connection! – José Figueroa-O'Farrill Dec 30 2009 at 14:06

I've seen bornologies in representation theory (in particular, some functional-analytic questions with p-adic groups). They are closed under containment and finite unions (together with a covering axiom).

-

The notion of a uniformity on a set was introduced by Weil in 1937 to formalise the notion of a uniformly continuous function. See Bourbaki's General Topology, Chapter II, Uniform structures.

-

I rather like (abstract) simplicial complexes. A simplicial complex is a family of sets which is closed under taking subsets: $X\in\mathcal{F}$ and $Y \subset X$ implies $Y\in\mathcal{F}$.

You might say that this is an uninterestingly loose condition. And it's true; you find simplicial complexes absolutely everywhere. But that just means it's good to give them a name.

And the geometric interpretation of a simplicial complex gives you a way to turn a combinatorial situation into topology. This is what Lovász did to prove Kneser's Conjecture.

-
Usually the simplexes are required to be finite subsets. – Mariano Suárez-Alvarez Feb 1 2010 at 4:05
I've heard that some people like to view simplicial complexes as subcomplexes of a really big simplex. I don't know of any explicit advantages of this viewpoint, though. – S. Carnahan Feb 1 2010 at 5:31

A ZF-algebra (as in Algebraic Set Theory) is a collection of sets closed under singleton and union.

A Grothendieck Universe (aka strongly inaccessible cardinal, aka model of set theory) is a collection of subsets which is closed under pairing, powerset, and unions indexed by its own elements. (*)

(*): Technically if you want to think of them as subsets, pairing and powerset need to be "singleton of the pair of subsets" and "singleton of the powerset of subsets", but you probably get the idea.

-
 Oh my, I seem to have missed the questioner's requirement that the entirity of S be one of the subsets in the collection. Neither of my examples has that feature. – Adam Jan 1 2010 at 20:51 Nevertheless these are interesting conditions and new to me. So thanks! – José Figueroa-O'Farrill Jan 2 2010 at 17:40

Another ultrafilter cousin is the concept of a majority space. This is a family $M$ of nonempty subsets of $X$, called the majorities, such that any superset of a majority is a majority, every subset of $X$ or its complement is a majority, and if disjoint sets are majorities, then they are complements. A strict majority space has $Y\in M\to Y^c\notin M$, and otherwise they are called weak majorities. A vast majority space is closed under finite differences in majorities. There are other various overwhelming majority concepts.

The main point is that the majority space concept generalizes the ultrafilter concept by omitting the intersection rule. Every ultrafilter on $X$ is a majority space. But there are others. For example, on a finite set, one may take the the subsets with at least half the size, and of course this situation motivates the voting theory terminology.

On an infinite set $X$, one can divide it into a finite odd number of disjoint pieces $X_i$, each carrying an ultrafilter $\mu_i$ on $X_i$, and then saying that $Y\subset X$ is a majority if for most $i$ one has $Y\cap X_i\in\mu_i$. This produces a vast majority on $X$ that is not an ultrafilter.

Eric Pacuit has investigated majority logic, and I recall that Andreas Blass has some very interesting work showing that it is consistent with ZFC that every majority space derives from ultrafilters in a simple way.

-
 Thanks for mentioning my result. It's in "Voting rules for infinite sets and Boolean algebras," currently the third item at math.lsa.umich.edu/~ablass/set.html . – Andreas Blass Jun 28 2010 at 18:52

Definable sets (in the sense of mathematical logic). That is, given a set $M$ and a collection of distinguished subsets $P_i$'s of Cartesian powers of $M$, called predicates forming a language $L$, you know that a subset it of a Cartesian power of $M$ is parameter-free definable in $L$ iff it can be generated from the distinguished ones by taking intersection, union, completement (to the relevant Cartesian power of $M$), and image under projections, and taking a product with a cartesian power of $M$. A subset is definable with parameters if you throw in also the singleton sets.

-

Let X be some set and $\mathcal{C}$ be a family of subsets of X containing X and being closed under arbitrary intersections. Such a collection is a Moore Collection. Every closure opertor gives rise to such a collection and vice versa. That is, if $cl:2^X\to 2^X$ is a function satisfy ing for all $S,T\subseteq X$ that

1. $S\subseteq T$ implies $cl(S)\subseteq cl(T)$,
2. cl(cl(S))=cl(S), and
3. $S\subseteq cl(S).$

Then the fixed points of $cl$ form a Moore collection $\mathcal{C}$ and $cl(S)=\bigcap_{C\supseteq S,C\in\mathcal{C}}C$. Every Moore collection is a complete lattice under set inclusion. If we define an operation on X as a function of the form $f:X^\Lambda\to X$ where $\Lambda$ is an arbitrary set, then every family of operations on $X$ give rise to a Moore closure containing the sets closed under this operation. It is even possible to reverse this procedure and find for each Moore closure a family of operations giving rise to it. Some characteristics of the operations can be recovered from the Moore collections. For example, if for every chain (under set containment) in a Moore collection, the union of the chain is in the Moore collection, then the Moore collection is generated by finitary operations ($\Lambda$ finite). The converse holds too.

Moore collections are extremely prevalent in Mathematics. Convex sets, closed sets, topologies and $\sigma$-algebras (on power sets),... For more information about Moore collections, see here.

-
 Best big-picture answer, in my humble opinion! – Jose Brox Jun 28 2010 at 11:09

Some people are interested in coarse structures. I am told they allow one to study the "large-scale" rather than "small-scale" structure of spaces. The Wikipedia article has references.

-