HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, a definable set is an ''n''-ary relation on the domain of a
structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
whose elements satisfy some
formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
in the first-order language of that structure. A
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
can be defined with or without parameters, which are elements of the domain that can be referenced in the formula defining the relation.


Definition

Let \mathcal be a first-order language, \mathcal an \mathcal-structure with domain M, X a fixed
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
of M, and m a
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
. Then: * A set A\subseteq M^m is ''definable in \mathcal with parameters from X'' if and only if there exists a formula \varphi _1,\ldots,x_m,y_1,\ldots,y_n/math> and elements b_1,\ldots,b_n\in X such that for all a_1,\ldots,a_m\in M, :(a_1,\ldots,a_m)\in A if and only if \mathcal\models\varphi _1,\ldots,a_m,b_1,\ldots,b_n :The bracket notation here indicates the semantic evaluation of the
free variable In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a variable may be said to be either free or bound. Some older books use the terms real variable and apparent variable for f ...
s in the formula. * A set ''A is definable in \mathcal without parameters'' if it is definable in \mathcal with parameters from the
empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...
(that is, with no parameters in the defining formula). * A function is definable in \mathcal (with parameters) if its graph is definable (with those parameters) in \mathcal. * An element a is definable in \mathcal (with parameters) if the
singleton set In mathematics, a singleton (also known as a unit set or one-point set) is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the a ...
\ is definable in \mathcal (with those parameters).


Examples


The natural numbers with only the order relation

Let \mathcal=(\mathbb,<) be the structure consisting of the natural numbers with the usual ordering. Then every natural number is definable in \mathcal without parameters. The number 0 is defined by the formula \varphi(x) stating that there exist no elements less than ''x'': :\varphi=\neg\exists y(y and a natural number n>0 is defined by the formula \varphi(x) stating that there exist exactly n elements less than ''x'': :\varphi = \exists x_0\cdots\exists x_(x_0 In contrast, one cannot define any specific
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
without parameters in the structure \mathcal=(\mathbb,<) consisting of the integers with the usual ordering (see the section on
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 automorphism ...
s below).


The natural numbers with their arithmetical operations

Let \mathcal=(\mathbb,+, \cdot, <) be the first-order structure consisting of the natural numbers and their usual arithmetic operations and order relation. The sets definable in this structure are known as the arithmetical sets, and are classified in the
arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
. If the structure is considered in
second-order logic 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. First-order logic quantifies on ...
instead of first-order logic, the definable sets of natural numbers in the resulting structure are classified in the analytical hierarchy. These hierarchies reveal many relationships between definability in this structure and
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, and are also of interest in
descriptive set theory In mathematical logic, descriptive set theory (DST) is the study of certain classes of "well-behaved" set (mathematics), subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has a ...
.


The field of real numbers

Let \mathcal=(\mathbb,0,1,+,\cdot) be the structure consisting of the field of
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s. Although the usual ordering relation is not directly included in the structure, there is a formula that defines the set of nonnegative reals, since these are the only reals that possess square roots: :\varphi = \exists y(y \cdot y \equiv x). Thus any a\in\R is nonnegative if and only if \mathcal\models\varphi /math>. In conjunction with a formula that defines the additive inverse of a real number in \mathcal, one can use \varphi to define the usual ordering in \mathcal: for a,b\in\R, set a\le b if and only if b-a is nonnegative. The enlarged structure \mathcal^=(\mathbb,0,1,+,\cdot,\le) is called a definitional extension of the original structure. It has the same expressive power as the original structure, in the sense that a set is definable over the enlarged structure from a set of parameters if and only if it is definable over the original structure from that same set of parameters. The
theory A theory is a systematic and rational form of abstract thinking about a phenomenon, or the conclusions derived from such thinking. It involves contemplative and logical reasoning, often supported by processes such as observation, experimentation, ...
of \mathcal^ has
quantifier elimination Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement "\exists x such that ..." can be viewed as a question "When is there an x such ...
. Thus the definable sets are Boolean combinations of solutions to polynomial equalities and inequalities; these are called semi-algebraic sets. Generalizing this property of the real line leads to the study of o-minimality.


Invariance under automorphisms

An important result about definable sets is that they are preserved under
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 automorphism ...
s which fix their parameter set. :Let \mathcal be an \mathcal-structure with domain M, X\subseteq M, and A\subseteq M^m definable in \mathcal with parameters from X. Let \pi:M\to M be an automorphism of \mathcal that is the identity on X. Then for all a_1,\ldots,a_m\in M, ::(a_1,\ldots,a_m)\in A if and only if (\pi(a_1),\ldots,\pi(a_m))\in A. This result can sometimes be used to classify the definable subsets of a given structure. For example, in the case of \mathcal=(\mathbb,<) above, any translation of \mathcal is an automorphism preserving the empty set of parameters, and thus it is impossible to define any particular integer in this structure without parameters in \mathcal. In fact, since any two integers are carried to each other by a translation and its inverse, the only sets of integers definable in \mathcal without parameters are the empty set and \mathbb itself. In contrast, there are infinitely many definable sets of pairs (or indeed ''n''-tuples for any fixed ''n'' > 1) of elements of \mathcal: (in the case ''n'' = 2) Boolean combinations of the sets \ for m \in \mathbb Z. In particular, any automorphism (translation) preserves the "distance" between two elements.


Additional results

The Tarski–Vaught test is used to characterize the elementary substructures of a given structure.


References

*Hinman, Peter. ''Fundamentals of Mathematical Logic'', A K Peters, 2005. *Marker, David. ''Model Theory: An Introduction'', Springer, 2002. * Rudin, Walter. ''Principles of Mathematical Analysis'', 3rd. ed. McGraw-Hill, 1976. * Slaman, Theodore A. and Woodin, W. Hugh. ''Mathematical Logic: The Berkeley Undergraduate Course''. Spring 2006. {{Authority control Model theory Logic Mathematical logic