definable sets
   HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
, a definable set is an ''n''-ary relation on the domain of a structure whose elements satisfy some formula in the
first-order language First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
of that structure. A set 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 of M, and m a
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
. 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/math> :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 free variable is a notation (symbol) that specifies places in an expression where substitution may take place and is not ...
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 (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 ...
\ 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 (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
without parameters in the structure \mathcal=(\mathbb,<) consisting of the integers with the usual ordering (see the section on automorphisms 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 set In mathematical logic, an arithmetical set (or arithmetic 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. The definition can be ...
s, 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 In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers ...
. These hierarchies reveal many relationships between definability in this structure and computability theory, and are also of interest in descriptive set theory.


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 distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
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)s is called a
definitional extension In mathematical logic, more specifically in the proof theory of first-order theories, extensions by definitions formalize the introduction of new symbols by means of a definition. For example, it is common in naive set theory to introduce a symbol ...
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 rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be ...
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 \ldots" can be viewed as a question "When is there an x such t ...
. 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 automorphisms. :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 which 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, since 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 W. Hugh Woodin. ''Mathematical Logic: The Berkeley Undergraduate Course''. Spring 2006. {{Authority control Model theory Logic Mathematical logic