Pregeometry, and in full combinatorial pregeometry, are essentially synonyms for "
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
". They were introduced by
Gian-Carlo Rota
Gian-Carlo Rota (April 27, 1932 – April 18, 1999) was an Italian-American mathematician and philosopher. He spent most of his career at the Massachusetts Institute of Technology, where he worked in combinatorics, functional analysis, proba ...
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
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
– closure, independence, subspace, basis, dimension – are available in the general framework of pregeometries.
In the branch of
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
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 In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S
:
Closure operators are de ...
s influence the structure of
first-order
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
models is called
geometric stability theory.
Motivation
If
is a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
over some field and
, we define
to be the set of all
linear combinations of vectors from
, also known as the
span
Span may refer to:
Science, technology and engineering
* Span (unit), the width of a human hand
* Span (engineering), a section between two intermediate supports
* Wingspan, the distance between the wingtips of a bird or aircraft
* Sorbitan ester ...
of
. Then we have
and
and
. The
Steinitz exchange lemma
The Steinitz exchange lemma is a basic theorem in linear algebra used, for example, to show that any two bases for a finite-dimensional vector space have the same number of elements. The result is named after the German mathematician Ernst Steinit ...
is equivalent to the statement: if
, then
The linear algebra concepts of independent set, generating set, basis and dimension can all be expressed using the
-operator alone. A pregeometry is an abstraction of this situation: we start with an arbitrary set
and an arbitrary operator
which assigns to each subset
of
a subset
of
, 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
, where
is a set and
(called the closure map) satisfies the following axioms. For all
and
:
#
is monotone increasing and dominates
(''i.e.''
implies
) and is idempotent (''i.e.''
)
# Finite character: For each
there is some finite
with
.
# Exchange principle: If
, then
(and hence by monotonicity and idempotence in fact
).
Sets of the form
for some
are called closed. It is then clear that finite intersections of closed sets are closed and that
is the smallest closed set containing
.
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
,
is independent over
if
for any
. We say that
is independent if it is independent over the empty set.
A set
is a basis for
over
if it is independent over
and
.
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 property all bases are of the same cardinality, hence we may define the dimension of
over
, written as
, as the cardinality of any basis of
over
. Again, the dimension
of
is defined to be the dimesion over the empty set.
The sets
are independent over
if
whenever
is a finite subset of
. Note that this relation is symmetric.
Automorphisms and homogeneous pregeometries
An automorphism of a pregeometry
is a bijection
such that
for any
.
A pregeometry
is said to be homogeneous if for any closed
and any two elements
there is an automorphism of
which maps
to
and fixes
pointwise.
The associated geometry and localizations
Given a pregeometry
its associated geometry (sometimes referred in the literature as the canonical geometry) is the geometry
where
#
, and
#For any
,
Its easy to see that the associated geometry of a homogeneous pregeometry is homogeneous.
Given
the localization of
is the pregeometry
where
.
Types of pregeometries
The pregeometry
is said to be:
* trivial (or degenerate) if
for all non-empty
.
* modular if any two closed finite dimensional sets
satisfy the equation
(or equivalently that
is independent of
over
).
* 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
is a locally modular homogeneous pregeometry and
then the localization of
in
is modular.
The geometry
is modular if and only if whenever
,
,
and
then
.
Examples
The trivial example
If
is any set we may define
for all
. This pregeometry is a trivial, homogeneous, locally finite geometry.
Vector spaces and projective spaces
Let
be a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
(a division ring actually suffices) and let
be a vector space over
. Then
is a pregeometry where closures of sets are defined to be their
span
Span may refer to:
Science, technology and engineering
* Span (unit), the width of a human hand
* Span (engineering), a section between two intermediate supports
* Wingspan, the distance between the wingtips of a bird or aircraft
* Sorbitan ester ...
. The closed sets are the linear subspaces of
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.
is locally finite if and only if
is finite.
is not a geometry, as the closure of any nontrivial vector is a subspace of size at least
.
The associated geometry of a
-dimensional vector space over
is the
-dimensional
projective space over
. It is easy to see that this pregeometry is a projective geometry.
Affine spaces
Let
be a
-dimensional
affine space
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related ...
over a field
. Given a set define its closure to be its
affine hull
In mathematics, the affine hull or affine span of a set ''S'' in Euclidean space R''n'' is the smallest affine set containing ''S'', or equivalently, the intersection of all affine sets containing ''S''. Here, an ''affine set'' may be defined ...
(i.e. the smallest affine subspace containing it).
This forms a homogeneous
-dimensional geometry.
An affine space is not modular (for example, if
and
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
be a
field extension. The set
becomes a pregeometry if we define
for
. The set
is independent in this pregeometry if and only if it is
algebraically independent
In abstract algebra, a subset S of a field L is algebraically independent over a subfield K if the elements of S do not satisfy any non-trivial polynomial equation with coefficients in K.
In particular, a one element set \ is algebraically in ...
over
. The dimension of
coincides with the
transcendence degree
In abstract algebra, the transcendence degree of a field extension ''L'' / ''K'' is a certain rather coarse measure of the "size" of the extension. Specifically, it is defined as the largest cardinality of an algebraically independent subset of ...
.
In model theory, the case of
being
algebraically closed
In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in .
Examples
As an example, the field of real numbers is not algebraically closed, because ...
and
its
prime field
In mathematics, the characteristic of a ring , often denoted , is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive ide ...
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 ''M,'' any definable subset ''D'' of ''M'' that is
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 mathematical logic, a theory is categorical if it has exactly one model ( up to isomorphism). Such a theory can be viewed as ''defining'' its model, uniquely characterizing the model's structure.
In first-order logic, only theories with a ...
.
In minimal sets over
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
Matroid theory
*
Model theory