Definitions

A subset of is an independent set if it is contained in some basis of the matroid.
- An extension of an independent set is an element such that is an independent set.
The basis is a maximal independent set. That is, no proper subset of the basis is contained in any other basis of .
A subset of is defined as a dependent set if it is not an independent set
A cycle is a minimal dependent set
The rank of a matroid is the number of elements of any basis. The rank of , denoted is the size of the largest independent set contained in .
The rank function is a function that maps subsets of to their rank. It satisfies the following properties
- For each
- If , then
- For any ,
A loop of a matroid with set is an element which satisfies the property that
Two elements are parallel if they satisfy

and they are not loops.
A matroid is weighted if it is associated with a weight function that assigns weights to each element such that

Matroid Definitions

Basis Definition: A matroid consists of a non-empty finite set and a non-empty collection of subsets of called the bases satisfying the following properties.
- No basis properly contains another basis
- Basis Exchange Property
  
  If and are bases and , then there is an element such that
  
  is also a basis of .
  ¹

Cycle Definition: A matroid consisting of a non-empty finite set and a collection of non empty subsets of called its cycles satisfying the properties:
- No cycle properly contains another cycle
- If and are distinct cycles each containing an element , then there exists a cycle in which does not contain .
Independent Set Definition*. A matroid consists of a non-empty finite set and a non-empty collection of subsets of called the set of independent sets satisfying the following properties
- Hereditary Property Let be an independent set. Then, is also an independent set
- Independent Set Exchange Property - If and are independent sets, where then there exists such that is an independent set.
Rank Function Definition. A matroid consists of a non-empty finite set and an integer valued function, called the rank function defined on the power set of .

(Wilson 33.4) Let be a matroid. Then contains disjoint bases if and only if for each subset .
(Wilson 33.5) Let be a matroid on . Then can be expressed as the union of independent sets if and only if for each subset
(CLRS Lemma 16.8) Let be a matroid. If is an extension of independent set , then is also an extension of .