0

In Boolos, Burgess, and Jeffrey (2007, 5th edition), the following statement is found on p. 224:

"[Consider] that the set of sentences that are provable and the set of sentences that are disprovable from any recursive set of axioms is semirecursive, and that all recursive sets are definable by ∃-rudimentary formulas. It follows that there are formulas PrvT (x) and DisprvT (x) of forms ∃y PrfT (x, y) and ∃y DisprfT (x, y) respectively, with Prf and Disprf rudimentary, such that A is a theorem of T if and only if the sentence PrvT ( A ) is correct or true in the standard interpretation."

My question is this: Why does it follow from the first sentence in the quotation that Prf and Disprf are rudimentary? Actually, if you could just explain why Prf and Disprf must be rudimentary, that would suffice for my purposes... Thanks in advance.

nontology
  • 19
  • That's just the definition of "$\exists$-rudimentary" - saying that (for example) the set $P$ of provable sentences (from a fixed recursive set $T$ of axioms) is $\exists$-rudimentary means exactly that there is some rudimentary predicate $\varphi$ such that $P={n: \exists x\varphi(n,x)}$. – Noah Schweber Apr 26 '22 at 04:27
  • Sorry, I'm not sure I follow. An "∃ -rudimentary" predicate can be fronted by mulitple unbounded existential quantifiers. So if I am told that ∃x F is ∃ -rudimentary, it does not follow that F is rudimentary, for F could still be fronted by unbounded existential quantifiers. In which case, F fails to be rudimentary. Right? – nontology Apr 26 '22 at 04:58
  • Oh wait, sorry, I was confusing ∃ -rudimentary predicate with a "generalized" ∃ -rudimentary predicate. Sorry, thanks for the head's up. – nontology Apr 26 '22 at 05:03
  • Sorry, even after the clarification above, I'm still unclear on something. The passage from Boolos et al. starts in a way that seems to imply that the set of provable formulae is recursive. That of course is incorrect. Regardless, I understand that the provability predicate is ∃-rudimentary, given that the proof predicate is ∃ -rudimentary – nontology Aug 05 '22 at 08:28

0 Answers0