Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It's predicate logic and I need to find a counterexample to disprove the follwowing claim

$(A \models \phi \implies A \models \psi) \implies A \models \phi \rightarrow \psi$

share|improve this question
2  
You will have to give us the definition of the satisfaction relation $(\models)$ and what do you require of $\phi,\psi$, as you can see from the answers and their comments: it is unclear. –  Asaf Karagila Jul 5 '12 at 7:05
1  
In particular, there are multiple definitions of $\models$ in the literature. These all agree on sentences, but for formulas with free variables they differ. In particular, you can ask whether your system satisfies $(A \models \phi) \to (A \models (\forall x)\phi)$. Some do and some do not. Which textbook are you following in your class? –  Carl Mummert Jul 5 '12 at 9:32

2 Answers 2

Some people define a formula (with free occurrences of variables) to be true in the structure $A$ if the sentence obtained by universally quantifying these variables is true in $A$. Then annoying things can happen, which is why I prefer not to do it.

For an informal example, let $A$ be the natural numbers, let $\phi(x)$ be the formula that says $x$ is even, and let $\psi(x)$ be the formula that says $x$ is odd. (It is not hard to write down the appropriate formulas.) Then it is not the case that $\phi$ is true in $A$. It follows that $A \models \phi \implies A \models \psi$ is true. But $ A \models \phi \rightarrow \psi$ is false, since it is not the case that for all $x$, if $x$ is even then $x$ is odd.

Remark: Expressing commutativity of addition as $x+y=y+x$ rather than $\forall x\forall y(x+y=y+x)$ is a useful abbreviation. However, building that abbreviation into the logic introduces complications, as illustrated by the example above.

share|improve this answer
    
$A \models \phi$ is not defined unless $\phi$ is a sentence. In your example, you need to add some quantifier in front of $\phi$ and $\psi$. Quantifers do not pull out of implications so the problem does not occur. –  William Jul 5 '12 at 6:53
    
In your example, $A \not\models (\forall x)\phi$ and $A \not\models (\forall x)(\psi)$. So $A \models (\forall x)(\phi) \Rightarrow A \models (\forall x)(\psi)$. However, $A \models (\forall x)(\phi) \rightarrow (\forall x)(\psi)$. Note that $(\forall x)(\phi) \rightarrow (\forall x)(\psi) \equiv (\exists x)\neg\phi \vee (\forall x)\psi$ so you can not pull the universal quantifier out. –  William Jul 5 '12 at 6:57
    
I have seen presentations in which $A\models \phi$ is defined for formulas. As you point out in your answer, there cannot be a counterexample if we restrict to sentences. –  André Nicolas Jul 5 '12 at 6:57
    
Wait, I thought that "$A\models \phi\implies A\models \psi$" was true iff for any structure $A$ such that $A\models \phi$, we have $A\models \psi$. –  Alex Becker Jul 5 '12 at 6:59
    
@AlexBecker No, you may be the thinking of the following. The symbol $T \models \phi$ means $A \models \phi$ for all $A \models T$, where $T$ is some theory. By the completeness theorem, its is equivalent to $T \vdash \phi$. –  William Jul 5 '12 at 7:01

I don't think there is a counterexample.

Suppose $A \models \phi \rightarrow \psi$ is false. This can only happen if $A \models \phi$ and $A \not\models \psi$. Hence $(A \models \phi \Rightarrow A \models \psi)$ is false.

share|improve this answer
    
Hm.. but we're told to disprove this.. I think it's got something to do with free variables.. –  goklo Jul 5 '12 at 6:40
    
@William I don't think that's the correct interpretation of $A\models \phi\to \psi$. –  Alex Becker Jul 5 '12 at 6:42
    
@AlexBecker $\phi \rightarrow \psi$ is $\neg\phi \vee \psi$. $A \models \kappa \vee \lambda$ if and only if $A \models \kappa$ or $A \models \lambda$. I think this is just the definition. –  William Jul 5 '12 at 6:45
1  
@William It does make sense to me. That's just the only possible issue I can find with your answer, so if the OP's is correct, then that's where the error must be. Also, after computability theory this year "it makes sense to me" is my #1 red flag when recalling a definition in logic. –  Alex Becker Jul 5 '12 at 6:48
1  
@William: see my comment on the answer by André Nicolas. Many authors do define $A \models \phi$ when $\phi$ is an arbitrary formula. There are two ways that this is done. One way is to include with $A$ a variable assignment, and say that $A \models \phi$ if $\phi$ holds with that assignment of free variables. Another way is to say that $A \models \phi$ if $A$ satisfies the universal closure of $\phi$, in other words a universal quantifier is taken over the variable assignments. These two conventions lead to different results. –  Carl Mummert Jul 5 '12 at 9:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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