PROBLEMS

Problems

22.1Does it follow from the fact that xFx & x Fx is satisfiable that X( xXx &x Xx) is valid?

22.2Let us write R ab to abbreviate

X[Xa & x y((X x & Rx y) → X y) → Xb].

Show that the following are valid:

(a)R aa

(b)Rab → R ab

(c)(R ab & R bc) → R ac

Suppose Rab if and only if a is a child of b. Under what conditions do we have

R ab?

22.3(A theorem of Frege) Show that (a) and (b) imply (c):

(a)x y z[(Rx y & Rx z) → y = z]

(b)x(R xa & R xb)

(c)(R ab a = b R ba).

22.4Write ♦(R) to abbreviate

x y( w(Rw x & Rwy) → z(Rx z & Ryz)).

Show that ♦(R) → ♦(R*) is valid.

22.5(The principle of Russell’s paradox) Show that X y x(X x ↔ Rx y) is valid.

22.6(A problem of Henkin) Let Q1 and Q2 be as in section 16.2, and let I be the induction axiom of Example 22.6. Which of the eight combinations {( )Q1, ( )Q2, ( )I }, where on each of the three sentences the negation sign may be present or absent, are satisfiable?

22.7Show that the set of (code numbers of) second-order sentences true in the standard model of arithmetic is not analytical.

22.8Show that PII is not logically equivalent to any first-order sentence.

22.9Show that for any firstor second-order sentence A of the language of arithmetic, either PII & A is equivalent to PII, or PII & A is equivalent to 0 = 0.

22.10Show that the set of (code numbers of) second-order sentences that are equivalent to first-order sentences is not analytical.

22.11Prove the Craig interpolation theorem for second-order logic.

the expansion of N that assigns G as denotation the set A. And we say a class of sets of numbers is arithmetically definable if and only if there is a sentence F(G) of LG such that is precisely the set of A for which F(G) is true in NAG .

The following two results contrast with Tarski’s theorem to the effect that V is not arithmetically definable.

23.1Theorem. For each n, Vn is arithmetically definable.

23.2Theorem. The class {V } whose one and only member is V is arithmetically definable.

This entire section will be devoted to the proofs. We are going to need certain facts about recursiveness (or the ‘arithmetization of syntax’):

(1)The set S of code numbers of the sentences of L is recursive.

(2)For each n, the set Sn of code numbers of sentences of L with no more than n occurrences of logical operators is recursive.

(3)There exists a recursive function ν such that if B is a sentence of L with code number b, then ν(b) is the code number of B.

(4)There exists a recursive function δ such that if B and C are sentences of L with code numbers b and c, then δ(b, c) is the code number of (B C).

(5)There exists a recursive function η such that if v is a variable with code numbers q and F(v) is a formula with code number p, then η( p, q) is the code number of

v F(v).

(6)There exists a recursive function σ such that if v, F(v), q, p are as in (5), then for any m, σ ( p, q, m) is the code number of F(m).

(7)The set V0 of atomic sentences of L that are true in N is recursive.

[We may suppose that ν, δ, η, σ take the value 0 for inappropriate arguments; for instance, if b is not the code number for a sentence, then ν(b) = 0.]

In every case, intuitively it is more or less clear that the set or function in question is effectively decidable or computable, so according to Church’s thesis they should all be recursive. Proofs not depending on appeal to Church’s thesis have been given for (1) and (3)–(6) in Chapter 15; and the proof for (2) is very similar and could easily have been included there as well (or placed among the problems at the end of that chapter).

As for (7), perhaps the simplest proof is to note that V0 consists of the elements of the recursive set S0 that are theorems of Q, and equivalently whose negations are not theorems of Q (since Q proves all true atomic sentences and disproves all false ones). But we know from Chapter 15 that the set of theorems of Q or any axiomatizable theory is a semirecursive set, and the set of sentences whose negations are not theorems is the complement of a semirecursive set. It follows that V0 is both a semirecursive set and the complement of one, and is therefore recursive.

The sets above all being recursive, they are definable in arithmetic and indeed in Q, and the functions are representable. Let S(x), S0(x), S1(x), S2(x), . . . , Nu(x, y), Delta(x, y, z), Eta(x, y, z), Sigma(x, y, z, w), and V 0(x) be defining or representing formulas for S, S0, S1, S2, . . . , ν, δ, η, σ , and V0. This machinery will be used in the proofs of both theorems.

Proof of Theorem 23.1: A sentence A that contains n + 1 logical operators is either the negation B of a sentence B containing n operators, or the disjunction B C of two sentences B and C each containing at most n operators, or else an existential quantification v F(v) of a formula F(v) containing n operators. In the last case, for each m, the sentence F(m) also contains n operators. In the first case A will be true if and only if B is not true. In the second case, A will be true if and only if B is true or C is true. In the third case, A will be true if and only if, for some m, F(m) is true.

In terms of Vn , we can therefore characterize Vn+1 as the set of those numbers a in Sn+1 such that either k is in Vn ; or for some b, a = ν(b) and b is not in Vn ; or for some b and c, a = δ(b, c) and either b is in Vn or c is in Vn ; or finally, for some p and q, a = η( p, q), and for some m, σ ( p, q, m) is in Vn . So if V n (x) arithmetically defines Vn , the following formula V n+1(x) arithmetically defines Vn+1:

Sn+1(x) & {V n (x) y[Nu(y, x) & V n (y)]

y z[Delta(y, z, x) & (V n (y) V n (z))]

y z[Eta(y, z, x) & u w(Sigma(y, z, u, w) & V n (w))]}.

Since we know V0 is arithmetically definable, it follows by induction that Vn is arithmetically definable for all n.

Proof of Theorem 23.2: The set of sentences true in N can be characterized as the unique set such that:

contains only sentences of L .

For any atomic sentence A, A is in if and only if A is a true atomic sentence. For any sentence B, B is in if and only if B is not in .

For any sentences B and C, (B C) is in if and only if B is in or C is in . For any variable v and formula F(v), v F(v) is in if and only if, for some m,

F(m)is in .

The set V of code numbers of sentences true in N can therefore be characterized as the unique set M such that:

For all b, if b is in M, then b is in S.

For all a, if a is in S0, then a is in M if and only if a is in V0.

For all b, if ν(b) is in S, then ν(b) is in M if and only if b is not in M.

For all b and c, if δ(b, c) is in S, then δ(b, c) is in M if and only if either b is in

Mor c is in M.

For all p and q, if η( p, q) is in S, then η( p, q) is in M if and only if, for some

m, σ ( p, q, m) is in M.

So on expanding L be adding the one-place predicate G, if we let F(G) be the conjunction

x(Gx → S(x)) &

x(S0(x) → (Gx ↔ V 0(x))) &

x y((Nu(x, y) & S(y)) → (Gy ↔ Gx)) &

x y z((Delta(x, y, x) & S(z)) → (Gz ↔ (Gx Gy))) &

x y z((Eta(x, y, z) & S(z)) → (Gz ↔ u w(Sigma(x, y, u, w) & Gw)))