Definable Sets of ($\mathbb{Z};<$)

Question

I came across this question "Prove that a subset $S$ of $\mathbb{Z}$ is definable in the structure $(\mathbb{Z};<)$ if and only if $S=\emptyset $ or $S=\mathbb{Z}$."

I found something on the wikipedia page (http://en.wikipedia.org/wiki/Definable_set), but I would like some elaboration. I'm not sure what parameters mean here in the article, which is probably why I don't understand the explanation.

My own attempt to understand goes something like that: if $S$ is definable, then there exists a formula such that the truth is preserved by elements of $S$. Since any two integers are "connected" by the translation function, if $a$ belongs to $S$, then $a+k$ for all $k \in \mathbb{Z}$ is also in $S$, hence $S=\mathbb{Z}$. Also, the formula $\exists v_1<(v_1,v_1)$ defines the empty set.

Am I right? How do I prove the converse?

Answer 1

To answer your various questions:

1. Parameters mean additional free variables which are fixed when considering this. For example $\{k\in\Bbb Z\mid k<0\}$ is definable using the parameter $0$.

   But usually definable means definable without parameters (although in some contexts, like set theory, definable might mean definable with parameters).

2. Your solution is right. If $a\in S$, then the translation by $k$ preserves truth values, so $a+k\in S$. Therefore either $S=\Bbb Z$ or $S=\varnothing$.

   More generally we consider functions which are bijections of the structure's universe with itself and preserve the interpretation of the symbols in the language (in this case, $f(x)<f(y)\iff x<y$). These are called automorphisms, and we can show that if $A$ is a definable set, then for any automorphism, $f(A)=A$. Precisely because these preserve truth values.

   Your argument was essentially this. Whether or not you have verified that $f_k(a)=a+k$ is indeed an automorphism is a different question, but it's not hard to show that it is indeed a bijection of $\Bbb Z$ with itself, and preserves the order.

3. The other direction? You mean showing that there is a formula which defines $\Bbb Z$ (you already gave one defining $\varnothing$). I'm sure that you can think about a formula that is satisfied by all the members of $\Bbb Z$.

Answer 2

Notice that if a set is definable in a structure then it is fixed (set-wise) under automorphisms. Since $x \to x+1$ is an automorphism of $(\mathbb{Z},<)$ fixes no subsets except $\emptyset$ and $\mathbb{Z}$, you have your result.