# What is definability in First-Order Logic?

Can someone explain to me the definition of definability in first-order logic in simple terms and with an example? I would appreciate this. I just want to really understand this.

Thank you.

Here is the definition I have.

Definability in an Interpretation

Let $I = (D,(\cdot)^{I})$ be a first-order interpretation and $\phi$ be a first-order formula. A set $B$ of $k$-tuples over $D$, i.e. $B \subseteq D^{k}$, is defined by the formula $\phi$ if $B = \{ (\theta(x_{1}),\theta(x_{2}),\ldots,\theta(x_{k})) \,|\, (I,\theta) \models \phi \}$.

A set $B$ is definable in first-order logic if it is defined by some first-order formula $\phi$.

-

Basically for a set to be definable means that it can be "defined" by a formula in your language.

To be more precise let $\mathbf{M}$ be an $\mathcal{L}$-structure. Then a subset $N \subset M^k$ (where $M$ is the underlying set of $\mathbf{M}$) is definable if there is some $\mathcal{L}$-formula $\varphi(x)$ so that $$\mathbf{M} \models \varphi(\underline{a}) \iff a \in N$$

This is actually very restrictive though, and so we want to expand our class of definable sets a little bit. To do this we can extend our language by adding some names for elements in $M$ and use the same definition but where $\varphi(x)$ is a formula in our new expanded language. (Some people might call this definable with paramaters)

For example suppose we have the language $\mathcal{L} = \{ \leq \}$ where $\leq$ is a binary relation symbol.

We can take a structure $\mathbf{Z} = (\mathbb{Z}, \leq)$ where $\leq$ is interpreted as the standard ordering on $\mathbb{Z}$.

We may want to know if we can define $\mathbb{N}$

We can do this by adding in a name for $0$ to our language, call if $\underline{0}$. Then we can define the formula $$\varphi(x) \equiv x \geq \underline{0}$$ You can see that $$\mathbf{Z} \models \varphi(\underline{a}) \iff a \geq 0 \iff a \in \mathbb{N}$$ So $\varphi(x)$ defines $\mathbb{N}$ in $\mathbf{Z}$ (with the parameter $0$).

-
Thank you for the response –  Masterminder Dec 8 '12 at 23:18
@Masterminder no problem, feel free to let me know if anything is still unclear. –  Deven Ware Dec 8 '12 at 23:33
so the way I can also look at this is that it is a mapping to an extent? phi(x) , where x is from N, and phi(x) will give you an element from the set M? Correct me if I am wrong –  Masterminder Dec 10 '12 at 1:48
@Masterminder I just updated to change my notation slightly so it may be more clear what we're saying. It's not that $\varphi$ is a map, but rather it is a formula. And this formula is satisfied by an element if and only if that element is in $N$ –  Deven Ware Dec 10 '12 at 5:16

Let $L$ be a first-order language. For definiteness, we will assume that $L$ has the constant symbols $O$ and $U$, and two binary function symbols, the "addition" symbol $+$ and the "multiplication" symbol $\times$. We make expressions with these using the symbols conventionally, in the middle, rather than in front like they should be in principle.

There is a huge variety of $L$ structures for this particular language $L$. We will only mention two important ones.

One such $L$-structure is set $\mathbb{N}$, the non-negative integers, with $+$ interpreted as ordinary addition, $\cdot$ as ordinary multiplication, $O$ as the number $0$, and $U$ as the number $1$.

Now consider the one free variable formula $\varphi(x)$ below: $$\lnot(x=U)\land \forall y\forall z(x=y\times z \implies (y=U\lor z=U)).$$ The subset of $\mathbb{N}$ defined by this formula is the set of all elements of $\mathbb{N}$ at which $\varphi$ is true.

If we read the formula carefully, interpreted in $\mathbb{N}$, it says that $x\ne 1$, but if two elements of $\mathbb{N}$ have product equal to $x$, then at least one of the elements is $1$. So we can see that the subset of $\mathbb{N}$ defined (described) by this formula is the set of all primes.

Look at the very same sentence, but change the $L$ structure, to the reals $\mathbb{R}$ under the usual addition and multiplication, with $O$ and $U$ interpreted as before. A bit of thinking will show that there are no real numbers at which $\varphi(x)$ is true. So if our $L$-structure is the reals, then the subset of $\mathbb{R}$ defined by $\varphi(x)$ is just the empty set.

Back to $\mathbb{N}$. Consider the formula $\psi(x,y)$ below: $$\exists z (x\times z=y).$$ The ordered pairs $(x,y)\in \mathbb{N}^2$ for which $\psi(x,y)$ holds are precisely the ordered pairs such that $x$ divides $y$. The set of all ordered pairs $(a,b)$ defined by $\psi(x,y)$ is precisely the set of ordered pairs such that $a$ divides $b$.

We say that a subset $A$ of $\mathbb{N}$ is definable if there is a formula $\varphi(x)$ of our language such that $a\in A$ precisely if, under the usual interpretation, $\varphi$ is true at $a$.

Similar considerations hold for subsets of $\mathbb{N}^2$, $\mathbb{N}^3$, and so on.

Informally, a definable subset of $\mathbb{N}$ is a set completely specifiable by a formula in our formal language. Ditto for subsets of $\mathbb{N}^2$ (binary relations), of $\mathbb{N}^3$, and so on.

It turns out that for example, the set of all pairs $(a,b)$ such that $b=2^a$ is a definable subset of $\mathbb{N}^2$. . This is not at all obvious. It takes a good deal of work to come up with an appropriate formula. Indeed, all the sets and relations we use in elementary number theory are definable in this language, but this takes a great deal of work to show.

By way of contrast, if for the same language we use the structure $\mathbb{R}$, or the structure $\mathbb{C}$ (the complex numbers), the definable subsets do not form a very rich collection.

Despite the fact that the definable subsets of $\mathbb{N}$, and of $\mathbb{N}^2$, include essentially all one needs for number theory, most subsets of $\mathbb{N}$ are not definable. This is most easily seen by noting that there are only countably many formulas, but there are uncountably many subsets of $\mathbb{N}$.

I am afraid this is only a start!

-
thanks a lot sir –  Masterminder Dec 8 '12 at 23:17