Re: Enderton 3.5 Problem 1

Suppose that there is a recursive set R with these properties. Since it is recursive, it is representable in by some formula (lecture 12, slide 10). By the fixpoint theorem, there exists a formula such that . Thus, says that its Gödel number is not in R.

Consider two cases: and and use the fact that R is representable in by .

Re: Enderton 3.5 Problem 1

Quote:

Originally Posted by

**emakarov** Suppose that there is a recursive set R with these properties. Since it is recursive, it is representable in

by some formula

(lecture 12, slide 10). By the fixpoint theorem, there exists a formula

such that

. Thus,

says that its Gödel number is not in R.

Consider two cases:

and

and use the fact that R is representable in

by

.

Could you check if the following attempt is O.K?

Suppose there is a recursive set having the required properties. Suppose also some formula represent . By the fixed-point theorem, there exists a formula such that . Then, . Either or (This part is not clear). Since by hypothesis, we have .

Since , we also have and , contradicting that .

Therefore, no recursive set having the required properties exists.

Re: Enderton 3.5 Problem 1

Quote:

Originally Posted by

**logics** Suppose there is a recursive set

having the required properties. Suppose also some formula

represent

.

This does not need to be supposed; the assumption that R is recursive implies this. It would be better to say, "Let be the formula that represents R."

Quote:

Originally Posted by

**logics** By the fixed-point theorem, there exists a formula

such that

.

The fixpoint theorem does not guarantee that the fixpoint formula is a negation. More importantly, here is a fixpoint of , i.e., says, "I am in R." I am not sure it is possible to get a contradiction from this. The point of the fixpoint construction is to have a formula that says, informally,

"I am *not* in R" (*)

Then if is in R, then (*) means that is refutable, and all refutable formulas are not in R by the assumption about R. If, on the other hand, is not in R, then (*) means that is provable, and all provable formulas are in R. In both cases we get a contradiction.

I suggest you follow this plan.

Quote:

Originally Posted by

**emakarov** Consider two cases:

and

and use the fact that R is representable in

by

.