Monte Carlo methods in finance

Pregeometry, and in full combinatorial pregeometry, are essentially synonyms for "matroid". They were introduced by G.-C. Rota with the intention of providing a less "ineffably cacophonous" alternative term. Also, the term combinatorial geometry, sometimes abbreviated to geometry, was intended to replace "simple matroid". These terms are now infrequently used in the study of matroids.

In the branch of mathematical logic called model theory, infinite finitary matroids, there called "pregeometries" (and "geometries" if they are simple matroids), are used in the discussion of independence phenomena. The study of how pregeometries, geometries, and abstract closure operators influence the structure of first-order models is called geometric stability theory.

Definition

A combinatorial pregeometry (also known as a finitary matroid), is a second-order structure: $(X,{\text{cl}})\,$, where ${\text{cl}}:{\mathcal {P}}(X)\to {\mathcal {P}}(X)\,$ (called the closure map) satisfies the following axioms. For all $a,b\in X\,$ and $A,B,C\subseteq X\,$:

1. ${\text{cl}}:({\mathcal {P}}(X),\subseteq )\to ({\mathcal {P}}(X),\subseteq )\,$ is an homomorphism in the category of partial orders (monotone increasing), and dominates ${\text{id}}\,$ (I.e. $A\subseteq B\,$ implies $A\subseteq {\text{cl}}(A)\subseteq {\text{cl}}(B)\,$.) and is idempotent.
2. Finite character: For each $a\in {\text{cl}}(A)\,$ there is some finite $F\subseteq A\,$ with $a\in {\text{cl}}(F)\,$.
3. Exchange principle: If $b\in {\text{cl}}(C\cup \{a\})\smallsetminus {\text{cl}}(C)\,$, then $a\in {\text{cl}}(C\cup \{b\})$ (and hence by monotonicity and idempotence in fact $a\in {\text{cl}}(C\cup \{b\})\smallsetminus {\text{cl}}(C)\,$).

A geometry is a pregeometry where the closure map also satisfies:

1. The closure of singletons are singletons and the closure of the empty set is the empty set.

It turns out that many fundamental concepts of linear algebra – closure, independence, subspace, basis, dimension – are preserved in the framework of abstract geometries.

Let $(X,{\text{cl}})\,$ be a pregeometry. We define a topology on $X$ by declaring the closed sets to be the fixed points of the closure map (hence by idempotence and monotonicity ${\text{cl}}(A)\,$ is the (topological) closure of $A\,$.) We say for $A,B\subseteq X\,$ that $A\,$ generates $B\,$ in case ${\text{cl}}(A)={\text{cl}}(B)\,$. We declare a subset independent if none of its proper subsets generate it.

For $A,B\subseteq X\,$, if $A\,$ is independent and generates $B\,$, we will say that $A\,$ is a base for $B\,$. Equivalently, a base for $B\,$ is a minimal $B\,$-generating set, or a maximal independent Subset of $B\,$.

Examples

For example, let $V$ be a vector space over a field, and, for $Y\subseteq V$, define $cl(Y)$ to be the span of $Y$, that is, the set of linear combinations of elements of $Y$. Then the pair $(V,cl)$ is a pregeometry, as it is easy to see.

In contrast, if $X$ is a topological space and we define $cl$ to be the topological-closure function, then the pair $(X,cl)$ will not necessarily be a pregeometry, as the finite character condition (2) may fail.

References

H.H. Crapo and G.-C. Rota (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries. M.I.T. Press, Cambridge, Mass.

Pillay, Anand (1996), Geometric Stability Theory. Oxford Logic Guides. Oxford University Press.