Logic- How to show something is NOT provable?

[hatsu27]

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.

 

[gopher_p]

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.

Presumably, you're permitted to use the theorem listed under "Relevant equations"?

If so, let $f$ be as in the theorem; i.e. (and I'm using different symbols for a reason here) $f(a)=T$ and $f(\lnot a)=F$ for $a$ atomic and $f(b\lor c)=f(c)$ for all formulas $b$ and $c$.

1. What kind of formula is $x=x$?
2. What can you say about $f(x=x)$?
3. What can you say about $f\big(\lnot(x=x)\big)$?

4. Supposing, towards a contradiction, that $\lnot\lnot(x=x)\lor\lnot(x=x)$ is provable without propositional axioms, what can you say, based on the theorem, about $f\big(\lnot\lnot(x=x)\lor\lnot(x=x)\big)$?
5. What does your answer in 4 say about $f\big(\lnot(x=x)\big)$ (remember $f(b\lor c)=f(c)$)?

Remark 1: The $f$ from the theorem is not a "truth function". However this fact is not relevant to the problem.
Remark 2: It is completely unnecessary in this problem to use the "meanings" of the symbols $\lnot,\lor,T,F$. In fact, presuming to know what those symbols "mean" is likely to lead to some confusion.

 

[hatsu27]

First off thank you for responding- I really appreciate your help- I am taking this as an independent study course and with no lectures and a Prof. who doesn't have a lot of time for me it can be frustrating and lonely! If anything it is nice to have someone just answer a question

Ok so I have been trying to think about your questions without seeing the meanings of not, or, T, F.

1) x = x is an equality formula such that every natural number is equal to itself.
2) ƒ(x = x) then is a function in which every natural number in this particular function is equal to itself.
3) ƒ(~(x = x)) is also an equality function? Since I am to ignore the ~, it is still just an equality function as in (2).

4) so then ƒ(~~(x = x) V ~(x = x)) is also just an equality function? It doesn't matter what is going on around it x will always equal x?
5) then, well I'm not sure what you mean here so I figure I am looking at this all wrong, but again maybe same concept as above? that x will equal what you set it to no matter what since you define x yourself?

I guess the way I look at the formula (~~(x = x) V ~(x = x)) is that it is similar to ∃xA, allowing some of the meanings to come back in, there are some times that (x = x) works and other times when it doesn't. Am I looking at this in the wrong way again?

 

[gopher_p]

Ok. Your answers are not what I expected.

The $x$ that is written in my post (and I'm guessing the text that you're reading) is basically a variable symbol of the formal language that we're working with. At present, it is completely meaningless. Similarly, the $=$ in the formula $x=x$ is a meaningless (for now) logical symbol that is treated like a binary relation symbol; that is for all variables $x$ and $y$, the string $x=y$ is a well-formed/valid formula in the empty language (i.e. the language with no non-logical symbols). In fact ...

(1) $x=x$ is an atomic formula in the empty language.

Now $f$ is a function whose domain consists of formulas in that language. $f(x=x)$ is the result of applying that function to the formula $x=x$. Since $x=x$ is atomic and we have presupposed that $f(a)=T$ for all atomic $a$, we can say that

(2) $f(x=x)=T$.

Now is that enough to get you going on the rest of my questions?

 

[hatsu27]

Ok I will try again (thanks for your patience with me)

1) x=x just an atomic formula
2) ƒ(x = x) = T
3) ƒ(~(x = x)) = F
4) then (~~(x = x) V ~(x = x)) is a wff, a string of atomic formulae?
5) then remembering ƒ(B V C) = ƒ(C) : ƒ(~~(x = x) V ~(x = x)) = ƒ(~(x = x))...?

4) Then again maybe because (~~(x = x) V ~(x = x)) is a wff, so ƒ(~~(x = x) V ~(x = x)) = T
5) and if that's true then if ƒ(~~(x = x) V ~(x = x)) = ƒ(~(x = x)) = T, then ƒ(~(x = x)) is just the function of a wff as well so it = T, thus we have contradiction?

Is this closer?

 

[gopher_p]

3) ƒ(~(x = x)) = F

Correct, because that's what $f$ does to negations of atomic formulas.

4) then (~~(x = x) V ~(x = x)) is a wff, a string of atomic formulae?

Well, yes. All wffs are built from atomic formulas. I wouldn't call it a string of formulas. From what I can tell looking at the first few pages of your text on Amazon, my string is the same as his expression.

Here we're supposing, in order to hopefully derive a contradiction, that this particular wff is provable without propositional axioms. What does $f$ do to formulas that are provable without propositional axioms? What does that say about $f\big(\lnot\lnot(x=x)\lor\lnot(x=x)\big)$?

5) then remembering ƒ(B V C) = ƒ(C) : ƒ(~~(x = x) V ~(x = x)) = ƒ(~(x = x))...?

Right. Now put that together with what you (hopefully) discovered in (4) and tell me what $f\big(\lnot(x=x)\big)$ is. Remember, we're trying to get a contradiction, so your answer here will likely contradict an earlier answer.

4) Then again maybe because (~~(x = x) V ~(x = x)) is a wff, so ƒ(~~(x = x) V ~(x = x)) = T
5) and if that's true then if ƒ(~~(x = x) V ~(x = x)) = ƒ(~(x = x)) = T, then ƒ(~(x = x)) is just the function of a wff as well so it = T, thus we have contradiction?

Is this closer?

Here you're getting closer, saying a lot of things that are true and relevant but not necessarily for the right reasons.