FACTOID # 13: New York has America's lowest percentage of residents who are veterans.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Saturated model

In mathematical logic, and in particular model theory, a saturated model M is one which realizes as many complete types as may be "reasonably expected" given its size. Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. ... In model theory, a type is a set of formulae in first-order logic such that all the formulae could be consistent descriptions of a certain element (or several elements) of the model. ...

Contents


Definition

Let κ be a finite or infinite cardinal number and M a model in some first-order language (whose nature is unimportant to the definition). Then M is κ-saturated if and only if for all subsets AM of cardinality less than κ, M realizes all complete types over A. M is saturated if and only if it is |M|-saturated; that is, it realizes all complete types over sets of parameters of size less than |M|. In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... Infinity is a word carrying a number of different meanings in mathematics, philosophy, theology and everyday life. ... In linguistics, cardinal numbers is the name given to number words that are used for quantity (one, two, three), as opposed to ordinal numbers, words that are used for order (first, second, third). ... First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as there is at least one X such that. ... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections, injections, and surjections, and another which uses cardinal numbers. ...


Motivation

This is a stronger requirement than asking only that M realize all the complete types of the base language; such a model is called weakly saturated (which is the same as being 1-saturated). The difference lies in the fact that M may (and likely does) contain points which are "invisible" to the complete theory of M, in the sense that they are not definable. This argument owes its ultimate success to Gödel's completeness theorem, which guarantees that any consistent additional requirements we can add to the theory of M will be satisfiable by some other model which is logically indistinguishable from M by the original theory. In other words, if we do not explicitly call attention to specific subsets of M, then we miss out on the special features of M which distinguish it from all other elementarily equivalent models, which is often the exact application to which types are put. In mathematics, a mathematical object X of some type T is definable, if there exists some predicate P(x) which is expressible using a finite string of mathematical symbols drawn from a finite language, such that P(X) is true and P(Y) is false for all Y of type... Gödels completeness theorem is a fundamental theorem in mathematical logic proved by Kurt Gödel in 1929. ... In mathematics, specifically model theory, two models of a language are said to be elementarily equivalent if their theories are the same; that is, any sentence satisfied by one model is also satisfied by the other. ...


The reason it is "reasonable" only to require that M realize types over strictly smaller (in cardinality) subsets is that we can trivially create a type p(x) which takes its parameters from all of M and which cannot be realized in M. Indeed, simply let p(x) be the set of formulas of the form xa, for arbitrary a in M; then for p(x) to be realized in M, it would have to be satisfied by an element of M unequal to any element of M! Likewise, knowing more about the structure of M we could concoct an unrealizable formula using most but not all the elements of M (for example, in the natural numbers example below we could omit any subset of the formulas so long as the ones which are left still require that x be unbounded above). This would therefore make the notion of saturation useless, so we do not require that such formulas be realized.


Examples

Saturated models exist: for instance, (Q, <) is saturated and the countable random graph is saturated. The natural numbers (N, S) (where S is the successor function, S(n) = n + 1 for any integer n) are not saturated: the type p(x) containing In the science of mathematics, a random graph is a graph that is generated by some random process. ...

{ x > 0, x > S(0), x > S(S(0)), …, x > S(… (S(0)) … ), … }

is not realized (since it would necessarily be realized by an infinite number!).


Relationship to prime models

The notion of saturated model is dual to the notion of prime model in the following way: let T be a countable theory in a first-order language (that is, a set of mutually consistent sentences in that language) and let P be a prime model of T. Then P admits an elementary embedding into any other model of T. The equivalent notion for saturated models is that any "reasonably small" model of T is elementarily embedded in a saturated model, where "reasonably small" means cardinality no larger than that of the model in which it is to be embedded! Any saturated model is also homogeneous. However, while for countable theories there is a unique prime model, saturated models are necessarily specific to a particular cardinality. Given certain set-theoretic assumptions, saturated models (albeit of very large cardinality) exist for arbitrary theories. For sufficiently stable theories, saturated models exist in all infinite cardinalities. In mathematics, and in particular model theory, a prime model is a model which is as simple as possible. ... In mathematical logic, given models and in the same language , a function is called an elementary embedding if is an elementary substructure of . ...


References

  • Chang, C. C.; Keisler, H. J. Model theory. Third edition. Studies in Logic and the Foundations of Mathematics, 73. North-Holland Publishing Co., Amsterdam, 1990. xvi+650 pp. ISBN 0-444-88054-2
  • Marker, David (2002). Model Theory: An Introduction. New York: Springer-Verlag. ISBN 0-387-98760-6
  • Poizat, Bruno; Trans: Klein, Moses (2000), A Course in Model Theory, New York: Springer-Verlag. ISBN 0-387-98655-3

  Results from FactBites:
 
Saturated model - Wikipedia, the free encyclopedia (694 words)
In mathematical logic, and in particular model theory, a saturated model M is one which realizes as many complete types as may be "reasonably expected" given its size.
Saturated models exist: for instance, (Q, <) is saturated and the countable random graph is saturated.
The notion of saturated model is dual to the notion of prime model in the following way: let T be a countable theory in a first-order language (that is, a set of mutually consistent sentences in that language) and let P be a prime model of T.
Type (model theory) - Wikipedia, the free encyclopedia (866 words)
In model theory, a type is a set of formulae in first-order logic such that all the formulae could be consistent descriptions of a certain element (or several elements) of the model.
A model that realizes the maximum possible variety of types is called a saturated model, and the ultrapower construction provides one way of producing saturated models.
The field of algebraic numbers is a model omitting this type, and the algebraic closure of any transcendental extension of the rationals is a model realizing this type.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m