3
$\begingroup$

I'm a beginner at matroids - so please forgive the banality of the following question.

Defining a matroid in terms of closed sets: Why is it that the intersection of two closed sets (flats) is a flat, while the union of two flats is not nesceassarily a flat? (This is relevant when defining the join and meet in the lattice of flats of a given matroid.)

Can anyone recommend a good book for getting started on matroids?

Thanks a lot.

  • 1
    http://mathoverflow.net/questions/67736/good-introductory-text-book-on-matroid-theory2011-07-24

2 Answers 2

4

Since no one else has done so, I’ll take a crack at the non-reference part of the question; whether this answer actually helps will probably depend on just what definitions you’re using.

Let $M$ be a matroid on a set $E$. The fact that the intersection of two closed sets is closed follows from the fact that the closed sets in $M$ can be defined in terms of a closure operator, i.e., a function $\sigma$ defined on subsets of $E$ that satisfies the following three conditions:

  • $X \subseteq \sigma(X)$ for all $X \subseteq E$ ($\sigma$ is expansive);
  • $\sigma(Y) \subseteq \sigma(X)$ whenever $Y \subseteq X \subseteq E$ ($\sigma$ is order-preserving); and
  • $\sigma(\sigma(X)) = \sigma(X)$ for all $X \subseteq E$ ($\sigma$ is idempotent).

The closed sets are then those $X \subseteq E$ such that $\sigma(X) = X$. Whenever a notion of closed set is defined from a closure operator in this way, it will have the property that the intersection of two closed sets is always a closed set. For suppose that $A$ and $B$ are closed sets. Then $A \cap B \subseteq \sigma(A \cap B) \subseteq \sigma(A) = A,$ and $A \cap B \subseteq \sigma(A \cap B) \subseteq \sigma(B) = B,$ so $A \cap B \subseteq \sigma(A \cap B) \subseteq A \cap B$, $A \cap B = \sigma(A \cap B)$, and $A \cap B$ is closed. Essentially the same argument shows that if $\mathscr{C}$ is any family of closed sets, then $\bigcap\mathscr{C}$ is closed. (The argument doesn’t actually use the idempotence of $\sigma$, but without idempotence there may not be much in the way of closed sets; the only one whose existence is guaranteed is $E$.)

In the case of a matroid the closure operator is the span function $\sigma_M$ defined by $\sigma_M(X) =$ $X \cup \{e \in E:Y + e\mbox{ is a circuit for some }Y \subseteq X\}$; depending on your definition of closed set, it may or may not be very obvious that a set $X$ is closed iff $\sigma_M(X) = X$.

The situation with unions is different simply because the axioms defining a closure operator aren’t strong enough to guarantee that the union of two closed sets is closed. This is most easily seen from examples. For example, let $E = \{a,b,c\}$, and say that $X \subseteq E$ is independent iff $|X| \le 2$. (Equivalently, $E$ is the only circuit.) Then $\{a\}$ and $\{b\}$ are closed, but $\{a,b\}$ is not, and this should be fairly clear no matter what definition of closed set you’re using.

  • 0
    Thanks for an excellent answer!2011-07-29
1

As Professor Scott states above, the axioms defining a general closure operator aren't strong enough to guarantee that the union of two closed sets is closed. One type of closure operator for which the union of two closed sets is closed is the Kuratowski closure operator equivalent to the notion of topology. In what follows, I will supplement Professor Scott's answer by attempting to give a complete explanation of what makes the matroid closure operator, for which the union of two closed sets does not have to be closed, different from the Kuratowski closure operator.

Following Professor Scott's answer, given a (finite) set $E$, let us define a basic closure operator to be any function $cl: 2^E \to 2^E$ such that:

  • For all $X \subseteq E$, we have that $X \subseteq cl(X)$. ($cl$ is enlarging, is expansive, has the increase property)
  • For all $X, Y \subseteq E$, $X \subseteq Y$ implies that $cl(X) \subseteq cl(Y)$. ($cl$ is monotone, is order-preserving)
  • For all $X \subseteq E$, we have that $cl[cl(X)] = cl(X)$. ($cl$ is idempotent)

