Tuesday, 5 March 2019

proof writing - On provability within minimal logic

In its most naive form my question boils down to this:




when is a proposition that is provable "by contradiction" also provable "directly"?




IOW, is it possible to know, a priori, that a proposition p, if it's provable at all, it can only be proved by contradiction (and therefore that it would be futile to attempt a direct proof)?







Let me try to sharpen my question slightly, by using the terminology and definitions given in this MSE answer. Let C be the set1 of all propositions that are provable using classical logic. Similarly, let M be all the propositions that are provable using minimal logic. Then, according to the cited post, M ("there are statements that are provable by contradiction that are not provable directly"), or IOW, C\backslash M \neq \varnothing.



So my question can be rephrased like this: given some proposition p \in C, is it possible to know, a priori (i.e. without necessarily finding a "direct proof" of p), whether p \in M\;?



In my very limited experience, proofs of results like "C\backslash M \neq \varnothing" are very unsatisfying because they rarely illuminate the question of whether a particular p of interest belongs to M or to C\backslash M. Is there any theorem from the standard mathematical curriculum but outside of mathematical logic that is known to belong to C\backslash M.






1 or class, or family, or whatever works!

No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...