I was learning about set systems and hereditary systems and I noticed that they also call a hereditary system a independence system and that didn't quite make sense to me intuitively.
First recall what a set system is:
A set system denoted by, $(V , \mathcal{I})$ is a mathematical system with a ground set $V$ and a set of subsets from $V$, $\emptyset \neq \mathcal{I} \subseteq 2^V$.
A set system $(V , \mathcal{I})$ is called Hereditary (independence system) if it satisfies the following properties:
- $\emptyset \in \mathcal{I}$ (contains the empty set)
- $\forall I \in \mathcal{I} , J \subset I \implies J \in \mathcal{I}$ (subclusive)
So my question is, why is such a system called an independence system? I think the name Hereditary is self evident but saying independent is not clear to me.
This is why its not clear to me why its called independence. Intuitively, for me two things are independent if the first can be "understood" alone without the other. For example, consider two set of vectors (A and B):
$$ A = \{ x_1 = <1, 0, 0>, x_2 = <0, 1, 0> \}$$
and
$$ B = \{ x_3 = <0, 0, 1> \} $$
Since $x_3$ cannot be expressed as a linear combination of the vectors of A, then it would be reasonable to consider the two sets independent. Another way of expressing this intuition is, if we were to add $x_3$ to A, then the true cardinality (rank) of A would actually increase, because we are providing a new element that provides new information, independent of the elements already present. So A actually increases in true size.
In this sense, the definition of matroid seems to be the correct notion of independence and not a hereditary system. In my opinion its a misnomer to call a hereditary system a independence system. Am I right?
If one recalls the definition of matroid, that is what it exactly means, to add an new element it actually strictly increases the size of a set by 1. i.e.:
A matroid has the following properties:
- $\emptyset \in \mathcal{I}$ (contains the empty set)
- $\forall I \in \mathcal{I} , J \subset I \implies J \in \mathcal{I}$ (subclusive)
- $\forall I, J \in \mathcal{I}$ with $|I| = |J| + 1, \implies \exists x \in I \setminus J s.t. J \cup \{ x \} \in \mathcal{I} $
Which is a much better definition of independence (because of its 3rd property). Is my complaint of a hereditary system being called independent valid? Is it usually called independent?
The place I saw these terms used are in the following talk:
http://research.microsoft.com/apps/video/default.aspx?id=207110
and his slides can be found on that same page.
The specific slide that they use hereditary and independence interchangeably is pasted bellow:
The underlying intuition seems to be that each set in an independence system is to be thought of as an "independent set". It's not the entire system that is "independent", but the sets in it.
The axioms you quote captures the basic property of many kinds of independence, that if $\{a,b,c,d,e,f\}$ are independent, then $\{a,b,c\}$ are also independent.
In the specific case of linear independence, the additional criterion in your "matroid" also holds, but it seems reasonable enough to want to study examples where it doesn't.
For example, let $V$ be the set of all formulas of propositional logic, and call a set of formulas "independent" if no formula in it is a logical consequence of the rest. Then your third axiom doesn't hold -- as a counterexample, let $I=\{A,B\}$ (where $A$ and $B$ are different propositional variables) and $J=\{A\land B\}$. These are both independent, but we cannot select any of the formulas from $I$ and add it to $J$ without producing a dependent set!