- #1
hatsu27
- 10
- 0
Homework Statement
Let S be the theory with no NONlogical symbols and no NONlogical axioms.
Show that ~~(x = x) V ~(x = x) is a theorem of S NOT provable without propositional axioms.
Homework Equations
Let ƒ be a mapping from the set of formulas to the set of truth values such that ƒ(A) = T for A atomic; ƒ(~A) = F; ƒ(A V B) = ƒ(B); ƒ(∃xA) = T. Show that if A is provable without propositional axioms then ƒ(A) = T.
The Attempt at a Solution
OK, so here are my thoughts:First I assumed that A = ~~(x = x) V ~(x = x) which is itself a propositional axiom, but then if that is so than what is B? so then should I set A = ~~(x = x) and B= ~(x = x)? now then can I use contradiction to prove this? Set ƒ(A) = F, then f(~A) = T and then ƒ(A V B) = ƒ(B) would allow ƒ(B) to be true since A is false. This also makes sense since ~A is really just B and ~A is true. But then (A V B) = (A V ~A) which is a propositional axiom-- the very thing I am not supposed to use!
So then I thought: suppose (A V B) and B are valid then ƒ(A V B) = ƒ(B) = T. then breaking down ƒ(A V B) then ƒ(A) = T or ƒ(B) = T. Now we know that ƒ(B) = T because it is part of our supposition, but since ƒ(∃xA) = T and ƒ(~A) = F then ƒ(A) must also be true.
Third thought was suppose ƒ(B) = F, then ƒ(A V B) = ƒ(B) = F then the only was for
ƒ(A V B) = F to be valid is if both A and B are false, but since we know that ƒ(∃xA) = T then
(A V B) cannot = F and since B does = F then A must = T therefore ƒ(A) = T.
Now I now that there is faulty logic in each of these scenarios, but am I close somewhere? Also how does showing ƒ(A) = T prove that I need propositional axioms to prove
~~(x =x) V ~(x = x)? Am I even on the right track here? How does one show something is not provable? It's easy to show provability, I only need one instance to make something true, I don't know how to do it the other way around!
PS- this problem comes from Shoenfield's Mathematical Logic book.