Having trouble with the forward direction of this proof. I assume that the decision problem for implication is solvable, so that for any set of sentences $T$, I can arrive at a yes or no answer to whether or not for any sentence $A$, $T \models A$.

I'm having trouble thinking of a way to prove this. I need to think of a sentence $A$ that can help me decide whether $T$ is valid or not. I've tried letting $A$ be a sentence that is true in every interpretation but that leads me nowhere since even if we knew $T \models A$, there could still be a member of $T$ that is false. Letting $A$ be a sentence that is false would be useful for showing that the decision problem for satisfiability is solvable, but this is not the case.

Any help that would lead me to being able to prove this would be greatly appreciated! Thanks in advance.

  • 2
    $\begingroup$ I'm not sure I understand. Isn't the decision problem for validity just the decision problem for implication where $T=\emptyset$ (so this is the trivial direction)? It might be good to give a precise definition of the two problems in the question. $\endgroup$ – spaceisdarkgreen Apr 12 at 1:47
  • $\begingroup$ @spaceisdarkgreen you were exactly right, it was right in front of my face but I had trouble understanding it. In an example proof given by my prof she used a sentence that was always false to show that the set was satisfiable or not unsatisfiable, and I was trying to follow what she did. What you commented is what I was looking for after all. $\endgroup$ – MattyS11 Apr 12 at 17:40

You want to show that if you can solve the problem of that takes a (finite?) set of sentences $T$ and a sentence $A$ and returns whether or not $T\vDash A$, then you can solve the problem that takes a sentence $A$ and returns whether or not $\vDash A$?

You can either solve the second problem using the first by setting $T = \emptyset$, or, if that is not allowed for some reason, let $T = \{p \lor \neg p\}$ (or any set of tautologies).

The meaty direction of the proof is the other way, using problem two to solve problem one.

  • $\begingroup$ I don't think I can set $T$ to anything, I think my prof wants us to prove this for ANY set $T$ using some sentence $A$ and the fact that $T \models A$. The example proof she gave us was: if the decision problem for implication is solvable, then the decision problem for satisfiability is solvable, and she let $A$ be a sentence that isn't true in any interpretation, and used this to show that if $T \models A$, then $T$ is unsatisfiable, and if $T \nvDash A$, then $T$ is satisfiable. I think she wants us to approach the proof in this way. $\endgroup$ – MattyS11 Apr 12 at 5:47
  • $\begingroup$ @MattyS11 If you fix $T$ ahead of time I don't think it works any more. For instance let $T = \{p, \neg p\}$. $T$ is unsatisfiable, so $T\vDash A$ is true for every $A$, so your solver always outputs "True". How can you use this to solve the problem for validity? Your solver, in this case, can't help you because you could always just replace an appeal to the solver with "True". $\endgroup$ – James Apr 12 at 15:32
  • $\begingroup$ @MattyS11 also note that your professor did the same thing that I did: she took a solver that takes two inputs $T$ and $A$ and defined an new solver that only takes $T$ by setting $A$ equal to any fixed unsatisfiable sentence. The procedure I outline just sets $T$ to be a constant rather than $A$. $\endgroup$ – James Apr 12 at 15:35
  • $\begingroup$ I see what you're saying, so If i let $T = \emptyset$ and run the implication solver on $T$ and $A$ to see whether or not $T \models A$ I come to a decision as to whether or not $A$ is valid or not? I guess i'm just confused because she used the definition to prove $T$ satisfiable or unsatisfiable so I thought we had to prove the fact about $T$, but i guess this isn't explicitly explained anywhere in the question. $\endgroup$ – MattyS11 Apr 12 at 17:33
  • $\begingroup$ @MattyS11 She proved facts about $T$ because the decision problem asks questions about $T$, i.e., is $T$ satisfiable. We need to prove things about $A$, in particular, whether $A$ is valid or not. $\endgroup$ – James Apr 12 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.