Throughout my course in Logic, I have not yet encountered a set that is definable with parameters. (Most of the examples are definable without parameters)

Is there a simple example of a set that is definable with parameters from a nonempty set $X$?

Also, what is the "motivation" or underlying idea of defining a set with parameters? I can understand the definition, but it seems devoid of any motivation.

My notes states that a subset $Y\subseteq M^n$ is definable in $\mathcal{M}=(M,I)$ with parameters from $X\subseteq M$ iff there are elements $b_1,\ldots ,b_m$ of $X$ and a formula $\varphi$ such that

(a) $\varphi$ has $n+m$ free variables, $x_{j_1},\ldots,x_{j_n},x_{k_1},\ldots,x_{k_m}$.

(b) For each $(a_1,\ldots,a_m)\in M^n$, $(a_1,\ldots,a_m)\in Y$ iff there exists an $\mathcal{M}$-assignment $\nu$ such that

(I) $\nu (x_{j_i})=a_i$ for all $1\leq i \leq n$

(ii) $\nu (x_{k_i})=b_i$ for all $1\leq i \leq m$

(iii) $(\mathcal{M},\nu)\models\varphi$

Sincere thanks for help!

  • 1
    $\begingroup$ If for every $p \in X$, the set $\{p\}$ is itself definable without parameters, then any set that is definable with parameters from $X$ is also definable without parameters. So let's assume that there is a $p \in X$ such that $\{p\}$ is not definable without parameters. Then $\{p\}$ would be a simple example of a set that is definable with parameters from $X$, but is not definable without parameters. Of course this example is not very interesting. To give a more interesting example, if might help to know what kind of structures $M$ you are interested in. $\endgroup$ – Trevor Wilson May 1 '13 at 19:12
  • $\begingroup$ By the way, any set that is definable without parameters is also definable with parameters. So your first sentence was rather surprising to me before I figured out what you meant to say :) $\endgroup$ – Trevor Wilson May 1 '13 at 19:13
  • $\begingroup$ Sorry for the confusion! What I meant is that is there any set that is definable with parameters but not definable without parameters? $\endgroup$ – yoyostein May 2 '13 at 13:51
  • $\begingroup$ @yoyostein: Sorry, what do you mean by the $I$ in $(M,I)$? Is $I$ just some collection of constant, relation, and function symbols? $\endgroup$ – Kyle Jul 14 '14 at 21:47

Here are some standard examples of definable sets which are not definable over the emptyset in one free variable.

We define $\varphi(\mathfrak{A})=$ the set which is defined by $\varphi$ in a model $\mathfrak{A}$.

$\mathbf{Example}$ $\mathbf{1}$: Let $L=\{E\}$ and let $T$ be the theory of infinitely many equivalence classes, each with infinitely many elements. Let $\mathfrak{A} \models T$. Note that here, the only definable sets are the emptyset and the entire model. However, let us adjoin a constant symbol for some element in each equivalence class. We now consider the definable sets over $(\mathfrak{A},a_i)_{i\in X}$ such that for each $a_i, a_j$ $a_iEa_j \iff i=j $. Now we can actually define each equivalence class in this model. We consider the formula $\varphi_i(x,a_i)=xEa_i$. Therefore, $|\varphi_i(\mathfrak{A})|=|M|$ and $\varphi_i(\mathfrak{A})\cap\varphi_j(\mathfrak{A})=\emptyset \iff i\neq j$. Now, we have infinitely many definable sets, each of coinfinite size, which (pairwise incompatibility) partition the elements of our model.

$\mathbf{Example}$ $\mathbf{2}$: Let $L=\{\leq\}$. We consider $\mathfrak{A}=\{\mathbb{N}+\mathbb{Z};\leq\}$. Our order type is the the natural numbers with a $\mathbb{Z}$-chain on the end. It is easy to show that all definable subsets over the emptyset are either finite or cofinite. Let us consdier the definable sets over $X=\{a\}$ where $a$ is greater than infinitely many elements of our model. What can we now define? Now we can define a coinfinite set. Note that for every element $x \in$ $\mathfrak{A}$, we know that there exists infinitely many elements larger than $x$. This follows since $\mathfrak{A}\equiv\{\mathbb{N};\leq\}$. Now, consider the formula $\varphi(x,a)=x\geq a$. Now $|\mathfrak{A}-\varphi(\mathfrak{A})|=|\varphi(\mathfrak{A})|=\aleph_0$. Therefore, this set, $\varphi(\mathfrak{A})$ was not definable before, but is now definable.

$\mathbf{Antiexample}$ $\mathbf{1}$: Let $L=\{+,\times,0,1\}$ and let $ACF_0$ be the theory of algebraically closed fields of characteristic zero. Let $\mathfrak{A}\models ACF_0$. We consider the definable sets in one free variable. Note that the only thing that you can say (atomically, in one free variable) is either equivalent $p(x)=0$ or $p(x)\neq 0$, where $p(x)$ is a polynomial. Now what are the definable sets? We can define every (algebraic) finite set and every cofinite set (containing all transcendentals in our model). If we have algebraic elements $a_1,...,a_n$, we have a polynomial definable in our language such that $p({\mathfrak{A}})=\{a_1,...,a_n\}$. However, there is no formula that will separate the transcendentals from our cofinite sets, i.e. $\neg p(\mathfrak{A})$ clearly contains every transcendental by definition. Note that to define an infinite set which does not contain any transendentals over any set of parameters (including the using our whole model as parameters) is impossible. Why? We can only say $p(x)=0$ or $\neg p(x)=0$. Since $\neg p(x) =0$ always defines a set with all the transcendental elements, it is useless. Since $p(x)=0$ only defines finitely many elements, then any finite disjunction (i.e. $[p(x)=0]\vee...\vee [q(x)=0]$) defines finitely many elements. Since there are infinitely many algebraic elements, we are done.

$\mathbf{Motivation}$ $\mathbf{1}$: The first type of motivation is classification. A theory $T$ is called strongly minimal if every definable sets in the model with parameters is either finite or cofinite. An example of this include algebraically closed fields of characteristic $p$ (essentially, stongly minimal theories is an anti-example to your question). Clearly classification is important since we can deal with collections of theories instead of working on each theory in particular. But this is just one side of the coin.

$\mathbf{Motivation}$ $\mathbf{2}$: Morely Rank is the other side. Morely Rank, informally, asks "How many infinite collections of pairwise incomparable definable sets are there in your model?". If you want, I can edit my post and define it, however, this can be found in Marker's text, Model Theory: An Introduction. For example, Example 1 has a Morely Rank of 1 (Rank starts at 0). As defined in the example, we can split the model into infinitely many sections, each non-intersecting. Then, we can do this again, and look at each (singleton) element in a particular equivalence class.

$\mathbf{Importance}$: Morely Rank and strongly minimal theories, as classification tools, were vital to the proof of Morley's Categoricity Theorem, namely, for all complete, first-order theories $T$ in a countable language, if $T$ is categorical in some uncountable power, then $T$ is categorical in all uncountable powers.

$\mathbf{Conclusion}$: In first-order logic, the possible definable sets and the number of pairwise incomparable definable sets gives rise to classification which in turns allows one to prove non-trivial theorems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.