No Cover Image

Journal article 1148 views

Ordinal notations and well-orderings in bounded arithmetic

Arnold Beckmann Orcid Logo, Chris Pollett, Samuel R Buss

Annals of Pure and Applied Logic, Volume: 120, Issue: 1-3, Pages: 197 - 223

Swansea University Author: Arnold Beckmann Orcid Logo

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.1016/S0168-0072(02)00066-0

Abstract

Ordinal notations and provability of well-foundedness have been a central tool in the study of the consistency strength and computational strength of formal theories of arithmetic. This development began with Gentzen's consistency proof for Peano arithmetic based on the well-foundedness of ordi...

Full description

Published in: Annals of Pure and Applied Logic
ISSN: 0168-0072
Published: 2003
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa13723
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2013-07-23T12:10:47Z
last_indexed 2018-02-09T04:44:36Z
id cronfa13723
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2013-10-17T11:51:01.9368103</datestamp><bib-version>v2</bib-version><id>13723</id><entry>2012-12-17</entry><title>Ordinal notations and well-orderings in bounded arithmetic</title><swanseaauthors><author><sid>1439ebd690110a50a797b7ec78cca600</sid><ORCID>0000-0001-7958-5790</ORCID><firstname>Arnold</firstname><surname>Beckmann</surname><name>Arnold Beckmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2012-12-17</date><deptcode>SCS</deptcode><abstract>Ordinal notations and provability of well-foundedness have been a central tool in the study of the consistency strength and computational strength of formal theories of arithmetic. This development began with Gentzen's consistency proof for Peano arithmetic based on the well-foundedness of ordinal notations up to &#x3B5;0 . Since the work of Gentzen, ordinal notations and provable well-foundedness have been studied extensively for many other formal systems, some stronger and some weaker than Peano arithmetic. In the present paper, we investigate the provability and non-provability of well-foundedness of ordinal notations in very weak theories of bounded arithmetic, notably the theories S i 2 and T i 2 with 1 &#x2264; i &#x2264; 2 . We prove several results about the provability of well-foundedness for ordinal notations; our main results state that for the usual ordinal notations for ordinals below &#x3B5;0 and &#x393;0 , the theories T i 2 and S 2 2 can prove the ordinal &#x3A3; b 1 - minimization principle over a bounded domain. PLS is the class of functions computed by a polynomial local search to minimize a cost function. It is a corollary of our theorems that the cost function can be allowed to take on ordinal values below &#x393;0 , without increasing the class PLS .</abstract><type>Journal Article</type><journal>Annals of Pure and Applied Logic</journal><volume>120</volume><journalNumber>1-3</journalNumber><paginationStart>197</paginationStart><paginationEnd>223</paginationEnd><publisher/><placeOfPublication/><issnPrint>0168-0072</issnPrint><issnElectronic/><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2003</publishedYear><publishedDate>2003-12-31</publishedDate><doi>10.1016/S0168-0072(02)00066-0</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2013-10-17T11:51:01.9368103</lastEdited><Created>2012-12-17T10:31:05.9240183</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author><author><firstname>Chris</firstname><surname>Pollett</surname><order>2</order></author><author><firstname>Samuel R</firstname><surname>Buss</surname><order>3</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2013-10-17T11:51:01.9368103 v2 13723 2012-12-17 Ordinal notations and well-orderings in bounded arithmetic 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2012-12-17 SCS Ordinal notations and provability of well-foundedness have been a central tool in the study of the consistency strength and computational strength of formal theories of arithmetic. This development began with Gentzen's consistency proof for Peano arithmetic based on the well-foundedness of ordinal notations up to ε0 . Since the work of Gentzen, ordinal notations and provable well-foundedness have been studied extensively for many other formal systems, some stronger and some weaker than Peano arithmetic. In the present paper, we investigate the provability and non-provability of well-foundedness of ordinal notations in very weak theories of bounded arithmetic, notably the theories S i 2 and T i 2 with 1 ≤ i ≤ 2 . We prove several results about the provability of well-foundedness for ordinal notations; our main results state that for the usual ordinal notations for ordinals below ε0 and Γ0 , the theories T i 2 and S 2 2 can prove the ordinal Σ b 1 - minimization principle over a bounded domain. PLS is the class of functions computed by a polynomial local search to minimize a cost function. It is a corollary of our theorems that the cost function can be allowed to take on ordinal values below Γ0 , without increasing the class PLS . Journal Article Annals of Pure and Applied Logic 120 1-3 197 223 0168-0072 31 12 2003 2003-12-31 10.1016/S0168-0072(02)00066-0 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2013-10-17T11:51:01.9368103 2012-12-17T10:31:05.9240183 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1 Chris Pollett 2 Samuel R Buss 3
title Ordinal notations and well-orderings in bounded arithmetic
spellingShingle Ordinal notations and well-orderings in bounded arithmetic
Arnold Beckmann
title_short Ordinal notations and well-orderings in bounded arithmetic
title_full Ordinal notations and well-orderings in bounded arithmetic
title_fullStr Ordinal notations and well-orderings in bounded arithmetic
title_full_unstemmed Ordinal notations and well-orderings in bounded arithmetic
title_sort Ordinal notations and well-orderings in bounded arithmetic
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
Chris Pollett
Samuel R Buss
format Journal article
container_title Annals of Pure and Applied Logic
container_volume 120
container_issue 1-3
container_start_page 197
publishDate 2003
institution Swansea University
issn 0168-0072
doi_str_mv 10.1016/S0168-0072(02)00066-0
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 0
active_str 0
description Ordinal notations and provability of well-foundedness have been a central tool in the study of the consistency strength and computational strength of formal theories of arithmetic. This development began with Gentzen's consistency proof for Peano arithmetic based on the well-foundedness of ordinal notations up to ε0 . Since the work of Gentzen, ordinal notations and provable well-foundedness have been studied extensively for many other formal systems, some stronger and some weaker than Peano arithmetic. In the present paper, we investigate the provability and non-provability of well-foundedness of ordinal notations in very weak theories of bounded arithmetic, notably the theories S i 2 and T i 2 with 1 ≤ i ≤ 2 . We prove several results about the provability of well-foundedness for ordinal notations; our main results state that for the usual ordinal notations for ordinals below ε0 and Γ0 , the theories T i 2 and S 2 2 can prove the ordinal Σ b 1 - minimization principle over a bounded domain. PLS is the class of functions computed by a polynomial local search to minimize a cost function. It is a corollary of our theorems that the cost function can be allowed to take on ordinal values below Γ0 , without increasing the class PLS .
published_date 2003-12-31T03:15:41Z
_version_ 1763750278789595136
score 11.035634

Similar Items