Note first that both Kuratowski closure operators and matroid closure operators satisfy these three axioms. If we define a closed set to be any $X \subseteq E$ such that $cl(X)=X$, it follows that these three axioms are, by themselves, not enough to guarantee that the union of two closed sets is again closed. (Since the matroid closure operator does not have this property but satisfies these axioms.)

Let's compare the two types of closure operators and see what distinguishes them. In addition to the above three axioms, a matroid closure operator satisfies the following fourth axiom:

  • For all $X \subseteq E$, and any points $y,z \in E$, if $y \in cl(X \cup \{z\})\setminus cl(X)$, then $z \in cl(X \cup \{y\}) \setminus cl(X)$. (This is called the exchange property.)

A Kuratowski closure operator satisfies two additional axioms in addition to the three above:

  • $cl(\emptyset) = \emptyset$. (the empty set is closed, preservation of nullary union)
  • For all $X, Y \subseteq E$, we have that $cl(X \cup Y) = cl(X) \cup cl(Y)$. (preservation of binary union)

This last of the Kuratowski closure operator axioms is really crucial. As an aside, note first that it makes the monotonicity property of a basic closure operator above redundant, since, given $X \subseteq Y$, $cl(Y) = cl(X \cup (Y \setminus X) ) = cl(X) \cup cl(Y \setminus X) \supseteq cl (X) \,. $ Hence the Kuratowski closure operator axioms are usually given as only four axioms, not five.

More to the point of your question, this last Kuratwoski closure operator axiom implies what you want to show, namely that the union of any two closed sets is again closed.

Because of the idempotence axiom, we have that a set $X \subseteq E$ is closed if and only if it equals $cl(\chi)$ for some $\chi \subseteq E$ (not necessarily distinct). Namely, the idempotence axiom guarantees that the closure of any subset of $E$ is a closed set, and by definition every closed set is its own closure.

So, assuming the idempotence axiom, the union of any two closed sets being closed is equivalent to showing that, for any $X, Y \subseteq E$ such that $X = cl(\chi)$ and $Y = cl(\Upsilon)$ for some $\chi, \Upsilon \subseteq E$ (i.e. $X, Y$ are closed), then $X \cup Y = cl(Z)$ for some $Z \subseteq E$ (i.e. $X \cup Y$ is closed). Because of the last Kuratowski closure operator axiom, preservation of binary union, we can take $Z = \chi \cup \Upsilon$, since then $cl(Z) = cl(\chi \cup \Upsilon) = cl(\chi) \cup cl(\Upsilon) = X \cup Y \,. $

We actually didn't need to assume idempotence to show that $(\text{preservation of binary union}) \implies (\text{union of closed sets is closed}) \,,$ but assuming idempotence allows one to show that they are equivalent, i.e. that the converse $(\text{union of closed sets is closed}) \implies (\text{preservation of binary union}) $ also holds. Let $X, Y \subseteq E$ be arbitrary, so that possibly $X \not= cl(X)$, or $Y \not= cl(Y)$. We want to be able to show, assuming idempotence and that the union of closed sets is again closed, that $cl(X) \cup cl(Y) = cl(X \cup Y) \,.$ To show this we first need the following:

Lemma: For any $X, Y \subseteq E$, $cl(X \cup Y)$ is the "smallest" closed set containing $X \cup Y$, in the sense that $cl(W) = W$ and $W \supseteq X \cup Y$ together imply that $W \supseteq cl(X \cup Y)$.

