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$

  • 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.2012-07-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?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
    $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.2012-07-05
  • 0
    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.2012-07-05
  • 0
    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.2012-07-05
  • 0
    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$.2012-07-05
  • 0
    @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$.2012-07-05
  • 0
    @CarlMummert I don't see why this works. Then $A$ must be expanded to be a structure in the new language. $c$ must be interpreted as something in the model $A$ of this new language. I don't see the counterexample.2012-07-05
  • 0
    @William: I deleted that comment. I see two ways at the moment to interpret the question to get a counterexample. The first is that $A$ is a theory, rather than a structure. The second is that $A$ is a structure, the formulas have free variables, and a certain definition of $\models$ is being employed. There is a somewhat common convention in which $A \models \phi$ means that $A$ satisfies the universal closure of $\phi$; then $A \models \phi \to \psi$ means $A$ satisfies the universal closure of $\phi \to \psi$. In this convention the example André Nicolas gives is correct. ...2012-07-05
  • 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.

  • 0
    Hm.. but we're told to disprove this.. I think it's got something to do with free variables..2012-07-05
  • 0
    @William I don't think that's the correct interpretation of $A\models \phi\to \psi$.2012-07-05
  • 0
    @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.2012-07-05
  • 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.2012-07-05
  • 0
    @goklo $A \models \phi$ is not defined unless $\phi$ has no free variables (is a sentence). $A \models \phi(\bar{a})$ also makes sense where $\bar{a} \in A^n$ and $\phi$ has free variable $\bar{x}$. However, in this case you will not find a counterexample either.2012-07-05
  • 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