Logic (L system)

• Oct 5th 2010, 05:19 PM
DavyHilbert
Logic (L system)
Let A be a well-formed statement of L and let L+ be the extension of L obtained by including A as a new axiom. Prove that the set of theorems of L+ is different from the set of theorems of L if and only if A is not a theorem of L.
• Oct 5th 2010, 08:44 PM
DavyHilbert
is it begging the question to say that since adding A to L increases Thm(L) that A is not a tautology and thus is not an element of L?
• Oct 6th 2010, 04:12 AM
emakarov
This is pretty clear, so it may be hard to find precisely correct words to justify it.

Quote:

Prove that the set of theorems of L+ is different from the set of theorems of L if and only if A is not a theorem of L.
The right-to-left direction is obvious.

Quote:

since adding A to L increases Thm(L) that A is not a tautology and thus is not an element of L
"Tautology" is the wrong word because it has to do with semantics, while here were are talking about derivability (i.e., syntax) only. If you replace "tautology" with "theorem", than this is what you need to show; I don't see how you simplified things.

The left-to-right direction can be shown by contradiction using this property: If $\vdash_L A$ and $A\vdash_L B$, then $\vdash_L B$ (here $\vdash_L$ denotes derivability in L). How this property is proved depends on the specifics of L.
• Oct 8th 2010, 01:38 AM
PiperAlpha167
Quote:

Originally Posted by DavyHilbert
Let A be a well-formed statement of L and let L+ be the extension of L obtained by including A as a new axiom. Prove that the set of theorems of L+ is different from the set of theorems of L if and only if A is not a theorem of L.

Presumably, system L is decidable; otherwise, I think we won't have an effective method for determining exactly what's in Thm(L) and Thm(L+).
If, in addition, the definitions of theorem and proof in system L are given in the usual way, then an axiom is a theorem with a one-line proof.

In such a system, I think both directions of the claim should go through pretty easily.

For example, in the => direction, argue the contrapositive.
That is, assume A is in Thm(L), and show then that the collection of theorems of the "extended" system L+, i.e., Thm(L+), must be identical with Thm(L).
• Oct 8th 2010, 01:49 AM
emakarov
Quote:

Presumably, system L is decidable; otherwise, I think we won't have an effective method for determining exactly what's in Thm(L) and Thm(L+).
One does not have to assume decidability of L to prove the claim in the OP; this assumption is never used in the proof sketch above.