Paris-Harrington principles, reflection principles and transfinite induction up to \(\epsilon _ 0\) (Q1082336)

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.