Monte Carlo methods in finance

From formulasearchengine
Revision as of 07:35, 21 January 2014 by en>Ent dk (Software)
Jump to navigation Jump to search

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,cl), where cl:𝒫(X)𝒫(X) (called the closure map) satisfies the following axioms. For all a,bX and A,B,CX:

  1. cl:(𝒫(X),)(𝒫(X),) is an homomorphism in the category of partial orders (monotone increasing), and dominates id (I.e. AB implies Acl(A)cl(B).) and is idempotent.
  2. Finite character: For each acl(A) there is some finite FA with acl(F).
  3. Exchange principle: If bcl(C{a})cl(C), then acl(C{b}) (and hence by monotonicity and idempotence in fact acl(C{b})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,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 cl(A) is the (topological) closure of A.) We say for A,BX that A generates B in case cl(A)=cl(B). We declare a subset independent if none of its proper subsets generate it.

For A,BX, 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 YV, 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.