Atomic model (mathematical logic)

Last updated September 12, 2024

In model theory, a subfield of mathematical logic, an atomic model is a model such that the complete type of every tuple is axiomatized by a single formula. Such types are called principal types, and the formulas that axiomatize them are called complete formulas.

Definitions

Let T be a theory. A complete type p(x₁, ..., x_n) is called principal or atomic (relative to T) if it is axiomatized relative to T by a single formula φ(x₁, ..., x_n) ∈ p(x₁, ..., x_n).

A formula φ is called complete in T if for every formula ψ(x₁, ..., x_n), the theory T ∪ {φ} entails exactly one of ψ and ¬ψ.^[1] It follows that a complete type is principal if and only if it contains a complete formula.

A model M is called atomic if every n-tuple of elements of M satisfies a formula that is complete in Th(M)—the theory of M.

Examples

The ordered field of real algebraic numbers is the unique atomic model of the theory of real closed fields.
Any finite model is atomic.
A dense linear ordering without endpoints is atomic.
Any prime model of a countable theory is atomic by the omitting types theorem.
Any countable atomic model is prime, but there are plenty of atomic models that are not prime, such as an uncountable dense linear order without endpoints.
The theory of a countable number of independent unary relations is complete but has no completable formulas and no atomic models.

Properties

The back-and-forth method can be used to show that any two countable atomic models of a theory that are elementarily equivalent are isomorphic.

Notes

↑ Some authors refer to complete formulas as "atomic formulas", but this is inconsistent with the purely syntactical notion of an atom or atomic formula as a formula that does not contain a proper subformula.

Related Research Articles

First-order logic—also called predicate logic, predicate calculus, quantificational logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables. Rather than propositions such as "all men are mortal", in first-order logic one can have expressions in the form "for all x, if x is a man, then x is mortal"; where "for all x" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

The proof of Gödel's completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 is not easy to read today; it uses concepts and formalisms that are no longer used and terminology that is often obscure. The version given below attempts to represent all the steps in the proof and all the important ideas faithfully, while restating the proof in the modern language of mathematical logic. This outline should not be considered a rigorous proof of the theorem.

In mathematical logic, model theory is the study of the relationship between formal theories, and their models. The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.

In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.

In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem.

In mathematical logic, and particularly in its subfield model theory, a saturated modelM is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ultrapower model of the hyperreals is $-saturated, meaning that every descending nested sequence of internal sets has a nonempty intersection.$

In model theory, a branch of mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences.

Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe.

In mathematical logic, an arithmetical set is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy.

In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take values in some fixed complete Boolean algebra.

In model theory and related areas of mathematics, a type is an object that describes how a element or finite collection of elements in a mathematical structure might behave. More precisely, it is a set of first-order formulas in a language L with free variables x₁, x₂,..., x_n that are true of a set of n-tuples of an L-structure $. Depending on the context, types can be complete or partial and they may use a fixed set of constants, A, from the structure . The question of which types represent actual elements of leads to the ideas of saturated models and omitting types .$

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

In mathematical logic, a theory is complete if it is consistent and for every closed formula in the theory's language, either that formula or its negation is provable. That is, for every sentence $the theory contains the sentence or its negation but not both. Recursively axiomatizable first-order theories that are consistent and rich enough to allow general mathematical reasoning to be formulated cannot be complete, as demonstrated by Gödel's first incompleteness theorem.$

In model theory, a branch of mathematical logic, the notion of an existentially closed model of a theory generalizes the notions of algebraically closed fields, real closed fields, existentially closed groups, and dense linear orders without endpoints.

In the mathematical field of model theory, a theory is called stable if it satisfies certain combinatorial restrictions on its complexity. Stable theories are rooted in the proof of Morley's categoricity theorem and were extensively studied as part of Saharon Shelah's classification theory, which showed a dichotomy that either the models of a theory admit a nice classification or the models are too numerous to have any hope of a reasonable classification. A first step of this program was showing that if a theory is not stable then its models are too numerous to classify.

In mathematical logic, an omega-categorical theory is a theory that has exactly one countably infinite model up to isomorphism. Omega-categoricity is the special case κ = $= ω of κ-categoricity, and omega-categorical theories are also referred to as ω-categorical . The notion is most important for countable first-order theories.$

This is a glossary of terms and definitions related to the topic of set theory.

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, Minkowski's question-mark function produces an isomorphism between the numerical ordering of the rational numbers and the numerical ordering of the dyadic rationals.

In mathematics, S2S is the monadic second order theory with two successors. It is one of the most expressive natural decidable theories known, with many decidable theories interpretable in S2S. Its decidability was proved by Rabin in 1969.

References

Chang, Chen Chung; Keisler, H. Jerome (1990), Model Theory, Studies in Logic and the Foundations of Mathematics (3rd ed.), Elsevier, ISBN 978-0-444-88054-3
Hodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 978-0-521-58713-6

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Some authors refer to complete formulas as "atomic formulas", but this is inconsistent with the purely syntactical notion of an atom or atomic formula as a formula that does not contain a proper subformula.

[1]