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$
2
-
2$\begingroup$ 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. $\endgroup$– Asaf Karagila ♦Jul 5, 2012 at 7:05
-
1$\begingroup$ 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? $\endgroup$– Carl MummertJul 5, 2012 at 9:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
8
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.
answered Jul 5, 2012 at 6:49
-
$\begingroup$ $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. $\endgroup$– WilliamJul 5, 2012 at 6:53
-
$\begingroup$ 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. $\endgroup$– WilliamJul 5, 2012 at 6:57
-
$\begingroup$ 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. $\endgroup$ Jul 5, 2012 at 6:57
-
$\begingroup$ 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$. $\endgroup$ Jul 5, 2012 at 6:59
-
$\begingroup$ @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$. $\endgroup$– WilliamJul 5, 2012 at 7:01
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ Hm.. but we're told to disprove this.. I think it's got something to do with free variables.. $\endgroup$– gokloJul 5, 2012 at 6:40
-
$\begingroup$ @William I don't think that's the correct interpretation of $A\models \phi\to \psi$. $\endgroup$ Jul 5, 2012 at 6:42
-
$\begingroup$ @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. $\endgroup$– WilliamJul 5, 2012 at 6:45
-
1$\begingroup$ @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. $\endgroup$ Jul 5, 2012 at 6:48
-
1$\begingroup$ @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. $\endgroup$ Jul 5, 2012 at 9:29