Open main menu

Wikipedia β

In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the language 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.

Contents

DefinitionEdit

Let   be a first-order language,   an  -structure with domain  ,   a fixed subset of  , and   a natural number. Then:

  • A set   is definable in   with parameters from   if and only if there exists a formula   and elements   such that for all  ,
  if and only if  
The bracket notation here indicates the semantic evaluation of the free variables in the formula.
  • A set   is definable in   without parameters if it is definable in   with parameters from the empty set (that is, with no parameters in the defining formula).
  • A function is definable in   (with parameters) if its graph is definable (with those parameters) in  .
  • An element   is definable in   (with parameters) if the singleton set   is definable in   (with those parameters).

ExamplesEdit

The natural numbers with only the order relationEdit

Let   be the structure consisting of the natural numbers with the usual ordering. Then every natural number is definable in   without parameters. The number   is defined by the formula   stating that there exist no elements less than x:

 

and a natural   is defined by the formula   stating there exist exactly   elements less than x:

 

In contrast, one cannot define any specific integer without parameters in the structure   consisting of the integers with the usual ordering (see the section on automorphisms below).

The natural numbers with their arithmetical operationsEdit

Let   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. If the structure is considered in second-order logic 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, and are also of interest in descriptive set theory.

The field of real numbersEdit

Let   be the structure consisting of the field of real numbers. 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:

 

Thus any   is nonnegative if and only if  . In conjunction with a formula that defines the additive inverse of a real number in  , one can use   to define the usual ordering in  : for  , set   if and only if   is nonnegative. The enlarged structure  s 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 of   has quantifier elimination. 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 automorphismsEdit

An important result about definable sets is that they are preserved under automorphisms.

Let   be an  -structure with domain  ,  , and   definable in   with parameters from  . Let   be an automorphism of   which is the identity on  . Then for all  ,
  if and only if  

This result can sometimes be used to classify the definable subsets of a given structure. For example, in the case of   above, any translation of   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  . In fact, since any two integers are carried to each other by a translation and its inverse, the only sets of integers definable in   without parameters are the empty set and   itself. In contrast, there are infinitely many definable sets of pairs (or indeed n-tuples for any fixed n>1) of elements of  , since any automorphism (translation) preserves the "distance" between two elements.

Additional resultsEdit

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

ReferencesEdit

  • 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.