FRIEDMAN-WEIERMANN STYLE INDEPENDENCE RESULTS BEYOND PEANO ARITHMETIC
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We expose a pattern for establishing Friedman-Weiermann style independence results according to which there are thresholds of prov- ability of some parameterized variants of well-partial-ordering. For this purpose, we investigate an ordinal notation system for ϑΩ ω , the small Ve- blen ordinal, which is the proof-theoretic ordinal of the theory (Π1/2-BI)0. We also show that it sometimes suffices to prove the independence w.r.t. PA in order to obtain the same kind of independence results w.r.t. a stronger theory such as (Π1/2-BI)0.
Abstract
We expose a pattern for establishing Friedman-Weiermann style independence results according to which there are thresholds of prov- ability of some parameterized variants of well-partial-ordering. For this purpose, we investigate an ordinal notation system for ϑΩ ω , the small Ve- blen ordinal, which is the proof-theoretic ordinal of the theory (Π1/2-BI)0. We also show that it sometimes suffices to prove the independence w.r.t. PA in order to obtain the same kind of independence results w.r.t. a stronger theory such as (Π1/2-BI)0.
참고문헌 (21)
- W. Buchholz, "Kruskals Theorem impliziert WF(ϑΩω)", Notes in German, ~ (1993)
- S. N. Burris, "Number theoretic density and logical limit laws" (2001), American Mathematical Society
- D. H. J. de Jongh, "Well-partial orderings and hierarchies", Indag. Math, 39(3), pp.195~207 (1977)
- R. L. Graham, "Concrete Mathematics" (1994), Addison-Wesley
- F. Harary, "Twenty-step algorithm for determining the asymptotic number of trees of various species", J. Austral. Math. Soc. Ser. A, 20(4), pp.483~503 (1975)
- J. B. Kruskal, "Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture", Trans. Amer. Math. Soc, 95, pp.210~225 (1960)
- G. Lee, "Phase transitions in axiomatic thought", PhD, pp.2005
- G. Lee, "A comparison of well-known ordinal notation systems for ε0", Ann. Pure Appl. Logic, 147(1-2), pp.48~70 (2007)
- I. Lepper, "Simplification Orders in Term Rewriting", PhD, pp.2001
- A. I. Markushevich, "Theory of functions of a complex variable. Vol. II" (1965), Prentice-Hall Inc.
- R. Otter, "The number of trees", Ann. of Math. (2), 49, pp.583~599 (1948)
- F. Pelupessy, "Phase transition results for three ramsey-like theorems", Notre Dame J. of Formal Logic, to appear, ~
- M. Rathjen, "Proof-theoretic investigations on Kruskal's theorem", Ann. Pure Appl. Logic, 60(1), pp.49~88 (1993)
- D. Schmidt, "Well-Partial Orderings and Their Maximal Order Types" (1979), Habilitationsschrift
- R. Sedgewick, "An introduction to the Analysis of Algorithms" (1996), Addison-Wesley
- S. G. Simpson, "Nonprovability of certain combinatorial properties of finite trees, In Harvey Friedman's research on the foundations of mathematics", Stud. Logic Found. Math., 117, pp.87~117 (1985)
- R. L. Smith, "The consistency strengths of some finite forms of the Higman and Kruskal theorems, In Harvey Friedman's research on the foundations of mathematics", Stud. Logic Found. Math., 117, pp.119~136 (1985)
- R. P. Stanley, "Generating functions, In Studies in combinatorics", MAA Stud. Math, 17, pp.100~141 (1978), Math. Assoc. America
- O. Veblen, "Continuous increasing functions of finite and transfinite ordinals", Trans. of the Amer. Math. Soc, 9(3), pp.280~292 (1908)
- A. Weiermann, "An application of graphical enumeration to PA", J. Symbolic Logic, 68(1), pp.5~16 (2003)
- H. S. Wilf, "Generating Functionology" (1994), Academic Press Inc.