1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Logic- How to show something is NOT provable?

  1. Aug 10, 2014 #1
    1. The problem statement, all variables and given/known data
    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.


    2. Relevant 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.


    3. 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.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Aug 12, 2014 #2
    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.
     
    Last edited: Aug 12, 2014
  4. Aug 12, 2014 #3
    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:redface:

    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?
     
  5. Aug 12, 2014 #4
    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?
     
  6. Aug 12, 2014 #5
    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?
     
  7. Aug 12, 2014 #6
    Correct, because that's what ##f## does to negations of atomic formulas.

    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)##?

    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.

    Here you're getting closer, saying a lot of things that are true and relevant but not necessarily for the right reasons.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Logic- How to show something is NOT provable?
Loading...