# Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds

From Wikipedia, a finite matroid $M$ is defined to be $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$, so that it satisfies

The two definitions should be equivalent. Do we need the augmentation property, for the following to be true:

a set system $(E,F)$ is nonempty and has the hereditary property, if and only if it is an accessible system, and has the Interval Property without Lower Bounds?

Without assuming the augmentation property, it is simple to see that the "only if" part is true, but I wonder if the "if"part is also true? Thanks and regards!

Note:

A set system $(E,F)$ that is nonempty and has the hereditary property is also called an independence system.

The aforementioned properties are defined as follows:

• The empty set is in $F$. (nonempty property)
• if $X \in F$, then every subset of $X$ is also in $F$. (The hereditary property)
• for all $X,Y ∈ F$ with $|X| > |Y|$, there is some $x ∈ X-Y$ such that $Y∪{x} ∈ F$. (The augmentation property)

• Every nonempty $X \in F$ contains an element $x$ such that $X-\{x\} \in F$. (I.e. $(E,F)$ is an accessible system)

• If $B, C ∈ F$ with $B ⊆ C$, then, for all $x ∈ E-C$, $C∪\{x\} ∈ F$ implies $B∪\{x\} ∈ F$. (the Interval Property without Lower Bounds)

-
I hope this is not a homework question, but if it is, I suggest you try to solve the next homework problem on your own. –  Yuval Filmus Jun 24 at 1:32
It is not homework. My self study. –  Tim Jun 24 at 1:35

Suppose that a set system $F$ is accessible and satisfies the interval property. We show that it is hereditary. Let $C = \{x_1,\ldots,x_n\}$ be any set. Without loss of generality, by accessibility we can assume that for all $t \in \{0,\ldots,n\}$, $\{x_1,\ldots,x_t\} \in F$. We show by induction that all subsets $B$ of $C$ are in $F$. If $|B| = 0$ then $B = \emptyset \in F$ (the case $t = 0$ above). Now suppose $B = \{x_{i_1}, \ldots, x_{i_k}\}$, where $i_1 < i_2 < \cdots < i_k$. By assumption, $A = \{x_{i_1},\ldots,x_{i_{k-1}}\} \in F$. Now $A \subseteq \{x_1,\ldots,x_{i_k-1}\}$ and both $\{x_1,\ldots,x_{i_k-1}\},\{x_1,\ldots,x_{i_k}\} \in F$, and so by the interval property, $B = A \cup \{x_{i_k}\} \in F$.