CBL Puzzle # 7 A Maze of Axioms and Theorems (+ and - as well)


For any two-place relations P(a,b) and Q(a,b) define P/Q to mean that
there is an M such that Q(M,a) <=> P(a,a) for all values of a.

Define s(a,b) to be the wff that is formed by replacing the free
variable in wff number a with the value for number b. Define three
two-place relations:

PR(a,b) : s(a,b) is provable.
TW(a,b) : s(a,b) is true.
DIS(a,b) : s(a,b) is refutable.

Then P and Q can be any of the following: PR, TW, DIS, ~PR, ~TW, ~DIS,
PRvDIS, TW&~PR, etc.

The puzzle is to determine the value of P/Q for each pair of P and Q.
+P/Q will mean P/Q is true and -P/Q will mean that P/Q is false. We
will have to start with specific ones. To get everyone started, here
are a few.

1. ~PR/TW : This says that unprovability is expressible. This is the
premise of Godel's 1st. Incompleteness Theorem based on Soundness.

"Now we will define a class K of natural numbers as follows:
K = { n in N | ~provable(Rn(n))} where provable(x) means x is a
provable formula. With other words, K is the set of numbers n where
the formula Rn(n) that you get when you insert n into its own formula
Rn is improvable. Since all the concepts used for this definition are
themselves definable inPM, so is the compound concept K, i.e. there is
a class-sign S such that the formula S(n) states that n is in K."

So we see that + ~PR/TW in PA.

2. TW/TW : Is truth expressible? Tarski said no. So - TW/TW.

3. PR/PR : Is provability representable? Yes, Rosser relied on this
fact. So we see that + PR/PR.

Now, who can evaluate other expressions P/Q? And of course the grand
prize is for an algorithm to evaluate any P/Q.

C-B
.

Quantcast