Results 1 to 5 of 5

Math Help - Axioms in Propositional Logic

  1. #1
    Junior Member
    Joined
    Jul 2008
    Posts
    28

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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=<br />
\begin{cases}<br />
1 & \text{if $p\le q$}\\<br />
q & \text{otherwise}<br />
\end{cases}<br />
    and
    \neg p=p\to0=<br />
\begin{cases}<br />
1 & \text{if $p=0$}\\<br />
0 & \text{otherwise}<br />
\end{cases}<br />
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2008
    Posts
    28
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2008
    Posts
    28
    Ah, thank you. I understand now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. propositional logic
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 30th 2011, 09:52 AM
  2. Propositional Logic
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 1st 2011, 03:22 PM
  3. propositional logic
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: August 3rd 2010, 11:52 AM
  4. Propositional Logic--Please help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 6th 2007, 05:25 AM
  5. propositional logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 10th 2007, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum