# Closure Matroids

How to contact me.

Base *B*,
Circuit *C*,
Closure *σ*,
Greedy *G*,
Independence *I*,
Rank *r*,
Rank *r'*.

Some of the proofs here come from memory, some come more directly from
Welsh.

A subset *A* of *S* is *closed* or a
*flat* or a *subspace* of
*M* if for all elements *x ∈ S \ A*,
*r(A ∪ {x}) = 1 + r(A)*.
If *x ∈ S* and
*A ⊆ S* and
*r(A ∪ {x}) = r(A)*
we say that *x*
*depends* on *A* and write *x ~ A*.
For a subset *A* of *S*,
let *σ(A) = {x : x ~ A}*.
We call *σ(A)* the *closure* of
*A*.

**Definition**.
A *σ-matroid M=(S,σ)*
is a finite set *S*
and a function *σ:2*^{S}→2^{S}
such that
for every pair of subsets *X,Y ⊆ S*
and for every pair of elements *x,y ∈ S*
the following four conditions
are satisfied.

(S1) *X ⊆ S(X)*;

(S2) if *Y ⊆ X*, then
*σ(Y) ⊆ σ(X)*;

(S3) *σ(X)=σ(σ(X))*; and

(S4) if *y ∉ σ(X)*
and *y ∈ σ(X ∪ {x})*, then
*x ∈ σ(X ∪ {y})*.

**Theorem 1**.
An *I*-matroid *M=(S,I)* is an *σ*-matroid.

**Proof**.

**Theorem 2**.
An *σ*-matroid *M=(S,σ)* is an *I*-matroid.

**Proof**.

**Proof of Theorem 1**.
For any *A ⊆ S*,
we define *σ(A)* as
above. Note that we have already proven the equivalence of
some of the other forms of matroids:
in particular, we have a
rank
function that
satisfies both sets of rank axioms.

(S1): If *x ∈ X*, then
*r(X ∪{x}) = r(X)*.
Thus *x ∈ σ(X)*, and *X ⊆ σ(X)*.

(S2): Suppose that *Y ⊆ X* and that
*y ∈ σ(Y)*. Suppose that
*r(X ∪ {y}) > r(X)*.
Let *V* be an independent subset of *Y*
with *|V| = r(Y)*
Let *W* be an independent
subset of *X ∪ {y}*,
with *|W| = r(X ∪ {y})*.
By (I3)', (repeated, if necessary) there is an
independent subset *Z* of *X ∪ {y}*
such that *Z ⊇ V* and with
*|Z| = r(X ∪ {y})*.
But, *y ∈ Z*, since *|Z| > r(X)*.
This, in turn, implies that *V ∪ {y}*
is independent and, hence, *y* does not depend
on *Y*. This is a contradiction. Thus,
*σ(Y) ⊆ σ(X)*.

Preparation for (S3), part 1: We first prove that if *J*
is a maximal independent subset of *X*, then
*σ(J)=σ(X)*. Since *J ⊆ X*,
applying (S2) shows that *σ(J) 7sube; σ(X)*.
Now, let *y ∈ σ(X) \ σ(J)*.
Then, *r(X ∪ {y}) = r(X)* and
*r(J ∪ {y}) = r(J) + 1*. Since
*r(J ∪ {y}) ≤ r(X ∪ {y})*,
we have a contradiction.

Preparation for (S3), part 2: We now prove that,
for any *X ⊆ S*,
*r(X) = r(σ(X))*.
Suppose *r(X) < r(σ(X))*.
Let *J* be a maximal independent subset of *X*.
Now, an application of (I3) yields an element *z ∈ σ(X) \ X*, such that *J ∪ {z}*
is independent. But then, *z ∉ σ(J)*, while we have already seen that
*σ(J) = σ(X)*.

(S3): Let *X ⊆ S* and
let *J* be a maximal independent subset
of *X*. Therefore, *r(J)=r(σ(X))* (by part 2)
and, therefore,
*σ(X) = σ(J) = σ(σ(X))* (by part 1).

(S4): Suppose that *X ⊆ S*, and that
*x,y ∈ S*.
Suppose also that *y ∈ σ(X ∪ {x}) \ σ(X)*, but
*x ∉ σ(X ∪ {y})*.
Then,

*r(X ∪ {y}) = r(X) + 1*,

*r((X ∪ {x}) ∪ {y}) = r(X ∪ {x}) ≤ r(X) + 1*,

*r((X ∪ {y}) ∪ {x}) = r(X ∪ {y}) + 1 = r(X) + 2*.

This is a contradiction. Therefore (S4) holds.

**Proof of theorem 2**.
We define a set *J*,
and then show that this set is the
collection of independent sets of a matroid.

let *J = {A ⊆ S : ∀x∈A, x∉ σ(A\{x})}*.

(I1): Obviously, *{ } ∈ J*.

(I2): Suppose that *A ∈ J*, and *B ⊆ A*, but *B ∉ J*.
Then, *B* has an element *x* such that
*x ∈ σ(B\{x})*. But then, by (S2),
*x ∈ σ(A\{x})*, contradicting the assumption
that *A ∈ J*.

*Preparation for (I3), part 1*:
*Definition*.
If *X ∈ J*,
we say that *X* is *J-independent*.

*Preparation for (I3), part 2*:
Let *A ⊆ S* and
let *X* be a maximal *J*-independent subset of
*A*. Then *σ(A)=σ(X)*.

