Re: Provable in T?

MoeBlee wrote:
Aatu Koskensilta wrote:
The theory ISigma_1 is just Robinson arithmetic + induction for Sigma_1
formulas.

Would you specify what a Sigma_1 formula is?

A Sigma_1 formula is a formula of the form

ExP(x)

where P(x) contains only bounded quantifiers.

ISigma_1 is stronger than PRA and Robinson arithmetic.

What does the 'I' stand for in 'ISigma_1'?

Induction.

Is ISigma_1 in some sense the least theory to which the incompleteness
theorem applies?

It's in a sense the weakest natural theory to which the second incompleteness theorem applies. Robinson arithmetic, for example, does not satisfy the derivability conditions - it does not prove its consistency, though, but the proof is somewhat more involved than for theories which do.

And should I take it that there's no common theory that is between Robinson
arithmetic and ISigma_1 in terms of strength?

There are any number of such theories, obtained e.g. by omitting some instances of the induction axiom schema for Sigma_1 formulas.

--
Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
.

Loading