In
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 ...
, specifically in the discipline of
model theory, the Fraïssé limit (also called the Fraïssé construction or Fraïssé amalgamation) is a method used to construct (infinite)
mathematical structures
In mathematics, a structure is a set endowed with some additional features on the set (e.g. an operation, relation, metric, or topology). Often, the additional features are attached or related to the set, so as to provide it with some additiona ...
from their (finite)
substructures. It is a special example of the more general concept of a
direct limit in a
category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce) ...
.
The technique was developed in the 1950s by its namesake, French logician
Roland Fraïssé.
The main point of Fraïssé's construction is to show how one can approximate a (
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
) structure by its finitely generated substructures. Given a
class of finite
relational structures, if
satisfies certain properties (described below), then there exists a unique
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
structure
, called the Fraïssé limit of
, which contains all the elements of
as
substructures.
The general study of Fraïssé limits and related notions is sometimes called Fraïssé theory. This field has seen wide applications to other parts of mathematics, including
topological dynamics,
functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defined o ...
, and
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask ...
.
Finitely generated substructures and age
Fix a
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
. By an ''
-structure'', we mean a
logical structure having
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
.
Given an
-structure
with
domain , and a subset
, we use
to denote the least
substructure of
whose domain contains
(i.e. the closure of
under all the function and constant symbols in
).
A substructure
of
is then said to be ''finitely generated'' if
for some ''finite'' subset
. The ''age of
,'' denoted
, is the class of all finitely generated substructures of ''
.''
One can prove that any class
that is the age of some structure satisfies the following two conditions:
Hereditary property (HP)
: If
and
is a finitely generated substructure of
, then
is isomorphic to some structure in
.
Joint embedding property (JEP)
: If
, then there exists
such that both
and
are embeddable in
.
Fraïssé's theorem
As above, we noted that for any
-structure ''
,
'' satisfies the HP and JEP. Fraïssé proved a sort-of-converse result: when
is any non-empty, countable set of finitely generated
-structures that has the above two properties, then it is the age of some countable structure.
Furthermore, suppose that
happens to satisfy the following additional properties.
Amalgamation property (AP)
: For any structures
, such that there exist embeddings ''
'', ''
'', there exists a structure
and embeddings ''
'', ''
'' such that
(i.e. they coincide on the image of A in both structures).
Essential countability (EC)
: Up to isomorphism, there are countably many structures in
.
In that case, we say that K is a ''Fraïssé class'', and there is a unique (up to isomorphism), countable, homogeneous structure
whose age is exactly
. This structure is called the ''Fraïssé limit'' of
.
Here, ''homogeneous'' means that any
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
''
'' between two finitely generated substructures
can be extended to an
automorphism of the whole structure.
Examples
The archetypal example is the class
of all finite
linear orderings, for which the Fraïssé limit is a
dense
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
linear order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
without endpoints (i.e. no
smallest nor largest element). By
Cantor's isomorphism theorem
In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. For instance, there is an isomorphism (a one-to-one order-preserving co ...
, up to isomorphism, this is always equivalent to the structure
, i.e. the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
s with the usual ordering.
As a non-example, note that neither
nor
are the Fraïssé limit of
. This is because, although both of them are countable and have
as their age, neither one is homogeneous. To see this, consider the substructures
and
, and the isomorphism
between them. This cannot be extended to an automorphism of
or
, since there is no element to which we could map
, while still preserving the order.
Another example is the class
of all finite
graphs, whose Fraïssé limit is the
Rado graph.
ω-categoricity
Suppose our class
under consideration satisfies the additional property of being ''uniformly locally finite'', which means that for every
, there is a uniform bound on the size of an
-generated substructure. This condition is equivalent to the Fraïssé limit of
being
ω-categorical.
For example, the class of
finite dimensional 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 ...
s over a fixed
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 ...
is always a Fraïssé class, but it is uniformly locally finite only if the field is finite.
See also
*
Structural Ramsey theory
*
Hrushovski construction
References
{{Mathematical logic
Category theory
Mathematical logic
Model theory