Consider a language L that contains the following items:

1. An in?nite set E whose elememts are called the expressions of L. 2. A subset S of E whose elements are called the sentences of L. 3. A subset P of S whose elements are called the provable sentences of L. 4. A subset R of S whose elements are called the refutable (sometimes disprovable) sentences of L. 5. A set H of expressions whose elements are called the predicates of L. 6. A function ? that assigns to every expression E and every natural number n an expression E(n), where E(n) is a sentence. 7. A subset T of sentences whose elements are called the true sentences of L.

The word number shall mean natural number. We will say that a predicate H is true for a number n or that n satis?es H if H(n) is a true sentence. By the set expressed by H, we mean the set of all n that satisfy H. Thus for any set A of numbers, H expresses A if and only if for every number n: H(n) ?T ? n ? A. A set A is called expressible or nameable in L if A is expressed by some predicate of L. The system L is called correct if every provable sentence is true and every refutable sentence is false. We let g be a 1-1 function which assigns to each expression E a natural number g(E) called the Godel number of E. We assume that every number is the Godel number of an expression. Assuming now that every number n is the Godel number of a unique expression, we let En be that expression whose Godel number is n. Thus, g(En) = n. By the diagonalization of En we will mean the expression En(n). If En is a predicate, then its diagonalization is a sentence; this sentence is true i? the predicate En is satis?ed by its own Godel number n. For any n, we let d(n) be the Godel number of En(n). We use the term number-set to mean set of (natural) numbers. For any number set A, by A? we shall mean the set of all numbers n such that d(n) ? A. Thus for any n, the equivalence n ? A? ? d(n) ? A holds. We let P be the set of Godel numbers of all the provable sentences. For any number set A, by its complement A, we mean the complement of A relative to the set N of natural numbers. Call a sentence En a Godel sentence for a number set A if either En is true and its Godel number n lies in A, or En is false and its Godel number lies outside A. Thus, En is a Godel sentence for A i? the following condition holds: En ?T ? n ? A.

Show that for any set A, if A? is expressible in L, then there is a Godel sentence for A.