Matroids and greedy algorithms - how can a singleton subset be dependent?

Question

I'm reading up on greedy algorithms (using [CRLS]) and the book discusses a connection between such algorithms and Matroids. The given definition for a Matroid is

1. $S$ is a finite set.
2. $I$ is a nonempty family of subsets of $S$, called the independent subsets of $S$, such that if $B \in I$ and $A \subseteq B$, then $A \in I$. We say that $I$ is *hereditary** if it satisfies this property. Note that the empty set is necessarily a member of $I$.
3. If $A \in I, B \in I$, and $|A| < |B|$, then there exists some element $x \in B - A$ such that $A \cup \{x\} \in I$. We say that $M$ satisfies the exchange property.

Two concrete examples given which are easier (for me) to reason about:

1. Matric matroids where the elements are vectors and the usual notion of independence is used.

2. Graphic matroid, which given a graph (V,E) treats the edges as the elements of $S$ and independence is defined in terms of acyclic subsets of $E$.

The book also makes the following definition:

Given a matroid $M=(S,I)$ call an element $x \notin A$ an extension of $A \in I$ if we can add $x$ to $A$ while preserving independence;

It then goes out to prove some theorems, one of which seems odd to me:

Corollary 16.9 (p441): Let $M =(S,I)$ be any matroid. If $x$ is an element of $S$ such that $x$ is not an extension of $\emptyset$, then $x$ is not an extension of any independent subset of $A$ of $S$.

The notion of a singleton set $\{x\}$ which is not independent (i.e. not an extension of $\emptyset$) makes no intuitive sense to me. Indeed, in the two concrete example given for matroids any singelton subset is clearly independent: a singelton set containing one vector is a linearly independent set, and a single edge of a graph cannot form cycles.

tl;dr

Can you give me an example of a matroid (not too obscure, if possible) which has an element that is not an extension of $\emptyset$?

[CRLS]: Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction to algorithms., Cambridge, MA: MIT Press (ISBN 978-0-262-03384-8/hbk; 978-0-262-53305-8/pbk). xix, 1292 p. (2009). ZBL1187.68679.

Answer 1

What you're describing is called a loop, that is, an element of the matroid that by itself has rank 0. Thinking of a representable matroid, where the elements are vectors, the zero vector is a loop- the span of the zero vector is just itself. In a graphic matroid, a loop is a graph loop (matroid terminology borrows heavily from graph theory and linear algebra), that is, an edge from a vertex to itself, since it contributes nothing to the connectivity.

Intuitively, loops are just redundant elements, so they can never add anything to the rank.

Answer 2

One possibility is to consider a vector matroid with the zero vector in the ground set, since the set $\{ 0 \}$ is linearly dependent.

Another is a graphic matroid. Then any loop $e$ in the graph gives rise to a dependent set $\{e\}$. Of course, this assumes you allow loops in your definition of graphs. Otherwise, consider a multigraph.