Paris-Harrington principles, reflection principles and transfinite induction up to \(\epsilon _ 0\)
type: Item
instance of: scholarly article
title: Paris-Harrington principles, reflection principles and transfinite induction up to \(\epsilon _ 0\)
zbMATH Open document ID: 0603.03015
DOI: 10.1016/0168-0072(86)90072-2
author: Reijiro Kurata
published in: Annals of Pure and Applied Logic
publication date: 1986-01-01T00:00:00Z
review text: Let M and X be finite subsets of \(\omega\), k, e, r be positive integers. For a function \(f: \omega\to \omega\), we say that X is f-large if f(min X)\(\leq | X|\). \(M\to^{f}_{*}(k)^ e_ r\) means that for every partition P: (M)\({}^ e\to r\), there exists an \(X\subseteq M\) satisfying (1) X is homogeneous for P, (2) \(| X| \geq k\) and (3) X is f-large. Let \(f_ n\) be a fixed \(\Delta_ n\) function in PA such that \(f_ n\) dominate all \(\Delta_{n-1}\) functions in PA. Here, PA is Peano Arithmetic with all primitive recursive function symbols and their defining equations. \(PH_ n\) (extended Paris Harrington principle) means that for all \(e,k,r<\omega\), there exists an \(M\in \omega\) such that \(M\to^{f_ n}_{*}(k)^ e_ r\), where M is considered a finite set \(\{\) 0,1,2,...,M-1\(\}\). \(RFN_{(PA)-\Sigma_ n}\) means Reflexion Principle on PA for \(\Sigma_ n\) formulas. \(WOP_{\Delta_ n}\) (Well Ordering Principle for \(\Delta_ n)\) means that there is no strictly \(\prec\) descending infinite \(\Delta_ n\) sequence, where \(\prec\) means a primitive recursive well ordering on \({\mathbb{N}}\) which is isomorphic to \(\epsilon_ 0\). \(LSP_{\Delta_ n}\) (Large Set Principle for \(\Delta_ n)\) means that for all strictly increasing \(\Delta_ n\) functions and all \(m<\omega\) and \(\alpha <\epsilon_ 0\), there exists a number k such that f([m,k]) is \(\alpha\)-large (in Ketonen Solovay's sense). \(TI_{\epsilon_ 0-\Pi_ n}\) (Transfinite Induction up to \(\epsilon_ 0\) for \(\Pi_ n\) formulas in PA). Theorem: All of \(RFN_{(PA)-\Sigma_ n}\), \(PH_ n\), \(WOP_{\Delta_ n}\), \(LSP_{\Delta_ n}\) and \(TI_{\epsilon_ 0-\Pi_ n}\) are provably equivalent in PA.
Mathematics Subject Classification ID: 03E30
zbMATH DE Number: 3972852
zbMATH Keywords: Peano Arithmetic
zbMATH Keywords: primitive recursive function symbols
zbMATH Keywords: extended Paris Harrington principle
zbMATH Keywords: Reflexion Principle
zbMATH Keywords: Well Ordering Principle
zbMATH Keywords: Large Set Principle
zbMATH Keywords: Transfinite Induction
MaRDI profile type: Publication
full work available at URL: 0168-0072(86)90072-2
OpenAlex ID: W1970089323
cites work: Rapidly growing Ramsey functions
cites work: Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems
cites work: Q3343982
cites work: Provably recursive functions in fragments of Peano arithmetic
cites work: Q3671980
description: scientific article; zbMATH DE number 3972852