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 \subsetneq C$ ("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}...