(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(x_{1},x_{2},...,x_{n}) of natural numbers is said to be **definable** in N iff there is a formula f(x_{1},...,x_{n}) in the language of arithmetic such that for every n_{1},...,n_{k}, R(n_{1},...,n_{k}) holds if and only if f(n_{1},...,n_{k}) is entailed by N (by "entailed by" i mean "is a semantic consequence of")

Note: I've been a bit informal here, by using n_{1},...,n_{k} 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...