(context:
logic;
first-order logic)
Suppose that N is the standard structure of arithmetic (i.e. the natural numbers with addition, multiplication and the 'less than' relation) and L is a language of N. Then a relation R(x1,x2,...,xn) of natural numbers is said to be definable in N iff there is a formula f(x1,...,xn) in the language of arithmetic such that for every n1,...,nk, R(n1,...,nk) holds if and only if f(n1,...,nk) is entailed by N (by "entailed by" i mean "is a semantic consequence of")
Note: I've been a bit informal here, by using n1,...,nk as both natural numbers themselves, and the symbols for those natural numbers in the language of arithmetic.
So what does this mean? Basically, a relation is definable if you can define it using the formal language of arithmetic. A set S, then, is arithmetically definable iff there is a definable relation R that holds exactly on members of S.
Tarski has shown that the 'truth relation' True(x) that holds iff x is the Godel number of a true statement in the language of arithmetic (x is the Godel number of a sentence X such that N entails X) is in fact not arithmetically definable (I might include that proof here sometime soon). Essentially, Tarski has demonstrated that you can't define the notion of truth from "within" the language being considered--you must "step outside" of the language to do it. (See also: Godel's Theorem)
Is this clear (I mean to those of you who haven't already studied a lot of it before)? Please /msg me and let me know...