Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A formula provable without is a tautology

  1. Sep 15, 2010 #1
    How can I prove that:

    If a formula [tex]A[/tex] is provable without use of substitution axioms, nonlogical axioms, equality and identity axioms, and the [tex]\exists[/tex]-introduction rule, than [tex]A[/tex] is a tautology.

    I try to act this way: consider a tautology A and show that using propositional axioms I get another tautology, and that if the hypothesis of a rule are tautologies then also the conclusion is a tautology. But I don't know wether it is the correct way or not.
    Anyone can help me?
  2. jcsd
  3. Sep 15, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    A good way to start might be by induction

    If your proof is one step then what can A possibly be?

    Then if it's true for all proofs of less than or equal to n steps... for an n+1 step proof how would you proceed?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook