Book contents
- Frontmatter
- Preface
- Contents
- Possible m-diagrams ofmodels of arithmetic
- Weak theories of nonstandard arithmetic and analysis
- Notions of compactness in weak subsystems of second order arithmetic
- Proof-theoretic strength of the stable marriage theorem and other problems
- Free sets and reversemathematics
- Interpreting arithmetic in the r.e. degrees under Σ4-induction
- Reverse mathematics, Archimedean classes, and Hahn's Theorem
- The Baire category theoremover a feasible base theory
- Basic applications of weak König's lemma in feasible analysis
- Maximal nonfinitely generated subalgebras
- Metamathematics of comparability
- A note on compactness of countable sets
- A survey of the reversemathematics of ordinal arithmetic
- Reversemathematics and ordinal suprema
- Did Cantor need set theory?
- Models of arithmetic: quantifiers and complexity
- Higher order reversemathematics
- Arithmetic saturation
- WQO and BQO theory in subsystems of second order arithmetic
- Reverse mathematics and graph coloring: eliminating diagonalization
- Undecidable theories and reversemathematics
- Π01 sets and models of WKL0
- Manipulating the reals in RCA0
- Reverse mathematics and weak systems of 0-1 strings for feasible analysis
- References
Reverse mathematics and graph coloring: eliminating diagonalization
Published online by Cambridge University Press: 31 March 2017
Edited by
Book contents
- Frontmatter
- Preface
- Contents
- Possible m-diagrams ofmodels of arithmetic
- Weak theories of nonstandard arithmetic and analysis
- Notions of compactness in weak subsystems of second order arithmetic
- Proof-theoretic strength of the stable marriage theorem and other problems
- Free sets and reversemathematics
- Interpreting arithmetic in the r.e. degrees under Σ4-induction
- Reverse mathematics, Archimedean classes, and Hahn's Theorem
- The Baire category theoremover a feasible base theory
- Basic applications of weak König's lemma in feasible analysis
- Maximal nonfinitely generated subalgebras
- Metamathematics of comparability
- A note on compactness of countable sets
- A survey of the reversemathematics of ordinal arithmetic
- Reversemathematics and ordinal suprema
- Did Cantor need set theory?
- Models of arithmetic: quantifiers and complexity
- Higher order reversemathematics
- Arithmetic saturation
- WQO and BQO theory in subsystems of second order arithmetic
- Reverse mathematics and graph coloring: eliminating diagonalization
- Undecidable theories and reversemathematics
- Π01 sets and models of WKL0
- Manipulating the reals in RCA0
- Reverse mathematics and weak systems of 0-1 strings for feasible analysis
- References
Summary
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
- Type
- Chapter
- Information
- Reverse Mathematics 2001 , pp. 331 - 348Publisher: Cambridge University PressPrint publication year: 2005
References
[1] , Effective coloration,The Journal of Symbolic Logic, vol. 41 (1976), pp. 469–480.
[2] , On-line chain partitions of orders,Theoretical Computer Science, vol. 175 (1997), pp. 283–292.
[3] and , Reverse mathematics and recursive graph theory,Mathematical Logic Quarterly, vol. 44 (1998), pp. 465–473.
[4] and , On-line and first-fit colorings of graphs,Journal of Graph Theory, vol. 12 (1988), pp. 217–227.
[5] and , First-fit and on-line chromatic number of families of graphs,Ars Combinatoria, vol. 29C (1990), pp. 168–176.
[6] , Jr., Degrees of functions with no fixed points,Logic, methodology and philosophy of science, VIII (Moscow, 1987) (, , and , editors), North-Holland, Amsterdam, 1989, pp. 191–201.
[7] , An effective version of Dilworth's theorem,Transactions of the American Mathematical Society, vol. 268 (1981), pp. 63–77.
[8] , Recursive and on-line graph coloring,Handbook of recursive mathematics, vol. 2, North-Holland, Amsterdam, 1988, pp. 1233–1269.
[9] , Coloring graphs on-line,Online algorithms (Schloss Dagstuhl, 1996), Lecture Notes in Computer Science, vol. 1442, Springer, Berlin, 1998, pp. 281–305.
[10] , , and , On-line graph coloring and recursive graph theory,SIAMJournal on DiscreteMathematics, vol. 7 (1994), pp. 72–89.
[11] , First-fit and on-line coloring of graphs which do not induce P 5, SIAM Journal on Discrete Mathematics, vol. 8 (1995), pp. 485–498.
[12] and , An extremal problem in recursive combinatorics,Congressus Numerantium, vol. 33 (1981), pp. 143–153.
[13] , On the decomposition of graphs,Studia Scientiarum Mathematicarum Hungarica, vol. 1 (1966), pp. 237–238.
[14] and , Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall),Proceedings of the London Mathematical Society. Third Series, vol. 25 (1972), pp. 615–654.
[15] and , Effective matchmaking and k-chromatic graphs, Proceedings of the American Mathematical Society, vol. 39 (1973), pp. 371–378.
[16] , Recursive colorings of graphs,Canadian Journal of Mathematics, vol. 32 (1980), pp. 821–830.
[17] , Graph coloring and reverse mathematics,Mathematical Logic Quarterly, vol. 46 (2000), pp. 543–548.
[18] , Subsystems of second order arithmetic, Perspectives inMathematical Logic, Springer-Verlag, 1998.
- 2
- Cited by