Independence system ($(E,\mathcal{I})$)

An independence system consists of a finite set $E$ and a nonempty family $\mathcal{I}$ of subsets such that $I\in \mathcal{I}$ and $J\subseteq I$ imply $J\in \mathcal{I}$. This is the hereditary condition: deleting chosen elements keeps a selection admissible. In particular, the empty set belongs to $\mathcal{I}$. An independence system becomes a matroid when it also satisfies the matroid independence axioms for exchange. The hereditary nonmatroid greedy obstruction shows why deletion alone does not justify a greedy algorithm.