FACTOID # 11: Oklahoma has the highest rate of women in State or Federal correctional facilities.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Model theory

In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined... An abstract structure is a set of rules, properties and relationships that is defined independently of any physical objects. ...

The independence of the axiom of choice and the continuum hypothesis from the other axioms of set theory (proved by Paul Cohen and Kurt Gödel) are the two most famous results arising from model theory. It was proved that both the axiom of choice and its negation are consistent with the Zermelo-Fraenkel axioms of set theory; the same result holds for the continuum hypothesis. These results are applications of model-theoretic methods to axiomatic set theory. In mathematics, the axiom of choice, or AC, is an axiom of set theory. ... In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... Paul Joseph Cohen (born April 2, 1934) is an American mathematician. ... Kurt GÃ¶del (IPA: ) (April 28, 1906 Brno, then Austria-Hungary, now Czech Republic â€“ January 14, 1978 Princeton, New Jersey) was an Austrian logician, mathematician, and philosopher of mathematics One of the most significant logicians of all time, GÃ¶dels work has had immense impact upon scientific and philosophical... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ... This article or section is in need of attention from an expert on the subject. ...

The theory of the real numbers provides an example of the concepts of model theory. We start with a set of individuals, where each individual is a real number, and a set of relations and/or functions, such as { ×, +, −, ., 0, 1 }. If we ask a question such as "∃y (y × y = 1 + 1)" in this language, then it is clear that the sentence is true for the reals - there is such a real number y, namely the square root of 2; for the rational numbers, however, the sentence is false. A similar proposition, "∃y (y × y = 0 − 1)", is false in the reals, but is true in the complex numbers, where i × i = 0 − 1. In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, a square root of a number x is a number whose square (the result of multiplying the number by itself) is x. ... In mathematics, a rational number (commonly called a fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = âˆ’1. ...

## Contents

A structure is formally defined in the context of some language L, which consists of a set of constant symbols, a set of relation symbols, and a set of function symbols. A structure over the language L, or L-structure, consists of several things: In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined...

1. a universe or underlying set A which contains all the objects of interest (the "domain of discourse"),
2. an element of A for each constant symbol of L,
3. a function from An to A for each function symbol of L of valence n, and
4. an n-ary relation on A (in other words, a subset of An) for each relation symbol of L of valence n.

The valence of functions or relations is sometimes also referred to as the arity (a back-formation from the terms "unary," "binary," "ternary," or "n-ary"). The domain of discourse, sometimes called the universe of discourse, is an analytic tool used in deductive logic, especially predicate logic. ... In logic, mathematics, and computer science, the arity (synonyms include type, adicity, and rank) of a function or operation is the number of arguments or operands that the function takes. ...

A theory in the language L, or L-theory, is defined as a set of sentences in the language L, and is called a closed theory if the set of sentences is closed under the usual rules of inference. For example, the set of all sentences true in some particular L-structure (e.g. the reals) is a closed L-theory. A model of an L-theory T consists of an L-structure in which all sentences of T are true, normally defined by means of a T-schema. Convention T is the inductive definition that lies at the heart of any realisation of Alfred Tarskis semantic theory of truth, expressing the commutation of truth over logical operators. ...

A theory is said to be satisfiable if it has a model.

For example, the language of partial orders has just one binary relation ≥. So a structure of the language of partial orders is just a set with a binary relation denoted by ≥, and it is a model of the theory of partial orders so long as it satisfies the axioms of a partial order.

## Theorems of model theory

Gödel's completeness theorem (not to be confused with his incompleteness theorems) says that a theory has a model if and only if it is consistent, i.e. no contradiction is proved by the theory. This is the heart of model theory as it lets us answer questions about theories by looking at models and vice-versa. One should not confuse the completeness theorem with the notion of a complete theory. A complete theory is a theory that contains every sentence or its negation. Importantly, one can find a complete consistent theory extending any consistent theory. However, as shown by Gödel's incompleteness theorems only in relatively simple cases will it be possible to have a complete consistent theory that is also recursive, i.e. that can be described by a recursively enumerable set of axioms. In particular, the theory of natural numbers has no recursive complete and consistent theory. Non-recursive theories are of little practical use, since it is undecidable if a proposed axiom is indeed an axiom, making proof-checking practically impossible. GÃ¶dels completeness theorem is an important theorem in mathematical logic which was first proved by Kurt GÃ¶del in 1929. ... In mathematical logic, GÃ¶dels incompleteness theorems, proved by Kurt GÃ¶del in 1931, are two celebrated theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. ... Consistency has several technical meanings: In NASCAR Racing, consistency is a term coined by NASCAR drivers about the frequency of finishing well in the top ten or top five each race as it helps to get enough points to make the Chase For The Cup and win the Nextel Cup... In mathematical logic, a sentence is a formula with no free variables; therefore, a sentence is either true or false in a given structure. ... In mathematical logic, GÃ¶dels incompleteness theorems, proved by Kurt GÃ¶del in 1931, are two celebrated theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. ... See: Recursion Recursively enumerable language Recursively enumerable set Recursive filter Recursive function Recursive set Primitive recursive function This is a disambiguation page â€” a list of pages that otherwise might share the same title. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input &#8212; typically an integer or a tuple of integers or a sequence of characters &#8212; eventually halts... Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ...

The compactness theorem states that a set of sentences S is satisfiable if every finite subset of S is satisfiable. In the context of proof theory the analogous statement is trivial, since every proof can have only a finite number of antecedents used in the proof. In the context of model theory, however, this proof is somewhat more difficult. There are two well known proofs, one by Gödel (which goes via proofs) and one by Malcev (which is more direct and allows us to restrict the cardinality of the resulting model). The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ... Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ... Kurt GÃ¶del (IPA: ) (April 28, 1906 Brno, then Austria-Hungary, now Czech Republic â€“ January 14, 1978 Princeton, New Jersey) was an Austrian logician, mathematician, and philosopher of mathematics One of the most significant logicians of all time, GÃ¶dels work has had immense impact upon scientific and philosophical... Anatoly Ivanovich Malcev was born 27 November 1909 in Misheronsky, near Moscow, and died 7 July 1967 in Novosibirsk, USSR. He was a mathematician noted for his work on the decidability of various algebraic groups. ...

Model theory is usually concerned with first-order logic, and many important results (such as the completeness and compactness theorems) fail in second-order logic or other alternatives. In first-order logic all infinite cardinals look the same to a language which is countable. This is expressed in the Löwenheim-Skolem theorems, which state that any countable theory with an infinite model $mathfrak{A}$ has models of all infinite cardinalities (at least that of the language) which agree with $mathfrak{A}$ on all sentences, i.e. they are 'elementarily equivalent'. First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ... GÃ¶dels completeness theorem is an important theorem in mathematical logic which was first proved by Kurt GÃ¶del in 1929. ... The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ... In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ... In mathematics the term countable set is used to describe the size of a set, e. ... In mathematical logic, the classic LÃ¶wenheim-Skolem theorem states that any infinite model M has a countably infinite submodel N that satisfies exactly the same set of first-order sentences that M satisfies. ... 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. ...

So in particular, set theory (which is expressed in a countable language) has a countable model; this is known as Skolem's paradox, since there are sentences in set theory which postulate the existence of uncountable sets and yet these sentences are true in our countable model. Particularly the proof of the independence of the continuum hypothesis requires considering sets in models which appear to be uncountable when viewed from within the model, but are countable to someone outside the model. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics the term countable set is used to describe the size of a set, e. ... In mathematical logic, specifically set theory, Skolems paradox is a direct result of the (downward) LÃ¶wenheim-Skolem theorem, which states that every model of a sentence of a first-order language has an elementarily equivalent countable submodel. ... In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ...

In mathematics, an axiomatizable class is a class of mathematical structures which are all models of a fixed set of sentences in formal (typically first order) logic. ... The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ... Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, in which we seek to characterize complexity classes by the type of logic needed to express the languages in them. ... In mathematical logic, given models and in the same language , a function is called an elementary embedding if is an elementary substructure of . ... Finite model theory is a subfield of model theory that focuses on properties of logical languages, such as first-order logic, over finite structures, such as finite groups, graphs, databases, and most abstract machines. ... In mathematical logic, a first-order theory is given by a set of axioms in some language. ... In axiomatic set theory, forcing is a technique, invented by Paul Cohen, for proving consistency and independence results with respect to the Zermelo-Fraenkel axioms. ... The system of hyperreal numbers represents a rigorous method of treating the ideas about infinite and infinitesimal numbers that had been used casually by mathematicians, scientists, and engineers ever since the invention of calculus by Newton and Leibniz. ... Institutional model theory generalizes a large portion of first-order model theory to an arbritary logical system. ... Kripke semantics (also known as possible world semantics, relational semantics, or frame semantics) is a formal semantics for modal logic systems, created in late 1950s and early 1960s by Saul Kripke. ... In mathematical logic, the classic LÃ¶wenheimâ€“Skolem theorem states that for any countable first-order language L with signature and L-structure M, there exists a countably infinite elementary substructure N M. A natural and useful corollary of this theorem is that every consistent L-theory has a countable... Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ... 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. ...

## References

• Wilfrid Hodges, A shorter model theory (1997) Cambridge University Press ISBN 0-521-58713-1
• Wilfrid Hodges, Model theory (1993) Cambridge University Press.
• C. C. Chang, H. J. Keisler Model theory (1977) ISBN 0-7204-0692-7
• David Marker Model Theory: An Introduction (2002) Springer-Verlag, ISBN 0-387-98760-6

A monograph available free online: Wilfrid Hodges (born 1941) is a British mathematician, known for his work in model theory. ... Wilfrid Hodges (born 1941) is a British mathematician, known for his work in model theory. ...

• Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.

Results from FactBites:

 Encyclopedia4U - Model theory - Encyclopedia Article (619 words) 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. Restricting the cardinality of models and noting that facts are true may allow the compactness theorem to be invoked, showing some theorem is true in a model of larger cardinality. Completeness in model theory is defined as the property that every statement in a language or its opposite is provable from some theory.
 Model theory - definition of Model theory in Encyclopedia (860 words) The independence of the axiom of choice and the continuum hypothesis from the other axioms of set theory (proven by Paul Cohen and Kurt Gödel) are the two most famous results arising from model theory. An example of the concepts of model theory is provided by the theory of the real numbers. Model theory is usually concerned with first order logic and many important results (such as the completeness and compactness theorems) fail in second order logic or other alternatives.
More results at FactBites »

Share your thoughts, questions and commentary here