Fraïssé limit
   HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of logic, 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 for ...
, specifically in the discipline of
model theory In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, 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 mathematics, a direct limit is a way to construct a (typically large) object from many (typically smaller) objects that are put together in a specific way. These objects may be groups, rings, vector spaces or in general objects from any categor ...
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é Roland Fraïssé (; 12 March 1920 – 30 March 2008) was a French mathematical logician. Fraïssé received his doctoral degree from the University of Paris in 1953. In his thesis, Fraïssé used the back-and-forth method to determine whether t ...
. 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 Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
\mathbf of finite relational structures, if \mathbf 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 \operatorname(\mathbf), called the Fraïssé limit of \mathbf, which contains all the elements of \mathbf 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 In mathematics, topological dynamics is a branch of the theory of dynamical systems in which qualitative, asymptotic properties of dynamical systems are studied from the viewpoint of general topology. Scope The central object of study in topol ...
,
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 space#Definition, inner product, Norm (mathematics)#Defini ...
, 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 a ...
.


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 met ...
\mathcal. By an ''\mathcal-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 ...
\mathcal. Given an \mathcal-structure \mathcal with
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function * Do ...
M, and a subset A \subseteq M, we use \langle A \rangle^\mathcal to denote the least substructure of \mathcal whose domain contains A (i.e. the closure of A under all the function and constant symbols in \mathcal). A substructure \mathcal of \mathcal is then said to be ''finitely generated'' if \mathcal = \langle A \rangle^\mathcal for some ''finite'' subset A \subseteq M. The ''age of \mathcal,'' denoted \operatorname(\mathcal), is the class of all finitely generated substructures of ''\mathcal.'' One can prove that any class \mathbf that is the age of some structure satisfies the following two conditions: Hereditary property (HP) : If A \in \mathbf and B is a finitely generated substructure of A, then B is isomorphic to some structure in \mathbf.
Joint embedding property In universal algebra and model theory, a class of structures ''K'' is said to have the joint embedding property if for all structures ''A'' and ''B'' in ''K'', there is a structure ''C'' in ''K'' such that both ''A'' and ''B'' have embeddings into ...
(JEP) : If A, B \in \mathbf, then there exists C \in \mathbf such that both A and B are embeddable in C.


Fraïssé's theorem

As above, we noted that for any \mathcal-structure ''\mathcal, \operatorname(\mathcal)'' satisfies the HP and JEP. Fraïssé proved a sort-of-converse result: when \mathbf is any non-empty, countable set of finitely generated \mathcal-structures that has the above two properties, then it is the age of some countable structure. Furthermore, suppose that \mathbf happens to satisfy the following additional properties.
Amalgamation property In the mathematical field of model theory, the amalgamation property is a property of collections of structures that guarantees, under certain conditions, that two structures in the collection can be regarded as substructures of a larger one. Thi ...
(AP) : For any structures A, B, C \in \mathbf, such that there exist embeddings ''f: A \to B'', ''g: A \to C'', there exists a structure D \in \mathbf and embeddings ''f': B \to D'', ''g': C \to D'' such that f' \circ f = g' \circ g (i.e. they coincide on the image of A in both structures). Essential countability (EC) : Up to isomorphism, there are countably many structures in \mathbf. In that case, we say that K is a ''Fraïssé class'', and there is a unique (up to isomorphism), countable, homogeneous structure \operatorname(\mathbf) whose age is exactly \mathbf. This structure is called the ''Fraïssé limit'' of \mathbf. 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 is ...
''\pi: A \to B'' between two finitely generated substructures A, B \in \mathbf can be extended to an
automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
of the whole structure.


Examples

The archetypal example is the class \mathbf 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 \langle \mathbb, < \rangle, 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 ration ...
s with the usual ordering. As a non-example, note that neither \langle \mathbb, < \rangle nor \langle \mathbb, < \rangle are the Fraïssé limit of \mathbf. This is because, although both of them are countable and have \mathbf as their age, neither one is homogeneous. To see this, consider the substructures \big\langle \, < \big\rangle and \big\langle \, < \big\rangle, and the isomorphism 1 \mapsto 5,\ 3 \mapsto 6 between them. This cannot be extended to an automorphism of \langle \mathbb, < \rangle or \langle \mathbb, < \rangle, since there is no element to which we could map 2, while still preserving the order. Another example is the class \mathbf of all finite
graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
, whose Fraïssé limit is the
Rado graph In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whe ...
.


ω-categoricity

Suppose our class \mathbf under consideration satisfies the additional property of being ''uniformly locally finite'', which means that for every n, there is a uniform bound on the size of an n-generated substructure. This condition is equivalent to the Fraïssé limit of \mathbf being ω-categorical. For example, the class of
finite dimensional In mathematics, the dimension of a vector space ''V'' is the cardinality (i.e., the number of vectors) of a basis of ''V'' over its base field. p. 44, §2.36 It is sometimes called Hamel dimension (after Georg Hamel) or algebraic dimension to dis ...
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 In mathematics, structural Ramsey theory is a categorical generalisation of Ramsey theory, rooted in the idea that many important results of Ramsey theory have "similar" logical structure. The key observation is noting that these Ramsey-type theore ...
* Hrushovski construction


References

{{Mathematical logic Category theory Mathematical logic Model theory