# Math Help - Axioms in Propositional Logic

1. ## Axioms in Propositional Logic

In my course on propositional logic, we are given the axioms:

1. p=>(q=>p)
2. (p=>(q=>r))=>((p=>q)=>(p=>r))
3. ¬¬p=>p

And, of course, modus ponens.

Why are these three chosen? Yes, you can use them to prove the completeness theorem, so in that respect they are useful. But I've never seen a proof that you can't deduce one of the three from the other two? (Without using the completeness theorem, obviously). Are these three independent? Are these three the maximum independent set of tautologies?

Thanks

2. I am pretty sure these axioms are independent. One way to prove this is to come up with a semantics where two axioms are true and truth is preserved by MP, but the third axiom is false.

The independence of the third axiom from the first two is well-known. The first two axioms give rise to the so-called minimal logic, which is a subsystem of intuitionistic logic, which itself is a proper subsystem of regular classical logic. It has several well-studied semantics, including Kripke models and Heyting algebras.

The latter link gives the following example of a Heyting algebra: the set {0, 1/2, 1} with the usual order and

$p\to q=
\begin{cases}
1 & \text{if p\le q}\\
q & \text{otherwise}
\end{cases}
$

and
$\neg p=p\to0=
\begin{cases}
1 & \text{if p=0}\\
0 & \text{otherwise}
\end{cases}
$

A formula is considered true (under a valuation that maps each propositional letter to one of the three truth values) if its value is 1. Let $p=1/2$. Then $\neg p=0$ and $\neg\neg p = 1$. However, $1\to 1/2=1/2$. It is left as an exercise to check that minimal logic is sound with respect to this semantics.

I believe that I saw in the "Introduction to Mathematical Logic" by Elliott Mendelson similar, but more ad-hoc, truth-table semantics that prove independence of the first two axioms. If I remember right, it also discusses alternative axiomatizations, including one with a single axiom. I may still have a copy somewhere, so if you can't find it in other places, ask here again.

3. Ok, that shows that with a strange valuation the law of double negative elimination is not semantically implied.

How does that relate to proving that the law of double negation is not provable, especially since we don't have a completeness theorem?

4. One has to prove that minimal logic (the first two axioms and MP) is sound w.r.t. this semantics. This will show that not only the axioms themselves, but all their corollaries are valid (i.e., true under any valuation of propositional letters). Since the law of double negation is not valid, it is not a corollary of the axioms.

Are these three the maximum independent set of tautologies?
This is what the completeness theorem says: every tautology is derivable from these axioms.

Why are these three chosen?
I've seen axiomatizations where the third axiom is (~A -> ~B) -> (B -> A), as, for example, here. They must be equivalent, but with Hilbert systems, it's hard to say for sure because it is very difficult to derive formulas in practice.

5. Ah, thank you. I understand now.