Incompleteness in Finite Combinatorics

Serafim Batzoglou
Additional contact information
Serafim Batzoglou: Seer Inc.

Chapter Chapter 8 in Introduction to Incompleteness, 2024, pp 133-154 from Springer

Abstract: Abstract There exist recursive functions over ℕ $$\mathbb {N}$$ that grow so quickly that PA cannot prove their totality. In 1977, Paris and Harrington introduced such a function PH ( n , k , l ) $$\mathrm {PH}(n, k, l)$$ , which can be represented in PA but where ( ∗ ) : = $$(*) :=$$ “ ∀ n , k , l ∃ ! m PH ( m , n , k , l ) $$\forall n,k,l \: \exists ! m \: \mathrm {PH}(m, n, k, l)$$ ” is true over ℕ $$\mathbb {N}$$ but not provable in PA.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-031-64217-3_8

Ordering information: This item can be ordered from
http://www.springer.com/9783031642173

DOI: 10.1007/978-3-031-64217-3_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().