On Gödel incompleteness and finite combinatorics
type: Item
instance of: scholarly article
title: On Gödel incompleteness and finite combinatorics
zbMATH Open document ID: 0627.03041
DOI: 10.1016/0168-0072(87)90074-1
author: Akihiro Kanamori
author: Kenneth McAloon
published in: Annals of Pure and Applied Logic
publication date: 1987-01-01T00:00:00Z
review text: This paper deals with a combinatorial principle which is independent of PA; this principle does not involve the notion of ``relatively large set'', and is stated as follows: Let m,n,K\(\in N\), \(X\subseteq N\); say that \(f:[X]^ n\to N\) is regressive iff \(fs<\min s\), whenever \(s\in [X]^ n\), and min s\(>0\). Also, say that \(H\leq X\) is min homogeneous for f iff \(fs=ft\) whenever \(s,t\in [H]^ n\) and min \(s\leq \min t\). As usual, let us identify each \(m\in N\) with \(\{\) \(n\in N:\) \(n<m\}\). Then: (*) For any n,k\(\in N\), there is an m such that for each regressive \(f:[m]^ n\to N\), there is a K-element subset H of m min homogeneous for f (we simply write: \(m\to (K)^ nreg\). Thus (*) is: \(\forall n,K \exists m:\) \(m\to (K)^ nreg).\) (*) is provable in ZF, because if follows from Erdős-Rado's Theorem: ``For each n and for each regressive \(f:[N]^ n\to N\), there is an infinite set \(H\subseteq N\), which is min homogeneous for f. Facts: i) (*) is proved to be independent of PA. (More precisely, it is shown to be provably equivalent to Paris-Harrington principle PH: \(\forall n,K,r \exists m\) \(m\to_{*}(K)^ n_ r)\). ii) The function \(\nu n=\mu z:z\to (2n)^ mreg\) eventually majorizes all prov. recursive functions. iii) The function \(\nu_ 0n=\mu z:z\to (n)^ 2reg\) has the same rate of amount as Ackermann's function. iv) Let \((PH)_{n+1}\) and \((*)_{n+1}\) denote the sentences resulting from PH and (*) by dropping the quantifier \(\forall n\) (i.e. by fixing the exponent n). Then \((PH)_{n+1}\) and \((*)_{n+1}\) are equivalent in \(I\Sigma_ 1\). The methods used are model-theoretical.
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03C62
zbMATH DE Number: 4019057
zbMATH Keywords: partition
zbMATH Keywords: independence of Peano Arithmetic
zbMATH Keywords: combinatorial principle
MaRDI profile type: Publication
full work available at URL: 0168-0072(87)90074-1
OpenAlex ID: W2036673058
cites work: A Combinatorial Theorem
cites work: Q3237252
cites work: Rapidly growing Ramsey functions
cites work: Q4138726
cites work: Accessible Independence Results for Peano Arithmetic
cites work: Q3912791
cites work: Q3912792
cites work: On the complexity of models of arithmetic
cites work: Q3926596
cites work: Some independence results for Peano arithmetic
cites work: Q3893931
cites work: Some strong axioms of infinity incompatible with the axiom of constructibility
Recommended article: Finite sets and Gödel's incompleteness theorems
Recommended article: Q5172389
Recommended article: Q4693596
Recommended article: Q3695280
Recommended article: Q3621607
Recommended article: On the incompleteness theorems
Recommended article: Gödel incompleteness, explicit expressions for complete arithmetic degrees and applications
Recommended article: On the Depth of Gödel’s Incompleteness Theorems
Recommended article: Infinite combinatorics and definability
Recommended article: Q4590669
description: scientific article; zbMATH DE number 4019057