Amalgamation property

Short description: Concept in model theory

A commutative diagram of the 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.

This property plays a crucial role in Fraïssé's theorem, which characterises classes of finite structures that arise as ages of countable homogeneous structures.

The diagram of the amalgamation property appears in many areas of mathematical logic. Examples include in modal logic as an incestual accessibility relation,[clarification needed] and in lambda calculus as a manner of reduction having the Church–Rosser property.

## Contents

* 1 Definition
* 2 Examples
* 3 Strong amalgamation property
* 4 See also
* 5 References
* 6 References

## Definition

An amalgam can be formally defined as a 5-tuple (A,f,B,g,C) such that A,B,C are structures having the same signature, and f: A → B, g: A → C are embeddings. Recall that f: A → B is an embedding if f is an injective morphism which induces an isomorphism from A to the substructure f(A) of B.[1]

A class K of structures has the amalgamation property if for every amalgam with A,B,C ∈ K and A ≠ Ø, there exist both a structure D ∈ K and embeddings f': B → D, g': C → D such that

f′∘f=g′∘g.

A first-order theory T has the amalgamation property if the class of models of T has the amalgamation property. The amalgamation property has certain connections to the quantifier elimination.

In general, the amalgamation property can be considered for a category with a specified choice of the class of morphisms (in place of embeddings). This notion is related to the categorical notion of a pullback, in particular, in connection with the strong amalgamation property (see below).[2]

## Examples

* The class of sets, where the embeddings are injective functions, and if they are assumed to be inclusions then an amalgam is simply the union of the two sets.
* The class of free groups where the embeddings are injective homomorphisms, and (assuming they are inclusions) an amalgam is the quotient group B*C/A, where * is the free product.
* The class of finite linear orderings. This is due to the fact that any homogeneous structure from an amalgamation class of finite structure. [3]

A similar but different notion to the amalgamation property is the joint embedding property. To see the difference, first consider the class K (or simply the set) containing three models with linear orders, L1 of size one, L2 of size two, and L3 of size three. This class K has the joint embedding property because all three models can be embedded into L3. However, K does not have the amalgamation property. The counterexample for this starts with L1 containing a single element e and extends in two different ways to L3, one in which e is the smallest and the other in which e is the largest. Now any common model with an embedding from these two extensions must be at least of size five so that there are two elements on either side of e.

Now consider the class of algebraically closed fields. This class has the amalgamation property since any two field extensions of a prime field can be embedded into a common field. However, two arbitrary fields cannot be embedded into a common field when the characteristic of the fields differ.

## Strong amalgamation property

A class K of structures has the strong amalgamation property (SAP), also called the disjoint amalgamation property (DAP), if for every amalgam with A,B,C ∈ K there exist both a structure D ∈ K and embeddings f': B → D, g': C → D such that

f′∘f=g′∘g

and

f′[B]∩g′[C]=(f′∘f)[A]=(g′∘g)[A]

where for any set X and function h on X,

h[X]={h(x)∣x∈X}.

## See also

* Span (category theory)
* Pushout (category theory)
* Joint embedding property
* Fraïssé's theorem

## References

1. ↑ Hodges, Section 1.2 and Exercise 4 therein. When no relation is present, as in the case of groups, the notion of embedding and of injective morphism are the same, see p. 6.
2. ↑ Kiss, Márki, Pröhle, Tholen, Section 6
3. ↑ (Macpherson 2011).

## References

* Hodges, Wilfrid (1997). A shorter model theory. Cambridge University Press. ISBN 0-521-58713-1.
* Entries on amalgamation property and strong amalgamation property in online database of classes of algebraic structures (Department of Mathematics and Computer Science, Chapman University).
* E.W. Kiss, L. Márki, P. Pröhle, W. Tholen, Categorical algebraic properties. A compendium on amalgamation, congruence extension, epimorphisms, residual smallness, and injectivity, Studia Sci. Math. Hungar 18 (1), 79-141, 1983 whole journal issue.
* Macpherson, Donald (2011), "A survey of homogeneous structures", Discrete Mathematics 311 (2): 1599-1634, doi:10.1016/j.disc.2011.01.024 .

* v
* t
* e

Mathematical logic

General|

* Formal language
* Formation rule
* Formal proof
* Formal semantics
* Well-formed formula
* Set
* Element
* Class
* Classical logic
* Axiom
* Rule of inference
* Relation
* Theorem
* Logical consequence
* Type theory
* Symbol
* Syntax
* Theory

Systems|

* Formal system
* Deductive system
* Axiomatic system
* Hilbert style systems
* Natural deduction
* Sequent calculus

Traditional logic|

* Proposition
* Inference
* Argument
* Validity
* Cogency
* Syllogism
* Square of opposition
* Venn diagram

Propositional calculus
and Boolean logic

* Boolean functions
* Propositional calculus
* Propositional formula
* Logical connectives
* Truth tables
* Many-valued logic

Predicate logic|

* First-order
* Quantifiers
* Predicate
* Second-order
* Monadic predicate calculus

Naive set theory|

* Set
* Empty set
* Element
* Enumeration
* Extensionality
* Finite set
* Infinite set
* Subset
* Power set
* Countable set
* Uncountable set
* Recursive set
* Domain
* Codomain
* Image
* Map
* Function
* Relation
* Ordered pair

Set theory|

* Foundations of mathematics
* Zermelo–Fraenkel set theory
* Axiom of choice
* General set theory
* Kripke–Platek set theory
* Von Neumann–Bernays–Gödel set theory
* Morse–Kelley set theory
* Tarski–Grothendieck set theory

Model theory|

* Model
* Interpretation
* Non-standard model
* Finite model theory
* Truth value
* Validity

Proof theory|

* Formal proof
* Deductive system
* Formal system
* Theorem
* Logical consequence
* Rule of inference
* Syntax

Computability
theory|

* Recursion
* Recursive set
* Recursively enumerable set
* Decision problem
* Church–Turing thesis
* Computable function
* Primitive recursive function

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Amalgamation property. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Amalgamation_property&oldid=4158257"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template