Some uses of dilators in combinatorial problems. III: Independence results by means of decreasing F-sequences (F weakly finite dilator) (Q913788): Difference between revisions

[For Part I see Logic and combinatorics, Proc. AMS-IMS-SIAM Conf., Arcata/Calif. 1985, Contemp. Math. 65, 25-53 (1987; Zbl 0634.03057). Part II is reviewed above (see Zbl 0701.03027).] Recently, some strictly mathematical statements about natural numbers have been discovered which are true but not provable in PA (Peano arithmetic) [cf., e.g., \textit{L. Kirby} and \textit{J. Paris}, Bull. Lond. Math. Soc. 14, 285-293 (1982; Zbl 0501.03017); \textit{J. Paris} and \textit{L. Harrington}, Handbook of mathematical logic, 1133-1142 (1977; Zbl 0443.03001)]. In this paper, by using methods of \(\Pi\) \({}^ 1_ 2\)-logic [cf. \textit{J.-Y. Girard}, Ann. Math. Logic 21, 75-219 (1981; Zbl 0496.03037)] and results obtained in Part I about decreasing F-sequences (F weakly finite dilator), we present a general method which enables us to obtain strictly mathematical statements about natural numbers which are true but not provable in (some extension of) PA. - Moreover, through this general method and by using a functional construction of the Veblen hierarchy [cf. \textit{J.-Y. Girard} and \textit{J. Vauzeilles}, J. Symb. Logic 49, 713- 729 (1984; Zbl 0568.03027)], we show another combinatorial theorem not provable in PA and the first example of a combinatorial theorem not provable in PA \(+\) ``truth definition for PA''.