What is an independent subset of a set?

Question

I am reading a book about approximation algorithms. The book first defines an independent system and an independent set of a family of subsets. The definition about the independent subset of a set confuses me. That is,

"For any $F\subseteq E$, a set $I\subseteq F$ is called a maximal independent subset of $F$ if no independent subset of $F$ contains $I$ as a proper subset."

So, what is the independent subset of $F$? Can someone shows me an example?

Thanks very much!

Answer 1

As stated in the comments, your question is about the definition of independent sets. The definition of an independent system in your book is given as:

Let $E$ be a finite set and $\mathcal I$ a family of subsets of $E$. The pair $(E,\mathcal I)$ is called an independent system if $$(I_1)\quad I\in\mathcal I\text{ and }I'\subseteq I\Rightarrow I'\in\mathcal I$$ Each subset of $\mathcal I$ is called an independent subset.

I believe this definition has a typo in it, or at the very least it is ambiguous. I think it should read (based on the definition of independent subsets of matroids and this article about independence systems):

Each element of $\mathcal I$ is called an independent subset (of E).

or equivalently,

A subset $I\subseteq E$ is called independent if $I\in \mathcal I$.

---

So $\mathcal I$ does not much more than putting a "label" on each subset of $E$, marking the difference between independent sets and non-independent sets.

So, if we have a subset $F\subseteq E$, we could ask which subsets of $F$ are independent. A maximally independent subset of $F$ is a subset $I\subseteq F$ such that $I\in \mathcal I$ (i.e. $I$ is independent) and such that no $I'\in\mathcal I$ exists with $I'\subseteq F$ for which $I\subsetneq I'$.

As an example, let: \begin{align} E&=\{1,2,3,4,5\}\\ \mathcal I&=\{\{1,2,3\},\{1,2,4\},\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{1\},\{2\},\{3\},\{4\},\varnothing\}.\end{align} You can check that $(E,\mathcal I)$ is an independent system. As an example, $\{1,2\}$ is an independent subset of $E$, since $\{1,2\}\in \mathcal I$.

Now let $F=\{2,3,4\}\subseteq E$, then $\{2,3\}$ is a maximally independent subset of $F$. It is independent because $\{2,3\}\in \mathcal I$, and it is maximal, since if we add any other element of $F$ to $\{2,3\}$, it won't be independent anymore: the only candidate is $4$, and $\{2,3,4\}\notin\mathcal I$, thus $\{2,3,4\}$ is not independent.

On the other hand, the set $\{3\}$ is an independent subset of $F$, but not maximally independent, since $\{2\}$ is a proper subset of the independent set $\{2,3\}\subseteq F$

Note that there can be multiple maximally independent subsets of $F$. In this example $\{2,4\}$ is maximally independent as well.