*Proof of part 2*.
Suppose that *A* is not a subset of *s(X)*.
Then, there is an element *a ∈ A\σ(X)*.
Let *Y = X ∪{a}*.
Suppose there is some element *x ∈ Y*
such that *x ∈ σ(Y\{x})*.
Obviously, *x ≠ a*.
Therefore, *x ∈ σ(Y \ {x}) = σ((X \ {x}) ∪ {a})*, but
*x ∉ σ(X \ {x})*.
By (S4),
*a ∈ σ((X \ {x}) ∪{x}) = s(X)*.
This is a contradiction.
Therefore, *A ⊆ σ(X)*.

On the other hand, *X ⊆ A*.
Hence, *A ⊆ σ(X)*
(from the previous paragraph)
and, by (S2), *σ(X) ⊆ σ(A)*.
Applying (S2) again,
*σ(A) ⊆ σ(σ(X))* and
*σ(σ(X)) ⊆ σ(σ(A))*.
But by (S3), this reduces to
*σ(A) ⊆ σ(X)* and
*σ(X) ⊆ σ(A)*.
Thus, *σ(X) = σ(A)*.

*Preparation for (I3), part 3*:
If *X* is *J*-independent,
and *Y ⊆ X*,
*Y ≠ X*, then
*σ(Y) ⊆ σ(X)*,
*σ(Y) ≠ σ(X)*.

*Proof of part 3*.
If *x ∈ X \ Y*,
then *x ∉ σ(X \ {x})*.
By (S2), *σ(Y) ⊆ σ(X \ {x})*.
Therefore, *x ∈ σ(X) \ σ(Y)*.

*Preparation for (I3), part 4*:
If *a ∈ σ(A)*, then
*σ(A ∪ {a}) = σ(A)*.

*Proof of part 4*.
By (S1), *A ⊆ σ(A)*.
Therefore, *A ∪ {a} ⊆ σ(A)*. Applying (S2),
*σ(A ∪ {a}) ⊆ σ(σ(A))*. Applying (S3),
*σ(A ∪ {a}) ⊆ σ(A)*.
Also, *A ⊆ A ∪ {a}*, and thus, by (S2),
*σ(A) ∪ σ(A ∪ {a})*.
Therefore,
*σ(A) = σ(A ∪ {a})*.

*Preparation for (I3), part 5*:
If *A ⊆ S* and
*X,Y* are maximal
*J*-independent subsets of *A*,
then *|X| =|Y|*.

*Proof of part 5*.
Let *A ⊆ S* and let
*X,Y* be maximal
*J*-independent subsets of *A*.
Suppose that *|X| < |Y|* and that,
subject to this,
*|X ∩ Y|* is maximum.
Let *y ∈ Y \ X*,
let *Z = Y \ {y}* and let
*D = σ(Z)*.
By parts (2) and (3), *D ⊆ σ(A)*, *D ≠ σ(A)*.
Add elements
*x*_{1},x_{2},...,x_{k}
of *X* to
*Z* until
*σ(Z ∪ {x*_{1},x_{2},...,x_{k}}) = σ(A).
This process must stop, with *k ≤ |X|*,
since, by part (2), *σ(X)=σ(A)*.

Now, let *Y'=Z ∪ {x*_{k}}.
Suppose that *Y'* is not *J*-independent.
Then, for some *a ∈ Y'*,
we must have *a ∈ σ(Y' \ {a})*.
Suppose that *a = x*_{k}.
We chose *x*_{k} such that
*σ(Z ∪ {x*_{1},x_{2},...,x_{k}}) = σ(A),
but
*σ(Z ∪ {x*_{1},x_{2},...,x_{k-1}}) ≠ σ(A).
Therefore, by part (4) and (S2),
*x*_{k} ∉ σ(Z ∪ {x_{1},x_{2},...,x_{k-1}}),
and
hence, by (S2), *x*_{k} ∉ σ(Z).
Thus, *a ≠ x*_{k}.

Now, suppose *a = w*, for some *w ∈ Z*. Thus,
*w ∈ σ((Z \ {w}) ∪ {x*_{k}}).
But, *Z* is *J*-independent, and therefore,
*w ∉ Z \ {w}*.
Hence, by (S4),
*x*_{k} ∈ σ ((Z \ {w}) ∪ {w}) = σ(Z) = σ(Y \ {y}),
which was already shown to be impossible.

Therefore, *Y'* is *J*-independent and, since
*x*_{k} ∈ Y' \ Y,
*|Y'* ∩ *X| gt; |Y* ∩ *X|*,
contradicting the choice of *X* and *Y*. Thus,
*|X| = |Y|*.

(I3):
Let *X* and *Y* be *J*-independent sets,
with *|Y| = |X| + 1*.
Let *A = X ∪ Y*. Since, by part 5,
all maximum *J*-independent subsets of *A*
must have the same cardinality, *X* cannot be maximal.
Therefore, there is some maximal *J*-independent
subset, *Z*, such that *X ⊆ Z*, *x ≠ Z*.
Let *x ∈ Z \ X*. Then, by (I2), which have already proven,
*X ∪ {x}* is *J*-independent.

A note before we depart this file:
there is a third way to state matroid
independence axioms:

**Definition**.
An *I"-matroid M=(S,I")* is a finite set S and
a collection of *independent*
subsets *I"* of *S*
satisfying the following three conditions:

(I1)" *{ } ∈ I"*;

(I2)" if *X ⊆ Y* and *Y ∈ I"*, then *X ∈ I"*; and

(I3)" for every *A ⊆ S*, all maximal independent subsets of *A* have the same
cardinality.

We have just seen that an *I"*-matroid is an
*I*-matroid.
The converse is easy.

**
****Department of Mathematical Sciences**

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA**
Office: Room 237, Science & Engineering**

Phone: (561) 297-3350

Fax: (561) 297-2436

URL: http://www.math.fau.edu/locke/closure.htm

Last modified March 12, 2014, by S.C. Locke.