On the structure of initial segments of models of arithmetic
type: Item
instance of: scholarly article
title: On the structure of initial segments of models of arithmetic
zbMATH Open document ID: 0678.03026
DOI: 10.1007/BF01633984
author: Jan Krajíček
author: Pavel Pudlák
published in: Archive for Mathematical Logic
publication date: 1989-01-01T00:00:00Z
review text: If M is a model of arithmetic and a is an element of M, then \(<a^ M\) denotes the initial segment of all elements of M which are less than a. The question considered in the paper is: for which functions f(x) the structure \(<a^ M\) (where \(+\) and \(\cdot\) are ternary relations on \(<a^ M)\) determines \(<f(a)^ M?\) The authors improve upon earlier results of Paris, Dimitracopoulos, Hájek and Solovay by showing that for every countable model M of a sufficiently strong theory T (extending \(I\Delta_ 0+\exp)\) and every nonstandard a and c in M there is a model K of T which agrees with M up to a and contains a proof of contradiction of T whose Gödel number is less than \(\exp (a^ c)\), where \(\exp (x)=2^ x\). The paper also contains a variant of the above result dealing with consistency statements for fragments of the form \(I\Sigma_ n\) and a discussion of improvements of upper bounds for proofs of inconsistency under additional assumptions about complexity classes.
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03H15
Mathematics Subject Classification ID: 03C62
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 4110686
zbMATH Keywords: length of proof
zbMATH Keywords: complexity classes
reviewed by: Roman Kossak
MaRDI profile type: Publication
cites work: Q3856756
cites work: Q3755452
cites work: Q3773878
Recommended article: Theories of initial segments of standard models of arithmetics and their complete extensions
Recommended article: Some remarks on initial segments in models of Peano arithmetic
Recommended article: Models of Peano arithmetic as modules over initial segments
Recommended article: Q3762319
Recommended article: Subsets of models of arithmetic
Recommended article: Q5484945
Recommended article: Q3781756
Recommended article: Models of arithmetic in \(A\)-isols
Recommended article: Q3128124
Recommended article: Theories of arithmetics in finite models
description: scientific article; zbMATH DE number 4110686