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
be a first-order language,
an
-structure with domain
,
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
, and
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
is ''definable in
with parameters from
'' if and only if there exists a formula
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