1
$\begingroup$

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$

  • 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?2012-07-05

2 Answers 2

7

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.

  • 0
    In my experience that convention is most common in settings where they will mostly be studying algebraic theories whose only relation symbol is equality. In that case they are really interested in whether an *equation* holds in a structure, or whether being the solution to one equation implies being a solution to another, etc.2012-07-05
2

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.

  • 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.2012-07-05