Bounded Arithmetic in Free Logic
One of the central open questions in bounded arithmetic is whether Buss' hierarchy of theories of bounded arithmetic collapses or not. In this paper, we reformulate Buss' theories using free logic and conjecture that such theories are easier to handle. To show this, we first prove that Bus...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2012-08-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/863/pdf |
| _version_ | 1827322915668885504 |
|---|---|
| author | Yoriyuki Yamagata |
| author_facet | Yoriyuki Yamagata |
| author_sort | Yoriyuki Yamagata |
| collection | DOAJ |
| description | One of the central open questions in bounded arithmetic is whether Buss'
hierarchy of theories of bounded arithmetic collapses or not. In this paper, we
reformulate Buss' theories using free logic and conjecture that such theories
are easier to handle. To show this, we first prove that Buss' theories prove
consistencies of induction-free fragments of our theories whose formulae have
bounded complexity. Next, we prove that although our theories are based on an
apparently weaker logic, we can interpret theories in Buss' hierarchy by our
theories using a simple translation. Finally, we investigate finitistic G\"odel
sentences in our systems in the hope of proving that a theory in a lower level
of Buss' hierarchy cannot prove consistency of induction-free fragments of our
theories whose formulae have higher complexity. |
| first_indexed | 2024-04-25T01:36:26Z |
| format | Article |
| id | doaj.art-3b08339847664f4783297053cdaa5e41 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:26Z |
| publishDate | 2012-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-3b08339847664f4783297053cdaa5e412024-03-08T09:28:00ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742012-08-01Volume 8, Issue 310.2168/LMCS-8(3:7)2012863Bounded Arithmetic in Free LogicYoriyuki YamagataOne of the central open questions in bounded arithmetic is whether Buss' hierarchy of theories of bounded arithmetic collapses or not. In this paper, we reformulate Buss' theories using free logic and conjecture that such theories are easier to handle. To show this, we first prove that Buss' theories prove consistencies of induction-free fragments of our theories whose formulae have bounded complexity. Next, we prove that although our theories are based on an apparently weaker logic, we can interpret theories in Buss' hierarchy by our theories using a simple translation. Finally, we investigate finitistic G\"odel sentences in our systems in the hope of proving that a theory in a lower level of Buss' hierarchy cannot prove consistency of induction-free fragments of our theories whose formulae have higher complexity.https://lmcs.episciences.org/863/pdfmathematics - logiccomputer science - logic in computer sciencecs.lo |
| spellingShingle | Yoriyuki Yamagata Bounded Arithmetic in Free Logic Logical Methods in Computer Science mathematics - logic computer science - logic in computer science cs.lo |
| title | Bounded Arithmetic in Free Logic |
| title_full | Bounded Arithmetic in Free Logic |
| title_fullStr | Bounded Arithmetic in Free Logic |
| title_full_unstemmed | Bounded Arithmetic in Free Logic |
| title_short | Bounded Arithmetic in Free Logic |
| title_sort | bounded arithmetic in free logic |
| topic | mathematics - logic computer science - logic in computer science cs.lo |
| url | https://lmcs.episciences.org/863/pdf |
| work_keys_str_mv | AT yoriyukiyamagata boundedarithmeticinfreelogic |