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 structure. A set can be defined with or without parameters, which are elements of the domain that can be referenced in the formula defining a set. Note that a unary relation on the domain of a structure is simply a subset of the domain, and when we refer to the definable sets in a structure we often mean the definable subsets of the domain. Formally,
For a given first-order language L, let M be an L-structure with domain M and X ⊆ M. We say that A ⊆ M^m is definable in M with parameters from X if and only if there exists a formula p(x_1, ..., x_m, y_1, ..., y_n) and elements b_1, ..., b_n ∈ X such that for all a_1, ..., a_m ∈ M,
(a_1, ..., a_m) ∈ A if and only if M |= p[a_1, ..., a_m, b_1, ..., b_n]
(Note that the bracket notation above indicates the semantic evaluation of the free variables in the formula.) We say that A is definable in M without parameters if and only if it is definable in M with parameters from the empty set.
Reference:
http://en.wikipedia.org/wiki/Definable_set
