Editing Greedoid (section)

==Definitions==
A '''set system''' {{math|(''F'', ''E'')}} is a collection {{mvar|F}} of [[subset]]s of a ground set {{mvar|E}} (i.e. {{mvar|F}} is a subset of the [[power set]] of {{mvar|E}}). When considering a greedoid, a member of {{mvar|F}} is called a '''feasible set'''. When considering a [[matroid]], a feasible set is also known as an ''independent set''.

An '''accessible set system''' {{math|(''F'', ''E'')}} is a set system in which every nonempty feasible set {{mvar|X}} contains an element {{mvar|x}} such that <math>X \setminus \{x\}</math> is feasible. This implies that any nonempty, [[finite set|finite]], accessible set system necessarily contains the [[empty set]] ∅.<ref>Note that the accessibility property is strictly weaker than the ''hereditary property'' of a [[matroid]], which requires that ''every'' subset of an independent set be independent.</ref>

A '''greedoid''' {{math|(''F'', ''E'')}} is a finite accessible set system that satisfies the ''exchange property'':

* for all <math>X, Y \in F</math> with <math>|X|>|Y|,</math> there is some <math>x \in X \setminus Y</math> such that <math>Y \cup \{x\} \in F.</math>

(Note:  Some people reserve the term ''exchange property'' for a condition on the bases of a greedoid, and prefer to call the above condition the “augmentation property”.)

A '''basis''' of a greedoid is a maximal feasible set, meaning it is a feasible set but not contained in any other one.  A basis of a subset {{mvar|X}} of {{mvar|E}} is a maximal feasible set contained in {{mvar|X}}.

The '''rank''' of a greedoid is the size of a basis.  
By the exchange property, all bases have the same size.
Thus, the rank function is [[well defined]].  The rank of a subset {{mvar|X}} of {{mvar|E}} is the size of a basis of {{mvar|X}}. Just as with matroids, greedoids have a [[cryptomorphism]] in terms of rank functions.<ref>{{Citation|last1=Björner|first1=Anders|last2=Ziegler|first2=Günter M.|authorlink2=Günter M. Ziegler|authorlink1=Anders Björner|chapter=8. Introduction to greedoids|series=Encyclopedia of Mathematics and its Applications|volume=40|editor-last=White|editor-first=Neil|publisher=Cambridge University Press|location=Cambridge|year=1992|isbn=0-521-38165-7|pages=[https://archive.org/details/matroidapplicati0000unse/page/284 284–357]|doi=10.1017/CBO9780511662041.009|mr=1165537|zbl=0772.05026|title=Matroid Applications|chapter-url=https://archive.org/details/matroidapplicati0000unse/page/284}}
</ref>
A function <math>r:2^E \to \Z</math> is the rank function of a greedoid on the ground set {{mvar|E}} if and only if {{mvar|r}} is [[Cardinal function|subcardinal]], [[Monotonic function|monotonic]], and locally [[Submodular set function|semimodular]], that is, for any <math>X,Y \subseteq E</math> and any <math>e,f \in E</math> we have:
* '''subcardinality''': <math>r(X)\le|X|</math>
* '''monotonicity''': <math>r(X)\le r(Y)</math> whenever <math>X \subseteq Y \subseteq E</math>
*'''local semimodularity''': <math>r(X) = r(X\cup\{e,f\})</math> whenever <math>r(X) = r(X \cup \{e\}) = r(X \cup \{f\})</math>