Proof of Lemma: This property even holds for matroid closure operators, allowing one to define the lattice of closed sets, so we expect that only the three basic closure operator axioms are necessary to show this. Anyway, let $W$ be a closed set containing $X \cup Y$, in symbols: $cl(W)=W\,, \quad X \cup Y \subseteq W \,. $ Because $cl$ is monotone, this implies that $cl(X \cup Y) \subseteq cl(W) = W \,, $ and since $cl$ is enlarging, we have that $X \cup Y \subseteq cl(X \cup Y)$ (i.e. $cl(X \cup Y)$ actually contains $X \cup Y$), and because $cl$ is idempotent, we have that $cl(X \cup Y) = cl[cl(X \cup Y)]$, i.e. $cl(X \cup Y)$ is actually a closed set. Therefore, $cl(X \cup Y)$ is the smallest closed set containing $X \cup Y$. $\square$

Anyway, because the union of closed sets is again closed, and the characterization of closed sets following from idempotence, we have that $cl(X) \cup cl(Y) = cl(Z)$ for some $Z \subseteq E$. Because $cl$ is enlarging, we have that $X \subseteq cl(X)$ and $Y \subseteq cl(Y)$, so that $X \cup Y \subseteq cl(X) \cup cl(Y) = cl(Z)$ and $X \cup Y \subseteq cl(X \cup Y)$. Due to the above lemma, because $cl(Z)$ is a closed set containing $X \cup Y$, $cl(X) \cup cl(Y) = cl(Z) \supseteq cl(X \cup Y)$.

For the other direction, because $cl$ is enlarging, the second of each of these chained inclusions is true: $X \subseteq X \cup Y \subseteq cl(X \cup Y)$ and $Y \subseteq X \cup Y \subseteq cl(X \cup Y)$. By idempotence, $cl(X \cup Y)$ is a closed set, so by the lemma, $X \subseteq cl(X \cup Y) \implies cl(X \cup Y) \supseteq cl(X)$, and $Y \subseteq cl(X \cup Y) \implies cl(X \cup Y) \supseteq cl(Y)$. Putting this all together, we get: $cl(X) \subseteq cl(X \cup Y)\,, cl(Y) \subseteq cl(X \cup Y) \implies cl(X) \cup cl(Y) \subseteq cl(X \cup Y) \,. $ Therefore, assuming idempotence and thus that lemma, $cl(X \cup Y) \subseteq cl(X) \cup cl(Y)$ and $cl(X) \cup cl(Y) \subseteq cl(X \cup Y)$, i.e. $cl(X) \cup cl(Y) = cl(X \cup Y)$ for arbitrary $X, Y \subseteq E$, proving preservation of binary union. Thus, when assuming idempotence, preservation of binary union is equivalent to the union of two closed sets being closed.

So, in order to have the union of closed sets again be a closed set for matroid closure operators, we must have that the basic closure operator axioms imply preservation of binary union or that the basic closure operator axioms plus the exchange property imply preservation of binary union. As Professor Scott's counterexample shows, neither of these is true.

As an aside, even if a given, special-case matroid closure operator satisfies preservation of binary union (since matroid closure operators are idempotent, this is equivalent to the union of closed sets being closed), the closed sets of the matroid still do not necessarily have to define a topology on the set $E$, since one could still have that $cl(\emptyset) \not= \emptyset$.

A matroid is called simple if it has neither loops nor parallel elements (circuits consisting of 1 or 2 elements, respectively). Apparently (I still need to work out the proof), this is equivalent to both the empty set, and all one-element subsets, being closed (with respect to the matroid closure operator). Thus being a simple matroid is a sufficient condition for $cl(\emptyset) = \emptyset$ to hold.

I may not be reading the paper correctly, but Closure Operators in Topologies, Simple Matroids, and Rough Sets, by Feng, Lu, Yin, and Yao seems to state that the matroid being simple is both sufficient and necessary for both of the Kuratowski closure axioms to hold, i.e. the empty set being closed and the union of two closed sets being closed. I admittedly still need to work out the details of how to verify or disprove this claim. If it is true, then note that the closure operators of simple matroids would not define arbitrary topologies on finite sets, but only special topologies for which the (Steinitz) echange axioms also holds.