What are interesting families of subsets of a given set?

Question

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?

Answer 1

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}$.

Answer 2

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

Answer 3

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.

Answer 4

How about Matroids?

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

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

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.