Editing Pregeometry (model theory)

{{Short description|Formulation of matroids using closure operators}}
{{for|pregeometry in physics|pregeometry (physics)}}

'''Pregeometry''', and in full '''combinatorial pregeometry''', are essentially synonyms for "[[matroid]]". They were introduced by [[Gian-Carlo 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.

It turns out that many fundamental concepts of [[linear algebra]] – closure, independence, subspace, basis, dimension – are available in the general framework of pregeometries.

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 operator]]s influence the structure of [[first-order logic|first-order]] models is called [[Stable theory#Geometric stability theory|geometric stability theory]].

== Motivation ==
If <math>V</math> is a [[vector space]] over some field and <math>A\subseteq V</math>, we define <math>\text{cl}(A)</math> to be the set of all [[linear combination]]s of vectors from <math>A</math>, also known as the [[linear span|span]] of <math>A</math>. Then we have <math>A\subseteq \text{cl}(A)</math> and <math>\text{cl}(\text{cl}(A))=\text{cl}(A)</math> and <math>A\subseteq B \Rightarrow \text{cl}(A)\subseteq\text{cl}(B)</math>. The [[Steinitz exchange lemma]] is equivalent to the statement: if <math>b\in\text{cl}(A\cup\{c\})\smallsetminus\text{cl}(A)</math>, then <math>c\in\text{cl}(A\cup\{b\}).</math>

The linear algebra concepts of independent set, generating set, basis and dimension can all be expressed using the <math>\text{cl}</math>-operator alone. A pregeometry is an abstraction of this situation: we start with an arbitrary set <math>S</math> and an arbitrary operator <math>\text{cl}</math> which assigns to each subset <math>A</math> of <math>S</math> a subset <math>\text{cl}(A)</math> of <math>S</math>, satisfying the properties above. Then we can define the "linear algebra" concepts also in this more general setting. 

This generalized notion of dimension is very useful in model theory, where in certain situation one can argue as follows: two models with the same cardinality must have the same dimension and two models with the same dimension must be isomorphic.

== Definitions ==

=== Pregeometries and geometries ===
A '''combinatorial pregeometry''' (also known as a '''finitary matroid''') is a pair <math>(S,\text{cl})</math>, where <math>S</math> is a set and <math>\text{cl}:\mathcal{P}(S)\to\mathcal{P}(S)</math> (called the '''closure map''') satisfies the following axioms. For all <math>a, b, c\in S</math> and <math>A, B\subseteq S</math>:

# <math>\text{cl}:(\mathcal{P}(S),\subseteq)\to(\mathcal{P}(S),\subseteq)</math> is '''monotone increasing''' and '''dominates''' <math>\text{id}</math> (''i.e.'' <math>A\subseteq B</math> implies <math>A\subseteq\text{cl}(A)\subseteq\text{cl}(B)</math>) and is '''idempotent''' (''i.e.'' <math>\text{cl}(\text{cl}(A))=\text{cl}(A)</math>)
# '''Finite character''': For each <math>a\in\text{cl}(A)</math> there is some finite <math>F\subseteq A</math> with <math>a\in\text{cl}(F)</math>.
# '''Exchange principle''': If <math>b\in\text{cl}(A\cup\{c\})\smallsetminus\text{cl}(A)</math>, then <math>c\in\text{cl}(A\cup\{b\}) </math> (and hence by monotonicity and idempotence in fact <math>c\in\text{cl}(A\cup\{b\})\smallsetminus\text{cl}(A)</math>).
Sets of the form <math>\text{cl}(A)</math> for some <math>A\subseteq S</math> are called '''closed'''. It is then clear that finite intersections of closed sets are closed and that <math>\text{cl}(A)</math> is the smallest closed set containing <math>A</math>.

A '''geometry''' is a pregeometry in which the closure of singletons are singletons and the closure of the empty set is the empty set.

=== Independence, bases and dimension ===

Given sets <math>A,D\subseteq S</math>, <math>A</math> is '''independent over''' <math>D</math> if <math>a\notin \text{cl}((A\setminus\{a\})\cup D)</math> for any <math>a\in A</math>. We say that <math>A</math> is '''independent''' if it is independent over the empty set.

A set <math>B \subseteq A</math> is a '''basis for''' <math>A</math> '''over''' <math>D</math> if it is independent over <math>D</math> and <math>A\subseteq \text{cl}(B\cup D)</math>. 

A basis is the same as a maximal independent subset, and using [[Zorn's lemma]] one can show that every set has a basis. Since a pregeometry satisfies the [[Steinitz exchange lemma|Steinitz exchange property]] all bases are of the same cardinality, hence we may define the  '''dimension''' of <math>A</math> over <math>D</math>, written as <math>\text{dim}_D A</math>, as the cardinality of any basis of <math>A</math> over <math>D</math>. Again, the dimension <math>\text{dim} A</math> of <math>A</math> is defined to be the dimension over the empty set.

The sets <math>A,B</math> are '''independent''' over <math>D</math> if <math>\text{dim}_{B\cup D} A' = \dim_D A'</math> whenever <math>A'</math> is a finite subset of <math>A</math>. Note that this relation is symmetric.

=== Automorphisms and homogeneous pregeometries ===

An '''automorphism''' of a pregeometry <math>(S,\text{cl})</math> is a bijection <math>\sigma:S\to S</math> such that <math>\sigma(\text{cl}(X))=\text{cl}(\sigma (X))</math> for any <math>X\subseteq S</math>.

A pregeometry <math>S</math> is said to be '''homogeneous''' if for any closed <math>X\subseteq S</math> and any two elements <math>a,b\in S\setminus X</math> there is an automorphism of <math>S</math> which maps <math>a</math> to <math>b</math> and fixes <math>X</math> pointwise.

=== The associated geometry and localizations ===

Given a pregeometry <math>(S,\text{cl})</math> its '''associated geometry''' (sometimes referred in the literature as the '''canonical geometry''') is the geometry <math>(S',\text{cl}')</math> where

#<math>S'=\{\text{cl}(a)\mid a\in S\setminus \text{cl} (\varnothing)\}</math>, and
#For any <math>X\subseteq S</math>, <math>\text{cl}'(\{\text{cl}(a)\mid a\in X\}) = \{\text{cl}(b)\mid b\in\text{cl}(X)\}</math>

Its easy to see that the associated geometry of a homogeneous pregeometry is homogeneous.

Given <math>A\subseteq S</math> the '''localization''' of <math>S</math> is the pregeometry <math>(S,\text{cl}_A)</math> where <math>\text{cl}_A(X)=\text{cl}(X\cup A)</math>.

=== Types of pregeometries ===

The pregeometry <math>(S,\text{cl})</math> is said to be:

* '''trivial''' (or '''degenerate''') if <math>\text{cl}(X)=\bigcup\{\text{cl}(a)\mid a\in X\}</math> for all non-empty <math>X\subseteq S</math>.
* '''modular''' if any two closed finite dimensional sets <math>X,Y\subseteq S</math> satisfy the equation <math>
\text{dim}(X\cup Y) = \text{dim}(X) + \text{dim}(Y) - \text{dim}(X\cap Y)
</math> (or equivalently that <math>X</math> is independent of <math>Y</math> over <math>X\cap Y</math>).
* '''locally modular''' if it has a localization at a singleton which is modular.
* (locally) '''projective''' if it is non-trivial and (locally) modular.
* '''locally finite''' if closures of finite sets are finite.

Triviality, modularity and local modularity pass to the associated geometry and are preserved under localization.

If <math>S</math> is a locally modular homogeneous pregeometry and <math>a\in S\setminus\text{cl}(\varnothing)</math> then the localization of <math>S</math> in <math>b</math> is modular.

The geometry <math>S</math> is modular if and only if whenever <math>a,b\in S</math>, <math>A\subseteq S</math>, <math>\text{dim}\{a,b\}=2</math> and <math>\text{dim}_A\{a,b\} \le 1</math> then <math>(\text{cl}\{a,b\}\cap\text{cl}(A))\setminus\text{cl}(\varnothing)\ne\varnothing</math>.

== Examples ==

=== The trivial example ===

If <math>S</math> is any set we may define <math>\text{cl}(A)=A</math> for all <math>A\subseteq S</math>. This pregeometry is a trivial, homogeneous, locally finite geometry.

=== Vector spaces and projective spaces ===

Let <math>F</math> be a [[Field (mathematics)|field]] (a division ring actually suffices) and let <math>V</math> be a vector space over <math>F</math>. Then <math>V</math> is a pregeometry where closures of sets are defined to be their [[Linear span|span]]. The closed sets are the linear subspaces of <math>V</math> and the notion of dimension from linear algebra coincides with the pregeometry dimension.

This pregeometry is homogeneous and modular. Vector spaces are considered to be the prototypical example of modularity.

<math>V</math> is locally finite if and only if <math>F</math> is finite.

<math>V</math> is not a geometry, as the closure of any nontrivial vector is a subspace of size at least <math>2</math>.

The associated geometry of a <math>\kappa</math>-dimensional vector space over <math>F</math> is the <math>(\kappa-1)</math>-dimensional [[projective space]] over <math>F</math>. It is easy to see that this pregeometry is a projective geometry.

=== Affine spaces ===

Let <math>V</math> be a <math>\kappa</math>-dimensional [[affine space]] over a field <math>F</math>. Given a set define its closure to be its [[affine hull]] (i.e. the smallest affine subspace containing it).

This forms a homogeneous <math>(\kappa+1)</math>-dimensional geometry.

An affine space is not modular (for example, if <math>X</math> and <math>Y</math> are parallel lines then the formula in the definition of modularity fails). However, it is easy to check that all localizations are modular.

=== Field extensions and transcendence degree ===

Let <math>L/K</math> be a [[field extension]]. The set <math>L</math> becomes a pregeometry if we define <math>\text{cl}(A)=\{x\in L : x \text{ is algebraic over } K(A)\}</math>for <math>A\subseteq L</math>.  The set <math>A</math> is independent in this pregeometry if and only if it is [[algebraically independent]] over <math>K</math>. The dimension of <math>A</math> coincides with the [[transcendence degree]] <math>\text{trdeg}(K(A)/K)</math>.

In model theory, the case of <math>L</math> being [[Algebraically closed field|algebraically closed]] and <math>K</math> its [[prime field]] is especially important.

While vector spaces are modular and affine spaces are "almost" modular (i.e. everywhere locally modular), algebraically closed fields are examples of the other extremity, not being even locally modular (i.e. none of the localizations is modular).

=== Strongly minimal sets in model theory ===
Given a countable first-order language ''L'' and an ''L-''[[Structure (mathematical logic)|structure]] ''M,'' any definable subset ''D'' of ''M'' that is [[Strongly minimal theory|strongly minimal]] gives rise to a pregeometry on the set ''D''. The closure operator here is given by the algebraic closure in the model-theoretic sense.

A model of a strongly minimal theory is determined up to isomorphism by its dimension as a pregeometry; this fact is used in the proof of [[Morley's categoricity theorem]].

In minimal sets over [[Stable theory|stable theories]] the independence relation coincides with the notion of forking independence.

==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.
* {{Cite web |last=Casanovas |first=Enrique |date=2008-11-11 |title=Pregeometries and minimal types |url=http://www.ub.edu/modeltheory/documentos/pregeometries.pdf}}

[[Category:Matroid theory]]
[[Category:Geometry|*]]
[[Category:Model theory]]