A curious inference
The paper discusses the proof of a statement about a recursively defined rapidly increasing function. The hypotheses involve universal quantifiers and the statement is easily proved in second order logic. An estimate of the size of the set needed to replace the quantifiers by Gentzen cuts shows that the first order proof would need a number of symbols largely in excess of the number of atoms in the universe; such a proof cannot be written down. The author's conclusion is that this gives additional strength to the position that first order logic ought never to have been accorded canonical status as logic. \{The argument is mathematically sound but the conclusion is questionable. In mathematics and computer science one presupposes a sufficiently large supply of labels that allow one to use abbreviations (from the purely logical point of view these would transform the language used to a new one) and which bring the proof down to manageable size.\}
- A slow growing analogue to Buchholz' proof
- Reasoning with sentences and diagrams
- Hybridizing nonmonotonic inheritance with theorem proving
- Higher-order modal logics: automation and applications
- scientific article; zbMATH DE number 1550361 (Why is no real title available?)
- Non-elementary speed-ups in proof length by different variants of classical analytic calculi
- Naturalizing indispensability: a rejoinder to `The varieties of indispensability arguments'
- Formal and Natural Proof: A Phenomenological Approach
- Lemmas: generation, selection, application
- First-order reasoning and primitive recursive natural number notations
- Types, Tableaus and Gödel’s God in Isabelle/HOL
- Automation of Boolos' Curious Inference in Isabelle/HOL
- Boolos's Curious Inference in Isabelle/HOL
This page was built for publication: A curious inference
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091390)