[FOM] Strong theorems and Z2

[Joe Shipman]

What are the best known lower and upper bounds for the proof strength of the Graph Minor Theorem, expressed in terms of the logical complexity of the sentences of Second Order Arithmetic to which induction or comprehension axioms must be applied? Does the answer to this question change if we take Friedman's "miniaturization" of the theorem, which is a statement of First Order Arithmetic?

What is the most famous theorem of "Ordinary Mathematics" which can be stated but not proven in Second Order Arithmetic?

-- JS

Sent from my iPhone