Definable set

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 first-order 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. 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 first-order 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. Let L {displaystyle {mathcal {L}}} be a first-order language, M {displaystyle {mathcal {M}}} an L {displaystyle {mathcal {L}}} -structure with domain M {displaystyle M} , X {displaystyle X} a fixed subset of M {displaystyle M} , and m {displaystyle m} a natural number. Then: Let N = ( N , < ) {displaystyle {mathcal {N}}=(mathbb {N} ,<)} be the structure consisting of the natural numbers with the usual ordering. Then every natural number is definable in N {displaystyle {mathcal {N}}} without parameters. The number 0 {displaystyle 0} is defined by the formula φ ( x ) {displaystyle varphi (x)} stating that there exist no elements less than x: φ = ¬ ∃ y ( y < x ) , {displaystyle varphi = eg exists y(y<x),} and a natural n > 0 {displaystyle n>0} is defined by the formula φ ( x ) {displaystyle varphi (x)} stating there exist exactly n {displaystyle n} elements less than x: φ = ∃ x 0 ⋯ ∃ x n − 1 ( x 0 < x 1 ∧ ⋯ ∧ x n − 1 < x ∧ ∀ y ( y < x → ( y ≡ x 0 ∨ ⋯ ∨ y ≡ x n − 1 ) ) ) {displaystyle varphi =exists x_{0}cdots exists x_{n-1}(x_{0}<x_{1}land cdots land x_{n-1}<xland forall y(y<x ightarrow (yequiv x_{0}lor cdots lor yequiv x_{n-1})))} In contrast, one cannot define any specific integer without parameters in the structure Z = ( Z , < ) {displaystyle {mathcal {Z}}=(mathbb {Z} ,<)} consisting of the integers with the usual ordering (see the section on automorphisms below). Let N = ( N , + , ⋅ , < ) {displaystyle {mathcal {N}}=(mathbb {N} ,+,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. 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. Let R = ( R , 0 , 1 , + , ⋅ ) {displaystyle {mathcal {R}}=(mathbb {R} ,0,1,+,cdot )} 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: