I'm trying to prove that $\lnot \lnot Q \to Q$ is not an intuitionistic tautology by constructing a special finitely-valued logic with strictly more tautologies than intuitonistic logic ... and then showing that that new logic rejects double negation elimination. Is this a valid proof technique?
In particular, there's a three-valued logic that accepts all the axioms of a specific axiomatization of intuitionistic logic (given below). Let's call it $L_3$ . In $L_3$ double negation elimination, i.e. $\lnot\lnot Q\to Q$ is not a tautology.
Can the existence of a logic whose tautologies are a strict superset of intuitionistic logic's tautologies be used to prove that a certain statement is a non-tautology in intuitionistic logic?
By plugging in all possible truth values for the metavariables in the axioms for intuitionistic logic, have I done enough work to show that $L_3$ "agrees" with intuitionistic logic in some sense?
Does it matter that $L_3$ has stray tautologies like triple negation elimination $\lnot\lnot\lnot Q \to Q$ ?
Let's write out the axioms of intuitionistic logic.
Then-1 $$ \phi \to (\chi \to \phi) $$ Then-2 $$ (\phi \to (\chi \to \psi)) \to ((\phi \to \chi) \to (\phi \to \psi)) $$ And-1 $$ (\phi \land \chi) \to \phi $$ And-2 $$ (\phi \land \chi) \to \chi $$ And-3 $$ \phi \to (\chi \to (\phi \land \chi)) $$ Or-1 $$ \phi \to (\phi \lor \chi) $$ Or-2 $$ \chi \to (\phi \lor \chi) $$ Or-3 $$ (\phi \to \psi) \to ((\chi \to \psi) \to ((\phi \lor \chi) \to \psi)) $$ EFQ $$ \bot \to \phi $$
The truth tables for our three-valued logic $L_3$ are as follows. The two designated truth values for our tautologies are $T$ and $U$ . Note that implication returns $U$ unless the right argument is $F$, in which case it cycles the three truth values.
AND OR IMP
F U T F U T F U T
(F) F F F (F) F U T (F) U U U
(U) F U U (U) U U T (U) T U U
(T) F U T (T) T T T (T) F U U
As we would hope, $Q \to (\lnot\lnot Q)$ is a tautology but $ (\lnot\lnot Q) \to Q $ is not.
Q→¬¬Q is a tautology, as in intuitionistic logic
T→¬¬T F→¬¬F U→¬¬U
T→ ¬F F→ ¬U U→ ¬T
T→ U F→ T U→ F
U U T
¬¬Q→Q is not a tautology, as in intuitionistic logic
L3 is finitely valued, so we can examine all the cases
¬¬T→T ¬¬F→F ¬¬U→U
¬F→T ¬U→F ¬T→U
U→T T→F F→U
U F U
For reference, here is a Python program I used to check the intuitionistic axioms and a few example tautologies and non-tautologies.
import itertools as it
F = "F"
T = "T"
U = "U"
domain = (F, U, T)
def and_(a, b):
ttab = {
F : {F:F, U:F, T:F},
U : {F:F, U:U, T:U},
T : {F:F, U:U, T:T},
}
return ttab[a][b]
def or_(a, b):
ttab = {
F : {F:F, U:U, T:T},
U : {F:U, U:U, T:T},
T : {F:T, U:T, T:T},
}
return ttab[a][b]
def imp_(a, b):
ttab = {
F : {F:U, U:U, T:U},
U : {F:T, U:U, T:U},
T : {F:F, U:U, T:U},
}
return ttab[a][b]
def is_true(x):
return x == T or x == U
def check_tautology(func, domain, args):
counterexample = None
for x in it.product(domain, repeat=args):
if not is_true(func(*x)):
counterexample = x
if counterexample is not None:
print(func.__name__, counterexample)
assert False
def check_non_tautology(func, domain, args):
counterexample = None
for x in it.product(domain, repeat=args):
if not is_true(func(*x)):
counterexample = x
if counterexample is None:
print(func.__name__, "is unexpectedly a tautology")
assert False
def then1(f, x):
return imp_(f, imp_(x, f))
check_tautology(then1, domain, 2)
def then2(f, x, p):
antecedent = imp_(f, imp_(x, p))
consequent = imp_(imp_(f, x), imp_(f, p))
return imp_(antecedent, consequent)
check_tautology(then2, domain, 3)
def and1(f, x):
return imp_(and_(f, x), f)
check_tautology(and1, domain, 2)
def and2(f, x):
return imp_(and_(f, x), x)
check_tautology(and2, domain, 2)
def and3(f, x):
return imp_(f, imp_(x, and_(f, x)))
check_tautology(and3, domain, 2)
def or1(f, x):
return imp_(f, or_(f, x))
check_tautology(or1, domain, 2)
def or2(f, x):
return imp_(x, or_(f, x))
check_tautology(or2, domain, 2)
def or3(f, x, p):
antecedent1 = imp_(f, p)
antecedent2 = imp_(x, p)
consequent = imp_(or_(f, x), p)
return imp_(antecedent1, imp_(antecedent2, consequent))
check_tautology(or3, domain, 3)
def efq(x):
return imp_(F, x)
check_tautology(efq, domain, 1)
# theorems and nontheorems
def double_negation_introduction(x):
return imp_(x, imp_(imp_(x, F), F))
check_tautology(double_negation_introduction, domain, 1)
def double_negation_elimination_BAD(x):
return imp_(imp_(imp_(x, F), F), x)
check_non_tautology(double_negation_elimination_BAD, domain, 1)
def contrapositive_introduction(x, p):
antecedent = imp_(x, p)
consequent = imp_(imp_(p, F), imp_(x, F))
return imp_(antecedent, consequent)
check_tautology(contrapositive_introduction, domain, 2)
def contrapositive_elimination_BAD(x, p):
consequent = imp_(x, p)
antecedent = imp_(imp_(p, F), imp_(x, F))
return imp_(antecedent, consequent)
check_non_tautology(contrapositive_elimination_BAD, domain, 2)